vyukov_mutex

type Event:
    wait()
    set()

type Link:
    get(ptr: Ptr):
        if LOAD(ptr, Acquire) |value|:
            return value
        
        e = Event{}
        if SWAP(ptr, cast(Ptr, &e), Release) |value|:
            FENCE(ptr, Acquire)
            return value
        
        e.wait()
        return ptr orelse unreachable
    
    set(ptr: Ptr, value):
        if SWAP(ptr, value, Release) |old|:
            FENCE(ptr, Acquire)
            cast(*Event, old).set()
    

type Mutex:
    state: ?*Waiter = null
    
    const locked = ?*Waiter(@alignOf(Waiter))
    
    type Waiter:
        prev: ?*Waiter = null
        next: ?*Waiter = null
        head: ?*Waiter = null
        tail: ?*Waiter = null
        signal: ?*Waiter = null
    
    pub try_lock():
        return CAS(&state, null, locked, Acquire, Relaxed) != null
        
    pub lock():
        _ = CAS_WEAK(&state, null, locked, Acquire, Relaxed) orelse return
        lock_slow()
        
    @cold
    lock_slow():
        w = Waiter{}
        w.tail = &w
        loop:
            tail = w.tail orelse unreachable
            if SWAP(&state, tail, Release) |prev|:
                Link.set(&w.prev, prev)
                _ = Link.get(&w.signal)
                w.signal = null
                continue
                
            if &w == tail:
                s = CAS(&state, head, locked, Acquire, Acquire) orelse return
                tail = s orelse unreachable
                w.prev = locked
                _ = find_tail(head)
                
            next = w.next orelse unreachable
            next.prev = lock
            tail.head = next
            return
    
    pub unlock():
        old = SWAP(&state, null, Release) orelse unreachable
        if old != locked:
            unlock_slow(old)
    
    @cold
    unlock_slow(tail):
        FENCE(&state, Acquire)
        head = find_head(tail)
        head.prev = null
        head.tail = tail
        Link.set(&head.signal, locked)
        
    find_head(tail):
        current = tail
        loop:
            current = current.head orelse current
            prev = Link.get(&current.prev)
            if prev == current:
                tail.head = current
                return current
            else:
                prev.next = current
                current = prev