Table of Contents

  1. Introduction
  2. Memory Organization in xv6
  3. Trap Handling in xv6
  4. Page Tables and Address Translation
  5. Memory Allocation in xv6
  6. Putting It All Together: A Complete Trap Handling Example
  7. Conclusion

Introduction

The xv6 operating system, a reimplementation of Unix V6 for educational purposes, provides an excellent platform for understanding the intricate workings of modern operating systems. In this comprehensive guide, we’ll dive deep into the memory layout and trap handling mechanisms of xv6, exploring how it manages the transition between user and kernel modes, handles interrupts, and organizes its virtual and physical memory spaces.

Memory Organization in xv6

image

Physical Memory Layout

xv6 is designed to run on RISC-V architecture with a specific physical memory layout. Let’s break it down:

  1. Low Memory (0x0 - 0x80000000)
    • Memory-mapped I/O devices
    • Boot ROM
    • CLINT (Core Local Interruptor)
    • PLIC (Platform-Level Interrupt Controller)
  2. Kernel Memory (0x80000000 - 0x88000000)
    • Kernel code and data
    • 128 MB of RAM
  3. User Memory (0x88000000 - 0xFFFFFFFF)
    • Available for user processes

Let’s look at a C representation of some key memory addresses:

#define UART0 0x10000000L
#define VIRTIO0 0x10001000
#define CLINT 0x2000000L
#define PLIC 0x0c000000L
#define KERNBASE 0x80000000L
#define PHYSTOP (KERNBASE + 128*1024*1024)

These definitions help the kernel interact with hardware devices and manage memory allocation.

Virtual Memory Layout

xv6 uses paging to create separate virtual address spaces for the kernel and each user process. The virtual memory layout is crucial for understanding how xv6 manages memory and handles transitions between user and kernel mode.

  1. Kernel Virtual Memory
    • Direct-mapped physical memory
    • Trampoline page
    • Kernel stacks
  2. User Virtual Memory
    • User code and data
    • User stack
    • Heap (grows upwards)
    • Trampoline page (shared with kernel)
    • Trap frame

Here’s a simplified representation of the user virtual memory layout in C:

#define MAXVA (1L << (9 + 9 + 9 + 12 - 1))
#define TRAMPOLINE (MAXVA - PGSIZE)
#define TRAPFRAME (TRAMPOLINE - PGSIZE)

struct proc {
  // ... other fields ...
  uint64 sz;                // Size of process memory (bytes)
  pagetable_t pagetable;    // User page table
  struct trapframe *trapframe; // data page for trampoline.S
  // ... other fields ...
};

This structure represents a process in xv6, including its size, page table, and trap frame.

Trap Handling in xv6

Trap handling is a critical aspect of any operating system. It allows the system to handle exceptions, system calls, and interrupts. In xv6, the trap handling mechanism is intricately designed to ensure smooth transitions between user and kernel modes.

The Trap Sequence

  1. User code execution: The process runs in user mode.
  2. Trap occurrence: An exception, system call, or interrupt occurs.
  3. Hardware response: The RISC-V hardware switches to supervisor mode and jumps to a predefined address.
  4. Trampoline code: Assembly code in the trampoline page saves user registers and switches to the kernel page table.
  5. C trap handler: The kernel’s C code handles the trap.
  6. Return preparation: The kernel prepares to return to user mode.
  7. Trampoline code (return): Assembly code restores user registers and switches back to the user page table.
  8. User code resumes: The process continues execution in user mode.

Let’s dive into some of the key components of this sequence.

The Trampoline Page

The trampoline page is a crucial part of xv6’s trap handling mechanism. It contains assembly code that’s mapped at the same virtual address in both user and kernel space, allowing for a smooth transition between the two.

Here’s a simplified version of the trampoline code in RISC-V assembly:

.globl trampoline
trampoline:
.align 4
.globl uservec
uservec:    
    # save user registers
    csrw sscratch, a0
    la a0, TRAPFRAME
    sd ra, 40(a0)
    sd sp, 48(a0)
    # ... save other registers ...

    # switch to kernel page table
    csrr t0, sscratch
    ld t1, 16(t0)
    csrw satp, t1
    sfence.vma zero, zero

    # jump to usertrap()
    ld t0, 8(a0)
    jr t0

.globl userret
userret:
    # switch to user page table
    csrw satp, a1
    sfence.vma zero, zero

    # restore user registers
    ld ra, 40(a0)
    ld sp, 48(a0)
    # ... restore other registers ...

    # return to user mode
    sret

This code handles the critical transition between user and kernel mode, saving and restoring registers as necessary.

The Trap Frame

The trap frame is a data structure that stores the state of a user process when a trap occurs. It’s allocated in the kernel for each process and is accessible through the process structure. Here’s a simplified version of the trap frame structure in C:

struct trapframe {
  /*   0 */ uint64 kernel_satp;   // kernel page table
  /*   8 */ uint64 kernel_sp;     // top of process's kernel stack
  /*  16 */ uint64 kernel_trap;   // usertrap()
  /*  24 */ uint64 epc;           // saved user program counter
  /*  32 */ uint64 kernel_hartid; // saved kernel tp
  /*  40 */ uint64 ra;
  /*  48 */ uint64 sp;
  /*  56 */ uint64 gp;
  /*  64 */ uint64 tp;
  /*  72 */ uint64 t0;
  // ... other registers ...
};

This structure allows the kernel to save and restore the complete state of a user process during trap handling.

Page Tables and Address Translation

xv6 uses a three-level page table structure for address translation. Each process has its own page table, and the kernel has a separate page table. Let’s explore how xv6 manages these page tables.

Page Table Structure

A page table in xv6 is a tree of physical pages. Each page contains 512 64-bit PTEs (Page Table Entries). Here’s a simplified representation of a PTE in C:

typedef uint64 pte_t;
typedef uint64 *pagetable_t; // 512 PTEs

#define PGSHIFT 12  // bits of offset within a page
#define PGSIZE (1 << PGSHIFT)  // bytes per page
#define PGROUNDUP(sz)  (((sz)+PGSIZE-1) & ~(PGSIZE-1))
#define PGROUNDDOWN(a) (((a)) & ~(PGSIZE-1))

// extract the three 9-bit page table indices from a virtual address
#define PXMASK          0x1FF // 9 bits
#define PXSHIFT(level)  (PGSHIFT+(9*(level)))
#define PX(level, va) ((((uint64) (va)) >> PXSHIFT(level)) & PXMASK)

// shift a physical address to the right place for a PTE
#define PA2PTE(pa) ((((uint64)pa) >> 12) << 10)
#define PTE2PA(pte) (((pte) >> 10) << 12)
#define PTE_FLAGS(pte) ((pte) & 0x3FF)

These macros and definitions help xv6 manage page tables and perform address translation.

Address Translation Process

When a virtual address needs to be translated to a physical address, xv6 follows these steps:

  1. Extract the indices for each level of the page table from the virtual address.
  2. Walk the page table using these indices.
  3. If a valid PTE is found at the leaf level, combine the physical page number from the PTE with the offset from the virtual address.

Here’s a simplified version of the page table walk in C:

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 || (pagetable = (pde_t*)kalloc()) == 0)
        return 0;
      memset(pagetable, 0, PGSIZE);
      *pte = PA2PTE(pagetable) | PTE_V;
    }
  }
  return &pagetable[PX(0, va)];
}

This function walks the page table for a given virtual address, allocating new page table pages if necessary.

Memory Allocation in xv6

xv6 uses a simple but effective memory allocation system. The kernel maintains a list of free physical pages and allocates them as needed.

The Kernel Allocator

The kernel allocator manages physical memory pages. Here’s a simplified version of the key structures and functions:

struct run {
  struct run *next;
};

struct {
  struct spinlock lock;
  struct run *freelist;
} kmem;

void*
kalloc(void)
{
  struct run *r;

  acquire(&kmem.lock);
  r = kmem.freelist;
  if(r)
    kmem.freelist = r->next;
  release(&kmem.lock);

  if(r)
    memset((char*)r, 5, PGSIZE); // fill with junk
  return (void*)r;
}

void
kfree(void *pa)
{
  struct run *r;

  if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
    panic("kfree");

  // Fill with junk to catch dangling refs.
  memset(pa, 1, PGSIZE);

  r = (struct run*)pa;

  acquire(&kmem.lock);
  r->next = kmem.freelist;
  kmem.freelist = r;
  release(&kmem.lock);
}

These functions handle the allocation and freeing of physical pages in the kernel.

Putting It All Together: A Complete Trap Handling Example

Let’s walk through a complete example of how xv6 handles a system call, from user space to kernel and back.

  1. User Space: A user program calls a system call using the ecall instruction.
.global fork
fork:
 li a7, SYS_fork
 ecall
 ret

  1. Trap Handling: The ecall instruction triggers a trap. The hardware switches to supervisor mode and jumps to the trampoline page.

  2. Trampoline: The uservec function in the trampoline saves user registers and switches to the kernel page table.

  3. C Trap Handler: Control is transferred to the usertrap function in C.

void
usertrap(void)
{
  int which_dev = 0;

  if((r_sstatus() & SSTATUS_SPP) != 0)
    panic("usertrap: not from user mode");

  // send interrupts and exceptions to kerneltrap(),
  // since we're now in the kernel.
  w_stvec((uint64)kernelvec);

  struct proc *p = myproc();
  
  // save user program counter.
  p->trapframe->epc = r_sepc();
  
  if(r_scause() == 8){
    // system call

    if(p->killed)
      exit(-1);

    // sepc points to the ecall instruction,
    // but we want to return to the next instruction.
    p->trapframe->epc += 4;

    // an interrupt will change sstatus &c registers,
    // so don't enable until done with those registers.
    intr_on();

    syscall();
  } else if((which_dev = devintr()) != 0){
    // ok
  } else {
    printf("usertrap(): unexpected scause %p pid=%d\n", r_scause(), p->pid);
    printf("            sepc=%p stval=%p\n", r_sepc(), r_stval());
    p->killed = 1;
  }

  if(p->killed)
    exit(-1);

  // give up the CPU if this is a timer interrupt.
  if(which_dev == 2)
    yield();

  usertrapret();
}

  1. System Call Handling: The syscall function identifies and executes the requested system call.

  2. Return Preparation: The usertrapret function prepares for the return to user space.

  3. Trampoline (Return): The userret function in the trampoline restores user registers and switches back to the user page table.

  4. User Space: Control returns to the user program, which continues execution.

Conclusion

xv6’s memory layout and trap handling mechanisms demonstrate the intricate dance between hardware and software in modern operating systems. By carefully managing virtual and physical memory, and providing a robust trap handling system, xv6 ensures safe and efficient execution of user programs while maintaining the integrity of the kernel.

Understanding these concepts is crucial for anyone looking to delve deeper into operating system design and implementation. The xv6 operating system provides an excellent educational platform for exploring these concepts in a relatively simple yet realistic environment.