Total Madness #0: Locks

This is the first post in a series about my urges to figure out the dark magics of the computer world. You see, I recently have had some free time on my hands, and I decided to spend it to scratch some itches I've had for as long as I can code (writing an OS in Rust, for instance). As I dove deeper into the dark magics, I discovered the truth about things I never really liked to assume are true (but did it anyways, for the sake of sanity, at the time).

I don't care anymore about sanity. Let's talk architectures, let's talk memory, let's talk concurrency until we drown in deadlocks, let's find out why there can never be an address 0x0, and yet there's always one. Those who read up beware: this is no place for the sane. Buckle up, for we're going towards Total Madness.

Episode 0: Locks

Let's start with an easy one: Locks. Gotcha! One of the most important lessons we'll learn here is this: absolutely nothing is as easy as it locks (pun intended). But seriously now, let's reflect on what a lock is. Ignore all the textbook stuff you may or may not know and think about what a lock would look like.

Obs: A lock is also called a Mutex, short for Mutual Exclusion.

Here are my personal initial thoughts, they come as a gross example: two siblings want to use the toothbrush they share, but obviously only one of them can use it at a time. The childish, sibling-like thing to do is to say "I'm first!" before than the other person. The rule is simple: whoever starts saying "I'm first" first, gets to use it. Now, there would be an argument to be made about mili or even nanoseconds of difference (clearly two humans cannot tell which sibling started saying it first if the time difference is mili or nanoseconds appart). Thankfully this is not an issue with typical computers as the sentence would be an instruction running on the computer, so whichever sibling's instruction runs first wins.

Here's a simple implementation of it in Rust (you don't need to know Rust to follow up, you just need to get the general idea of the snippets which should be straightforward for anyone with some general programming experience):

struct ToothbrushLock {
    locked: bool,
}

That's it! We only need a variable (locked) that says if the lock is being used, we call this locked, (locked == true) or not (locked == false). Now for the functionality part. In Rust we can write functions that belong to a type, in this case our struct ToothbrushLock like so:

impl ToothbrushLock {
    fn new() -> Self {
        Self { locked: false }
    }
}

This function returns an instance of ToothbrushLock. We call it in our main function like so:

fn main() {
    let mut tb_lock = ToothbrushLock::new();
}

We need the mut to tell rust that this is a mutable variable, since we'll need to change (mutate) it. In fact, let's do this now. We'll add a function to lock ToothbrushLock, and another function to unlock it:

impl ToothbrushLock {
    fn new() -> Self {
        Self { locked: false }
    }

    fn lock(&mut self) {
        self.locked = true;
    }
    fn unlock(&mut self) {
        self.locked = false;
    }
}

Here's how we'd use these new functions:

fn main() {
    let mut tb_lock = ToothbrushLock::new();
    tb_lock.lock();
    // brush teeth
    tb_lock.unlock();
}

This time the functions take a &mut self, which is a mutable reference to an instance of ToothbrushLock, and change the locked variable to true (when locking) and to false (when unlocking). Neat! But there's an issue with this approach. Can you spot it? Really try to figure it out on your own before reading on!

Obs: the lock() and unlock() functions can also be called acquire() and release() respectvely.

Ok, ready?

Here it is: the lock function doesn't check if the lock is already locked! This means that we can have this horrific case:

fn main() {
    let mut tb_lock = ToothbrushLock::new();

    tb_lock.lock(); // gabriel locks toothbrush
    // gabriel starts brushing teeth
    tb_lock.lock(); // nathan locks toothbrush
    // nathan starts brushing tee- OH NOOOOOOOOOOOO
    tb_lock.unlock();
}

Obs: Nathan is my brother, in case you're wondering.

This is no good! Our lock is basically doing nothing.

Spinlocks

The idea behind the solution to this issue is what most locks do: the lock() function blocks until the lock is locked, like so:

impl ToothbrushLock {
    fn new() -> Self {
        Self { locked: false }
    }

    // updated lock function!
    fn lock(&mut self) {
        while self.locked == true {} // keep looping until locked is false
        self.locked = true;
    }


    fn unlock(&mut self) {
        self.locked = false;
    }
}

This is called a Spinlock because it spins in a loop until it gets the lock, and it works really well. However, there are a couple issues with this approach, can you figure out what those are? Again, reeeeally try to figure it out on your own before moving on.

Let's check out our usage from before. What happens when Nathan tries to lock tb_lock now?

fn main() {
    let mut tb_lock = ToothbrushLock::new();

    tb_lock.lock(); // gabriel locks toothbrush
    // gabriel starts brushing teeth
    tb_lock.lock(); // nathan locks toothbrush
    tb_lock.unlock();
}

It'll never make it after the second tb_lock.lock() // nathan locks toothbrush, because this lock() waits until locked == false, which it will never be since it needs unlock to be called, and unlock doesn't get called until after this lock. We've reached the infamous Deadlock! A deadlock occurs when a resource tries to lock() something that will never unlock. We won't go into much detail regarding deadlocks

Now you must be thinking: "Gabe, you're a moron! You just create another thread for Nathan!", and you'd be right about one of two things there. We didn't talk about threads (yet!), and so let's assume that in our current tooth brushing world there is no such thing as a thread (yet!!). Our computer can only run a single instruction at a time, which begs the question: "Then we don't need locks at all, right?". You see, just because we don't run two things at the same time it doesn't mean that our computer can't pretend like it does. Yes sure, our computer doesn't have threads, but you know what it does have? Interrupts!

Interrupts: a lock's nightmare!

If you know me, you know I absolutely hate interrupts. I mean really, they're so annoying! They think they're so important with their news they think everyone can jus-

Interrupt:

A KEY HAS BEEN PRESSED DEAL WITH IT RIGHT NOW

Ass. Mr. Rude Interrupt

The above is a good example of an interrupt. An interrupt is the processor's way of letting you know that there's important priority work that needs to be handled, like a key press on a keyboard. Key presses happen very rarely (even if you type 300 words per minute, that's still very slow for the processor), and so you want to deal with them as soon as possible. Almost all I/O operations can be handled with interrupts: disk reads and writes, network packets, etc.

The way I see it, an interrupt is just like another thread, because for the running program that gets interrupted, it's like the entire interrupt happened in an infinitesimal moment in time. But what does all of this mean for our spinlocks? Let's look at an example where my aunt Fefê yanks the toothbrush off my teeth to brush my counsins' teeth. Can you see the problem here?

fn main() {
    let mut tb_lock = ToothbrushLock::new();
    tb_lock.lock();
    // gabriel brushes teeth
    // <--- INTERRUPT (Fefê)
    tb_lock.unlock();
}


fn interrupt() {
    tb_lock.lock();
    // brush cousins' teeth...
}

Again we've reached a deadlock: the interrupt will never end because it's waiting for the lock to be released. However, the lock will never be released because for that to happen it needs to be unlocked by the code that was interrupted, which it'll never be because... You get the idea. How would you fix this? Again, try to think of a solution before moving on.

One thing we could do is add a function try_lock(), which is also very common to locks, to our ToothbrushLock, like so:

impl ToothbrushLock {
    fn new() -> Self {
        Self { locked: false }
    }

    fn lock(&mut self) {
        while self.locked == true {}
        self.locked = true;
    }

    fn try_lock(&mut self) -> bool {
        if self.locked == true {
            return false;
        }
        self.locked = true;
        return true;
    }

    fn unlock(&mut self) {
        self.locked = false;
    }
}

The try_lock() function returns right away with a boolean value (true or false) letting the caller know whether it could or could not lock right away. Now we can rewrite our interrupt:

fn main() {
    let mut tb_lock = ToothbrushLock::new();
    tb_lock.lock();
    // gabriel brushes teeth
    // <--- INTERRUPT (Fefê)
    tb_lock.unlock();
}


fn interrupt() {
    if tb_lock.try_lock() {
        // brush cousins' teeth...
    }
}

Now my aunt will only brush my cousins' teeth if it can lock, and will just return otherwise (perhaps she'll try again 5 minutes from now, or look for another less gross brush). This also solves our problem with my brother from earlier:

fn main() {
    let mut tb_lock = ToothbrushLock::new();
    tb_lock.lock();
    // brush teeth
    if tb_lock.try_lock() { // nathan tries to lock toothbrush
         // nathan brushes teeth
    }
    tb_lock.unlock();
}

Of course we'd need more code to have my brother and my aunt try again later if they don't get the lock, but the deadlocks are gone, which is great! However there's again another problem we've ignored. This one is a bit harder to spot, but I'll have you try to anyways, can you see it?

Ok here it is: what if...

impl ToothbrushLock {
    fn new() -> Self {
        Self { locked: false }
    }

    fn lock(&mut self) {
        while self.locked == true {}
        self.locked = true;
    }

    fn try_lock(&mut self) -> bool {
        if self.locked == true {
            return false;
        }
        // <----------------- INTERRUPT
        self.locked = true;
        return true;
    }

    fn unlock(&mut self) {
        self.locked = false;
    }
}
fn main() {
    let mut tb_lock = ToothbrushLock::new();
    if tb_lock.try_lock() { // nathan locks toothbrush
         // nathan brushes teeth
    }
}

To imagine this on our tooth brushing analogy, think about aunt Fefê's interruption like a time stopping device. So the sequence of events would be like so:

1. Nathan calls try_lock().
2. Inside try_lock(), Nathan checks if locked == false, which it is.
3. At this point, after Nathan has checked the locked but right before he locks it, aunt Fefê stops time (interrupt) and calls try_lock() herself.
4. Inside try_lock(), aunt Fefê checks if locked == false, which it is.
5. Aunt Fefê sets locked to true.
6. The interrupt ends without unlocking.
7. Nathan sets locked to true thinking it's available (which isn't, it's locked by aunt Fefê).
8. Nathan brushes tee- oh no! Two people brushing their teeth at the same time?

Of course one could say: "Well, then just make sure interrupts release all locks before they return then!", but as now professional lock designers, we can't ship our ToothbrushLock with a note saying "This is a great lock! However you have to be REEEEEEALLY careful wehn using it." I mean come n, we can surely better than that.

Atomics

Do you know what an atom is? It's been a hot topic in Chemistry for a long time, and nowadays we know a lot about them: they're tiny things that make the world around us. But did you know that atoms are not atomic? Here's a definition of atomic:

The smallest part of an element that can exist

We now know that what Chemistry and Physics call atoms are not really atoms, because they can be split apart, etc. But what does that have to do with locks, computers and code? In Systems Design, an atomic instruction is an instruction that cannot be split. You see, the issue with our try_lock() is that we need to check if locked == true and, if not, update it, all of that without being interrupted in the middle. We need this process to be atomic. Luckily, most modern computer architectures offer indivisible instructions to do that. On x86 (which is Intel's architecture) for instance, this instruction is called compareAndSwap or compareAndExchange. Here's the pseudocode for it in Rust:

fn compare_and_exchange(original: &mut bool, expected: bool, new: bool) -> {
    if *original == expected {
        *original = new;
        return true;
    }
    return false;
}

Obs: The actual compareAndExchange and compareAndSwap instructions take integer numbers instead of booleans, but as bools and ints are generally equivalent (booleans are usually implemented using ints), I've decided to use bools for the sake of simplicity in this example.

This function gets two boolean values original and expected and, if they're the same, it updates original with the value of new. Here's how we'd use it:

fn compare_and_exchange(original: &mut bool, expected: bool, new: bool) {
    if *original == expected {
        *original = new;
    }
}

fn main() {
    let mut original = false;
    compare_and_exchange(&mut original, false, true);
    println!("{original}");                         // prints "true"
}

Here's how our try_lock() would look with this function:

fn try_lock(&mut self) -> bool {
    let expected = false;
    let new = true;
    return compare_and_exchange(&mut self.locked, expected, new);
}

Obs: in rust, we'd implement actual atomics using the Atomic types. Check out the Appendix I below for an actual implementation.

There's also another interesting approach for locks that allows us to entirely ditch the try_lock function, but I believe we've had enough madness for today. The next post will prepare us with the concepts we need to understand these locks. Then we'll move on to implement them on the third post of the series.

Appendix I: Atomics in rust

Here's how to actually implement our locks in rust, using Atomic types:

use std::sync::atomic::{AtomicBool, Ordering};

struct ToothbrushLock {
    locked: AtomicBool,
}

impl ToothbrushLock {
    fn new() -> Self {
        Self {
            locked: AtomicBool::new(false),
        }
    }

    fn lock(&mut self) {
        while self.locked.load(Ordering::SeqCst) {}
        self.locked.store(true, Ordering::SeqCst);
    }

    fn try_lock(&mut self) -> bool {
        let expected = false;
        let new = true;
        match self
            .locked
            .compare_exchange(expected, new, Ordering::SeqCst, Ordering::SeqCst)
        {
            Ok(_) => return true,
            Err(_) => return false,
        }
    }

    fn unlock(&mut self) {
        self.locked.store(false, Ordering::SeqCst);
    }
}

fn main() {
    let mut tb_lock = ToothbrushLock::new();
    tb_lock.lock();
    // brush teeth
    if tb_lock.try_lock() { // nathan locks toothbrush
         // nathan brushes teeth
    }
    tb_lock.unlock();
}

---

Thank you for reading! You can find the full source code for this episode at https://github.com/gmelodie/total-madness.

References

• Operating Systems: Three Easy Pieces: I should note that I intentionally tried to mimic the writing style of this book, in which you make the reader stop and think before giving the answers. Huge shoutouts!
• Writing an OS in Rust
• Atom definition (Oxford Reference)