Loading learning content...
In the entire edifice of virtual memory—spanning page tables, TLBs, page fault handlers, swap management, and more—one of the most critical components is surprisingly simple: a single bit. This bit, stored in each page table entry, answers a fundamental question: Is this page currently in physical memory, or does it need to be loaded from disk?
This bit goes by many names: the valid-invalid bit, the present bit, the in-memory bit, or sometimes just the P bit. Regardless of nomenclature, its function is singular and essential: it tells the Memory Management Unit (MMU) whether a page-to-frame mapping is currently usable or whether the operating system must intervene to make the page accessible.
Without this single bit, demand paging would be impossible. There would be no way for the hardware to detect when a page needs to be loaded, and no way to trigger the page fault that initiates the loading process. This humble flag is the bridge between the illusion of a large, fully-populated address space and the reality of limited physical memory.
By the end of this page, you will understand the valid-invalid bit in depth: its role in page table entries, how it enables the MMU to trigger page faults, the various states it can indicate, and how the operating system manipulates this bit as part of page fault handling. You'll also explore edge cases and the relationship between this bit and other page table entry fields.
Before focusing on the valid-invalid bit, let's understand the context in which it lives: the page table entry (PTE). Each PTE describes the mapping for one page of virtual address space, and it contains several pieces of information.
The Anatomy of a Page Table Entry:
While the exact format varies by architecture, a typical PTE contains:
Frame Number (Physical Page Number): When the page is in memory, this field indicates which physical frame holds the page's data
Present/Valid Bit (P): Indicates whether the page is currently in physical memory
Read/Write Bit (R/W): Permission flag for write access
User/Supervisor Bit (U/S): Access permission based on CPU privilege level
Accessed Bit (A): Set by hardware when the page is read
Dirty/Modified Bit (D): Set by hardware when the page is written
Execute Disable Bit (NX/XD): Prevents code execution from this page
Other Flags: Cache control, global page, etc.
Example: x86-64 Page Table Entry Format
63 62 52 51 12 11 9 8 7 6 5 4 3 2 1 0
┌────────┬──────────┬────────────────────────────────────────────────┬───────┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
│ NX │ Reserved │ Physical Frame Number │ Avail │G│ │D│A│ │ │U│W│P│
│Exec Dis│ (9 bits) │ (40 bits) │(3 bits)│ │ │ │ │ │ │/│/│ │
│ │ │ │ │ │ │ │ │ │ │S│R│ │
└────────┴──────────┴────────────────────────────────────────────────┴───────┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
P (bit 0): Present bit - THE VALID-INVALID BIT
R/W (bit 1): Read/Write (0 = read-only, 1 = read-write)
U/S (bit 2): User/Supervisor (0 = supervisor only, 1 = user accessible)
PWT (bit 3): Page-level Write-Through
PCD (bit 4): Page-level Cache Disable
A (bit 5): Accessed (set by CPU on access)
D (bit 6): Dirty (set by CPU on write)
PAT (bit 7): Page Attribute Table index
G (bit 8): Global (don't flush from TLB on context switch)
In this 64-bit entry, the Present bit (P) occupies bit 0—the least significant bit. When this bit is 0, the processor treats the entire rest of the entry differently than when it's 1.
When the Present bit is 0, the CPU ignores all other fields in the PTE. The remaining 63 bits are available for the operating system to use for any purpose—typically to store information about where the page can be found (swap location, file offset, etc.). This dual interpretation of the PTE based on the Present bit is fundamental to efficient demand paging implementation.
The terminology "valid-invalid bit" can be confusing because "valid" has multiple meanings in the context of virtual memory. Let's clarify the distinction carefully.
What "Valid" Means:
When the bit is set (1), the page table entry is considered valid in the sense that:
What "Invalid" Means:
When the bit is clear (0), the page table entry is invalid in the sense that:
Important: "Invalid" does NOT necessarily mean "illegal." An invalid PTE might represent:
| Present Bit | Status | Frame Number Field | Access Result | Example Scenario |
|---|---|---|---|---|
| 1 (Valid) | In memory | Valid frame number | Direct memory access | Recently accessed code page |
| 0 (Invalid) | Not in memory | OS-defined data | Page fault exception | Page swapped to disk |
| 0 (Invalid) | Never allocated | Null/special marker | Page fault → segfault | Access beyond heap limit |
| 0 (Invalid) | Demand zero | Zero-fill marker | Page fault → zero page | Fresh heap allocation |
The Dual Nature of Page Faults:
When a page fault occurs, the operating system must determine what kind of "invalid" entry triggered it:
The OS typically maintains additional data structures (like Linux's vm_area_struct) to track which address ranges are legitimate. The page fault handler consults these structures to determine the appropriate response.
The hardware (MMU) doesn't distinguish between 'needs to be loaded' and 'illegal access'—it just sees Present = 0 and triggers a fault. The distinction is made by the OS in the page fault handler, which has access to additional metadata about the process's address space layout.
Understanding exactly how the hardware uses the valid-invalid bit is essential for systems programming. Let's trace through the MMU's behavior step by step.
The Memory Access Sequence:
When the CPU issues a memory access (read or write):
Virtual Address Generated: The CPU's execution unit generates a virtual address
TLB Check: The MMU first checks the Translation Lookaside Buffer
Page Table Walk: The MMU traverses the page table hierarchy
Final PTE Check: The MMU examines the leaf-level PTE
The Page Fault Exception:
When Present = 0, the processor raises a page fault exception. On x86 architectures, this is interrupt vector 14. The processor:
Note that bit 0 of the error code being 0 indicates the fault was due to Present = 0. If bit 0 is 1, the page was present but some other violation occurred (like writing to a read-only page).
123456789101112131415161718192021222324252627282930313233343536373839404142434445
/* Simplified x86-64 page fault handler */ void page_fault_handler(struct registers *regs) { /* Get faulting address from CR2 register */ uint64_t fault_addr; asm volatile("mov %%cr2, %0" : "=r"(fault_addr)); /* Get error code pushed by CPU */ uint64_t error_code = regs->error_code; /* Decode error code */ bool page_present = (error_code & 0x1) != 0; bool write_access = (error_code & 0x2) != 0; bool user_mode = (error_code & 0x4) != 0; bool reserved_write = (error_code & 0x8) != 0; bool instruction_fetch = (error_code & 0x10) != 0; if (page_present) { /* Page was present - this is a protection fault, not a missing page fault */ handle_protection_fault(fault_addr, write_access, user_mode); return; } /* Present bit was 0 - page not in memory */ struct vm_area *vma = find_vm_area(current->mm, fault_addr); if (!vma) { /* Fault address not in any valid region - SIGSEGV */ send_signal(current, SIGSEGV); return; } /* Valid region - handle the demand fault */ if (vma->flags & VM_ANONYMOUS) { /* Anonymous page - zero fill or load from swap */ handle_anonymous_fault(vma, fault_addr, write_access); } else { /* File-backed page - load from file */ handle_file_fault(vma, fault_addr, write_access); } /* Instruction will be restarted by hardware on return */}After the page fault handler loads the page and updates the PTE (setting Present = 1), it returns. The CPU then restarts the faulting instruction from the beginning. This time, the present bit is set, and the access succeeds. This seamless restart is what makes demand paging transparent to applications.
A page table entry doesn't just toggle between "present" and "not present." In practice, there are multiple logical states a PTE can occupy throughout a page's lifecycle. Understanding these states is crucial for understanding demand paging behavior.
The Page State Machine:
| State | P Bit | Other Bits | Meaning |
|---|---|---|---|
| Not Allocated | 0 | Null/zero | Address space not mapped |
| Demand Zero | 0 | Zero-fill marker | Will get a zero page on access |
| File-Backed Pending | 0 | File + offset | Data available in file |
| Swapped Out | 0 | Swap slot ID | Data in swap partition/file |
| Present Clean | 1 | R/W, A set | In memory, unmodified |
| Present Dirty | 1 | R/W, A, D set | In memory, modified |
| Present Read-Only | 1 | R only, COW flag | Shared, copy-on-write pending |
State Transitions:
Pages move between these states as a result of various operations:
┌──────────────────────────────────────┐
│ │
▼ │
┌──────────────┐ ┌──────────────┐ ┌──────────────────┐ │
│ Not Allocated│───▶│ Demand Zero │───▶│ Present (Clean) │───┤
└──────────────┘ └──────────────┘ └──────────────────┘ │
│ │ first ▲ │ │
│ mmap(file) │ access │ │ write │
▼ ▼ │ ▼ │
┌──────────────┐ ┌──────────────┐ ┌──────────────────┐ │
│ File Pending │───▶│ Present │◀───│ Present (Dirty) │───┤
└──────────────┘ │ (from file) │ └──────────────────┘ │
▲ └──────────────┘ │ │
│ │ │ evicted │
│ clean page evicted │ ▼ │
│ │ ┌──────────────────┐ │
└────────────────────┘ │ Swapped Out │───┘
└──────────────────┘
│
│ accessed again
▼
Page fault → swap in
Each transition involves updating the page table entry, and many transitions are triggered by memory accesses (which cause page faults if the present bit is 0).
When Present = 0, the encoding of the remaining bits is entirely OS-defined. Linux, Windows, and macOS each use different formats to store swap slot numbers, file offsets, and state flags in non-present PTEs. The hardware doesn't care—it just faults without examining the other bits.
Linux's Non-Present PTE Encoding:
Linux uses the following convention for non-present PTEs (simplified):
For a swapped-out page (x86-64):
┌────────────────────────────────────────────────────────────┐
│ P=0 │ Type=1 │ Swap Type │ Swap Offset │
│ │ (swap) │ (5 bits) │ (50 bits) │
└────────────────────────────────────────────────────────────┘
For a file-backed not-present page:
┌────────────────────────────────────────────────────────────┐
│ P=0 │ Type=0 │ File Page Offset (stored elsewhere) │
│ │ (file) │ │
└────────────────────────────────────────────────────────────┘
The "Swap Type" field identifies which swap device (if multiple are configured), and the "Swap Offset" identifies the location within that device. This allows the page fault handler to know exactly where to read the page from.
The operating system manipulates the valid-invalid bit as part of several critical operations. Understanding when and why these manipulations occur is essential for systems programming.
Operations That Change the Valid-Invalid Bit:
1. Page Fault Resolution (0 → 1): When replacing a not-present page with a present one:
1. Allocate a physical frame
2. Load page content (from disk, swap, or zero-fill)
3. Update PTE:
- Set frame number
- Set Present = 1
- Set appropriate protection bits
4. Flush TLB entry for this page (if stale)
2. Page Eviction (1 → 0): When making room for other pages:
1. If page is dirty, write contents to backing store
2. Update PTE:
- Set Present = 0
- Store backing store location in PTE
3. Flush TLB entry for this page
4. Free the physical frame
3. Copy-on-Write Setup (page marked read-only):
1. Page stays present (Present = 1)
2. But R/W bit set to read-only
3. Write attempt causes protection fault, not page fault
4. Handler copies page, then sets both copies to R/W
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869
/* Example PTE manipulation functions */ typedef uint64_t pte_t; /* PTE bit masks for x86-64 */#define PTE_PRESENT (1UL << 0)#define PTE_WRITABLE (1UL << 1)#define PTE_USER (1UL << 2)#define PTE_ACCESSED (1UL << 5)#define PTE_DIRTY (1UL << 6)#define PTE_FRAME_MASK 0x000FFFFFFFFFF000UL /* Make a page present in memory */void pte_make_present(pte_t *pte, uint64_t frame_phys_addr, bool writable, bool user_accessible) { pte_t new_pte = 0; /* Set frame address (must be page-aligned) */ new_pte |= (frame_phys_addr & PTE_FRAME_MASK); /* Set present bit */ new_pte |= PTE_PRESENT; /* Set permissions */ if (writable) new_pte |= PTE_WRITABLE; if (user_accessible) new_pte |= PTE_USER; /* Atomic update to prevent races */ *pte = new_pte; /* TLB flush may be needed if there was an old mapping */} /* Mark a page as not present (evicting it) */swap_entry_t pte_make_not_present(pte_t *pte) { pte_t old_pte = *pte; /* Record if page was dirty - need to write to swap */ bool was_dirty = (old_pte & PTE_DIRTY) != 0; /* Get the frame number for writeback */ uint64_t frame_addr = old_pte & PTE_FRAME_MASK; /* Allocate swap slot if page was modified */ swap_entry_t swap_entry = SWAP_ENTRY_NONE; if (was_dirty) { swap_entry = swap_allocate_slot(); swap_write_page(swap_entry, frame_addr); } /* Create new non-present PTE with swap location */ pte_t new_pte = 0; /* Present bit = 0 */ new_pte |= swap_entry_to_pte(swap_entry); /* Atomic update */ *pte = new_pte; /* MUST flush TLB after clearing present bit */ tlb_flush_page(pte_to_virtual_address(pte)); return swap_entry;} /* Check if a PTE represents a present page */static inline bool pte_is_present(pte_t pte) { return (pte & PTE_PRESENT) != 0;}When changing the present bit from 1 to 0, the TLB MUST be flushed for that page. Otherwise, the processor might continue using the stale TLB entry and access memory that has been freed or reassigned. This is a common source of extremely subtle bugs in OS development. On multiprocessor systems, the TLB must be flushed on ALL CPUs (a costly operation called TLB shootdown).
Atomic Operations and Race Conditions:
PTE manipulation must be carefully synchronized:
Operating systems use atomic operations (compare-and-swap, locked read-modify-write) and careful locking strategies to ensure PTE updates are correct in the face of concurrency.
While the valid-invalid bit is our focus, two related bits in the PTE work closely with it: the Accessed bit (A) and the Dirty bit (D). These bits are primarily set by hardware and read by the OS.
The Accessed Bit (A):
The Dirty Bit (D):
| Present | Accessed | Dirty | Interpretation |
|---|---|---|---|
| 0 | N/A | N/A | Page not in memory - A and D bits not relevant |
| 1 | 0 | 0 | In memory, never accessed since bits cleared |
| 1 | 1 | 0 | In memory, read but not written |
| 1 | 1 | 1 | In memory, has been written to |
| 1 | 0 | 1 | Impossible (write implies access) |
Using These Bits for Page Replacement:
The OS uses the Accessed and Dirty bits to make intelligent eviction decisions:
Page Replacement Priority (lowest = evict first):
1. Present, Accessed=0, Dirty=0 → Ideal victim
- Not used recently, no write-back needed
2. Present, Accessed=0, Dirty=1 → Good victim
- Not used recently, but needs write-back
3. Present, Accessed=1, Dirty=0 → Poor choice
- Recently used, might need again soon
4. Present, Accessed=1, Dirty=1 → Worst victim
- Recently used AND needs write-back
The clock (second-chance) algorithm uses the Accessed bit:
- Scan pages; if Accessed=1, clear it and give another chance
- If Accessed=0, select as eviction victim
This mechanism allows the OS to approximate LRU behavior without expensive precise tracking of access times.
A key asymmetry: hardware automatically sets the A and D bits during normal memory access, but never clears them. The OS must periodically clear these bits as part of its page aging and replacement algorithms. This division of labor keeps normal memory access fast while giving the OS the information it needs.
The valid-invalid bit participates in several special scenarios that go beyond basic demand paging. Understanding these cases is important for advanced systems work.
1. Guard Pages:
Guard pages are intentionally left invalid to catch memory errors:
Stack layout with guard page:
┌───────────────────┐ High addresses
│ Stack │
│ (grows down) │ Present = 1
│ ↓ │
├───────────────────┤
│ GUARD PAGE │ Present = 0 (intentionally)
│ │ Any access = immediate fault
├───────────────────┤
│ Other data │
└───────────────────┘ Low addresses
If stack overflows into guard page → page fault
OS can either extend stack or signal stack overflow
2. Lazy Deallocation:
When the OS "frees" memory, it often just marks pages invalid without immediately reclaiming frames:
3. Page Table Entries for Page Tables:
In multi-level page tables, intermediate page table pages also have PTEs:
Recursive function calling itself, consuming stack spacePage fault on guard page access → SIGSEGV signal → process termination (or stack extension)Without guard pages:
With guard pages:
The guard page is simply a page with Present = 0 that the OS recognizes as a deliberate trap, not a demand-paging trigger.
4. Kernel vs. User Space:
The valid-invalid bit applies to kernel pages as well:
5. Hardware Walkers and Prefetch:
Modern processors speculatively walk page tables:
'Wired' or 'pinned' pages are marked with Present = 1 and cannot be evicted by the page replacement algorithm. These are used for DMA buffers, real-time processing, kernel critical sections, and other situations where page faults would be unacceptable. The mlockall() system call allows user-space processes to wire their pages.
The valid-invalid bit has significant performance implications that systems programmers must understand.
Cost of a Page Fault:
When Present = 0 and a fault occurs, the performance impact is dramatic:
| Operation | Typical Latency | Notes |
|---|---|---|
| Memory access (TLB hit) | ~1 ns | Best case |
| Memory access (TLB miss, page present) | ~10-20 ns | Page table walk |
| Minor page fault (page in RAM, just not mapped) | ~1-10 μs | No I/O needed |
| Major page fault (load from SSD) | ~50-200 μs | SSD random read |
| Major page fault (load from HDD) | ~5-15 ms | Mechanical seek + read |
A major page fault is 10,000 to 10,000,000 times slower than a TLB-hit memory access!
Implications for System Design:
1. Working Set Sizing:
2. Memory Access Patterns:
3. Prefetching:
madvise(MADV_WILLNEED) tells OS to preload pages4. Page Locking:
mlock() / mlockall() prevents evictionFor latency-sensitive applications (real-time systems, interactive UIs, game engines), the variance introduced by page faults is often more problematic than average performance. A system that's fast 99% of the time but freezes for 10ms on each page fault delivers a poor user experience. Understanding the valid-invalid bit helps you design systems that avoid these latency spikes.
We've explored the valid-invalid bit—the single bit that enables demand paging. Let's consolidate the essential points:
What's Next:
Now that we understand how the valid-invalid bit triggers page faults when pages are not present, we need to examine what happens next: page fault handling. The page fault handler is the OS component that responds to faults by loading pages, updating page tables, and resuming execution. It's one of the most performance-critical and complex components of any operating system kernel.
You now understand the valid-invalid bit—the hardware mechanism that enables demand paging. This single bit, by distinguishing between present and not-present pages, allows the OS to intercept memory accesses at exactly the right moments to create the illusion of more memory than physically exists.