Linux Kernel Architecture

Chapter 16: Page and Buffer Cache

Super-

block

Block

device

Inode Addressspace

Radix tree

Pages

Backing

device

information

Page cache

Readahead

Synchronization

Figure 16-3: Address spaces and their connection with central kernel data

structures and subsystems.

16.3.2 Page Trees

The kernel uses radix trees to manage all pages associated with an address space at least possible cost. A

general overview of trees of this kind was provided above; now the corresponding data structures in the

kernel are focused on.

As is clear from the layout ofaddress_space,theradix_tree_rootstructure is the root element of every

radix tree:

<radix_tree_root.h>

struct radix_tree_root {

unsigned int height;

gfp_t gfp_mask;

struct radix_tree_node *rnode;

};

❑ heightspecifies the height of the tree, that is, the number of levels below the root. On the basis

of this information and the number of entries per node, the kernel is able to calculate quickly

the maximum number of elements in a given tree and to expand the tree accordingly if there is

insufficient capacity to accept new data.

❑ gfp_maskspecifies the zone from which memory is to be allocated.

❑ rnodeis a pointer to the first node element of the tree. Theradix_tree_nodedate type discussed

below is used for this node.