CSE Roadmap

Common tier · about 5 hours · 6 parts

Part 2 of 6 · 2 min read

Segments

In plain words: A book has chapters of different lengths, and a reader refers to "page 12 of chapter 3". A program is also made of parts of different lengths: its code, its heap, its stack. Segmentation gives each part its own region. An address has two numbers: the segment number, and the offset inside the segment. The hardware has a segment table, with a base and a limit for each segment. This is the base and limit of page 1, once for each part. The analogy stops in one place: a book's chapters are all fixed once printed, while a heap segment may need to grow.

Here is a made-up segment table:

Segment Use Base Size (limit) Allowed
0 Code 32,768 2,048 read, execute
1 Heap 40,960 3,000 read, write
2 Stack 28,672 2,048 read, write

Translations of (segment, offset) pairs:

Address Offset below limit? Physical address
(0, 100) 100 < 2,048: yes 32,768 + 100 = 32,868
(1, 2,999) 2,999 < 3,000: yes 40,960 + 2,999 = 43,959
(1, 3,000) 3,000 is not below 3,000 Trap
(2, 40) 40 < 2,048: yes 28,672 + 40 = 28,712
(0, 2,048) 2,048 is not below 2,048 Trap

Segmentation has good points. Each part has its own protection (the code segment is read-only), its own size, and it can be shared. But segments have different lengths, so the memory manager meets external fragmentation again (page 2): a segment must fit in one hole. Systems that used segmentation, such as early Intel processors, added paging below the segments, so that each segment was a set of pages. That removes the fragmentation, and keeps the protection.

Modern 64-bit x86 hardware has made segmentation nearly empty. In 64-bit mode the base of the main segments is forced to 0 and the limits are not checked, so the whole address space is one flat segment. Two segment registers, FS and GS, still hold a base address, and Linux uses FS to find the thread-local storage of each thread (Level 2). The protection that segments gave now comes from the control bits of the page table entries, as in section 2.

Segment

A segment is a region of an address space that holds one logical part of a program, such as its code or its stack, with its own base, size and permissions; an address names the segment and an offset inside it.

Example: the address (1, 2,999) is byte 2,999 of segment 1, and it is valid only if the size of segment 1 is greater than 2,999.

Check yourself: 1. Using the table above, translate (2, 2,047) and (1, 0). 2. Why does segmentation bring back external fragmentation? 3. What does Linux still use a segment register for on x86-64?