Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-base

Source of release 0.46.0

0.46.0 / src / std / sync.lucb

#==============================================================================================
#
#   sync - Locks, conditions, once and semaphores
#
#   DESCRIPTION:
#       Blocking synchronisation over the host's futex-like wait and wake: a mutex, a condition
#       variable, a run-once gate, and a counting semaphore.
#
#       The host's sleep returns on wakes nothing here sent: Linux and macOS rarely, and
#       Windows often when a thread waiting on an address less than 32 bytes away is woken.
#       Every sleep below checks its own word again and sleeps again when it has not
#       changed, so such a wake costs a context switch and is never seen by a caller.
#
#==============================================================================================

import platform
import time

## macOS: the `ulock` calls libSystem builds its own locks on.
extern func __ulock_wait(operation: u32, address: void*, value: u64, timeout: u32) -> i32
extern func __ulock_wake(operation: u32, address: void*, wake_value: u64) -> i32
## Linux: the futex system call, through `syscall`; the number is the architecture's.
extern func syscall(number: i64, ...) -> i64
extern func WaitOnAddress(address: void*, comparison: u32*, size: usize, milliseconds: u32) -> i32
extern func WakeByAddressSingle(address: void*)
extern func WakeByAddressAll(address: void*)

let compare_and_wait: u32 = 1
let wake_all: u32 = 256
let futex_number: i64 = 98 if platform.arm64 else 202
let futex_wait_private: i32 = 128
let futex_wake_private: i32 = 129

## Sleep in the kernel while the word at `address` still holds `value`; a change
## or a wake returns, and so may nothing at all, so every caller loops.
func sleep_on(address: void*, value: u32):
    if platform.windows:
        var expected = value
        _ = WaitOnAddress(address, &expected, 4, 4294967295)
    elif platform.macos:
        _ = __ulock_wait(compare_and_wait, address, (u64)value, 0)
    else:
        let no_timeout: void*? = none
        _ = syscall(futex_number, address, futex_wait_private, value, no_timeout)

## `sleep_on`, giving up after about `milliseconds`: a timeout, a change, a wake or nothing
## at all return, so every caller loops against its own deadline.
func sleep_on_for(address: void*, value: u32, milliseconds: u64):
    if milliseconds == 0:
        return
    if platform.windows:
        var expected = value
        _ = WaitOnAddress(address, &expected, 4, (u32)(milliseconds if milliseconds < 4294967294 else 4294967294))
    elif platform.macos:
        # microseconds, where 0 would wait for ever
        let micros = milliseconds *? 1000 else 4294967295
        _ = __ulock_wait(compare_and_wait, address, (u64)value, (u32)(micros if micros < 4294967295 else 4294967295))
    else:
        var timeout = Timeout(seconds = (i64)(milliseconds // 1000), nanoseconds = (i64)(milliseconds % 1000) * 1000000)
        _ = syscall(futex_number, address, futex_wait_private, value, &timeout)

## A relative `timespec` for the futex call.
extern struct Timeout:
    seconds: i64
    nanoseconds: i64

func wake_one(address: void*):
    if platform.windows:
        WakeByAddressSingle(address)
    elif platform.macos:
        _ = __ulock_wake(compare_and_wait, address, 0)
    else:
        _ = syscall(futex_number, address, futex_wake_private, 1)

func wake_every(address: void*):
    if platform.windows:
        WakeByAddressAll(address)
    elif platform.macos:
        _ = __ulock_wake(compare_and_wait | wake_all, address, 0)
    else:
        _ = syscall(futex_number, address, futex_wake_private, 2147483647)

## A lock whose waiters sleep: zero is unlocked, so `var lock: Mutex` is ready to
## use; one is locked; two is locked with someone asleep on it.
## A mutual-exclusion lock; a waiter sleeps until it is free.
pub struct Mutex:
    var state: @u32

    ## Acquire the lock, blocking until it is free.
    pub func lock():
        let (taken, seen) = self.state.cas(0, 1, .acquire, .relaxed)
        if taken:
            return
        var current = seen
        if current != 2:
            current = self.state.swap(2, .acquire)
        while current != 0:
            sleep_on((void*)&self.state, 2)
            # still held with sleepers: not the holder's wake, so sleep again
            if self.state.load(.relaxed) == 2:
                continue
            current = self.state.swap(2, .acquire)

    ## Release the lock and wake one waiter.
    pub func unlock():
        if self.state.swap(0, .release) == 2:
            wake_one((void*)&self.state)

    ## Acquire the lock without blocking; whether it was taken.
    pub func try_lock() -> bool:
        let (taken, seen) = self.state.cas(0, 1, .acquire, .relaxed)
        _ = seen
        return taken

## A sequence number waiters watch; every signal advances it and wakes.
## A condition variable: waiters sleep until signalled. As with every condition variable,
## a waiter checks its predicate in a loop around `wait`: a signal says that something
## changed, not what, and another thread may have acted on it first.
pub struct Condition:
    var sequence: @u32

    ## Release `mutex`, sleep until signalled, then reacquire it. A wake with no signal
    ## since the call is not returned; a signal or broadcast meant for another waiter may be.
    pub func wait(mutex: Mutex*):
        let seen = self.sequence.load(.acquire)
        mutex.unlock()
        while self.sequence.load(.acquire) == seen:
            sleep_on((void*)&self.sequence, seen)
        mutex.lock()

    ## `wait`, giving up after about `milliseconds`; a caller tells a timeout from a signal
    ## by checking its predicate.
    pub func wait_for(mutex: Mutex*, milliseconds: u64):
        let seen = self.sequence.load(.acquire)
        mutex.unlock()
        let start = time.now()
        var left = milliseconds
        while left > 0 and self.sequence.load(.acquire) == seen:
            sleep_on_for((void*)&self.sequence, seen, left)
            let waited = time.since(start) // 1000000
            left = milliseconds - waited if waited < milliseconds else 0
        mutex.lock()

    ## Wake one waiter.
    pub func signal():
        _ = self.sequence.add(1, .release)
        wake_one((void*)&self.sequence)

    ## Wake every waiter.
    pub func broadcast():
        _ = self.sequence.add(1, .release)
        wake_every((void*)&self.sequence)

## Runs its function exactly once; later callers wait for the first to finish.
## Runs a function exactly once; later callers wait for the first.
pub struct Once:
    var state: @u32

    ## Run `function` on the first call; later calls wait for it to finish.
    pub func run(function: func() -> unit):
        let (first, seen) = self.state.cas(0, 1, .acq_rel, .acquire)
        _ = seen
        if first:
            function()
            self.state.store(2, .release)
            wake_every((void*)&self.state)
            return
        while self.state.load(.acquire) != 2:
            sleep_on((void*)&self.state, 1)

## A counting semaphore whose waiters sleep.
## A counting semaphore whose waiters sleep.
pub struct Semaphore:
    var count: @u32

    ## Take one permit, blocking until one is available.
    pub func acquire():
        while true:
            let n = self.count.load(.acquire)
            if n > 0:
                let (taken, seen) = self.count.cas(n, n - 1, .acq_rel, .relaxed)
                _ = seen
                if taken:
                    return
            else:
                sleep_on((void*)&self.count, 0)

    ## Return one permit and wake one waiter.
    pub func release():
        _ = self.count.add(1, .release)
        wake_one((void*)&self.count)

# mark: Cancellation ========================================================================

## A one-way cancellation signal shared by reference. Zero is not requested.
## Keep this object alive until every waiting thread returns; do not copy or reset
## it while shared. Requests use release/acquire synchronization.
pub struct Cancellation:
    var requested: @u32

    ## Request cancellation.
    pub func request():
        self.requested.store(1, .release)

    ## Whether cancellation was requested.
    pub func is_requested() -> bool:
        return self.requested.load(.acquire) != 0