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

// Physical frame allocator (simplified)
 
// Per-NUMA-node free lists
struct free_area {
    struct list_head free_list;  // List of free page blocks
    unsigned long nr_free;       // Count of free pages
};
 
// Per-zone free area lists (one per order for buddy allocator)
struct zone {
    struct free_area free_area[MAX_ORDER];  // Order 0-10 (1, 2, 4, ... 1024 pages)
    unsigned long managed_pages;
    unsigned long watermark[NR_WMARK];      // Min-low-high watermarks
};
 
// Core page allocation function
struct page *alloc_pages(gfp_t gfp_mask, unsigned int order) {
    struct page *page;
    unsigned int alloc_flags;
    
    // Step 1: Determine allocation flags from gfp_mask
    alloc_flags = gfp_to_alloc_flags(gfp_mask);
    
    // Step 2: Try to get a page from the free lists
    page = get_page_from_freelist(gfp_mask, order, alloc_flags);
    if (page)
        return page;  // Got a page immediately
    
    // Step 3: No free pages - enter the slow path
    // This may involve reclaiming pages from caches
    page = __alloc_pages_slowpath(gfp_mask, order);
    
    return page;  // May be NULL if truly out of memory
}
 
// Page fault specific allocation
struct page *alloc_page_for_fault(struct vm_area_struct *vma, 
                                   unsigned long address) {
    gfp_t gfp_flags = GFP_HIGHUSER_MOVABLE;
    
    // Prefer memory close to the faulting CPU (NUMA)
    int preferred_nid = numa_node_id();
    
    // Policy might specify different behavior
    if (vma->vm_policy) {
        preferred_nid = get_policy_node(vma->vm_policy, address);
    }
    
    // Allocate the page
    struct page *page = __alloc_pages_node(preferred_nid, gfp_flags, 0);
    
    if (!page) {
        // Emergency: try any node
        page = __alloc_pages(gfp_flags | __GFP_THISNODE, 0);
    }
    
    return page;
}

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

// Simplified page reclaim logic
 
// kswapd - background reclaim daemon
int kswapd(void *p) {
    struct zone *zone = p;
    
    while (!kthread_should_stop()) {
        if (zone_watermark_ok(zone, order, zone->watermark[WMARK_HIGH]))
            // Enough free memory, sleep
            wait_event_interruptible(zone->kswapd_wait, !zone_watermark_ok());
        else
            // Below high watermark, reclaim pages
            shrink_zone(zone, &sc);
    }
}
 
// Direct reclaim - called when allocation fails
static unsigned long try_to_free_pages(struct zonelist *zonelist, gfp_t gfp_mask) {
    struct scan_control sc = {
        .nr_to_reclaim = SWAP_CLUSTER_MAX,
        .gfp_mask = gfp_mask,
        .priority = DEF_PRIORITY,
    };
    
    unsigned long nr_reclaimed = 0;
    
    do {
        nr_reclaimed += shrink_zones(zonelist, &sc);
        sc.priority--;  // Get more aggressive
    } while (nr_reclaimed < sc.nr_to_reclaim && sc.priority >= 0);
    
    return nr_reclaimed;
}
 
// Shrink by scanning LRU lists
static unsigned long shrink_lruvec(struct lruvec *lruvec, 
                                    struct scan_control *sc) {
    unsigned long nr_reclaimed = 0;
    
    // Scan inactive anonymous pages (candidates for swap)
    nr_reclaimed += shrink_inactive_list(LRU_INACTIVE_ANON, lruvec, sc);
    
    // Scan inactive file pages (candidates for discarding/writeback)
    nr_reclaimed += shrink_inactive_list(LRU_INACTIVE_FILE, lruvec, sc);
    
    return nr_reclaimed;
}
 
// For a single page, decide and execute reclaim
static int shrink_page(struct page *page, struct scan_control *sc) {
    // Is page referenced recently? Move to active list
    if (page_referenced(page)) {
        activate_page(page);
        return PAGEREF_ACTIVE;
    }
    
    // Anonymous page - must swap out
    if (PageAnon(page)) {
        if (!add_to_swap(page))
            return PAGEREF_KEEP;  // No swap space, can't reclaim
        
        // Write to swap (may be async)
        swap_writepage(page);
    }
    
    // File-backed dirty page - write back
    if (PageDirty(page)) {
        writepage(page);
    }
    
    // Remove from page tables (reverse mapping)
    try_to_unmap(page);
    
    // Free the page
    free_page(page);
    return PAGEREF_RECLAIMED;
}

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

// Reading a page from swap
 
int swap_readpage(struct page *page, swp_entry_t entry) {
    struct swap_info_struct *sis;
    struct bio *bio;
    sector_t sector;
    int ret;
    
    // Lock the page - prevents concurrent I/O or access
    lock_page(page);
    
    // Get swap device info
    sis = swp_swap_info(entry);
    
    // Calculate disk sector for this swap slot
    sector = swp_offset(entry);
    sector <<= PAGE_SHIFT - SECTOR_SHIFT;  // Convert page offset to sector
    
    // Allocate and set up bio (block I/O request)
    bio = bio_alloc(sis->bdev, 1, REQ_OP_READ, GFP_KERNEL);
    bio->bi_iter.bi_sector = sector + sis->start_sector;
    bio_add_page(bio, page, PAGE_SIZE, 0);
    
    // Submit the I/O request
    bio->bi_end_io = swap_read_endio;  // Completion callback
    bio->bi_private = page;
    submit_bio(bio);
    
    // Wait for completion (page fault path waits synchronously)
    wait_on_page_locked(page);
    
    // Check if read succeeded
    if (PageError(page)) {
        ClearPageError(page);
        return -EIO;
    }
    
    SetPageUptodate(page);  // Mark page as having valid content
    return 0;
}
 
// Completion callback for swap read
static void swap_read_endio(struct bio *bio) {
    struct page *page = bio->bi_private;
    
    if (bio->bi_status) {
        SetPageError(page);
    } else {
        SetPageUptodate(page);
    }
    
    unlock_page(page);  // Wake up waiters
    bio_put(bio);
}
 
// Reading from a file (filesystem-specific)
int generic_file_read_page(struct file *file, struct page *page) {
    struct inode *inode = file->f_inode;
    struct address_space *mapping = inode->i_mapping;
    loff_t offset = page_offset(page);
    
    // Read from filesystem into page
    return mapping->a_ops->readpage(file, page);
}
 
// Special case: zero-fill (no I/O needed)
void zero_fill_page(struct page *page) {
    void *kaddr = kmap_local_page(page);
    memset(kaddr, 0, PAGE_SIZE);
    kunmap_local(kaddr);
    SetPageUptodate(page);
}

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

// Updating the page table entry after loading page
 
int finish_fault(struct vm_fault *vmf) {
    struct mm_struct *mm = vmf->vma->vm_mm;
    struct page *page = vmf->page;
    pte_t *pte = vmf->pte;
    pte_t entry;
    spinlock_t *ptl;
    
    // Step 1: Construct the new PTE
    entry = mk_pte(page, vmf->vma->vm_page_prot);
    
    // Apply VMA permissions
    if (vmf->vma->vm_flags & VM_WRITE)
        entry = pte_mkwrite(entry);
    if (vmf->vma->vm_flags & VM_EXEC)
        entry = pte_mkexec(entry);
    
    // Mark as young (just accessed)
    entry = pte_mkyoung(entry);
    
    // For write faults, may mark dirty
    if (vmf->flags & FAULT_FLAG_WRITE)
        entry = pte_mkdirty(entry);
    
    // Step 2: Lock the page table
    ptl = pte_lockptr(mm, vmf->pmd);
    spin_lock(ptl);
    
    // Step 3: Check if PTE was modified by another thread
    if (!pte_none(*pte) && pte_present(*pte)) {
        // Another thread already handled this fault!
        spin_unlock(ptl);
        put_page(page);  // We don't need this page
        return VM_FAULT_NOPAGE;
    }
    
    // Step 4: Atomically install the new PTE
    set_pte_at(mm, vmf->address, pte, entry);
    
    // Step 5: Update memory accounting
    mm->_rss++;  // Increment resident set size
    
    spin_unlock(ptl);
    
    return 0;
}
 
// Architecture-specific PTE setting (x86-64)
static inline void set_pte_at(struct mm_struct *mm, 
                               unsigned long addr,
                               pte_t *ptep, 
                               pte_t pte) {
    // On x86-64, PTEs are 64-bit and naturally aligned
    // A simple store is atomic for aligned 64-bit on x86-64
    WRITE_ONCE(*ptep, pte);
    
    // Memory barrier to ensure PTE is visible before TLB operations
    smp_wmb();
}
 
// Allocating intermediate page table levels if needed
pte_t *walk_and_allocate(struct mm_struct *mm, unsigned long addr) {
    pgd_t *pgd;
    p4d_t *p4d;
    pud_t *pud;
    pmd_t *pmd;
    
    pgd = pgd_offset(mm, addr);
    
    p4d = p4d_alloc(mm, pgd, addr);
    if (!p4d) return NULL;
    
    pud = pud_alloc(mm, p4d, addr);
    if (!pud) return NULL;
    
    pmd = pmd_alloc(mm, pud, addr);
    if (!pmd) return NULL;
    
    return pte_alloc_map(mm, pmd, addr);
}

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

// TLB operations in page fault context
 
// When installing a completely new mapping (not present → present)
// No TLB invalidation needed - there was no valid TLB entry
void install_new_pte(struct mm_struct *mm, pte_t *pte, pte_t entry) {
    set_pte_at(mm, addr, pte, entry);
    // Next access will TLB miss and load our entry - no flush needed
}
 
// When modifying an existing mapping (e.g., COW, permission upgrade)
void modify_existing_pte(struct mm_struct *mm, unsigned long addr,
                          pte_t *pte, pte_t new_entry) {
    pte_t old_entry = *pte;
    
    // Install new PTE
    set_pte_at(mm, addr, pte, new_entry);
    
    // Must invalidate stale TLB entries
    // Single CPU case:
    flush_tlb_page(mm, addr);
    
    // Multi-CPU case: This is a TLB shootdown
    // Must send IPI to all CPUs that might have this mapping cached
}
 
// TLB shootdown - invalidate on all relevant CPUs
void flush_tlb_page_all(struct mm_struct *mm, unsigned long addr) {
    // Get mask of CPUs that have used this mm
    const cpumask_t *mm_cpumask = mm_cpumask(mm);
    
    // Current CPU - local flush
    local_flush_tlb_page(addr);
    
    // Other CPUs - send Inter-Processor Interrupt
    smp_call_function_many(mm_cpumask, 
                           tlb_flush_func, 
                           &addr, 
                           1 /* wait */);
}
 
// IPI handler on remote CPU
void tlb_flush_func(void *info) {
    unsigned long addr = *(unsigned long *)info;
    local_flush_tlb_page(addr);
}
 
// Local TLB flush (x86)
static inline void local_flush_tlb_page(unsigned long addr) {
    // INVLPG instruction invalidates single TLB entry
    asm volatile("invlpg (%0)" : : "r" (addr) : "memory");
}
 
// Flush entire TLB (x86) - used for larger changes
static inline void local_flush_tlb(void) {
    // Reloading CR3 flushes entire TLB (except global entries)
    unsigned long cr3 = read_cr3();
    write_cr3(cr3);
}

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

// Locking in page fault path
 
int __do_page_fault(struct mm_struct *mm, unsigned long address,
                    unsigned int flags, struct pt_regs *regs) {
    struct vm_area_struct *vma;
    int fault;
    
    // Step 1: Acquire mmap_lock in read mode
    // This protects VMA structure from concurrent modification
    mmap_read_lock(mm);
    
    // Find VMA under lock protection
    vma = find_vma(mm, address);
    if (!vma) {
        mmap_read_unlock(mm);
        return VM_FAULT_SIGSEGV;
    }
    
    // Step 2: Handle the fault (will acquire PTL internally)
    fault = handle_mm_fault(mm, vma, address, flags);
    
    // Step 3: Release mmap_lock
    mmap_read_unlock(mm);
    
    return fault;
}
 
// Fine-grained page table locking
int finish_fault(struct vm_fault *vmf) {
    spinlock_t *ptl;
    pte_t *pte;
    
    // Acquire page table lock for this specific PTE
    // Different from mmap_lock - very fine-grained
    pte = pte_offset_map_lock(vmf->vma->vm_mm, vmf->pmd, 
                               vmf->address, &ptl);
    
    // ... update PTE ...
    
    pte_unmap_unlock(pte, ptl);
}
 
// Page lock for I/O synchronization
int read_swap_page(struct page *page, swp_entry_t entry) {
    // Lock page - blocks other threads from same page I/O
    lock_page(page);
    
    // Do swap read I/O
    int err = swap_readpage(page, entry);
    
    // Page stays locked until I/O completes
    // Then swap_read_endio() unlocks it
    return err;
}
 
// Speculative fault handling (kernel 5.8+)
// Try without mmap_lock first
int do_user_addr_fault(struct pt_regs *regs, unsigned long error_code,
                       unsigned long address) {
    // First, try lockless (speculative) handling
    // Works if VMA is stable and page tables are populated
    if (maybe_handle_faults_without_lock(mm, address, flags))
        return 0;
    
    // Fall back to locked path
    mmap_read_lock(mm);
    // ... full fault handling ...
    mmap_read_unlock(mm);
}

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

// Error handling in page fault path
 
int do_fault_around(struct vm_fault *vmf, pgoff_t start_pgoff) {
    struct page *page;
    int ret;
    
    // Try to allocate a page
    page = alloc_page(GFP_HIGHUSER_MOVABLE);
    if (!page) {
        // OOM - couldn't allocate
        return VM_FAULT_OOM;
    }
    
    // Try to read from file/swap
    ret = do_read_page(page, vmf);
    if (ret < 0) {
        put_page(page);
        if (ret == -EIO)
            return VM_FAULT_SIGBUS;  // I/O error
        if (ret == -ENOMEM)
            return VM_FAULT_OOM;     // OOM during I/O
        return VM_FAULT_ERROR;       // Generic error
    }
    
    // Check for data corruption
    if (!PageUptodate(page)) {
        put_page(page);
        return VM_FAULT_SIGBUS;  // Page didn't load correctly
    }
    
    return 0;  // Success
}
 
// After do_page_fault returns, higher level handles result
void handle_page_fault_result(int fault_result, struct pt_regs *regs,
                               unsigned long address) {
    if (fault_result & VM_FAULT_OOM) {
        // OOM - this is serious
        pagefault_out_of_memory();  // May invoke OOM killer
        return;
    }
    
    if (fault_result & VM_FAULT_SIGBUS) {
        // I/O error or similar
        do_sigbus(regs, address);  // Send SIGBUS to process
        return;
    }
    
    if (fault_result & VM_FAULT_SIGSEGV) {
        // Invalid access
        do_sigsegv(regs, address);  // Send SIGSEGV to process
        return;
    }
    
    // Success - return to user mode and retry instruction
}
 
// OOM killer - last resort
void pagefault_out_of_memory(void) {
    if (current_thread_has_oom_victim())
        return;  // This thread is already being killed
    
    // Select a process to kill to free memory
    out_of_memory(&oc);
}