Virtual Memory: pages and page frames

October 31, 2012

Virtual memory decouples the virtual address space that the programmer and the processor sees from the physical address space of the actual RAM memory. For each process, a mapping is maintained between virtual addresses to physical addressed, and every memory access must pass through this map. The Memory Management Unit, MMU, is the physical contraption on the computer chip that does the mapping.

The virtual address space is divided into pages, a contiguous span of addresses of a particular size. The pages are page aligned in that the starting address of a page is a multiple of the page size. For instance, the starting virtual address of the first several pages when the page size is 4K are 0, 4096, 8192, 16384, etc. The MMU architecture of a 32 bit i386 allows for small page of 4K bytes and large pages of 4M bytes.

The physical address space is likewise divided into page frames. The MMU is responsible for maintaing a map of pages to page frames. A page frame will be the same size as a page, and it will have the same page alignment. This simplifies the mapping — the MMU must maintain explicitly only a map between the pages and page frames. The map of individual bytes between a page and page frame just passes through the least significant bites of the address. For instance, for 4K pages on a 32 bit architecture maps the top 20 bits of a the virtual address to the top 20 bits of a physical address, and lower 12 bits are just passed through unchanged.

Various schemes exist to implement the mapping of virtual pages to physical page frames. The method used by many operating system is the page table. I will overly simplify the description on first explanation to make the mechanism clear. The page table is simply an array where the i-th entry contains the number j when virtual page i is associated with physical page j. The page and page frame numbers neglect the lower bits that indicated the offset into the page and page frame. As an example, if virtual address 0x0000 3003 where to map to physical address 0x0000 6003 then index 3 of the page table will contain the number 6 (assuming 4K pages).

Note that most entries in the page table will be empty, that is, the number in the page table will be invalid, as most pages are not associated with any physical page frames. In order to save space, a multilevel page table is more common than the single large table that we have described in the last paragraph. A multilevel page table will save space at the cost of more memory fetches into the page table structure.

A sample multilevel page table is the two level table of Linux in the 32 bit address mode. In this scheme, the virtual address is divided into the highest 10 bits, which index one of 1024 page diretory entries (PDE’s) in a PDE table; then the next highest 10 bites, which index one of 1024 page table entries (PTE’s) in a PTE table. The values in the PDE are physical page frame addresses, so that the exact entry in the selected PTE is simply that 22 bit page frame address adjoined with the 12 bits of index information. It’s 12 bits, not 10, because each PTE is 4 bytes long. The last two bits are 0 for indexing purposes. The PDE’s are also 4 bytes long.

Note that this all works out very well. Since there are 1024 entires, each 4 bytes long, a PDE table as well as a PTE table is exactly the size of a page frame. This saves memory in the situation where the PDE entry can be marked invalid, because there is a space of 4M of virtual address which are entirely unused.

The x386 architecture also allows that “large pages” can be mixed with the 4k pages. The trick to this is that the PDE is marked as a large page, and the lookup stops. The 10 bits from the PDE are combined with the lower order 22 bits of the virtual address to form the physical address. This gives 4M pages.

Page tables and processes

Each process has its own virtual to physical mapping, and therefore its own set of page tables. To context switch from one process to another, the switch in mapping is effectuated by loading a single hardware register. That register is the base physical address of the PDE (the page frame number).

For some operating systems (OSX) the kernel as a virtual memory space completely distinct from any user processes virtual address space. Linux and many other operating systems place the operating system in high memory. This way, when the kernel runs it has access to the full memory space, including the current user’s memory. When in user mode, running in the lower, user reserved memory portion, the high memory is read/write protected against any access by the user.

Linux reserves the lower 3G for user process memory and the upper 1G for kernel memory. In this situation the upper one quarter of the the PDE entries are the same for all processes — they are the PDE’s that map the common memory space of the kenel. Often the first few of these, in the lowest portion of the upper memory, map the programming code for the kernel by using large pages.

The x386 architecture also supports a mode in which the physical address space is larger than the virtual address space. This becomes unnecessary for 64 bit computing, but it was worthwhile in 32 bit computing since it is possible that summed over all processes, the memory demands can exceed 4G (and swapping to satisfy this demand would reduce performance). Each process would still be 4G limited by the nature of 32 bits of address (and really 3G limited, since the upper 1G is reserved to the kernel), but different processes would map different page frames, so overall more than 32G of physical memory could be used.

The Physical Address Extension mode (PAE) suports up to 52 bits of physical address. Many of the intel chips to implement all 52 bits, but the architecture provides for the possibility. Since the lowest 12 bits are offset in a page, this means that a page frame is indicated by 40 bits. The size of the PDE’s and PTE’s are increased to 8 bytes to make room for the 40 bits, and the number of entries in a single table is reduced to 512.

By the way, the remaining bits of a PDE or PTE are not all wasted. In addition to a page frame number, the entry contains:

  • A valid flag to indicate if the entry is in use or not;
  • An accessed flag to indicate that there has been a read or write on the page since the last clearing of this flag;
  • A dirty flag to indicate that there as been a write on this flag since the last clearing of this flag;
  • A page size flag to indicate if this is a small or large page frame (PDE entry only).

Given 9 bits per index into a PDE or PTE, to support PAE and third level of indexing is required.

For 64 bit computing, the 64 bit virtual address space is in fact reduced to 48 bits, which maps to a 52 bit physical address space by a cascade of four tables: the PTE, the PDE, the PTPDE and the unlikely named PML4E. For completeness, I will mention that the 64 bit architecture, sometimes call IA-32e, or amd-64, supports three sizes of pages, depending on where the cascade of tables is terminated: 4K by using all 4 tables, 2M using 3 tables, or 1G using 2 tables.

posted in CSC521 by admin

Powered by Wordpress and MySQL. Theme by Shlomi Noach,