Linux Kernel Architecture

Chapter 16: Page and Buffer Cache

The tagging information is stored in a two-dimensional array (tags)thatisapartofradix_tree_node.

The first array dimension distinguishes between the possible tags, and the second contains a sufficient

number of elements ofunsigned longs so that there is a bit for each page that can be organized in the

node.

radix_tree_tag_setis used to set a flag for a specific page:

<radix-tree.h>

void *radix_tree_tag_set(struct radix_tree_root *root,

unsigned long index, unsigned int tag);

The kernel searches for the corresponding positions in the bit list and sets the bit to 1. When this is done,

the tree is scanned from top to bottom to update the information in all nodes.

In order to find all pages with a certain tag, the kernel still has to scan the entire tree, but this operation

can be accelerated by first filtering out all subtrees that containat least onepage for which the flag is set.

Again, this can be speeded up because the kernel does not check each bit one after the other but simply

checks whether at least one of theunsigned longvariables in which the bits are stored is greater than 1:

lib/radix-tree.c

int radix_tree_tagged(struct radix_tree_root *root, int tag)

{

int idx;

if (!root->rnode)

return 0;

for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) {

if (root->rnode->tags[tag][idx])

return 1;

}

return 0;

}

Accessing Radix Tree Elements

The kernel also provides the following functions to process radix trees (they are all implemented in

lib/radix_tree.c):

<radix-tree.h>

int radix_tree_insert(struct radix_tree_root *, unsigned long, void *);

void *radix_tree_lookup(struct radix_tree_root *, unsigned long);

void *radix_tree_delete(struct radix_tree_root *, unsigned long);

int radix_tree_tag_get(struct radix_tree_root *root,

unsigned long index, unsigned int tag);

void *radix_tree_tag_clear(struct radix_tree_root *root,

unsigned long index, unsigned int tag);

❑ radix_tree_insertadds a new element to a radix tree by means of avoidpointer. The tree is

automatically expanded if too little capacity is available.

❑ radix_tree_lookupfinds a radix tree element whose key — an integer — was passed to the

function as argument. The value returned is avoidpointer that must be converted to the appro-

priate target data type.