Chapter 27: Spinlocks

27.1 What is a Spinlock?

A spinlock is a lock where the thread simply waits (spins) in a tight loop until the lock becomes available. Unlike a mutex, the thread does not sleep. Spinlocks are appropriate when:

• The critical section is very short (a few instructions)
• The wait time is expected to be less than a context switch
• The code runs in interrupt context (cannot sleep)

27.2 Simple Spinlock

The simplest spinlock uses an atomic flag:

/* Simple spinlock */
struct spinlock {
    volatile int locked;  /* 0 = unlocked, 1 = locked */
};

void spinlock_init(struct spinlock *s) {
    s->locked = 0;
}

void spinlock_lock(struct spinlock *s) {
    while (atomic_cas(&s->locked, 0, 1)) {
        /* Spin: optionally use WFE (Wait For Event) to save power */
        asm volatile("wfe");
    }
    dmb();  /* Acquire barrier: ensure all subsequent loads/stores happen after lock */
}

void spinlock_unlock(struct spinlock *s) {
    dmb();  /* Release barrier: ensure all previous loads/stores complete before unlock */
    atomic_set(&s->locked, 0);
    asm volatile("sev");  /* Send event to wake up WFE-spinning threads */
}

27.3 Ticket Spinlock

A ticket spinlock ensures fairness by handing out tickets in order. Each thread takes a number and waits until its number is served:

/* Ticket spinlock (fair) */
struct ticket_spinlock {
    volatile uint16_t next_ticket;  /* Next ticket to hand out */
    volatile uint16_t now_serving;  /* Ticket currently being served */
};

void ticket_lock(struct ticket_spinlock *s) {
    uint16_t my_ticket = atomic_fetch_add(&s->next_ticket, 1);
    while (s->now_serving != my_ticket) {
        asm volatile("wfe");
    }
    dmb();
}

void ticket_unlock(struct ticket_spinlock *s) {
    dmb();
    atomic_fetch_add(&s->now_serving, 1);
    asm volatile("sev");
}

Ticket spinlocks guarantee FIFO ordering: threads acquire the lock in the order they arrive. This prevents starvation.

27.4 Interrupt-Safe Spinlocks

A spinlock held in a thread can deadlock if an interrupt handler on the same CPU tries to acquire the same lock. The solution: disable interrupts on the local CPU while holding the lock.

/* Spinlock with IRQ save/restore */
void spinlock_lock_irq(struct spinlock *s, uint64_t *flags) {
    *flags = local_irq_save();
    spinlock_lock(s);
}

void spinlock_unlock_irq(struct spinlock *s, uint64_t flags) {
    spinlock_unlock(s);
    local_irq_restore(flags);
}

/* Usage pattern: protect a data structure shared with interrupt handler */
struct spinlock list_lock;
struct list_head device_list;

/* Called from interrupt handler (IRQs already disabled) */
void irq_handler_add_device(struct device *dev) {
    spinlock_lock(&list_lock);
    list_add(&device_list, &dev->node);
    spinlock_unlock(&list_lock);
}

/* Called from thread context */
void thread_add_device(struct device *dev) {
    uint64_t flags;
    spinlock_lock_irq(&list_lock, &flags);
    list_add(&device_list, &dev->node);
    spinlock_unlock_irq(&list_lock, flags);
}

27.5 Read-Write Spinlocks

A read-write spinlock allows multiple readers but exclusive writers. This improves concurrency when reads are common and writes are rare:

/* Read-Write spinlock */
struct rw_spinlock {
    volatile int readers;   /* Number of current readers (-1 means writer) */
};

void rw_lock_read(struct rw_spinlock *s) {
    while (1) {
        int r = s->readers;
        if (r >= 0 && atomic_cas(&s->readers, r, r + 1)) {
            dmb();
            return;
        }
    }
}

void rw_unlock_read(struct rw_spinlock *s) {
    dmb();
    atomic_fetch_sub(&s->readers, 1);
}

void rw_lock_write(struct rw_spinlock *s) {
    while (!atomic_cas(&s->readers, 0, -1)) {
        /* Spin until no readers */
    }
    dmb();
}

void rw_unlock_write(struct rw_spinlock *s) {
    dmb();
    atomic_set(&s->readers, 0);
}

27.6 Our Implementation

Our kernel uses ticket spinlocks as the default (fair spinlocks). Simple spinlocks are used in a few low-level paths (interrupt dispatcher, scheduler). Key features:

• WFE/SEV: spinlocks use WFE (Wait For Event) and SEV (Send Event) to reduce power consumption while spinning
• Lock debugging: in development builds, spinlocks track the owner CPU, check for double-lock, and detect long hold times
• Spinlock profiling: count spin iterations to identify contention bottlenecks
• Read-Write spinlocks: for data structures with read-dominated access patterns

27.7 Exercises

27.8 Summary

Spinlocks provide mutual exclusion with busy-wait semantics, suitable for short critical sections and interrupt context. Ticket spinlocks ensure FIFO fairness. WFE/SEV reduce power during spinning. Read-write spinlocks improve concurrency for read-mostly data. Interrupt-safe variants prevent deadlocks between thread and interrupt handler by disabling local interrupts while the lock is held. Our kernel uses ticket spinlocks by default with debugging and profiling support.