3.1 Data Structures

In order to implement this mechanism we have added some data structures to the original Linux kernel. In this section, we will describe each of these structures in some detail. A general picture with all the structures and most of the fields is presented in Figure 3.

 
Figure 3:   Data structures needed for the compressed swap.

• virtual_swap_info: this structure keeps the information of all the compressed pages. The size of this array is MAX_VPAGES, which is the maximum number of compressed pages that our system will be able to handle. The size of this array can be modified to suit the needs of each system as explained in Section 3.6. In each entry of this array we have the following information:

  physical_offset: it indicates the disk block where the compressed page is stored.

  buffer_offset: it is the field used to mark the position where this compressed page is kept. As we store more than one compressed pages per disk block, we need to know at which byte does the page start.

  compressed_size: as can be guessed from its name, this field is used to keep the size of the swapped page once it has been compressed.

  rw_remaining: it is a counter of the number of pending read or write operations for this page. We need this information not to free a page while still being used.

• swap_map: this structure was already used in the original Linux kernel. We have only modified its size as we need an entry for each one in the virtual_swap_info array. Its function is to keep the number of processes that have this page mapped in their address space.
• physical_swap: for each disk block, we need to know the number of compressed pages kept in it. This table is responsible for maintaining this information.
• swap_lockmap: there are situation where we need to perform atomic operations on the disk block. To ensure that no other process will work with a given block, we use this data structure already implemented in the original Linux kernel. It is a bitmap where each bit tells whether the given disk block is being used in exclusive mode or not.
• swap_cache_info: this structure is used to keep all the information needed to maintain the compressed cache. It has as many entries as buffers in the cache (CACHE_BUFFERS).

  physical_offset: it indicates the disk block assigned to this buffer.

  buffer_addr: it points to the cache buffer where the compressed pages are really stored. We need this pointer as all buffers are not necessarily contiguous. This is because we cannot allocate as many buffers as needed in a single call (Linux implementation issues).

  next_free_byte: it keeps the first free byte. This is the position where the next compressed page inserted in this buffer will be placed.

  flags: cache buffers need some flags such as the dirty bit.

• swap_cache: this structure is just a set of buffers (not necessarily contiguous) that are used to keep the compressed pages before they are sent to the disk.
• Swap device: finally, this is the disk partition where the compressed pages are finally stored.