Linux Kernel Architecture

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

Appendix C: Notes on C

node = rcu_dereference(root->rnode);

if (node == NULL)

return NULL;

if (!radix_tree_is_indirect_ptr(node)) {

if (index > 0)

return NULL;

return node;

}

node = radix_tree_indirect_to_ptr(node);

height = node->height;

if (index > radix_tree_maxindex(height))

return NULL;

shift = (height-1) * RADIX_TREE_MAP_SHIFT;

do {

slot = (struct radix_tree_node **)

(node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK));

node = rcu_dereference(*slot);

if (node == NULL)

return NULL;

shift -= RADIX_TREE_MAP_SHIFT;

height--;

} while (height > 0);

return node;

}

Logically, the algorithm for traversing the tree is identical to the one described previously for inserting

new elements. However, searching is a simple operation because the kernel need not concern itself with

allocating new branches. If a slot at any height in the tree has a null pointer and is therefore not present,

the element being searched is not in the tree. Consequently, work can be terminated immediately and a

null pointer can be returned.

C.3 Summary

C is a Spartan language, and one might be tempted at first glance to equate this with simplicity. However,

it is quite the opposite: Despite being frugal, C allows for many tricks of the trade that can be used for

good, but can likewise be abused to create unreadable and unmaintainable code. This chapter described

some of the more off-standard features of C that are required in kernel development to squeeze the last

percents of performance out of hardware. It also briefly introduced you to the internals of the GNU

C compiler, and showed you some optimization techniques. Additionally, the chapter described some

extensions to the C language that are heavily employed in kernel development.

Finally, this chapter covered some standard data structures that are used all over the kernel sources,

and that therefore must be implemented as generically as possible — which again requires you to utilize

some of the finer points of C.