apparently <stdatomic.h> is just a header file and can't hurt you :3
(assuming the CPU you're compiling for supports atomicity)

ok extremely underrated feature of C imo, the fact that some standard header files work even with the -nostdlib flag, like YESSSSSsss

(why is -nostdlib important to me? read this short post!!)

#include <stdatomic.h>

#define mutex_t volatile atomic_flag
#define mutex_init(m) atomic_flag_clear(m)
#define mutex_get(m) while (atomic_flag_test_and_set(m))
#define mutex_free(m) atomic_flag_clear(m)

mutex_t m;

void _start()
{
  mutex_init(&m);
  volatile int exampleData = 0;
  mutex_get(&m);
  exampleData = 5;
  mutex_free(&m);
}

#include <stdatomic.h>

#define mutex_t volatile atomic_uint_fast8_t
#define mutex_init(m) *(m) = 0
#define mutex_get(m) while (atomic_exchange((m), 1))
#define mutex_free(m) *(m) = 0

// ... (same as before)

i love talking about mutexes so now i'm going to make that everyone else's problem

ok so. indeed, that code is a relatively straightforward implementation of mutexes. i could digress into stuff about volatile and memory orderings, but instead, there is something more important we need to talk about before considering if this mutex is "good":

What Is A Mutex?

By its name, a mutex is something that provides Mutual Exclusion of a shared resource for concurrent tasks. In plain language:

Only one task can access the thing at a time

Programmers call it "acquiring" or "locking" the mutex when you attempt to access that shared resource, and "releasing" or "unlocking" the mutex when you had ownership of the resource and are giving it away for others to use.

Besides mutual exclusion, there's another property (not in the name) that's required for something to be a proper mutex:

Progress

No matter how many tasks are trying to acquire the mutex, if the resource isn't owned, someone will be able to get it

It's hard to mess this one up; in fact I'd say most buggy mutex implementations skew the other way by not correctly providing mutual exclusion. To give a concrete example of how progress could be violated, consider the following implementation: (for some reason i couldn't put it inside a <details>, sorry)

#include <stdatomic.h>

typedef struct {
  queue_t waiters;
  atomic_int owner;
} mutex_t;

static const int EMPTY = 0;

void lock(mutex_t *m, int pid) {
  if (!atomic_compare_exchange_strong(&m->owner, &EMPTY, pid)) {
    push_back(&m->q, pid);
    deschedule(); // Pauses execution until reschedule(pid) called
  }
  m->owner = pid;
}

void unlock(mutex_t *mutex) {
  int pid = pop_front(&m->q);
  if (pid != EMPTY) {
    reschedule(pid);
  } else {
    atomic_store(&m->owner, EMPTY);
  }
}

Progress and mutual exclusion are basically required for a correct mutex, but this last one is just nice to have:

Bounded Waiting

If a task tries to acquire the mutex, it will eventually be the owner of the resource

This can be strengthened further by putting bounds on how long it will take (a function of the number of competing tasks, proportional to), or weakened to deal with probabilistic algorithms. In any case, it's common for implementations attempting to go for bounded waiting do so at the cost of progress or mutual exclusion (by accident, as was the case in the example). So it is refreshing to see a simple spinlock that won't even try to deal with it.

However! Bounded waiting is still a very important property, and any non-specialized implementation should have it. Consider the following code:

void mainloop(void) {
  while (!should_stop) {
    lock(&m);
    process(&shared_resource);
    unlock(&m);
  }
}

To be clear, this is is a terrible, effectively single-threaded design. Still, it's not all that uncommon in real designs for threads to relatively quickly acquire and release the same mutex over and over, which can starve other threads if there isn't bounded waiting on the mutex.

Can We Achieve Bounded Waiting With Only <stdatomic.h>?

My claim is yes! Here is an example of such a mutex, known as a ticket lock:

#include <stdatomic.h>

typedef struct {
  atomic_int next_ticket;
  atomic_int now_serving;
} mutex_t;

void lock(mutex_t *m) {
  // Get our ticket
  int ticket = atomic_fetch_add(&m->next_ticket, 1, memory_order_relaxed);
  // Spin until we are being served
  while (ticket != m->now_serving) {}
  atomic_thread_fence(memory_order_acquire);
}

void unlock(mutex_t *m) {
  // Let the next ticket be served
  atomic_fetch_add(&m->now_serving, 1, memory_order_release);
}

How it works is fairly simple, and pretty much entirely explained in the comments already. It's inspired by how you'd wait in line at a deli or pharmacy.

Some great things about this lock:

• just one atomic operation to lock and unlock
• small (8 bytes)

Some not-great things about this lock:

• spin waiting :(
• technically, ABA, but with 32-bit tickets this shouldn't be an issue in practice
• doesn't detect misuse

Most of these deficits could be solved by better design, but i am too lazy rn :P

Now, you may have still some questions like "wait why didn't you use volatile?" and "what's with that memory order stuff?", but this post is a little long as it stands, so I figure I'll leave the discussion about How Your Compiler And CPU Lie To You for a future post. Or just read Tower Of Weakenings because it answers or has links to answers for those questions and more.

And by the way, it's entirely possible I missed something and this code has a bug I am unaware of, so please do ask questions if you think something is up! edit: I did get it wrong in multiple ways the first time. After talking with a few friends I am now more confident it is correct :) will explain in the later post edit 2: I got it wrong again! Definitely making a post because explaining how I got things wrong is quite a journey.