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 struct page height = 2 ptr

P

P

P

P

P

Count

t

t

t

t

t

r

r

r

r

r

PAGECACHE_TAG_DIRTY PAGECACHE_TAG_WRITEBACK

>

r

f

P

P

P

P

P

P

P

P

P

P

Count

t

t

t

t

t

Count

t

t

t

t

t

r

r

r

r

r

r

r

r

r

r

Continue reading here: Writing Back Modified Data

Was this article helpful?

0 0