The goals for this implementation of non-resident page bookkeeping:
- minimal space overhead
- SMP scalability
- reasonably fast
Data structures
When looking up a page, we use page->offset, page->mapping to determine which nr_bucket hash bucket to put the page in, and hash page->offset, page->mapping and page->mapping->host->i_ino to get to the value stored in the nr_bucket.page array. We recycle nr_bucket.page entries in a circular fashion, with hand pointing to the current entry that's being updated.
This means we do not need a lookup list for these pages, we simply look through all the objects in the cacheline, doing simple comparisons. Hopefully the cost of comparing 31 entries is outweighed by only having 1 cache miss per lookup.
/* Number of non-resident pages per hash bucket */
#define NUM_NR ((L1_CACHE_BYTES - sizeof(atomic_t))/sizeof(unsigned long))
struct nr_bucket
{
atomic_t hand;
unsigned long page[NUM_NR];
} ____cacheline_aligned;
Uniqueness of mapping
Because the address_space structure underlying mapping can be freed by the kernel and then reallocated for another file, we need to take some measures to prevent the VM from thinking a brand-new page of a newly opened file was recently evicted. The obvious way to do this would be invalidating all entries of a particular mapping when the struct address_space is freed. However, we would need a much larger data structure if we wanted to support efficient invalidation.
The alternative is to simply hash the inode number into the non-resident page value, and hope that the next time a particular struct address_space is allocated to a different file, that file will have a different inode number.
The swap cache is a special case, since we can invalidate entries when a process exits, because we free up swap pages one by one. We can simply call the recently_evicted function from remove_exclusive_swap_page. This also covers swapoff(8) and a subsequent swapon(8), since the non-resident entries will be invalidated at swapoff time.
Back to AdvancedPageReplacement