Build, link and boot · xv6, line by line

1warm-upChoose one

Every hart runs these lines of _entry at the same time. Why does the stack pointer use hartid + 1 instead of hartid?

kernel/entry.S

7_entry:
      # set up a stack for C.
      # stack0 is declared in start.c,
      # with a 4096-byte stack per CPU.
      # sp = stack0 + ((hartid + 1) * 4096)
      la sp, stack0
      li a0, 1024*4
      csrr a1, mhartid
      addi a1, a1, 1
      mul a0, a0, a1
      add sp, sp, a0
      # jump to start() in start.c
      call start
20spin:
      j spin

Stacks grow down, so sp must start at the top (the end) of the hart’s 4096-byte slice of stack0.Hart IDs start at 1 on QEMU, so the + 1 turns them into array indexes.Slice 0 is reserved for the scheduler, so every hart skips it.It leaves an unused 4096-byte guard area between consecutive harts’ stacks.

2warm-upType a number

In this build, stack0 is at 0x80007890. What value does sp hold on hart 2 right after line 17 (add sp, sp, a0)? Answer in hex.

kernel/entry.S

7_entry:
      # set up a stack for C.
      # stack0 is declared in start.c,
      # with a 4096-byte stack per CPU.
      # sp = stack0 + ((hartid + 1) * 4096)
      la sp, stack0
      li a0, 1024*4
      csrr a1, mhartid
      addi a1, a1, 1
      mul a0, a0, a1
      add sp, sp, a0
      # jump to start() in start.c
      call start
20spin:
      j spin

decimal, 0x hex or 0b binary

3warm-upChoose one

Every kernel file is compiled with $(CC), the RISC-V cross-compiler / toolchain. Why is mkfs compiled with plain gcc on line 124?

Makefile

123mkfs/mkfs: mkfs/mkfs.c $K/fs.h $K/param.h

124 gcc -Wno-unknown-attributes -I. -o mkfs/mkfs mkfs/mkfs.c

mkfs runs on your own computer during the build, to write fs.img, so it must be native code for that computer.mkfs needs the host’s C library for printf, and the cross-compiler has no C library at all.Plain gcc is a shortcut; $(CC) would work just as well because both produce the same code.mkfs runs inside xv6 at boot to format the disk, and plain gcc is enough because QEMU translates it.

4warm-upMatch the pairs

Match each build input with its job.

kernel/kernel.lduser/user.ldmkfs/mkfsuser/usys.plthe -MD flag

5warm-upTrue or false, and why

True or false: when hart 0 calls kvminithart on line 21 of main, paging is turned on for all three harts.

kernel/main.c

  kinit();            // physical page allocator
  kvminit();          // create kernel page table
  kvminithart();      // turn on paging
  procinit();         // process table
  trapinit();         // trap vectors
  trapinithart();     // install kernel trap vector

TrueFalse

Why?

Harts 1 and 2 get paging automatically when they see started become 1.satp is a per-hart CSR. Harts 1 and 2 keep running with paging off until each calls kvminithart itself, on line 39.The kernel page table does not exist yet when line 21 runs, so nothing is turned on until line 33.

6warm-upChoose one

userinit creates process 1 with no user memory at all (p->sz stays 0). How does process 1 get the code of /init?

kernel/proc.c

216
217// Set up first user process.
218void
219userinit(void)
220{
221  struct proc *p;
222
223  p = allocproc();
224  initproc = p;
225
226  p->cwd = namei("/");
227
228  p->state = RUNNABLE;
229
230  release(&p->lock);
231}

userinit copies a small hand-assembled program, initcode, into the process’s first page.QEMU loads /init into memory together with the kernel, and userinit maps it.main calls kexec("/init") right after userinit().forkret calls kexec("/init", ...) inside the kernel, the first time it runs, before process 1 ever reaches user mode.

7warm-upChoose all that apply

While hart 0 runs the if branch of main (lines 14–33), what are harts 1 and 2 doing? Choose all that apply.

kernel/main.c

9// start() jumps here in supervisor mode on all CPUs.
10void
11main()
12{
if (cpuid() == 0) {
  consoleinit();
  printkinit();
  printk("\n");
  printk("xv6 kernel is booting\n");
  printk("\n");
  kinit();            // physical page allocator
  kvminit();          // create kernel page table
  kvminithart();      // turn on paging
  procinit();         // process table
  trapinit();         // trap vectors
  trapinithart();     // install kernel trap vector
  plicinit();         // set up interrupt controller
  plicinithart();     // ask PLIC for device interrupts
  binit();            // buffer cache
  iinit();            // inode table
  fileinit();         // file table
  virtio_disk_init(); // emulated hard disk
  userinit();         // first user process
32
  __atomic_store_n(&started, 1, __ATOMIC_RELEASE);
} else {
  while (__atomic_load_n(&started, __ATOMIC_ACQUIRE) == 0)
    ;
37
  printk("hart %d starting\n", cpuid());
  kvminithart();  // turn on paging
  trapinithart(); // install kernel trap vector
  plicinithart(); // ask PLIC for device interrupts
}
43
scheduler();
45}

Loading started over and over with an acquire loadRunning with paging offExecuting wfi until hart 0 sends them an interruptRunning with interrupts offSpinning in acquire on a lock that hart 0 holds until it finishesSleeping on a channel until hart 0 calls wakeup

8warm-upChoose one

binit and iinit run in main, but fsinit, which reads the superblock from the disk, does not. Why must it wait until the first process runs?

kernel/proc.c

// Still holding p->lock from scheduler.
release(&p->lock);
521
if (first) {
  first = 0;
524
  // File system initialization must be run in the context of a
  // regular process (e.g., because it calls sleep), and thus cannot
  // be run from main().
  fsinit(ROOTDEV);
529
  // We can invoke kexec() now that file system is initialized.
  // Put the return value (argc) of kexec into a0.
  p->trapframe->a0 = kexec("/init", (char *[]){"/init", 0});
  if (p->trapframe->a0 == -1) {
    panic("exec");
  }
}

Reading a disk block means sleeping until the disk interrupt, and only a process can sleep; main runs with no process.The disk driver is initialized only after main finishes.The buffer cache is not ready until the scheduler starts.Only user-mode code is allowed to read the disk.

9solidClick the line

kvmmake maps everything below etext read+execute and everything above it read+write, page by page, so etext must be a multiple of 0x1000. Click the line that makes it so.

kernel/kernel.ld

.text : {
  kernel/entry.o(_entry)
  *(.text .text.*)
  . = ALIGN(0x1000);
  _trampoline = .;
  *(trampsec)
  . = ALIGN(0x1000);
  ASSERT(. - _trampoline == 0x1000, "error: trampoline larger than one page");
  PROVIDE(etext = .);
}

Your pick: none yet (click a line in the code)

10solidPut in order

Put these events on hart 0 in the order they happen, from power-on to the first moment it can take an interrupt.

mret drops the hart to supervisor mode at main
QEMU’s boot ROM at 0x1000 jumps to 0x80000000
_entry points sp at the top of hart 0’s slice of stack0
kvminithart writes satp: paging on
started is set to 1 with a release store
start sets mstatus.MPP to S and mepc to main
the scheduler’s first intr_on()
trapinithart sets stvec to kernelvec

11solidChoose all that apply

Which of these functions does hart 1 call during boot? Choose all that apply.

kernel/main.c

9// start() jumps here in supervisor mode on all CPUs.
10void
11main()
12{
if (cpuid() == 0) {
  consoleinit();
  printkinit();
  printk("\n");
  printk("xv6 kernel is booting\n");
  printk("\n");
  kinit();            // physical page allocator
  kvminit();          // create kernel page table
  kvminithart();      // turn on paging
  procinit();         // process table
  trapinit();         // trap vectors
  trapinithart();     // install kernel trap vector
  plicinit();         // set up interrupt controller
  plicinithart();     // ask PLIC for device interrupts
  binit();            // buffer cache
  iinit();            // inode table
  fileinit();         // file table
  virtio_disk_init(); // emulated hard disk
  userinit();         // first user process
32
  __atomic_store_n(&started, 1, __ATOMIC_RELEASE);
} else {
  while (__atomic_load_n(&started, __ATOMIC_ACQUIRE) == 0)
    ;
37
  printk("hart %d starting\n", cpuid());
  kvminithart();  // turn on paging
  trapinithart(); // install kernel trap vector
  plicinithart(); // ask PLIC for device interrupts
}
43
scheduler();
45}

12solidFill in the machine state

Hart 1 is spinning on line 35 of main, waiting for started. Hart 0 is somewhere in kinit. Fill in hart 1’s state.

kernel/main.c

} else {
  while (__atomic_load_n(&started, __ATOMIC_ACQUIRE) == 0)
    ;
37
  printk("hart %d starting\n", cpuid());
  kvminithart();  // turn on paging
  trapinithart(); // install kernel trap vector
  plicinithart(); // ask PLIC for device interrupts

Privilege modeActive stackPage table (satp)Interrupts (sstatus.SIE)noff

13solidChoose one

The kernel’s .bss section is 0x19350 bytes and holds proc, stack0, cpus and the other zero-initialized globals. The C code assumes they start as zero. Who zeroes them?

Nothing in xv6. The ELF program header asks for more memory (0x20bb0) than the file provides (0x7860), and QEMU provides that extra memory as zeros.start calls memset on it before mret.kinit clears it as part of setting up memory._entry runs a loop that clears .bss before calling start.

14solidChoose all that apply

Which of these live in the kernel’s .bss section (0x80007860–0x80020bb0 in this build)? Choose all that apply.

the process table proc[]stack0, the boot stacksstarted in main.c (volatile static int started = 0;)the string "xv6 kernel is booting\n"the static int first = 1; flag in forkretthe root page of the kernel page table that satp points to

15solidType a number

How many metadata blocks (nmeta) does mkfs compute? In this tree FSSIZE = 2000, BSIZE = 1024, LOGBLOCKS = 30, sizeof(struct dinode) = 64 (so IPB = 16) and BPB = 1024 × 8 = 8192.

mkfs/mkfs.c

23#define NINODES 200
24
25// Disk layout:
26// [ boot block | sb block | log | inode blocks | free bit map | data blocks ]
27
28int nbitmap = FSSIZE / BPB + 1;
29int ninodeblocks = NINODES / IPB + 1;
30int nlog = LOGBLOCKS + 1; // Header followed by LOGBLOCKS data blocks.
31int nmeta;   // Number of meta blocks (boot, sb, nlog, inode, bitmap)
32int nblocks; // Number of data blocks

decimal, 0x hex or 0b binary

16solidChoose one

The comment on line 24 says writing main’s address into mepc “requires gcc -mcmodel=medany”. Why?

kernel/start.c

// set M Exception Program Counter to main, for mret.
// requires gcc -mcmodel=medany
w_mepc((uint64)main);

medany enables the compressed instructions that keep start short.medany is what allows 64-bit CSR writes like csrw mepc.The default code model can only form addresses within 2 GiB of address 0, and the kernel lives at 0x80000000 and above; medany builds addresses relative to the pc instead.medany makes the kernel position-independent, so QEMU can load it at any address.

17solidType a number

make runs mkfs/mkfs fs.img README $(UPROGS). mkfs gives the root directory the first inode, then one inode to each file in command-line order. What is the inode number of /init?

Makefile

132UPROGS=\
$U/_cat\
$U/_echo\
$U/_forktest\
$U/_grep\
$U/_init\
$U/_kill\
$U/_ln\
$U/_ls\
$U/_mkdir\
$U/_rm\
$U/_sh\
$U/_stressfs\
$U/_usertests\
$U/_grind\
$U/_wc\
$U/_zombie\
$U/_logstress\
$U/_forphan\
$U/_dorphan\
$U/_sync\
153
154fs.img: mkfs/mkfs README $(UPROGS)
mkfs/mkfs fs.img README $(UPROGS)

decimal, 0x hex or 0b binary

18solidTrue or false, and why

True or false: right after kvminithart turns on paging, hart 0’s sp (still in its slice of stack0) points at usable memory, with no change to sp.

kernel/vm.c

// map kernel text executable and read-only.
kvmmap(kpgtbl, KERNBASE, KERNBASE, (uint64)etext - KERNBASE, PTE_R | PTE_X);
40
// map kernel data and the physical RAM we'll make use of.
kvmmap(kpgtbl, (uint64)etext, (uint64)etext, PHYSTOP - (uint64)etext,
       PTE_R | PTE_W);

TrueFalse

Why?

kvmmake maps the kernel’s data and the rest of RAM at virtual addresses equal to their physical addresses, read+write, and stack0 is in .bss, inside that range.sp is never translated by the page table, only instruction fetches are.The hart keeps using physical addresses until it returns to user mode.

19solidChoose one

To leave for user mode the first time, forkret calls userret through the address TRAMPOLINE + (userret - trampoline) (0x3ffffff09c), not at its link address 0x8000609c. Why?

kernel/proc.c

// return to user space, mimicing usertrap()'s return.
prepare_return();
uint64 satp = MAKE_SATP(p->pagetable);
uint64 trampoline_userret = TRAMPOLINE + (userret - trampoline);
((void (*)(uint64))trampoline_userret)(satp);

User mode can only execute code at high addresses, and userret runs in user mode.It is only an optimization to avoid a long jump; either address would work.The kernel page table does not map 0x8000609c, so the link address cannot be used at all.userret switches to the user page table, which does not map 0x8000609c; the TRAMPOLINE alias is mapped in both page tables, so the next instruction can still be fetched.

20deepType a number

In this build end is 0x80020bb0 and PHYSTOP is 0x88000000. How many pages does kinit hand to the page allocator?

kernel/kalloc.c

26void
27kinit()
28{
29  initlock(&kmem.lock, "kmem");
30  freerange(end, (void *)PHYSTOP);
31}
32
33void
34freerange(void *pa_start, void *pa_end)
35{
36  char *p;
37  p = (char *)PGROUNDUP((uint64)pa_start);
38  for (; p + PGSIZE <= (char *)pa_end; p += PGSIZE)
39    kfree(p);
40}

decimal, 0x hex or 0b binary

21deepChoose one

You delete line 15 of kernel/kernel.ld (the ALIGN(0x1000) before _trampoline = .) and run make. In this build the ordinary kernel code ends at 0x80005bc0 and the trampoline code is 0x124 bytes long. What happens?

kernel/kernel.ld

.text : {
  kernel/entry.o(_entry)
  *(.text .text.*)
  . = ALIGN(0x1000);
  _trampoline = .;
  *(trampsec)
  . = ALIGN(0x1000);
  ASSERT(. - _trampoline == 0x1000, "error: trampoline larger than one page");
  PROVIDE(etext = .);
}

The link fails at the ASSERT: _trampoline is now 0x80005bc0, line 18 still pads to 0x80006000, so . - _trampoline is 0x440, not 0x1000.The build succeeds, but the first system call crashes because uservec is no longer at the start of a page.The assembler rejects trampoline.S because trampsec must start on a page boundary.The build succeeds, because line 18 still aligns the end of the trampoline to a page boundary.

22deepChoose one

NCPU is 8, so stack0 has 8 slices and cpus has 8 entries. You run make qemu CPUS=10. What happens?

kernel/start.c

10// entry.S needs one stack per CPU.

11__attribute__((aligned(16))) char stack0[4096 * NCPU];

The kernel prints an error and panics, because NCPU is too small.Harts 8 and 9 wrap around and share the stacks of harts 0 and 1.Only 8 harts start; QEMU refuses to create more harts than the kernel was compiled for.Harts 8 and 9 compute stack tops past the end of stack0 and push onto the globals that follow it in .bss (cons, kmem, cpus, proc…); their cpus[] entries are out of bounds too. Memory is silently corrupted.

23deepChoose one

Process 1 runs fsinit with interrupts off on its hart (the scheduler’s acquire recorded intena = 0, so forkret's release leaves them off). Its first disk read sleeps waiting for the completion interrupt. Which hart can take that interrupt?

kernel/proc.c

512void
513forkret(void)
514{
515  extern char userret[];
516  static int first = 1;
517  struct proc *p = myproc();
518
519  // Still holding p->lock from scheduler.
520  release(&p->lock);
521
522  if (first) {
523    first = 0;
524
525    // File system initialization must be run in the context of a
526    // regular process (e.g., because it calls sleep), and thus cannot
527    // be run from main().
528    fsinit(ROOTDEV);

No hart; during boot the driver polls the disk instead of waiting for an interrupt.Only hart 0, because it is the only hart that ran plicinit.Any hart that has called plicinithart and is in its scheduler loop’s interrupt window, including process 1’s own hart once process 1 has gone to sleep.Process 1’s hart, inside fsinit, because sleeping turns interrupts on for the sleeping process.

24deepChoose all that apply

Suppose harts 1 and 2, after seeing started == 1, also ran these functions themselves. Which would corrupt shared kernel state? Choose all that apply.

kernel/main.c

if (cpuid() == 0) {
  consoleinit();
  printkinit();
  printk("\n");
  printk("xv6 kernel is booting\n");
  printk("\n");
  kinit();            // physical page allocator
  kvminit();          // create kernel page table
  kvminithart();      // turn on paging
  procinit();         // process table
  trapinit();         // trap vectors
  trapinithart();     // install kernel trap vector
  plicinit();         // set up interrupt controller
  plicinithart();     // ask PLIC for device interrupts
  binit();            // buffer cache
  iinit();            // inode table
  fileinit();         // file table
  virtio_disk_init(); // emulated hard disk
  userinit();         // first user process
32
  __atomic_store_n(&started, 1, __ATOMIC_RELEASE);
} else {
  while (__atomic_load_n(&started, __ATOMIC_ACQUIRE) == 0)
    ;
37
  printk("hart %d starting\n", cpuid());
  kvminithart();  // turn on paging
  trapinithart(); // install kernel trap vector
  plicinithart(); // ask PLIC for device interrupts
}
43
scheduler();

25deepPut in order

Put the steps of process 1’s life in order, from its creation to its first user instruction.

kexec("/init") loads the program and installs its new page table
prepare_return points stvec at uservec and sets sepc to the entry point
fsinit reads the superblock and recovers the log
userret switches satp to the user page table and executes sret
forkret releases p->lock
a scheduler sets RUNNING and calls swtch, whose ret lands in forkret
allocproc sets p->context.ra = forkret and p->context.sp to the top of its kernel stack
userinit sets p->state = RUNNABLE