Spinlocks and interrupt state · xv6, line by line

1warm-upChoose one

acquire calls push_off before it tries to take the lock. Why must interrupts be off before the lock is taken, rather than just after?

kernel/spinlock.c

21void
22acquire(struct spinlock *lk)
23{
push_off(); // disable interrupts to avoid deadlock.
if (holding(lk))
  panic("acquire");
27
// 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)
  ;
39
// Record info about lock acquisition for holding() and debugging.
lk->cpu = mycpu();
42}

Because the atomic swap instruction only works with interrupts disabled.So that no interrupt handler on this hart can find the lock held by the very code it interrupted, and spin forever.It makes no difference; the window between taking the lock and calling push_off would be only a few instructions long.To stop other harts from taking the lock at the same time.

2solidChoose all that apply

Which of these locks are acquired inside an interrupt handler (from devintr or code it calls) in this kernel?

3solidType a number

A process is in kwait holding wait_lock and a zombie child’s p->lock. It calls freeproc, which calls kfree, which is now inside acquire(&kmem.lock) with the lock held. What is mycpu()->noff at that moment?

decimal, 0x hex or 0b binary

4solidPut in order

Put the steps of acquire in the order they happen.

kernel/spinlock.c

21void
22acquire(struct spinlock *lk)
23{
push_off(); // disable interrupts to avoid deadlock.
if (holding(lk))
  panic("acquire");
27
// 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)
  ;
39
// Record info about lock acquisition for holding() and debugging.
lk->cpu = mycpu();
42}

holding(lk) check, panic if this hart already holds the lock
amoswap.w.aq in a loop until the old value is 0
push_off(): interrupts off, noff + 1
lk->cpu = mycpu()

5solidClick the line

In pop_off, click the line that can turn interrupts back on.

kernel/spinlock.c

105void
106pop_off(void)
107{
108  struct cpu *c = mycpu();
109  if (intr_get())
110    panic("pop_off - interruptible");
111  if (c->noff < 1)
112    panic("pop_off");
113  c->noff -= 1;
114  if (c->noff == 0 && c->intena)
115    intr_on();
116}

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

6solidFill in the machine state

Hart 1 is running cat’s consoleread (a read system call). It has just executed line 95, acquire(&cons.lock), and the lock is now held. What is the state of hart 1?

kernel/console.c

87int
88consoleread(int user_dst, uint64 dst, int n)
89{
uint target;
int c;
char cbuf;
93
target = n;
acquire(&cons.lock);
while (n > 0) {
  // wait until interrupt handler has put some
  // input into cons.buffer.
  while (cons.r == cons.w) {
    if (killed(myproc())) {
      release(&cons.lock);
      return -1;
    }
    sleep_prepare(&cons.r);
    release(&cons.lock);
    sleep();
    acquire(&cons.lock);
  }

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

7deepDecode the bits

gdb shows sstatus = 0x200000122 on a hart running kernel code. Decode it.

Value: 0x200000122

SIE (bit 1)SPIE (bit 5)SPP (bit 8): where sret returnsCould this hart be holding a spinlock right now?

8warm-upMatch the pairs

Match each panic message with the mistake that triggers it.

panic: acquirepanic: releasepanic: sched lockspanic: pop_off - interruptible

9deepTrue or false, and why

True or false: holding tells you whether the current process holds the lock.

TrueFalse

Why?

Spinlocks have no owner at all; holding() only checks locked.holding() compares lk->pid with myproc()->pid.holding() compares lk->cpu with mycpu(), so it is about the hart; p->lock is even acquired by the scheduler and released by the process on the same hart.

10warm-upChoose one

Hart 0 holds a spinlock. Hart 1, inside acquire, executes the swap below with a5 = 1 and s1 pointing at the lock’s locked word. What happens?

80000c02:  mv     a5,a4
80000c04:  amoswap.w.aq  a5,a5,(s1)
80000c08:  sext.w a5,a5
80000c0a:  bnez   a5,80000c02

kernel/spinlock.c

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

38 ;

The instruction stalls inside the hardware until hart 0 stores 0, then completes.The instruction raises an exception, because the word is already locked.Hart 1 now also owns the lock, because its swap wrote a 1 into the word.The word is written with 1 (it already held 1), a5 receives the old value 1, and bnez jumps back to try again.

11warm-upChoose one

Hart 0 holds kmem.lock. A process on hart 1 calls acquire(&kmem.lock). Until hart 0 releases it, what is hart 1 doing?

Running the swap loop in acquire again and again, with its own interrupts off, so it takes no interrupts and runs nothing else.It waits in a wfi instruction until hart 0’s release sends it an interrupt.It puts the current process to sleep and runs another process until the lock is free.It spins with interrupts on, so a timer tick can still make it yield to another process.

12warm-upTrue or false, and why

True or false: push_off saves the current value of SIE into intena every time it is called.

kernel/spinlock.c

92void
93push_off(void)
94{
95  // disable interrupts to prevent an involuntary context
96  // switch while using mycpu().
97  uint64 flags = rc_sstatus(SSTATUS_SIE);
98  int old = !!(flags & SSTATUS_SIE);
99
100  if (mycpu()->noff == 0)
101    mycpu()->intena = old;
102  mycpu()->noff += 1;
103}

TrueFalse

Why?

Only the outermost push_off (noff 0 → 1) writes it; a nested one finds SIE already 0 and would overwrite the value that matters.push_off never writes intena; acquire writes it after the swap succeeds.intena is written by pop_off, not push_off.

13warm-upType a number

A spinlock is free (locked is 0). Three harts execute their amoswap.w.aq on its locked word at the same instant. How many of the three swaps return 0?

decimal, 0x hex or 0b binary

14warm-upChoose one

Why does xv6 hold spinlocks only for short stretches of code, never across a disk read or a wait for input?

Because acquire gives up and panics if it has spun for more than one timer tick.Because the lock word is only 32 bits wide and fills up if a lock is held too long.Because a timer interrupt during a long critical section would make the holder yield and leave the lock held while it is off the CPU.Any other hart that wants the lock spins with interrupts off for the whole time it is held, doing no useful work.

15warm-upChoose one

Why does xv6 count interrupt-disabling with push_off/pop_off instead of having acquire call intr_off and release call intr_on?

Locks nest; releasing an inner lock must not turn interrupts on while an outer lock is still held.So that other harts can read noff and see how many locks this hart holds.Because intr_off and intr_on are much slower than push_off and pop_off.Because the counter is what detects a hart acquiring the same lock twice.

16solidChoose one

release frees the lock with __atomic_store_n(&lk->locked, 0, __ATOMIC_RELEASE), which compiles to fence rw,w followed by sw zero,0(s1). What does the fence prevent?

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}

Other harts’ swaps writing to the lock word while this hart is clearing it.Nothing on RISC-V; it is there only for other architectures.Another hart seeing locked == 0 while some of this critical section’s stores are not yet visible, or while one of its loads has not yet read its value.An interrupt arriving between the fence and the store.

17solidChoose one

release clears lk->cpu on line 51 before it stores 0 into lk->locked on line 73. What could go wrong if the two were the other way round?

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}

This hart’s pop_off would panic, because it checks lk->cpu.The fence would no longer cover the store to lk->cpu, so other harts could see a torn pointer.Nothing; lk->cpu is only for debugging, as the comment in spinlock.h says.Another hart could take the lock in between and record itself in lk->cpu, and this hart’s late lk->cpu = 0 would erase the new owner.

18solidClick the line

Click the line of release from which another hart’s acquire can succeed.

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)

19solidPut in order

A system call on hart 0 is in sys_uptime, holding tickslock, when hart 0’s timer deadline passes. Put the events in order.

kernel/sysproc.c

104sys_uptime(void)
105{
106  uint xticks;
107
108  acquire(&tickslock);
109  xticks = ticks;
110  release(&tickslock);
111  return xticks;
112}

the pending timer interrupt is taken, and clockintr acquires tickslock, which hart 0 no longer holds
pop_off takes noff to 0, sees intena 1, and sets SIE
release stores 0 into tickslock.locked
the amoswap takes tickslock
the timer deadline passes: the interrupt becomes pending but is not taken
acquire’s push_off clears SIE on hart 0 and records intena = 1

20solidChoose all that apply

Besides acquire and release, which of these functions call push_off and pop_off directly?

21solidChoose one

The comment above holding says “Interrupts must be off.” What could go wrong if holding(lk) ran with interrupts on?

kernel/spinlock.c

78// Check whether this cpu is holding the lock.
79// Interrupts must be off.
80int
81holding(struct spinlock *lk)
82{
83  int r;
84  r = (lk->locked && lk->cpu == mycpu());
85  return r;
86}

holding() writes lk->locked, so an interrupt could corrupt the lock word.An interrupt handler could release the lock while holding() is reading it.The thread could be preempted between reading lk->cpu and calling mycpu(), resume on another hart, and compare against the wrong hart.The amoswap inside holding() is only atomic with interrupts off.

22deepChoose one

sh went to sleep in consoleread (a system call) on hart 0, so the p->lock it took in sleep was acquired with SIE on and hart 0’s intena is 1. Suppose line 456 (mycpu()->intena = 0) were deleted. What goes wrong when hart 0’s scheduler continues after its swtch?

kernel/proc.c

  intr_on();
  intr_off();
443
  int found = 0;
  for (p = proc; p < &proc[NPROC]; p++) {
    acquire(&p->lock);
    if (p->state == RUNNABLE) {
      // Switch to chosen process.  It is the process's job
      // to release its lock and then reacquire it
      // before jumping back to us.
      p->state = RUNNING;
      c->proc = p;
      swtch(&c->context, &p->context);
454
      // Don't re-enable interrupts on release.
      mycpu()->intena = 0;
457
      // Process is done running for now.
      // It should have changed its p->state before coming back.
      c->proc = 0;
      found = 1;
    }
    release(&p->lock);
  }

The scheduler’s release would panic with “pop_off - interruptible”.Nothing; intena is only ever read by the thread that wrote it.Its release(&p->lock) on line 463 sees intena 1 and turns interrupts on inside the scheduler loop.sh would later resume from sched with intena 0 and finish its system call with interrupts off.

23deepChoose all that apply

Which of these can change sstatus.SIE from 0 to 1 on a hart in this kernel?

kerneltrap's w_sstatus(sstatus) (kernel/trap.c:163)prepare_return's w_sstatus(x) (kernel/trap.c:128)sret at the end of kernelvec, when SPIE is 1pop_off's intr_on (kernel/spinlock.c:115)scheduler's intr_on (kernel/proc.c:441)usertrap's intr_on (kernel/trap.c:66), for a system call

24deepFill in the machine state

A process called exit(0). kexit has just executed line 360, release(&wait_lock), while still holding its own p->lock (taken on line 355). What is the state of its hart?

kernel/proc.c

347  acquire(&wait_lock);
348
349  // Give any children to init.
350  reparent(p);
351
352  // Parent might be sleeping in wait().
353  wakeup(p->parent);
354
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");

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

25deepType a number

iput drops the last reference to an unlinked file. Holding itable.lock, it calls acquiresleep(&ip->lock) on line 362. Inside acquiresleep, line 32 calls myproc. Right after myproc’s push_off, what is mycpu()->noff?

kernel/sleeplock.c

21void
22acquiresleep(struct sleeplock *lk)
23{
acquire(&lk->lk);
while (lk->locked) {
  sleep_prepare(lk);
  release(&lk->lk);
  sleep();
  acquire(&lk->lk);
}
lk->locked = 1;
lk->pid = myproc()->pid;
release(&lk->lk);
34}

decimal, 0x hex or 0b binary