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

structradix_tree_root{unsignedintheight;

gfp_t gfp_mask;structradix_tree_node *rnode;};structradix_tree_node{unsignedintheight; /* Height from the bottom */unsignedintcount;structrcu_head rcu_head;void*slots[RADIX_TREE_MAP_SIZE];unsignedlongtags[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

## No comments:

## Post a Comment