🔨 File 02: Custom Mutex / Spinlock — Build Your Own From Scratch

When the interviewer says: "You can't use std::mutex or any OS primitives. Build your own."

📖 What is a Spinlock? (Simple Explanation)

A spinlock is a lock where a waiting thread doesn't go to sleep — it just keeps checking in a tight loop ("spinning") until the lock becomes available.

Analogy: Imagine you're at a bathroom door:

Mutex = You try the handle. It's locked. You sit down in a chair and fall asleep. Someone wakes you up when the bathroom is free. (Expensive — falling asleep and waking up takes time)
Spinlock = You try the handle. It's locked. You keep jiggling the handle every millisecond until it opens. (Cheap if the wait is short, wasteful if the wait is long)

When is a Spinlock Better Than a Mutex?

Scenario	Use Spinlock	Use Mutex
Critical section is very short (< 100 ns)	✅	❌ (sleep overhead > work)
Critical section is long (> 1 μs)	❌ (wastes CPU)	✅ (let CPU do other work)
Low contention (few threads)	✅	Either works
High contention (many threads)	❌ (all spinning = wasted CPU)	✅

In the Tree of Space with $N = 10^5$ nodes (tree height $H \approx 17$):

Critical section is $2 \times H \approx 34$ operations $\times 1.5\text{ ns}$ (L1/L2 cache hit) = ~30 to 60 ns.
OS Mutex context switch penalty = ~2,000 to 5,000 ns.
Because $50\text{ ns} \ll 3,000\text{ ns}$, Spinlock wins overwhelmingly (spinning for 150 cycles is 60× faster than a kernel context switch).

🔧 Level 1: Basic Test-and-Set (TAS) Spinlock

What is Test-and-Set?

__sync_lock_test_and_set(&variable, new_value) is a hardware instruction that does THREE things as one indivisible operation:

READ the current value of variable
WRITE new_value into variable
RETURN the old value (what was there before the write)

No thread can interrupt between steps 1 and 2. The CPU hardware guarantees this.

Why Can't We Just Do This Instead?

// ❌ THIS IS BROKEN — TOCTOU Bug:
void lock() {
    while (true) {
        if (isLocked == 0) {     // Step 1: READ (check)
            // ⚡ CONTEXT SWITCH CAN HAPPEN HERE ⚡
            // Another thread also reads 0, also enters!
            isLocked = 1;         // Step 2: WRITE (set)
            return;
        }
    }
}

Between the READ and WRITE, another thread can read the same "unlocked" value. Both think they got the lock. Bug!

__sync_lock_test_and_set fuses both into ONE instruction → no gap → no bug.

Implementation: Basic TAS Spinlock

class SpinLock {
private:
    static const int LOCKED = 1;
    static const int UNLOCKED = 0;
    volatile int isLocked;  // volatile = don't cache in CPU register
    
public:
    SpinLock() : isLocked(UNLOCKED) {}
    
    void lock() {
        // Atomically: read old value, write 1.
        // If old value was 1 → someone else has it → spin
        // If old value was 0 → we just set it to 1 → we got it!
        while (__sync_lock_test_and_set(&isLocked, LOCKED) == LOCKED) {
            // Spin-wait (busy loop)
        }
    }
    
    void unlock() {
        __sync_lock_release(&isLocked);  // Atomically set to 0
    }
    
    bool try_lock() {
        // Non-blocking: try once, return immediately
        return __sync_lock_test_and_set(&isLocked, LOCKED) != LOCKED;
    }
};

⚠️ The Ownership Flaw — This is NOT a True Mutex!

Thread A calls lock()  → isLocked = 1 (Thread A has the lock)
Thread B calls unlock() → isLocked = 0 (Thread B released Thread A's lock!)

Any thread can call unlock()! A true mutex only allows the locking thread to unlock.

Interview point: "A bare spinlock with just a 0/1 flag behaves like a binary semaphore, not a true mutex. For a true mutex, we need to track the thread ID of the owner."

🔧 Level 2: Ownership Mutex (True Mutex With Thread ID)

#include <thread>
#include <atomic>
#include <stdexcept>

class OwnershipMutex {
private:
    // Stores the thread ID of the owner. Empty thread::id = no owner.
    std::atomic<std::thread::id> owner{std::thread::id()};

public:
    OwnershipMutex() = default;

    void lock() {
        std::thread::id myId = std::this_thread::get_id();
        std::thread::id expected = std::thread::id();  // expected: no owner
        
        // Atomically: if owner is "no one", set owner to myId
        // memory_order_acquire: nothing after this can be reordered before it
        while (!owner.compare_exchange_weak(
            expected,
            myId,
            std::memory_order_acquire,
            std::memory_order_relaxed))
        {
            expected = std::thread::id();  // reset expected on failure
            std::this_thread::yield();     // give CPU to other threads
        }
    }

    void unlock() {
        std::thread::id myId = std::this_thread::get_id();
        
        // 🚨 STRICT OWNERSHIP CHECK:
        if (owner.load(std::memory_order_relaxed) != myId) {
            throw std::runtime_error(
                "IllegalMonitorState: You don't own this lock!"
            );
        }
        
        // Release: flush all writes before clearing ownership
        owner.store(std::thread::id(), std::memory_order_release);
    }

    bool try_lock() {
        std::thread::id myId = std::this_thread::get_id();
        std::thread::id expected = std::thread::id();
        return owner.compare_exchange_strong(
            expected, myId,
            std::memory_order_acquire,
            std::memory_order_relaxed
        );
    }
};

Key Differences from Basic SpinLock:

Feature	Basic SpinLock	Ownership Mutex
State	`int` (0 or 1)	`thread::id` (empty or owner's ID)
Any thread can unlock?	✅ Yes (bug!)	❌ No (throws exception)
Uses CAS?	No (uses TAS)	Yes (compare_exchange)
True mutex?	No (binary semaphore)	Yes

🔧 Level 3: TTAS (Test-and-Test-and-Set) — Performance Optimization

The basic TAS spinlock has a performance problem:

// Basic TAS: Every iteration does an ATOMIC write to memory
while (__sync_lock_test_and_set(&isLocked, 1) == 1) {
    // Each iteration: LOCK XCHG writes to isLocked
    // This invalidates the cache line on ALL other CPU cores (MESI protocol)
    // → Massive bus traffic → "Cache line ping-pong"
}

TTAS optimization: First check with a normal read (cache-local, no bus traffic), only do the expensive atomic operation when the lock appears free:

class TTASSpinLock {
private:
    volatile int isLocked = 0;

public:
    void lock() {
        while (true) {
            // OUTER: Test with regular READ (hits L1 cache, no bus traffic)
            while (isLocked == 1) {
                // Just read from local cache. Super cheap.
                // When the lock holder writes 0, MESI protocol
                // invalidates our cache line → we see the update.
            }
            
            // Lock appears free! Now try the expensive atomic swap:
            if (__sync_lock_test_and_set(&isLocked, 1) == 0) {
                return;  // Got it!
            }
            // If we lost the race, go back to cheap spinning
        }
    }

    void unlock() {
        __sync_lock_release(&isLocked);
    }
};

Why TTAS is Better:

TAS:   spin spin spin spin spin spin spin spin  ← each spin = bus write
                                                   (invalidates all caches)

TTAS:  read read read read read read             ← each read = L1 cache hit
       ... lock appears free ...                    (no bus traffic!)
       TAS (one atomic write)                     ← only ONE bus write

🌳 Tree of Space with Custom Spinlock

#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>

using namespace std;

// Use the TTAS SpinLock from above
vector<TTASSpinLock> nodeLocks;
vector<int> parentArr;
vector<int> lockedArr;
vector<unordered_set<int>> descLocked;
unordered_map<string, int> nameMap;

bool lockWithSpinLock(const string& name, int uid) {
    int node = nameMap[name];
    
    // 1. Gather path from node to root
    vector<int> path;
    int cur = node;
    while (cur != -1) {
        path.push_back(cur);
        cur = parentArr[cur];
    }
    
    // 2. Acquire spinlocks in leaf-to-root order
    for (int p : path) {
        nodeLocks[p].lock();
    }
    
    // 3. Critical Section — safe now
    bool success = true;
    
    if (lockedArr[node] != -1) success = false;
    if (success && !descLocked[node].empty()) success = false;
    
    if (success) {
        for (int i = 1; i < (int)path.size(); i++) {
            if (lockedArr[path[i]] != -1) {
                success = false;
                break;
            }
        }
    }
    
    if (success) {
        lockedArr[node] = uid;
        for (int i = 1; i < (int)path.size(); i++) {
            descLocked[path[i]].insert(node);
        }
    }
    
    // 4. Release spinlocks in reverse order (root to leaf)
    for (auto it = path.rbegin(); it != path.rend(); ++it) {
        nodeLocks[*it].unlock();
    }
    
    return success;
}

🔑 `volatile` vs Memory Barriers — Critical Distinction

`volatile` in C/C++:

ONLY prevents the compiler from caching the variable in a CPU register
DOES NOT prevent CPU out-of-order execution
DOES NOT guarantee atomicity
DOES NOT emit memory fences

`volatile` in Java:

DOES emit memory fences (happens-before relationship)
DOES guarantee visibility across threads
MUCH stronger than C/C++ volatile

Memory Barriers/Fences:

__sync_lock_test_and_set has an Acquire barrier built in
__sync_lock_release has a Release barrier built in
These ensure: writes before unlock are visible to the thread that next acquires the lock

📝 What to Say to the Interviewer

"Since std::mutex has OS sleep overhead (~3000 ns) for a ~30 ns critical section, I'll build a custom spinlock using __sync_lock_test_and_set, which maps to the x86 XCHG instruction. It atomically reads and writes a flag in one CPU cycle. I'll use the TTAS optimization to avoid cache-line ping-pong during spinning. Each node gets its own spinlock, and I acquire them leaf-to-root to prevent deadlocks."

"If you need a TRUE mutex (not just a binary semaphore), I'll track the owning thread ID and use Compare-And-Swap (compare_exchange_weak) instead of plain Test-And-Set, and verify ownership in unlock()."

02_custom_mutex_spinlock.md