wiki:AclDesign

ACL implementation design

The basic mechanism would consist of two areas. One would be the actual checking classes, which get a message together with some other information (we would call it ACL context probably), like IP address, possible scratchpad areas for the checkers themselfs, and would return if it matches or not. The other part would be the loader, which gets part of JSON description (probably in form of ConstElementPtr?) and produces ACL object representing this ACL, optionally remembering it under a name.

The checking classes

We would have an abstract base class defining interface of the ACL checking class. Such interface should define the checking function itself, something like

virtual bool check(ConstMessagePtr message, ACLContext &context) const = 0;

Or, optionally, the message could be hidden inside the context as well, for consistency. The context would contain all the needed information (IP address, some scratchpad areas in future used in optimisations (see below for them)).

Another function that would be nice to have is something that would return expected cost of the match in some relative units, because of optimisations. The real checks would return some constant (let's say IPCheck could be 1, TSIG check 10), a compound check would probably be some sum of its subexpressions. This one could have a default with some really huge number („unknown“ cost would be considered big to be on the safe side on the optimisations). As this would be used for heuristics, this doesn't need to be something really exact.

Another derived virtual base class would add an ability to list direct subexpressions/subACLs. The composition ACLs would be derived from this to allow walking the tree in optimisations. They could provide some kind of iterators or just a vector of the shared pointers to them (the conversion/copy wouldn't be problem, they would be used at the loading time only, not in the performance-critical parts).

The class hierarchy would look something like this:

ACLChecker
   |
   +-- IPCheck
   |
   +-- TSIGCheck
   |
   +-- SizeChek
   |
   +-- …
   |
   +-- CompoundACL
          |
	  +-- ANY_OF
	  |
	  +-- ALL_OF
	  |
	  +-- NOT
	  |
	  +-- FIRST_MATCH

Of course, this doesn't name exact class names and deviations are allowed, like ANY_OF and ALL_OF could have a common ancestor to share most of their code, or something.

In general, each of these concrete classes would get relevant part of the JSON configuration in their constructor, to know their respective parameters. The compound ACLs would use the loader to load their subexpressions recursively. If the configuration would be misformatted or otherwise bad, they would throw exception, aborting the creation of whole ACL structure.

The loader

The loader would have several related functionalities to provide its main goal ‒ transforming JSON descriptions into created objects of some ACLChecker subclass.

Registration of types

To allow adding new checking types without modifying this class (which will, eventually, allow writing custom plugins for ACLs and such), it would provide an interface to add a new type of ACL checker. Upon registration, a factory function (or functor) would be passed (one that would get part of JSON and would call the constructor of the correct ACLChecker class), the desired name of this type and some other properties (like if it wants to participate in the OR-abbreviated form, as described in AclSyntax). Optionally, deregistration might be needed in future as well to allow reloading/unloading the plugins, but this probably wouldn't be needed as for now.

Loading the ACLs from JSON

In the simple form, it would get a dict with single key-value pair, look up the factory function for this name of type and pass the value to it (handling situations like the name does not exist, etc).

For the support of the abbreviated forms, it would need to know about the ANY_OF and ALL_OF checkers explicitly and examine the structure of the JSON data more closely ‒ if the dict contains more than one pair, it would create a ALL_OF and place them one by one into it. Similarly, if the constructed type would like to participate in the OR-abbreviated form and it's parameter is a list, it would create an ANY_OF instead and iterate trough the values, creating one instance of the type for each of the values, placing them inside the ANY_OF.

Remembering named ACLs

It should be possible to load the ACLs under a name from configuration (so both application can use it when referring to some ACL in it's configuration and allowing other ACLs to use named subACLs).

This will need a map (or something similar) to remember them, function to load them with name (by passing name and JSON, not JSON only).

For the loading of named ones, if a string is passed instead of dict to the loading function, it would look it up in the map. However, this will need a cycle-protection, as noted in AclSyntax.

Optimisation runs

After the whole tree of the ACL is built, we'll need eventually to optimise it (replacing parts of the tree containing IP address checks only with radix trees, reordering of logic operator subexpressions by expected matching cost, etc). For this to work, there should be a possibility to register functions to be run on the ACL tree. These would be called before returning the final tree to the user or storing it under a name.

We don't want to hardcode the optimisations into the loader, custom checks might want custom optimisations.

As the order of functions matter, we either want to run them in cycles until all of them say „I didn't optimise anything“ or allow pluging them into any place in the chain.

Reusability considerations

As pointed out, it might be nice to be able to reuse the whole thing for other ACLish purposes. So we probably should build all this as a template depending on what kind of context (if the message is hidden inside) is used. Then most of the work could be reused (the loader, compound ACLs, maybe even checks for IP address or any other item that is named the same in the context). We would then just have something like this for the ACLs:

class Context {
        ConstMessagePtr message;
        // IP address, etc…
};

template<class Context> class GenericLoader {
        ...
};

template<class Context> class GenericACL {

};

namespace dns {
typedef GenericLoader<Context> Loader;
typedef GenericACL<Context> ACL;
}

(Of course, after splitting into files, with proper names and namespaces, etc.)

Mapping to tickets and to functionality

This would be the whole dependency graph of tasks:

ACL Base class (#977)
  |
  +-- IPChek
  |
  +-- TSIGCheck
  |
  +-- …
  |
  +-- Simplified loader (#978)
        |
	+-- Named loader (#982)
	|     |
	|     +-- Python wrappers (#983)
	|     |      |
	|     |      +-- Configuration plugin (#768)
	|     |      |
	|     |      +-- Integration into python program
	|     |
	|     +-- Integration into C++ program
	|
	+-- NOT operator (#981)
	|
	+-- FIRST-MATCH operator
	|
	+-- ANY-OF and ALL-OF operators (#979)
	      |
	      +-- Abbreviated form loader (#980)
	            |
		    +-- The optimisations (to be expanded to more detail)

These list code-level dependencies. However, to get something working functionally-wise, we need both intogration into some program and the configuration plugin (it's not possible to configure it without it or check it after user) and at last one checking class.

To get something practically usable, we need the NOT and ANY-OFF/ALL-OF. Providing the abbreviated form loader would increase the convenience a lot and the first match operator would be wanted by many people probably.

Some other checks and the optimisations can probably wait.

Proposed optimisations

We would like to do some optimisations in the end. This describes which ones we thought about and how they could be performed. But first, what is the scratchpad in context.

Sometimes, we need to perform some operation to do a property check that is not entirely cheap. But the same operation would be done when matching the message against a different property value. The scratchpad would allow to have a place for related kinds of checks to save this operation for further use or to place a precomputing pseudo-check in front of the whole checking.

  • Reordering of the checks in single ANY-OF or ALL-OF, so that cheap ones are placed first. In case they supply the result of the whole ANY-OF or ALL-OF, the expensive ones would be avoided.
  • Using radix trees for IP checks. If there would be a subtree (or, not necessarily a subtree, if there's a bunch of checks for IP addresses in ANY-OF or ALL-OFF), it could be replaced by single radix-tree lookup. We can do it by marking DFS-traversing the tree and locating the component of IP-checks-only. Then we would partition the IP namespace into components of equivalence and then choosing a representant from each component, simulating the match on it. Then we could merge continuous bits of same results and transform this into a radix tree.
  • Converting this to doing only one radix tree at the beginning of processing. It would have an bitarray as a result and each of the above small radix trees would be replaced by single indexing of this array. This array would be stored inside the scratchpad area.
  • Doing only one TSIG check at the beginning (we need to do it anyway if the message is signed), storing the key used into the scratchpad and just checking the key is the one in separate checks.
  • Finding common subexpressions, computing them only at the first occurence and reusing the result on successive ones, for example by wrapping the subexpression into a pseudo-ACL check that would first look into a scratchpad and if the result is not there, call the subexpression, store it and return it.
  • Producing C++ code of the whole tree (or the parts that support it, it could call the checks which don't support it directly), compiling it and loading as .so. This would bring the whole bunch of optimisations compilers have in them, which is a lot more than we can handle, it could be optimised for specific hardware, avoid many virtual method calls and we could do it in two phases, compile it the first time, produce a profile and then compile with the profiling information, adapting it to the real traffic the server would get. The whole thing could be done in background, something that JIT compilers do. This could be both potentially strong optimisation and a geek magnet ;-).
Last modified 6 years ago Last modified on Jun 2, 2011, 11:25:38 AM