Linux Kernel Architecture

Chapter 18: Page Reclaim and Swapping

A B

......

start_page = 0

nr_pages = 3

start_block = A

start_page = 3

nr_pages = 10

start_block = B

start_page = 13

nr_pages = 7

start_block = C

start_page = 0

nr_pages = 270

start_block = 0

C

...

Figure 18-1: Extents for managing non-contiguous swap areas.

The situation is more complicated when files are used as the basis for swap memory because there is then

no guarantee that all blocks of the file are located sequentially on disk. Consequently, mapping between

page slots and disk blocks is more complex. Figure 18-1 illustrates this by means of an example.

A file consists of multiple sections located anywhere on the block device. (The lesser disk fragmentation

there is, the smaller the number of sections — after all, it is best if file data are kept as close together as

possible, as discussed in Chapter 9.) Theextent_listlist has the task of associating the scattered blocks

of the file with the linear page slots. In doing so, it should ensure two things — that as little memory

space as possible is used, and that search time is kept to a minimum.

It is not necessary to associate the page slot and block number foreverypage slot. It is sufficient to asso-

ciate the first block of a contiguous block group with the corresponding page slot and to note how many

blocks there are after the first block so that the file structure can be reproduced in a very compact manner.

Let us illustrate the procedure using the example above. As the figure shows, the first three contiguous

block groups consist of 3, 10, and 7 blocks. What happens when the kernel wants to read the data of the

sixth page slot? These data are not in the first block group as this block contains only slots 0 through 2.

The search terminates successfully at the second group, which contains slots 3 through 12 and logically

slot 6. The kernel must therefore determine the start block of the second group (using the extent list). The

group’s third member (which corresponds to the sixth page slot) can be found easily by twice adding

the page size to the start address as the offset.

The extent structurestruct extent_listis defined to serve exactly this purpose:

<swap.h>

struct swap_extent {

struct list_head list;

pgoff_t start_page;

pgoff_t nr_pages;

sector_t start_block;

};

listis used to manage the members of the extent list on a doubly linked standard list. The other mem-

bers describe the data of a single, contiguous block group:

❑ The number of the first page slot in a block group is held instart_page.

❑ nr_pagesspecifies the number of pages that fit into the block group.

❑ start_blockis the block number of the first block of the group on the hard disk.