This project proposal is a subtask of smp networking and is elegible for funding independently.

The goal of this project is to implement lockless, atomic and generic Radix and Patricia trees. BSD systems have always used a radix tree for their routing tables. However, the radix tree implementation is showing its age. Its lack of flexibility (it is only suitable for use in a routing table) and overhead of use (requires memory allocation/deallocation for insertions and removals) make replacing it with something better tuned to today's processors a necessity.

Since a radix tree branches on bit differences, finding these bit differences efficiently is crucial to the speed of tree operations. This is most quickly done by XORing the key and the tree node's value together and then counting the number of leading zeroes in the result of the XOR. Many processors today (ARM, PowerPC) have instructions that can count the number of leading zeroes in a 32 bit word (and even a 64 bit word). Even those that do not can use a simple constant time routine to count them:

int
clz(unsigned int bits)
{
    int zeroes = 0;
    if (bits == 0)
        return 32;
    if (bits & 0xffff0000) bits &= 0xffff0000; else zeroes += 16;
    if (bits & 0xff00ff00) bits &= 0xff00ff00; else zeroes += 8;
    if (bits & 0xf0f0f0f0) bits &= 0xf0f0f0f0; else zeroes += 4;
    if (bits & 0xcccccccc) bits &= 0xcccccccc; else zeroes += 2;
    if (bits & 0xaaaaaaaa) bits &= 0xaaaaaaaa; else zeroes += 1;
    return zeroes;
}

The existing BSD radix tree implementation does not use this method but instead uses a far more expensive method of comparision. Adapting the existing implementation to do the above is actually more expensive than writing a new implementation.

The primary requirements for the new radix tree are:

To make the radix tree flexible, all knowledge of how keys are represented has to be encapsulated into a pt_tree_ops_t structure with these functions:

All bit offsets are relative to the most significant bit of the key,

The ptree programming interface should contains these routines:

Add a comment