xv6, line by line
test yourself

Test yourself · category 6 of 20

The stacks

User stacks, kernel stacks and the boot-turned-scheduler stack, the four instructions that move sp between them, where interrupts push their frames, and the save areas that are not stacks.

1warm-upChoose one

Where does a hart’s scheduler stack come from?

kernel/main.c
9// start() jumps here in supervisor mode on all CPUs.
10void
11main()
12{
13 if (cpuid() == 0) {
14 consoleinit();
15 printkinit();
16 printk("\n");
17 printk("xv6 kernel is booting\n");
18 printk("\n");
19 kinit(); // physical page allocator
20 kvminit(); // create kernel page table
21 kvminithart(); // turn on paging
22 procinit(); // process table
23 trapinit(); // trap vectors
24 trapinithart(); // install kernel trap vector
25 plicinit(); // set up interrupt controller
26 plicinithart(); // ask PLIC for device interrupts
27 binit(); // buffer cache
28 iinit(); // inode table
29 fileinit(); // file table
30 virtio_disk_init(); // emulated hard disk
31 userinit(); // first user process
32
33 __atomic_store_n(&started, 1, __ATOMIC_RELEASE);
34 } else {
35 while (__atomic_load_n(&started, __ATOMIC_ACQUIRE) == 0)
36 ;
37
38 printk("hart %d starting\n", cpuid());
39 kvminithart(); // turn on paging
40 trapinithart(); // install kernel trap vector
41 plicinithart(); // ask PLIC for device interrupts
42 }
43
44 scheduler();
45}
2warm-upType a number

How many kernel-stack pages does proc_mapstacks allocate at boot in this kernel?

kernel/proc.c
29// Allocate a page for each process's kernel stack.
30// Map it high in memory, followed by an invalid
31// guard page.
32void
33proc_mapstacks(pagetable_t kpgtbl)
34{
35 struct proc *p;
36
37 for (p = proc; p < &proc[NPROC]; p++) {
38 char *pa = kalloc();
39 if (pa == 0)
40 panic("kalloc");
41 uint64 va = KSTACK((int)(p - proc));
42 kvmmap(kpgtbl, va, (uint64)pa, PGSIZE, PTE_R | PTE_W);
43 }
44}
decimal, 0x hex or 0b binary
3warm-upTrue or false, and why

True or false: a child created by fork starts with a copy of its parent’s kernel stack.

Why?

4warm-upMatch the pairs

Match each instruction with what it does to the hart’s active stack.

5solidType a number

In this build stack0 is at 0x80007890. What value does sp hold on hart 2 right after line 17 of entry.S? Give it in hex.

kernel/entry.S
7_entry:
8 # set up a stack for C.
9 # stack0 is declared in start.c,
10 # with a 4096-byte stack per CPU.
11 # sp = stack0 + ((hartid + 1) * 4096)
12 la sp, stack0
13 li a0, 1024*4
14 csrr a1, mhartid
15 addi a1, a1, 1
16 mul a0, a0, a1
17 add sp, sp, a0
18 # jump to start() in start.c
19 call start
20spin:
21 j spin
decimal, 0x hex or 0b binary
6warm-upClick the line

In swtch, click the line at which the hart stops running on the old thread’s stack and starts running on the new one’s.

kernel/swtch.S
8.globl swtch
9swtch:
10 sd ra, 0(a0)
11 sd sp, 8(a0)
12 sd s0, 16(a0)
13 sd s1, 24(a0)
14 sd s2, 32(a0)
15 sd s3, 40(a0)
16 sd s4, 48(a0)
17 sd s5, 56(a0)
18 sd s6, 64(a0)
19 sd s7, 72(a0)
20 sd s8, 80(a0)
21 sd s9, 88(a0)
22 sd s10, 96(a0)
23 sd s11, 104(a0)
24
25 ld ra, 0(a1)
26 ld sp, 8(a1)
27 ld s0, 16(a1)
28 ld s1, 24(a1)
29 ld s2, 32(a1)
30 ld s3, 40(a1)
31 ld s4, 48(a1)
32 ld s5, 56(a1)
33 ld s6, 64(a1)
34 ld s7, 72(a1)
35 ld s8, 80(a1)
36 ld s9, 88(a1)
37 ld s10, 96(a1)
38 ld s11, 104(a1)
39
40 ret

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

7solidFill in the machine state

A process is returning to user mode. The hart has just executed line 111 of userret, csrw satp, a0, and has not reached line 118 yet. What is its state?

kernel/trampoline.S
100.globl userret
101userret:
102 # usertrap() returns here, with user satp in a0.
103 # return from kernel to user.
104
105 # flush icache, in case this is the first time
106 # we're running this proc on this hart.
107 fence.i
108
109 # switch to the user page table.
110 sfence.vma zero, zero
111 csrw satp, a0
112 sfence.vma zero, zero
113
114 li a0, TRAPFRAME
115
116 # restore all but a0 from TRAPFRAME
117 ld ra, 40(a0)
118 ld sp, 48(a0)
119 ld gp, 56(a0)
120 ld tp, 64(a0)
8deepFill in the machine state

Hart 0’s scheduler has just switched to init (pid 1) for the first time. The hart is at the first instruction of forkret, before line 520. What is its state?

kernel/proc.c
510// A fork child's very first scheduling by scheduler()
511// will swtch to forkret.
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);
529
530 // We can invoke kexec() now that file system is initialized.
531 // Put the return value (argc) of kexec into a0.
532 p->trapframe->a0 = kexec("/init", (char *[]){"/init", 0});
533 if (p->trapframe->a0 == -1) {
534 panic("exec");
535 }
536 }
537
538 // return to user space, mimicing usertrap()'s return.
539 prepare_return();
540 uint64 satp = MAKE_SATP(p->pagetable);
541 uint64 trampoline_userret = TRAMPOLINE + (userret - trampoline);
542 ((void (*)(uint64))trampoline_userret)(satp);
543}
9warm-upChoose one

sh makes a read system call. Which stack do usertrap, syscall and sys_read run on?

10solidChoose all that apply

Which of these are save areas (fixed slots for registers) rather than stacks?

11warm-upChoose one

A process is in the middle of a system call, with interrupts on, when a timer interrupt arrives. Where does kernelvec save the interrupted registers?

kernel/kernelvec.S
9.globl kerneltrap
10.globl kernelvec
11.align 4
12kernelvec:
13 # make room to save registers.
14 addi sp, sp, -256
15
16 # save caller-saved registers.
17 sd ra, 0(sp)
18 # sd sp, 8(sp)
19 sd gp, 16(sp)
20 # sd tp, 24(sp)
21 sd t0, 32(sp)
22 sd t1, 40(sp)
23 sd t2, 48(sp)
24 sd a0, 72(sp)
25 sd a1, 80(sp)
26 sd a2, 88(sp)
27 sd a3, 96(sp)
28 sd a4, 104(sp)
29 sd a5, 112(sp)
30 sd a6, 120(sp)
31 sd a7, 128(sp)
32 sd t3, 216(sp)
33 sd t4, 224(sp)
34 sd t5, 232(sp)
35 sd t6, 240(sp)
36
37 # call the C trap handler in trap.c
38 call kerneltrap
12deepChoose one

kernelvec saves most caller-saved registers in its frame and restores them, but it deliberately neither saves nor restores tp (lines 20 and 44). Why?

kernel/kernelvec.S
40 # restore registers.
41 ld ra, 0(sp)
42 # ld sp, 8(sp)
43 ld gp, 16(sp)
44 # not tp (contains hartid), in case we moved CPUs
45 ld t0, 32(sp)
46 ld t1, 40(sp)
47 ld t2, 48(sp)
48 ld a0, 72(sp)
49 ld a1, 80(sp)
50 ld a2, 88(sp)
51 ld a3, 96(sp)
52 ld a4, 104(sp)
53 ld a5, 112(sp)
54 ld a6, 120(sp)
55 ld a7, 128(sp)
56 ld t3, 216(sp)
57 ld t4, 224(sp)
58 ld t5, 232(sp)
59 ld t6, 240(sp)
60
61 addi sp, sp, 256
62
63 # return to whatever we were doing in the kernel.
64 sret
13solidChoose one

A timer interrupt arrives while hart 2 is in its scheduler’s interrupt window (between lines 441 and 442 of proc.c). Which stack does kerneltrap run on, and does it call yield?

kernel/trap.c
134// interrupts and exceptions from kernel code go here via kernelvec,
135// on whatever the current kernel stack is.
136void
137kerneltrap()
138{
139 int which_dev = 0;
140 uint64 sepc = r_sepc();
141 uint64 sstatus = r_sstatus();
142 uint64 scause = r_scause();
143
144 if ((sstatus & SSTATUS_SPP) == 0)
145 panic("kerneltrap: not from supervisor mode");
146 if (intr_get() != 0)
147 panic("kerneltrap: interrupts enabled");
148
149 if ((which_dev = devintr()) == 0) {
150 // interrupt or trap from an unknown source
151 printk("scause=0x%lx sepc=0x%lx stval=0x%lx\n", scause, r_sepc(),
152 r_stval());
153 panic("kerneltrap");
154 }
155
156 // give up the CPU if this is a timer interrupt.
157 if (which_dev == 2 && myproc() != 0)
158 yield();
159
160 // the yield() may have caused some traps to occur,
161 // so restore trap registers for use by kernelvec.S's sepc instruction.
162 w_sepc(sepc);
163 w_sstatus(sstatus);
164}
14solidChoose all that apply

Which of these stacks have a guard page below them in this kernel?

15solidType a number

How many registers does kernelvec store into its 256-byte frame?

kernel/kernelvec.S
12kernelvec:
13 # make room to save registers.
14 addi sp, sp, -256
15
16 # save caller-saved registers.
17 sd ra, 0(sp)
18 # sd sp, 8(sp)
19 sd gp, 16(sp)
20 # sd tp, 24(sp)
21 sd t0, 32(sp)
22 sd t1, 40(sp)
23 sd t2, 48(sp)
24 sd a0, 72(sp)
25 sd a1, 80(sp)
26 sd a2, 88(sp)
27 sd a3, 96(sp)
28 sd a4, 104(sp)
29 sd a5, 112(sp)
30 sd a6, 120(sp)
31 sd a7, 128(sp)
32 sd t3, 216(sp)
33 sd t4, 224(sp)
34 sd t5, 232(sp)
35 sd t6, 240(sp)
36
37 # call the C trap handler in trap.c
38 call kerneltrap
decimal, 0x hex or 0b binary
16solidType a number

TRAMPOLINE is 0x3ffffff000 and PGSIZE is 0x1000. What address is the top of slot 4’s kernel stack, the value uservec loads into sp for the process in proc[4]? Give it in hex.

kernel/memlayout.h
46// map the trampoline page to the highest address,
47// in both user and kernel space.
48#define TRAMPOLINE (MAXVA - PGSIZE)
49
50// map kernel stacks beneath the trampoline,
51// each surrounded by invalid guard pages.
52#define KSTACK(p) (TRAMPOLINE - ((p) + 1) * 2 * PGSIZE)
decimal, 0x hex or 0b binary
17solidDecode the bits

gdb shows sp = 0x3fffff9ee0 on a hart in supervisor mode. Decode this address using KSTACK(i) = 0x3ffffff000 - (i + 1) * 0x2000.

Value: 0x3fffff9ee0

18solidChoose one

While kexec copies the argument strings onto the new program’s user stack (exec.c lines 101–119), which stack is the hart running on?

kernel/exec.c
89 sz = PGROUNDUP(sz);
90 uint64 sz1;
91 if ((sz1 = uvmalloc(pagetable, sz, sz + (USERSTACK + 1) * PGSIZE, PTE_W)) ==
92 0)
93 goto bad;
94 sz = sz1;
95 uvmclear(pagetable, sz - (USERSTACK + 1) * PGSIZE);
96 sp = sz;
97 stackbase = sp - USERSTACK * PGSIZE;
98
99 // Copy argument strings into new stack, remember their
100 // addresses in ustack[].
101 for (argc = 0; argv[argc]; argc++) {
102 sp -= strlen(argv[argc]) + 1;
103 sp -= sp % 16; // riscv sp must be 16-byte aligned
104 if (sp < stackbase)
105 goto bad;
106 if (copyout(pagetable, sz, sp, argv[argc], strlen(argv[argc]) + 1) < 0)
107 goto bad;
108 ustack[argc] = sp;
109 }
110 ustack[argc] = 0;
111
112 // push a copy of ustack[], the array of argv[] pointers.
113 sp -= (argc + 1) * sizeof(uint64);
114 sp -= sp % 16;
115 if (sp < stackbase)
116 goto bad;
117 if (copyout(pagetable, sz, sp, (char *)ustack, (argc + 1) * sizeof(uint64)) <
118 0)
119 goto bad;
19deepPut in order

Process A, running in user mode on hart 1, is interrupted by the timer. Hart 1 then runs process B, which had been preempted the same way earlier. Put hart 1’s stacks in the order sp visits them.

  1. B’s user stack, loaded by ld sp, 48(a0) in userret
  2. hart 1’s scheduler stack, loaded by ld sp, 8(a1) in swtch called from sched
  3. A’s user stack
  4. A’s kernel stack, loaded by ld sp, 8(a0) in uservec
  5. B’s kernel stack, at the point inside sched where B stopped, loaded by swtch called from scheduler
20deepChoose one

kexit marks the process ZOMBIE and calls sched, never to return. What happens to the kernel stack it was running on?

kernel/proc.c
355 acquire(&p->lock);
356
357 p->xstate = status;
358 p->state = ZOMBIE;
359
360 release(&wait_lock);
361
362 // Jump into the scheduler, never to return.
363 sched();
364 panic("zombie exit");
21solidChoose one

A scheduler switches to a fork child for the very first time. What does swtch’s ld sp, 8(a1) load, and what is on that stack?

kernel/proc.c
143 // Set up new context to start executing at forkret,
144 // which returns to user space.
145 memset(&p->context, 0, sizeof(p->context));
146 p->context.ra = (uint64)forkret;
147 p->context.sp = p->kstack + PGSIZE;
148
149 return p;
22deepChoose one

When process A gives up hart 1, why does sched switch to the scheduler stack instead of picking process B and switching directly from A’s kernel stack to B’s?

kernel/proc.c
479void
480sched(void)
481{
482 int intena;
483 struct proc *p = myproc();
484
485 if (!holding(&p->lock))
486 panic("sched p->lock");
487 if (mycpu()->noff != 1)
488 panic("sched locks");
489 if (p->state == RUNNING)
490 panic("sched RUNNING");
491 if (intr_get())
492 panic("sched interruptible");
493
494 intena = mycpu()->intena;
495 swtch(&p->context, &mycpu()->context);
496 mycpu()->intena = intena;
497}
23warm-upTrue or false, and why

True or false: while a process is running in user mode, its kernel stack still holds the frames of its last system call.

Why?

24deepChoose all that apply

Hypothetically, hart 0’s scheduler stack overflows by 32 bytes: some code on it pushes 32 bytes below the bottom of hart 0’s slice of stack0 (0x80007890). Which of these would be overwritten? (In this build kernel_pagetable is at 0x80007870, initproc at 0x80007878, ticks at 0x80007880, and cpus at 0x8000f9d0.)

25solidClick the line

In prepare_return, click the line that decides where sp will point when this process next traps in from user mode.

kernel/trap.c
100void
101prepare_return(void)
102{
103 struct proc *p = myproc();
104
105 // we're about to switch the destination of traps from
106 // kerneltrap() to usertrap(). because a trap from kernel
107 // code to usertrap would be a disaster, turn off interrupts.
108 intr_off();
109
110 // send syscalls, interrupts, and exceptions to uservec in trampoline.S
111 uint64 trampoline_uservec = TRAMPOLINE + (uservec - trampoline);
112 w_stvec(trampoline_uservec);
113
114 // set up trapframe values that uservec will need when
115 // the process next traps into the kernel.
116 p->trapframe->kernel_satp = r_satp(); // kernel page table
117 p->trapframe->kernel_sp = p->kstack + PGSIZE; // process's kernel stack
118 p->trapframe->kernel_trap = (uint64)usertrap;
119 p->trapframe->kernel_hartid = r_tp(); // hartid for cpuid()
120
121 // set up the registers that trampoline.S's sret will use
122 // to get to user space.
123
124 // set S Previous Privilege mode to User.
125 unsigned long x = r_sstatus();
126 x &= ~SSTATUS_SPP; // clear SPP to 0 for user mode
127 x |= SSTATUS_SPIE; // enable interrupts in user mode
128 w_sstatus(x);
129
130 // set S Exception Program Counter to the saved user pc.
131 w_sepc(p->trapframe->epc);
132}

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