The page hash table

When a process reads a large file, the page cache may become filled with pages related to that file. In such cases, scanning a long list of page descriptors to find the page that maps the required file portion could become a time-consuming operation.

For this reason, Linux uses a hash table of page descriptor pointers named page_hash_table. Its size depends on the amount of available RAM; for example, for systems having 128 MB of RAM, page_hash_table is stored in 32 page frames and includes 32,768 page descriptor pointers.

The page_hash macro uses the address of an address_space object and an offset value to derive the address of the corresponding entry in the hash table. As usual, chaining is introduced to handle entries that cause a collision: the next_hash and pprev_hash fields of the page descriptors are used to implement doubly circular lists of entries that have the same hash value. The page_cache_size variable specifies the number of page descriptors included in the collision lists of the page hash table (and therefore in the whole page cache).

The add page to hash queue( ) and remove page from hash queue( ) functions add an element into the hash table and remove an element from it, respectively.

Was this article helpful?

0 0

Responses

  • Lauryn McDonald
    Why hash table is uesd in a linux kernel?
    2 years ago

Post a comment