Futex Based RwLock.txt

unlocked = 0
readers_parked = 1 << 0
writers_parked = 1 << 1

value = 1 << 2
mask = ~(value - 1)

reader = value
writer = mask

type RwLock:
    state: u32 = 0
    epoch: u32 = 0

    try_write():
        return CAS(&state, unlocked, writer, Acquire) == null

    write():
        s = CAS(&state, unlocked, writer, Acquire) orelse return
        acquire_with = 0

        loop:
            while s & mask == unlocked:
                s = CAS(&state, s, s|writer|acquire_with, Acquire) orelse return

            if s & writers_parked == 0:
                if CAS(&state, s, s|writers_parked, Relaxed) |new_s|:
                    s = new_s
                    continue
            
            loop:
                e = LOAD(&epoch, Acquire)

                s = LOAD(&state, Relaxed)
                if (s & mask == unlocked) or (s & writers_parked == 0):
                    break

                WAIT(&epoch, e)
                acquire_with = writers_parked

    unlock_write():
        s = CAS(&state, writer, unlocked, Release) orelse return
        assert(s & mask == writer)

        p = s & (readers_parked | writers_parked)
        assert(p != 0)

        if p != (readers_parked | writers_parked):
            if CAS(&state, s, s & ~(writer | p), Release) |new_s|:
                assert(new_s == (writer | readers_parked | writers_parked))
                p = readers_parked | writers_parked

        if p == (readers_parked | writers_parked):
            STORE(&state, writers_parked, Release)
            p = readers_parked

        if p == readers_parked:
            WAKE(&state, max(u32))
            return

        assert(p == writers_parked)
        _ = ADD(&epoch, 1, Release)
        WAKE(&epoch, 1)

    try_read():
        s = unlocked
        while s & mask < (writer - 1):
            s = CAS(&state, s, s + reader, Acquire) orelse return true
        return false

    read():
        s = LOAD(&state)
        if s & mask < (writer - 1):
            s = CAS(&state, unlocked, reader, Acquire) orelse return

        loop:
            while s & mask < writer:
                assert(s + READER < writer)
                s = CAS(&state, s, s + READER, Acquire) orelse return

            if s & readers_parked == 0:
                if CAS(&state, s, s|readers_parked, Relaxed) |new_s|:
                    s = new_s
                    continue
            
            WAIT(&state, s|readers_parked)
            s = LOAD(&state, Relaxed)

    unlock_read():
        s = SUB(&state, reader, Release)
        if s & (mask | writers_parked) != (reader | writers_parked):
            return

        _ = CAS(&state, writers_parked, unlocked, Relaxed) orelse:
            _ = ADD(&epoch, 1, Release)
            WAKE(&epoch, 1)
            return