Radix Tree

Because the kernel must check for the existence of a page in the page cache before initiating any page I/O, such a check must be quick. Otherwise, the overhead of searching and checking the page cache could nullify any benefits the cache might provide (at least if the cache hit rate is lowthe overhead would have to be awful to cancel out the benefit of retrieving the data from memory in lieu of disk).

As you saw in the previous section, the page cache is searched via the address_space object plus an offset value. Each address_space has a unique radix tree stored as page_tree. A radix tree is a type of binary tree. The radix tree allows very quick searching for the desired page, given only the file offset. Page cache searching functions such as find_get_page() call radix_tree_lookup(), which performs a search on the given tree for the given object.

The core radix tree code is available in generic form in lib/radix-tree.c. Users of the radix tree need to include <linux/radix-tree.h>.

The Old Page Hash Table

Prior to the 2.6 kernel, the page cache was not searched via radix tree. Instead, a global hash was maintained over all the pages in the system. The hash returned a doubly linked list of entries that hash to the same given value. If the desired page was in the cache, one of the items in the list was the corresponding page. Otherwise, the page was not in the page cache and the hash function returned NULL.

The global hash had four primary problems:

• A single global lock protected the hash. Lock contention was quite high on even moderately sized machines, and performance suffered as a result.

• The hash was larger than necessary because it contained all the pages in the page cache, whereas only pages pertaining to the current file were relevant.

• Performance when the hash lookup failed (that is, the given page was not in the page cache) was slower than desired, particularly because it was necessary to walk the chains off of a given hash value.

• The hash consumed more memory than other possible solutions.

The introduction of a radix tree-based page cache in 2.6 solved these issues.