Performance Improvement

[Sami Kerola]

08.11.2005 15:28, christ lee <christfer1.lee at gmail.com>:

> I am studying query.c, client.c in BIND9 source code. can u 
> suggest me where to optimize the code in order to improve the 
> performance i.e by decreasing the time taken by the name server. 
> Expecting ur Suggestions........

Hello,

If I read bind sources correctly ACL matchin is linear list 
checking. ACLs should be writen in most used first order, but this 
is nearly impossible. Perhaps ACL list should be AVL tree or heap.

http://en.wikipedia.org/wiki/AVL_tree 
http://en.wikipedia.org/wiki/Binary_heap

Before ACLs can be put into tree they must be cleaned. Basicly 
these are same ACL entry.

10.0.0.0/8	167772160 - 184549375
10.11.12.0/24	168496128 - 168496383

Tree could be build so that there first and last numeric IP of 
range. If something is added to tree it must be checked that begin 
or end point of range is not in any range that is already in tree. 
If either begin or ned is in range but other is not the range 
which matches end or begin must be grown in direction which misses 
the range. Something like this.

10 - 20 && 15 - 25 => 10 - 25

If there is two ranges 10 - 20 and 25 - 30 which are in tree and 
update range is 15 - 28 all three can be joined to be one range 10 
- 30.

Searching from ACL tree should be done either begining or end of 
range. I use begining of range. Lets say IP is X, range smaller is 
RS and range greater is RG. If X >= RS && X <= RG -> match. If X < 
RS go left where is smaller numbers. If X > RS go right. If 
direction returns null ACL matching is over and status is miss.

That should make ACL matching quite much faster if list is long, 
like many ISPs has at allow-query config. With short ACLs tree is 
probably less efficient than currently used list. Perhaps there 
should be some logic when bind chooses to store ACL in tree and 
when in list depending on list lenght.

Unfortunately I am crappy coder so don't ask how big list to tree 
change might be. By quessing I'd say change is bigger than I am 
able to write acceptable code.

-- 
    Sami Kerola
    http://www.iki.fi/kerolasa/