4-6 Vol. 3A
PAGING
4.2
HIERARCHICAL PAGING STRUCTURES: AN OVERVIEW
All three paging modes translate linear addresses using hierarchical paging structures. This section provides an
overview of their operation. Section 4.3, Section 4.4, and Section 4.5 provide details for the three paging modes.
Every paging structure is 4096 Bytes in size and comprises a number of individual entries. With 32-bit paging,
each entry is 32 bits (4 bytes); there are thus 1024 entries in each structure. With PAE paging and IA-32e paging,
each entry is 64 bits (8 bytes); there are thus 512 entries in each structure. (PAE paging includes one exception, a
paging structure that is 32 bytes in size, containing 4 64-bit entries.)
The processor uses the upper portion of a linear address to identify a series of paging-structure entries. The last of
these entries identifies the physical address of the region to which the linear address translates (called the page
frame). The lower portion of the linear address (called the page offset) identifies the specific address within that
region to which the linear address translates.
Each paging-structure entry contains a physical address, which is either the address of another paging structure or
the address of a page frame. In the first case, the entry is said to reference the other paging structure; in the
latter, the entry is said to map a page.
The first paging structure used for any translation is located at the physical address in CR3. A linear address is
translated using the following iterative procedure. A portion of the linear address (initially the uppermost bits)
selects an entry in a paging structure (initially the one located using CR3). If that entry references another paging
structure, the process continues with that paging structure and with the portion of the linear address immediately
below that just used. If instead the entry maps a page, the process completes: the physical address in the entry is
that of the page frame and the remaining lower portion of the linear address is the page offset.
The following items give an example for each of the three paging modes (each example locates a 4-KByte page
frame):
•
With 32-bit paging, each paging structure comprises 1024 = 2
10
entries. For this reason, the translation
process uses 10 bits at a time from a 32-bit linear address. Bits 31:22 identify the first paging-structure entry
and bits 21:12 identify a second. The latter identifies the page frame. Bits 11:0 of the linear address are the
page offset within the 4-KByte page frame. (See Figure 4-2 for an illustration.)
•
With PAE paging, the first paging structure comprises only 4 = 2
2
entries. Translation thus begins by using
bits 31:30 from a 32-bit linear address to identify the first paging-structure entry. Other paging structures
comprise 512 =2
9
entries, so the process continues by using 9 bits at a time. Bits 29:21 identify a second
paging-structure entry and bits 20:12 identify a third. This last identifies the page frame. (See Figure 4-5 for
an illustration.)
•
With IA-32e paging, each paging structure comprises 512 = 2
9
entries and translation uses 9 bits at a time
from a 48-bit linear address. Bits 47:39 identify the first paging-structure entry, bits 38:30 identify a second,
bits 29:21 a third, and bits 20:12 identify a fourth. Again, the last identifies the page frame. (See Figure 4-8
for an illustration.)
The translation process in each of the examples above completes by identifying a page frame; the page frame is
part of the translation of the original linear address. In some cases, however, the paging structures may be
configured so that the translation process terminates before identifying a page frame. This occurs if the process
encounters a paging-structure entry that is marked “not present” (because its P flag — bit 0 — is clear) or in which
a reserved bit is set. In this case, there is no translation for the linear address; an access to that address causes a
page-fault exception (see Section 4.7).
In the examples above, a paging-structure entry maps a page with a 4-KByte page frame when only 12 bits remain
in the linear address; entries identified earlier always reference other paging structures. That may not apply in
other cases. The following items identify when an entry maps a page and when it references another paging struc-
ture:
•
If more than 12 bits remain in the linear address, bit 7 (PS — page size) of the current paging-structure entry
is consulted. If the bit is 0, the entry references another paging structure; if the bit is 1, the entry maps a page.
•
If only 12 bits remain in the linear address, the current paging-structure entry always maps a page (bit 7 is
used for other purposes).
If a paging-structure entry maps a page when more than 12 bits remain in the linear address, the entry identifies
a page frame larger than 4 KBytes. For example, 32-bit paging uses the upper 10 bits of a linear address to locate
the first paging-structure entry; 22 bits remain. If that entry maps a page, the page frame is 2
22
Bytes = 4 MBytes.