Memory ordering and atomics · xv6, line by line

1warm-upChoose one

Why can’t a spinlock be written as plain C, like this?

while (lk->locked)
  ;
lk->locked = 1;

Two harts can both read 0 before either of them stores 1, and then both believe they hold the lock.It works on one hart, and xv6 runs each lock on only one hart.Because lk->locked = 1 might be compiled into two separate byte stores.Because a C loop cannot run with interrupts off.

2warm-upChoose one

Line 37 compiles to amoswap.w.aq a5,a5,(s1) with a5 = 1 and s1 = &lk->locked. What does this one instruction do?

kernel/spinlock.c

// On RISC-V, __atomic_exchange_n turns into an atomic swap:
//   a5 = 1
//   s1 = &lk->locked
//   amoswap.w.aq a5, a5, (s1)
//
// Passing __ATOMIC_ACQUIRE to __atomic_exchange_n tells
// the C compiler and the processor to not move loads or stores
// past this point, to ensure that the critical section's memory
// references happen strictly after the lock is acquired.
while (__atomic_exchange_n(&lk->locked, 1, __ATOMIC_ACQUIRE) != 0)
  ;

It swaps the contents of registers a5 and s1.It waits in hardware until lk->locked becomes 0, then sets it to 1.It reads the old value of lk->locked into a5 and writes 1 there, with no other hart able to touch the word in between.It writes 1 only if lk->locked is 0, and leaves memory unchanged otherwise.

3warm-upTrue or false, and why

True or false: started is declared volatile on line 7, so the boot handoff would still be correct on RISC-V if lines 33 and 35 used plain started = 1; and while (started == 0) ;.

kernel/main.c

7volatile static int started = 0;
8
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)
    ;

TrueFalse

Why?

It would be correct, because a 32-bit store on RISC-V is atomic.volatile would make the waiting loop read started only once.volatile emits no fence, so other harts could see started == 1 before hart 0’s earlier stores (the page table, the free list), and the readers could load that data before the flag.

4warm-upChoose one

Hart 0 executes two stores to different addresses, first to x and then to y, with no fence between them. Under RISC-V’s memory model (RVWMO), which statement is right?

Another hart may see them in any order, and so may hart 0 itself.Hart 0 itself always sees them in program order, but another hart may see the new y while still seeing the old x.Every hart sees them in program order, because RISC-V executes instructions in order.Order only matters for device registers; ordinary memory is always seen in order.

5warm-upChoose all that apply

Why does release free the lock with __atomic_store_n(&lk->locked, 0, __ATOMIC_RELEASE) rather than lk->locked = 0;? Choose all that apply.

kernel/spinlock.c

44// Release the lock.
45void
46release(struct spinlock *lk)
47{
if (!holding(lk))
  panic("release");
50
lk->cpu = 0;
52
// Release the lock, equivalent to lk->locked = 0.
//
// This code doesn't use a C assignment, since the C standard
// implies that an assignment might be implemented with
// multiple store instructions.
//
// On RISC-V, __atomic_store_n turns into a single atomic store:
//   s1 = &lk->locked
//   fence rw,w
//   sw zero,0(s1)
//
// The __ATOMIC_RELEASE argument to __atomic_store_n tells the
// the C compiler and the CPU to not move loads or stores past
// this point, to ensure that all the stores in the critical
// section are visible to other CPUs before the lock is released,
// and that loads in the critical section occur strictly before
// the lock is released.
//
// On RISC-V, this generates a fence instruction before the store:
//   fence rw,w
__atomic_store_n(&lk->locked, 0, __ATOMIC_RELEASE);
74
pop_off();
76}

It is what turns interrupts back on after the critical section.It uses an amoswap so that release can check the lock really was held.It stops both the compiler and the CPU from letting the critical section’s loads and stores move after the store that frees the lock.It pushes the store out to other harts immediately, so the next waiter sees 0 at once.The C standard does not promise that a plain assignment is a single store; the atomic built-in does.

6warm-upClick the line

Click the line of release that compiles to the fence rw,w at 0x80000c86.

kernel/spinlock.c

44// Release the lock.
45void
46release(struct spinlock *lk)
47{
if (!holding(lk))
  panic("release");
50
lk->cpu = 0;
52
// Release the lock, equivalent to lk->locked = 0.
//
// This code doesn't use a C assignment, since the C standard
// implies that an assignment might be implemented with
// multiple store instructions.
//
// On RISC-V, __atomic_store_n turns into a single atomic store:
//   s1 = &lk->locked
//   fence rw,w
//   sw zero,0(s1)
//
// The __ATOMIC_RELEASE argument to __atomic_store_n tells the
// the C compiler and the CPU to not move loads or stores past
// this point, to ensure that all the stores in the critical
// section are visible to other CPUs before the lock is released,
// and that loads in the critical section occur strictly before
// the lock is released.
//
// On RISC-V, this generates a fence instruction before the store:
//   fence rw,w
__atomic_store_n(&lk->locked, 0, __ATOMIC_RELEASE);
74
pop_off();
76}

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

7warm-upChoose one

kalloc updates kmem.freelist with ordinary loads and stores and no fence of its own, yet three harts call it. Why do the harts see each other’s updates correctly?

kernel/kalloc.c

68void *
69kalloc(void)
70{
71  struct run *r;
72
73  acquire(&kmem.lock);
74  r = kmem.freelist;
75  if (r)
76    kmem.freelist = r->next;
77  release(&kmem.lock);
78
79  if (r)
80    memset((char *)r, 5, PGSIZE); // fill with junk
81  return (void *)r;
82}

It works by luck; on real hardware kalloc would need its own fences.The lock’s acquire (amoswap.w.aq) and release (fence rw,w) order every access inside the critical section for any hart that takes the same lock.Because interrupts are off inside the critical section.Because kmem.freelist is declared volatile.

8warm-upType a number

Hart 2 waits in acquire for a lock held by hart 1. Its swap on line 37 runs 1,000 times: the first 999 return 1, the last returns 0. How many times does hart 2 write to lk->locked in total?

kernel/spinlock.c

37 while (__atomic_exchange_n(&lk->locked, 1, __ATOMIC_ACQUIRE) != 0)

38 ;

decimal, 0x hex or 0b binary

9solidDecode the bits

kernel.asm shows the spin instruction in acquire as 80000c04: 0cf4a7af amoswap.w.aq a5,a5,(s1). Decode the 32-bit word. (AMO format: funct5 in bits 31–27, aq bit 26, rl bit 25, rs2 24–20, rs1 19–15, funct3 14–12, rd 11–7, opcode 6–0.)

Value: 0x0cf4a7af

funct5 (bits 31–27)aq (bit 26)rl (bit 25)funct3 (bits 14–12), the widthrs1 (bits 19–15), the address registerWhat ordering does aq = 1, rl = 0 give?

10solidDecode the bits

kernel.asm contains 0310000f fence rw,w at 0x80000c86 and again at 0x80000f0a. Decode the word. (FENCE format: fm in bits 31–28; the predecessor set PI PO PR PW in bits 27–24; the successor set SI SO SR SW in bits 23–20; opcode in bits 6–0.)

Value: 0x0310000f

Opcode (bits 6–0 = 0001111)Predecessor set (bits 27–24)Successor set (bits 23–20)Which C statements produce it?

11solidClick the line

Click the line whose compiled code includes fence r,rw.

kernel/main.c

  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
}

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

12solidMatch the pairs

Match each ordering instruction in this build’s kernel.asm with where it comes from.

amoswap.w.aq at 0x80000c04fence r,rw at 0x80000e76fence (iorw, iorw) at 0x80005a66fence.i at 0x8000609csfence.vma at 0x80000f1a

13solidType a number

A hart calls acquire(&kmem.lock) and, a few lines later, release(&kmem.lock). The lock was free, so the swap succeeds at once. How many instructions whose mnemonic is fence (not sfence.vma, not fence.i) does the hart execute inside these two calls?

decimal, 0x hex or 0b binary

14solidType a number

How many atomic memory operation instructions (AMOs such as amoswap, amoadd, or LR/SC pairs counted as one) does this build’s kernel/kernel.asm contain?

decimal, 0x hex or 0b binary

15solidChoose one

Compile static int started; ... while (started == 0) ; (a plain int, no volatile, no atomics) with this toolchain and xv6’s flags (-O). What does GCC emit for the loop?

One load of started before the loop, then a branch that jumps to itself forever if the value was 0.Nothing at all; GCC removes the loop as dead code.A load and a branch on every iteration, just slower than the atomic version.A load followed by fence r,rw on every iteration.

16solidChoose all that apply

volatile is used on its own for the UART’s registers (Reg() in kernel/uart.c:17) and for the panicked flag. Which of these does volatile guarantee? Choose all that apply.

Every read written in the source performs a real load (a loop re-reads the value each time).The compiler emits a fence instruction next to each volatile access.Other harts see this hart’s earlier ordinary stores before they see the volatile store.Every write written in the source performs a real store, not merged with or dropped in favour of another.A volatile x++ is an atomic read-modify-write.

17solidFill in the machine state

Hart 1 is spinning on line 35 of main, waiting for started, while hart 0 is still building the kernel. What is hart 1’s state?

kernel/main.c

  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
}

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

18solidChoose one

release clears lk->cpu on line 51 before the store on line 73 frees the lock. What would go wrong if the order were reversed (free the lock first, then lk->cpu = 0)?

kernel/spinlock.c

44// Release the lock.
45void
46release(struct spinlock *lk)
47{
if (!holding(lk))
  panic("release");
50
lk->cpu = 0;
52
// Release the lock, equivalent to lk->locked = 0.
//
// This code doesn't use a C assignment, since the C standard
// implies that an assignment might be implemented with
// multiple store instructions.
//
// On RISC-V, __atomic_store_n turns into a single atomic store:
//   s1 = &lk->locked
//   fence rw,w
//   sw zero,0(s1)
//
// The __ATOMIC_RELEASE argument to __atomic_store_n tells the
// the C compiler and the CPU to not move loads or stores past
// this point, to ensure that all the stores in the critical
// section are visible to other CPUs before the lock is released,
// and that loads in the critical section occur strictly before
// the lock is released.
//
// On RISC-V, this generates a fence instruction before the store:
//   fence rw,w
__atomic_store_n(&lk->locked, 0, __ATOMIC_RELEASE);
74
pop_off();
76}

Nothing; lk->cpu is only for debugging.The fence rw,w would then order lk->cpu = 0 before the free, so it would be fine.Another hart could take the lock and record itself in lk->cpu in between, and this hart’s late store would erase the new owner, so the new owner’s release would panic.Interrupts would come back on before lk->cpu is cleared.

19solidTrue or false, and why

True or false: panicked (kernel/printk.c:19) is a plain volatile int with no atomics or fences, and that is enough for what it is used for.

kernel/printk.c

137void
138panic(char *s)
139{
140  panicking = 1;
141  printk("panic: ");
142  printk("%s\n", s);
143  panicked = 1; // freeze uart output from other CPUs
144  for (;;)
145    ;
146}

TrueFalse

Why?

panic holds pr.lock while setting it, and the lock’s fences order it.Every hart checks panicked with interrupts off, which orders the read.A hart that sees panicked == 1 only stops (in uartputc_sync); it reads nothing that panic prepared, so the order of other memory does not matter.

20deepChoose one

Hart 0’s store to started is a release (fence rw,w; sw). Why must harts 1 and 2 also use an acquire load (lw; fence r,rw) instead of a plain lw in the loop?

kernel/main.c

  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
}

Without it, RVWMO lets hart 1 perform a later load (say, of kernel_pagetable in kvminithart) before the load that sees started == 1, even though a branch separates them.Because the fence rw,w on hart 0 orders only stores to started itself.To make hart 0’s store become visible sooner.It isn’t needed; the loop’s beqz already prevents hart 1 from running ahead.

21deepPut in order

Put these events in the order that makes hart 1’s first use of the kernel page table safe at boot.

Hart 1: fence r,rw (0x80000e76)
Hart 1: sfence.vma at the start of kvminithart
Hart 0: sw sets started to 1
Hart 1: csrw satp turns paging on
Hart 1: lw reads started == 1
Hart 0: fence rw,w (0x80000f0a)
Hart 0: kvminit's ordinary stores build the kernel page table

22deepChoose one

A timer interrupt makes sh yield on hart 1: swtch saves its 14 registers with ordinary sd instructions into p->context, and hart 1’s scheduler releases sh’s p->lock. Later hart 0’s scheduler acquires that lock, sees RUNNABLE, and swtch loads p->context. What guarantees hart 0 loads the values hart 1 saved, not older ones?

kernel/swtch.S

9swtch:
      sd ra, 0(a0)
      sd sp, 8(a0)
      sd s0, 16(a0)
      sd s1, 24(a0)
      sd s2, 32(a0)
      sd s3, 40(a0)
      sd s4, 48(a0)
      sd s5, 56(a0)
      sd s6, 64(a0)
      sd s7, 72(a0)
      sd s8, 80(a0)
      sd s9, 88(a0)
      sd s10, 96(a0)
      sd s11, 104(a0)
24
      ld ra, 0(a1)
      ld sp, 8(a1)

The fence.i in userret on hart 0.swtch contains a fence after its sd instructions.Hart 1’s release of p->lock (fence rw,w; sw) orders the sds before the lock is freed, and hart 0’s amoswap.w.aq keeps its later loads after it took the lock.Nothing is needed, because all harts share one memory.

23deepChoose one

virtio_disk_rw holds disk.vdisk_lock, a spinlock with acquire and release ordering. Why does it still need io_fence() between writing avail->idx and writing the QUEUE_NOTIFY register?

kernel/virtio_disk.c

274  // tell the device the first index in our chain of descriptors.
275  disk.avail->ring[disk.avail->idx % NUM] = idx[0];
276
277  io_fence();
278
279  // tell the device another avail ring entry is available.
280  disk.avail->idx += 1; // not % NUM ...
281
282  io_fence();
283
284  *R(VIRTIO_MMIO_QUEUE_NOTIFY) = 0; // value is queue number

The device never takes the lock; it reads the rings by DMA after the notify, so the ring and index stores must be ordered before the device write by a fence that covers device output (fence iorw,iorw).Because release’s fence rw,w already covers it, io_fence only makes the compiler reload avail->idx.Because interrupts are on inside the critical section.It does not; the fences are leftovers that could be removed.

24deepChoose one

An experiment built a copy of the kernel with __ATOMIC_RELAXED on release's line 73, so the compiled release has no fence at all. Run under QEMU on an x86-64 host, it passed usertests -q three times and two stress runs. What does that show?

kernel/spinlock.c

// On RISC-V, this generates a fence instruction before the store:
//   fence rw,w
__atomic_store_n(&lk->locked, 0, __ATOMIC_RELEASE);
74
pop_off();

That the fence in release is unnecessary, since amoswap.w.aq in acquire is enough on its own.Little about correctness: the x86 host keeps stores in program order (total store order), so the reordering RVWMO allows never happened in these runs, but it could on a real RISC-V core.That QEMU ignores the RISC-V memory model and always runs with one hart at a time.That usertests does not use any spinlocks.

25deepChoose all that apply

Consider the fence rw,w that release executes before sw zero,0(s1). Which of these orderings does it guarantee, as other harts observe them? Choose all that apply.

kernel/spinlock.c

44// Release the lock.
45void
46release(struct spinlock *lk)
47{
if (!holding(lk))
  panic("release");
50
lk->cpu = 0;
52
// Release the lock, equivalent to lk->locked = 0.
//
// This code doesn't use a C assignment, since the C standard
// implies that an assignment might be implemented with
// multiple store instructions.
//
// On RISC-V, __atomic_store_n turns into a single atomic store:
//   s1 = &lk->locked
//   fence rw,w
//   sw zero,0(s1)
//
// The __ATOMIC_RELEASE argument to __atomic_store_n tells the
// the C compiler and the CPU to not move loads or stores past
// this point, to ensure that all the stores in the critical
// section are visible to other CPUs before the lock is released,
// and that loads in the critical section occur strictly before
// the lock is released.
//
// On RISC-V, this generates a fence instruction before the store:
//   fence rw,w
__atomic_store_n(&lk->locked, 0, __ATOMIC_RELEASE);
74
pop_off();
76}

The lk->cpu = 0 store on line 51 is ordered before the store that frees the lock.Other harts see the freeing store within a fixed, bounded time.The critical section’s loads are performed before the lock is seen as free.The critical section’s stores become visible before the store that frees the lock.Loads this hart makes after release returns are kept after the freeing store.