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 of address_space, the radix_tree_root structure 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;

□ height specifies 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_mask specifies the zone from which memory is to be allocated.

□ rnode is a pointer to the first node element of the tree. The radix_tree_node date type discussed below is used for this node.

Continue reading here: Implementation

Was this article helpful?

0 0