30. Adopting Mutex Locks - josehu07/hux-kernel GitHub Wiki

This chapter is meant to be read before the persistence chapter of "FS Data Structures".

Concurrency is a term for any scenario where multiple running entities/events could exist at the same time and they share something. Yes, our kernel is already facing a concurrent workload, even though we only have one CPU core and we do not have multi-threading yet. Since multiple processes are time-sharing the CPU, an unfortunate timer interrupt could happen during process A's manipulation of some global data structure, scheduling another process B to run. B could be modifying that global data as well, resulting in data races.

In this chapter, we will add support of mutex locks into the system. Locks are the most common type of synchronization primitives in a concurrent system.

Main References of This Chapter

Scan through them before going forth:

• Locks chapter of the OSTEP book: basics of mutex locks
• Spinlock & sleeplock implementation of xv6 ✭

Synchronization Primitives

Three Classic Forms

There are three classic forms of synchronization primitives in concurrent programming:

1. Mutex locks: ensures mutual exclusion of critical section code protected
2. Condition variables: ensures ordering of execution among processes
3. Semaphores: semantically as powerful as both mutex locks and condition variables (i.e., could be used to implement both, if the architecture provides hardware semaphores)

Please see the referenced OSTEP chapter for necessary background knowledge.

Hardware Atomic Instructions

Let's focus on mutex locks for now. Though there are theoretically-correct software algorithms to implement locks (see the bakery algorithm for example), hardware-assisted solutions tend to be much more efficient and intuitive. Real OSes make use of the atomic hardware instructions provided by the underlying chipset architecture to implement synchronization primitives ✭.

An atomic instruction is one that does its work atomically (not being interfered by other instructions) guaranteed by the micro-architecture. One example we will use in implementing basic mutex locks is TEST_AND_SET:

old_val TEST_AND_SET(ptr, new_val):
    writes `new_val` into `*ptr`, and
    returns the `old_val` on `*ptr`, atomically

In x86, this is the XCHG instruction.

Other examples of atomic instructions include COMPARE_AND_SWAP, LOAD_LINK/STORE_CONDITIONAL pair, FETCH_AND_ADD, etc.

Spinlocks

You can think of a lock as an integer that takes the value of either 0 (unlocked) or 1 (locked), where changes to the integer value must be atomic. A lock represents the right of accessing a protected, shared resource. Definition @ src/common/spinlock.h:

/** Simple spinlock structure. */
struct spinlock {
    uint32_t locked;    /** 0 unlocked, 1 locked, changes must be atomic. */
    const char *name;   /** Lock name for debugging. */
};
typedef struct spinlock spinlock_t;


void spinlock_acquire(spinlock_t *lock);
void spinlock_release(spinlock_t *lock);

bool spinlock_locked(spinlock_t *lock);

void spinlock_init(spinlock_t *lock, const char *name);

We will try out the simplest (but not the most efficient) way of implementing a spinlock with TEST_AND_SET. The CPU loops on doing TEST_AND_SET on the lock integer indefinitely, until it succeeds in acquiring it:

acquire(lock):
    while TEST_AND_SET(lock, 1) != 0:
        continue loop

release(lock):
    lock = 0

Implementation @ src/common/spinlock.c:

/** Returns true if the lock is currently locked. */
bool
spinlock_locked(spinlock_t *lock)
{
    cli_push();
    bool locked = (lock->locked == 1);
    cli_pop();
    return locked;
}


/** x86 atomic XCHG instruction wrapper. */
static inline uint32_t
_xchgl(volatile uint32_t *ptr, uint32_t new_val)
{
    uint32_t old_val;
    asm volatile ( "lock; xchgl %0, %1"
                   : "+m" (*ptr), "=a" (old_val)
                   : "1" (new_val) );
    return old_val;
}

/** Atomically assign an uint32_t. */
static inline void
_movl(volatile uint32_t *ptr, uint32_t val)
{
    asm volatile ( "movl %1, %0" : "+m" (*ptr) : "r" (val) );
}

/**
 * Loops until the lock is acquired.
 * 
 * Should succeed immediately in Hux since we only have one CPU and any
 * process must not yield when holding a spinlock (which may cause
 * another process that gets scheduled to deadlock on spinning on the
 * lock). Hence, it basically serves as `cli_push()` for now.
 */
void
spinlock_acquire(spinlock_t *lock)
{
    cli_push();

    if (spinlock_locked(lock))
        error("spinlock_acquire: lock %s is already locked", lock->name);

    /** Spins until XCHG gets old value of "unlocked". */
    while (_xchgl(&(lock->locked), 1) != 0) {}

    /** Memory barrier, no loads/stores could cross this point. */
    __sync_synchronize();
}

/** Release the lock. */
void
spinlock_release(spinlock_t *lock)
{
    if (!spinlock_locked(lock))
        error("spinlock_release: lock %s is not locked", lock->name);

    /** Memory barrier, no loads/stores could cross this point. */
    __sync_synchronize();

    /** Atomically assign to 0. */
    _movl(&(lock->locked), 0);

    cli_pop();
}


/** Initialize the spinlock. */
void
spinlock_init(spinlock_t *lock, const char *name)
{
    lock->name = name;
    lock->locked = 0;
}

Notice that, since we only have a single-CPU, any process must not yield itself to the scheduler when holding any lock other than the ptable lock, otherwise deadlocks could happen. As a result, spinlocks are basically equivalent to cli_push()/cli_pop() pairs in the current state of Hux. Nonetheless, having the notion of spinlocks is still rewardful as it clarifies concurrency and eases future extensions to the system.

Be aware that there are many optimized ways of implementing mutex locks to improve its performance and scalability on modern machines.

Parking Locks

Spinlocks may be nice, elegant, and efficient in some low-level cases where the locks are frequently acquired & released and are held for very short period of time. In other cases, spinning the CPU on a variable wastes a lot of CPU time (and may even be unacceptable if we only have one CPU core).

We introduce a higher-level lock which is called a parking lock (or blocking lock, sleeplock) under the context of user processes. With this type of lock, the caller process of acquire() blocks itself if the lock is currently held by another process, and wakes up until it becomes available.

• Advantages:
  • Enables a process to give up the CPU while locking some resource up (e.g., locking up an inode before waiting for its disk I/O to finish, as we will soon see in the file system chapters)
  • Avoids wasting CPU time on some long-holding locks
• Disadvantages:
  • Blocking/Unblocking takes time, so the acquire & release operations take longer than spinlocks, hence not suited for low-level locks
  • Needs careful design about the queuing algorithm of waiters

A basic parking lock can be made up of a boolean state + a spinlock. Definition @ src/common/parklock.h:

/** Parking lock structure. */
struct parklock {
    bool locked;        /** True if locked, changes must be protected. */
    spinlock_t lock;    /** Internal spinlocks that protects `locked`. */
    int8_t holder_pid;  /** Holder process's PID. */
    const char *name;   /** Lock name for debugging. */
};
typedef struct parklock parklock_t;


void parklock_acquire(parklock_t *lock);
void parklock_release(parklock_t *lock);

bool parklock_holding(parklock_t *lock);

void parklock_init(parklock_t *lock, const char *name);

Implemention @ src/common/parklock.c:

/** Returns true if the lock is currently held by the caller process. */
bool
parklock_holding(parklock_t *lock)
{
    spinlock_acquire(&(lock->lock));
    bool held = lock->locked && (lock->holder_pid == running_proc()->pid);
    spinlock_release(&(lock->lock));

    return held;
}


/**
 * Acquire the lock, blocks (parks) the caller if the lock is currently held
 * by some other process.
 */
void
parklock_acquire(parklock_t *lock)
{
    process_t *proc = running_proc();

    spinlock_acquire(&(lock->lock));

    /**
     * Park until lock is released and I'm the first one scheduled among
     * woken up process waiting on this lock.
     */
    while (lock->locked) {
        /** Must hold ptable lock when yielding. */
        spinlock_acquire(&ptable_lock);
        spinlock_release(&lock->lock);

        proc->wait_lock = lock;
              // Add this field to the PCB in `src/process/process.h`
        process_block(ON_LOCK);
                      // Add this to the enum in `src/process/process.h`
        proc->wait_lock = NULL;

        spinlock_release(&ptable_lock);
        spinlock_acquire(&(lock->lock));
    }

    lock->locked = true;
    lock->holder_pid = proc->pid;

    spinlock_release(&(lock->lock));
}

/** Release the lock and wake up waiters. */
void
parklock_release(parklock_t *lock)
{
    spinlock_acquire(&(lock->lock));

    lock->locked = false;
    lock->holder_pid = 0;

    /**
     * Wake up all waiter process - the first one getting scheduled among
     * them will be the next one succeeding in acquiring this lock.
     */
    spinlock_acquire(&ptable_lock);
    for (process_t *proc = ptable; proc < &ptable[MAX_PROCS]; ++proc) {
        if (proc->state == BLOCKED && proc->block_on == ON_LOCK
            && proc->wait_lock == lock) {
            process_unblock(proc);
        }
    }
    spinlock_release(&ptable_lock);

    spinlock_release(&(lock->lock));
}


/** Initialize the parking lock. */
void
parklock_init(parklock_t *lock, const char *name)
{
    spinlock_init(&(lock->lock), "parklock's internal spinlock");
    lock->name = name;
    lock->locked = false;
    lock->holder_pid = 0;
}

Note that ptable_lock is a spinlock we now use to protect the global process table.

Concurrency Bugs - Deadlocks

Synchronization is complicated and many concurrency bugs could happen, of which deadlocks are one of the most dangerous types. Deadlocks have been extensively explained in many resources, such as the "Concurrency Bugs" chapter of the OSTEP book and this Wikipedia page.

For now, we take the brute-force way of avoiding deadlocks by simply disabling interrupts with cli_push() upon acquiring a lock ✭. This way, whenever a process locks some resource, timer interrupts on that CPU core goes off and no one else could be calling any acquire() to even different locks on that CPU. This is not an ideal solution for fairness and efficiency in real systems, but is sufficient for our small single-CPU kernel.

Progress So Far

Replace the temporary cli_push()/cli_pop() pairs with locks on the corresponding resources. I will not list all the places of modification since that would be too tedious. Please search for lock acquire/release calls in code to see where they are needed and how they are used.

The system should be functioning just as well as before. We have not seen cases of using parking locks yet, but they are coming soon in the file system chapters.

Current repo structure:

hux-kernel
├── Makefile
├── scripts
│   ├── gdb_init
│   ├── grub.cfg
│   └── kernel.ld
├── src
│   ├── boot
│   │   ├── boot.s
│   │   ├── elf.h
│   │   └── multiboot.h
│   ├── common
│   │   ├── bitmap.c
│   │   ├── bitmap.h
│   │   ├── debug.c
│   │   ├── debug.h
│   │   ├── intstate.c
│   │   ├── intstate.h
│   │   ├── parklock.c
│   │   ├── parklock.h
│   │   ├── port.c
│   │   ├── port.h
│   │   ├── printf.c
│   │   ├── printf.h
│   │   ├── spinlock.c
│   │   ├── spinlock.h
│   │   ├── string.c
│   │   ├── string.h
│   │   ├── types.c
│   │   └── types.h
│   ├── device
│   │   ├── idedisk.c
│   │   ├── idedisk.h
│   │   ├── keyboard.c
│   │   ├── keyboard.h
│   │   ├── sysdev.c
│   │   ├── sysdev.h
│   │   ├── timer.c
│   │   └── timer.h
│   ├── display
│   │   ├── sysdisp.c
│   │   ├── sysdisp.h
│   │   ├── terminal.c
│   │   ├── terminal.h
│   │   └── vga.h
│   ├── filesys
│   │   ├── block.h
│   ├── interrupt
│   │   ├── idt-load.s
│   │   ├── idt.c
│   │   ├── idt.h
│   │   ├── isr-stub.s
│   │   ├── isr.c
│   │   ├── isr.h
│   │   ├── syscall.c
│   │   └── syscall.h
│   ├── memory
│   │   ├── gdt-load.s
│   │   ├── gdt.c
│   │   ├── gdt.h
│   │   ├── kheap.c
│   │   ├── kheap.h
│   │   ├── paging.c
│   │   ├── paging.h
│   │   ├── slabs.c
│   │   ├── slabs.h
│   │   ├── sysmem.c
│   │   └── sysmem.h
│   ├── process
│   │   ├── layout.h
│   │   ├── process.c
│   │   ├── process.h
│   │   ├── scheduler.c
│   │   ├── scheduler.h
│   │   ├── switch.s
│   │   ├── sysproc.c
│   │   └── sysproc.h
│   └── kernel.c
├── user
│   ├── lib
│   │   ├── debug.h
│   │   ├── malloc.c
│   │   ├── malloc.h
│   │   ├── printf.c
│   │   ├── printf.h
│   │   ├── string.c
│   │   ├── string.h
│   │   ├── syscall.h
│   │   ├── syscall.s
│   │   ├── syslist.s
│   │   ├── types.c
│   │   └── types.h
│   └── init.c