tiny-parking-lot

parking_lot is an alternative to rust's std concurrent primitives (mutex, rwlock, condvar). was way faster until rust 1.62 (july 2022)
the core idea is using userspace queue instead of calling OS mutex

done:

• RawMutex
• ThreadParker (just a std::thread, no custom linux/win implementations)
• Spinwait
• WordLock
• Mutex
• RwLock

surprised:

• using requeued_threads for a condvar, cleverly moving it to a mutex queue
• prepare_park - optimization to immediately prevent park if some thread was unparked just before the first thread went to sleep (race condition)
• atomically possible to downgrade from write lock to read lock
• validate callback to prevent race conditions
• using lower bits of WordLock's AtomicPtr for flags (storing flags in the pointer itself, possible cuz of alignment - zero bits at the end)
• word lock and core parking both doing FIFO but word lock have to use LIFO structure cuz it doesnt have lock (only lock-free CAS)

out of scope (lazy):

• condvar
• parking fairness
• parking hashtable resizing
• deadlock detection
• rwlock recursive/timed/upgrade

---
config:
  look: neo
  theme: mc
---
graph TD
    subgraph User Thread
        A["mutex.lock()"] --> B{RawMutex};
    end

    subgraph "RawMutex Logic"
        B -- "1. Fast Path" --> C{"CAS on state"};
        C -- Success --> D["Lock Acquired"];
        C -- Contended --> E{SpinWait};
        E -- "Still Contended" --> F["Slow Path: Park"];
    end

    subgraph "Parking Lot API"
        F --> G["parking::park(key, validate, ...)"];
        G --> H{Global HashTable};
        G --> I["thread_local! ThreadData"];
    end

    subgraph "Owner Thread"
        J["mutex.unlock()"] --> K{RawMutex};
        K -- "state has PARKED bit?" --> L["parking::unpark_one(key, ...)"];
        L --> H;
    end

    subgraph "OS Kernel"
        I -- "park()" --> M["Thread Sleeps"];
        H -- "finds waiting thread" --> N["ThreadData.parker.unpark()"];
        N -- "signals OS to wake thread" --> M;
        M -- "woken up, retries lock" --> B;
    end

Loading

---
config:
  look: neo
  theme: mc
---
graph TD
    subgraph "Global State"
        GS["OnceLock<HashTable>"] --> HT(HashTable);
        HT --> B1(Bucket 0);
        HT --> B2(Bucket 1);
        HT --> B_etc("...");
        HT --> BN("Bucket N");
    end

    subgraph "Bucket 1"
        B2 -- contains --> M2[WordLock];
        B2 -- contains --> Q2["Queue Head/Tail"];
    end

    subgraph Threads
        T_A["Thread A<br/><i>(wants to park)</i>"] --> TD_A("thread_local!<br/>ThreadData A");
        T_B["Thread B<br/><i>(already parked)</i>"] --> TD_B("thread_local!<br/>ThreadData B");
        T_C["Thread C<br/><i>(also wants to park)</i>"] --> TD_C("thread_local!<br/>ThreadData C");
    end

    subgraph "Parking Logic"
        Key["Mutex Address<br/>(e.g., 0xABCD_1234)"] --> Hash{"hash(key) % N"};
        Hash -- "e.g., result is 1" --> B2;
        
        T_A -- "1. wants to park on Key" --> Hash;
        T_A -- "2. locks" --> M2;
        T_A -- "3. adds self to queue" --> Q2;
        Q2 -- "linked list" --> TD_B;
        TD_B -- next --> TD_C_in_queue("ThreadData C");
        TD_C_in_queue -- next --> TD_A_in_queue("ThreadData A");
    end

Loading

$RUSTFLAGS="-Zsanitize=thread"; cargo run
cargo test