Isolating LRU Pages and Lumpy Reclaim

Both the active and inactive pages of a zone are kept on lists that need to be protected by a spinlock, to be precise: by zone->lru_lock. To simplify matters, I have ignored this lock until now because it was not essential for our purposes. Now we need to consider it, though. When operations with the LRU lists 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 in shrink_active_list and shrink_inactive_list on a local list, drop the lock, and proceed with 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 the local list of pages is therefore not required.

The function isolate_lru_pages is 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, the PG_lru bit 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 because isolate_lru_pages also implements the lumpy 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 struct page

page frames

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

10Besides, the function needs to acquire a reference on the page and also 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.

11While 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.

the selected page frames could very well be unreclaimable. However, an attempt has been made, and the probability of reclaiming higher-order allocations is drastically increased with lumpy reclaim as compared to the situation without this technique.

Naturally, there are some complications in practice, but these are best discussed directly with the source code. The first part of isolate_lru_pages is not very interesting. As described above, a single page is isolated from the LRU list under consideration:

Continue reading here: Mmvmscanc

Was this article helpful?

0 0


  • myrtle
    Why remove lumpy reclaim?
    11 months ago