[bind10-dev] ACL Syntax proposal

Michal 'vorner' Vaner michal.vaner at nic.cz
Sun May 29 10:38:46 UTC 2011


On Sat, May 28, 2011 at 08:40:12PM +0000, Evan Hunt wrote:
> It also might not process as quickly, depending on how we code things.
> With a first-match ACL, in principle you try the first rule and if you
> get a match you're done, whereas with a boolean expression you might need
> to walk a syntax tree to be sure you've covered everything.  We'll need to
> be careful about that.

Well, with boolean expression, you might as well be lucky, if you have an OR and
the first one is true, you're done as well. And in the first-match, if nothing
matches, you need to walk it as well.

Anyway, naïve implementation of the syntax I describe would probably run slower
in most cases, because of need to call some virtual methods and so on. But just
from short thinking about it, I see various places where optimisation could
happen (sorted by craziness):

• Usual expression optimisations, like trying to flatten it a little, finding
  common subexpressions.
• Reordering OR and AND subexpressions to get the cheaper ones first (this can
  be computed or at last estimated, IP address check is cheaper than TSIG one
  and that one is probably cheaper than calling some unknown python code). So
  there's a chance the cheap one will answer the question and the rest won't be
• Property-based tricks, like dividing address space into equivalence classes,
  using a radix tree to identify the class the address belongs to and replacing
  all address checks with bitwise and between accepted classes and the class we
  got (which could be up to 128 bits long almost for free, if we have SSE).
  Single bitwise check could replace whole subtree of IP-address based checks.
  Or running TSIG check only once, at the first place it's needed and
  note down the key used to sign it (well, actually, we need to perform the TSIG
  validation even if no ACL uses it, so it can be as well prepared before even
  running any ACL).
• Creating C/C++ code at runtime, compiling it into an .so automatically and
  loading it. This would let lose the whole army of optimisations of compiler to
  our ACLs, would eliminate any virtual calls inside the tree and could
  inline/interlink the checks between themself, down to the instruction
  interleaving level. If we were really crazy, we could compile it with
  profiling instrumentation, let it run for a while and then recompile again,
  adapting it to actual network traffic pattern. Or at last create a tool that
  generates the code and lets the admin call it manually and create his own
  customized ACL plugin.

As this happens at the time we load the ACLs, not at every check, we can do
quite a lot I guess. But we should start with the naïve approach first and see
how slow it is.

> You may want to take a look at the underlying data structure for ACLs
> in BIND 9 (though it will hurt your head to do so, and I will need to buy
> you a recreational beverage of your choice to apologize for the way I
> wrote it).

I'd love to, but I don't know if there's enough time for studying it. Maybe I'll
enjoy it when there'll be the need to optimise it ;-). So, for now, I just take
the description.

Thanks a lot

Wait few minutes before opening this email. The temperature difference 
could lead to vapour condensation.

Michal 'vorner' Vaner
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: not available
URL: <https://lists.isc.org/pipermail/bind10-dev/attachments/20110529/f41b7126/attachment.bin>

More information about the bind10-dev mailing list