[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
• 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
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
Size: 198 bytes
Desc: not available
More information about the bind10-dev