The goals for this implementation of non-resident page bookkeeping:

• minimal space overhead
• SMP scalability
• reasonably fast

Data structures

The nr_page data structure represents one non-resident page, by virtue of pointing to the page mapping (or mm) and the page offset. We steal some bits from both fields for the object generation and to indicate which pageout list the page was on before it got evicted.

struct nr_page {
        void * mapping;
        unsigned long offset_and_gen;
};

We fit multiple of these nr_page structs in one (cacheline sized?) hash bucket. This means we do not need a lookup list for these pages, we simply look through all the objects in the cacheline, doing quick pointer comparisons. Having one spin_lock per hash bucket, and having that spinlock in the same cacheline, should help SMP scalability.

/* Number of non-resident pages per hash bucket */
#define NUM_NR ((L1_CACHE_BYTES - sizeof(spinlock_t))/sizeof(struct nr_page))

struct nr_bucket
{
        spinlock_t lock;
        struct nr_page pages[NUM_NR];
} __cacheline_aligned;

Object generation number

Because this data structure does not allow efficient invalidation of entries when an address space is destroyed, the caller needs to pass in an object generation cookie. This does not need to be an actual version number stored in the data structure that *mapping points to, but could also be something generated on the fly - as long as it stays stable across the lifetime of the object and is not too likely to collide with the next object allocated at the same address.

Eg. for a pagecache struct address_space we could use a hash of mapping->host->i_ino and mapping->host->i_sb. After all, neither of these should change during normal system operation.

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.