Linux Kernel Architecture

Chapter 18: Page Reclaim and Swapping

are performed, they need to be locked, and one problem arises: The page reclaim code belongs to the

hottest and most important paths in the kernel for many workloads, and lock contention is rather high.

Therefore, the kernel need to work outside the lock as often as possible.

One optimization is to place all pages that are about to be analyzed inshrink_active_listand

shrink_inactive_liston a local list, drop the lock, and proceedwith the pages on the local list. Since

they are not present on any global zone-specific list anymore, no other part of the kernel except the

owner of the local list can touch them — the pages will not be affected by subsequent operations on the

zone lists. Taking the zone list lock to work with thelocallist of pages is therefore not required.

The functionisolate_lru_pagesis responsible for selecting a given number of pages from either the

active, or the inactive list. This is not very difficult: Starting from the end of the list — which is very

important because the oldest pages must be scanned first in an LRU algorithm! — a loop iterates over

the list, takes off one page in each step, and moves it to the local list until the desired number of pages is

reached. For each page, thePG_lrubit is removed because the page is now not on an LRU list anymore.^10

So far for the simplest case. Reality, however, is slightly more involved becauseisolate_lru_pagesalso

implements thelumpy reclaim algorithm. What is the purpose of lumpy reclaim? It can be difficult to fulfill

higher-order allocation requests that require a continuous interval of physical RAM that consists of more

than one page — the more pages, the harder is the problem. When a system has been running for some

time, physical memory tends to become fragmented more and more. How can this problem be solved?

Consider Figure 18-14, which illustrates the kernel’s approach.^11

struct page

LRU list

..
0510
Physical
page frames

15

Figure 18-14: The lumpy reclaim technique helps the

kernel reclaim larger continuous intervals of physical

RAM.

Assume that the kernel requires four page frames in a row. Unfortunately, the page frames belonging to

the pages that are currently on the LRU list are scattered in memory, and the largest continuous region

consists of two pages. To escape this situation, lumpy reclaim simply takes page frames that surround a

page frame belonging to one of the pages on the LRU list, the tag page. Not only the tag page, but also

the surrounding pages, are selected for reclaim. This way, four continuous page frames in a row can be

attempted to be freed. This does not yet guarantee that a block with four free pages will result because

(^10) Besides, the function needs to acquire a reference on the page andalso ensure that the reference count was zero before. Usually,
pages with zero reference count are in the buddy system, as discussed in Chapter 3.5. However, concurrency allows pages with zero
page count to live on the LRU list for a short amount of time.
(^11) While lumpy reclaim is not exactly what computer science likes to teach, it works well in practice, and is above all very
simple — which is sometimes much more important to the kernel than looking good and elegant on paper.