386 Paging BasicsWe have seen how segmentation works in the 386. Now let's examine paging. For our purposes, segmentation on the 386 is defeated by running in "flat" mode. We can then consider intrasegment addresses as if they are linear address space.
Paging works with a two-level scheme that permits the sparse allocation of address space, so that the whole address space, or even all of the address space mapping information, need not be present. Otherwise, a 4 gigabyte process would require more than 4 Mbyte of page tables, even though it may be the case that only a few thousand would be active at any time. Typically, for our purposes, only three pages of page tables are allocated per process (page directory and the top and bottom address space page tables). This is sufficient to run a 4-Mbyte process (instruction plus data size) and 4 Mbyte of stack. (Note that all processes run with a full-sized address space and can dynamically grow to use it.) This mechanism is quite successful in reducing memory-management overhead.
The two-level scheme splits the incoming virtual address into three parts: 10 bits of page table directory index, 10 bits of page table index, and 12 bits of offset within a page. The page table directory is a single page of physical memory that facilitates allocation of page table space by breaking it up into 4-Mbyte chunks of linear address space per each of its 1024 PDEs (Page Directory Entry), which determine the location of underlying page tables in physical memory.
Each PDE-addressed page of a page table contains 1024 PTEs (Page Table Entry). A PTE is similar in form and function to a PDE. The major difference between a PDE and a PTE is that a PTE selects the physical page frame for the desired reference. Once the frame offset least-significant address bits are obtained, the final address is determined. This method is identical to that used in many other common microprocessors (the MC68030, Clipper, and NS32532, among others).
Each PDE and PTE may be marked either "invalid" (not currently used) or "valid" (the underlying page of physical memory is present). In addition, other attribute bits mark entries as "read only" or "read-write" and "supervisor" or "user." Because segmentation is not used to control memory protection, we keep processes honest by relying entirely on the paging mechanism's attributes for protection as well as for the allocation of memory.
The 386 paging mechanism impacts the 386BSD specification with respect to address space allocation constants: Each page is 4K byte in size and must reflect the minimum granularity of address space allocation, while each page of page tables maps 4 Mbyte of address space. These constants determine address boundaries used to allocate memory and share address space between similar processes. Shared objects starting on 4-Mbyte boundaries can share page tables as well as underlying physical memory.
Page size granularity is important to the layout of executable files. Instruction and data regions are arranged into discrete and aligned memory page units, so that it is possible to demand load pages that may be either "read-only" (instructions) or "read-write" (data or stack). The page table size granularity is typically located at the beginning of each user, user stack, and kernel address space. It is possible to share these among many processes, obviating the need for separate page tables. As a result, while each process has its own page table directory, the top eight PDEs of each process page table directory point to the same kernel page tables. Thus, the kernel's portion of address space is global to all other processes.