Extents for Implementing Non Contiguous Swap Areas

The kernel uses the extent_list and curr_swap_extent elements to implement extents, which create mappings between the swap slots that are assumed to be contiguous and the disk blocks of the swap file. This is not necessary if partitions are used as the basis for swap space because the kernel can then rely on the fact that the blocks on the disk are arranged linearly. Mapping between page slots and disk blocks is therefore very simple. Starting from the position of the first block, it is only necessary to multiply a constant offset by the required page number in order to obtain the required address, as illustrated in Figure 18-1. In this case, just one swap_extent instance is needed. (Actually, this could also be dispensed with, but its existence makes things easier for the kernel as it narrows the differences between partition swap areas and file swap areas.)




- u



- 3



- 13


= 3


- 10


- 7


- A


- B


- C


- 0


- 270

start block

- 0

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.) The extent_list list 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 for every page slot. It is sufficient to associate 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 structure struct extent_list is 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;

list is used to manage the members of the extent list on a doubly linked standard list. The other members describe the data of a single, contiguous block group:

□ The number of the first page slot in a block group is held in start_page.

□ nr_pages specifies the number of pages that fit into the block group.

□ start_block is the block number of the first block of the group on the hard disk.

These lists can become extremely long. The two sample swap areas in files that each contain around 16,000 pages consist of, for example, 37 or even 76 block groups. The second extent mechanism requirement — high search speed — is not always met by doubly linked lists since they may well comprise hundreds of entries. It is, of course, extremely time-consuming to scan through such lists each time the swap area is accessed.

The solution is relatively simple. An additional element called curr_swap_extent in swap_info_struct is used to hold a pointer to the last element accessed in the extent list. Each new search starts from this element. As access is often made to consecutive page slots, the searched block is generally found in this or the next extent element.2

If the search by the kernel is not immediately successful, the entire extent list must be scanned element-by-element until the entry for the required block is found.

Continue reading here: Creating a Swap Area

Was this article helpful?

0 0