The idea: two ways to map a program into memory
A program uses addresses that are not the real ones. The CPU's memory management unit turns each of them into a physical address on every access. There are two classic ways to do it. Segmentation gives each part of the program (code, data, heap, stack) one block of memory of whatever size it needs. Paging cuts everything into small blocks of the same size, pages, and puts each page wherever there is room. x86 CPUs have both, one after the other, and Linux turns the first one into a no-op.
On the canvas the same processes are loaded twice into the same 64 KiB of physical memory: on the left by segmentation, on the right by paging with 4 KiB pages. The kernel owns the first 8 KiB on both sides. Below them, the Linux strip shows what a 64-bit Linux process really does with its segment registers.
Segmentation: base, limit, permissions
An address is a pair, segment:offset. The segment picks a descriptor from a table. The
descriptor holds a base (where the block starts in physical memory), a limit (its size) and
permissions. The CPU checks offset < limit and the permissions, then computes
base + offset. If a check fails, it raises a general-protection fault (#GP) and the OS kills the process.
On the canvas, A's data segment has base 0x4000 and limit 0x1000, so
data:0x0A00 is physical 0x4A00 (Demo 1: same access, two schemes) and
data:0x1400 is refused (Demo 2: past the end of a segment).
Paging: pages, frames and the page table
Here an address is one number, the virtual address. Its low 12 bits are the offset inside a 4 KiB page.
The bits above them are the page number (VPN). The process's page table maps each VPN to a
frame (a 4 KiB slot of physical memory), with a present bit and permission bits per page. The physical
address is frame × 4096 + offset. A missing or forbidden page raises a page fault; the kernel
either fixes the mapping or sends SIGSEGV.
The canvas uses a toy 16-bit address space with 16 pages: code at 0x0000, data at 0x4000, heap at
0x6000, libraries at 0x8000 and the stack at 0xF000. The same byte as above,
data:0x0A00, is virtual address 0x4A00: VPN 4, which A's page table maps to frame 2, so it lands at
0x2A00. Real x86-64 has 48-bit addresses and a four-level table; see
Linux Virtual Memory for the walk and the TLB.
Fragmentation: external vs internal
Blocks of different sizes come and go, so free memory with segmentation ends up as holes between them. That is external fragmentation: there can be enough memory in total but no single hole big enough. The OS can then compact memory, sliding blocks down to merge the holes. That means copying them, and the processes wait meanwhile.
In Demo 6: external fragmentation A, B and C are loaded and B exits. Now 19 KiB are free, but the largest hole is 15 KiB, and A wants to map a 16 KiB library. Segmentation must slide C down (18 KiB copied) before the library fits. Paging just takes the 4 free frames, wherever they are.
Paging has no external fragmentation, because every hole is a whole frame and any page fits any frame. It pays with internal fragmentation instead: a 3 KiB heap still takes a 4 KiB page, so the last page of each region has an unused tail (grey on the canvas). With A, B and C loaded that is 4 KiB in total. Real pages are 4 KiB and real regions are big, so the waste is about half a page per region.
Growing, sharing and protecting
| segmentation | paging | |
|---|---|---|
| unit | one block per region, any size | fixed 4 KiB pages |
| table entry | base, limit, permissions per segment | frame, present, R/W, U/S, NX per page |
| free memory | holes of any size: external fragmentation | whole frames: internal fragmentation in last pages |
| a region grows | extend in place, or copy it to a bigger hole | map one more page into any frame |
| protection | exact to the byte (the limit) | per 4 KiB page |
| sharing | whole segments | single pages (copy-on-write after fork()) |
| swapping | whole segments | single pages, on demand |
| table size | a few entries per process | one entry per page (hence multi-level tables and a TLB) |
In Demo 5: heap grows by 4 KiB, A's heap can't grow in place because A's stack sits right after it, so segmentation copies the heap to a free hole and leaves a 3 KiB hole behind. Paging maps one more frame and moves nothing.
Protection cuts both ways. A write to code is caught by both: the segment is R-X, and the page table entry
has R/W = 0 (Demo 4: write to code). But a write 256 bytes past the end of A's 3 KiB heap is caught only by the
segment limit. The page is 4 KiB and present, so paging lets the write land in the unused tail
(Demo 3: small overflow). This is why tools like AddressSanitizer and guard pages exist on paged systems.
What Linux does on x86-64
A 32-bit x86 CPU in protected mode always applies segmentation before paging: logical address →
linear address → physical address. Linux never wanted segments. It set up a
flat model: the kernel and user code and data segments (__KERNEL_CS, __KERNEL_DS,
__USER_CS, __USER_DS) all have base 0 and a 4 GiB limit. So the linear address equals the offset,
and paging does all the placement and protection. In 64-bit long mode the CPU ignores the base and limit of CS, DS, ES and SS
entirely.
Two segment registers kept their base: FS and GS. glibc points FS at each thread's
thread-local storage (with arch_prctl(ARCH_SET_FS)), so fs:0x28 is the stack
canary that -fstack-protector checks. The kernel points GS at its per-CPU area and switches it
on kernel entry with swapgs. Demo 7: how Linux does it shows both kinds of access.
The words "segment" and "segmentation fault" stayed. A program's text, data, heap and stack segments are, on Linux,
VMAs (virtual memory areas): ranges of pages with the same permissions, listed in
/proc/<pid>/maps. A "segmentation fault" is a page fault that the kernel can't fix: no VMA covers the address,
or the VMA doesn't allow that access.
A short history
- 8086 (1978): segments without protection. Physical = segment × 16 + offset, to reach 1 MiB with 16-bit registers.
- 80286 (1982): protected mode. Segment registers hold selectors into descriptor tables (GDT, LDT) with base, limit and privilege level.
- 80386 (1985): 32-bit segments plus paging underneath. Linux (1991) first gave each process its own 64 MiB segment in the LDT, and soon moved to the flat model.
- x86-64 (2003): long mode drops base and limit for CS, DS, ES and SS; only FS and GS keep a base.
- Multics (1960s): combined both: each segment was itself paged. That idea lives on in VMAs.
See also Paging and Page Replacement (what happens when frames run out), Virtual Memory in Hardware (the page table and TLB as circuits) and Linux Context Switch (loading CR3, the page table base, on a switch).
What the page leaves out
Real addresses are 48 bits wide and the page table has four or five levels, cached by a TLB. Real Linux maps pages lazily, at the first touch, and can swap them out; here every page of a region is mapped at load. The segment side has no LDT, no privilege levels, no call gates and no expand-down stack segments. Shared libraries are not shared between processes here, and there is no swapping on either side.