Before plunging into details, let’s give a brief overview of Linux page frame reclaiming. (Looking too close to the trees’ leaves might lead us to miss the whole forest!)

Page frames can be freed in two ways:

Of course, the algorithm should take into consideration the various different kinds of page frames. For instance, it is preferable to reclaim page frames from a memory cache rather than from a disk cache because the latter pages include precious data obtained by costly accesses to block disk devices.

Moreover, the algorithm should keep track of the number of accesses to every page frame. If a page has not been accessed for a long time, the probability that it will be accessed in the near future is low; on the other hand, if a page has been accessed recently, the probability that it will continue to be accessed is high. This is just another application of the locality principle mentioned in Section 2.4.7.

Therefore, the page frame reclaiming algorithm is a blend of several heuristics:

The main function that triggers page frame reclaiming is try_to_free_pages( ). It is invoked every time the kernel fails in allocating memory. For instance:

The core of the try_to_free_pages( ) function is the shrink_caches( ) function: it receives as a parameter a “goal”—namely, a given number of page frames to be reclaimed—and it terminates as soon as it has reached the goal, if possible.

To help shrink_caches( ) do its job, all pages in dynamic memory are grouped into two lists called the “active list” and the “inactive list”; they are also collectively denoted as LRU lists . The former list tends to include the pages that have been accessed recently, while the latter tends to include the pages that have not been accessed for some time. Clearly, pages should be stolen from the inactive list, although some percolation between the two lists is performed from time to time.

The shrink_caches( ) function invokes, in turn, the following functions:

Let’s now discuss in greater detail the various components of the page frame reclaiming algorithm.

The active list and the inactive list of pages are the core data structures of the page frame reclaiming algorithm. The heads of these two doubly linked lists are stored, respectively, in the active_list and inactive_list variables. The nr_active_pages and nr_inactive_pages variables store the number of pages in the two lists. The pagemap_lru_lock spin lock protects the two lists against concurrent accesses in SMP systems.

If a page belongs to an LRU list, its PG_lru flag in the page descriptor is set. Moreover, if the page belongs to the active list, the PG_active flag is set, while if it belongs to the inactive list, the PG_active flag is cleared. The lru field of the page descriptor stores the pointers to the next and previous elements in the LRU list.

Several auxiliary functions and macros are available to handle the LRU lists:

Moving pages across the LRU lists

The kernel collects the pages that were recently accessed in the active list so that it will not scan them when looking for a page frame to reclaim. Conversely, the kernel collects the pages that have not been accessed for a long time in the inactive list. Of course, pages should move from the inactive list to the active list and back, according to whether they are being accessed.

Clearly, two page states (“active” and “inactive”) are not sufficient to describe all possible access patterns. For instance, suppose a logger process writes some data in a page once every hour. Although the page is “inactive” for most of the time, the access makes it “active,” thus denying the reclaiming of the corresponding page frame, even if it is not going to be accessed for an entire hour. Of course, there is no general solution to this problem because the kernel has no way to predict the behavior of User Mode processes; however, it seems reasonable that pages should not change their status on every single access.

The PG_referenced flag in the page descriptor is used to double the number of accesses required to move a page from the inactive list to the active list; it is also used to double the number of “missing accesses” required to move a page from the active list to the inactive list (see below). For instance, suppose that a page in the inactive list has the PG_referenced flag set to 0. The first page access sets the value of the flag to 1, but the page remains in the inactive list. The second page access finds the flag set and causes the page to be moved in the active list. If, however, the second access does not occur within a given time interval after the first one, the page frame reclaiming algorithm may reset the PG_referenced flag.

As shown in Figure 16-4, the kernel uses the mark_page_accessed( ) and refill_inactive( ) functions to move the pages across the LRU lists. In the figure, the LRU list including the page is specified by the status of the PG_active flag.

Figure 16-4. Moving pages across the LRU lists

Whenever the kernel must mark a page as accessed, it invokes the mark_page_accessed( ) function. This happens every time the kernel determines that a page is being referenced either by a User Mode process, a filesystem layer, or a device driver. For instance, mark_page_accessed( ) is invoked in the following cases:

• When loading an anonymous page of a process on demand (performed by the do_anonymous_page( ) function in Section 8.4.3).

• When reading a block from disk (performed by the bread( ) function in Section 13.4.8).

• When loading on demand a page of a memory mapped file (performed by the filemap_nopage( ) function in Section 15.2.4).

• When reading a page of data from a file (performed by the do_generic_file_read( ) function in Section 15.1.1).

• When swapping in a page (see the earlier section Section 16.6.1).

• When the kernel finds the Accessed flag set in the Page Table entry while searching for a page to be swapped out (see the earlier section Section 16.5.1).

• When the kernel reads a page of data from a disk device (performed by the ext2_get_page( ) function in Chapter 17).

The mark_page_accessed( ) function executes the following code fragment:

if (PageActive(page) || !PageReferenced(page))
    SetPageReferenced(page);
else {
    activate_page(page);
    ClearPageReferenced(page);
}

As shown in Figure 16-4, the function moves the page from the inactive list to the active list only if the PG_referenced flag is set before the invocation.

The kernel periodically checks the status of the pages in the active list by executing the refill_inactive( ) function. Starting from the bottom of the active list (the older pages in the list), the function checks whether the PG_referenced flag of each page is set. If it is, the function clears the flag and moves the page into the first position of the active list; if it isn’t, the function moves the page into the first position of the inactive list. The logic in the function is as follows:

if (PageReferenced(page)) {
    ClearPageReferenced(page);
    list_del(&page->lru);
    list_add(&page->lru, &active_list);
} else {
    del_page_from_active_list(page);
    add_page_to_inactive_list(page);
    SetPageReferenced(page);
}

The refill_inactive( ) function does not scan the pages in the inactive list; hence, the PG_referenced flag of a page is never cleared as long as the page remains in the inactive list.

The try_to_free_pages( ) function is the main function that triggers the reclaiming of page frames. It receives as parameters:

The goal of the function is to free SWAP_CLUSTER_MAX page frames (usually, 32) by repeatedly invoking the shrink_caches( ) function, each time with a higher priority than the previous invocation. The try_to_free_pages( ) function is thus essentially equivalent to the following code fragment:

int priority = DEF_PRIORITY;
int nr_pages = SWAP_CLUSTER_MAX;

if (current->flags & PF_NOIO)
    gfp_mask &= ~(_ _GFP_IO | _ _GFP_HIGHIO | _ _GFP_FS);

do {
    nr_pages = shrink_caches(classzone, priority, gfp_mask, nr_pages);
    if (nr_pages <= 0) 
        return 1;
} while (--priority);
out_of_memory( );

try_to_free_pages( ) clears the _ _GFP_IO, _ _GFP_HIGHIO, and _ _GFP_FS bits in the gfp_mask parameter if the current process has the PF_NOIO flag set. This flag is set whenever the kernel must ensure that the page frame reclaiming algorithm never triggers I/O data transfers; it is currently used only by kernel threads of the loop device driver, which allows User Mode processes to handle regular files as if they were disk block partitions.

The loop is repeated at most DEF_PRIORITY times (usually six times). The value of the decreasing priority loop index is passed to the shrink_caches( ) function. Each time shrink_caches( ) tries harder to reclaim a page frame because lower values correspond to higher priorities.

If DEF_PRIORITY iterations are not enough to reclaim SWAP_CLUSTER_MAX page frames, the kernel is in serious trouble. It has just one last resort: killing a User Mode process to free all its page frames. This operation is performed by the out_of_memory( ) function. Loosely speaking, the victim process is selected from those that have the smallest runtimes, ruling out those that have superuser privileges and those that perform direct I/O operations (see Section 15.3).

The shrink_caches( ) function invokes several auxiliary functions in a fixed order to reclaim page frames in different memory subsystems. One of the functions invoked is called shrink_cache( ) and should not be confused with the parent function shink_caches( ). The function shrink_caches( ) acts on the following parameters:

The function returns the difference between nr_pages and the number of page frames that have been effectively reclaimed; if more than nr_pages page frames have been freed, the function returns 0. It executes the following actions:

The shrink_cache( ) function acts on the same parameters as shrink_caches( ): nr_pages, classzone, gfp_mask, and priority. It looks for page frames to be reclaimed in the inactive list. Since the last inserted elements are placed near the head of the list, the function starts scanning from the tail of the list and moves backward.

The function achieves its goal by:

The priority parameter controls the size of the portion of the inactive list to be scanned in this invocation of shrink_cache( ). If priority is equal to 6 (DEF_PRIORITY, the lowest priority), the function scans at most one-sixth of the list; as priority decreases, the function scans more and more of the list until it reaches 1 (the highest priority), whereupon it scans the whole list.

The function starts by acquiring the pagemap_lru_lock spin lock and then loops over the pages of the inactive list backwards until either the chosen portion of the list is scanned or the number of elements specified by priority is reached. For every scanned page, the function performs the following actions:

Dentry and inode objects themselves aren’t big, but freeing one of them has a cascading effect that can ultimately free a lot of memory by releasing several data structures. For this reason, the shrink_caches( ) function invokes two special purpose functions to reclaim page frames from the dentry and inode caches.

The kswapd kernel thread is another kernel mechanism that activates the reclamation of memory. Why is it necessary? Is it not sufficient to invoke try_to_free_pages( ) when free memory becomes really scarce and another memory allocation request is issued?

Unfortunately, this is not the case. Some memory allocation requests are performed by interrupt and exception handlers, which cannot block the current process waiting for a page frame to be freed; moreover, some memory allocation requests are done by kernel control paths that have already acquired exclusive access to critical resources and that, therefore, cannot activate I/O data transfers. In the infrequent case in which all memory allocation requests are done by such sorts of kernel control paths, the kernel is never able to free memory.

kswapd also has a beneficial effect on system performances by keeping memory free in what would otherwise be idle time for the machine; processes can thus get their pages much faster.

The kswapd kernel thread is activated when a zone includes a number of free page frames that is below a “warning” threshold. Essentially, the kernel starts to reclaim some page frames in order to avoid much more dramatic “low on memory” conditions.

The “warning” threshold is stored into the pages_low field of the memory zone descriptor. Recall from Section 7.1.2 that this descriptor also includes the pages_min field (a threshold that specifies the minimum number of free page frames that should always be preserved) and the pages_high field (a threshold that specifies the “safe” number of free page frames above which page frame reclaiming should be stopped). Usually, the pages_min field is set to the ratio between the size of the memory zone in pages and the number 128, the pages_low field is set to twice pages_min, and the pages_high field is set to three times the value of pages_min.^[114]

The kswapd kernel thread is usually inserted into the kswapd_wait wait queue. As mentioned in Section 7.1.5, if the alloc_pages( ) function fails to find a memory zone that has more than pages_low page frames, it sets the need_balance field of the first checked memory zone and wakes up kswapd.

The kswapd kernel thread executes the kswapd( ) function, which at each activation performs the following operations:

The kswapd_balance( ) function checks the need_balance flag of all existing memory zones. For any memory zone having the flag set, the function invokes try_to_free_pages( ) to start reclaiming page frames. As we know, the latter function might not succeed in freeing SWAP_CLUSTER_MAX page frames; in this case, a process is killed. When this happens, kswapd_balance( ) suspends itself for one second, thus letting the kernel reclaim the page frames owned by the victim.

The kswapd_balance( ) function keeps invoking try_to_free_pages( ) on a memory zone until the number of free page frames in the zone (or in one of the other zones in the node) rises above the threshold stored in the pages_high field of the memory zone descriptor.