Linux Kernel Architecture

Mauerer app03.tex V1 - 09/04/2008 6:11pm Page 1217

Appendix C: Notes on C

void *slots[RADIX_TREE_MAP_SIZE];

unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];

};

slotsis an array of pointers that, according to their position in the tree (i.e., the level on which the node
is located), point either to other nodes or to data elements.countindicates the number of occupied array
positions. The macros defined in the code segment specify statically how many array positions there are
in each node. By default, the kernel uses 2^6 =64. Empty slots are given a null pointer.

Every tree node can be associated withtagsthat correspond to a set or an unset bit. Per node, a maximum
ofRADIX_TREE_MAX_TAGSdifferent tags are possible, the default setting is a meager 2. This is, however
sufficient for the page cache.

The RCU mechanism (described in Chapter 5) is used to allow lock-free radix tree lookups.

An array ofunsigned longs is used to represent the tags, andRADIX_TREE_TAG_LONGSis computed
by the kernel such that sufficient storage space is available to hold the tags. Alongarray with
RADIX_TREE_MAX_TAGS*RADIX_TREE_TAG_LONGScontains enough bits to attachRADIX_TREE_MAX_TAGS
tags to each slot. The functionsradix_tree_tag_setandradix_tree_tag_clearare provided to set
and clear tag bits, respectively. Notice that a tag is not only set in the leaf entry, but in every entry from
root to bottom.

The tree root is defined by the following data structure (notice that this definition is in a public visible
header file, in contrast to the definition of tree nodes):

<radix-tree.h>

struct radix_tree_root {

unsigned int height;

gfp_t gfp_mask;

struct radix_tree_node *rnode;

};

heightspecifies the current height of the tree, andrnodepoints to the first node.gfp_maskspecifies the
memory area from which the required data structure instances of the tree are to be taken.

The maximum number of elements that can be stored in a tree can be derived directly from the tree
height — that is, from the number of node levels. The kernel provides the following function to compute
the height:

lib/radix-tree.c

static inline unsigned long radix_tree_maxindex(unsigned int height)

{

return height_to_maxindex[height];

}

height_to_maxindexis an array that stores the maximum number of elements for different tree heights.
The number is computed when the system is initialized as shown here:

lib/radix-tree.c

#define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsigned long))

#define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \

RADIX_TREE_MAP_SHIFT))