dymokomi/luce-base
Source of release 0.45.0
0.45.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