Introduction
This page is currently work in progress and will be updated over the following weeks.
- The intention of this page is to introduce the concept of Variable Radix Page Tables,
Christian Szmajda of the University of New South Wales (UNSW) wrote the origianal paper, which can be found here.
The basic concept involved in a radix page table is to split the virtual address into a number of fields. The lowest field is an index into the actual memory page, but the other fields are used as indices into the different levels of the page table which is used to find the desired page frame.
Linux currently uses a three level page table. The address is divided into four fields. The first field indexes the top level of the pagetable to give a pointer to a middle level directory block. The next address field indexes the middle level directory to give a pointer to a leaf node containing PTEs. The 3rd field from the address indexes the block of PTEs to give a page frame in memory, and the remaining bits index into the page frame to give the desired byte.
Under Linux the page table index fields are the same size. A variable radix page table format can divide the address into different numbers of fields in different parts of the page table, and make those fields different widths. One of the effects of this is to allow the page table to be different depths in different places e.g., a part of the page table mapping to superpages may not need the full three levels needed by the current page table to map to base sized page frames.
Associated Links
An introduction to Linux memory management. This introduction may be slightly outdated however it gives a nice overview of how Linux manages memory.
- Linux memory management documents:
Memory Management in Linux Abhishek Nayani et.al. 25/05/2002.
Understanding The Linux Virtual Memory Manager Mel Gorman 14/03/2003.
Code Commentary On The Linux Virtual Memory Manager Mel Gorman 14/03/2003.
Originals and updates of the above papers can be found at the Linux kernel documentation project.
- Linux memory management web sites:
Linux-MM home page.
- Linux VM benchmarking and testing
GenGraph/CodeViz, this tool generates graphs of a sequence of function calls, for C/C++ source code.
