Linux Kernel Architecture

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

Appendix C: Notes on C

Armed with this information, thecontainer_ofmacro is able to set about extraction of the container

data structure. In the example, the code expands as follows:

const (struct file*) __mptr = (ptr);

(struct file *)( (char *)__mptr - offset;

ptrpoints to thelist_headinstance in the container element. The kernel first creates a pointer__mptr

with the same value whose type is a pointer to the desired target data type — in this case,struct file.

Then the offset information previously computed is used to move__mptrso that it no longer points to the

list element but to the container element. To make sure that the requisite pointer arithmetic is performed

byte-by-byte,__mptris converted into achar*pointer. However, this change is reversed during final

assignment after computation.

C.2.8 Hash Lists

The kernel also provides an adapted version of doubly linked lists that is especially suitable to implement

overflow lists in hash tables. In this case, the list elements are also embedded into other data structures,

but there is an asymmetry between the list head and the list elements:

<list.h>

struct hlist_head {

struct hlist_node *first;

};

struct hlist_node {

struct hlist_node *next, **pprev;

};

The list elements themselves are still doubly linked, but the list head is connected with the list by a

single pointer. The end of the list cannot be accessed in constant time any more, but this is usually never

required for hash lists anyway. Instead, the containing data structure becomes slightly smaller because

only one pointer instead of two is required. To manipulate hash lists, essentially the same API can be

used as for regular lists. The only difference is thatlistmust be replaced byhlist—solist_add_head

will becomehlist_add_head;list_delwill becomehlist_del. It’s all quite logical.

As for lists, it is possible to use the RCU mechanism to provide protection against concurrent access. If

this is desired, the hash list operations must be postfixed with_rcu— for instance,hlist_del_rcuto

delete a list element. See Chapter 5 for a description of the protection that the RCU mechanism offers.

C.2.9 Red-Black Trees

Red-black trees(RB trees) are used when implementing memory management in order to organize sorted

elements in a tree. RB trees are frequently used data structures in computer science because they offer a

good mix of speed and implementation complexity. This section describes some general properties of RB

trees and the data structures used in the kernel without discussing the implementation of the possible

tree operations. (which are covered in the classical textbooks on algorithms).

Red-black trees are binary trees characterized by the following properties:

❑ Each node is either red or black.

❑ Each leaf (or node at the edge of the tree) is black.