[rbldnsd] ipv6 support: beginnings of an ip6trie dataset

[Jeff Dairiki]

On Sat, Mar 02, 2013 at 11:26:55AM -0800, Jeff Dairiki wrote:
> On Sat, Mar 02, 2013 at 09:13:02PM +0400, Michael Tokarev wrote:
>  
> > Now I must find some time to integrate this (and a few other
> > contributions too, which has been done before) into main code.
> >
> > Should we make v6 listings a reality finally?
> 
> Don't pull my code just yet.  I'm continuing to work on it.  I've
> figured out a significantly more memory-efficient layout for the
> trie nodes (and a few other improvements).
> 
> I should have the improved code ready for inspection in two or three
> days.

Okay, it took longer than two or three days, but I've completely
redone the trie implementation (several times, at this point...) I
think it was worth it. The current implementation uses less memory
than the previous one by roughly a factor of three.  For details on
the implementation, see the essay-like comments at the top of btrie.c.

The code is at:

   https://github.com/dairiki/rbldnsd

The actual code is in the 'ipv6' branch:

   https://github.com/dairiki/rbldnsd/tree/ipv6

If you don't want to deal with the git, you can fetch a tarball from:

   https://github.com/dairiki/rbldnsd/tarball/ipv6/rbldnsd.tar.gz


Some notes, in order of decreasing significance:

Untested on Big-Endian Systems
------------------------------

The new trie code does some hairy bit-field packing.  As of yet, it
has only been tested in an Intel, little-endian environment.  I've
attempted to ensure that it should work on big-endian machines, but
that is currently untested.  (Please send me reports of success or
failure.)  (Also see 'tests' below.)

Other Changes
-------------

I've also plugged the new trie code into the ip4trie (and acl)
datasets.  For the ip4trie, with 64k random 32-bit IP4 addresses, the
new code uses less memory by a factor of roughly three.  That means
that the ip4trie dataset (containing only 32-bit addresses) now uses
only 50% more memory than the ip4set dataset.

The ACL dataset now allows both IP4 and IP6 entries.

The NEWS and debian/changelog files, and the rbldnsd.8 man page have
been updated to reflect the changes I've made.  Refer to them for
slightly more detailed descriptions of what has been done.

Tests
-----

There are a number of tests for the new trie code.  Some are written
in C; there are also now some python scripts which test rbldnsd by
running it as a foreground daemon and sending it DNS queries.  Both
the C self-tests and the python tests provide near 100% coverage of
the trie insertion and lookup code. (The test coverage of the "zone
dump" code is spotty at present.)

You can run the tests like this:

  ./configure
  make
  make check

To run the python test scripts, you'll need to have python 2.6 or 2.7
installed, as well as the pydns library (which in debian is in the
python-dns package.)

The new trie code also makes use of run-time assertions (or "sanity
checks").  By default these are disabled, to compile them in, run
configure with the --enable-asserts argument.



Cheers,
Jeff