Kernel basis(2): radix trees

Abstract: this article talks about the data structure radix trees and its usage in Linux kernel.

1. What is a radix tree?
As described by wikipedia, A radix tree, Patricia trie/tree, or crit bit tree is a specialized set data structure based on the trie that is used to store a set of strings.


2. Linux kernel radix tree internals

struct radix_tree_root {
unsigned int  height;
gfp_t   gfp_mask;
struct radix_tree_node *rnode;
};

struct radix_tree_node {
unsigned int height;  /* Height from the bottom */
unsigned int count;
struct rcu_head rcu_head;
void *slots[RADIX_TREE_MAP_SIZE];
unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
};
#ifdef __KERNEL__
#define RADIX_TREE_MAP_SHIFT (CONFIG_BASE_SMALL ? 4 : 6)
#else
#define RADIX_TREE_MAP_SHIFT 3 /* For more stressful testing */
#endif

In Linux kernel, each radix tree node has 16/64 slots and can be indexed by a portion of the integer key. The leaf node points to the content. Empty slots contain a NULL pointer. For example, each node of the above three levels radix tree is indexed by 6 bits of the key. Nodes that have no children are not presented. Thus radix tree can be used to store sparse files.

3. Usage
In vanilla kernel, the PowPC architecture uses a radix tree to map real and virtual IRQ numbers. The NFS code uses a radix tree to index inode structures to keep track of outstanding requests. The address_space structure used to keep track of backing store contains a radix tree which tracks in-core pages tied to that mapping. Among other things, this tree allows the memory management code to quickly find pages which are dirty or under writeback.

4. How to use radix trees?
There are two ways to initialize a radix tree:

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

The first approach is simply a wrapper of combination of the latter one.
Then all functions defined in linux/radix-tree.h can be used to manipulate the tree.

5. Notes
(1)Synchronization
The radix-tree API requires users to provide all synchronizations(with some specific exceptions).
For API usage, in general,
- any function _modifying_ the tree or tags (inserting or deleting
items, setting or clearing tags) must exclude other modifications, and
exclude any functions reading the tree.
- any function _reading_ the tree or tags (looking up items or tags,
gang lookups) must exclude modifications to the tree, but may occur
concurrently with other readers.

The notable exceptions to this rule are the following functions:
radix_tree_lookup
radix_tree_lookup_slot
radix_tree_tag_get
radix_tree_gang_lookup
radix_tree_gang_lookup_slot
radix_tree_gang_lookup_tag
radix_tree_gang_lookup_tag_slot
radix_tree_tagged
(1)Destroying a radix tree.
There is no function for destroying a radix tree. It is, evidently, assumed that radix trees will last forever. In practice, deleting all items from a radix tree will free all memory associated with it other than the root node, which can then be disposed of normally.

6. Reference:
http://lwn.net/Articles/175432/
http://en.wikipedia.org/wiki/Radix_tree