Segmentation Concepts - Learning Module

Loading content...

0/227

Segment Table

The Engine Behind Segmentation

Everything we've discussed about segmentation—logical organization, variable sizes, protection, sharing—depends on a single critical data structure: the segment table.

The segment table is the bridge between logical addresses (segment, offset) and physical addresses. It stores, for each segment, where that segment resides in physical memory, how large it is, and what access permissions it has. Without the segment table, segmentation would be pure concept with no implementation.

Understanding the segment table means understanding how segmentation actually works at the hardware level. It's where policy meets mechanism, where the programmer's logical view transforms into physical reality, and where protection decisions become enforced guarantees.

What You Will Learn

By the end of this page, you will understand: the structure and purpose of the segment table, the anatomy of a segment table entry (base, limit, permissions), how the hardware uses the segment table for address translation, segment table registers and their role, protection checking during translation, how segment tables enable sharing between processes, implementation considerations and optimizations, and the relationship to modern segment descriptors.

What is the Segment Table?

The segment table is an array of segment descriptors, one per segment. Each process has its own segment table, defining its unique view of memory. When a process references memory using a (segment, offset) address, the hardware:

Uses the segment number to index into the segment table
Retrieves the segment descriptor (base, limit, permissions)
Validates the access (offset < limit, permissions allow operation)
Computes the physical address (base + offset)

The segment table is to segmentation what the page table is to paging—the essential translation mechanism.

Converting Mermaid diagram...

Key Properties:

Per-Process: Each process has its own segment table. Segment 2 in Process A points to different physical memory than Segment 2 in Process B (unless sharing).
Indexed by Segment Number: The segment table is an array. Segment number N maps to entry[N]. This makes lookup O(1).
Kernel Managed: The operating system creates and maintains segment tables. User processes cannot modify their own segment tables directly—that would compromise protection.
Hardware Accessed: During every memory reference, the hardware (MMU or CPU) reads the relevant segment table entry. This must be extremely fast.
Cached for Performance: Because segment table lookups are frequent, segment descriptors are cached in segment registers (x86) or TLB-like structures.

The Segment Table as a Contract

Think of the segment table as a contract between the OS and the process. The OS guarantees: 'Here are your segments, their locations, sizes, and permissions.' The hardware enforces this contract on every memory access. The process cannot exceed these bounds or violate these permissions—the hardware physically prevents it.

Segment Table Entry Structure

Each entry in the segment table (a segment descriptor or segment table entry) contains all the information needed to translate and validate a memory access. The exact structure varies by architecture, but the essential components are universal.

Core Components:

Segment Table Entry Fields
Field	Size (typical)	Purpose
Base Address	32-64 bits	Physical address where segment starts
Limit	16-32 bits	Size of segment (highest valid offset)
Present (P)	1 bit	Is segment currently in physical memory?
Read (R)	1 bit	Is reading permitted?
Write (W)	1 bit	Is writing permitted?
Execute (X)	1 bit	Is execution permitted?
Privilege Level (DPL)	2 bits	Required privilege to access (0-3)
Direction/Expand	1 bit	Growth direction (up for data, down for stack)
Accessed (A)	1 bit	Has segment been accessed since loaded?
Granularity (G)	1 bit	Is limit in bytes or pages?

segment_table_entry.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// Conceptual segment table entry structure
 
typedef struct segment_table_entry {
    // Address Translation
    uint64_t base;          // Physical base address of segment
    uint32_t limit;         // Size of segment (max valid offset)
    
    // Validity
    uint8_t  present : 1;   // 1 = in memory, 0 = swapped/invalid
    
    // Protection Bits
    uint8_t  readable : 1;  // Can read from this segment
    uint8_t  writable : 1;  // Can write to this segment
    uint8_t  executable : 1;  // Can execute code from this segment
    
    // Privilege Level (0 = kernel, 3 = user)
    uint8_t  dpl : 2;       // Descriptor Privilege Level
    
    // Type Information
    uint8_t  is_code : 1;   // 1 = code segment, 0 = data segment
    uint8_t  expand_down : 1;  // 1 = stack (grows down), 0 = normal
    
    // Tracking
    uint8_t  accessed : 1;  // Set by hardware when accessed
    
    // Granularity
    uint8_t  granularity : 1;  // 0 = byte, 1 = page (4KB units)
    
} __attribute__((packed)) segment_table_entry_t;
 
// Example entries:
// Code segment:  base=0x10000, limit=0x5000, R+X, DPL=3
// Data segment:  base=0x20000, limit=0x8000, R+W, DPL=3
// Stack segment: base=0x70000, limit=0x1000, R+W, DPL=3, expand_down=1
// Kernel code:   base=0x80000, limit=0x10000, R+X, DPL=0

Field Details:

Base Address: The physical address where the segment begins. When the CPU calculates physical_address = base + offset, this is the base. May be any address; not required to be aligned (though alignment improves performance).

Limit: The highest valid offset within the segment. If limit = 0x1000 and offset = 0x1001, the access is invalid—segment violation. Some architectures (like x86) can interpret limit in byte or page (4KB) granularity.

Present Bit: Indicates whether the segment is currently in physical memory. If present = 0 and the segment is accessed, a segment-not-present fault occurs. The OS can then load the segment from disk (if it was swapped) and retry.

Protection Bits: Define what operations are permitted:

Read: Can fetch data from this segment
Write: Can store data to this segment
Execute: Can fetch instructions from this segment

Privilege Level (DPL): In systems with protection rings (like x86), the DPL specifies the minimum privilege required to access this segment. User code (ring 3) cannot access segments with DPL < 3.

The Expand-Down Bit for Stacks

For normal data segments, valid offsets are 0 to limit. For stack segments (expand_down = 1), valid offsets are limit+1 to 0xFFFF (or 0xFFFFFFFF for 32-bit). This allows stacks to grow downward: as the stack pointer decreases, it stays within bounds as long as it's above the limit. This elegant trick lets stacks grow toward lower addresses naturally.

Address Translation Process

Every memory access in a segmented system goes through the translation process. This happens in hardware for every instruction fetch, data read, and data write—billions of times per second. The process must be fast and precise.

Step-by-Step Translation:

Translation Algorithm

•Extract Segment Number: The CPU extracts the segment number from the logical address (often implicitly from the type of access: code fetch uses CS, stack access uses SS, data uses DS).
•Locate Segment Descriptor: Using the segment number as an index, locate the corresponding entry in the segment table. Entry address = table_base + (segment_number × entry_size).
•Check Present Bit: If present = 0, the segment is not in memory. Raise a segment-not-present fault. The OS handles loading the segment.
•Check Privilege Level: If the current privilege level (CPL) is greater than the DPL, access is denied. Raise a general protection fault.
•Check Bounds (Limit): If offset > limit (or offset ≤ limit for expand-down), the access exceeds segment bounds. Raise a segment fault.
•Check Access Type: If the access type (read/write/execute) is not permitted by the segment's protection bits, raise a protection fault.
•Compute Physical Address: All checks passed. Physical address = base + offset. Access proceeds to physical memory.

translation.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// Pseudocode: Hardware segment translation logic
 
physical_address_t translate(segment_number_t seg, offset_t offset, 
                             access_type_t access, privilege_t cpl) {
    
    // Step 1: Get segment table base (from STBR register)
    segment_table_entry_t* table = get_segment_table_base();
    
    // Step 2: Index into table
    segment_table_entry_t* entry = &table[seg];
    
    // Step 3: Check present
    if (!entry->present) {
        raise_fault(SEGMENT_NOT_PRESENT, seg);
        // OS handler may load segment and retry
    }
    
    // Step 4: Check privilege
    if (cpl > entry->dpl) {
        raise_fault(GENERAL_PROTECTION, "Privilege violation");
    }
    
    // Step 5: Check bounds
    if (!entry->expand_down) {
        // Normal segment: valid offsets are [0, limit]
        if (offset > entry->limit) {
            raise_fault(SEGMENT_FAULT, "Offset exceeds limit");
        }
    } else {
        // Expand-down segment (stack): valid offsets are [limit+1, max]
        if (offset <= entry->limit) {
            raise_fault(SEGMENT_FAULT, "Offset below stack limit");
        }
    }
    
    // Step 6: Check access type
    if (access == READ && !entry->readable) {
        raise_fault(PROTECTION_FAULT, "Read not permitted");
    }
    if (access == WRITE && !entry->writable) {
        raise_fault(PROTECTION_FAULT, "Write not permitted");
    }
    if (access == EXECUTE && !entry->executable) {
        raise_fault(PROTECTION_FAULT, "Execute not permitted");
    }
    
    // Step 7: Compute physical address
    entry->accessed = 1;  // Mark as accessed
    return entry->base + offset;
}

Translation Performance:

This seven-step process happens for every memory reference. At billions of references per second, even small inefficiencies compound. Hardware optimizations are essential:

Segment Descriptor Caches: Segment registers cache the full descriptor, not just the segment number. Loading a segment register is slow; using it thereafter is fast.
Parallel Checking: Bounds check, privilege check, and type check can happen simultaneously (combinational logic).
Speculative Translation: While previous instruction completes, the next instruction's translation begins speculatively.
Base Addition in Address Generation Unit (AGU): The base + offset addition happens in dedicated hardware designed for this purpose.

Every Fault Has a Handler

Each fault type (segment not present, protection, bounds) has a corresponding exception handler in the OS. The handler determines whether to: load the segment from disk (not present), terminate the process (invalid access), or signal the process (for debugging). The hardware raises the fault; the OS decides what it means.

Segment Table Registers

The hardware needs to know where the segment table is located and, for efficiency, caches frequently used segment descriptors. This is accomplished through special CPU registers.

Segment Table Base Register (STBR):

Every process has its own segment table located somewhere in memory. The Segment Table Base Register holds the physical address of the current process's segment table. When the OS switches between processes, it loads the new process's segment table address into the STBR.

Process A running: STBR = 0x100000 (A's segment table)
Context switch to Process B: STBR = 0x200000 (B's segment table)

Segment Table Length Register (STLR):

The Segment Table Length Register holds the number of entries in the segment table. This prevents accessing invalid segment numbers:

If (segment_number >= STLR) {
    raise_fault(INVALID_SEGMENT);
}

Together, STBR and STLR define the current segment table. The OS updates both during context switches.

Key Registers for Segmentation
Register	Purpose	Set By	Used By
STBR	Physical address of segment table	OS (context switch)	MMU (translation)
STLR	Number of entries in segment table	OS (context switch)	MMU (bounds check)
CS (Code Segment)	Cached code segment descriptor	CPU (on segment load)	CPU (instruction fetch)
DS (Data Segment)	Cached data segment descriptor	CPU (on segment load)	CPU (data access)
SS (Stack Segment)	Cached stack segment descriptor	CPU (on segment load)	CPU (push/pop/call/ret)
ES, FS, GS	Extra cached segment descriptors	CPU (on segment load)	CPU (explicit override)

Segment Registers as Descriptor Caches:

In x86 architecture, segment registers serve a dual purpose:

Visible Part: The 16-bit segment selector that programs can read/write
Hidden Part: The full segment descriptor (base, limit, attributes) cached from the segment table

When a program loads a segment register:

mov ax, 0x23    ; Segment selector 0x23
mov ds, ax      ; Load into DS

The CPU:

Uses selector 0x23 to index into the descriptor table
Loads the full descriptor (base, limit, access rights) into DS's hidden part
Subsequent DS-relative accesses use the cached descriptor—no table lookup needed

This is critical for performance: Without caching, every memory access would require a memory access to the segment table—doubling memory traffic.

segment_register.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// Conceptual structure of an x86 segment register
 
typedef struct segment_register {
    // Visible part (accessible to software)
    uint16_t selector;  // Segment selector value
    
    // Hidden/cached part (loaded from descriptor table)
    struct {
        uint32_t base;      // Cached base address
        uint32_t limit;     // Cached limit
        uint16_t attributes;  // Cached access rights
    } cached_descriptor;
    
} segment_register_t;
 
// When you execute: MOV DS, selector
// The CPU does:
void load_segment_register(segment_register_t* reg, uint16_t selector) {
    reg->selector = selector;
    
    // Look up descriptor in table
    descriptor_t* desc = get_descriptor(selector);
    
    // Cache the full descriptor
    reg->cached_descriptor.base = desc->base;
    reg->cached_descriptor.limit = desc->limit;
    reg->cached_descriptor.attributes = desc->attributes;
    
    // Now every DS:offset access uses cached.base + offset
    // No table lookup needed until DS is loaded again
}
 
// Result: One slow table lookup, then many fast cached accesses

Context Switch Must Save Segment Descriptors

When the OS switches between processes, it saves the current segment register contents (including cached descriptors) and loads the new process's segment registers. This is part of the process's context. On x86, segment selectors are saved; the cached parts are automatically reloaded when the selectors are restored.

Protection Through the Segment Table

The segment table is the enforcement mechanism for all segmentation-based protection. Every protection policy is encoded in segment descriptors and checked by hardware on every access.

Protection Checks Performed:

Hardware Protection Checks

•Bounds Checking — Offset must be within [0, limit] for normal segments or [limit+1, max] for expand-down. Prevents buffer overflows from accessing other segments.
•Read Permission — Descriptor's readable bit must be set for data reads. Some systems allow execute-only code (not readable—prevents code disclosure).
•Write Permission — Descriptor's writable bit must be set. Code segments are never writable (at runtime). Read-only data segments prevent modification.
•Execute Permission — Descriptor's executable bit must be set for instruction fetches. Data segments should never be executable (prevents code injection).
•Privilege Level — Current Privilege Level (CPL) must be numerically ≤ Descriptor Privilege Level (DPL). Ring 3 cannot access Ring 0 segments.
•Type Checking — Can't load a code segment descriptor into DS (data segment register). Can't execute from a non-code descriptor.

Protection Example Scenarios:

Protection Violations and Results
Attempt	Descriptor State	Result	Fault Type
Read offset 0x2000	Limit = 0x1000	Blocked	#GP (bounds violation)
Write to code segment	Writable = 0	Blocked	#GP (write protection)
Execute data segment	Executable = 0	Blocked	#GP (execute protection)
User access kernel seg	DPL = 0, CPL = 3	Blocked	#GP (privilege violation)
Access swapped segment	Present = 0	Blocked	#NP (not present)
Valid access within bounds	All checks pass	Permitted	N/A

Privilege Levels (Protection Rings):

The x86 architecture implements four protection rings (0-3):

Ring 0 (Kernel): Full hardware access, all segments
Ring 1 (Services): Device drivers (rarely used in practice)
Ring 2 (Services): Less privileged drivers (rarely used)
Ring 3 (User): Applications, limited to user segments

Each segment descriptor has a DPL (Descriptor Privilege Level). A process running at CPL (Current Privilege Level) n can only access segments with DPL ≥ n.

User process (Ring 3):

Can access segments with DPL = 3
Cannot access segments with DPL = 0, 1, or 2
Cannot modify segment registers to bypass this (the checks apply to the selector, which is validated)

Kernel (Ring 0):

Can access all segments regardless of DPL
Can modify segment tables (user processes cannot)
Runs when handling system calls, interrupts, exceptions

This hardware-enforced privilege separation is fundamental to OS security.

Hardware Enforcement is Unforgeable

Unlike software-only checks, hardware protection cannot be bypassed by buggy or malicious code. The CPU physically refuses to complete the memory access if any check fails. There's no 'ignore protection' mode accessible from user space. This is why segmentation-based protection (and its successor, paging-based protection) is trusted to isolate processes.

Sharing Through Segment Tables

Segment tables enable sharing by allowing multiple processes' segment table entries to point to the same physical memory. This is natural and elegant: sharing means "your entry and my entry have the same base address."

How Sharing Works:

Converting Mermaid diagram...

In the diagram above:

Process 1's segment 3 and Process 2's segment 3 both point to physical 0x20000
That region contains a shared library
One copy in physical memory serves both processes
All other segments are private (different base addresses)

Requirements for Sharing:

Same Base Address: Both descriptors must point to the same physical memory
Compatible Limits: The limits should match (or the smaller limit applies for safety)
Appropriate Permissions: Shared code is typically R+X (read, execute). Shared data requires careful coordination if writable.

Sharing Scenarios:

What's Shared	Permissions	Notes
Code segment (same program)	R+X	Multiple instances of the same program
Shared library code	R+X	libc shared by hundreds of processes
Read-only data	R	Constants, lookup tables, fonts
Writable shared memory	R+W	IPC, requires synchronization

Reference Counting:

The OS tracks how many processes reference each shared segment. When a process exits:

Decrement reference count for each segment
If count reaches zero, the segment can be deallocated
If count > 0, the segment remains for other sharers

shared_segment.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// OS implementation of segment sharing
 
typedef struct shared_segment_info {
    physical_address_t base;  // Physical memory location
    size_t size;              // Segment size
    int ref_count;            // Number of processes sharing
    int permissions;          // Protection attributes
} shared_segment_t;
 
// When Process P wants to share segment S:
void map_shared_segment(process_t* p, int seg_num, shared_segment_t* shared) {
    // Point process's segment table entry to shared memory
    p->segment_table[seg_num].base = shared->base;
    p->segment_table[seg_num].limit = shared->size;
    p->segment_table[seg_num].permissions = shared->permissions;
    p->segment_table[seg_num].present = 1;
    
    // Increment reference count
    shared->ref_count++;
    
    // Now p's segment_num accesses the same memory as all other sharers
}
 
// When Process P exits or unmaps a shared segment:
void unmap_shared_segment(process_t* p, int seg_num, shared_segment_t* shared) {
    // Invalidate entry
    p->segment_table[seg_num].present = 0;
    
    // Decrement reference count
    shared->ref_count--;
    
    // Free physical memory if no more sharers
    if (shared->ref_count == 0) {
        free_physical_memory(shared->base, shared->size);
        free(shared);
    }
}

Different Segment Numbers Can Share

Process A might share memory at its segment 5, while Process B accesses the same memory at its segment 12. The segment numbers don't have to match—only the base addresses. Each process organizes its own segment namespace independently.

x86 Segment Descriptors: Real Implementation

The Intel x86 architecture provides the most widely-known implementation of segmentation. Understanding x86 segment descriptors gives concrete insight into how these concepts are realized in hardware.

x86 Segment Descriptor Layout (8 bytes):

x86_descriptor.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// Intel x86 Segment Descriptor (64 bits / 8 bytes)
// This is the exact hardware layout
 
/* Bit layout:
 * 
 * Bytes 0-1: Limit (bits 0-15)
 * Bytes 2-3: Base (bits 0-15)
 * Byte 4:    Base (bits 16-23)
 * Byte 5:    Access byte
 *            [7]    Present (P)
 *            [6:5]  Descriptor Privilege Level (DPL)
 *            [4]    Descriptor type (S): 1=code/data, 0=system
 *            [3:0]  Type (depends on S bit)
 * Byte 6:    Flags + Limit
 *            [7]    Granularity (G): 0=byte, 1=4KB page
 *            [6]    Default operation size (D/B)
 *            [5]    64-bit code segment (L)
 *            [4]    Available for OS use (AVL)
 *            [3:0]  Limit (bits 16-19)
 * Byte 7:    Base (bits 24-31)
 */
 
typedef struct __attribute__((packed)) {
    uint16_t limit_low;       // Limit bits 0-15
    uint16_t base_low;        // Base bits 0-15
    uint8_t  base_mid;        // Base bits 16-23
    uint8_t  access;          // Access byte (type, DPL, present)
    uint8_t  flags_limit_hi;  // Flags + Limit bits 16-19
    uint8_t  base_high;       // Base bits 24-31
} segment_descriptor_t;
 
// Example: Create a code segment descriptor
// Base = 0x00000000, Limit = 0xFFFFF (4GB in page granularity)
// Ring 3 (user), Present, Code segment, Readable, Executable
 
segment_descriptor_t user_code_segment = {
    .limit_low     = 0xFFFF,      // Limit bits 0-15
    .base_low      = 0x0000,      // Base bits 0-15
    .base_mid      = 0x00,        // Base bits 16-23
    .access        = 0b11111010,  // P=1, DPL=11(3), S=1, Type=1010(code,readable)
    .flags_limit_hi= 0b11001111,  // G=1, D=1, L=0, AVL=0, Limit[19:16]=F
    .base_high     = 0x00         // Base bits 24-31
};
 
// This descriptor creates a 4GB code segment starting at address 0
// Accessible from ring 3, readable and executable

The Global Descriptor Table (GDT):

In x86, segment descriptors are stored in the Global Descriptor Table (GDT)—the system-wide segment table. The GDT register (GDTR) points to this table:

GDTR = { base = physical address of GDT, limit = size of GDT }

Segment Selectors:

x86 segment selectors are 16-bit values with three fields:

15            3  2  1 0
┌──────────────┬───┬───┐
│   Index      │TI │RPL│
└──────────────┴───┴───┘

Index (13 bits): Entry number in descriptor table
TI (1 bit): Table Indicator (0=GDT, 1=LDT)
RPL (2 bits): Requested Privilege Level

Example: Selector 0x1B = 0b00011011

Index = 3 (use descriptor at GDT[3])
TI = 0 (use GDT, not LDT)
RPL = 3 (request at privilege level 3)

Flat Model on x86:

Modern operating systems use a "flat" model where all segment bases are 0 and limits cover the entire address space. This effectively disables segment translation while retaining privilege checking:

Code segment: Base=0, Limit=4GB, Ring 0 or 3
Data segment: Base=0, Limit=4GB, Ring 0 or 3

// With base=0, segment:offset = offset (flat addressing)

This is why modern x86-64 essentially ignores segmentation for addressing while still using it for privilege levels.

Why x86 Descriptors Are So Complex

The x86 descriptor format seems bizarrely laid out—base and limit are split across non-contiguous fields. This is a legacy of the 80286 (which had 24-bit addresses) being extended for 32-bit in the 80386. Intel added fields at available bit positions rather than redesigning the format. Backward compatibility preserved the awkward layout into x86-64.

Segment Tables and Paging Together

Modern x86 systems use both segmentation and paging. The segment table produces a linear address, which then goes through page translation to produce a physical address. This two-stage translation combines the benefits of both schemes.

Two-Stage Translation:

Logical Address: (Segment, Offset)
         │
         v
    ┌─────────────┐
    │ Segment     │
    │ Translation │
    └─────────────┘
         │
         v
Linear Address (virtual address)
         │
         v
    ┌─────────────┐
    │ Page        │
    │ Translation │
    └─────────────┘
         │
         v
Physical Address

Translation Pipeline

•Logical Address → Segment table lookup → Linear Address: base + offset = linear address. Segment protection checks apply here.
•Linear Address → Page table lookup → Physical Address: Page directory → Page table → Frame number + offset. Page protection checks apply here.
•Physical Address → Memory: The actual RAM access finally occurs.

Why Both?

Segmentation provides:

Logical organization (code vs. data vs. stack)
Semantic protection (execute code, read/write data)
Privilege levels (kernel vs. user)
Variable-size logical units

Paging provides:

Fixed-size physical allocation (no external fragmentation)
Demand paging (load pages on demand)
Swapping (page out to disk)
Fine-grained memory management

Together they provide:

Logical segments with semantic meaning
Paged within each segment for efficient physical management
Two layers of protection (segment AND page permissions)
The programmer's view (segments) with the OS's efficiency (pages)

In Practice Today:

On x86-64, segment bases are forced to 0 in 64-bit mode, making the linear address equal to the offset. Segmentation is effectively disabled for addressing. However:

Privilege levels still enforce Ring 0 vs Ring 3
FS and GS registers are still usable with non-zero bases (for TLS)
Paging handles all memory management

So segmentation persists in vestigial form, while paging does the heavy lifting.

Segmented Paging: The Full Picture

Intel's design allows full use of both segmentation and paging, giving architects flexibility. Operating systems chose to emphasize paging for its benefits, but the segmentation machinery remains available. This architectural flexibility is part of why x86 has remained relevant for decades—it can adapt to different memory management philosophies.

Summary: The Segment Table

This page has provided a comprehensive exploration of the segment table—the data structure that implements all aspects of memory segmentation. Let's consolidate the key insights:

Key Takeaways

•The segment table is per-process, mapping segment numbers to physical locations with size limits and permissions.
•Segment table entries contain base address, limit, present bit, protection bits (R/W/X), and privilege level (DPL).
•Address translation is direct: physical_address = base + offset, with bounds and protection checks on every access.
•Segment registers cache descriptors for performance—loading the segment register fetches the descriptor; subsequent accesses use the cache.
•Protection is hardware-enforced via bounds checking, permission verification, and privilege level comparison—unforgeable from user space.
•Sharing is natural: multiple processes' segment table entries point to the same physical memory, with reference counting for lifecycle management.
•x86 implements segmentation with the GDT/LDT, segment selectors, and 8-byte descriptors—though modern systems use a flat model.
•Segmentation and paging combine: segment translation produces a linear address, paging produces the physical address, together providing logical organization with physical efficiency.

Module Complete:

With the segment table, we've completed our exploration of Segmentation Concepts. You now understand:

What segments are (logical, variable-size memory units)
The main segment types (code, data, stack)
Why variable sizes matter (matching program structure, but causing fragmentation)
The programmer's perspective (meaningful addresses, natural protection)
The implementation (segment tables with base, limit, permissions)

This foundational knowledge prepares you for the next module: Segment Tables in Depth, where we'll explore the finer details of segment table implementation, the segment table entry structure in various architectures, and advanced topics like segment table base registers and protection domains.

Module Complete

Congratulations! You've mastered the fundamental concepts of memory segmentation. You understand what segments are, how they're used, and how segment tables implement the translation and protection that makes segmentation work. This knowledge provides essential context for understanding both historical systems that relied on segmentation and modern systems that use segmentation concepts in software while relying on paging for physical memory management.

Segment Table

The Engine Behind Segmentation

Everything we've discussed about segmentation—logical organization, variable sizes, protection, sharing—depends on a single critical data structure: the segment table.

What You Will Learn

What is the Segment Table?

Uses the segment number to index into the segment table
Retrieves the segment descriptor (base, limit, permissions)
Validates the access (offset < limit, permissions allow operation)
Computes the physical address (base + offset)

The segment table is to segmentation what the page table is to paging—the essential translation mechanism.

Converting Mermaid diagram...

Key Properties:

Per-Process: Each process has its own segment table. Segment 2 in Process A points to different physical memory than Segment 2 in Process B (unless sharing).
Indexed by Segment Number: The segment table is an array. Segment number N maps to entry[N]. This makes lookup O(1).
Kernel Managed: The operating system creates and maintains segment tables. User processes cannot modify their own segment tables directly—that would compromise protection.
Hardware Accessed: During every memory reference, the hardware (MMU or CPU) reads the relevant segment table entry. This must be extremely fast.
Cached for Performance: Because segment table lookups are frequent, segment descriptors are cached in segment registers (x86) or TLB-like structures.

The Segment Table as a Contract

Segment Table Entry Structure

Core Components:

Segment Table Entry Fields
Field	Size (typical)	Purpose
Base Address	32-64 bits	Physical address where segment starts
Limit	16-32 bits	Size of segment (highest valid offset)
Present (P)	1 bit	Is segment currently in physical memory?
Read (R)	1 bit	Is reading permitted?
Write (W)	1 bit	Is writing permitted?
Execute (X)	1 bit	Is execution permitted?
Privilege Level (DPL)	2 bits	Required privilege to access (0-3)
Direction/Expand	1 bit	Growth direction (up for data, down for stack)
Accessed (A)	1 bit	Has segment been accessed since loaded?
Granularity (G)	1 bit	Is limit in bytes or pages?

segment_table_entry.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// Conceptual segment table entry structure
 
typedef struct segment_table_entry {
    // Address Translation
    uint64_t base;          // Physical base address of segment
    uint32_t limit;         // Size of segment (max valid offset)
    
    // Validity
    uint8_t  present : 1;   // 1 = in memory, 0 = swapped/invalid
    
    // Protection Bits
    uint8_t  readable : 1;  // Can read from this segment
    uint8_t  writable : 1;  // Can write to this segment
    uint8_t  executable : 1;  // Can execute code from this segment
    
    // Privilege Level (0 = kernel, 3 = user)
    uint8_t  dpl : 2;       // Descriptor Privilege Level
    
    // Type Information
    uint8_t  is_code : 1;   // 1 = code segment, 0 = data segment
    uint8_t  expand_down : 1;  // 1 = stack (grows down), 0 = normal
    
    // Tracking
    uint8_t  accessed : 1;  // Set by hardware when accessed
    
    // Granularity
    uint8_t  granularity : 1;  // 0 = byte, 1 = page (4KB units)
    
} __attribute__((packed)) segment_table_entry_t;
 
// Example entries:
// Code segment:  base=0x10000, limit=0x5000, R+X, DPL=3
// Data segment:  base=0x20000, limit=0x8000, R+W, DPL=3
// Stack segment: base=0x70000, limit=0x1000, R+W, DPL=3, expand_down=1
// Kernel code:   base=0x80000, limit=0x10000, R+X, DPL=0

Field Details:

Protection Bits: Define what operations are permitted:

Read: Can fetch data from this segment
Write: Can store data to this segment
Execute: Can fetch instructions from this segment

The Expand-Down Bit for Stacks

Address Translation Process

Step-by-Step Translation:

Translation Algorithm

•Extract Segment Number: The CPU extracts the segment number from the logical address (often implicitly from the type of access: code fetch uses CS, stack access uses SS, data uses DS).
•Locate Segment Descriptor: Using the segment number as an index, locate the corresponding entry in the segment table. Entry address = table_base + (segment_number × entry_size).
•Check Present Bit: If present = 0, the segment is not in memory. Raise a segment-not-present fault. The OS handles loading the segment.
•Check Privilege Level: If the current privilege level (CPL) is greater than the DPL, access is denied. Raise a general protection fault.
•Check Bounds (Limit): If offset > limit (or offset ≤ limit for expand-down), the access exceeds segment bounds. Raise a segment fault.
•Check Access Type: If the access type (read/write/execute) is not permitted by the segment's protection bits, raise a protection fault.
•Compute Physical Address: All checks passed. Physical address = base + offset. Access proceeds to physical memory.

translation.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// Pseudocode: Hardware segment translation logic
 
physical_address_t translate(segment_number_t seg, offset_t offset, 
                             access_type_t access, privilege_t cpl) {
    
    // Step 1: Get segment table base (from STBR register)
    segment_table_entry_t* table = get_segment_table_base();
    
    // Step 2: Index into table
    segment_table_entry_t* entry = &table[seg];
    
    // Step 3: Check present
    if (!entry->present) {
        raise_fault(SEGMENT_NOT_PRESENT, seg);
        // OS handler may load segment and retry
    }
    
    // Step 4: Check privilege
    if (cpl > entry->dpl) {
        raise_fault(GENERAL_PROTECTION, "Privilege violation");
    }
    
    // Step 5: Check bounds
    if (!entry->expand_down) {
        // Normal segment: valid offsets are [0, limit]
        if (offset > entry->limit) {
            raise_fault(SEGMENT_FAULT, "Offset exceeds limit");
        }
    } else {
        // Expand-down segment (stack): valid offsets are [limit+1, max]
        if (offset <= entry->limit) {
            raise_fault(SEGMENT_FAULT, "Offset below stack limit");
        }
    }
    
    // Step 6: Check access type
    if (access == READ && !entry->readable) {
        raise_fault(PROTECTION_FAULT, "Read not permitted");
    }
    if (access == WRITE && !entry->writable) {
        raise_fault(PROTECTION_FAULT, "Write not permitted");
    }
    if (access == EXECUTE && !entry->executable) {
        raise_fault(PROTECTION_FAULT, "Execute not permitted");
    }
    
    // Step 7: Compute physical address
    entry->accessed = 1;  // Mark as accessed
    return entry->base + offset;
}

Translation Performance:

This seven-step process happens for every memory reference. At billions of references per second, even small inefficiencies compound. Hardware optimizations are essential:

Segment Descriptor Caches: Segment registers cache the full descriptor, not just the segment number. Loading a segment register is slow; using it thereafter is fast.
Parallel Checking: Bounds check, privilege check, and type check can happen simultaneously (combinational logic).
Speculative Translation: While previous instruction completes, the next instruction's translation begins speculatively.
Base Addition in Address Generation Unit (AGU): The base + offset addition happens in dedicated hardware designed for this purpose.

Every Fault Has a Handler

Segment Table Registers

The hardware needs to know where the segment table is located and, for efficiency, caches frequently used segment descriptors. This is accomplished through special CPU registers.

Segment Table Base Register (STBR):

Process A running: STBR = 0x100000 (A's segment table)
Context switch to Process B: STBR = 0x200000 (B's segment table)

Segment Table Length Register (STLR):

The Segment Table Length Register holds the number of entries in the segment table. This prevents accessing invalid segment numbers:

If (segment_number >= STLR) {
    raise_fault(INVALID_SEGMENT);
}

Together, STBR and STLR define the current segment table. The OS updates both during context switches.

Key Registers for Segmentation
Register	Purpose	Set By	Used By
STBR	Physical address of segment table	OS (context switch)	MMU (translation)
STLR	Number of entries in segment table	OS (context switch)	MMU (bounds check)
CS (Code Segment)	Cached code segment descriptor	CPU (on segment load)	CPU (instruction fetch)
DS (Data Segment)	Cached data segment descriptor	CPU (on segment load)	CPU (data access)
SS (Stack Segment)	Cached stack segment descriptor	CPU (on segment load)	CPU (push/pop/call/ret)
ES, FS, GS	Extra cached segment descriptors	CPU (on segment load)	CPU (explicit override)

Segment Registers as Descriptor Caches:

In x86 architecture, segment registers serve a dual purpose:

Visible Part: The 16-bit segment selector that programs can read/write
Hidden Part: The full segment descriptor (base, limit, attributes) cached from the segment table

When a program loads a segment register:

mov ax, 0x23    ; Segment selector 0x23
mov ds, ax      ; Load into DS

The CPU:

Uses selector 0x23 to index into the descriptor table
Loads the full descriptor (base, limit, access rights) into DS's hidden part
Subsequent DS-relative accesses use the cached descriptor—no table lookup needed

This is critical for performance: Without caching, every memory access would require a memory access to the segment table—doubling memory traffic.

segment_register.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// Conceptual structure of an x86 segment register
 
typedef struct segment_register {
    // Visible part (accessible to software)
    uint16_t selector;  // Segment selector value
    
    // Hidden/cached part (loaded from descriptor table)
    struct {
        uint32_t base;      // Cached base address
        uint32_t limit;     // Cached limit
        uint16_t attributes;  // Cached access rights
    } cached_descriptor;
    
} segment_register_t;
 
// When you execute: MOV DS, selector
// The CPU does:
void load_segment_register(segment_register_t* reg, uint16_t selector) {
    reg->selector = selector;
    
    // Look up descriptor in table
    descriptor_t* desc = get_descriptor(selector);
    
    // Cache the full descriptor
    reg->cached_descriptor.base = desc->base;
    reg->cached_descriptor.limit = desc->limit;
    reg->cached_descriptor.attributes = desc->attributes;
    
    // Now every DS:offset access uses cached.base + offset
    // No table lookup needed until DS is loaded again
}
 
// Result: One slow table lookup, then many fast cached accesses

Context Switch Must Save Segment Descriptors

Protection Through the Segment Table

The segment table is the enforcement mechanism for all segmentation-based protection. Every protection policy is encoded in segment descriptors and checked by hardware on every access.

Protection Checks Performed:

Hardware Protection Checks

•Bounds Checking — Offset must be within [0, limit] for normal segments or [limit+1, max] for expand-down. Prevents buffer overflows from accessing other segments.
•Read Permission — Descriptor's readable bit must be set for data reads. Some systems allow execute-only code (not readable—prevents code disclosure).
•Write Permission — Descriptor's writable bit must be set. Code segments are never writable (at runtime). Read-only data segments prevent modification.
•Execute Permission — Descriptor's executable bit must be set for instruction fetches. Data segments should never be executable (prevents code injection).
•Privilege Level — Current Privilege Level (CPL) must be numerically ≤ Descriptor Privilege Level (DPL). Ring 3 cannot access Ring 0 segments.
•Type Checking — Can't load a code segment descriptor into DS (data segment register). Can't execute from a non-code descriptor.

Protection Example Scenarios:

Protection Violations and Results
Attempt	Descriptor State	Result	Fault Type
Read offset 0x2000	Limit = 0x1000	Blocked	#GP (bounds violation)
Write to code segment	Writable = 0	Blocked	#GP (write protection)
Execute data segment	Executable = 0	Blocked	#GP (execute protection)
User access kernel seg	DPL = 0, CPL = 3	Blocked	#GP (privilege violation)
Access swapped segment	Present = 0	Blocked	#NP (not present)
Valid access within bounds	All checks pass	Permitted	N/A

Privilege Levels (Protection Rings):

The x86 architecture implements four protection rings (0-3):

Ring 0 (Kernel): Full hardware access, all segments
Ring 1 (Services): Device drivers (rarely used in practice)
Ring 2 (Services): Less privileged drivers (rarely used)
Ring 3 (User): Applications, limited to user segments

Each segment descriptor has a DPL (Descriptor Privilege Level). A process running at CPL (Current Privilege Level) n can only access segments with DPL ≥ n.

User process (Ring 3):

Can access segments with DPL = 3
Cannot access segments with DPL = 0, 1, or 2
Cannot modify segment registers to bypass this (the checks apply to the selector, which is validated)

Kernel (Ring 0):

Can access all segments regardless of DPL
Can modify segment tables (user processes cannot)
Runs when handling system calls, interrupts, exceptions

This hardware-enforced privilege separation is fundamental to OS security.

Hardware Enforcement is Unforgeable

Sharing Through Segment Tables

How Sharing Works:

Converting Mermaid diagram...

In the diagram above:

Process 1's segment 3 and Process 2's segment 3 both point to physical 0x20000
That region contains a shared library
One copy in physical memory serves both processes
All other segments are private (different base addresses)

Requirements for Sharing:

Same Base Address: Both descriptors must point to the same physical memory
Compatible Limits: The limits should match (or the smaller limit applies for safety)
Appropriate Permissions: Shared code is typically R+X (read, execute). Shared data requires careful coordination if writable.

Sharing Scenarios:

What's Shared	Permissions	Notes
Code segment (same program)	R+X	Multiple instances of the same program
Shared library code	R+X	libc shared by hundreds of processes
Read-only data	R	Constants, lookup tables, fonts
Writable shared memory	R+W	IPC, requires synchronization

Reference Counting:

The OS tracks how many processes reference each shared segment. When a process exits:

Decrement reference count for each segment
If count reaches zero, the segment can be deallocated
If count > 0, the segment remains for other sharers

shared_segment.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// OS implementation of segment sharing
 
typedef struct shared_segment_info {
    physical_address_t base;  // Physical memory location
    size_t size;              // Segment size
    int ref_count;            // Number of processes sharing
    int permissions;          // Protection attributes
} shared_segment_t;
 
// When Process P wants to share segment S:
void map_shared_segment(process_t* p, int seg_num, shared_segment_t* shared) {
    // Point process's segment table entry to shared memory
    p->segment_table[seg_num].base = shared->base;
    p->segment_table[seg_num].limit = shared->size;
    p->segment_table[seg_num].permissions = shared->permissions;
    p->segment_table[seg_num].present = 1;
    
    // Increment reference count
    shared->ref_count++;
    
    // Now p's segment_num accesses the same memory as all other sharers
}
 
// When Process P exits or unmaps a shared segment:
void unmap_shared_segment(process_t* p, int seg_num, shared_segment_t* shared) {
    // Invalidate entry
    p->segment_table[seg_num].present = 0;
    
    // Decrement reference count
    shared->ref_count--;
    
    // Free physical memory if no more sharers
    if (shared->ref_count == 0) {
        free_physical_memory(shared->base, shared->size);
        free(shared);
    }
}

Different Segment Numbers Can Share

x86 Segment Descriptors: Real Implementation

x86 Segment Descriptor Layout (8 bytes):

x86_descriptor.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// Intel x86 Segment Descriptor (64 bits / 8 bytes)
// This is the exact hardware layout
 
/* Bit layout:
 * 
 * Bytes 0-1: Limit (bits 0-15)
 * Bytes 2-3: Base (bits 0-15)
 * Byte 4:    Base (bits 16-23)
 * Byte 5:    Access byte
 *            [7]    Present (P)
 *            [6:5]  Descriptor Privilege Level (DPL)
 *            [4]    Descriptor type (S): 1=code/data, 0=system
 *            [3:0]  Type (depends on S bit)
 * Byte 6:    Flags + Limit
 *            [7]    Granularity (G): 0=byte, 1=4KB page
 *            [6]    Default operation size (D/B)
 *            [5]    64-bit code segment (L)
 *            [4]    Available for OS use (AVL)
 *            [3:0]  Limit (bits 16-19)
 * Byte 7:    Base (bits 24-31)
 */
 
typedef struct __attribute__((packed)) {
    uint16_t limit_low;       // Limit bits 0-15
    uint16_t base_low;        // Base bits 0-15
    uint8_t  base_mid;        // Base bits 16-23
    uint8_t  access;          // Access byte (type, DPL, present)
    uint8_t  flags_limit_hi;  // Flags + Limit bits 16-19
    uint8_t  base_high;       // Base bits 24-31
} segment_descriptor_t;
 
// Example: Create a code segment descriptor
// Base = 0x00000000, Limit = 0xFFFFF (4GB in page granularity)
// Ring 3 (user), Present, Code segment, Readable, Executable
 
segment_descriptor_t user_code_segment = {
    .limit_low     = 0xFFFF,      // Limit bits 0-15
    .base_low      = 0x0000,      // Base bits 0-15
    .base_mid      = 0x00,        // Base bits 16-23
    .access        = 0b11111010,  // P=1, DPL=11(3), S=1, Type=1010(code,readable)
    .flags_limit_hi= 0b11001111,  // G=1, D=1, L=0, AVL=0, Limit[19:16]=F
    .base_high     = 0x00         // Base bits 24-31
};
 
// This descriptor creates a 4GB code segment starting at address 0
// Accessible from ring 3, readable and executable

The Global Descriptor Table (GDT):

In x86, segment descriptors are stored in the Global Descriptor Table (GDT)—the system-wide segment table. The GDT register (GDTR) points to this table:

GDTR = { base = physical address of GDT, limit = size of GDT }

Segment Selectors:

x86 segment selectors are 16-bit values with three fields:

15            3  2  1 0
┌──────────────┬───┬───┐
│   Index      │TI │RPL│
└──────────────┴───┴───┘

Index (13 bits): Entry number in descriptor table
TI (1 bit): Table Indicator (0=GDT, 1=LDT)
RPL (2 bits): Requested Privilege Level

Example: Selector 0x1B = 0b00011011

Index = 3 (use descriptor at GDT[3])
TI = 0 (use GDT, not LDT)
RPL = 3 (request at privilege level 3)

Flat Model on x86:

Modern operating systems use a "flat" model where all segment bases are 0 and limits cover the entire address space. This effectively disables segment translation while retaining privilege checking:

Code segment: Base=0, Limit=4GB, Ring 0 or 3
Data segment: Base=0, Limit=4GB, Ring 0 or 3

// With base=0, segment:offset = offset (flat addressing)

This is why modern x86-64 essentially ignores segmentation for addressing while still using it for privilege levels.

Why x86 Descriptors Are So Complex

Segment Tables and Paging Together

Two-Stage Translation:

Logical Address: (Segment, Offset)
         │
         v
    ┌─────────────┐
    │ Segment     │
    │ Translation │
    └─────────────┘
         │
         v
Linear Address (virtual address)
         │
         v
    ┌─────────────┐
    │ Page        │
    │ Translation │
    └─────────────┘
         │
         v
Physical Address

Translation Pipeline

•Logical Address → Segment table lookup → Linear Address: base + offset = linear address. Segment protection checks apply here.
•Linear Address → Page table lookup → Physical Address: Page directory → Page table → Frame number + offset. Page protection checks apply here.
•Physical Address → Memory: The actual RAM access finally occurs.

Why Both?

Segmentation provides:

Logical organization (code vs. data vs. stack)
Semantic protection (execute code, read/write data)
Privilege levels (kernel vs. user)
Variable-size logical units

Paging provides:

Fixed-size physical allocation (no external fragmentation)
Demand paging (load pages on demand)
Swapping (page out to disk)
Fine-grained memory management

Together they provide:

Logical segments with semantic meaning
Paged within each segment for efficient physical management
Two layers of protection (segment AND page permissions)
The programmer's view (segments) with the OS's efficiency (pages)

In Practice Today:

On x86-64, segment bases are forced to 0 in 64-bit mode, making the linear address equal to the offset. Segmentation is effectively disabled for addressing. However:

Privilege levels still enforce Ring 0 vs Ring 3
FS and GS registers are still usable with non-zero bases (for TLS)
Paging handles all memory management

So segmentation persists in vestigial form, while paging does the heavy lifting.

Segmented Paging: The Full Picture

Summary: The Segment Table

This page has provided a comprehensive exploration of the segment table—the data structure that implements all aspects of memory segmentation. Let's consolidate the key insights:

Key Takeaways

•The segment table is per-process, mapping segment numbers to physical locations with size limits and permissions.
•Segment table entries contain base address, limit, present bit, protection bits (R/W/X), and privilege level (DPL).
•Address translation is direct: physical_address = base + offset, with bounds and protection checks on every access.
•Segment registers cache descriptors for performance—loading the segment register fetches the descriptor; subsequent accesses use the cache.
•Protection is hardware-enforced via bounds checking, permission verification, and privilege level comparison—unforgeable from user space.
•Sharing is natural: multiple processes' segment table entries point to the same physical memory, with reference counting for lifecycle management.
•x86 implements segmentation with the GDT/LDT, segment selectors, and 8-byte descriptors—though modern systems use a flat model.
•Segmentation and paging combine: segment translation produces a linear address, paging produces the physical address, together providing logical organization with physical efficiency.

Module Complete:

With the segment table, we've completed our exploration of Segmentation Concepts. You now understand:

What segments are (logical, variable-size memory units)
The main segment types (code, data, stack)
Why variable sizes matter (matching program structure, but causing fragmentation)
The programmer's perspective (meaningful addresses, natural protection)
The implementation (segment tables with base, limit, permissions)

Module Complete