CK_SPINLOCK(3)

✨ NAME ✨

okay so bestie, meet ck_spinlock(3) — the Concurrency Kit spinlock page, aka the whole ✨spinlock implementations✨ family. There are a LOT of them, and they all live here:

• the base one: ck_spinlock_init, ck_spinlock_lock, ck_spinlock_unlock, ck_spinlock_locked, ck_spinlock_trylock
• Anderson: ck_spinlock_anderson_init, ck_spinlock_anderson_locked, ck_spinlock_anderson_lock, ck_spinlock_anderson_unlock
• Compare-and-Swap: ck_spinlock_cas_init, ck_spinlock_cas_locked, ck_spinlock_cas_lock, ck_spinlock_cas_lock_eb, ck_spinlock_cas_trylock, ck_spinlock_cas_unlock
• CLH: ck_spinlock_clh_init, ck_spinlock_clh_locked, ck_spinlock_clh_lock, ck_spinlock_clh_unlock
• Decrement: ck_spinlock_dec_init, ck_spinlock_dec_locked, ck_spinlock_dec_lock, ck_spinlock_dec_lock_eb, ck_spinlock_dec_trylock, ck_spinlock_dec_unlock
• Fetch-and-store: ck_spinlock_fas_init, ck_spinlock_fas_lock, ck_spinlock_fas_lock_eb, ck_spinlock_fas_locked, ck_spinlock_fas_trylock, ck_spinlock_fas_unlock
• Hierarchical CLH: ck_spinlock_hclh_init, ck_spinlock_hclh_locked, ck_spinlock_hclh_lock, ck_spinlock_hclh_unlock
• Mellor-Crummey and Scott: ck_spinlock_mcs_init, ck_spinlock_mcs_locked, ck_spinlock_mcs_lock, ck_spinlock_mcs_trylock, ck_spinlock_mcs_unlock
• Ticket: ck_spinlock_ticket_init, ck_spinlock_ticket_locked, ck_spinlock_ticket_lock, ck_spinlock_ticket_lock_pb, ck_spinlock_ticket_trylock, ck_spinlock_ticket_unlock

periodt 💅

---

📚 LIBRARY 📚

this is all Concurrency Kit — that's libck, and you link it with -lck. 🫶

---

🌈 SYNOPSIS 🌈

first, the include, because obviously:

#include <ck_spinlock.h>

💖 the plain old ck_spinlock_t 💖

ck_spinlock_t spinlock = CK_SPINLOCK_INITIALIZER;

void
ck_spinlock_init(ck_spinlock_t *lock);

void
ck_spinlock_lock(ck_spinlock_t *lock);

void
ck_spinlock_unlock(ck_spinlock_t *lock);

bool
ck_spinlock_locked(ck_spinlock_t *lock);

bool
ck_spinlock_trylock(ck_spinlock_t *lock);

🦋 anderson 🦋

void
ck_spinlock_anderson_init(ck_spinlock_anderson_t *lock,
    ck_spinlock_anderson_thread_t *slots, unsigned int count);

bool
ck_spinlock_anderson_locked(ck_spinlock_anderson_t *lock);

void
ck_spinlock_anderson_lock(ck_spinlock_anderson_t *lock,
    ck_spinlock_anderson_thread_t **slot);

void
ck_spinlock_anderson_unlock(ck_spinlock_anderson_t *lock,
    ck_spinlock_anderson_thread_t *slot);

🎀 cas 🎀

ck_spinlock_cas_t spinlock = CK_SPINLOCK_CAS_INITIALIZER;

void
ck_spinlock_cas_init(ck_spinlock_cas_t *lock);

bool
ck_spinlock_cas_locked(ck_spinlock_cas_t *lock);

void
ck_spinlock_cas_lock(ck_spinlock_cas_t *lock);

void
ck_spinlock_cas_lock_eb(ck_spinlock_cas_t *lock);

bool
ck_spinlock_cas_trylock(ck_spinlock_cas_t *lock);

void
ck_spinlock_cas_unlock(ck_spinlock_cas_t *lock);

🌸 clh 🌸

void
ck_spinlock_clh_init(ck_spinlock_clh_t **lock,
    ck_spinlock_clh_t *unowned);

bool
ck_spinlock_clh_locked(ck_spinlock_clh_t **lock);

void
ck_spinlock_clh_lock(ck_spinlock_clh_t **lock, ck_spinlock_clh_t *node);

void
ck_spinlock_clh_unlock(ck_spinlock_clh_t **node);

🍓 dec 🍓

ck_spinlock_dec_t spinlock = CK_SPINLOCK_DEC_INITIALIZER;

void
ck_spinlock_dec_init(ck_spinlock_dec_t *lock);

bool
ck_spinlock_dec_locked(ck_spinlock_dec_t *lock);

void
ck_spinlock_dec_lock(ck_spinlock_dec_t *lock);

void
ck_spinlock_dec_lock_eb(ck_spinlock_dec_t *lock);

bool
ck_spinlock_dec_trylock(ck_spinlock_dec_t *lock);

void
ck_spinlock_dec_unlock(ck_spinlock_dec_t *lock);

🔥 fas 🔥

ck_spinlock_fas_t spinlock = CK_SPINLOCK_FAS_INITIALIZER;

void
ck_spinlock_fas_init(ck_spinlock_fas_t *lock);

void
ck_spinlock_fas_lock(ck_spinlock_fas_t *lock);

void
ck_spinlock_fas_lock_eb(ck_spinlock_fas_t *lock);

bool
ck_spinlock_fas_locked(ck_spinlock_fas_t *lock);

bool
ck_spinlock_fas_trylock(ck_spinlock_fas_t *lock);

void
ck_spinlock_fas_unlock(ck_spinlock_fas_t *lock);

💜 hclh 💜

void
ck_spinlock_hclh_init(ck_spinlock_hclh_t **lock,
    ck_spinlock_hclh_t *unowned);

bool
ck_spinlock_hclh_locked(ck_spinlock_hclh_t **lock);

void
ck_spinlock_hclh_lock(ck_spinlock_hclh_t **lock,
    ck_spinlock_hclh_t *node);

void
ck_spinlock_hclh_unlock(ck_spinlock_hclh_t **node);

🧚 mcs 🧚

ck_spinlock_mcs_t spinlock = CK_SPINLOCK_MCS_INITIALIZER;

void
ck_spinlock_mcs_init(ck_spinlock_mcs_t **lock);

bool
ck_spinlock_mcs_locked(ck_spinlock_mcs_t **lock);

void
ck_spinlock_mcs_lock(ck_spinlock_mcs_t **lock, ck_spinlock_mcs_t *node);

bool
ck_spinlock_mcs_trylock(ck_spinlock_mcs_t **lock,
    ck_spinlock_mcs_t *node);

void
ck_spinlock_mcs_unlock(ck_spinlock_mcs_t **lock,
    ck_spinlock_mcs_t *node);

⭐ ticket ⭐

ck_spinlock_ticket_t spinlock = CK_SPINLOCK_TICKET_INITIALIZER;

void
ck_spinlock_ticket_init(ck_spinlock_ticket_t *lock);

bool
ck_spinlock_ticket_locked(ck_spinlock_ticket_t *lock);

void
ck_spinlock_ticket_lock(ck_spinlock_ticket_t *lock);

void
ck_spinlock_ticket_lock_pb(ck_spinlock_ticket_t *lock,
    unsigned int period);

bool
ck_spinlock_ticket_trylock(ck_spinlock_ticket_t *lock);

void
ck_spinlock_ticket_unlock(ck_spinlock_ticket_t *lock);

---

👑 DESCRIPTION 👑

so basically: this is a whole family of busy-wait spinlock implementations, and they all just... spin until they get the lock. iconic behavior honestly. 💅

the ck_spinlock_t one? it's literally just a wrapper around the fetch-and-swap (ck_spinlock_fas_t) implementation. no cap.

here's the rundown of every current implementation, bestie — full tea, nothing held back:

• ck_spinlock_anderson
  • Algorithm: Anderson
  • Type: Array
  • Restrictions: Fixed number of threads
  • Fair: Yes ✨
• ck_spinlock_cas
  • Algorithm: Compare-and-Swap
  • Type: Centralized
  • Restrictions: None
  • Fair: No
• ck_spinlock_clh
  • Algorithm: Craig, Landin and Hagersten
  • Type: Queue
  • Restrictions: Lifetime requirements
  • Fair: Yes ✨
• ck_spinlock_dec
  • Algorithm: Decrement (Linux kernel)
  • Type: Centralized
  • Restrictions: UINT_MAX concurrency
  • Fair: No
• ck_spinlock_fas
  • Algorithm: Fetch-and-store
  • Type: Centralized
  • Restrictions: None
  • Fair: No
• ck_spinlock_hclh
  • Algorithm: Hierarchical CLH
  • Type: Queue
  • Restrictions: Lifetime requirements
  • Fair: Yes * (see the footnote, babe)
• ck_spinlock_mcs
  • Algorithm: Mellor-Crummey and Scott
  • Type: Queue
  • Restrictions: None
  • Fair: Yes ✨
• ck_spinlock_ticket
  • Algorithm: Ticket
  • Type: Centralized
  • Restrictions: None
  • Fair: Yes ✨

* Hierarchical CLH only offers weak fairness for threads across cluster nodes. so like... fair-ish. 😭

---

🫶 which one do i pick though 🫶

okay here's the vibe check, straight from the page:

• If contention is low and there's no hard requirement for starvation-freedom → grab a centralized greedy (unfair) spinlock. simple as.
• If contention is high and there's no requirement for starvation-freedom → a centralized greedy spinlock, but pair it with an exponential backoff mechanism. that's the move.
• If contention is generally low and you hard-require starvation-freedom → the ticket lock. slay.
• If contention is high and you hard-require starvation-freedom → the Craig and Landin and Hagersten queue spinlock, unless stack allocation is necessary or NUMA factor is high — in which case the Mellor-Crummey and Scott spinlock is the one.
• If you cannot afford O(n) space-usage from array or queue spinlocks but still need fairness under high contention → the ticket lock with proportional back-off. ate. 🎀
• If NUMA factor is high but you'd still prefer a greedy lock → please go see ck_cohort(3). iykyk.

---

💻 EXAMPLE 💻

here's the whole thing, verbatim, go off:

#include <ck_spinlock.h>
#include <stdbool.h>

/*
 * Alternatively, the mutex may be initialized at run-time with
 * ck_spinlock_init(&mutex).
 */
ck_spinlock_t mutex = CK_SPINLOCK_INITIALIZER;

void
example(void)
{

        ck_spinlock_lock(&mutex);
        /*
         * Critical section.
         */
        ck_spinlock_unlock(&mutex);

        ck_spinlock_lock_eb(&mutex);
        /*
         * Critical section.
         */
        ck_spinlock_unlock(&mutex);

        if (ck_spinlock_trylock(&mutex) == true) {
                /*
                 * Critical section.
                 */
                ck_spinlock_unlock(&mutex);
        }
}

---

🔍 SEE ALSO 🔍

• ck_cohort(3)
• ck_elide(3)

and if you want even more, there's additional information available at http://concurrencykit.org/ 🌈

---

k that's the whole page, bestie!! this one's dated July 26, 2013, and it's ck_spinlock(3) from Concurrency Kit — go forth and lock things responsibly, mwah 💖🎀🦋