Paging: Smaller Tables

How Linear Tables Balloon

Slicing a 32-bit space into 4 KiB pages yields roughly a million virtual pages. Four-byte entries then force a 4 MiB contiguous table per process. A hundred live processes therefore consume hundreds of megabytes just for mappings, most of which stay invalid. Compression techniques become mandatory.

The Simple Trade-off of Bigger Pages

Switching to 16 KiB pages immediately cuts the number of virtual pages by four, shrinking the linear table to 1 MiB. The price is internal fragmentation: even a few kilobytes of demand still occupies an entire large page, trapping unused bytes inside the allocation unit. Hence general-purpose systems stay with 4 KiB or 8 KiB pages.

A Hybrid of Paging and Segmentation

Instead of one giant array covering the whole space, a compact page table is kept for code, heap and stack separately. The old base register now holds the physical address of that segment’s table; the limit register stores how many valid entries exist. High-order address bits select the correct table, so unused holes consume zero page-table memory. All three base/limit pairs must be swapped on every context switch.

Pitfalls

• Blindly adopting huge pages to shrink tables can make internal fragmentation larger than the memory saved.
• In the hybrid design, omitting the VPN-versus-limit check lets a process index past its own table into another process’s mappings.

Minimum C11 · complete program · Download .c

#include <stdio.h>
#include <stdint.h>

int main(void) {
    const uint64_t vas_bits = 32;
    const uint64_t page_bits_small = 12;
    const uint64_t pte_bytes = 4;
    uint64_t num_pages_small = 1ULL << (vas_bits - page_bits_small);
    uint64_t pt_size_small = num_pages_small * pte_bytes;
    printf("32-bit address space, 4 KiB pages:\n");
    printf("  Virtual pages: %llu\n", (unsigned long long)num_pages_small);
    printf("  Linear page-table size: %llu bytes (%.1f MiB)\n",
           (unsigned long long)pt_size_small, pt_size_small / (1024.0 * 1024));
    const uint64_t page_bits_large = 14;
    uint64_t num_pages_large = 1ULL << (vas_bits - page_bits_large);
    uint64_t pt_size_large = num_pages_large * pte_bytes;
    printf("\nSame VAS, 16 KiB pages:\n");
    printf("  Virtual pages: %llu\n", (unsigned long long)num_pages_large);
    printf("  Linear page-table size: %llu bytes (%.1f MiB)\n",
           (unsigned long long)pt_size_large, pt_size_large / (1024.0 * 1024));
    printf("\nLarger pages shrink the table by the same factor but waste space inside pages.\n");
    return 0;
}

Compile locally

gcc -std=c11 -Wall -Wextra -Wpedantic -Werror ostep-20-advanced-page-tables.c -o example && ./example

Expected result

32-bit address space, 4 KiB pages:
  Virtual pages: 1048576
  Linear page-table size: 4194304 bytes (4.0 MiB)

Same VAS, 16 KiB pages:
  Virtual pages: 262144
  Linear page-table size: 1048576 bytes (1.0 MiB)

Larger pages shrink the table by the same factor but waste space inside pages.

CHECK YOUR UNDERSTANDING

Close the answer. Explain it.

How large is a linear page table for a 32-bit space with 4 KiB pages and 4-byte PTEs? What size after switching to 16 KiB pages? What new problem appears?

Check the sources

• OSTEP chapter PDF

Drafts and official chapters change. The version mark is only the example’s minimum.