x86 Addressing and the Segment Descriptor Tables
jake May 11th, 2007
It’s easy to think of a C pointer as containing a physical memory location; if my program calls int x = 42; int *p = &x; printf("p = 0x%p\n", p); and the output is p = 0xdeadbeef, I could imagine that dereferencing p would actually set the address bus to 11011110101011011011111011101111 = 0xdeadbeef to read its value. The real story of the x86 is a bit more complicated…
The Intel 8086 has a 20-bit address bus, capable of addressing one megabyte (2^20 bytes) of memory, but only a 16-bit data bus — all registers are 16 bits wide. To access the entire address space, then, an offset stored in one of the general purpose registers is added to the base address of a memory segment. The segment number is stored in one of the segment registers (CS, where program code resides; SS, for the stack, DS, for global data, and ES, often used for extra program data like strings), and the final address is computed as segment*16 + offset.
The 80286 introduces a 16-bit protected mode, in which the segment registers no longer index physical locations in memory, but rather contain a 13-bit index into a table of 8-byte segment descriptors. 24 bits of these 8 bytes contain a base address, and physical addresses are computed by adding the offset directly to it, allowing 2^24 bytes = 16MiB to be addressed. The descriptors also contain segment limits, allowing the kernel to detect when a piece of code addresses memory it’s not supposed to.
There are three table types: the global descriptor table, the interrupt descriptor table, and local descriptor tables. There is a single global table which is available to all processes, but each process can have its own local table. The tables can be located anywhere in memory, and there are special instructions (lgdt, lidt, and lldt) for setting them up. These instructions tell the CPU about both the location and size of the tables; since the table index from the segment register is 13 bits, the maximum table length is 8192 entries.
In addition to the 13-bit table index, the segment register also contains a bit which selects between the global table or the current local table (the remaining two bits specify a privilege level, which I won’t discuss here). The x86 architecture distinguishes between the logical address stored in the segment and offset registers visible to the programmer and the linear address, which the CPU forms using the segmentation table lookup. Since we have 13 + 1 bits in the segment register used for addressing and 16 bits in the offset register, logical addresses in the 286 are 30 bits long. The documentation for the 286 will refer to 1 GiB of virtual address space, which refers to logical addressing. Of course, the address bus on the 286 is only 24 bits, and the mapping of logical addresses to linear addresses is not bijective, since the segments described in a descriptor table can overlap. In practice, the CPU raises an exception when a segment register contains a table index which is out of bounds, and the kernel can trap this exception to retrieve the data from its virtual memory implementation.
When protected mode was introduced with the 80286, the old 8086-style of addressing was referred to as real mode. To remain compatible with older code, the 80286 defaults to real mode and must be explicitly told to go into protected mode, from which it could not return without resetting the chip.
The intel 80386 was introduced in 1985 and extended the data bus to 32 bits. The segment registers were still 16 bits, but the segment descriptors they indexed were extended to allow 32-bit base addresses and handle 32-bit offset limits. This scheme is known as 32-bit protected mode.
Since the 386 allows each segment to address 2^32 = 4 Gib of linear address space, it is possible to set up one segment each for code and data, and not worry about segmentation; in fact, this is how the Linux kernel operates. The nice protection features allowed by segment limits can be implemented using the hardware’s paging mechanisms, which are not so x86-specific. I’ll write about paging in a future article.