Linux Specifics

Address Space Layout

Linux divides the available address space up into a shared kernel component and private user space addresses. This means that addresses in the kernel port of the address space map to the same physical memory for each process, whilst userspace addresses are private to the process. On Linux, the shared kernel space is at the very top of the available address space. On the most common processor, the 32 bit x86, this split happens at the 3GB point. As 32 bits can map a maximum of 4GB, this leaves the top 1GB for the shared kernel region[1].

Three Level Page Table

There are many different ways for an operating system to organise the page tables but Linux chooses to use a hierarchical system.

As the page tables use a heirarchy that is three levels deep, the Linux scheme is most commonly referred to as the three level page table. The three level page table has proven to be robust choice, although it is not without it's criticism. The details of the virtual memory implementation of each processor vary widley meaning that the generic page table Linux chooses must be portable and relatively generic.

The concept of the three level page table is not difficult. We already know that a virtual address consists of a page number and an offset in the physical memory page. In a three level page table, the virtual address is further split up into a number levels.

Each level is a page table of it's own right; i.e. it maps a page number of a physical page. In a single level page table the "level 1" entry would directly map to the physical frame. In the multilevel version each of the upper levels gives the address of the physical memory frame holding the next lower levels page table.

So a sample reference involves going to the top level page table, finding the physical frame that the next level address is on, reading that levels table and finding the physical frame that the next levels page table lives on, and so on.

At first, this model seems to be needlessly complex. The main reason this model is implemented is for size considerations. Imagine the theoretical situation of a process with only one single page mapped right near the end of it's virtual address space. We said before that the page table entry is found as an offset from the page table base register, so the page table needs to be a contiguous array in memory. So the single page near the end of the address space requires the entire array, which might take up considerable space (many, many physical pages of memory).

In a three level system, the first level is only one physical frame of memory. This maps to a second level, which is again only a single frame of memory, and again with the third. Consequently, the three level system reduces the number of pages required to only a fraction of those required for the single level system.

There are obvious disadvantages to the system. Looking up a single address takes more references, which can be expensive. Linux understands that this system may not be appropriate on many different types of processor, so each architecture can collapse the page table to have less levels easily (for example, the most common architecture, the x86, only uses a two level system in its implementation).