Trees I: Radix trees

Wikipedia hasa radixtree article, but Linux radix trees are not well described by thatarticle. A Linux radix tree is a mechanism by which a (pointer) value canbe associated with a (long) integer key. It is reasonably efficient in terms ofstorage, and is quite quick on lookups. Additionally, radix trees in theLinux kernel have some features driven by kernel-specific needs, includingthe ability to associate tags with specific entries.

The cheesy diagram on the right shows a leaf node from a Linux radix tree.The node contains a number of slots, each of which can contain a pointer tosomething of interest to the creator of the tree. Empty slots contain aNULL pointer. These trees are quite broad - in the 2.6.16-rckernels, there are 64 slots in each radix tree node. Slots are indexed bya portion of the (long) integer key. If the highest key value is less than64, the entire tree can be represented with a single node.Normally, however, a rather larger set of keys is in use - otherwise, asimple array could have been used. So a larger tree might look somethinglike this:

This tree is three levels deep. When the kernel goes to look up a specifickey, the most significant six bits will be used to find the appropriateslot in the root node. The next six bits then index the slot in the middlenode, and the least significant six bits will indicate the slot containing apointer to the actual value. Nodes which have no children are not presentin the tree, so a radix tree can provide efficient storage for sparsetrees.

Radix trees have a few users in the mainline kernel tree. The PowerPCarchitecture uses a tree to map between real and virtual IRQ numbers. TheNFS code attaches a tree to relevantinode structures to keeptrack of outstanding requests. The most widespread use of radix trees,however, is in the memory management code. Theaddress_spacestructure used to keep track of backing store contains a radix tree whichtracks in-core pages tied to that mapping. Among other things, this treeallows the memory management code to quickly find pages which are dirty orunder writeback.

As is typical with kernel data structures, there are two modes fordeclaring and initializing radix trees:

    #include <linux/radix-tree.h>    RADIX_TREE(name, gfp_mask);  /* Declare and initialize */    struct radix_tree_root my_tree;    INIT_RADIX_TREE(my_tree, gfp_mask);

The first form declares and initializes a radix tree with the givenname; the second form performs the initialization at run time. Ineither case, agfp_mask must be provided to tell the code howmemory allocations are to be performed. If radix tree operations(insertions, in particular) are to be performed in atomic context, thegiven mask should beGFP_ATOMIC.

The functions for adding and removing entries are straightforward:

    int radix_tree_insert(struct radix_tree_root *tree, unsigned long key,                           void *item);    void *radix_tree_delete(struct radix_tree_root *tree, unsigned long key);

A call toradix_tree_insert() will cause the givenitemto be inserted (associated withkey) in the giventree. Thisoperation may require memory allocations; should an allocation fail, theinsertion will fail and the return value will be-ENOMEM. Thecode will refuse to overwrite an existing entry; ifkey alreadyexists in the tree,radix_tree_insert() will return-EEXIST. On success, the return value is zero.radix_tree_delete() removes the item associated withkeyfromtree, returning a pointer to that item if it was present.

There are situations where failure to insert an item into a radix tree canbe a significant problem. To help avoid such situations, a pair of specializedfunctions are provided:

    int radix_tree_preload(gfp_t gfp_mask);    void radix_tree_preload_end(void);

This function will attempt to allocate sufficient memory (using the givengfp_mask) to guarantee that the next radix tree insertion cannotfail. The allocated structures are stored in a per-CPU variable, meaningthat the calling function must perform the insertion before it can scheduleor be moved to a different processor. To that end,radix_tree_preload() will, when successful, return with preemptiondisabled; the caller must eventually ensure that preemption is enabledagain by callingradix_tree_preload_end(). On failure,-ENOMEM is returned and preemption isnot disabled.

Radix tree lookups can be done in a few ways:

    void *radix_tree_lookup(struct radix_tree_root *tree, unsigned long key);    void **radix_tree_lookup_slot(struct radix_tree_root *tree, unsigned long key);    unsigned int radix_tree_gang_lookup(struct radix_tree_root *root,                                         void **results,unsigned long first_index, unsigned int max_items);

The simplest form,radix_tree_lookup(), looks forkey inthetree and returns the associated item (orNULL onfailure).radix_tree_lookup_slot() will, instead, return apointer to the slot holding the pointer to the item. The caller can, then,change the pointer to associate a new item with thekey. If theitem does not exist, however,radix_tree_lookup_slot() will notcreate a slot for it, so this function cannot be used in place ofradix_tree_insert().

Finally, a call toradix_tree_gang_lookup() will return up tomax_items items inresults, with ascending key valuesstarting atfirst_index. The number of items returned may be lessthan requested, but a short return (other than zero) does not imply thatthere are no more values in the tree.

One should note that none of the radix treefunctions perform any sort of locking internally. It is up to the callerto ensure that multiple threads do not corrupt the tree or get into othersorts of unpleasant race conditions. Nick Piggin currently has a patchcirculating which would use read-copy-update to free tree nodes; this patchwould allow lookup operations to be performed without locking as long as(1) the resulting pointer is only used in atomic context, and(2) the calling code avoids creating race conditions of its own. Itis not clear when that patch might be merged, however.

The radix tree code supports a feature called "tags," wherein specific bitscan be set on items in the tree. Tags are used, for example, to markmemory pages which are dirty or under writeback. The API for working withtags is:

    void *radix_tree_tag_set(struct radix_tree_root *tree,unsigned long key, int tag);    void *radix_tree_tag_clear(struct radix_tree_root *tree,unsigned long key, int tag);    int radix_tree_tag_get(struct radix_tree_root *tree,unsigned long key, int tag);

radix_tree_tag_set() will set the giventag on the itemindexed bykey; it is an error to attempt to set a tag on anonexistent key. The return value will be a pointer to the tagged item.Whiletag looks like an arbitrary integer, thecode as currently written allows for a maximum of two tags. Use of any tagvalue other than zero or one will silently corrupt memory in someundesirable place; consider yourself warned.

Tags can be removed withradix_tree_tag_clear(); once again, thereturn value is a pointer to the (un)tagged item. The functionradix_tree_tag_get() will check whether the item indexed bykey has the giventag set; the return value is zero ifkey is not present, -1 ifkey is present buttagis not set, and +1 otherwise. This function is currently commented out inthe source, however, since no in-tree code uses it.

There are two other functions for querying tags:

    int radix_tree_tagged(struct radix_tree_root *tree, int tag);    unsigned int radix_tree_gang_lookup_tag(struct radix_tree_root *tree,                                             void **results,    unsigned long first_index,     unsigned int max_items,     int tag);

radix_tree_tagged() returns a non-zero value if any item in thetree bears the giventag. A list of items with a given tag can beobtained withradix_tree_gang_lookup_tag().

In concluding, we can note one other interesting aspect of the radix treeAPI: there is no function for destroying a radix tree. It is, evidently,assumed that radix trees will last forever. In practice, deleting allitems from a radix tree will free all memory associated with it other thanthe root node, which can then be disposed of normally.