Linux Kernel Architecture

Chapter 16: Page and Buffer Cache

is transparent to user applications as they do not know whether they are interacting directly with a block

device or with a copy of their data held in memory — the read and write system calls return identical

results in both cases.

Naturally, the situation is somewhat different for the kernel. In order to support the use of cached pages,

anchors must be positioned at the various points in the code that interact with the page cache. The oper-

ation required by the user process must always be performed regardless of whether the desired page

resides in the cache or not. When a cache hit occurs, the appropriate action is performed quickly (this is

the very purpose of the cache). In the event of a cache miss, the required page must first be read from the

underlying block device, and this takes longer. Once the page has been read, it is inserted in the cache

and is, therefore, quickly available for subsequent access.

The time spent searching for a page in the page cache must be minimized to ensure that cache misses are

as cheap as possible — if a miss occurs, the compute time needed to perform the search is (more or less)

wasted. The efficient organization of the cached pagesis, therefore, a key aspect of page cache design.

16.1.1 Managing and Finding Cached Pages

The problem of quickly fetching individual elements (pages) from a large data set (page cache) is not

specific to the Linux kernel. It has long been common to all areas of information technology and has

spawned many sophisticated data structures that have stood the test of time. Tree data structures of

various kinds are very popular, and Linux also opts for such a structure — known as a radix tree — to

manage the pages held in page caches.

Appendix C provides a more detailed description of this data structure. This chapter gives a brief

overview of how the individual pages are organized in the structure.

Figure 16-1 shows a radix tree in which various instances of a data structure (represented by squares) are

interlinked.^1

height = 2

ptr =

P

t

r

Count

P

t

r

P

t

r

P

t

r

P t r P t r

Count

P

t

r

P

t

r

P

t

r

P

t

r

P

t

r

Count

P

t

r

P

t

r

P

t

r

P

t

r

struct page

PAGECACHE_TAG_DIRTYPAGECACHE_TAG_WRITEBACK

Figure 16-1: Example of a radix tree.

(^1) The structure shown is simplified because the kernel makes use of additional tags in each node to hold specific information on the
pages organized in the node. This has no effect on the basic architecture of the tree.