Hash Based And Inverted Page Tables - Learning Module

Loading content...

0/227

Collision Handling in Hashed Page Tables

The Inevitable Collision Problem

Hash functions, by their very nature, must map a larger domain to a smaller range. When hashing 52-bit virtual page numbers into a hash table with thousands or millions of buckets, collisions are mathematically inevitable. Two or more distinct VPNs will hash to the same bucket index.

The Pigeonhole Principle guarantees this: if we have N possible VPNs and M buckets where N > M, at least one bucket must eventually receive more than one entry. For 64-bit systems mapping millions of pages into hash tables with tens of thousands of buckets, collisions are not edge cases—they are expected behavior.

Collision handling is thus not an optional feature but a fundamental component of hashed page table design. The strategy chosen for resolving collisions profoundly impacts lookup performance, memory efficiency, insertion/deletion complexity, and even system security. Understanding these trade-offs deeply is essential for anyone designing or optimizing memory management systems.

What You Will Learn

By the end of this page, you will understand the mathematical foundations of hash collisions, master chaining and open addressing strategies, analyze their performance characteristics, and appreciate why chaining dominates in page table implementations despite open addressing's theoretical advantages in some scenarios.

The Mathematics of Collisions

Understanding collision probability is essential for designing hash tables with predictable performance. The mathematics reveals surprising results about when and how frequently collisions occur.

The Birthday Problem Connection:

Collision probability in hash tables is analogous to the famous Birthday Problem: How many people must be in a room before there's a 50% chance two share a birthday?

The surprising answer—23 people for a 50% probability with 365 days—illustrates that collisions occur much sooner than intuition suggests.

For hash tables:

P(collision after k insertions) ≈ 1 - e^(-k²/2m)

Where:
  k = number of inserted entries
  m = number of buckets

Collision Probability Examples:

Collision Probability Analysis
Buckets (m)	Entries (k)	P(≥1 collision)	Expected Collisions
1,000	10	4.4%	0.045
1,000	40	55.3%	0.8
1,000	100	99.3%	4.9
10,000	100	39.3%	0.5
10,000	1,000	99.99%	49.5
100,000	10,000	99.99%	495

The Load Factor Formula:

The load factor α = k/m (entries / buckets) determines collision behavior:

Expected entries per bucket (under uniform hashing) = α

Probability bucket has exactly j entries:
P(bucket has j entries) = (α^j × e^(-α)) / j!   (Poisson approximation)

For α = 0.5:
  P(0 entries) = 60.65%  (empty buckets)
  P(1 entry)   = 30.33%  (no collision)
  P(2 entries) = 7.58%   (one collision)
  P(3 entries) = 1.26%   (two collisions)
  P(≥4)        = 0.18%   (multiple collisions)

This distribution shows that even with load factor 0.5, about 9% of buckets experience collisions. As load factor increases, collision severity grows rapidly.

The 50% Rule in Practice

Most well-tuned hash tables maintain load factors between 0.5 and 0.75. Below 0.5, memory is wasted on empty buckets. Above 0.75, collision chains lengthen significantly. This range represents the sweet spot balancing memory efficiency against lookup performance.

Expected Search Length:

The average number of entries examined during a lookup depends on whether the search is successful (entry exists) or unsuccessful (entry not in table):

For Chaining:

Successful search:   E[probes] ≈ 1 + α/2
Unsuccessful search: E[probes] ≈ α

With α = 0.75:
  Successful:   1.375 probes average
  Unsuccessful: 0.75 probes average

For Open Addressing (Linear Probing):

Successful search:   E[probes] ≈ ½(1 + 1/(1-α))
Unsuccessful search: E[probes] ≈ ½(1 + 1/(1-α)²)

With α = 0.75:
  Successful:   2.5 probes average
  Unsuccessful: 8.5 probes average

These formulas reveal why chaining typically outperforms open addressing at higher load factors—the quadratic growth of unsuccessful search in open addressing becomes problematic.

Chaining: The Primary Strategy for Page Tables

Separate chaining is the dominant collision resolution strategy in hashed page tables. When multiple VPNs hash to the same bucket, their entries are linked together in a list (chain) emanating from that bucket.

Structure:

Bucket Array:         Collision Chains:
┌─────────┐
│ Bucket 0 │ ──→ NULL (empty)
├─────────┤
│ Bucket 1 │ ──→ [VPN:A5, PFN:42] ──→ [VPN:C1, PFN:107] ──→ NULL
├─────────┤
│ Bucket 2 │ ──→ NULL (empty)
├─────────┤
│ Bucket 3 │ ──→ [VPN:F7, PFN:88] ──→ NULL
├─────────┤
│ Bucket 4 │ ──→ [VPN:04, PFN:15] ──→ [VPN:24, PFN:203] ──→ [VPN:B4, PFN:91] ──→ NULL
└─────────┘

Each bucket contains a pointer to the first entry in its chain. Each entry contains a pointer to the next entry (or NULL if it's the last).

Converting Mermaid diagram...

Chaining Operations:

Lookup:

Compute hash: bucket = hash(vpn) % table_size
Traverse chain from buckets[bucket]
Compare each entry's VPN with target VPN
Return entry if match found, or signal page fault if chain exhausted

Insert:

Compute hash: bucket = hash(vpn) % table_size
Check if VPN already exists in chain (duplicates typically disallowed)
Allocate new entry, link it into chain (typically at head for O(1) insert)

Delete:

Compute hash: bucket = hash(vpn) % table_size
Traverse chain to find entry with matching VPN
Update predecessor's next pointer to skip deleted entry
Free deleted entry's memory

chaining_implementation.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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
// Complete chaining implementation for hashed page tables
 
typedef struct HPTEntry {
    uint64_t vpn;                    // Virtual page number
    uint64_t pfn;                    // Physical frame number
    uint32_t control;                // Control/protection bits
    struct HPTEntry* next;           // Chain pointer
} HPTEntry;
 
typedef struct {
    HPTEntry** buckets;              // Array of chain heads
    size_t num_buckets;              // Table size
    size_t entry_count;              // Current number of entries
    uint64_t hash_seed;              // Hash randomization seed
} HashedPageTable;
 
// Lookup with full chain traversal
HPTEntry* hpt_lookup_chained(HashedPageTable* table, uint64_t vpn) {
    // Compute bucket index
    uint64_t bucket = hash_vpn(vpn, table->hash_seed) & (table->num_buckets - 1);
    
    // Traverse the chain
    HPTEntry* entry = table->buckets[bucket];
    while (entry != NULL) {
        if (entry->vpn == vpn) {
            return entry;  // Found!
        }
        entry = entry->next;
    }
    
    return NULL;  // Not found - page fault
}
 
// Insert at chain head (O(1) insertion)
bool hpt_insert_chained(HashedPageTable* table, uint64_t vpn, 
                        uint64_t pfn, uint32_t control) {
    // Check for duplicates (optional, depends on policy)
    if (hpt_lookup_chained(table, vpn) != NULL) {
        return false;  // Already exists
    }
    
    // Allocate new entry
    HPTEntry* new_entry = (HPTEntry*)malloc(sizeof(HPTEntry));
    if (new_entry == NULL) return false;
    
    new_entry->vpn = vpn;
    new_entry->pfn = pfn;
    new_entry->control = control;
    
    // Compute bucket and insert at head
    uint64_t bucket = hash_vpn(vpn, table->hash_seed) & (table->num_buckets - 1);
    new_entry->next = table->buckets[bucket];
    table->buckets[bucket] = new_entry;
    
    table->entry_count++;
    
    // Check if resize needed
    if ((float)table->entry_count / table->num_buckets > 0.75) {
        hpt_resize(table, table->num_buckets * 2);
    }
    
    return true;
}
 
// Delete entry from chain
bool hpt_delete_chained(HashedPageTable* table, uint64_t vpn) {
    uint64_t bucket = hash_vpn(vpn, table->hash_seed) & (table->num_buckets - 1);
    
    HPTEntry* entry = table->buckets[bucket];
    HPTEntry* prev = NULL;
    
    while (entry != NULL) {
        if (entry->vpn == vpn) {
            // Found - remove from chain
            if (prev == NULL) {
                // Removing head of chain
                table->buckets[bucket] = entry->next;
            } else {
                // Removing from middle/end
                prev->next = entry->next;
            }
            
            free(entry);
            table->entry_count--;
            return true;
        }
        
        prev = entry;
        entry = entry->next;
    }
    
    return false;  // Not found
}

Why Chaining Dominates for Page Tables:

Unbounded Entries per Bucket: Chaining can handle any number of collisions gracefully—chains simply grow longer. This is important because page tables can experience burst insertions when processes load large programs.
Simple Memory Management: Each entry is independently allocated and freed. Entry lifetime is independent of other entries.
Stable Pointers: Once inserted, an entry's address doesn't change. This allows external references to entries (e.g., from TLB hardware that caches page table entries).
Efficient Deletion: Removing an entry only requires updating one pointer. No tombstones or reorganization needed.
Graceful Degradation: Even if collisions increase, the table remains functional (just slower). There's no catastrophic failure mode.
Concurrent Access Friendly: With appropriate locking (per-bucket locks, RCU), chains allow fine-grained concurrent access.

Open Addressing Alternatives

Open addressing stores all entries directly in the bucket array itself. When a collision occurs, the algorithm probes alternative buckets according to a probing sequence until an empty slot is found.

Core Concept:

Hash to bucket i
If bucket i is occupied:
    Probe bucket (i+probe(1)) mod m
    If that's occupied:
        Probe bucket (i+probe(2)) mod m
        ...
    Until empty bucket found or table full

No Chain Pointers: Open addressing eliminates the next-pointer overhead in each entry. All storage is contiguous in the bucket array.

Probing Strategies:

1. Linear Probing:

probe(k) = k
Sequence: i, i+1, i+2, i+3, ...

Pros: Excellent cache locality (sequential memory access) Cons: Primary clustering—long runs of occupied slots form

2. Quadratic Probing:

probe(k) = k²  (or k² + k)/2
Sequence: i, i+1, i+4, i+9, i+16, ...

Pros: Reduces primary clustering Cons: Secondary clustering, may not probe all buckets

3. Double Hashing:

probe(k) = k × hash₂(key)
Sequence: i, i+h₂, i+2h₂, i+3h₂, ...

Pros: Best distribution, minimal clustering Cons: Requires second hash function, more computation

Probing Strategy Comparison
Strategy	Clustering	Cache Behavior	Computation	Coverage
Linear	Severe (primary)	Excellent	Minimal	Full
Quadratic	Moderate (secondary)	Good	Low	Partial*
Double Hash	Minimal	Poor	Higher	Full

*Quadratic probing with table size m guarantees full coverage only if m is prime and load factor ≤ 0.5

Open Addressing Implementation:

open_addressing.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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
// Open addressing with linear probing
 
typedef struct {
    uint64_t vpn;          // Virtual page number (0 = empty)
    uint64_t pfn;          // Physical frame number
    uint32_t control;      // Control bits
    uint8_t state;         // EMPTY, OCCUPIED, DELETED
} OAEntry;
 
#define STATE_EMPTY    0
#define STATE_OCCUPIED 1
#define STATE_DELETED  2   // Tombstone for lazy deletion
 
typedef struct {
    OAEntry* entries;      // Contiguous array of entries
    size_t num_slots;      // Total slots
    size_t entry_count;    // Occupied slots (not counting deleted)
} OpenAddressTable;
 
// Lookup with linear probing
OAEntry* oa_lookup(OpenAddressTable* table, uint64_t vpn) {
    uint64_t slot = hash_vpn(vpn) & (table->num_slots - 1);
    uint64_t start = slot;
    
    do {
        OAEntry* entry = &table->entries[slot];
        
        if (entry->state == STATE_EMPTY) {
            // Empty slot - entry doesn't exist
            return NULL;
        }
        
        if (entry->state == STATE_OCCUPIED && entry->vpn == vpn) {
            // Found it!
            return entry;
        }
        
        // Continue probing (skip DELETED tombstones)
        slot = (slot + 1) & (table->num_slots - 1);
        
    } while (slot != start);  // Full table traversed
    
    return NULL;  // Not found
}
 
// Insert with linear probing
bool oa_insert(OpenAddressTable* table, uint64_t vpn, 
               uint64_t pfn, uint32_t control) {
    // Check load factor - must resize before table is full
    if ((float)table->entry_count / table->num_slots > 0.7) {
        if (!oa_resize(table, table->num_slots * 2)) {
            return false;  // Resize failed
        }
    }
    
    uint64_t slot = hash_vpn(vpn) & (table->num_slots - 1);
    uint64_t first_deleted = UINT64_MAX;  // Track first tombstone
    
    while (true) {
        OAEntry* entry = &table->entries[slot];
        
        if (entry->state == STATE_EMPTY) {
            // Use first deleted slot if we found one, else use empty
            if (first_deleted != UINT64_MAX) {
                slot = first_deleted;
                entry = &table->entries[slot];
            }
            
            entry->vpn = vpn;
            entry->pfn = pfn;
            entry->control = control;
            entry->state = STATE_OCCUPIED;
            table->entry_count++;
            return true;
        }
        
        if (entry->state == STATE_DELETED && first_deleted == UINT64_MAX) {
            first_deleted = slot;  // Remember first tombstone
        }
        
        if (entry->state == STATE_OCCUPIED && entry->vpn == vpn) {
            // Already exists - update
            entry->pfn = pfn;
            entry->control = control;
            return true;
        }
        
        slot = (slot + 1) & (table->num_slots - 1);
    }
}
 
// Delete with tombstone (lazy deletion)
bool oa_delete(OpenAddressTable* table, uint64_t vpn) {
    OAEntry* entry = oa_lookup(table, vpn);
    if (entry == NULL) return false;
    
    // Cannot simply mark as empty - would break probe chains
    // Use tombstone instead
    entry->state = STATE_DELETED;
    table->entry_count--;
    
    return true;
}

The Tombstone Problem

Deleted entries in open addressing cannot simply be marked empty—doing so would break probe chains for entries inserted after the deleted one. Tombstones (DELETED state) must be used, but they accumulate over time, degrading lookup performance. Periodic rehashing is needed to clean tombstones, adding complexity.

Chaining vs Open Addressing: Deep Trade-off Analysis

Choosing between chaining and open addressing involves balancing multiple competing factors. For page tables specifically, the decision is influenced by unique constraints of address translation workloads.

Memory Efficiency:

Chaining Memory:

Bucket array: m × 8 bytes (pointers)
Per entry: sizeof(entry) + 8 bytes (next ptr)

For m=16K buckets, n=10K entries:
  Bucket array: 128 KB
  Entry overhead: 8 bytes × 10K = 80 KB
  Entry data: 24 bytes × 10K = 240 KB
  Total: ~448 KB

Open Addressing Memory:

Slots: m × sizeof(entry) bytes
No separate pointers needed
Must keep load factor < 0.7

For n=10K entries at α=0.7:
  Slots needed: 10K / 0.7 ≈ 14.3K
  Use 16K slots (power of 2)
  Each slot: 24 bytes
  Total: 384 KB

Open addressing wins slightly on memory, but the difference is modest. The chain pointer overhead in chaining is offset by open addressing's need for extra empty slots.

Cache Performance:

Open Addressing (Linear Probing) Advantages:

Sequential memory access during probing
Prefetcher-friendly probe patterns
Entire probe sequence may be in same cache line
Better for tight loops with many lookups

Chaining Advantages:

Bucket array is compact and cacheable
Short chains (1-2 entries) common with good load factor
No wasted cache space for empty slots
Better when chains are short and entries are large

Worst-Case Behavior:

Worst-Case Analysis
Scenario	Chaining	Open Addressing
All entries hash to same bucket	O(n) chain traversal	O(n) probe sequence
Table nearly full	Chains grow, but still works	Probe sequences explode; may fail to insert
High deletion rate	Clean deallocation	Tombstone accumulation
Burst insertions	Chains grow gracefully	Must resize proactively
Adversarial input	Single long chain	Pathological probe sequences

Why Page Tables Use Chaining:

For address translation specifically, chaining wins decisively for several reasons:

Hardware TLB Integration: Modern TLBs cache pointers to page table entries. With chaining, an entry's address never changes after insertion. Open addressing may relocate entries during resizing, invalidating cached pointers.
Concurrent Access: Page tables are accessed by multiple CPUs simultaneously. Chaining allows per-bucket locking for fine-grained concurrency. Open addressing requires more complex synchronization because probe sequences span multiple buckets.
Deletion Patterns: Page mappings are frequently created and destroyed (process creation/exit, mmap/munmap). Chaining handles deletions cleanly without tombstone accumulation.
Predictable Latency: Real-time systems prefer bounded worst-case lookup times. While both can degrade to O(n), chaining's chain length is more predictable than open addressing's probe sequence length at high load.
Sparse Table Support: Page tables for large sparse address spaces have many unmapped regions. Chaining wastes no space for unmapped pages—empty buckets contain only NULL pointers.

Industry Practice

All major operating systems using hashed page tables (IA-64 Linux, PowerPC systems, research OSes) use chaining. Open addressing appears in user-space hash tables (Python dicts pre-3.6, some database indices) where the simpler memory model and cache advantages outweigh concurrent access concerns.

Advanced Collision Mitigation Techniques

Beyond basic chaining and open addressing, several advanced techniques can further reduce collision impact in hashed page tables.

1. Multiple Hash Functions (Cuckoo Hashing):

Cuckoo hashing uses two (or more) hash functions. Each entry can be stored in one of k possible locations:

Locations for entry E:
  - hash₁(E.vpn) mod m
  - hash₂(E.vpn) mod m
  (optionally more with k-ary cuckoo)

Insert: Try each location in order. If all occupied, "kick out" an existing entry and relocate it to its alternative location. Cascade until stable or cycle detected.

Lookup: Check all k locations in parallel (if hardware supports) or sequentially.

Benefits:

Worst-case O(1) lookup (only k locations to check)
High load factors (up to 0.9) achievable
Cache-friendly when k is small

cuckoo_hashing.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
51
52
53
54
55
56
57
58
59
60
61
62
// Simplified cuckoo hashing for page table entries
 
#define NUM_HASH_FUNCTIONS 2
#define MAX_KICKS 500  // Limit relocations before resize
 
typedef struct {
    CuckooEntry* tables[NUM_HASH_FUNCTIONS];  // Multiple tables
    size_t table_size;
    uint64_t seeds[NUM_HASH_FUNCTIONS];
} CuckooHashTable;
 
// Compute slot in table i for vpn
static inline uint64_t cuckoo_slot(CuckooHashTable* cht, 
                                    uint64_t vpn, int table_idx) {
    return hash_vpn(vpn, cht->seeds[table_idx]) & (cht->table_size - 1);
}
 
// Lookup: O(1) worst case - check exactly 2 locations
CuckooEntry* cuckoo_lookup(CuckooHashTable* cht, uint64_t vpn) {
    for (int i = 0; i < NUM_HASH_FUNCTIONS; i++) {
        uint64_t slot = cuckoo_slot(cht, vpn, i);
        CuckooEntry* entry = &cht->tables[i][slot];
        
        if (entry->valid && entry->vpn == vpn) {
            return entry;
        }
    }
    return NULL;  // Not found
}
 
// Insert with cuckoo displacement
bool cuckoo_insert(CuckooHashTable* cht, uint64_t vpn, uint64_t pfn) {
    // Check if already exists
    if (cuckoo_lookup(cht, vpn) != NULL) {
        return false;
    }
    
    CuckooEntry new_entry = {.vpn = vpn, .pfn = pfn, .valid = true};
    
    for (int kick = 0; kick < MAX_KICKS; kick++) {
        // Try to place in first available slot
        for (int i = 0; i < NUM_HASH_FUNCTIONS; i++) {
            uint64_t slot = cuckoo_slot(cht, new_entry.vpn, i);
            CuckooEntry* target = &cht->tables[i][slot];
            
            if (!target->valid) {
                // Empty slot - success!
                *target = new_entry;
                return true;
            }
        }
        
        // No empty slot - kick out entry from table 0
        uint64_t slot = cuckoo_slot(cht, new_entry.vpn, 0);
        CuckooEntry kicked = cht->tables[0][slot];
        cht->tables[0][slot] = new_entry;
        new_entry = kicked;
    }
    
    // Too many kicks - need to resize or use stash
    return cuckoo_resize_and_insert(cht, new_entry);
}

2. Hopscotch Hashing:

A hybrid approach combining open addressing's cache friendliness with chaining's resistance to clustering.

Concept:

Each bucket has a neighborhood (e.g., 32 adjacent buckets)
Entries must reside within their neighborhood
Bitmap in each bucket tracks which neighbors contain its entries
Lookup checks bitmap, only probing indicated positions

3. Robin Hood Hashing:

A fairness-based open addressing variant:

Concept:

Track probe distance for each entry (how far from ideal position)
During insert, if new entry has traveled farther than existing entry, swap them
"Steal from the rich, give to the poor" - equalizes probe distances

Benefits:

Expected maximum probe distance is O(log log n)
Much tighter variance than standard open addressing
Cache performance remains excellent

4. Bloom Filter Pre-screening:

Before searching the hash table, consult a Bloom filter:

if (!bloom_might_contain(vpn)) {
    return PAGE_FAULT;  // Definitely not in table
}
// Only now search hash table
return hpt_lookup(table, vpn);

Benefits:

Bloom filters are very fast (few cache-friendly memory accesses)
Eliminate most unsuccessful searches without touching hash table
Particularly valuable when page faults are common

Research vs Production

Cuckoo hashing and Robin Hood hashing see significant use in user-space hash tables and databases. However, kernel page tables typically stick to simple chaining due to implementation complexity concerns, debugging difficulty, and the already-low collision rates achieved with proper sizing and hash functions.

Security Considerations: Hash Flooding Attacks

Hash tables, including page tables, are vulnerable to algorithmic complexity attacks where an adversary crafts inputs that cause pathological collision behavior, degrading performance from O(1) to O(n).

The Attack Model:

Attacker runs code on the system (local process or network service)
Attacker discovers or guesses the hash function
Attacker generates VPN allocation requests that all hash to the same bucket
Page table degrades to a single long chain
Every subsequent translation becomes O(n), causing system-wide slowdown

Real-World Impact:

Hash flooding attacks have been demonstrated against:

Web servers (HTTP header hash tables) - CVE-2011-4885
Language runtimes (Python, Ruby, PHP dictionaries)
DNS resolvers (response caching)
Network stacks (connection hash tables)

Page tables are somewhat protected because VPN allocation is typically controlled by the OS, but shared hosting environments and user-controlled mmap could expose vulnerabilities.

Defense Mechanisms:

1. Hash Randomization:

Initialize hash function with per-table random seed:

table->seed = get_random_u64();  // From hardware RNG

uint64_t hash(uint64_t vpn, uint64_t seed) {
    return final_mix(vpn ^ seed);  // Seed makes hash unpredictable
}

Attacker cannot predict which VPNs will collide without knowing the seed.

2. SipHash:

Cryptographically strong hash function designed for hash tables:

128-bit key (seed)
Proven collision resistance
Reasonably fast (<10 cycles/byte on modern CPUs)
Used by Linux kernel, Python 3.4+, Rust

3. Chain Length Limits:

Enforce maximum chain length and trigger defensive action:

#define MAX_CHAIN_LENGTH 64

if (chain_length > MAX_CHAIN_LENGTH) {
    // Potential attack detected
    trigger_rehash_with_new_seed();
    log_security_warning("Excessive hash collisions");
}

4. Secondary Structures:

Convert long chains to balanced trees:

if (chain_length > TREE_THRESHOLD) {
    convert_chain_to_rb_tree(bucket);
    // Now worst-case is O(log n) instead of O(n)
}

Java 8 HashMap uses this approach.

secure_hashing.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
51
52
53
54
55
56
57
58
// Secure hashing with SipHash for page tables
 
#include <stdint.h>
 
// SipHash-2-4: Two rounds per message block, four finalization rounds
// Provides sufficient security with excellent performance
 
static inline uint64_t rotl64(uint64_t x, int b) {
    return (x << b) | (x >> (64 - b));
}
 
static inline void sipround(uint64_t* v0, uint64_t* v1, 
                            uint64_t* v2, uint64_t* v3) {
    *v0 += *v1; *v1 = rotl64(*v1, 13); *v1 ^= *v0;
    *v0 = rotl64(*v0, 32);
    *v2 += *v3; *v3 = rotl64(*v3, 16); *v3 ^= *v2;
    *v0 += *v3; *v3 = rotl64(*v3, 21); *v3 ^= *v0;
    *v2 += *v1; *v1 = rotl64(*v1, 17); *v1 ^= *v2;
    *v2 = rotl64(*v2, 32);
}
 
uint64_t siphash_vpn(uint64_t vpn, const uint64_t key[2]) {
    uint64_t v0 = key[0] ^ 0x736f6d6570736575ULL;
    uint64_t v1 = key[1] ^ 0x646f72616e646f6dULL;
    uint64_t v2 = key[0] ^ 0x6c7967656e657261ULL;
    uint64_t v3 = key[1] ^ 0x7465646279746573ULL;
    
    // Process 8-byte VPN block
    v3 ^= vpn;
    sipround(&v0, &v1, &v2, &v3);
    sipround(&v0, &v1, &v2, &v3);
    v0 ^= vpn;
    
    // Finalization
    v2 ^= 0xff;
    for (int i = 0; i < 4; i++) {
        sipround(&v0, &v1, &v2, &v3);
    }
    
    return v0 ^ v1 ^ v2 ^ v3;
}
 
// Usage in page table
typedef struct SecureHashedPageTable {
    HPTEntry** buckets;
    size_t num_buckets;
    uint64_t sip_key[2];  // 128-bit random key
} SecureHashedPageTable;
 
void init_secure_hpt(SecureHashedPageTable* table) {
    // Get cryptographically random key
    get_random_bytes(table->sip_key, 16);
}
 
uint64_t secure_bucket(SecureHashedPageTable* table, uint64_t vpn) {
    uint64_t hash = siphash_vpn(vpn, table->sip_key);
    return hash & (table->num_buckets - 1);
}

Defense in Depth

No single defense is foolproof. Production systems should combine multiple protections: randomized hashing, chain length monitoring, graceful degradation to tree structures, and rate limiting of allocation requests. Assume attackers will find ways to probe the hash function—defense must remain robust even under partial information leakage.

Summary: Collision Handling

Collision handling is fundamental to hashed page table operation. The strategy chosen determines lookup performance, memory efficiency, concurrent access behavior, and security posture of the address translation system.

Key Takeaways

•Collisions are inevitable when mapping large VPN spaces to smaller hash tables—the Pigeonhole Principle guarantees this. Understanding collision probability mathematics enables proper table sizing.
•Chaining is the dominant strategy for page tables because it handles deletions cleanly, supports stable entry addresses for TLB caching, and enables fine-grained concurrent access with per-bucket locking.
•Open addressing alternatives (linear probing, quadratic probing, double hashing) offer better cache behavior but suffer from tombstone accumulation and are problematic for concurrent access.
•Advanced techniques like cuckoo hashing, hopscotch hashing, and Robin Hood hashing offer O(1) worst-case lookup but add implementation complexity unsuitable for kernel code.
•Hash flooding attacks can weaponize collisions for denial-of-service. Defenses include hash randomization (SipHash), chain length limits, and graceful degradation to tree structures.
•The load factor trade-off between 0.5 and 0.75 balances memory efficiency against collision frequency—proper sizing is crucial for predictable performance.

What's Next:

With collision handling mastered, we turn to inverted page tables—a radically different approach that maintains a single table indexed by physical frame number rather than virtual page number. This architecture offers unique advantages for systems with large physical memories and presents fascinating trade-offs in address translation design.

Page Complete

You now understand collision handling in hashed page tables comprehensively—from the mathematics of hash collisions through chaining and open addressing implementations to advanced techniques and security considerations. This knowledge is essential for understanding why hashing is viable for address translation despite inevitable collisions.

Collision Handling in Hashed Page Tables

The Inevitable Collision Problem

What You Will Learn

The Mathematics of Collisions

Understanding collision probability is essential for designing hash tables with predictable performance. The mathematics reveals surprising results about when and how frequently collisions occur.

The Birthday Problem Connection:

Collision probability in hash tables is analogous to the famous Birthday Problem: How many people must be in a room before there's a 50% chance two share a birthday?

The surprising answer—23 people for a 50% probability with 365 days—illustrates that collisions occur much sooner than intuition suggests.

For hash tables:

P(collision after k insertions) ≈ 1 - e^(-k²/2m)

Where:
  k = number of inserted entries
  m = number of buckets

Collision Probability Examples:

Collision Probability Analysis
Buckets (m)	Entries (k)	P(≥1 collision)	Expected Collisions
1,000	10	4.4%	0.045
1,000	40	55.3%	0.8
1,000	100	99.3%	4.9
10,000	100	39.3%	0.5
10,000	1,000	99.99%	49.5
100,000	10,000	99.99%	495

The Load Factor Formula:

The load factor α = k/m (entries / buckets) determines collision behavior:

Expected entries per bucket (under uniform hashing) = α

Probability bucket has exactly j entries:
P(bucket has j entries) = (α^j × e^(-α)) / j!   (Poisson approximation)

For α = 0.5:
  P(0 entries) = 60.65%  (empty buckets)
  P(1 entry)   = 30.33%  (no collision)
  P(2 entries) = 7.58%   (one collision)
  P(3 entries) = 1.26%   (two collisions)
  P(≥4)        = 0.18%   (multiple collisions)

This distribution shows that even with load factor 0.5, about 9% of buckets experience collisions. As load factor increases, collision severity grows rapidly.

The 50% Rule in Practice

Expected Search Length:

The average number of entries examined during a lookup depends on whether the search is successful (entry exists) or unsuccessful (entry not in table):

For Chaining:

Successful search:   E[probes] ≈ 1 + α/2
Unsuccessful search: E[probes] ≈ α

With α = 0.75:
  Successful:   1.375 probes average
  Unsuccessful: 0.75 probes average

For Open Addressing (Linear Probing):

Successful search:   E[probes] ≈ ½(1 + 1/(1-α))
Unsuccessful search: E[probes] ≈ ½(1 + 1/(1-α)²)

With α = 0.75:
  Successful:   2.5 probes average
  Unsuccessful: 8.5 probes average

These formulas reveal why chaining typically outperforms open addressing at higher load factors—the quadratic growth of unsuccessful search in open addressing becomes problematic.

Chaining: The Primary Strategy for Page Tables

Structure:

Bucket Array:         Collision Chains:
┌─────────┐
│ Bucket 0 │ ──→ NULL (empty)
├─────────┤
│ Bucket 1 │ ──→ [VPN:A5, PFN:42] ──→ [VPN:C1, PFN:107] ──→ NULL
├─────────┤
│ Bucket 2 │ ──→ NULL (empty)
├─────────┤
│ Bucket 3 │ ──→ [VPN:F7, PFN:88] ──→ NULL
├─────────┤
│ Bucket 4 │ ──→ [VPN:04, PFN:15] ──→ [VPN:24, PFN:203] ──→ [VPN:B4, PFN:91] ──→ NULL
└─────────┘

Each bucket contains a pointer to the first entry in its chain. Each entry contains a pointer to the next entry (or NULL if it's the last).

Converting Mermaid diagram...

Chaining Operations:

Lookup:

Compute hash: bucket = hash(vpn) % table_size
Traverse chain from buckets[bucket]
Compare each entry's VPN with target VPN
Return entry if match found, or signal page fault if chain exhausted

Insert:

Compute hash: bucket = hash(vpn) % table_size
Check if VPN already exists in chain (duplicates typically disallowed)
Allocate new entry, link it into chain (typically at head for O(1) insert)

Delete:

Compute hash: bucket = hash(vpn) % table_size
Traverse chain to find entry with matching VPN
Update predecessor's next pointer to skip deleted entry
Free deleted entry's memory

chaining_implementation.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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
// Complete chaining implementation for hashed page tables
 
typedef struct HPTEntry {
    uint64_t vpn;                    // Virtual page number
    uint64_t pfn;                    // Physical frame number
    uint32_t control;                // Control/protection bits
    struct HPTEntry* next;           // Chain pointer
} HPTEntry;
 
typedef struct {
    HPTEntry** buckets;              // Array of chain heads
    size_t num_buckets;              // Table size
    size_t entry_count;              // Current number of entries
    uint64_t hash_seed;              // Hash randomization seed
} HashedPageTable;
 
// Lookup with full chain traversal
HPTEntry* hpt_lookup_chained(HashedPageTable* table, uint64_t vpn) {
    // Compute bucket index
    uint64_t bucket = hash_vpn(vpn, table->hash_seed) & (table->num_buckets - 1);
    
    // Traverse the chain
    HPTEntry* entry = table->buckets[bucket];
    while (entry != NULL) {
        if (entry->vpn == vpn) {
            return entry;  // Found!
        }
        entry = entry->next;
    }
    
    return NULL;  // Not found - page fault
}
 
// Insert at chain head (O(1) insertion)
bool hpt_insert_chained(HashedPageTable* table, uint64_t vpn, 
                        uint64_t pfn, uint32_t control) {
    // Check for duplicates (optional, depends on policy)
    if (hpt_lookup_chained(table, vpn) != NULL) {
        return false;  // Already exists
    }
    
    // Allocate new entry
    HPTEntry* new_entry = (HPTEntry*)malloc(sizeof(HPTEntry));
    if (new_entry == NULL) return false;
    
    new_entry->vpn = vpn;
    new_entry->pfn = pfn;
    new_entry->control = control;
    
    // Compute bucket and insert at head
    uint64_t bucket = hash_vpn(vpn, table->hash_seed) & (table->num_buckets - 1);
    new_entry->next = table->buckets[bucket];
    table->buckets[bucket] = new_entry;
    
    table->entry_count++;
    
    // Check if resize needed
    if ((float)table->entry_count / table->num_buckets > 0.75) {
        hpt_resize(table, table->num_buckets * 2);
    }
    
    return true;
}
 
// Delete entry from chain
bool hpt_delete_chained(HashedPageTable* table, uint64_t vpn) {
    uint64_t bucket = hash_vpn(vpn, table->hash_seed) & (table->num_buckets - 1);
    
    HPTEntry* entry = table->buckets[bucket];
    HPTEntry* prev = NULL;
    
    while (entry != NULL) {
        if (entry->vpn == vpn) {
            // Found - remove from chain
            if (prev == NULL) {
                // Removing head of chain
                table->buckets[bucket] = entry->next;
            } else {
                // Removing from middle/end
                prev->next = entry->next;
            }
            
            free(entry);
            table->entry_count--;
            return true;
        }
        
        prev = entry;
        entry = entry->next;
    }
    
    return false;  // Not found
}

Why Chaining Dominates for Page Tables:

Unbounded Entries per Bucket: Chaining can handle any number of collisions gracefully—chains simply grow longer. This is important because page tables can experience burst insertions when processes load large programs.
Simple Memory Management: Each entry is independently allocated and freed. Entry lifetime is independent of other entries.
Stable Pointers: Once inserted, an entry's address doesn't change. This allows external references to entries (e.g., from TLB hardware that caches page table entries).
Efficient Deletion: Removing an entry only requires updating one pointer. No tombstones or reorganization needed.
Graceful Degradation: Even if collisions increase, the table remains functional (just slower). There's no catastrophic failure mode.
Concurrent Access Friendly: With appropriate locking (per-bucket locks, RCU), chains allow fine-grained concurrent access.

Open Addressing Alternatives

Core Concept:

Hash to bucket i
If bucket i is occupied:
    Probe bucket (i+probe(1)) mod m
    If that's occupied:
        Probe bucket (i+probe(2)) mod m
        ...
    Until empty bucket found or table full

No Chain Pointers: Open addressing eliminates the next-pointer overhead in each entry. All storage is contiguous in the bucket array.

Probing Strategies:

1. Linear Probing:

probe(k) = k
Sequence: i, i+1, i+2, i+3, ...

Pros: Excellent cache locality (sequential memory access) Cons: Primary clustering—long runs of occupied slots form

2. Quadratic Probing:

probe(k) = k²  (or k² + k)/2
Sequence: i, i+1, i+4, i+9, i+16, ...

Pros: Reduces primary clustering Cons: Secondary clustering, may not probe all buckets

3. Double Hashing:

probe(k) = k × hash₂(key)
Sequence: i, i+h₂, i+2h₂, i+3h₂, ...

Pros: Best distribution, minimal clustering Cons: Requires second hash function, more computation

Probing Strategy Comparison
Strategy	Clustering	Cache Behavior	Computation	Coverage
Linear	Severe (primary)	Excellent	Minimal	Full
Quadratic	Moderate (secondary)	Good	Low	Partial*
Double Hash	Minimal	Poor	Higher	Full

*Quadratic probing with table size m guarantees full coverage only if m is prime and load factor ≤ 0.5

Open Addressing Implementation:

open_addressing.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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
// Open addressing with linear probing
 
typedef struct {
    uint64_t vpn;          // Virtual page number (0 = empty)
    uint64_t pfn;          // Physical frame number
    uint32_t control;      // Control bits
    uint8_t state;         // EMPTY, OCCUPIED, DELETED
} OAEntry;
 
#define STATE_EMPTY    0
#define STATE_OCCUPIED 1
#define STATE_DELETED  2   // Tombstone for lazy deletion
 
typedef struct {
    OAEntry* entries;      // Contiguous array of entries
    size_t num_slots;      // Total slots
    size_t entry_count;    // Occupied slots (not counting deleted)
} OpenAddressTable;
 
// Lookup with linear probing
OAEntry* oa_lookup(OpenAddressTable* table, uint64_t vpn) {
    uint64_t slot = hash_vpn(vpn) & (table->num_slots - 1);
    uint64_t start = slot;
    
    do {
        OAEntry* entry = &table->entries[slot];
        
        if (entry->state == STATE_EMPTY) {
            // Empty slot - entry doesn't exist
            return NULL;
        }
        
        if (entry->state == STATE_OCCUPIED && entry->vpn == vpn) {
            // Found it!
            return entry;
        }
        
        // Continue probing (skip DELETED tombstones)
        slot = (slot + 1) & (table->num_slots - 1);
        
    } while (slot != start);  // Full table traversed
    
    return NULL;  // Not found
}
 
// Insert with linear probing
bool oa_insert(OpenAddressTable* table, uint64_t vpn, 
               uint64_t pfn, uint32_t control) {
    // Check load factor - must resize before table is full
    if ((float)table->entry_count / table->num_slots > 0.7) {
        if (!oa_resize(table, table->num_slots * 2)) {
            return false;  // Resize failed
        }
    }
    
    uint64_t slot = hash_vpn(vpn) & (table->num_slots - 1);
    uint64_t first_deleted = UINT64_MAX;  // Track first tombstone
    
    while (true) {
        OAEntry* entry = &table->entries[slot];
        
        if (entry->state == STATE_EMPTY) {
            // Use first deleted slot if we found one, else use empty
            if (first_deleted != UINT64_MAX) {
                slot = first_deleted;
                entry = &table->entries[slot];
            }
            
            entry->vpn = vpn;
            entry->pfn = pfn;
            entry->control = control;
            entry->state = STATE_OCCUPIED;
            table->entry_count++;
            return true;
        }
        
        if (entry->state == STATE_DELETED && first_deleted == UINT64_MAX) {
            first_deleted = slot;  // Remember first tombstone
        }
        
        if (entry->state == STATE_OCCUPIED && entry->vpn == vpn) {
            // Already exists - update
            entry->pfn = pfn;
            entry->control = control;
            return true;
        }
        
        slot = (slot + 1) & (table->num_slots - 1);
    }
}
 
// Delete with tombstone (lazy deletion)
bool oa_delete(OpenAddressTable* table, uint64_t vpn) {
    OAEntry* entry = oa_lookup(table, vpn);
    if (entry == NULL) return false;
    
    // Cannot simply mark as empty - would break probe chains
    // Use tombstone instead
    entry->state = STATE_DELETED;
    table->entry_count--;
    
    return true;
}

The Tombstone Problem

Chaining vs Open Addressing: Deep Trade-off Analysis

Memory Efficiency:

Chaining Memory:

Bucket array: m × 8 bytes (pointers)
Per entry: sizeof(entry) + 8 bytes (next ptr)

For m=16K buckets, n=10K entries:
  Bucket array: 128 KB
  Entry overhead: 8 bytes × 10K = 80 KB
  Entry data: 24 bytes × 10K = 240 KB
  Total: ~448 KB

Open Addressing Memory:

Slots: m × sizeof(entry) bytes
No separate pointers needed
Must keep load factor < 0.7

For n=10K entries at α=0.7:
  Slots needed: 10K / 0.7 ≈ 14.3K
  Use 16K slots (power of 2)
  Each slot: 24 bytes
  Total: 384 KB

Open addressing wins slightly on memory, but the difference is modest. The chain pointer overhead in chaining is offset by open addressing's need for extra empty slots.

Cache Performance:

Open Addressing (Linear Probing) Advantages:

Sequential memory access during probing
Prefetcher-friendly probe patterns
Entire probe sequence may be in same cache line
Better for tight loops with many lookups

Chaining Advantages:

Bucket array is compact and cacheable
Short chains (1-2 entries) common with good load factor
No wasted cache space for empty slots
Better when chains are short and entries are large

Worst-Case Behavior:

Worst-Case Analysis
Scenario	Chaining	Open Addressing
All entries hash to same bucket	O(n) chain traversal	O(n) probe sequence
Table nearly full	Chains grow, but still works	Probe sequences explode; may fail to insert
High deletion rate	Clean deallocation	Tombstone accumulation
Burst insertions	Chains grow gracefully	Must resize proactively
Adversarial input	Single long chain	Pathological probe sequences

Why Page Tables Use Chaining:

For address translation specifically, chaining wins decisively for several reasons:

Hardware TLB Integration: Modern TLBs cache pointers to page table entries. With chaining, an entry's address never changes after insertion. Open addressing may relocate entries during resizing, invalidating cached pointers.
Concurrent Access: Page tables are accessed by multiple CPUs simultaneously. Chaining allows per-bucket locking for fine-grained concurrency. Open addressing requires more complex synchronization because probe sequences span multiple buckets.
Deletion Patterns: Page mappings are frequently created and destroyed (process creation/exit, mmap/munmap). Chaining handles deletions cleanly without tombstone accumulation.
Predictable Latency: Real-time systems prefer bounded worst-case lookup times. While both can degrade to O(n), chaining's chain length is more predictable than open addressing's probe sequence length at high load.
Sparse Table Support: Page tables for large sparse address spaces have many unmapped regions. Chaining wastes no space for unmapped pages—empty buckets contain only NULL pointers.

Industry Practice

Advanced Collision Mitigation Techniques

Beyond basic chaining and open addressing, several advanced techniques can further reduce collision impact in hashed page tables.

1. Multiple Hash Functions (Cuckoo Hashing):

Cuckoo hashing uses two (or more) hash functions. Each entry can be stored in one of k possible locations:

Locations for entry E:
  - hash₁(E.vpn) mod m
  - hash₂(E.vpn) mod m
  (optionally more with k-ary cuckoo)

Insert: Try each location in order. If all occupied, "kick out" an existing entry and relocate it to its alternative location. Cascade until stable or cycle detected.

Lookup: Check all k locations in parallel (if hardware supports) or sequentially.

Benefits:

Worst-case O(1) lookup (only k locations to check)
High load factors (up to 0.9) achievable
Cache-friendly when k is small

cuckoo_hashing.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
51
52
53
54
55
56
57
58
59
60
61
62
// Simplified cuckoo hashing for page table entries
 
#define NUM_HASH_FUNCTIONS 2
#define MAX_KICKS 500  // Limit relocations before resize
 
typedef struct {
    CuckooEntry* tables[NUM_HASH_FUNCTIONS];  // Multiple tables
    size_t table_size;
    uint64_t seeds[NUM_HASH_FUNCTIONS];
} CuckooHashTable;
 
// Compute slot in table i for vpn
static inline uint64_t cuckoo_slot(CuckooHashTable* cht, 
                                    uint64_t vpn, int table_idx) {
    return hash_vpn(vpn, cht->seeds[table_idx]) & (cht->table_size - 1);
}
 
// Lookup: O(1) worst case - check exactly 2 locations
CuckooEntry* cuckoo_lookup(CuckooHashTable* cht, uint64_t vpn) {
    for (int i = 0; i < NUM_HASH_FUNCTIONS; i++) {
        uint64_t slot = cuckoo_slot(cht, vpn, i);
        CuckooEntry* entry = &cht->tables[i][slot];
        
        if (entry->valid && entry->vpn == vpn) {
            return entry;
        }
    }
    return NULL;  // Not found
}
 
// Insert with cuckoo displacement
bool cuckoo_insert(CuckooHashTable* cht, uint64_t vpn, uint64_t pfn) {
    // Check if already exists
    if (cuckoo_lookup(cht, vpn) != NULL) {
        return false;
    }
    
    CuckooEntry new_entry = {.vpn = vpn, .pfn = pfn, .valid = true};
    
    for (int kick = 0; kick < MAX_KICKS; kick++) {
        // Try to place in first available slot
        for (int i = 0; i < NUM_HASH_FUNCTIONS; i++) {
            uint64_t slot = cuckoo_slot(cht, new_entry.vpn, i);
            CuckooEntry* target = &cht->tables[i][slot];
            
            if (!target->valid) {
                // Empty slot - success!
                *target = new_entry;
                return true;
            }
        }
        
        // No empty slot - kick out entry from table 0
        uint64_t slot = cuckoo_slot(cht, new_entry.vpn, 0);
        CuckooEntry kicked = cht->tables[0][slot];
        cht->tables[0][slot] = new_entry;
        new_entry = kicked;
    }
    
    // Too many kicks - need to resize or use stash
    return cuckoo_resize_and_insert(cht, new_entry);
}

2. Hopscotch Hashing:

A hybrid approach combining open addressing's cache friendliness with chaining's resistance to clustering.

Concept:

Each bucket has a neighborhood (e.g., 32 adjacent buckets)
Entries must reside within their neighborhood
Bitmap in each bucket tracks which neighbors contain its entries
Lookup checks bitmap, only probing indicated positions

3. Robin Hood Hashing:

A fairness-based open addressing variant:

Concept:

Track probe distance for each entry (how far from ideal position)
During insert, if new entry has traveled farther than existing entry, swap them
"Steal from the rich, give to the poor" - equalizes probe distances

Benefits:

Expected maximum probe distance is O(log log n)
Much tighter variance than standard open addressing
Cache performance remains excellent

4. Bloom Filter Pre-screening:

Before searching the hash table, consult a Bloom filter:

if (!bloom_might_contain(vpn)) {
    return PAGE_FAULT;  // Definitely not in table
}
// Only now search hash table
return hpt_lookup(table, vpn);

Benefits:

Bloom filters are very fast (few cache-friendly memory accesses)
Eliminate most unsuccessful searches without touching hash table
Particularly valuable when page faults are common

Research vs Production

Security Considerations: Hash Flooding Attacks

The Attack Model:

Attacker runs code on the system (local process or network service)
Attacker discovers or guesses the hash function
Attacker generates VPN allocation requests that all hash to the same bucket
Page table degrades to a single long chain
Every subsequent translation becomes O(n), causing system-wide slowdown

Real-World Impact:

Hash flooding attacks have been demonstrated against:

Web servers (HTTP header hash tables) - CVE-2011-4885
Language runtimes (Python, Ruby, PHP dictionaries)
DNS resolvers (response caching)
Network stacks (connection hash tables)

Page tables are somewhat protected because VPN allocation is typically controlled by the OS, but shared hosting environments and user-controlled mmap could expose vulnerabilities.

Defense Mechanisms:

1. Hash Randomization:

Initialize hash function with per-table random seed:

table->seed = get_random_u64();  // From hardware RNG

uint64_t hash(uint64_t vpn, uint64_t seed) {
    return final_mix(vpn ^ seed);  // Seed makes hash unpredictable
}

Attacker cannot predict which VPNs will collide without knowing the seed.

2. SipHash:

Cryptographically strong hash function designed for hash tables:

128-bit key (seed)
Proven collision resistance
Reasonably fast (<10 cycles/byte on modern CPUs)
Used by Linux kernel, Python 3.4+, Rust

3. Chain Length Limits:

Enforce maximum chain length and trigger defensive action:

#define MAX_CHAIN_LENGTH 64

if (chain_length > MAX_CHAIN_LENGTH) {
    // Potential attack detected
    trigger_rehash_with_new_seed();
    log_security_warning("Excessive hash collisions");
}

4. Secondary Structures:

Convert long chains to balanced trees:

if (chain_length > TREE_THRESHOLD) {
    convert_chain_to_rb_tree(bucket);
    // Now worst-case is O(log n) instead of O(n)
}

Java 8 HashMap uses this approach.

secure_hashing.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
51
52
53
54
55
56
57
58
// Secure hashing with SipHash for page tables
 
#include <stdint.h>
 
// SipHash-2-4: Two rounds per message block, four finalization rounds
// Provides sufficient security with excellent performance
 
static inline uint64_t rotl64(uint64_t x, int b) {
    return (x << b) | (x >> (64 - b));
}
 
static inline void sipround(uint64_t* v0, uint64_t* v1, 
                            uint64_t* v2, uint64_t* v3) {
    *v0 += *v1; *v1 = rotl64(*v1, 13); *v1 ^= *v0;
    *v0 = rotl64(*v0, 32);
    *v2 += *v3; *v3 = rotl64(*v3, 16); *v3 ^= *v2;
    *v0 += *v3; *v3 = rotl64(*v3, 21); *v3 ^= *v0;
    *v2 += *v1; *v1 = rotl64(*v1, 17); *v1 ^= *v2;
    *v2 = rotl64(*v2, 32);
}
 
uint64_t siphash_vpn(uint64_t vpn, const uint64_t key[2]) {
    uint64_t v0 = key[0] ^ 0x736f6d6570736575ULL;
    uint64_t v1 = key[1] ^ 0x646f72616e646f6dULL;
    uint64_t v2 = key[0] ^ 0x6c7967656e657261ULL;
    uint64_t v3 = key[1] ^ 0x7465646279746573ULL;
    
    // Process 8-byte VPN block
    v3 ^= vpn;
    sipround(&v0, &v1, &v2, &v3);
    sipround(&v0, &v1, &v2, &v3);
    v0 ^= vpn;
    
    // Finalization
    v2 ^= 0xff;
    for (int i = 0; i < 4; i++) {
        sipround(&v0, &v1, &v2, &v3);
    }
    
    return v0 ^ v1 ^ v2 ^ v3;
}
 
// Usage in page table
typedef struct SecureHashedPageTable {
    HPTEntry** buckets;
    size_t num_buckets;
    uint64_t sip_key[2];  // 128-bit random key
} SecureHashedPageTable;
 
void init_secure_hpt(SecureHashedPageTable* table) {
    // Get cryptographically random key
    get_random_bytes(table->sip_key, 16);
}
 
uint64_t secure_bucket(SecureHashedPageTable* table, uint64_t vpn) {
    uint64_t hash = siphash_vpn(vpn, table->sip_key);
    return hash & (table->num_buckets - 1);
}

Defense in Depth

Summary: Collision Handling

Key Takeaways

•Collisions are inevitable when mapping large VPN spaces to smaller hash tables—the Pigeonhole Principle guarantees this. Understanding collision probability mathematics enables proper table sizing.
•Chaining is the dominant strategy for page tables because it handles deletions cleanly, supports stable entry addresses for TLB caching, and enables fine-grained concurrent access with per-bucket locking.
•Open addressing alternatives (linear probing, quadratic probing, double hashing) offer better cache behavior but suffer from tombstone accumulation and are problematic for concurrent access.
•Advanced techniques like cuckoo hashing, hopscotch hashing, and Robin Hood hashing offer O(1) worst-case lookup but add implementation complexity unsuitable for kernel code.
•Hash flooding attacks can weaponize collisions for denial-of-service. Defenses include hash randomization (SipHash), chain length limits, and graceful degradation to tree structures.
•The load factor trade-off between 0.5 and 0.75 balances memory efficiency against collision frequency—proper sizing is crucial for predictable performance.

What's Next:

Page Complete