134 lines
3.4 KiB
C
134 lines
3.4 KiB
C
/**
|
|
* Mutual exclusion spin locks.
|
|
* (Not mutexes as these are spinning locks).
|
|
*/
|
|
|
|
#include "stddef.h"
|
|
#include <panic.h>
|
|
#include <proc.h>
|
|
#include <riscv.h>
|
|
#include <spinlock.h>
|
|
#include <uart.h>
|
|
|
|
/**
|
|
* The aquire() and release() functions control ownership of the lock.
|
|
* To perform these operations, modern CPU's provide atomic instructions
|
|
* that prevent the cores from stepping on each other's toes, otherwise known
|
|
* as a deadlock.
|
|
*
|
|
* GCC provides a set of built-in functions that allow you to use atomic
|
|
* instructions in an architecture-independent way. These functions are
|
|
* defined in the GCC manual:
|
|
*
|
|
* See: https://gcc.gnu.org/onlinedocs/gcc/_005f_005fsync-Builtins.html
|
|
* See: https://en.wikipedia.org/wiki/Memory_barrier
|
|
*
|
|
* On RISC-V, sync_lock_test_and_set turns into an atomic swap:
|
|
* a5 = 1
|
|
* s1 = &lk->locked
|
|
* amoswap.w.aq a5, a5, (s1)
|
|
*
|
|
* On RISC-V, sync_lock_release turns into an atomic swap:
|
|
* s1 = &lk->locked
|
|
* amoswap.w zero, zero, (s1)
|
|
*
|
|
* __sync_synchronize();
|
|
*
|
|
* This function 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/locked.
|
|
* On RISC-V, this emits a fence instruction.
|
|
*/
|
|
|
|
/*
|
|
* These are from the original xv6 implementation, with only slight modifications on their return type.
|
|
*
|
|
* push_off/pop_off are like intr_off()/intr_on() except that they are matched:
|
|
* it takes two pop_off()s to undo two push_off()s. Also, if interrupts
|
|
* are initially off, then push_off, pop_off leaves them off.
|
|
*/
|
|
|
|
uint32_t push_off(void) {
|
|
int old = intr_get();
|
|
Cpu *cpu = mycpu();
|
|
|
|
intr_off();
|
|
|
|
if (cpu->noff == 0)
|
|
cpu->intena = old;
|
|
|
|
cpu->noff += 1;
|
|
return cpu->noff;
|
|
}
|
|
|
|
uint32_t pop_off(void) {
|
|
Cpu *cpu = mycpu();
|
|
|
|
if (intr_get())
|
|
PANIC("pop_off - interruptible");
|
|
|
|
if (cpu->noff < 1)
|
|
PANIC("pop_off when cpu->noff < 1");
|
|
|
|
cpu->noff -= 1;
|
|
|
|
if (cpu->noff == 0 && cpu->intena)
|
|
intr_on();
|
|
|
|
return cpu->noff;
|
|
}
|
|
|
|
void spinlock_init(spinlock_t *l) {
|
|
l->v = 0;
|
|
l->cpu = NULL;
|
|
}
|
|
|
|
__attribute__((warn_unused_result)) bool spin_trylock(spinlock_t *l) {
|
|
uint32_t old;
|
|
// old = xchg_acquire(&l->v, 1) using AMO
|
|
__asm__ volatile("amoswap.w.aq %0, %2, (%1)\n" : "=&r"(old) : "r"(&l->v), "r"(1u) : "memory");
|
|
return old == 0;
|
|
}
|
|
|
|
void spin_unlock(spinlock_t *l) {
|
|
if (!spin_is_holding(l))
|
|
PANIC("Unlocking a spinlock that is not held by the locking cpu!");
|
|
|
|
/* TODO: Replace with corresponding __atomic builtins */
|
|
__sync_lock_release(&l->v);
|
|
__sync_synchronize();
|
|
|
|
l->cpu = NULL;
|
|
pop_off();
|
|
}
|
|
|
|
/**
|
|
* Test-and-test-and-set acquire with polite spinning + exponential backoff.
|
|
*/
|
|
void spin_lock(spinlock_t *l) {
|
|
uint32_t backoff = 1;
|
|
for (;;) {
|
|
if (spin_trylock(l)) {
|
|
l->cpu = mycpu();
|
|
push_off();
|
|
return;
|
|
}
|
|
|
|
while (__atomic_load_n(&l->v, __ATOMIC_RELAXED) != 0) {
|
|
for (uint32_t i = 0; i < backoff; ++i)
|
|
__asm__ volatile("nop"); /* NOTE: Pause can be used here if supported */
|
|
if (backoff < 1u << 12)
|
|
backoff <<= 1;
|
|
}
|
|
}
|
|
}
|
|
|
|
/**
|
|
* Check whether this cpu is holding the lock.
|
|
* Interrupts must be off.
|
|
*/
|
|
bool spin_is_holding(spinlock_t *l) {
|
|
int r;
|
|
r = (l->v && l->cpu == mycpu());
|
|
return r;
|
|
}
|