Linux Kernel Architecture

Chapter 4: Virtual Process Memory

4.4.1 Trees and Lists

Each region is described by an instance ofvm_area_struct, and the regions of a process are sorted in

two ways:

1. On a singly linked list (starting withmm_struct->mmap).


2. In a red-black tree whose root element is located inmm_rb.

mmap_cacheis a cache for the region last handled; its meaning will become clear in Section 4.5.1.

Red-black treesare binary search trees whose nodes also have a color (red or black). They exhibit all the

properties of normal search trees (and can therefore be scanned very efficiently for a specific element).

The red-black property also simplifies re-balancing.^5 Readers unfamiliar with this concept are referred

to Appendix C, which deals extensively with the structure, properties, and implementation of red-black

trees.

The start and end addresses describe each region in virtual user address space. The existing regions

are included in the linked list in ascending order of start address. Scanning the list to find the region

associated with a particular address is a very inefficient operation if there are a very large number of

regions (as is the case with data-intensive applications). The individual instances ofvm_area_structare

therefore also managed in a red-black tree, which speeds up scanning considerably.

To add a new region, the kernel first searches the red-black tree for the region immediately preceding the

new region. With its help, it can add the new region to the tree and also to the linear list without having

to explicitly scan the list (the algorithm used by the kernel to add new regions is discussed at length in

Section 4.5.3). Finally, the situation in memory is illustrated in Figure 4-6. Notice that the representation

of the tree is only symbolic and does not reflect the real layout, which is more complicated.

mm

mmap struct vm_area_struct

Red_Black

tree

mmap_rb

struct

task_struct

struct

mm_struct

Manage vm_area_structs

associated with a process

Figure 4-6: Association ofvm_area_structinstances with the virtual process space of a

process.

(^5) All important tree operations (add, delete, find) can be performed inO(logn),wherenis the number of elements in the tree.