DEV Community: Gabriel Cruz (he/him)

WTF is an API? (or, "Everything's a Lie")

Gabriel Cruz (he/him) — Wed, 07 Aug 2024 19:37:48 +0000

This is a rewrite of an older post of mine (this one). It bothers me that a lot of people explaining APIs throw around loads of confusing, meaningless buzzwords, to an otherwise easily explainable topic. It feels like these people are just trying to sound smart instead of explaining APIs. The reason why this post could also be called "Everything's a Lie" is because a lot of what we'll be doing is proving that most things you see around about APIs are just lies.

In this post, we'll explore the meaning and reasoning behind the idea of an API, see some examples, and talk about REST. Oh, and we'll be doing some coding as well, as always.

Shall we?

The naming

First things first, let's talk about the acronym. API stands for Application Programming Interface, what does that mean?

The important part is Interface. An interface is anything that sits between two other things. We call the USB port a USB interface because it lets the computer communicate with peripherals (or vice-versa). Interfaces are important because they enforce a protocol that both ends must speak. It doesn't matter how the mouse or the computer are built, if they communicate through USB, they should follow the USB standard. Application Programming means creating an interface for applications to talk to each other, making application programming easier.

Protocols in the computer world are a set of rules that devices should adhere to to communicate. Something like: "To adhere to the USB standard, you must send three bytes with values x, y and z, then you should wait for the other device to send value a1, etc."

e.g.: In a valid HTTP request message, the first few characters must be the method (GET, POST, DELETE, etc) followed by a whitespace, followed by a path (/users, /, etc) followed by... You get the idea.

If you have ever read anything about APIs you might be wondering: what does this have to do with HTTP or GET or POST? And the answer is: nothing! Really, nothing. In theory, there's nothing that dictates that APIs have to be implemented using HTTP.

If you've never read anything about APIs before, however, the last paragraph made no sense whatsoever. Let's rewind a bit.

APIs are like libs

To explain what I mean, let's implement a simple Rust library (or lib) to print ASCII characters enclosing text, like so:

let my_text = "hello world";
enclose(my_text, '#');

The output for the above should be:

###############
# hello world #
###############

Here's the full Rust source code for the curious:

fn enclose(text: &str, enclose_char: char) {
    println!("{}", enclose_char.to_string().repeat(text.len() + 4));

    println!("{enclose_char} {text} {enclose_char}");

    println!("{}", enclose_char.to_string().repeat(text.len() + 4));
}

fn main() {
    let my_text = "hello world";
    enclose(my_text, '#');
}

Now let's say that we want other people to use our code, for that we'd make this into a lib and the code wouldn't look much different:

pub fn enclose(text: &str, enclose_char: char) {
    println!("{}", enclose_char.to_string().repeat(text.len() + 4));

    println!("{enclose_char} {text} {enclose_char}");

    println!("{}", enclose_char.to_string().repeat(text.len() + 4));
}

We just deleted the main function and added pub to make the enclose() function public. You'd need to alter some things in the package configs as well, but the point is that if we actually want our code to be modular and usable, there are much more important changes we need to do:

pub fn enclose(text: &str, enclose_char: char) -> String {
    let horizontal_line = enclose_char.to_string().repeat(text.len() + 4);
    format!("{horizontal_line}\n{enclose_char} {text} {enclose_char}\n{horizontal_line}")
}

The important change is that we return the new enclosed string instead of printing it to the standard output. This is important because if we want people programming applications we need to make our code easily pluggable. This new version allows programmers to get the strings and do whatever they want with it. Maybe they don't want to print the string, maybe they want to plot it as a 3D model instead!

What we wrote is a library (lib, for short). Libs are collections of functions and types that help to develop something. An API is like a lib: it's code on top of which people build applications. Now, let's explore what people usually mean when they talk about APIs.

Note: "Technically," purists will say, "libs have APIs, because the API would be only the function signatures such as pub fn enclose(&str, char) -> String in our example."

Purists are bikeshedding dicks. Do not trust purists.

What people usually mean when they talk about APIs

In the early days of the internet websites were dead stupid: static HTML, manually updated from time to time.

Static HTML pages are what we call HTML that's in a file in the server (the HTTP server, also called a "web server"), which hands clients a copy of that file. Dynamic pages on the other hand contain code and style sheets, usually JavaScript and CSS respectively, that allow the client to dynamically generate the "final" HTML. With dynamic pages, the client downloads HTML templates, JS, CSS, and then generates one big HTML by crunching those three together.

Let's say we wanted to write a bot to get the news titles from your local newspaper website back in 2001. Back then, you'd probably have to download the HTML for the entire page, parse it, and spit out only the titles¹. Here's what that would look like in Python (in this case we're parsing motherfuckingwebsite.com):

import requests
import re

text = requests.get("http://motherfuckingwebsite.com/").content.decode('utf-8')

pattern = re.compile(r'<h2>(.*?)</h2>', re.DOTALL)

# Find all text between <h2> and </h2> in the HTML content
titles = pattern.findall(str(text))

for t in titles:
    print(t)

Output:

Seriously, what the fuck else do you want?
It's fucking lightweight
It's responsive
It fucking works
This is a website. Look at it.  You've never seen one before.

This approach is (1) wasteful because we have to download many characters (the entire page!) only to get a few titles and (2) the code is hard to maintain because we have to figure out where the titles are in the HTML (in this case they're on the h2 tags), and if they decide to change the layout of the website, we'd have to rewrite our bot.

So when people talk about APIs, they usually mean HTTP APIs, which is a way to facilitate getting information for your website. Let's write an API for motherfuckingwebsite.com:

from flask import Flask, jsonify
import requests
import re

app = Flask(__name__)

@app.route('/titles', methods=['GET'])
def get_titles():
    text = requests.get("http://motherfuckingwebsite.com/").content.decode('utf-8')

    pattern = re.compile(r'<h2>(.*?)</h2>', re.DOTALL)

    # Find all text between <h2> and </h2> in the HTML content
    titles = pattern.findall(str(text))

    # Return the titles as JSON
    return jsonify(titles)

if __name__ == '__main__':
    app.run(debug=True)

Here's what we do:

Get the raw HTML
Spawn a webserver of our own
Make the list of titles available in JSON by GETting /titles

If our website were called amazingwebsite.com then you'd only have to GET http://amazingwebsite.com/titles to get the JSON with the titles.

REST: Representational State Transfer

Over time people started getting clever and realized that they could make their APIs receive data from the applications/users instead of only giving it away. A canonical example is Twitter's API, which allows programmers to create bots that send data (like a bio update or a tweet) to the server.

Here's what a bio update looks like:

curl -X POST https://api.twitter.com/1.1/account/update_profile.json?name=Sean%20Cook&description=Keep%20calm%20and%20rock%20on

HTTP uses verbs/methods to allow us to do different things with a server. If we're requesting information, that's typically a GET request, but in the example above we're actually sending data to the server, so we use the POST method. The cool thing is that we can have different behaviors for the same route by using different methods:

# get data on the gmelodie account
curl -X GET mywebsite.com/accounts/gmelodie

# delete the gmelodie account
curl -X DELETE mywebsite.com/accounts/gmelodie

# update the description of the gmelodie account to newDescription
curl -X POST mywebsite.com/accounts/gmelodie?description=newDescription

That's basically what a REST API is. Again, purists will say there's much more to REST APIs, but the gist of it is: REST APIs are APIs that do different things based on the HTTP method you pass to a route.

Appendix I: Idempotency

From dictionary.cambridge.org:

An idempotent element of a set does not change in value when multiplied by itself.

In programming, a function is idempotent if, when called twice with the same parameters, the operation only happens once. This is especially interesting when building APIs. For instance, if a client makes two requests to send the same tweet, they probably don't want to post the same tweet again.

Or do they? Maybe they do! To make sure the client wants to do the same thing twice, you can add an idempotency-key field to the requests. If the server gets two identical requests to post the same tweet with the same idempotency-key, it'll disregard one of them. Now, if the server receives two identical requests to post a tweet, but with two different idempotency-keys, it'll post both tweets.

Thank you for reading!

References

RSS wasn't very popular then. ↩

Total Madness #2: Async Locks

Gabriel Cruz (he/him) — Wed, 31 Jul 2024 12:48:24 +0000

In the first episode of this series, we discussed why locks are important and the issues that come with them. Last time we unraveled the inners of the async/await concurrency model. Now, let us finally merge these two topics to explore Async Locks: a way to overcome some traditional locking issues using the async/await model. Finally, we'll explore the difference between Rust's std::sync::Mutex and tokio::sync::Mutex and how this relates to async locks.

Obs: I'll use the terms "Lock" and "Mutex" interchangeably (lock == mutex), as well as the verbs "Acquire" and "Lock" (lock == acquire). So to avoid saying "lock the lock" I'll say "acquire the lock" or "lock the mutex", just know it is all the same thing.

Episode 2: Async Locks

As a reminder, let's review our original example and see why we even need locks in the first place:

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 the other person. The rule is simple: whoever starts saying “I’m first” first, gets to use it.

A lock, or Mutex, is just a way to allow tasks to do that. In this analogy, saying "I'm first!" is analogous to mutex.lock(), so if a task acquires a mutex, all other tasks trying to acquire it have to wait until the first one is done (i.e. when it calls mutex.unlock(), or mutex.release() or whatever name the developers decided to use).

As we saw on Episode #0: Locks, this is all fun and games until we face Deadlocks, which is when tasks get stuck waiting forever on each other. Several different situations can cause a deadlock, but a very common one is interrupts. Let's see an example of interrupts causing a deadlock from that episode:

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


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

In the above example, the main() function is interrupted right after locking the toothbrush, but the interrupt() function needs to lock tb_lock as well, which causes the interrupt code to be deadlocked. This is a typical situation of: "your computer stopped working" because interrupts usually can't be themselves interrupted, so, since they can't be interrupted and are stuck, there's nothing to help the computer regain control of execution. We talked about a way to avoid this in the first post: instead of using lock(), we use try_lock(), which returns either true if it acquired the lock, or false otherwise. Either way, the function returns. It doesn't block (this is what we call a non-blocking function).

Aside: why (most) interrupts can't be interrupted

Think about a keyboard buffer: when a key gets pressed on the keyboard, the processor generates an interrupt so that the kernel can get the key from the keyboard's memory, which could very well only hold a maximum of one key) and put it in a buffer (i.e. an array/vector). If the code that copies the key gets interrupted by another key press event, the key is lost. Avoiding interrupts is called Interrupt Masking. However, some less critical interrupts can in fact be interrupted.

An async lock is an alternative to the try_lock() idea using, you guessed it, async/await. Here's more or less what we'll do to the original lock() code, can you tell why this would be better than the first approach?

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


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

Well, the first obvious advantage is that you can guarantee that a lock will be locked. I mean think about it, in this snippet of the try_lock() example, I actually hid something very bad, can you figure out what it is?

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

It's the else statement! The big downside of try_locking is that, if you can't lock(), then you just... deal with it. There are no guarantees that try_lock() will succeed, and the big advantage of async locks is that you can tell the computer: "Can I lock now? Not yet? That's alright, I'll just let someone else run, and try again later". Let's now see how an implementation of async locks would look.

Implementing an async lock

We're going to get somewhat Rust-specific, but the errors raised by the compiler will help us understand the issues and limitations of async locks. In this sense, getting a bit Rust-specific is a feature, not a bug!

First, let's use some boilerplate code. This is the code we wrote in the last post for our toothbrushing example:

mod executor;
mod task;

use executor::Executor;
use futures::pending;
use task::Task;

async fn brush_teeth(times: usize) -> String {
    for i in 0..times {
        // TODO: lock
        println!("Brushing teeth {}", i);
        pending!(); // new!
    }
    return "Done".to_string();
}

fn main() {
    let mut executor = Executor::new();

    let task_gabe = Task::new("gabe".to_string(), brush_teeth(20));
    let task_nat = Task::new("nat".to_string(), brush_teeth(30));
    let task_fefe = Task::new("fefe".to_string(), brush_teeth(100));

    executor.tasks.push(task_gabe);
    executor.tasks.push(task_nat);
    executor.tasks.push(task_fefe);

    while executor.tasks.len() != 0 {
        for task in executor.tasks.iter_mut() {
            print!("{}: ", task.name);
            task.poll();
        }
        println!("--- Went through all tasks once");

        // clean up tasks that are done
        executor.tasks.retain(|task| !task.is_done());
    }
}

Now, what we want to do is change it to have a ToothbrushLock. For this, let's start with the code we wrote in the first episode:

struct ToothbrushLock {
    locked: bool,
}

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

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

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

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

And finally, let's make the brush_teeth function use our lock:

async fn brush_teeth(brush_lock: &mut ToothbrushLock, times: usize) -> String {
    for i in 0..times {
        brush_lock.lock(); // new!
        println!("Brushing teeth {}", i);
        pending!();
        brush_lock.unlock(); // new!
    }
    return "Done".to_string();
}

fn main() {
    let mut executor = Executor::new();

    let mut brush_lock = ToothbrushLock::new(); // new! (literally)

    let task_gabe = Task::new("gabe".to_string(), brush_teeth(&mut brush_lock, 20));
    let task_nat = Task::new("nat".to_string(), brush_teeth(&mut brush_lock, 30));
    let task_fefe = Task::new("fefe".to_string(), brush_teeth(&mut brush_lock, 100));

    executor.tasks.push(task_gabe);
    executor.tasks.push(task_nat);
    executor.tasks.push(task_fefe);

// ... (rest of the code)

There's nothing async in our lock for now. Not to worry though, we'll get there soon enough. First, let's get this code to compile because as of now it doesn't. Let's see why:

error[E0597]: `brush_lock` does not live long enough
  --> src/main.rs:27:63
   |
25 |     let mut brush_lock = ToothbrushLock::new(); // new! (literally)
   |         -------------- binding `brush_lock` declared here
26 |
27 |     let task_gabe = Task::new("gabe".to_string(), brush_teeth(&mut brush_lock, 20));
   |                     ------------------------------------------^^^^^^^^^^^^^^^------
   |                     |                                         |
   |                     |                                         borrowed value does not live long enough
   |                     argument requires that `brush_lock` is borrowed for `'static`
...
45 | }
   | - `brush_lock` dropped here while still borrowed

This error happens three times, one for each call of Task::new(), but I've redacted the other two since they're the same. The problem here is that, since brush_teeth() is a Future, it doesn't run right away. Actually, it can run whenever! The compiler doesn't know when it'll run, much less when it'll finish. As a result, it can't guarantee that it will finish running before main() finishes (which is when brush_lock will be freed).

Scopes: Scopes are how the Rust compiler knows which variables get discarded/freed/dropped. A good rule of thumb is: if a variable has been declared inside brackets {}, it belongs to this "block". For example, if a variable is declared inside of a function (e.g. brush_lock inside of main()), it will belong to the function's scope, and therefore will be dropped when the scope of the function ends (a.k.a.: in line 45). Another example would be a for{...} loop. Variables declared inside loops belong to the scope of that single loop iteration.

One way around this is to use Reference Counting (RC), or, even better Atomic Reference Counting (ARC), which is the same thing but with atomic operations. Arc allows an object to have several owners, and, when the scopes of all its owners end, only then the Arc is dropped. Here's how to use it:

async fn brush_teeth(brush_lock: Arc<ToothbrushLock>, times: usize) -> String {
    for i in 0..times {
        brush_lock.lock(); // new!
        println!("Brushing teeth {}", i);
        pending!();
        brush_lock.unlock(); // new!
    }
    return "Done".to_string();
}

fn main() {
    let mut executor = Executor::new();

    let brush_lock = Arc::new(ToothbrushLock::new()); // new! (literally)

    let task_gabe = Task::new("gabe".to_string(), brush_teeth(brush_lock.clone(), 20));
    let task_nat = Task::new("nat".to_string(), brush_teeth(brush_lock.clone(), 30));
    let task_fefe = Task::new("fefe".to_string(), brush_teeth(brush_lock.clone(), 100));

    executor.tasks.push(task_gabe);
    executor.tasks.push(task_nat);
    executor.tasks.push(task_fefe);

We enclose our thing (ToothbrushLock in this case) with Arc and it should do its magic! Unfortunately for us, this is not the only issue we have to deal with. Here's what we get when we try to compile now:

error[E0596]: cannot borrow data in an `Arc` as mutable
  --> src/main.rs:14:9
   |
14 |         brush_lock.lock(); // new!
   |         ^^^^^^^^^^ cannot borrow as mutable
   |
   = help: trait `DerefMut` is required to modify through a dereference, but it is not implemented for `Arc<ToothbrushLock>`

error[E0596]: cannot borrow data in an `Arc` as mutable
  --> src/main.rs:17:9
   |
17 |         brush_lock.unlock(); // new!
   |         ^^^^^^^^^^ cannot borrow as mutable
   |
   = help: trait `DerefMut` is required to modify through a dereference, but it is not implemented for `Arc<ToothbrushLock>`

For more information about this error, try `rustc --explain E0596`.
error: could not compile `episode-2-async-locks` (bin "episode-2-async-locks") due to 2 previous errors

The problem now is that, while Arc allows a variable to be owned by multiple scopes, it doesn't allow them to mutate the data. This is one of the mechanisms that Rust has to ensure memory safety: having two or more tasks altering the same memory region can cause data races for the region. As a reminder, take a look at this example, where both taskA and taskB want to flip the value of var1: bool (to true if it is false and to false if it is true):

taskA reads var1: value is true
taskB reads var1: value is true
taskA writes to var1: value is false
taskB writes to var1: value is false

At the end of this example var1 == false, while it should be true since we flip it twise. Allowing only one mutable reference to the variable solves this issue, but also restricts the code quite a bit. Another solution that allows us to have multiple mutable references is precisely what we've been doing: locks! So now we need a way to ignore this rule, and for that, we'll use UnsafeCells:

use std::cell::UnsafeCell; // new!

pub struct ToothbrushLock {
    locked: UnsafeCell<bool>, // new!
}

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

    pub fn lock(&self) {
        unsafe {  // new! unsafe
            while *self.locked.get() == true {}
            *self.locked.get() = true;
        }
    }

    pub fn unlock(&self) {
        unsafe { // new! unsafe
            *self.locked.get() = false;
        }
    }
}

Obs: I've removed the try_lock() method since our async lock is trying to get rid of it anyway.

UnsafeCells allow us to have multiple mutable references to a variable, but, as the name suggests, it is unsafe, meaning that Rust's borrow checker won't enforce its memory safety rules to it. In fact, we have to enclose all calls to self.locked.get() in unsafe {..} blocks. unsafe {...} blocks basically tell the compiler to ignore checking for memory safety on these regions, it's our way of saying "don't worry, I know what I'm doing".

And with this change, our code compiles!!! Hooray! But wait, what is this output?

gabe: Brushing teeth 0

The code hangs after printing this first line, try to figure out what is wrong with the code. Here's the solution:

async fn brush_teeth(brush_lock: Arc<ToothbrushLock>, times: usize) -> String {
    for i in 0..times {
        brush_lock.lock();
        println!("Brushing teeth {}", i);
        brush_lock.unlock();
        pending!();
    }
    return "Done".to_string();
}

// rest of code...

The change is minimal but effective: putting the unlock() call before pending!(). Of course, we need to release the mutex before we return execution flow to the scheduler/executor because if we don't, the next task (in this case nat or fefe) will be stuck trying to lock(). But what we wanted, in the beginning, was precisely a way to return execution flow to the scheduler until we're able to lock(). In other words, this is what we want to be able to do:

async fn brush_teeth(brush_lock: Arc<ToothbrushLock>, times: usize) -> String {
    for i in 0..times {
        brush_lock.lock().await; // try to lock the mutex, continue running other tasks otherwise
        println!("Brushing teeth {}", i);
        // no need for unlock(), mutex is unlocked magically
    }
    return "Done".to_string();
}

// rest of code...

We're close, but not quite there yet. As a next step, let's keep the unlock() method, and focus on making lock() async so we can call await on it:

use futures::pending;
use std::cell::UnsafeCell;

pub struct ToothbrushLock {
    locked: UnsafeCell<bool>,
}

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

    pub async fn lock(&self) { // new! async fn
        unsafe {
            while *self.locked.get() == true {
                pending!(); // new!
            }
            *self.locked.get() = true;
        }
    }

    pub fn unlock(&self) {
        unsafe {
            *self.locked.get() = false;
        }
    }
}

With those two small adjustments, we can call the lock like so:

async fn brush_teeth(brush_lock: Arc<ToothbrushLock>, times: usize) -> String {
    for i in 0..times {
        brush_lock.lock().await;
        println!("Brushing teeth {}", i);
        brush_lock.unlock();
    }
    return "Done".to_string();
}

// rest of code...

And our new output is:

gabe: Brushing teeth 0
Brushing teeth 1
...
Brushing teeth 18
Brushing teeth 19
nat: Brushing teeth 0
Brushing teeth 1
Brushing teeth 2
Brushing teeth 3
...
Brushing teeth 28
Brushing teeth 29
fefe: Brushing teeth 0
Brushing teeth 1
Brushing teeth 2
Brushing teeth 3
Brushing teeth 4
...
Brushing teeth 98
Brushing teeth 99
--- Went through all tasks once

As you can see, we're not circling through tasks. This happens because we only yield execution on the lock() method. This means that a task that owns the lock will do:

print Brushing teeth 1
unlock the lock
lock/acquire the lock
yield execution

Then all the tasks will try to lock, but not have any success and yield execution back. When the scheduler finally goes back to the task that owns the lock, it'll repeat the sequence above. To fix that we can make unlock() also yield execution back:

use futures::pending;
use std::cell::UnsafeCell;

pub struct ToothbrushLock {
    locked: UnsafeCell<bool>,
}

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

    pub async fn lock(&self) {
        unsafe {
            while *self.locked.get() == true {
                pending!();
            }
            *self.locked.get() = true;
        }
    }

    pub async fn unlock(&self) {
        unsafe {
            *self.locked.get() = false;
            pending!(); // new!
        }
    }
}

And our call becomes:

async fn brush_teeth(brush_lock: Arc<ToothbrushLock>, times: usize) -> String {
    for i in 0..times {
        brush_lock.lock().await;
        println!("Brushing teeth {}", i);
        brush_lock.unlock().await;
    }
    return "Done".to_string();
}

// rest of code...

Yes! Now our execution is back to being:

gabe: Brushing teeth 0
nat: Brushing teeth 0
fefe: Brushing teeth 0
--- Went through all tasks once
gabe: Brushing teeth 1
nat: Brushing teeth 1
fefe: Brushing teeth 1
--- Went through all tasks once
gabe: Brushing teeth 2
nat: Brushing teeth 2
fefe: Brushing teeth 2
--- Went through all tasks once
gabe: Brushing teeth 3
nat: Brushing teeth 3
fefe: Brushing teeth 3
--- Went through all tasks once
gabe: Brushing teeth 4
nat: Brushing teeth 4
fefe: Brushing teeth 4
--- Went through all tasks once
gabe: Brushing teeth 5
nat: Brushing teeth 5
fefe: Brushing teeth 5
...

Yes! Now our async lock works. The only last detail we need to take care of is the fact that we need to call unlock(). You see, we can use the magic of Rust to make the compiler call unlock() for us whenever is appropriate to release the lock (i.e. when the lock goes out of scope). In our example, the scope of the lock is one iteration of the for loop, so the unlock would happen exactly where we put it, just before the end of a loop. To do that, we need two things:

Have a ToothbrushGuard type that is returned by lock, which will be in the for scope (i.e. a variable that is declared inside the for{..} loop and thus belongs to the scope of that iteration).
Implement the Drop trait for ToothbrushGuard, Drop tells the compiler what to do when an object goes out of scope. In our case, we want to make it unlock when ToothbrushGuard goes out of scope.

pub struct ToothbrushGuard<'guard_life> {
    mutex: &'guard_life ToothbrushLock,
}
impl<'guard_life> ToothbrushGuard<'guard_life> {
    pub fn new(mutex: &'guard_life ToothbrushLock) -> Self {
        ToothbrushGuard { mutex }
    }
}
impl Drop for ToothbrushGuard<'_> {
    // this function is called by the compiler when the ToothbrushGuard goes out of scope
    fn drop(&mut self) {
        self.mutex.unlock();
    }
}

And have lock() return a guard:

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

    pub async fn lock(&self) -> ToothbrushGuard {
        unsafe {
            while *self.locked.get() == true {
                pending!();
            }
            *self.locked.get() = true;
            ToothbrushGuard::new(self) // new!
        }
    }

    fn unlock(&self) {
        unsafe {
            *self.locked.get() = false;
            // no longer able to call pending!() here
        }
    }
}

With these things in place, we can finally call our functions the way we wanted:

async fn brush_teeth(brush_lock: Arc<ToothbrushLock>, times: usize) -> String {
    for i in 0..times {
        brush_lock.lock().await;
        println!("Brushing teeth {}", i);
    }
    return "Done".to_string();
}

Amazing! There's only one last thing to do though. You see, because the drop() function cannot be async, and unlock() is called in drop(), this means that unlock() can no longer be async (aka it can no longer call pending!() to yield execution back. As a result, the previous example does compile and works, but we're once again not circling through the tasks. A quick hack fixes that (try to do that yourself without peeking first!):

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

    pub async fn lock(&self) -> ToothbrushGuard {
        unsafe {
            pending!(); // new: return pending before!
            while *self.locked.get() == true {
                pending!();
            }
            *self.locked.get() = true;
            ToothbrushGuard::new(self)
        }
    }

    fn unlock(&self) {
        unsafe {
            *self.locked.get() = false;
        }
    }
}

Returning pending!() before the while{...} loop in lock() ensures that execution will be yielded back even if the lock was previously acquired by the task.

That's it! Async locks.

Appendix I: tokio::sync::Mutex vs. std::sync::Mutex

This is somewhat Rust-specific, but very interesting nontheless. If you're a Rust developer you might have encoutered tokio::sync::Mutex and wondered how it is different from std::sync::Mutex (I know I have).

Obs: For the curious non-Rust people, tokio is an async runtime for Rust, in other words, it's like our Executor, only much more powerful and well-written.

Let's look at Tokio's documentation for its Mutex:

This type acts similarly to std::sync::Mutex, with two major differences: lock is an async method so does not block, and the lock guard is designed to be held across .await points.
Source

Interesting! It's just like ours then. Let's think about this. Why would a Mutex not be safe to be held across .awaits? Well, one obvious answer is: if it causes deadlocks. Remember when we first tried implementing our Mutex and we got a deadlock? Allow me to refresh your memory, Our lock was:

use std::cell::UnsafeCell; // new!

pub struct ToothbrushLock {
    locked: UnsafeCell<bool>, // new!
}

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

    pub fn lock(&self) {
        unsafe {  // new! unsafe
            while *self.locked.get() == true {}
            *self.locked.get() = true;
        }
    }

    pub fn unlock(&self) {
        unsafe { // new! unsafe
            *self.locked.get() = false;
        }
    }
}

But the code got stuck after printing:

gabe: Brushing teeth 0

Because our lock was blocking, so when the nat task tried to acquire the lock (in while *self.locked.get() == true {}) it got stuck on that loop, and it never awaited, so no other task could run. This, my friends, is a deadlock.

By changing the lock() function to the following, we allowed other tasks to run, at the cost of having more context switches (because you have to circle through all tasks until you go back to the one that has the lock):

pub async fn lock(&self) -> ToothbrushGuard {
    unsafe {
        pending!();
        while *self.locked.get() == true {
            pending!();
        }
        *self.locked.get() = true;
        ToothbrushGuard::new(self)
    }
}

Suck it Tokio.

Obs: I'm kidding of course, you absolutely should not be writing your own locks if can you have the super smart Tokio people do that for you. Go do something else, i don't know, go fish or whatever.

Appendix II: Atomic Async Locks

What we did was all fun and games, but if an interrupt occurs in the middle of the code we wrote, it all goes to shit. Solving this requires atomic operations that guarantee that they won't be interrupted. We did the same thing in Episode #0: Locks:

use futures::pending;
use std::cell::UnsafeCell;
use std::sync::atomic::{AtomicBool, Ordering};

pub struct ToothbrushLock {
    locked: UnsafeCell<AtomicBool>,
}

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

    pub async fn lock(&self) -> ToothbrushGuard {
        unsafe {
            pending!();
            while (&*self.locked.get()).load(Ordering::SeqCst) == true {
                pending!();
            }
            (&*self.locked.get()).store(true, Ordering::SeqCst);
            ToothbrushGuard::new(self)
        }
    }

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

pub struct ToothbrushGuard<'guard_life> {
    mutex: &'guard_life ToothbrushLock,
}
impl<'guard_life> ToothbrushGuard<'guard_life> {
    pub fn new(mutex: &'guard_life ToothbrushLock) -> Self {
        ToothbrushGuard { mutex }
    }
}
impl Drop for ToothbrushGuard<'_> {
    fn drop(&mut self) {
        self.mutex.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!
Understanding and handling Rust mutex poisoning
How are mutexes implemented in Rust?

Total Madness #1: Async/Await

Gabriel Cruz (he/him) — Wed, 10 Jul 2024 21:36:37 +0000

In the last episode (which is also the first episode, lol) we explored a bit of the world of concurrency by talking about locks. I mean, we didn't use the word "concurrent" explicitly, but effectively that's what we were talking about.

Concurrency means multiple computations are happening at the same time.

MIT

Today we'll explore a crucial concurrency model: async/await.
Oh and don't you think I forgot about the promise I made about async locks, they're coming in the next post. First, though, we need to understand why async/await is even a thing, and how it actually works.

Episode 1: Async/Await

You might remember the gross example we used to illustrate what happens on a computer when different tasks are competing for resources. Here's a refresher:

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 the other person. The rule is simple: whoever starts saying “I’m first” first, gets to use it.

Now the word task here is an important, deliberate choice. We're talking about theoretical concepts, not what one programming language calls Task (and another would call Process, or Thread, or anything else). For us now, a task is simply a sequence of things a computer will do like add 1 to a variable or load a file from disk. For example, task1 could be updating a file while task2 would be printing to the screen. Here are the rough steps each task would need to accomplish:

Task1
1. task1 loads file from disk to memory (RAM)
2. task1 writes to file in memory
3. task1 saves file from memory to disk

Task2
1. task2 loads matrix of pixels from disk
2. task2 updates matrix of pixels
3. task2 writes matrix of pixes to screen

Because we want our computers to do a lot of things at once but have limited processing units (in our theoretical computer, we only have one processing unit!), clever computer people created the concept of multitasking, where tasks run intermittently to give the users the impression that everything is happening at once. Behind the scenes, however, the computer jiggles tasks like crazy to create this illusion. In our task1 and task2 examples from before, the sequence of instructions running could look like this:

1. task1 loads file from disk to memory (RAM)
2. task2 loads matrix of pixels from disk
3. task1 writes to file in memory
4. task1 saves file from memory to disk
5. task2 updates matrix of pixels
6. task2 writes matrix of pixes to screen

As you can see, the tasks are broken into pieces and jiggled by the processing unit. How would you design an algorithm to do that given a list of tasks?

Tasks

Ready? A first, naïve idea, is fairly straightforward: we use a queue of tasks being run. We cycle through this list and run a part of each task for a little bit of time. Then, when we reach the end of the queue, we go back to the beginning and do it all over again.

Seems simple enough, but a ton of issues can stem from this approach, as well as a ton of ways to solve them. Let's implement a simple task runner following this idea. In case you're new to the posts, the examples are in Rust, but I'll explain the non-trivial parts.

So I'm thinking that we'll eventually need to have a struct holding important information about our executor, but I have no idea what that is at this point, so I'll make an empty struct for now and focus on the methods I want it to have.

struct Executor {}

impl Executor {
    fn new() -> Self {
        Self {}
    }
}

fn main() {
    let mut executor = Executor::new();
}

Okay, we have a struct, an associated new() function/method that returns a new instance of the struct, and a way to call it. The Rust compiler complains of course: "You're not doing anything!", it says. The compiler is right, so let's do something. But, before we do anything, let's also create a Task type that our executor will hold in the queue:

// new!
struct Task {}

// new!
impl Task {
    fn new() -> Self {
        Self {}
    }
}

struct Executor {
    tasks: Vec<Task>, // new: task queue
}

impl Executor {
    fn new() -> Self {
        Self { tasks: Vec::new() } // create new empty task queue
    }
}

fn main() {
    let mut executor = Executor::new();
}

I added a Task struct and a field on our executor to hold a list of tasks (in a Vec). But still, we're not really doing anything with it. Our task should also be able to run(), so let's add a method for this:

impl Task {
    fn new() -> Self {
        Self {}
    }
    fn run(&mut self) {} // new!
}


// ... rest of code

run() takes the Task it refers to as a mutable reference (hence the &mut self as the first argument), this is because it will need to change something in the Task struct when run()ing. To run our tasks, we'll add a for loop that goes from start to finish of the list, calls run() on each task, and do that for as long as we have tasks to run:

// ... rest of code

fn main() {
    let mut executor = Executor::new();

    // new!
    while executor.tasks.len() != 0 { // while there are taks at queue
        for task in executor.tasks.iter_mut() { // go over each task at queue
            task.run(); // run task
        }
    }
}

Here we used iter_mut to get an Iterator of mutable references (remember our run() method needs to be able to mutate the struct). Now we just need to create some tasks to add to our executor:

// ... rest of code

fn main() {
    let mut executor = Executor::new();

    executor.tasks.push(Task::new()); // add task 1
    executor.tasks.push(Task::new()); // add task 2
    executor.tasks.push(Task::new()); // add task 3

    while executor.tasks.len() != 0 {
        for task in executor.tasks.iter_mut() {
            task.run();
        }
    }
}

Nice. But these tasks don't do anything! Let's give each of them a name and make them print to the screen. This is the new entire code:

struct Task {
    name: String,
}

impl Task {
    fn new(name: String) -> Self { // new: name
        Self { name: name } // new: name
    }
    fn run(&mut self) {
        println!("Hi from task: {}", self.name); // new: print to screen
    }
}

struct Executor {
    tasks: Vec<Task>,
}

impl Executor {
    fn new() -> Self {
        Self { tasks: Vec::new() }
    }
}

fn main() {
    let mut executor = Executor::new();

    // new!
    executor.tasks.push(Task::new("task1".to_string())); // add task 1
    executor.tasks.push(Task::new("task2".to_string())); // add task 2
    executor.tasks.push(Task::new("task3".to_string())); // add task 3

    while executor.tasks.len() != 0 {
        for task in executor.tasks.iter_mut() {
            task.run();
        }
    }
}

Wohoooo! Our code does something! Now the problem is that it never stops "doing something". Here's a part of the output:

Hi from task: task1
Hi from task: task2
Hi from task: task3
Hi from task: task1
Hi from task: task2
Hi from task: task3
Hi from task: task1
Hi from task: task2
Hi from task: task3
Hi from task: task1
Hi from task: task2
...

What is happening here? Going back to our original idea: the plan was to have each task run for a bit, then circle back when we got to the end of the task queue, but we also need two more things: (1) a way for the task to signal it's done and (2) remove all tasks that are done before circling back to the begining of the queue.

For the first issue, the solution is easy:

add a bool field called done to the Task struct
set the done field to false when a task is first created (inside new())
set the done field to true at the end of run()

Obs: I'll also add a simple method is_done() to check if the task is done (note that is_done() doesn't need &mut self, but rather &self since it just needs to read the struct, not mutate/change it).

Obs2: Don't stress too much about &self and &mut self, as these concepts are not too important to us.

struct Task {
    name: String,
    done: bool,
}

impl Task {
    fn new(name: String) -> Self {
        Self {
            name: name,
            done: false, // new!
        }
    }

    // new!
    fn is_done(&self) -> bool {
        self.done // returns self.done (equivalent to `return self.done;`, note that we don't put a ; at the end with this approach)
    }

    fn run(&mut self) {
        println!("Hi from task: {}", self.name);
        self.done = true; // new!
    }
}

// ... rest of the code

Now for our second issue, we can remove all tasks that are done from the tasks vector. A task is done if is_done() returns true. Rather, we'll retain() all the tasks that return false on is_done():

// ... rest of the code

fn main() {
    let mut executor = Executor::new();

    executor.tasks.push(Task::new("task1".to_string())); // add task 1
    executor.tasks.push(Task::new("task2".to_string())); // add task 2
    executor.tasks.push(Task::new("task3".to_string())); // add task 3

    while executor.tasks.len() != 0 {
        for task in executor.tasks.iter_mut() {
            task.run();
        }
        // new: clean up tasks that are done (aka retain tasks that are not done)
        executor.tasks.retain(|task| !task.is_done());
    }
}

Here's our new output:

Hi from task: task1
Hi from task: task2
Hi from task: task3

Eureka! Our executor runs the three tasks and stops running. Here's the full code for the curious:

struct Task {
    name: String,
    done: bool,
}

impl Task {
    fn new(name: String) -> Self {
        Self {
            name: name,
            done: false,
        }
    }

    fn is_done(&self) -> bool {
        self.done // returns self.done (equivalent to `return self.done;`, note that we don't put a ; at the end with this approach)
    }

    fn run(&mut self) {
        println!("Hi from task: {}", self.name);
        self.done = true;
    }
}

struct Executor {
    tasks: Vec<Task>,
}

impl Executor {
    fn new() -> Self {
        Self { tasks: Vec::new() }
    }
}

fn main() {
    let mut executor = Executor::new();

    executor.tasks.push(Task::new("task1".to_string())); // add task 1
    executor.tasks.push(Task::new("task2".to_string())); // add task 2
    executor.tasks.push(Task::new("task3".to_string())); // add task 3

    while executor.tasks.len() != 0 {
        for task in executor.tasks.iter_mut() {
            task.run();
        }
        // clean up tasks that are done
        executor.tasks.retain(|task| !task.is_done());
    }
}

Okay, but is this really what we wanted? Are we missing something? Think about it, then read on.

Async

Let's review what we wanted in the beginning:

A first, naïve idea, is fairly straightforward: we use a queue of tasks being run. We cycle through this list and run a part of each task for a little bit of time. Then, when we reach the end of the queue, we go back to the beginning and do it all over again.

We're missing the part where we run each task for a little bit of time. Our implementation runs each task to completion before moving on, but that's not what we want. What if one of the tasks took a long time to run, while the next two were super quick? The two tasks would starve waiting for the processor to run them. To fix that, we'll first make our example a bit more complicated. Here are the new tasks, see if you can understand how they work (I'll explain below):

struct Task {
    name: String,
    done: bool,
    run_counter: usize,
}

impl Task {
    fn new(name: String) -> Self {
        Self {
            name, // this is equivalent to `name: name`
            done: false,
            run_counter: 0,
        }
    }

    fn is_done(&self) -> bool {
        self.done
    }

    fn run(&mut self) {
        if self.run_counter == 100 {
            self.done = true;
            return;
        }
        self.run_counter += 1;
        println!("Hi from task: {}", self.name);
    }
}

We added a field called run_counter that starts with zero and is incremented every time we call run(). When the counter is 100 and we call run(), the done field is set to true, and the task returns. Then our executor will clean it up since is_done() == true. What this effectively does is make every task print "Hi from task {name}" 100 times. For our purposes, this simulates the task being run partially every time we call run() on it.

Ideally, however, we want our tasks to be general and flexible, that is, we want to create a task and pass a function that it'll execute, rather than having it hardcoded in the run() method. To do that, let's go back to our tooth-brushing example from the last post.

Let's say Aunt Fefê brushes her teeth exactly 100 times, she's a very meticulous lady! Nathan, however, is not as clean, he brushes his teeth 30 times, and I'll brush mine 20 times. How would this look in terms of code?

First, we create a function that takes in the number of times a person brushes their teeth:

fn brush_teeth(times: usize) {
    for i in 0..times {
        println!("Brushing teeth {}", i);
    }
}

Now, we to make our run() function execute the brush_teeth() function. There are two ways to do that in Rust: closures and function pointers. The former requires way too much magic (perhaps a topic for a future post?). Here's how we'd adjust our Task type to use function pointers:

struct Task {
    name: String,
    done: bool,
    max_runs: usize, // new!
    run_counter: usize,
    func: fn(usize), // new: f is a variable of type function pointer
}

impl Task {
    // f is a pointer to a fn that takes a usize as first (and only) argument and returns nothing
    fn new(name: String, max_runs: usize, f: fn(usize)) -> Self {
        Self {
            name,
            done: false,
            max_runs, // new!
            run_counter: 0,
            func: f, // new!
        }
    }

    fn is_done(&self) -> bool {
        self.done
    }

    fn run(&mut self) {
        if self.run_counter == self.max_runs { // new: run self.max_runs times
            self.done = true;
            return;
        }
        self.run_counter += 1;

        (self.func)(self.run_counter); // new!
                                       // old: println!("Hi from task: {}", self.name);
    }
}

fn brush_teeth(times: usize) {
    for i in 0..times {
        println!("Brushing teeth {}", i);
    }
}

struct Executor {
    tasks: Vec<Task>,
}

impl Executor {
    fn new() -> Self {
        Self { tasks: Vec::new() }
    }
}

fn main() {
    let mut executor = Executor::new();

    let gabe = Task::new("gabe".to_string(), 20, brush_teeth);
    let nathan = Task::new("nathan".to_string(), 30, brush_teeth);
    let fefe = Task::new("fefe".to_string(), 100, brush_teeth);

    executor.tasks.push(gabe);
    executor.tasks.push(nathan);
    executor.tasks.push(fefe);

    while executor.tasks.len() != 0 {
        for task in executor.tasks.iter_mut() {
            task.run();
        }
        // clean up tasks that are done
        executor.tasks.retain(|task| !task.is_done());
    }
}

Summary of the changes:

Added a func field that will hold the function pointer to the Task struct.
Added a max_runs field that will hold the number of times to run brush_teeth.
Added an f and max_runs as inputs to the new() function.
Made run() call (self.func), effectively executing the function that the task holds.
Finally, we changed the call to executor.tasks.push(Task::new(...)) to include the brush_teeth function pointer and max_runs.

You might've noticed that this causes a new issue: Aunt Fefê brushes her teeth 5050 times! Why is that? The run() function is the culprit:

fn run(&mut self) {
    if self.run_counter == self.max_runs {
        self.done = true;
        return;
    }
    self.run_counter += 1;

    (self.func)(self.run_counter); // new!
}

The issue is that run() calls self.func, which is brush_teeth(), 100 times, but each time brush_teeth() runs, it receives run_counter as an argument. In the first call, run_counter is zero, so Aunt Fefê will brush her teeth one time. The second call will have run_counter == 2, making her brush twice. In the end, she'll brush her teeth 100 times in a single call! Adding all of those together gives us 5050 brushes when we wanted only 100 (you can thank Gauss for the calculations here). The fix is as simple as:

fn run(&mut self) {
    if self.run_counter == self.max_runs {
        self.done = true;
        return;
    }
    self.run_counter += 1;

    (self.func)(1); // fixed!
}

This looks good, but our executor is still way too limited. For starters, our Task still very much depends on the func signature we're passing. What if we wanted to run different tasks? For instance, if I'm brushing my teeth (brush_teeth(20)) while Nathan does the dishes (do_dishes(10, 20))? Now we have a problem, because these functions have different signatures (brush_teeth(usize) and do_dishes(usize, usize)), but our Task struct can only hold fn(usize), not fn(usize, usize), and certainly not both! We need an even more general and flexible approach. Enter Futures!

Note: This next section will be a bit Rust-specific, but bear with me as these concepts are important to really understand async. Also, we'd have to go through this language-specific part ragardless of the language we were using anyway.

Futures

Ever wonder what the future looks like? Here it is:

pub trait Future {
    type Output;
    fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output>;
}

But what are we even looking at here? First of all, let's talk traits. Traits are what other programming languages like Java refer to as an Interface (although there might be slight differences between those definitions). In Rust, traits are a way to define general characteristics a type needs to fulfill in order to be considered "something".

An example is in order: let's say a general characteristic a Person needs to fulfill in order to be considered a Sibling is the ability to annoy another Sibling. This is how it would look in Rust:

trait Sibling {
    fn annoy(&mut self, other: &dyn Sibling);
}

struct Person {
    name: String,
}

impl Person {
    fn new(name: String) -> Self {
        Self { name }
    }
}

impl Sibling for Person {
    fn annoy(&mut self, other: &dyn Sibling) {
        println!("I am {} and I'm annoying you!", self.name);
    }
}

fn main() {
    let mut gabe = Person::new("gabriel".to_string());
    let nathan = Person::new("nathan".to_string());

    gabe.annoy(&nathan);
}

This is good because Person is not the only type that can be Sibling, but any type that implements the annoy function. By our definition, any type MyType that implements all the functions specified in Sibling (impl Sibling for MyType) is a Sibling. Say we had an Elephant struct. As long as we corrently implement all the functions that Sibling requires, with an impl Sibling for Elephant clause, then the Elephant struct could be a Sibling as well!

This is very useful especially when we want to create functions that take or return different types. Remember our problem of Task receiving functions of both fn(usize) and fn(usize, usize)? We could just have it receive a Future and it'd be able to receive different types, as long as they're Futures.

Now let's go back to the Future trait:

pub trait Future {
    type Output;
    fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output>;
}

Here we're basically saying: "Any type that implements the poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output> function is a Future".

Obs: Another important thing to note is the Output type inside the trait. As every task/job/future will have a different output/return type, we need to specify what the output of our Future will be. This will make more sense as we impl Future for Task, so don't worry too much about it for now.

You may be wondering what the poll function is and what it does. Great thinking! Let's review that next.

Poll

Remember that in our original tooth brushing implementation we had to return every time we wanted to tell the executor "I'm done doing a little work"? Well, polling is a better way to do exactly that. The idea is simple:

On the executor side we poll Futures;
On the Future side we return one of two possible answers:
1. Poll::Pending: "I did some work but there's still more"
2. Poll::Ready(T): "I did some work (or not) and I'm all done! Here's the output T"

Poll is an enum (not to be mistaken with the function poll that returns a variable of the type enum Poll). An enum is basically a struct that represents different options, in this case, either Ready or Pending. For reference, here's the source code for the Poll enum:

pub enum Poll<T> {
    Ready(T),
    Pending,
}

This is a good time to stop and appreciate how much we've covered so far: a lot! Come back later if you need to. Also, it might be a good idea to code along. It can be hard to understand things like the need for Poll and Future (and even traits) without actually writing code.

*clears throat*

Let's continue.

An async implementation of our executor

Now let's try to use Poll and Future to solve our problem. First, we'll change our Task struct to hold a Future instead of a function pointer.

pub struct Task {
    name: String,
    done: bool,
    future: Pin<Box<dyn Future<Output = String>>>,
}

And our new() function will take in a future as well:

pub fn new(name: String, future: impl Future<Output = String> + 'static) -> Self {
    Self {
        name,
        done: false,
        future: Box::pin(future),
    }
}

Again, we need to do that because a function pointer has a strict function signature (like fn(usize), which needs to be a function that takes exactly one usize and returns "nothing"). In other words, all Tasks will need to have the same function signature, while with Futures that's not the case.

Obs: Let's accept the concepts of "nothing", Pin, Box, and the dyn keyword as things we need to have for our code to work. We can go into detail about why those are important in a later post.

Now we can write a poll method for our Task struct:

pub fn poll(&mut self) -> String {
    let binding = futures::task::noop_waker();
    let mut cx = Context::from_waker(&binding);

    match self.future.as_mut().poll(&mut cx) {
        Poll::Ready(output) => {
            self.done = true;
            output
        }
        Poll::Pending => "Task not finished".to_string(),
    }
}

Our poll() method in turn calls poll() on a mutable reference to our future (hence the .as_mut() there). Another thing to note is that the poll() method on Futures takes in a Context, but for now we're just using a placeholder from noop_waker() that holds no information whatsoever.

Now for the important part: we do a match (which is like a switch/case or an if/else clause, but much more powerful) and, if the return result of the poll() function is Poll::Ready(output) we set self.done = true, take that output and return it ourselves. Otherwise, if the return result is Poll::Pending we return a string saying we're not done.

Obs: We will not go into pattern matching and how this makes match incredible in this post, again, let's save that discussion for the future.

In our main function, things are pretty much the same:

fn main() {
    let mut executor = Executor::new();

    while executor.tasks.len() != 0 {
        for task in executor.tasks.iter_mut() {
            task.poll();
        }
        // clean up tasks that are done
        executor.tasks.retain(|task| !task.is_done());
    }
}

The only change was task.run() to task.poll(). But now you may be thinking: "Wait what??? We went through all that work for this?! This is stupid.". Well, not quite. You see, there's one thing missing in our main(), can you spot what it is? I'll give you a hint, it's actually three things.

We're missing... tasks! We never spawn any! How about we do that:

fn main() {
    let mut executor = Executor::new();

    let task1 = Task::new("first_task".to_string(), future);
    executor.tasks.push(task1);

    while executor.tasks.len() != 0 {
        for task in executor.tasks.iter_mut() {
            task.poll();
        }
        // clean up tasks that are done
        executor.tasks.retain(|task| !task.is_done());
    }
}

Okay, now we have a task on our executor, but trying to run this code gives us:

➜  cargo run
   Compiling episode-1-async v0.1.0
error[E0425]: cannot find value `future` in this scope
  --> src/main.rs:10:53
   |
10 |     let task1 = Task::new("first_task".to_string(), future);
   |                                                     ^^^^^^ not found in this scope

For more information about this error, try `rustc --explain E0425`.
error: could not compile `episode-1-async` (bin "default") due to 1 previous error

We never specify a future! Come to think of it, we haven't talked about how to create a future. Here's how: imagine we have a function we want the task to run. All we need to do is add the async keyword to that function and some await statements inside it to tell the compiler where it should return Poll::Pending (aka saying "I'm done working a little"), like so:

// new!
async fn brush_teeth(times: usize) -> String {
    for i in 0..times {
        println!("Brushing teeth {}", i);
    }
    return "Done".to_string();
}

fn main() {
    let mut executor = Executor::new();

    let future = brush_teeth(10); // new!
    let task1 = Task::new("first_task".to_string(), future);
    executor.tasks.push(task1);

    while executor.tasks.len() != 0 {
        for task in executor.tasks.iter_mut() {
            task.poll();
        }
        // clean up tasks that are done
        executor.tasks.retain(|task| !task.is_done());
    }
}

This code runs just fine, but we need a final touch. Can you figure out what it is? Hint: try to figure out what the output of the following code will be versus what it should be:

async fn brush_teeth(times: usize) -> String {
    for i in 0..times {
        println!("Brushing teeth {}", i);
    }
    return "Done".to_string();
}

fn main() {
    let mut executor = Executor::new();

    let future = brush_teeth(10);
    let task1 = Task::new("first_task".to_string(), future);
    executor.tasks.push(task1);

    while executor.tasks.len() != 0 {
        for task in executor.tasks.iter_mut() {
            task.poll();
        }
        println!("Went through all tasks once"); // new!

        // clean up tasks that are done
        executor.tasks.retain(|task| !task.is_done());
    }
}

The output is:

Brushing teeth 0
Brushing teeth 1
Brushing teeth 2
Brushing teeth 3
Brushing teeth 4
Brushing teeth 5
Brushing teeth 6
Brushing teeth 7
Brushing teeth 8
Brushing teeth 9
Went through all tasks once

But it should be:

Brushing teeth 0
Went through all tasks once
Brushing teeth 1
Went through all tasks once
Brushing teeth 2
Went through all tasks once
Brushing teeth 3
Went through all tasks once
Brushing teeth 4
Went through all tasks once
Brushing teeth 5
Went through all tasks once
Brushing teeth 6
Went through all tasks once
Brushing teeth 7
Went through all tasks once
Brushing teeth 8
Went through all tasks once
Brushing teeth 9
Went through all tasks once

One way to let our executor know we're done running a little is to use the pending!() macro from the futures crate. A crate is a library in Rust. A library is a collection of utilities (functions, structs, traits, enums, etc.) you can use in your code. Here's how we'll use this:

use futures::pending; // import the pending!() macro

async fn brush_teeth(times: usize) -> String {
    for i in 0..times {
        println!("Brushing teeth {}", i);
        pending!(); // new: I'm done with "a little work" (aka return Poll::Pending)
    }
    return "Done".to_string(); // I'm done with all the work (aka return Poll::Ready("Done")
}

The use futures::pending line imports the pending!() macro. A macro is used like a function, so we can see it as that (see Appendix I for more about Rust macros). Another way of having brush_teeth() return after "a little" work is done would be to have a type BrushTeethFuture and implement the Future trait on it (impl Future for BrushTeethFuture) aka implement the poll() function which would return Poll::Pending after a single brush. In fact, that's a good exercise for the reader: try to implement Future for a struct BrushTeethFuture, put it inside our Task, and have the Executor run it and get the expected result.

Now let's unfold what the pending!() macro actually does. Here's the source code for it:

use core::pin::Pin;
use futures_core::future::Future;
use futures_core::task::{Context, Poll};

/// A macro which yields to the event loop once.
///
/// This is equivalent to returning [`Poll::Pending`](futures_core::task::Poll)
/// from a [`Future::poll`](futures_core::future::Future::poll) implementation.
/// Similarly, when using this macro, it must be ensured that [`wake`](std::task::Waker::wake)
/// is called somewhere when further progress can be made.
///
/// This macro is only usable inside of async functions, closures, and blocks.
/// It is also gated behind the `async-await` feature of this library, which is
/// activated by default.
#[macro_export]
macro_rules! pending {
    () => {
        $crate::__private::async_await::pending_once().await
    };
}

#[doc(hidden)]
pub fn pending_once() -> PendingOnce {
    PendingOnce { is_ready: false }
}

#[allow(missing_debug_implementations)]
#[doc(hidden)]
pub struct PendingOnce {
    is_ready: bool,
}

impl Future for PendingOnce {
    type Output = ();
    fn poll(mut self: Pin<&mut Self>, _: &mut Context<'_>) -> Poll<Self::Output> {
        if self.is_ready {
            Poll::Ready(())
        } else {
            self.is_ready = true;
            Poll::Pending
        }
    }
}

Phew! This may look like a mess, but it's actually pretty simple. Here's the breakdown:

There's a struct PendingOnce that holds an is_ready boolean field.
The Future trait is implemented for PendingOnce.
When poll() is called on PendingOnce:
- If is_ready == false: set it to true and return Poll::Pending.
- If is_ready == true: return Poll::Ready(()).
There's a function pending_once() that returns an instance of the PendingOnce struct with the is_ready field set to false. Much like our Task::new() and Executor::new() functions that create initialized structs.

What all of this effectively does is create a type (a struct) that returns Poll::Pending when first poll()ing, and after that it'll always return Poll::Ready (hence the name PendingOnce). The pending!() macro calls pending_once().await, which will make the future run. That's all await is.

And voilà! Here's our output now:

Brushing teeth 0
Went through all tasks once
Brushing teeth 1
Went through all tasks once
Brushing teeth 2
Went through all tasks once
Brushing teeth 3
Went through all tasks once
Brushing teeth 4
Went through all tasks once
Brushing teeth 5
Went through all tasks once
Brushing teeth 6
Went through all tasks once
Brushing teeth 7
Went through all tasks once
Brushing teeth 8
Went through all tasks once
Brushing teeth 9
Went through all tasks once
Went through all tasks once

As a final exercise, try to figure out why Went through all tasks once appears twice in the end.

Now of course there is one last thing (I promise) for us to do: solve our original toothbrushing problem. For that, all we need to do is add some tasks. Here's what that would look like:

fn main() {
    let mut executor = Executor::new();

    let task_gabe = Task::new("gabe".to_string(), brush_teeth(20));     // new: gabe + brush_teeth(20)
    let task_nat = Task::new("nat".to_string(), brush_teeth(30));       // new: nat + brush_teeth(30)
    let task_fefe = Task::new("fefe".to_string(), brush_teeth(100));    // new: fefe + brush_teeth(100)

    // new: push tasks
    executor.tasks.push(task_gabe);
    executor.tasks.push(task_nat);
    executor.tasks.push(task_fefe);

    while executor.tasks.len() != 0 {
        for task in executor.tasks.iter_mut() {
            print!("{}: ", task.name); // new: print task.name
            task.poll();
        }
        println!("--- Went through all tasks once"); // new: "--- " for better readability

        // clean up tasks that are done
        executor.tasks.retain(|task| !task.is_done());
    }
}

Here's the output for that code. Note that the executor cycles through the three tasks, but as long as gabe finishes, then only nat and fefe are alternating, until when there's only fefe left and it runs forever:

gabe: Brushing teeth 0
nat: Brushing teeth 0
fefe: Brushing teeth 0
--- Went through all tasks once
gabe: Brushing teeth 1
nat: Brushing teeth 1
fefe: Brushing teeth 1
--- Went through all tasks once
gabe: Brushing teeth 2
nat: Brushing teeth 2
fefe: Brushing teeth 2
--- Went through all tasks once
gabe: Brushing teeth 3
nat: Brushing teeth 3
fefe: Brushing teeth 3
--- Went through all tasks once
gabe: Brushing teeth 4
nat: Brushing teeth 4
fefe: Brushing teeth 4
--- Went through all tasks once
gabe: Brushing teeth 5
nat: Brushing teeth 5
fefe: Brushing teeth 5
--- Went through all tasks once
gabe: Brushing teeth 6
nat: Brushing teeth 6
fefe: Brushing teeth 6
--- Went through all tasks once
gabe: Brushing teeth 7
nat: Brushing teeth 7
fefe: Brushing teeth 7
--- Went through all tasks once
gabe: Brushing teeth 8
nat: Brushing teeth 8
fefe: Brushing teeth 8
--- Went through all tasks once
gabe: Brushing teeth 9
nat: Brushing teeth 9
fefe: Brushing teeth 9
--- Went through all tasks once
gabe: Brushing teeth 10
nat: Brushing teeth 10
fefe: Brushing teeth 10
--- Went through all tasks once
gabe: Brushing teeth 11
nat: Brushing teeth 11
fefe: Brushing teeth 11
--- Went through all tasks once
gabe: Brushing teeth 12
nat: Brushing teeth 12
fefe: Brushing teeth 12
--- Went through all tasks once
gabe: Brushing teeth 13
nat: Brushing teeth 13
fefe: Brushing teeth 13
--- Went through all tasks once
gabe: Brushing teeth 14
nat: Brushing teeth 14
fefe: Brushing teeth 14
--- Went through all tasks once
gabe: Brushing teeth 15
nat: Brushing teeth 15
fefe: Brushing teeth 15
--- Went through all tasks once
gabe: Brushing teeth 16
nat: Brushing teeth 16
fefe: Brushing teeth 16
--- Went through all tasks once
gabe: Brushing teeth 17
nat: Brushing teeth 17
fefe: Brushing teeth 17
--- Went through all tasks once
gabe: Brushing teeth 18
nat: Brushing teeth 18
fefe: Brushing teeth 18
--- Went through all tasks once
gabe: Brushing teeth 19
nat: Brushing teeth 19
fefe: Brushing teeth 19
--- Went through all tasks once
gabe: nat: Brushing teeth 20
fefe: Brushing teeth 20
--- Went through all tasks once
nat: Brushing teeth 21
fefe: Brushing teeth 21
--- Went through all tasks once
nat: Brushing teeth 22
fefe: Brushing teeth 22
--- Went through all tasks once
nat: Brushing teeth 23
fefe: Brushing teeth 23
--- Went through all tasks once
nat: Brushing teeth 24
fefe: Brushing teeth 24
--- Went through all tasks once
nat: Brushing teeth 25
fefe: Brushing teeth 25
--- Went through all tasks once
nat: Brushing teeth 26
fefe: Brushing teeth 26
--- Went through all tasks once
nat: Brushing teeth 27
fefe: Brushing teeth 27
--- Went through all tasks once
nat: Brushing teeth 28
fefe: Brushing teeth 28
--- Went through all tasks once
nat: Brushing teeth 29
fefe: Brushing teeth 29
--- Went through all tasks once
nat: fefe: Brushing teeth 30
--- Went through all tasks once
fefe: Brushing teeth 31
--- Went through all tasks once
fefe: Brushing teeth 32
--- Went through all tasks once
...

Appendix I: Rust Macros

Macros are processed before the actual code is compiled, and thus is an effective way to include and alter source code before compilation. On our pending_once example, the pending!() macro is defined as follows:

#[macro_export]
macro_rules! pending {
    () => {
        $crate::__private::async_await::pending_once().await
    };
}

This roughly means that when we call it in our code, the compile will replace pending!() with futures::__private::async_await::pending_once().await. So, when compiled, our code actually looks like this:

use futures::pending;

async fn brush_teeth(times: usize) -> String {
    for i in 0..times {
        println!("Brushing teeth {}", i);
        futures::__private::async_await::pending_once().await;
    }
    return "Done".to_string(); // I'm done with all the work
}

In this case, the macro is a mere and simple convenience, but they can be incredibly powerful. For more information check out The Little Book of Rust Macros.

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!
The Little Book of Rust Macros

Total Madness #0: Locks

Gabriel Cruz (he/him) — Wed, 03 Jul 2024 18:07:16 +0000

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:

Nathan calls try_lock().
Inside try_lock(), Nathan checks if locked == false, which it is.
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.
Inside try_lock(), aunt Fefê checks if locked == false, which it is.
Aunt Fefê sets locked to true.
The interrupt ends without unlocking.
Nathan sets locked to true thinking it's available (which isn't, it's locked by aunt Fefê).
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)

6 tips for your developer resume

Gabriel Cruz (he/him) — Fri, 19 Feb 2021 14:10:47 +0000

1. It should look alike

When you shop at an e-commerce store you expect it to look like Amazon or Ebay and there's a reason for that: we are lazy people. When you're browsing for a new pair of pants you don't want to stop and learn how to browse every particular e-commerce website. In the same way, an employer doesn't want to learn how your resume is structured (especially considering they have hundreds of others to go through). Make their life easier. Use a somewhat standard software engineer template.

Credits: "Don't make me think", Steve Krug

2. Write an initial version

All the tips mentioned here won't work unless you have an initial version of your resume. I know, you want to get it right the first time. Well, you won't. Begin with a good template and improve from there.

3. Get it dirty

I know we're in the middle of a global pandemic, but the best thing you can do to improve your resume is print it out and send it to as many people as possible. Now I know this could be a sanitary issue, so you better email it instead.

Seriously, though, getting feedback is really important. Mostly because what your resume is supposed to do is leave a good impression on an employer. Feedback helps you understand the impressions people have when they look at your resume.

Send it to your parents, past employers, work or student colleagues. Everyone.

4. Take feedback with a grain of salt

Feedback always comes from a particular perspective. Some people will say you should put your name in the center of the page, others will tell you to right-justify and others will go as far as to say, god forbid, that left-justified names are amazing.

Now where your name goes is no big deal, the important thing is that you absolutely need to have your name at the top of your resume. These are the things you should be worrying about.

Another good tip here is to pay more attention to comments that are similar. If Bob hates your font and thinks you need to add an "Experience" section where Alice loves your font but also thinks you need an "Experience" section, then use whatever font you like but include the damn "Experience" section, because that is probably more important than your font being Arial 12 or Sans Serif 10.34.

The more feedback you have, the easier it is to take those decisions (because you have more outside, unbiased information.

5. Not everyone's gonna dig it

Some will say it has too much information, some will say there's too little. Bob will hate the fonts, Alice will love them. Might as well face it: not everyone's gonna dig your resume.

The only person that has to completely like your resume from top to bottom is you, so stop trying to make it perfect to everybody. Instead, make it okay to everybody and awesome to you.

6. It should look like you

Remember I told you to make your resume similar to others? Well, now that you've taken feedback from all sorts of different people and analyzed it to figure out what of it is important and what is subjective, you are free to go crazy on the parts that are subjective and really make this resume your own. If you're a designer, include colors and change the layout to show you know how to design a good resume. The resume should look professional and like others, but it should also look like you! It is you, after all.

My ideal resume

I thought it'd be a good idea for me to share my personal preferences for a software engineer resume. This is the stuff I tell you to take with a grain of salt, so please do so.

Big name on top of the page and contact information right under (Github, Linkedin and email are a MUST).
Education: Put this first if you have some really important education experience like a college degree. This shouldn't take too much space, the employer just wants to know whether you have a course, they don't care a lot about your grades (unless it's an academic role).
(Work) Experience: by far the most important part of your resume. Use bullet points:
3.1. What/how was the experience
3.2. What you did (include technologies)
3.3. What impact you had (people love numbers, especially big ones!)
Skills: This is where you put a lot of keywords for ATSs (Applicant Tracking Systems) to classify you. Include the following:
4.1. Programming languages
4.2. Tools (frameworks and other programs used for development)
4.3. Natural languages (the languages you speak)
Achievements/Awards: Small optional section where you add in any relevant prizes or distinctions you got.

Other quick tips

Keep your resume to one page.
No pictures of you on your resume. Ever.
No progress bars to show experience, they are confusing. Be specific, instead, say how long have you been using a certain technology.
Don't clutter your resume with irrelevant information just to fill the page, having blank spaces on your resume is not necessarily a bad thing.

Resources and further readings

Here's my resume in case you want to have a look (contact me if you feel like sharing your feedback :)
Twitter thread on how to improve your resume depending on how much time you have (credits to Randall Kanna)
I love LaTeX and always use it to write my resumes. More specifically, I use Overleaf to edit my resume online and quickly compile the LaTeX code.
How to tweak your resume to beat ATSs

Remote team building: online scavenger/treasure hunt (without the bullshit)

Gabriel Cruz (he/him) — Mon, 07 Dec 2020 17:30:35 +0000

This post exists because I spent the last 30 minutes trying to find a post that only teaches you to play scavenger hunt online for remote team building, without the 30 paragraphs of bullshit no one is interested in.

Pick a letter or theme
Give everybody a couple minutes to find as many items starting with that letter or corresponding to the theme as possible
Go through each person's items, each unique item (that the person has but nobody else has it) gives them a point
The person with the most points wins

Demystifying Computers: I/O Devices

Gabriel Cruz (he/him) — Wed, 28 Oct 2020 16:11:24 +0000

This post is part of a series where I try to dissect computers in just enough detail so you can understand the "magic" that goes on behind the curtains when you write a "hello world" program or open up a browser.

In the last post we were talking about RAM memory and how it's different than HDDs and SSDs. The difference is: HDDs and SSDs are input and output devices.

Input and Output devices, frequently called I/O devices, are all around us, and most of what we think as "a computer" is actually just a bunch of I/O devices. To name a few: hard drives, mouses, keyboards, monitors, printers, projectors, sensors, microphones and speakers are all I/O devices.

Now the first thing to realize here is that I/O devices are very different, and I'm not only talking about how a microphone is different than a printer, but how different microphones can be when compared to each other. Just think of how different a professional ASMRtist's mic looks when compared to mine. Just as they look different, they operate differently. But you don't care about that, right? I mean, you want every microphone to be plug-and-play. That's the first challenge with I/O devices: handle all their different types and standards.

Controllers

I/O Controllers (IOC) are pieces of hardware that, you guessed it, control the I/O devices. They are responsible for sending and receiving data from and to the devices. Some examples of controllers are USB controllers, DMA controllers, etc.

Drivers

Drivers are pieces of software that control hardware, more specifically in this case, they control the controllers. Think of it this way: if a controller is the infrastructure that allows the CPU to send instructions to the I/O devices, then the driver's role is to translate those CPU instructions into ones that the controllers can understand.

Drivers help us solve the problem of having to support several different types of hardware because, with drivers, each driver manufacturer is responsible for providing, along with the hardware, a driver to control that hardware. Thus, the only thing we have to do to use the hardware is install the device's driver and pray it's supports our Operating System and doesn't have any bugs.

*cough
Nvidia
*cough

The second problem with I/O devices is speed. I/O devices are by far the slowest part of any computer (well... besides networking stuff, but that's a discussion for another post). You've heard me complain about this for a couple posts now, so it's about time I make my case.

In a computer the physical distance of components matter. The cache is closer to the CPU, so it's faster to access than the RAM (which is farther away). In terms of distance, I/O devices are connected using long cables and, on top of that, these cables (like USB and HDMI) are not as fast as a PCI connection for example, which is what's mostly used to connect graphics cards to the motherboard (more on that in future posts).

Access types

An access type is exactly what it looks like: how does the CPU access I/O devices. There are three main ways of accessing I/O: programmed I/O, interrupt initiated I/O and DMA.

Programmed I/O: Here the I/O data is read by a computer program that's running on the CPU, meaning that it's the CPU, following instructions of a particular program, that will fetch data or send it to the devices. This often requires the CPU to be constantly checking if the I/O device is done with the task (which is called busy wait), and so it's the slowest of the three access types we'll cover here.

Interrupt Initiated I/O: To avoid busy waiting for the I/O device, in the interrupt initiated I/O the I/O device will interrupt the CPU once it's done with the task. Here, the CPU does not need to check if the I/O device is done at all, and, once it's done issuing the task to the I/O device, it will go do other tasks. Finally, when interrupted by the device, the CPU comes back to the task at hand.

Direct Memory Access (DMA): What if we didn't need to involve the CPU at all after it issues the task to the I/O device? Direct Memory Access means that the CPU will tell the device where to put the data once it's done. This way, the CPU will only need to issue the task to the I/O device, but no busy waiting or interrupts or any other task needs to be done on the CPU side.

We've already covered a lot of content. We've seen about the Von Neumman architecture, CPUs, GPUs, memory, and now I/O devices. Now, I think it's about time we talk about her. On the next (and last) post of the series we'll talk about the thing that glues everything together: The Motherboard.

References

Demystifying Computers: RAM (Random Access Memory)

Gabriel Cruz (he/him) — Fri, 16 Oct 2020 14:39:17 +0000

We've talked about CPUs and how they get data from memory and compute things with it and then write to memory. But how exactly do reads and writes occur from the memory's perspective? Let's start with the most important question.

What is Memory?

When I say memory I'm referring to memory as defined in Von Neumann's Architecture. For most recent computers, this is called the RAM, or Random Access Memory.

The RAM is the memory your computer uses to do all the major tasks. Every running process loads its information into the RAM and, while running, that's where that information lives. Once the process is done, the data is erased from the RAM.

Random-access memory?

When I was first learning about RAM I thought the random meant you actually couldn't control which part of the memory would be accessed, and that you had to get a random position of the memory over and over again until you got what you wanted (much like bogosort).

That's not how it works. Random in RAM means you can access any position of the memory with the same time cost, unlike Hard Drives in which you have to wait until the disk has spun to where you want to read and then read it (meaning if you're lucky to already be where you want to read then you don't have to wait).

RAM vs Hard Drives

RAM is what we call a volatile memory, meaning every time you turn off or restart your computer it gets completely erased. The way we currently keep information between restarts are Hard Disk Drives (HDDs or HDs) and Solid-State Dives (SSDs). Theses devices can store information for far longer than the RAM, so every time you open your browser (or any other installed software for that matter) for the first time after a restart, its information gets loaded from the HDD to the RAM, then the data is used and altered in RAM, and once you're done that new data gets updated on the HDD.

Now the question is:

Why bother? Why don't we only have HDDs (or SSDs) and use them directly? Why do we have to use this weird RAM in the middle of things?

The answer is, just like cache vs RAM in CPUs, RAM is roughly 100 times faster than HDD to access. But you know what? I've always heard that, but how about we actually test it? I did a quick code to measure the access times of RAM vs HDD. To access the RAM we simply write to an array and read from it:

def get_ram_time():
    arr = [i for i in range(1000)] # Create array
    start = time.time() # Start counting time
    a = arr[2]          # Access the array
    end = time.time()   # Stop counting time

    return end - start

For the HDD access I created a file hello.txt (every file lives on the HDD) with some text inside and tried reading from it:

def get_hdd_time():
    start = time.time()    # Start counting time
    fp = open('hello.txt') # Open file for reading
    fp.read()              # Read file
    end = time.time()      # Stop counting time

    return end - start

Finally I call these functions 100 times and get the average access times:

samples = 100
total_hdd_time = 0
total_ram_time = 0

for i in range(samples):
    total_hdd_time += get_hdd_time()
    total_ram_time += get_ram_time()

print(f"Average HDD time:{format(total_hdd_time/samples, '.9f')}s")
print(f"Average RAM time:{format(total_ram_time/samples, '.9f')}s")

Here's the result for 100 samples:

Average HDD time: 0.000018055s
Average RAM time: 0.000000298s

So it turns out that accessing the HDD is indeed about 100 times slower than RAM on average.

Types of RAM

Just like humans, not all RAM chips are made equal. DRAM (Dynamic RAM) uses capacitors to store the data, which are cheaper but slower because they need to be refreshed from time to time. SRAM (Static RAM), however, does not need to be constantly refreshed. But, because DRAM is considerably cheaper, it's the prevalent type of RAM today for personal computers.

SDRAM (Synchronous Dynamic RAM) synchronizes the RAM with the computer's clock so that the RAM controller can predict at which cycle the requested data will be ready and so the CPU can optimize tasks better. I like to think of this as having lunch at my grandma's. At my grandma's, lunch is always served at 12pm. This means that I can prepare for it better instead of interrupting some extremely important chess game with grandpa just because we started it 2 minutes before lunch was ready.

DDR (Double Data Rate) is a technique in which the amount of data transferred in one clock cycle is doubled. I'll not go into detail about this, but it's important to know what it stands for as most RAMs today are DDR3 and DDR4.

Finally, VRAM (Video RAM) is a dedicated RAM for the GPU. It holds all the data that the GPU is operating over.

Swapping

What if you computer runs out of RAM? What then?

Swapping is a technique where you set a partition of your Hard Drive to act like RAM when the actual RAM is full. So let's say you have 4GB of RAM and you need to load 5GB of data into the RAM. If you have swap set up the extra 1GB would get loaded to the Hard Drive.

Now this is no magical solution. Just because you set up 50GB of swap space that doesn't mean you actually have extra 50GB of RAM. You can't expect the swap to perform as fast at the RAM (because it's not RAM). Ideally, you want to have enough RAM so you don't even need swapping (because the RAM is never full).

More RAM or Faster RAM?

In general, more RAM is better than faster RAM. RAM is supposed to be a fast memory, but not even the oldest RAM technologies in the market are close to being as slow as a Hard Drive or an SSD. So your first goal when assembling a computer is not buying the fastest RAM possible, but rather making sure you'll almost never need to swap out because of lack of space on your RAM (because that means downgrading to Hard Dive speed, which is way worse than a slower RAM).

As we've touched in Hard Drives and SSDs, I think some further explanation on I/O devices is in order. In the next post we'll talk about how this "external" devices interact and why are they treated differently as well as the hacks we've created to make them as efficient as possible.

References

Demystifying Computers: GPU (Graphics Processing Unit)

Gabriel Cruz (he/him) — Sat, 10 Oct 2020 16:54:40 +0000

Last post we saw that CPUs today have more than one core, which is roughly a part of the chip that calculates things. With multiple cores, we can now calculate multiple things at once.

We also saw that simply adding a bunch of cores onto a CPU wouldn't necessarily improve its speed because tasks might be dependent on one another (blocking).

So right now you might be thinking:

Hey Gabe, so we're good the way we are right? I mean, we don't need nor does it make sense to have a machine that can compute thousands of threads simulta--

Introducing GPUs

GPUs are exactly that. They are processing chips that have lots and lots of little cores capable of processing thousands of threads simultaneously. But the question remains:

If most tasks can't be broken down to a lot of smaller ones, why would we need a computer that's capable of calculating a lot of smaller tasks in the first place?

The answer is here:

I really like the analogy on this video as it shows why GPUs were invented: to calculate graphical stuff (although today they're used to other things as well, more on that later). As it turns out, graphical stuff is a type of task that has very few dependencies and so can be heavily parallelized. Just think about calculating colors and other things for millions of individual pixels, none of which depend on one another.

However, I still think the video lacks the other side of the analogy: cooking. Imagine you were to make a machine that automatically makes you breakfast (including doing the dishes). It can't fry your eggs at the same time as it cracks them open and it can't do the dishes if the breakfast is not done (and eaten) yet!

What I mean is this: GPUs are great for calculating the colors of millions of pixels in a screen, but they do not perform well when doing heavy, tightly coupled tasks (because a GPU core are not as powerful as a CPU core).

The calculations a GPU really does

So I gave you an intuition behind what a GPU does when it's computing graphical stuff, but I think something more realistic is in order.

An image in a screen is just a rectangle with lots and lots of pixels, each of which has a color and combined they form an image. The more pixels you have on your screen (pixel density), the more realistic the image looks because the squares are tinier and it's harder to notice them with the naked eye.

To represent the physical pixels of a screen programmers had the idea of representing their colors as numbers on a matrix. Each number represents the intensity of the light in that pixel.

Let's imagine we have a gray scale display (no colors), here's how you'd create and plot a square gray scale image in Python:

from PIL import Image # for image plotting
import numpy as np # to build the array

# Create empty 512x512 matrix
mat = np.zeros((512, 512))

# Fill matrix with a pattern
for i in range(0, 512):
    for j in range(0, 512):
        mat[i][j] = i*j

# Print matrix in grayscale
im = Image.fromarray(mat, 'L')
im.show()

Other uses

Now originally GPUs were really "Graphics Processing Units", but actually they were just hardware that was good to do matrix operations. As it turns out, a lot of newer fields need hardware that does that, notably machine learning and bruteforcing such as bitcoin mining.

Parallelism vs Concurrency

I've been using the term "parallelism" for quite a while now and I think it's time we clear this out.

As every discussion involving definitions, there's a lot of discussion around this. Here's how I'll define these two:

Parallelism: Performing multiple tasks at the same time.
Concurrency: Decoupling tasks in a bigger task.

This means that a program can be concurrent (be divided on different threads, for example) and not run in parallel.

The best example I can think of is fetching data on a Hard Drive. This is one of the slowest tasks your computer does and, compared to other operations like adding two numbers, it's extremely slow. I mean 1000x slower.

When the CPU asks the Hard Drive for some data, it doesn't wait around until it receives the data. Instead, a concurrent program could context switch out of the CPU while the data isn't retrieved, allowing it to make 1000 other operations and, when the data is finally ready, it resumes execution of the original task. In this case, the Hard Drive data fetching and the other calculations are decoupled, making the execution concurrent.

References

What’s the Difference Between a CPU and a GPU? (Nvidia Blog)

Concurrency is not Parallelism by Rob Pike

Demystifying Computers: CPU (Central Processing Unit)

Gabriel Cruz (he/him) — Wed, 30 Sep 2020 20:40:08 +0000

Let's say you love playing games and finally have the money to assemble the definitive gaming PC. You start by (what seems like) the most important part of the computer: the CPU, or the processor.

Obs: There is a discussion about whether CPUs and processors are the same thing or not, but for the sake of this post I'll just use these terms interchangeably.

You go to Amazon.com and type in "CPU" on the search bar. What pops up makes you feel like a total moron -- or at least that's how I feel being a CS bachelor and not understanding even half of that gibberish.

Here are the first results I get when searching for "CPU" at Amazon:

AMD Ryzen 7 3700X 8-Core, 16-Thread Unlocked Desktop Processor with Wraith Prism LED Cooler

Intel Core i7-9700K Desktop Processor 8 Cores up to 4.9 GHz Turbo unlocked LGA1151 300 Series 95W

AMD Ryzen 5 3600 6-Core, 12-Thread Unlocked Desktop Processor with Wraith Stealth Cooler

A much more powerful calculator

The way I see it, a CPU can be reduced to the ALU, the Arithmetic Logic Unit. Most of the other mechanisms a processor has serve to support the ALU do its job as quickly and efficiently as possible. Sure, this is a simplification of what a CPU does (it also performs a bunch of I/O operations and all), but I think looking at it this way helps us understand the basics.

The tasks a standard ALU performs are Integer Arithmetic and Bitwise Logic. Integer Arithmetic is simple math operations like adding, subtracting, multiplying and dividing using integer numbers.

Bitwise Logic is the type of operations done in singular bits rather than integer numbers. For example, a bitwise AND operation works like so:

First bit	Second bit	AND result
0	0	0
0	1	0
1	0	0
1	1	1

So for exmple

0011 AND 0101 = 0001

Other examples of bitwise operations are OR, NOT and XOR (exclusive OR).

Note: CPUs often also have an FPU, or Floating-Point Unit, which does similar tasks as the ALU, but with floating-point (non-integer) numbers.

Power is never enough

Imagine you work in a bakery and you bake bread all day long. On your first day you manage to bake two batches. On your second day, you bake 5 batches. On your third day, you bake 7 batches.

Although in the beginning you used to bake almost double the batches of the previous day, at some point you'll reach a limit, right? I mean you can't bake double the bread forever.

Moore's """law""" is exactly like that:

Moore's Law is the observation that the number of transistors in a dense integrated circuit (IC) doubles about every two years.

This means that, according to Moore's law, the computing power of a processor should double once two years because transistors, the basic component of integrated circuits, would get twice as smaller and we'd be able to fit double the number of transistors in the same space.

But, as we quickly saw, there is a physical barrier: at some point we simply won't be able to produce tinier transistors. The solution? Instead of trying to make a single processor faster, we can also double the number of "processors" (cores).

Cores

A core is a part of a processor that basically contains an ALU and other supporting pieces around it, but which shares some resources with other cores in the same processor.

Putting an extra core in a processor enables, theoretically, double the processing power (now you can do 2 operations at once). However, some operations might be dependent in one another. Let's say you have to add a number in the memory with another number in the memory. Retrieving the numbers from memory can be done in parallel, but adding them is dependent on the numbers to be retrieved in the first place.

Note: An interesting discussion here is parallelism vs concurrency. Don't worry too much about this right now though, we'll dive deeper into that when we talk about GPUs on the next post.

So, quickly coming back to one of our CPU examples:

AMD Ryzen 7 3700X 8-Core, 16-Thread Unlocked Desktop Processor with Wraith Prism LED Cooler

This one has 8 cores, meaning it can, in theory, execute 8 little independent tasks at once.

Great! Now we have multiple cores and can run stuff muuuuch faster than we did before.

But how does the processor know which tasks can be run before others or in parallel to others?

It doesn't, you have to tell it to. And you do so by spawning multiple threads on your programs to do different tasks.

Threads

If cores are the fundamental processing unit of a processor, threads are the fundamental tasks that run in a core.

Whenever you open up a terminal or fire up League of Legends, a process is being created and ran. Threads are a way to subdivide a process so that it performs better in multi-core processors, that is, processors that have more than one core.

Note: You might have stumbled upon the word Hyperthreading. Hyperthreading is a technique to enhance thread scheduling by increasing the amount of independent tasks on the processor so that there's the least amount of idle time possible on the cores. This could give the end user the impression that there are more (virtual) cores than there actually (physically) are. This is why you might see a processor that has 6 virtual cores but only 4 physical ones.

Clock

The number of cores a processor has is not the only characteristic that impacts its speed. The clock is the number of cycles the CPU processes per second (e.g. 4.9 GHz means 49 000 000 000 cycles/second).

You can think of a CPU cycle as the period of time in which your CPU can accomplish a small task. So if a thread has three operations, it'll take roughly three cycles to accomplish them.

In general, the more cycles a processor can accomplish per second, the more operations it can do (the faster the CPU).

Cache

Last but not least we have cache. Cache is a type of memory that is very physically close to the processor and, because of that, is very fast to access. Whenever the processor needs some information, instead of looking at the main memory of the computer (which takes a lot of time in terms of super fast machines), it first looks at the cache and, if it doesn't find the information it's looking for, then it goes all the way to the main memory and retrieves it.

Think of it this way: imagine the memory of your computer is like a supermarket and the cache is your fridge. Whenever you want something to eat, you go to the fridge and see if it's there (because it's faster and we're super lazy). If you don't find it, you go to the supermarket, buy a bunch of it and keep some in your fridge so you don't have to go to the supermarket for a while.

That's what happens with the cache. It's a way to reduce the number of times the processor needs to access the main memory of the computer by keeping more relevant data closer to the processor.

This is not an extensive list of the features and components of CPUs. CPUs are different, specific and have a lot of little details that make them very different from one another and complex overall. The aim of this post was to shed some light into what happens inside them in a general way.

In the next post we'll discuss perhaps the most obscure and yet widely used piece of hardware: GPUs

Demystifying Computers: Intro to Computer Architecture

Gabriel Cruz (he/him) — Tue, 22 Sep 2020 14:27:04 +0000

This post is the first in a series where I try to dissect the inners of computers in just enough detail so you can understand the "magic" that goes on behind the curtains when you write a "hello world" program or open up your browser.

Introduction

A while back I visited the Palace of Versailles and boy was it big. I thought "How could something this big have been someone's house?". One thing's for sure: houses can be very, very different.

The architecture of a computer is much like the architecture of a house. Some houses, like the Palace of Versailles, are unbelievably big; others, however, can be incredibly small. Similarly, some computers, like mainframes, are huge. They use a lot of energy and do tons of heavy work. Other computers however, like the Raspberry Pi, are small, compact and often can only do very specific tasks.

So what is a computer?

Computers are very different from one another and serve different purposes in different ways. So, defining what we're calling a "computer" is super important.

Don't get me wrong though. I think that having a definition is important, but trying to get to a "perfect" definition is impossible, time-consuming and yields some purist discussions that I just can't stand.

So, for the purpose of this post and the next ones, here's the definition I'll use:

Computers are electronic machines that take inputs, perform operations with those inputs, and produce outputs.

Now that we have a rough definition of what a computer is, let's move on to a more meaty and practical question.

What are computers made of?

Computers come in a lot of different shapes and sizes, simply because they serve different purposes and are used in different situations. Some computers serve one, and only one, human being, others are used by a lot of people, often at the same time.

So computers will have different architectures depending on the type tasks they were designed to do. But most of today's computers still follow one basic, hella old architecture: Von Neumann's architecture.

Von Neumann's Architecture

In 1945 John Von Neumann and his team were trying to create an architecture that would allow people to build computers that were both (1) general purpose and (2) electronic. At the time, general purpose computers, as well as electronic computers, already existed, but there was not a computer that were both general purpose and electronic at the same time.

A Von Neumann's computer has 4 main components:

A processing unit (that computes operations)
A control unit (which basically tells the processing unit what operation to compute next)
Memory
Input/output devices such as keyboards, mouses (input) and monitors (output).

Obs: Input/output devices are often called "I/O devices"

We can now answer our question of what computers are made of:

A processing unit
A control unit
Memory
I/O devices

That's it. That's what computers are made of.

What is your computer made of?

So right now you might be asking yourself:

What does all this have to do with demystifying computers? I mean, this Von Neumann guy might be important for historical reasons, but my computer doesn't look like that. I have a graphics card, network connection, multiple monitors, SSD,...

Well, computers nowadays are a bit different than what they were in Von Neumann's time, that's for sure. But their architecture is basically still the same.

Let's dissect my laptop real quick, I have an Acer Aspire E 14:

Component	Model
Processor (CPU)	Intel i3-8130U
Graphics Card	Intel UHD Graphics 620
RAM Memory	4GB DDR4 SDRAM
Storage	1TB Serial ATA
Input Devices	TouchPad & Keyboard
Display/Monitor	14" LCD CineCrystal HD

How does that fit into Von Neumann's architecture?

Processing and control unit: CPU and Graphics Card
Memory: RAM Memory
I/O devices: Storage, TouchPad, Keyboard, Display

You see, that's the magic of Von Neumann's architecture. Even though he had no idea that GPUs would be a thing, his architecture still holds up until this day and we build computers based on his architecture.

In the next posts of the series we'll answer questions like "why isn't storage classified as memory but as an I/O device?" or "what are the differences between CPUs and GPUs?" and "how do CPUs add and subtract numbers?".

Creating a minute with 100 "seconds"

Gabriel Cruz (he/him) — Mon, 14 Sep 2020 12:32:17 +0000

Counting to 60 is lame.

No, really, think about it. We (humans) generally use base 10 to general counting tasks, because we have 10 fingers on our hands. So I'd expect that our time system would go from 1 to 10 or from 1 to 100. But no, we count from 1 to 60...

Wanna know what's even more disturbing? This time system is not even consistent. Sometimes we count to 60 (60 seconds is a minute and 60 minutes is an hour), but sometimes we count to 100 (like milliseconds, microseconds, etc.)! That's just outrageous.

As programmers, it's our job to fix the World's nastiest issues, such as this dirty little time counting system.

Now imagine a day had 100 hours, an hour had 100 minutes, and a minute had 100 seconds. Wouldn't that be great? Introducing cclock.

gmelodie / cclock

CLI clock that divides time in 100, not 60

Cclock is a basic conversion tool that will convert hours, minutes and seconds to CTime, a time system that actually makes sense:

$ cclock 1 49 30
Normal Time:    1h  49min   50s
CTime:          1ch 83ct    6cs

Cclock, or centhclock, has three basic time measures: centhconds (cs), centhutes (ct) and centhours (ch), where

1ch = 100ct
1ct = 100cs
1ch = 1h

Here's a conversion table with more detailed conversions

Time measure	Centhconds	Centhutes	Centhours
1 Second	2.777778 cs	0.02777778 ct	0.0002777778 ch
1 Minute	166.66668 cs	1.6666668 ct	0.016666668 ch
1 Hour	10000.0008 cs	100.000008 ct	1.00000008 ch
1 Day	240000.01920 cs	2400.0001920 ct	24.000001920 ch

DEV Community: Gabriel Cruz (he/him)

WTF is an API? (or, "Everything's a Lie")

The naming

APIs are like libs

What people usually mean when they talk about APIs

REST: Representational State Transfer

Appendix I: Idempotency

References

Total Madness #2: Async Locks

Episode 2: Async Locks

Implementing an async lock

Appendix I: tokio::sync::Mutex vs. std::sync::Mutex

Appendix II: Atomic Async Locks

References

Total Madness #1: Async/Await

Episode 1: Async/Await

Tasks

Async

Futures

Poll

An async implementation of our executor

Appendix I: Rust Macros

References

Total Madness #0: Locks

Episode 0: Locks

Spinlocks

Interrupts: a lock's nightmare!

Atomics

Appendix I: Atomics in rust

References

6 tips for your developer resume

1. It should look alike

2. Write an initial version

3. Get it dirty

4. Take feedback with a grain of salt

5. Not everyone's gonna dig it

6. It should look like you

My ideal resume

Other quick tips

Resources and further readings

Remote team building: online scavenger/treasure hunt (without the bullshit)

Demystifying Computers: I/O Devices

Controllers

Drivers

Access types

References

Demystifying Computers: RAM (Random Access Memory)

What is Memory?

Random-access memory?

RAM vs Hard Drives

Types of RAM

Swapping

More RAM or Faster RAM?

References

Demystifying Computers: GPU (Graphics Processing Unit)

Introducing GPUs

The calculations a GPU really does

Other uses

Parallelism vs Concurrency

References

Demystifying Computers: CPU (Central Processing Unit)

A much more powerful calculator

Power is never enough

Cores

Threads

Clock

Cache

Further readings

General explanations

Arithmetic Logic Unit (ALU)

Hyper Threading

Demystifying Computers: Intro to Computer Architecture

Introduction

So what is a computer?

What are computers made of?

Von Neumann's Architecture

What is your computer made of?

Creating a minute with 100 "seconds"

gmelodie / cclock

CLI clock that divides time in 100, not 60