Skip to content

Latest commit

 

History

History
448 lines (304 loc) · 19.5 KB

Concepts_Lab.md

File metadata and controls

448 lines (304 loc) · 19.5 KB

Week 3 Lab — Exploring xv6 Internals

Repository Guide | English | 한국어

Last Updated: 2026-11-19

Learning Objectives:

  1. Navigate the xv6 source code structure
  2. Trace the system call path from user space to kernel
  3. Explain the fields and purpose of struct proc
  4. Describe the internal steps of fork() in xv6

Table of Contents



1. Lab Overview

  • Objective: Explore the xv6 kernel source and trace how system calls work from start to finish.
graph LR
    L0["Lab 0<br/>Environment Setup"] --> L1["Lab 1<br/>Source Structure"]
    L1 --> L2["Lab 2<br/>System Call Tracing"]
    L2 --> L3["Lab 3<br/>struct proc"]
    L3 --> L4["Lab 4<br/>fork() Deep Dive"]
    style L0 fill:#e3f2fd
    style L2 fill:#fff3e0
    style L4 fill:#e8f5e9
Loading

Figure 1. Order of Lab 0-4



2. Lab 0: Environment Setup

If the xv6 build environment is already set up, skip to Section 3.

2.1 Prerequisites

Building xv6-riscv requires a RISC-V cross compiler and a QEMU emulator.

Definition: QEMU (Quick EMUlator) is a software emulator capable of running an entire OS built for a different CPU architecture. It allows running xv6 (built for RISC-V) on an x86/ARM laptop without actual RISC-V hardware.

macOS (Homebrew)

brew install qemu
brew install riscv64-elf-gcc

Ubuntu / Debian

sudo apt update
sudo apt install -y git build-essential \
  qemu-system-misc \
  gcc-riscv64-linux-gnu \
  binutils-riscv64-linux-gnu

Windows (WSL2)

# PowerShell (administrator):
wsl --install -d Ubuntu

After restarting, follow the Ubuntu installation instructions above in the WSL Ubuntu terminal.

Caution: In WSL2, work in ~/. /mnt/c/ is very slow.

Clone xv6 (common to all platforms):

git clone https://github.com/mit-pdos/xv6-riscv.git

[Computer Architecture] xv6 runs on the RISC-V architecture, where the transition from user mode (U-mode) to kernel mode (S-mode) is performed via the ecall instruction. Understanding this structure makes it much easier to follow the system call path later.

U-mode (User mode) is where normal programs run with restricted privileges; S-mode (Supervisor mode) is the privileged level where the kernel runs, and the CPU enforces strict rules about which operations each mode can perform.

2.2 Build Verification and Troubleshooting

Build and Run

cd xv6-riscv
make qemu

Expected output:

xv6 kernel is booting

hart 2 starting
hart 1 starting
init: starting sh
$

Try running ls, echo hello in the xv6 shell. Exit QEMU: Press Ctrl-A then X.

Common Issues

Problem Solution
riscv64 version of GCC not found Manually set TOOLPREFIX as shown below
QEMU version < 5.0 Upgrade QEMU
macOS linker error Use brew install riscv64-elf-gcc (not linux-gnu)
WSL2 "KVM not available" Harmless warning, so ignore it

Table 1. Common xv6 build problems and their solutions

TOOLPREFIX: when auto-detection fails, specify it as follows:

# Check installed tools:
ls /usr/bin/riscv64-*

# Set explicitly:
make TOOLPREFIX=riscv64-linux-gnu- qemu
# Or for macOS:
make TOOLPREFIX=riscv64-elf- qemu


3. Lab 1: Source Structure

File Role
proc.h struct proc definition
proc.c fork, exit, wait, scheduler
syscall.c System call dispatch table
sysproc.c System call handlers
trap.c Trap entry from user space
usys.pl User-space stub code generator

Table 2. Main xv6 kernel source files and their roles

A stub is a short piece of code that acts as a proxy for the actual implementation. Here, user-space stubs only put the system call number into a register and execute the ecall instruction when a user program calls fork(). In other words, the user writes fork() as if calling a regular function, but the stub actually mediates the entry into the kernel. The usys.pl script auto-generates these stubs.



4. Lab 2: System Call Tracing

4.1 System Call Path

The full path of fork() from user space to the kernel:

flowchart TD
    u["User program: fork()"] --> us["usys.S: li a7, SYS_fork → ecall"]
    us --> tr["trap.c: usertrap()<br/>Handles all user traps"]
    tr --> sc["syscall.c: syscall()<br/>Reads a7, looks up dispatch table"]
    sc --> sp["sysproc.c: sys_fork()<br/>Thin wrapper"]
    sp --> pc["proc.c: kfork()<br/>Performs the actual work"]
Loading

Figure 2. Path of the fork() system call from user space to the kernel implementation

The kernel-side implementation is named kfork() to distinguish it from the user-facing fork() system call. In the current xv6-riscv source, this function is defined as kfork() in proc.c; older versions named it fork().

Exercise: Add a printf to sys_fork(), rebuild, and verify that you found the correct location.

When the ecall instruction is executed, the hardware automatically performs the following: (1) saves the current PC to the sepc register, (2) switches the privilege mode to S-mode, (3) jumps to the trap handler address set in the stvec register. Understanding this flow makes the usertrap() → syscall() path clear.

[Computer Architecture] The RISC-V assembly instructions in Figure 2 are as follows:

  • li a7, SYS_fork: the Load Immediate instruction, which loads the constant SYS_fork (= 1) into register a7. a7 is the register used to convey the system call number.
  • ecall: the Environment Call instruction, which raises a trap signaling that there is a request for the kernel. The hardware automatically switches from user mode to kernel mode.

RISC-V register naming conventions: a0-a7 are for function arguments/return values, t0-t6 are temporaries, s0-s11 are saved registers (callee-saved), sp is the stack pointer, ra is the return address.

4.2 How to Run the Tracing Exercise

Step 1: Modify the kernel

Add a printf to sys_fork() in kernel/sysproc.c that prints a trace message each time it is called.

Step 2: Add the test program

Add a test program lab2_trace.c that calls fork() to the xv6 user/ directory.

Step 3: Modify the Makefile

Open xv6-riscv/Makefile, find the UPROGS list, and add the following:

UPROGS=\
  ...
  $U/_lab2_trace\

Step 4: Build and run

make clean && make qemu

At the xv6 shell prompt:

$ lab2_trace

You should see [TRACE] sys_fork() called by ... output from the kernel.

Exit QEMU: Press Ctrl-A then X.



5. Lab 3: struct proc Analysis

5.1 Process State Machine

The Process State Machine is defined in kernel/proc.h:

stateDiagram-v2
    UNUSED --> USED : allocproc()
    USED --> RUNNABLE : fork()/userinit()
    RUNNABLE --> RUNNING : scheduler
    RUNNING --> RUNNABLE : yield()/interrupt
    RUNNING --> SLEEPING : sleep()
    SLEEPING --> RUNNABLE : wakeup()
    RUNNING --> ZOMBIE : exit()
    ZOMBIE --> UNUSED : wait() reaps
Loading

Figure 3. The xv6 process state machine

Key fields: state, pid, pagetable, trapframe, context, ofile[], parent

  • Exercise: Which fields change at each state transition?

enum procstate is a C enumeration that represents each state as an integer constant. State machines are a design pattern used not only in operating systems but in protocols, game logic, and many other fields.

5.2 Full Definition of struct proc

struct proc {
  struct spinlock lock;
  enum procstate state;        // UNUSED → USED → RUNNABLE → RUNNING → ZOMBIE
  void *chan;                  // Sleep channel (when in SLEEPING state)
  int killed;                  // Pending kill signal
  int xstate;                  // Exit status to pass to parent
  int pid;                     // Process ID

  struct proc *parent;         // Parent process (protected by wait_lock)

  uint64 kstack;               // Kernel stack virtual address
  uint64 sz;                   // Process memory size (bytes)
  pagetable_t pagetable;       // User page table (see note below)
  struct trapframe *trapframe; // Saved user registers (used by trampoline.S)
  struct context context;      // Saved kernel registers (used by swtch.S)
  struct file *ofile[NOFILE];  // Open file descriptors
  struct inode *cwd;           // Current working directory
  char name[16];               // Process name (for debugging)
};

[Computer Programming] A C structure (struct) is a user-defined type that groups fields of different types, and struct proc is the structure representing a single process. Each field covers a different aspect of the process (scheduling state, memory layout, open files, etc.). In the Linux kernel, the corresponding task_struct has hundreds of fields, highlighting the simplicity of xv6 for learning purposes.

The fields of struct proc fall into three broad groups by what they do. The first group, from lock to parent, holds management information that the scheduler and wait() consult, such as the state, the identifier, and the parent relationship.

struct spinlock lock is the spinlock for this process structure. A spinlock is the simplest synchronization tool that prevents other CPU cores from simultaneously modifying the same struct proc. It is called a spinlock because a core trying to acquire it spins in a while (lock == held) loop. Since xv6 supports multi-core, this lock must be acquired before changing the process state. Details on spinlocks and synchronization are covered in Week 9.

A sleep channel is an arbitrary address value that identifies what a process is waiting for while sleeping. For example, if a process sleeps while waiting for data on a pipe, the address of that pipe structure is stored in chan. Later, when data arrives, wakeup(chan) is called to wake all processes sleeping on that address. This mechanism avoids busy waiting and uses the CPU efficiently. The behavior of sleep()/wakeup() is traced in the Week 6 lab.

The second group, from kstack to context, holds the memory and register state of the process. Two fields save registers: trapframe and context.

context saves callee-saved kernel registers used when the scheduler switches between processes inside the kernel (via swtch.S), while trapframe saves the full user-mode register state when entering the kernel from user space. They serve different switches: kernel↔kernel vs. user↔kernel.

trapframe is a structure for preserving user register values when transitioning from user mode to kernel mode. It is the core mechanism that allows a user program to resume exactly where it left off after a system call completes. The representative registers saved in the trapframe are listed in Section 6.

pagetable_t in xv6 is a typedef for a pointer to the root of a process's page table; it maps virtual addresses to physical memory. Its definition is typedef uint64 *pagetable_t; in kernel/riscv.h.

The third group, ofile[] and cwd, points to file system resources such as the files the process has opened and its current working directory. The last field, name, is used only for debugging.

ofile[] holds kernel-side file objects. The file descriptor number that user programs use (e.g., fd = 3) is simply the index into this array.

Definition: An inode is the kernel's internal descriptor for a file or directory, storing metadata like size, permissions, and disk location.



6. Lab 4: Deep Dive into fork() Implementation

  1. allocproc()         ── Secure new process slot, pid, kstack*, trapframe
         │
  2. uvmcopy()           ── Copy parent's page table + memory
         │
  3. Copy trapframe      ── Child also returns from fork()
         │
  4. Set a0 = 0          ── Child's fork() return value is 0
         │
  5. Copy ofile[]        ── Share open file descriptors
         │
  6. Set parent,         ── Child becomes runnable
     state = RUNNABLE
         │
  7. Return child PID    ── To the parent

Figure 4. Steps of the xv6 fork() implementation

The kernel stack (kstack) is a private stack region in kernel memory used when this process executes inside the kernel (e.g., during a system call). It is completely separate from the user stack to prevent user code from tampering with kernel execution. In xv6, kernel stacks are allocated and mapped for every process slot at boot, and allocproc() does not allocate a new kernel stack but uses the one attached to the slot (the kstack* in Figure 4).

Discussion questions:

  • Why does the child process need its own copy of the trapframe?

    Hint

    Think about what happens when parent and child execute different instructions after fork() returns: they need independent register state.

  • What happens if step 4 (a0 = 0) is skipped?

    Hint

    Consider what value the child's a0 register would hold. The child's trapframe is a copy of the parent's, so a0 keeps the value the parent had when it executed ecall; if that value is nonzero, the child would wrongly think it is the parent.

  • Why does uvmcopy copy all pages? (Hint: COW fork in Week 12)

    Hint

    xv6 takes the simple approach. Real OSes like Linux defer copying until a write occurs (Copy-On-Write).

Breaking down the internal operation of uvmcopy() step by step:

  1. Walk the parent's page table to find all mapped user pages.
  2. For each page, allocate a new physical memory frame with kalloc().
  3. Copy the contents of the parent's page to the new frame byte by byte (memmove).
  4. Map the new frame to the same virtual address in the child's page table.

This process becomes more expensive as the process memory grows. In the function name, u stands for user, vm for virtual memory, and copy for copy; as the name suggests, it is a function that copies user virtual memory.

Note: Having uvmcopy() copy all pages is highly inefficient. In real Linux, the COW (Copy-On-Write) technique is used: at fork time, only page table entries are copied, and actual physical pages are copied only when a write is attempted. This optimization is covered in Week 12.

Steps 3 and 4 deal with the trapframe. The child receives an exact copy of the parent's trapframe, so it resumes execution at the point where the parent called fork(), and only the register that holds the return value is changed to 0.

Representative registers saved in the trapframe are as follows:

  • epc: program counter at the time of the trap (the address to return to)
  • a0-a7: function arguments / system call arguments / return values
  • sp: user stack pointer
  • s0-s11: callee-saved registers (values that must be preserved per calling convention)

Setting trapframe->a0 = 0 in fork() ensures that when the child returns from kernel to user mode, it reads 0 from a0 (the return value register), allowing it to recognize that it is the child. Because a0 is the RISC-V register that conveys function return values, the parent's a0 holds the child PID while the child's a0 holds 0, which is what lets identical code return different values in two processes.

  What this lab explored:

  Source structure ──▶ System call path ──▶ struct proc lifecycle ──▶ fork() implementation

Figure 5. Flow of the topics explored in this lab



Summary

Concept Key Summary
xv6 xv6 is an educational OS of about 10,000 lines of C code, small enough to read in its entirety.
Key kernel files The key files are proc.h/c (processes), syscall.c (dispatch), sysproc.c (handlers), and trap.c (trap entry).
System call path A call proceeds as user → ecall → usertrap() → syscall() → handler → implementation.
struct proc It is the kernel's complete view of a process (scheduling state, memory, files).
Process states The basic lifecycle is UNUSED → USED → RUNNABLE → RUNNING → ZOMBIE → UNUSED.
fork() It proceeds as allocproc → uvmcopy → copy trapframe → a0=0 → copy files → RUNNABLE.
fork() return value The parent receives the child PID and the child receives 0, implemented via trapframe->a0 manipulation.
COW fork xv6 copies all pages, but Linux optimizes with COW (Week 12).


Self-Check Questions

  1. System call path: List the 6 files (in order) that a fork() call passes through, from the user program to the kernel implementation. Which file performs the actual process creation work?

    Answer

    ① The user program (e.g., user/sh.c, user-side call) → ② user/usys.S (syscall trap stub) → ③ kernel/trap.c (usertrap()) → ④ kernel/syscall.c (dispatcher) → ⑤ kernel/sysproc.c (sys_fork()) → ⑥ kernel/proc.c (kfork() implementation). Right after ecall, uservec in kernel/trampoline.S saves the registers to the trapframe and jumps to usertrap(), and kfork() copies the page table with uvmcopy() in kernel/vm.c. The actual process-creation work is done in kernel/proc.c's kfork().

  2. struct proc fields: Which field in struct proc allows the child process to resume execution at the correct point after fork() returns? Why is this field separate from context?

    Answer

    It is the trapframe field. It stores the complete user-register state (PC, sp, a0..a7, etc.) captured at the moment of the syscall, so the child resumes at the instruction after fork(). context is different: it holds the callee-saved registers used by swtch() between the kernel-side scheduler thread and the process's kernel thread. The two serve distinct transitions (user↔kernel vs kernel↔kernel) and must be stored separately.

  3. Process states: A process in RUNNING state calls sleep(). Describe the state transitions that occur and which fields of struct proc change.

    Answer

    RUNNING → SLEEPING. The updated fields are state = SLEEPING and chan = <wait channel> (used to match wakeup()). After updating, the process calls sched() to hand control back to the scheduler.