Paged Memory Management in the 80386
INTEL introduced the 80386 chip in 1985.
It was the first 32-bit microprocessor in the 80×86 series, and its manufacturing process was also a major advance. Compared with the 80286, the 80386 contained 275,000 transistors. Its clock frequency was initially 12.5 MHz and was later increased to 20 MHz, 25 MHz, and 33 MHz. Both the internal and external data buses of the 80386 were 32 bits wide, as was its address bus, allowing it to address up to 4 GB of memory. In addition to real mode and protected mode, it added an operating mode called virtual 8086 mode, which could provide multitasking capabilities by simultaneously emulating multiple 80×86 processors. In addition to the standard 80386 chip—the 80386DX—INTEL subsequently introduced several other 80386 variants for different markets and applications: the 80386SX, 80386SL, 80386DL, and others.
The most classic 80386 product was the 80386DX-33MHz, which is generally what we mean when we refer to the 80386. To address the memory speed bottleneck, Intel designed a high-speed cache (Cache) for the 80386, using memory prefetching to alleviate the bottleneck. The original design called for the 80386 to include an L1 Cache, but because of constraints involving the manufacturing process, cost, development schedule, and other factors, the final 80386 did not have a built-in L1 Cache. Instead, the specially developed L1 Cache chip was placed on the motherboard outside the CPU. From then on, however, Cache and the CPU became inseparable. The 80386 also had highly advanced memory management, with three modes—paging, segmentation, and segmentation with paging—capable of managing a vast memory space and thus giving applications ample room to operate. These three memory management modes correspond to enabling the segmentation and paging units separately or enabling both at the same time.
As shown in the figure, two 32-bit address paths emerge from the arithmetic logic unit (ALU), one for reading source operand data and the other for reading the destination operand. An address is first sent to the segmentation unit; if that unit is not enabled, the address passes transparently to the paging unit. An address produced by the ALU is called a logical address. After a logical address is input to the segmentation unit, it outputs a linear address (also called a virtual address in Linux). After that linear address is input to the paging unit, the paging unit outputs a physical address.
The paging unit divides memory neatly into 4K page frames and organizes these page frames into a two-level directory structure. A linear address is likewise understood as consisting of three parts: a directory index, a page table index, and an offset within the page.
• Directory index, PD (Page Directory)
• Page table index, PT (Page Table)
The directory index retrieves a directory entry from the page directory. The directory entry is a pointer to a page table. The page table index retrieves a page table entry from that page table, and the page table entry contains a page frame number. The paging unit combines the page frame number with the offset within the page to obtain the actual physical address corresponding to the linear address.
Page directories and page tables at every level are usually referred to collectively as page tables. Like segment descriptor tables, each process has its own page tables. Whenever a process resumes execution, the starting address of its page tables is placed in the CR3 register.
When the CPU encounters a memory-access instruction, translating the logical address into a linear address is very simple: it merely adds the segment base of the current data segment, code segment, or extra segment selector to the offset address in the instruction. Because the contents of the segment descriptor corresponding to a segment selector have already been loaded into that selector’s shadow register, this process does not involve accessing memory to retrieve the segment descriptor. During a given period, the CPU accesses only data within the segments described by the segment descriptors corresponding to its current memory segment selectors. When a segment switch is required, the program explicitly modifies the CS, DS, or ES register.
Translating a linear address into a physical address is different. Because it is completely impossible to predict which physical page will contain the memory accessed by a program, translating a linear address into a physical address requires accessing the corresponding page table entry (or page directory entry) in memory. Having to access one memory location before being able to access another is rather absurd. A TLB, or Translation Lookaside Buffer, was therefore added to the CPU. The TLB is a high-speed cache for the page table, equivalent to a dedicated section of Cache. Because program execution also exhibits locality, the TLB hit rate is very high. Even so, on a TLB miss, the CPU must still load the page table from memory to determine the physical address corresponding to the linear address.
The TLB has relatively few entries; the 80386 has 32. Each TLB entry contains information about one page: a valid bit, virtual page number, modified bit, protection code, and the number of the physical page containing it. These correspond one-to-one with entries in the page table.
Because the TLB is a cache of the page table and every process has different page tables, while CR3 stores the address of the current process’s page tables, CR3 is reloaded during a process switch; reloading CR3 invalidates the contents of the TLB. The TLB is flushed even when the contents of CR3 are the same before and after the reload, and this technique is commonly used to flush the TLB.
The 80386 supports only a two-level page table structure because memory capacities were still very small at the time. Even 4 MB was considered a large amount of memory (it was the minimum requirement for Windows 95), while running DOS required only 1 MB. With the Pentium Pro, paging can use three levels.
Page Directory Entries and Page Table Entries
A two-level page table is organized as shown below:
A given linear address is divided into three parts: DIR, TABLE, and OFFSET.
Translation into a physical address takes three steps: (1) CR3 is the starting address of the page directory, and the location at CR3+DIR gives the starting address of the page table; (2) TABLE is used to index into the page table, yielding a page table entry; and (3) bits 12~31 are taken from the page table entry as the upper 24 bits of the physical address, while the lower 12 bits of the linear address—OFFSET—are used as the lower 12 bits of the physical address, forming a 32-bit physical address.
In a 32-bit page table entry, in addition to the upper 24 bits serving as the upper 32 bits of the physical address (and also as the page frame number), there are another 12 bits used as flags. These flags indicate whether the current page frame is dirty, whether it is readable and writable, whether it contains user or system memory, whether the memory has been accessed, and so on.
The Linux kernel initially used three-level page tables and adopted four-level page tables after version 2.6.11. The principle is the same as for two-level page tables.
For processors that support multilevel page tables, the OS can select the number of page table levels it supports by configuring a register, as well as how many bits of the linear address represent each level. (I have not yet found information on exactly which register this is; it will be added later).
Control Registers
With segmented memory, the starting address of the segment descriptor table is loaded into the LDTR register. With paged memory management, the starting address of the page table is loaded into the CR3 register.
The segmentation unit can be enabled through bit 0 of CR0, while the paging unit is enabled through bit 31 of CR0. Enabling both produces segmented-paged memory management.
CR0
The lower 16 bits of CR0 contain the same bit definitions as the 80286 MSW, maintaining compatibility with the 80286 as well as with the two instructions introduced with the 80286, LMSW and SMSW. The LMSW and SMSW instructions load and save machine status word information, respectively, while CR0 can be read and written with the MOV instruction. The bits in CR0 have the following meanings:
PE (Protection Enable), the protected mode enable bit, is used to place the CPU in protected virtual-address mode. PE=0 means the CPU is operating in real-address mode; PE=1 means the CPU is operating in protected virtual-address mode.
MP (Monitor Coprocessor) monitors the coprocessor. MP=1 means the coprocessor is operating; MP=0 means the coprocessor is not operating.
EM (Emulation) controls coprocessor emulation. When MP=0 and EM=1, the coprocessor is being emulated in software.
TS (Task Switched) indicates a task switch. Whenever a task switch occurs, TS=1; when the task switch is complete, TS=0. The coprocessor is not permitted to operate while TS=1.
ET (Extension Type), the processor extension type, reflects the type of coprocessor installed: ET=0 indicates the 80287, and ET=1 indicates the 80387.
PG (Paging) enables the paging mechanism. The paging mechanism operates when PG=1 and does not operate otherwise.
NE (Numeric Error) controls numeric-exception interrupts. When NE=1, a fault occurring during execution of a coprocessor instruction is handled by an exception interrupt; when NE=0, it is handled by an external interrupt.
WP (Write Protect) provides write protection. When WP=1, writing to a read-only page generates a page fault.
AM (Alignment Mask) is the alignment flag. AM=1 permits alignment checking, while AM=0 does not. Alignment was introduced when discussing the AC flag in EFLAGS. In CPUs from the 80486 onward, CPU alignment checking requires three conditions: AC=1, AM=1, and a current privilege level of 3.
NW (Not Write-through) and CD (Cache Disable) both control the CPU’s internal CACHE. CACHE is enabled when NW=0 and CD=0; the other combinations are more complicated.
The first four definitions date from the 80286, the next two from the 80386, and the final four from the 80486.
CR1
The CR1 register is reserved for future development of Intel microprocessors;
CR2
The CR2 register contains a 32-bit linear address pointing to the address of the most recent page fault. CR2 is valid only when PG=1. When the page fault handler is activated, the error code pushed onto the page fault handler’s stack provides status information about the page fault;
CR3
The CR3 register contains the physical base address of the physical page directory table. Because each page is 4 KB, the 80386 page directory table is always located on an integral page boundary, and the lower 13 bits of CR3 are always 0. The page directory base address in CR3 is valid only when PG=1 in CR0.
Comments