CS 326 Lecture/Lab Summary – Spring 2025

Date: May 01, 2025, 02:51 PM Pacific Time (US and Canada)
Meeting ID: 813 3845 7711

Quick Recap

• The focus was on understanding how xv6 code works with page tables.
• The instructor examined the PT_print user-level program and its corresponding kernel system call implementation.
• Topics included:
  • Kernel memory initialization and management
  • The system call path and page table structure
  • The process of traversing a page table
  • The implementation of shared memory, including modifications to functions like Uvm copy, Uvm unmap, and Uvm free

Next Steps

• Instructor Tasks:
  • Post solutions for practice problems for Projects 2, 3, and 4 before next Thursday’s meeting.
  • Upload past lecture recordings (when available) and post updates on Campus Wire.
• Student Tasks:
  • Review the Campus Wire post regarding the guide and resources for learning the material.
  • Work on the practice problems for Projects 2, 3, and 4.
  • Revisit the conceptual overview of memory mapping and review the associated code from the lecture.
  • Engage with the material by discussing with peers (e.g., Roo), drawing diagrams, and creating scenarios for address translation using mock page tables.
  • Ask questions on Campus Wire if clarification is needed.

Detailed Summary

Analyzing xv6 Page Table Code

The instructor emphasized a detailed analysis of the xv6 page table code. The lecture focused on:

• Examining the output of the ptprint tool, which processes page table entries.
• Explaining that additional object files during compilation may result in multiple code pages appearing in the output.
• Discussing improvements and practice problem additions for upcoming projects.

Kernel Virtual Addresses and Guard Pages

The discussion covered the following points:

• Guard Pages:
  A guard page is mapped in memory but is configured without user-level permissions, so any access triggers a page fault.

• Kernel Virtual Addresses (KVA):
  In this system, kernel virtual addresses are directly associated with physical addresses. Even when virtual memory is enabled, both user mode and kernel mode use page tables to manage address translations.

Mermaid Diagram: Virtual Address to Physical Address Mapping

flowchart LR
    VA[Virtual Address]
    PT[Page Table Lookup]
    PA[Physical Address]
    GP[Guard Page : No User Perm]
    VA --> PT --> PA
    GP -.->|Access leads to| Fault[Page Fault]

Kernel Memory Initialization Process

The instructor explained how memory is initialized and managed in the kernel:

• During startup, free memory (from code and data segments) is placed onto the kernel free list.
• The first free page is placed at the highest address, with subsequent pages added at the front of the list.

Example: Kernel Memory Initialization in xv6

/* In xv6, the kinit function initializes the freelist for physical memory. */
void kinit(void) {
    initlock(&kmem.lock, "kmem");
    freerange((void*)KERNBASE, (void*)PHYSTOP);
}

ptprint System Call Path

The ptprint system call follows a specific path in the kernel:

• The system call gathers page table entries and creates an array of structures (pt_info) to hold details for printing.
• A temporary array is used to collect and populate the structures before printing.
• Understanding the complete system call path was stressed as essential for deep comprehension of page table traversal.

Page Table Structure and Mapping

Key points regarding page table structure included:

• Three-Level Hierarchy:
  xv6 page tables consist of three levels:
  • Top Level (Level 2): Always needed as the root.
  • L1 Level: Intermediate mapping level.
  • L0 Level: Maps virtual addresses to physical or kernel virtual addresses.
• Sparsity:
  The page table is sparse; not every entry is populated. The number of entries depends on the virtual address space in use.

Improving Virtual Address Mapping Code

The lecture also addressed code improvements:

• The code was modified to sort and print page table entries in reverse order—in line with high memory addresses appearing first.
• Emphasis was placed on enhancing the logic for mapping virtual addresses to their corresponding memory regions.

Page Table Traversal Process

The process of traversing a page table was explained as follows:

• Recursive Traversal:
  A recursive function (similar to a walk function) is used to traverse page tables from the highest level (Level 2) down to Level 0.

• Valid Bit:
  The valid bit in a page table entry is critical—it is set to one during the creation of a mapping.

• Hardware Analogy:
  The software walk function serves a similar role to the hardware’s breakdown of a virtual address into indices for each level.

Example: Page Table Walk Function in xv6

/* This function walks the page table to find the PTE responsible for a given virtual address. */
pte_t *walk(pagetable_t pagetable, uint64 va, int alloc) {
    if (va >= MAXVA)
        panic("walk");
    for (int level = 2; level > 0; level--) {
        pte_t *pte = &pagetable[PX(level, va)];
        if (*pte & PTE_V) {
            pagetable = (pagetable_t)PTE2PA(*pte);
        } else {
            if (!alloc)
                return 0;
            pagetable = (pagetable_t)kalloc();
            if (pagetable == 0)
                return 0;
            memset(pagetable, 0, PGSIZE);
            *pte = PA2PTE(pagetable) | PTE_V;
        }
    }
    return &pagetable[PX(0, va)];
}

Mermaid Diagram: Conceptual Page Table Traversal Process

flowchart TD
    A[Start at Root Page Table]
    B[Calculate Index for Level 2]
    C[Lookup Entry]
    D{Entry Valid?}
    E[Proceed to Next Level]
    F[Return Pointer to PTE]
    A --> B --> C --> D
    D -- Yes --> E
    D -- No --> F

Virtual and Physical Address Mapping

The lecture addressed the relationship between virtual and physical addresses:

• Multiple Virtual Mappings:
  Two virtual addresses may map to the same physical address. This is a foundation for shared memory.

• Helper Functions:
  Functions (such as PP and print) are used in the code to visualize and debug the mapping between virtual and physical addresses.

Mermaid Diagram: Shared Mapping in Parent and Child Processes

flowchart LR
    P[Parent's Virtual Address Space]
    C[Child's Virtual Address Space]
    SP[Shared Physical Page]
    P --> SP
    C --> SP

Memory Mapping in Parent-Child Processes

The instructor described how a parent and child process can share the same physical memory:

• Shared Memory Region:
  A shared memory region is mapped in both the parent’s and the child’s virtual address spaces, allowing both processes to read and write to the same physical page.

• Map Test Program:
  A test program (map test) demonstrates creating a shared memory region and performing read/write operations in both processes.

Shared Memory Implementation in the OS

Details regarding the shared memory implementation include:

• Shared Memory Structure:
  The OS represents a shared memory page with a structure that contains:
  • The physical address
  • A reference count
  • A lock for synchronization
  • An allocation status flag
• Mapping and Unmapping:
  • map Function: Allocates a physical page if needed, increments the reference count, and maps the shared region.
  • unmap Function: Decrements the reference count, frees the page if no longer referenced, and removes its mapping.
  • The fork system call was also modified to handle shared memory correctly so that the shared mapping persists without duplicating the page.

Conclusion

The lecture offered an in-depth analysis of how xv6 handles page tables, from basic structure and traversal to complex aspects like shared memory implementation. Students are encouraged to:

• Review the provided diagrams and code snippets.
• Engage with the material through discussions, drawing additional diagrams, and working on practice problems.
• Ask clarifying questions on Campus Wire as needed.

This structured overview should help in grasping the intricacies of virtual memory management and system calls in xv6.