Linux Kernel Architecture

Chapter 16: Page and Buffer Cache

To make lookup operations faster, the kernel first scans the cache entries from top to bottom to find an

independent buffer each time a request is made. Ifan element contains the required data, the instance

in the cache can be used. If not, the kernel must submit a low-level request to the block device to get the

desired data.

The element last used is automatically placed at the first position by the kernel. If the element was already

in the cache, only the positions of the individual elements change. If the element was read from the block

device, the last element of the array ‘‘drops out‘‘ of the cache and can therefore be removed from memory.

The algorithm is very simple but nevertheless effective. The time needed to look up frequently used

elements is reduced because the element is automatically located at one of the top array positions. At the

same time, less used elements automatically drop out of the cache if they are not accessed for a certain

period. The only disadvantage of this approach is the fact that almost the full contents of the array need

to be repositioned after each lookup operation. This is time-consuming and can be implemented for small

caches only. Consequently, buffer caches have only a low capacity.

Implementation

Let us examine how the kernel implements the algorithm just described for the LRU cache.

Data Structures

As the algorithm is not complicated, it requires only relatively simple data structures. The starting point

of the implementation is thebh_lrustructure which is defined as follows:

fs/buffer.c

#define BH_LRU_SIZE 8

struct bh_lru {

struct buffer_head *bhs[BH_LRU_SIZE];

};

static DEFINE_PER_CPU(struct bh_lru, bh_lrus) = {{ NULL }};

It is defined in a C file and not in a header file — as usual, an indication for the rest of the kernel code

that the cache data structures should (and, besides, can!) not be addressed directly but by means of the

dedicated helper functions discussed below.

bhsis an array of pointers to buffer heads and is used as a basis for implementing the LRU algorithm

(eight entries are used as the pre-processor definition shows). The kernel usesDEFINE_PER_CPUto instan-

tiate an instance for each CPU of the system to improve utilization of the CPU caches.

The cache is managed and utilized by two public functions provided by the kernel:lookup_bh_lru

checks whether a required entry is present in the cache, andbh_lru_installadds new buffer heads to

the cache.

The function implementations hold no surprises since they merely implement the algorithm described

above.^14 All they need do is select the corresponding array for the current CPU at the start of the action

Using Sockets

(^14) Or as aptly put by a comment in the kernel code:The LRU management algorithm is dopey-but-simple. Sorry.