系列文章 : [6.1810] 跟著 MIT 6.1810 學習基礎作業系統觀念

大綱

• kernel/proc.c/mycpu
• kernel/riscv.h/intr_get
• kernel/riscv.h/intr_on
• kernel/riscv.h/intr_off
• kernel/proc.h/struct cpu
• kernel/spinlock.c/push_off
• kernel/spinlock.c/pop_off
• kernel/spinlock.c/holding
• __sync_synchronize
• __sync_lock_test_and_set
• __sync_lock_release
• kernel/spinlock.c/acquire
• kernel/spinlock.c/release
• kernel/spinlock.c/initlock

kernel/proc.c/mycpu

{ https://github.com/TommyWu-fdgkhdkgh/xv6-riscv/blob/xv6-riscv-rev5/kernel/proc.c#L74 }

• 用 cpuid()，也就是 tp register 拿到 hart-id
• 依靠 hart-id，從 struct cpu cpus[NCPU] 陣列裡面拿到屬於自己的 struct cpu。

kernel/riscv.h/intr_get

{ https://github.com/TommyWu-fdgkhdkgh/xv6-riscv/blob/xv6-riscv-rev5/kernel/riscv.h#L301 }

回傳 sstatus.SIE 這個 bit ( 0 or 1 )

// are device interrupts enabled?
static inline int
intr_get()
{
  uint64 x = r_sstatus();
  return (x & SSTATUS_SIE) != 0;
}

kernel/riscv.h/intr_on

{ https://github.com/TommyWu-fdgkhdkgh/xv6-riscv/blob/xv6-riscv-rev5/kernel/riscv.h#L287 }

把 sstatus.SIE 設為 true

// enable device interrupts
static inline void
intr_on()
{ 
  w_sstatus(r_sstatus() | SSTATUS_SIE);
}

kernel/riscv.h/intr_off

{ https://github.com/TommyWu-fdgkhdkgh/xv6-riscv/blob/xv6-riscv-rev5/kernel/riscv.h#L294 }

把 sstatus.SIE 設為 false

kernel/proc.h/struct cpu

{ https://github.com/TommyWu-fdgkhdkgh/xv6-riscv/blob/xv6-riscv-rev5/kernel/proc.h#L22 }

• 每個 CPU ( 或是 hart ) 都有自己的 CPU state
• noff : 被呼叫 push_off 的深度
• intena ( interrupt enable ) : 在呼叫 push_off 之前，interrupt 是否有被打開 ?
  • 只有在 noff 從 0 轉變成 1 的時候，會將 intena 儲存起來

// Per-CPU state.
struct cpu {
  struct proc *proc;             // The process running on this cpu, or null.
  struct context context;     // swtch() here to enter scheduler().
  int noff;                            // Depth of push_off() nesting.
  int intena;                        // Were interrupts enabled before push_off()?
};

kernel/spinlock.c/push_off

{ https://github.com/TommyWu-fdgkhdkgh/xv6-riscv/blob/xv6-riscv-rev5/kernel/spinlock.c#L89 }

• 在呼叫 mycpu，需要記得先 disable interrupt
  • 假如沒有 disable interrupt，可能會在呼叫 mycpu 之後，收到 timer interrupt，然後這個 process 可能就交給其他 cpu 執行了，這時候這個 mycpu 的值就會不合理，明明是執行在 CPU-A 上，卻更改 CPU-B 的狀態!!
• 假如 noff ( push_off 的深度 ) 從 0 變成 1 的時候，需要把 sstatus.SIE 存進 intena，用以記得一開始有沒有 enable interrupt。

void
push_off(void)
{
  int old = intr_get();

  // disable interrupts to prevent an involuntary context
  // switch while using mycpu().
  intr_off();

  if(mycpu()->noff == 0)
    mycpu()->intena = old;
  mycpu()->noff += 1;
}

kernel/spinlock.c/pop_off

{ https://github.com/TommyWu-fdgkhdkgh/xv6-riscv/blob/xv6-riscv-rev5/kernel/spinlock.c#L103 }

• 使用 pop_off 的時候，預期已經是關掉中斷的狀態
• 使用 pop_off 的時候，假如 c->noff < 1，就表示根本沒有先呼叫過 push_off
• 假如 noff 回到 0，記得要把 intena 放回 sstatuc.SIE

void
pop_off(void)
{
  struct cpu *c = mycpu();
  if(intr_get())
    panic("pop_off - interruptible");
  if(c->noff < 1)
    panic("pop_off");
  c->noff -= 1;
  if(c->noff == 0 && c->intena)
    intr_on();
}

kernel/spinlock.c/holding

{ https://github.com/TommyWu-fdgkhdkgh/xv6-riscv/blob/xv6-riscv-rev5/kernel/spinlock.c#L74C1-L77C29 }

檢查該所的擁有者，是不是目前的這顆 CPU

// Check whether this cpu is holding the lock.
// Interrupts must be off.
int
holding(struct spinlock *lk)
{
  int r;
  r = (lk->locked && lk->cpu == mycpu());
  return r;
}

__sync_synchronize

{ https://gcc.gnu.org/onlinedocs/gcc/_005f_005fsync-Builtins.html }

在之前的筆記裏面 ( https://ithelp.ithome.com.tw/articles/10399460 ) 有提到。
這個 instruction 在 RISC-V 的實作就是 fence ( memory barrier )

note : 我們可以用 objdump kernel/kernel 來取得組合語言。

__sync_lock_test_and_set

{ https://gcc.gnu.org/onlinedocs/gcc/_005f_005fsync-Builtins.html }

__sync_lock_test_and_set(addr, new_value)
一樣是 gcc __built_in 的 function，效果如下 :

• old_value = *addr
• *addr = new_value
• return old_value

所以我們可以用一個迴圈來看能不能取用到 lock。

while(__sync_lock_test_and_set(&lk->locked, 1) != 0)

當 __sync_lock_test_and_set(&lk->locked, 1) 的回傳值是 0 的時候，就表示我們取得的 old_value 是 0，也就表示我們碰上了這個鎖沒有人取用的瞬間 ! 這時候我們就可以聲稱，我們取得了這個鎖了。

在 RISC-V 裡，會使用 instruction amoswap.w.aq 來實作。

amoswap.w.aq rd, rs2, (rs1)

• old_value = *rs1
• *rs1 = rs2
• rd = old_value

以這邊的組合語言為例
amoswap.w.aq a5, a5, (s1)

• 從 s1 指向的位址讀取出 old_value
• 把 a5 的值寫入 s1 指向的位址
• 將 old_value 交給 a5

__sync_lock_release

{ https://gcc.gnu.org/onlinedocs/gcc/_005f_005fsync-Builtins.html }

__sync_lock_release(addr)
一樣是 gcc __built_in 的 function，效果如下 :

• *addr = 0

  // 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, sync_lock_release turns into an atomic swap:
  //   s1 = &lk->locked
  //   amoswap.w zero, zero, (s1)
  __sync_lock_release(&lk->locked);

kernel/spinlock.c/acquire

{ https://github.com/TommyWu-fdgkhdkgh/xv6-riscv/blob/xv6-riscv-rev5/kernel/spinlock.c#L22 }

// Acquire the lock.
// Loops (spins) until the lock is acquired.
void
acquire(struct spinlock *lk)

這個 function 可以讓我們取用一個鎖，假如這個鎖已經被取用的話，我們就不停地 loop ( or spin )，直到我們拿到鎖為止。

  if(holding(lk))
    panic("acquire");

檢查該鎖目前的使用者是不是目前這顆 CPU。
假如這個 CPU 之前已經取用了這個鎖，然後再次呼叫 acquire 的話，就變成沒人可以解鎖了，最後導致 deadlock。

於是在這邊，xv6-riscv 乾脆用 panic 來擋住這種情況的發生。

  // Record info about lock acquisition for holding() and debugging.
  lk->cpu = mycpu();

把鎖的擁有者改為目前這顆 CPU。

Q: 為什麼進入 spinlock 的時候，需要使用 push_off 把中斷關掉呢 ?

假若現在同一個 CPU 上有兩個 process A, B，且這兩個 process 都會想要取用同一個 lock L。假如取用 spinlock 的時候，沒有取消中斷的話，那以下情況會出現 deadlock。

• A 取用 L
• A 在使用 spinlock 的時候中斷，並切換到 process B 執行
• B 進入中斷後取用 L，因為 L 正在被使用，所以開始 spin。
  • B 因為在中斷裡，所以會取消中斷
  • B 需要等待 A 釋放鎖，但 A 永遠也沒辦法起來執行
  • 互相鎖死，deadlock !!

kernel/spinlock.c/release

{ https://github.com/TommyWu-fdgkhdkgh/xv6-riscv/blob/xv6-riscv-rev5/kernel/spinlock.c#L49 }

// Release the lock.
void
release(struct spinlock *lk)

釋放這個鎖。

  if(!holding(lk))
    panic("release");

假如我們在釋放鎖的時候，發覺這顆 CPU 根本就不是這個鎖的擁有者，那表示一定是某個地方搞錯了，用 panic 來噴錯。

 // Tell 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 emits a fence instruction.
  __sync_synchronize();

在我們釋放鎖之前，希望確保釋放鎖之前的記憶體操作，也就是在 critical section 內的記憶體操作都已經能夠被其他 CPU 所觀察到了。

  // 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, sync_lock_release turns into an atomic swap:
  //   s1 = &lk->locked
  //   amoswap.w zero, zero, (s1)
  __sync_lock_release(&lk->locked);

這邊會將 lk->locked 設為 0，表示真的把這個鎖給釋放了。

kernel/spinlock.c/initlock

{ https://github.com/TommyWu-fdgkhdkgh/xv6-riscv/blob/xv6-riscv-rev5/kernel/spinlock.c#L11-L17 }

初始化一個鎖，會給鎖一個名字，來方便我們 debug。

Reference

• __sync Built-in Functions for Atomic Memory Access
  https://gcc.gnu.org/onlinedocs/gcc/_005f_005fsync-Builtins.html