Linux Kernel Architecture

Chapter 4: Virtual Process Memory

priority tree that contains allvm_area_structinstances describing the mapping of an interval of the

file associated with the inode into some virtual address space. Since each instance ofstruct vm_area

contains a pointer to themm_structof the process to which it belongs, the desired connection is set up!

Note thatvm_area_structs can also be associated with an address space via a doubly linked list headed

byi_mmap_nonlinear.Thisisrequiredfornonlinear mappings, which I neglect for now. I will come back

to them in Section 4.7.3, though.

i_mapping

struct

file

i_mapping

i_mmap

i_mmap_nonlinear

host

struct

file

i_mapping

struct inode

vm_mm

vm_mm

vm_mm

mm_struct

Backing

device

mm_struct

mm_struct

struct

address_space

Manage vm_area_structs

associated with a file

struct vm_area_struct

Figure 4-7: Tracking the virtual address spaces into which a given interval of a file is mapped with

the help of a priority tree.

Recall that Figure 4-6 shows howvm_area_structinstances are organized in a linked list and a red-black

tree. It is important to realize that these are thesamevm_area_structinstances that are managed in the

prio tree. While keepingvm_area_structs in two or more data structures at the same time is no problem

for the kernel at all, it is nearly impossible to visualize. Therefore, keep in mind that a given instance of

struct vm_areacan be contained in two data structures: One establishes a connection between a region

in the virtual address space of a process to the data in the underlying file, and one allows for finding all

address spaces that map a given file interval.

RepresentingPriority Trees

Priority trees allow for management of thevm_area_structinstances that represent a particular interval

of the given file. This requires that the data structure cannot only deal withoverlapping, but also with

identicalfile intervals. The situation is illustrated in Figure 4-8: Two processes map the region [7, 12] of a

file into their virtual address space, while a third process maps the interval [10, 30].

Managing overlapping intervals is not much of a problem: The boundaries of the interval provide a

unique index that allows for storing each interval in a unique tree node. I will not discuss in detail

how this is implemented by the kernel because it rather similar to radix trees (see Appendix C for more

details). It suffices to know that if intervalsB,C,andDare completely contained in another intervalA,

thenAwill be the parent element ofB,C,andD.

However, what happens if multipleidenticalintervals must be included in the prio tree? Each prio

tree node is represented by theraw_prio_tree_nodeinstance, which isdirectly includedin each