runtime: implement race-free signals using futexes

This requires an API introduced in MacOS 11. I think that's fine, since
the version before that (MacOS 10.15) is EOL since 2022. Though if
needed, we could certainly work around it by using an older and slightly
less nice API.

10 files changed, 247 insertions, 178 deletions

diff --git a/GNUmakefile b/GNUmakefile
index 2bf023c62..5f82599e7 100644
--- a/GNUmakefile
+++ b/GNUmakefile
@@ -935,6 +935,7 @@ endif
 	@cp -rp lib/musl/src/malloc          build/release/tinygo/lib/musl/src
 	@cp -rp lib/musl/src/mman            build/release/tinygo/lib/musl/src
 	@cp -rp lib/musl/src/math            build/release/tinygo/lib/musl/src
+	@cp -rp lib/musl/src/misc            build/release/tinygo/lib/musl/src
 	@cp -rp lib/musl/src/multibyte       build/release/tinygo/lib/musl/src
 	@cp -rp lib/musl/src/signal          build/release/tinygo/lib/musl/src
 	@cp -rp lib/musl/src/stdio           build/release/tinygo/lib/musl/src
diff --git a/builder/musl.go b/builder/musl.go
index b156430d4..3c79c7c43 100644
--- a/builder/musl.go
+++ b/builder/musl.go
@@ -128,6 +128,7 @@ var libMusl = Library{
 			"malloc/mallocng/*.c",
 			"mman/*.c",
 			"math/*.c",
+			"misc/*.c",
 			"multibyte/*.c",
 			"signal/" + arch + "/*.s",
 			"signal/*.c",
diff --git a/compileopts/target.go b/compileopts/target.go
index 3dc8af02f..f60ee3097 100644
--- a/compileopts/target.go
+++ b/compileopts/target.go
@@ -390,6 +390,7 @@ func defaultTarget(options *Options) (*TargetSpec, error) {
 			"-platform_version", "macos", platformVersion, platformVersion,
 		)
 		spec.ExtraFiles = append(spec.ExtraFiles,
+			"src/internal/futex/futex_darwin.c",
 			"src/runtime/os_darwin.c",
 			"src/runtime/runtime_unix.c",
 			"src/runtime/signal.c")
@@ -413,6 +414,7 @@ func defaultTarget(options *Options) (*TargetSpec, error) {
 			spec.CFlags = append(spec.CFlags, "-mno-outline-atomics")
 		}
 		spec.ExtraFiles = append(spec.ExtraFiles,
+			"src/internal/futex/futex_linux.c",
 			"src/runtime/runtime_unix.c",
 			"src/runtime/signal.c")
 	case "windows":
diff --git a/lib/macos-minimal-sdk b/lib/macos-minimal-sdk
-Subproject 4e4113e3b1244b8fdc5e1486577f25e22d63f36
+Subproject 9b69407cb59f8ccbb674bb77b358df7befcbb42
diff --git a/loader/goroot.go b/loader/goroot.go
index 631cc6e7e..5442df9b5 100644
--- a/loader/goroot.go
+++ b/loader/goroot.go
@@ -243,6 +243,7 @@ func pathsToOverride(goMinor int, needsSyscallPackage bool) map[string]bool {
 		"internal/binary/":            false,
 		"internal/bytealg/":           false,
 		"internal/cm/":                false,
+		"internal/futex/":             false,
 		"internal/fuzz/":              false,
 		"internal/reflectlite/":       false,
 		"internal/gclayout":           false,
diff --git a/src/internal/futex/futex.go b/src/internal/futex/futex.go
new file mode 100644
index 000000000..5ecdd79c2
--- /dev/null
+++ b/src/internal/futex/futex.go
@@ -0,0 +1,72 @@
+package futex
+
+// Cross platform futex implementation.
+// Futexes are supported on all major operating systems and on WebAssembly.
+//
+// For more information, see: https://outerproduct.net/futex-dictionary.html
+
+import (
+	"sync/atomic"
+	"unsafe"
+)
+
+// A futex is a way for userspace to wait with the pointer as the key, and for
+// another thread to wake one or all waiting threads keyed on the same pointer.
+//
+// A futex does not change the underlying value, it only reads it before going
+// to sleep (atomically) to prevent lost wake-ups.
+type Futex struct {
+	atomic.Uint32
+}
+
+// Atomically check for cmp to still be equal to the futex value and if so, go
+// to sleep. Return true if we were definitely awoken by a call to Wake or
+// WakeAll, and false if we can't be sure of that.
+func (f *Futex) Wait(cmp uint32) bool {
+	tinygo_futex_wait((*uint32)(unsafe.Pointer(&f.Uint32)), cmp)
+
+	// We *could* detect a zero return value from the futex system call which
+	// would indicate we got awoken by a Wake or WakeAll call. However, this is
+	// what the manual page has to say:
+	//
+	// > Note that a wake-up can also be caused by common futex usage patterns
+	// > in unrelated code that happened to have previously used the futex
+	// > word's memory location (e.g., typical futex-based implementations of
+	// > Pthreads mutexes can cause this under some conditions). Therefore,
+	// > callers should always conservatively assume that a return value of 0
+	// > can mean a spurious wake-up, and use the futex word's value (i.e., the
+	// > user-space synchronization scheme) to decide whether to continue to
+	// > block or not.
+	//
+	// I'm not sure whether we do anything like pthread does, so to be on the
+	// safe side we say we don't know whether the wakeup was spurious or not and
+	// return false.
+	return false
+}
+
+// Like Wait, but times out after the number of nanoseconds in timeout.
+func (f *Futex) WaitUntil(cmp uint32, timeout uint64) {
+	tinygo_futex_wait_timeout((*uint32)(unsafe.Pointer(&f.Uint32)), cmp, timeout)
+}
+
+// Wake a single waiter.
+func (f *Futex) Wake() {
+	tinygo_futex_wake((*uint32)(unsafe.Pointer(&f.Uint32)))
+}
+
+// Wake all waiters.
+func (f *Futex) WakeAll() {
+	tinygo_futex_wake_all((*uint32)(unsafe.Pointer(&f.Uint32)))
+}
+
+//export tinygo_futex_wait
+func tinygo_futex_wait(addr *uint32, cmp uint32)
+
+//export tinygo_futex_wait_timeout
+func tinygo_futex_wait_timeout(addr *uint32, cmp uint32, timeout uint64)
+
+//export tinygo_futex_wake
+func tinygo_futex_wake(addr *uint32)
+
+//export tinygo_futex_wake_all
+func tinygo_futex_wake_all(addr *uint32)
diff --git a/src/internal/futex/futex_darwin.c b/src/internal/futex/futex_darwin.c
new file mode 100644
index 000000000..358a87655
--- /dev/null
+++ b/src/internal/futex/futex_darwin.c
@@ -0,0 +1,49 @@
+//go:build none
+
+// This file is manually included, to avoid CGo which would cause a circular
+// import.
+
+#include <stdint.h>
+
+// This API isn't documented by Apple, but it is used by LLVM libc++ (so should
+// be stable) and has been documented extensively here:
+// https://outerproduct.net/futex-dictionary.html
+
+int __ulock_wait(uint32_t operation, void *addr, uint64_t value, uint32_t timeout_us);
+int __ulock_wait2(uint32_t operation, void *addr, uint64_t value, uint64_t timeout_ns, uint64_t value2);
+int __ulock_wake(uint32_t operation, void *addr, uint64_t wake_value);
+
+// Operation code.
+#define UL_COMPARE_AND_WAIT 1
+
+// Flags to the operation value.
+#define ULF_WAKE_ALL 0x00000100
+#define ULF_NO_ERRNO 0x01000000
+
+void tinygo_futex_wait(uint32_t *addr, uint32_t cmp) {
+    __ulock_wait(UL_COMPARE_AND_WAIT|ULF_NO_ERRNO, addr, (uint64_t)cmp, 0);
+}
+
+void tinygo_futex_wait_timeout(uint32_t *addr, uint32_t cmp, uint64_t timeout) {
+    // Make sure that an accidental use of a zero timeout is not treated as an
+    // infinite timeout. Return if it's zero since it wouldn't be waiting for
+    // any significant time anyway.
+    // Probably unnecessary, but guards against potential bugs.
+    if (timeout == 0) {
+        return;
+    }
+
+    // Note: __ulock_wait2 is available since MacOS 11.
+    // I think that's fine, since the version before that (MacOS 10.15) is EOL
+    // since 2022. Though if needed, we could certainly use __ulock_wait instead
+    // and deal with the smaller timeout value.
+    __ulock_wait2(UL_COMPARE_AND_WAIT|ULF_NO_ERRNO, addr, (uint64_t)cmp, timeout, 0);
+}
+
+void tinygo_futex_wake(uint32_t *addr) {
+    __ulock_wake(UL_COMPARE_AND_WAIT|ULF_NO_ERRNO, addr, 0);
+}
+
+void tinygo_futex_wake_all(uint32_t *addr) {
+    __ulock_wake(UL_COMPARE_AND_WAIT|ULF_NO_ERRNO|ULF_WAKE_ALL, addr, 0);
+}
diff --git a/src/internal/futex/futex_linux.c b/src/internal/futex/futex_linux.c
new file mode 100644
index 000000000..ffefc97e4
--- /dev/null
+++ b/src/internal/futex/futex_linux.c
@@ -0,0 +1,33 @@
+//go:build none
+
+// This file is manually included, to avoid CGo which would cause a circular
+// import.
+
+#include <limits.h>
+#include <stdint.h>
+#include <sys/syscall.h>
+#include <time.h>
+#include <unistd.h>
+
+#define FUTEX_WAIT         0
+#define FUTEX_WAKE         1
+#define FUTEX_PRIVATE_FLAG 128
+
+void tinygo_futex_wait(uint32_t *addr, uint32_t cmp) {
+    syscall(SYS_futex, addr, FUTEX_WAIT|FUTEX_PRIVATE_FLAG, cmp, NULL, NULL, 0);
+}
+
+void tinygo_futex_wait_timeout(uint32_t *addr, uint32_t cmp, uint64_t timeout) {
+    struct timespec ts = {0};
+    ts.tv_sec = timeout / 1000000000;
+    ts.tv_nsec = timeout % 1000000000;
+    syscall(SYS_futex, addr, FUTEX_WAIT|FUTEX_PRIVATE_FLAG, cmp, &ts, NULL, 0);
+}
+
+void tinygo_futex_wake(uint32_t *addr) {
+    syscall(SYS_futex, addr, FUTEX_WAKE|FUTEX_PRIVATE_FLAG, 1, NULL, NULL, 0);
+}
+
+void tinygo_futex_wake_all(uint32_t *addr) {
+    syscall(SYS_futex, addr, FUTEX_WAKE|FUTEX_PRIVATE_FLAG, INT_MAX, NULL, NULL, 0);
+}
diff --git a/src/runtime/runtime_unix.go b/src/runtime/runtime_unix.go
index 3b20330e2..fc577066e 100644
--- a/src/runtime/runtime_unix.go
+++ b/src/runtime/runtime_unix.go
@@ -3,6 +3,8 @@
 package runtime
 
 import (
+	"internal/futex"
+	"internal/task"
 	"math/bits"
 	"sync/atomic"
 	"tinygo"
@@ -223,46 +225,30 @@ func nanosecondsToTicks(ns int64) timeUnit {
 }
 
 func sleepTicks(d timeUnit) {
-	// When there are no signal handlers present, we can simply go to sleep.
-	if !hasSignals {
-		// timeUnit is in nanoseconds, so need to convert to microseconds here.
-		usleep(uint(d) / 1000)
-		return
-	}
+	until := ticks() + d
 
-	if GOOS == "darwin" {
-		// Check for incoming signals.
-		if checkSignals() {
-			// Received a signal, so there's probably at least one goroutine
-			// that's runnable again.
-			return
+	for {
+		// Sleep for the given amount of time.
+		// If a signal arrived before going to sleep, or during the sleep, the
+		// sleep will exit early.
+		signalFutex.WaitUntil(0, uint64(ticksToNanoseconds(d)))
+
+		// Check whether there was a signal before or during the call to
+		// WaitUntil.
+		if signalFutex.Swap(0) != 0 {
+			if checkSignals() && hasScheduler {
+				// We got a signal, so return to the scheduler.
+				// (If there is no scheduler, there is no other goroutine that
+				// might need to run now).
+				return
+			}
 		}
 
-		// WARNING: there is a race condition here. If a signal arrives between
-		// checkSignals() and usleep(), the usleep() call will not exit early so
-		// the signal is delayed until usleep finishes or another signal
-		// arrives.
-		// There doesn't appear to be a simple way to fix this on MacOS.
-
-		// timeUnit is in nanoseconds, so need to convert to microseconds here.
-		result := usleep(uint(d) / 1000)
-		if result != 0 {
-			checkSignals()
-		}
-	} else {
-		// Linux (and various other POSIX systems) implement sigtimedwait so we
-		// can do this in a non-racy way.
-		tinygo_wfi_mask(activeSignals)
-		if checkSignals() {
-			tinygo_wfi_unmask()
+		// Set duration (in next loop iteration) to the remaining time.
+		d = until - ticks()
+		if d <= 0 {
 			return
 		}
-		signal := tinygo_wfi_sleep(activeSignals, uint64(d))
-		if signal >= 0 {
-			tinygo_signal_handler(signal)
-			checkSignals()
-		}
-		tinygo_wfi_unmask()
 	}
 }
 
@@ -353,21 +339,21 @@ func growHeap() bool {
 	return true
 }
 
-func init() {
-	// Set up a channel to receive signals into.
-	signalChan = make(chan uint32, 1)
-}
-
-var signalChan chan uint32
-
 // Indicate whether signals have been registered.
 var hasSignals bool
 
+// Futex for the signal handler.
+// The value is 0 when there are no new signals, or 1 when there are unhandled
+// signals and the main thread doesn't know about it yet.
+// When a signal arrives, the futex value is changed to 1 and if it was 0
+// before, all waiters are awoken.
+// When a wait exits, the value is changed to 0 and if it wasn't 0 before, the
+// signals are checked.
+var signalFutex futex.Futex
+
 // Mask of signals that have been received. The signal handler atomically ORs
 // signals into this value.
-var receivedSignals uint32
-
-var activeSignals uint32
+var receivedSignals atomic.Uint32
 
 //go:linkname signal_enable os/signal.signal_enable
 func signal_enable(s uint32) {
@@ -377,7 +363,6 @@ func signal_enable(s uint32) {
 		runtimePanicAt(returnAddress(0), "unsupported signal number")
 	}
 	hasSignals = true
-	activeSignals |= 1 << s
 	// It's easier to implement this function in C.
 	tinygo_signal_enable(s)
 }
@@ -389,7 +374,6 @@ func signal_ignore(s uint32) {
 		// receivedSignals into a uint32 array.
 		runtimePanicAt(returnAddress(0), "unsupported signal number")
 	}
-	activeSignals &^= 1 << s
 	tinygo_signal_ignore(s)
 }
 
@@ -400,20 +384,13 @@ func signal_disable(s uint32) {
 		// receivedSignals into a uint32 array.
 		runtimePanicAt(returnAddress(0), "unsupported signal number")
 	}
-	activeSignals &^= 1 << s
 	tinygo_signal_disable(s)
 }
 
 //go:linkname signal_waitUntilIdle os/signal.signalWaitUntilIdle
 func signal_waitUntilIdle() {
-	// Make sure all signals are sent on the channel.
-	for atomic.LoadUint32(&receivedSignals) != 0 {
-		checkSignals()
-		Gosched()
-	}
-
-	// Make sure all signals are processed.
-	for len(signalChan) != 0 {
+	// Wait until signal_recv has processed all signals.
+	for receivedSignals.Load() != 0 {
 		Gosched()
 	}
 }
@@ -431,102 +408,93 @@ func tinygo_signal_disable(s uint32)
 //
 //export tinygo_signal_handler
 func tinygo_signal_handler(s int32) {
-	// This loop is essentially the atomic equivalent of the following:
+	// The following loop is equivalent to the following:
 	//
-	//   receivedSignals |= 1 << s
+	//     receivedSignals.Or(uint32(1) << uint32(s))
 	//
-	// TODO: use atomic.Uint32.And once we drop support for Go 1.22 instead of
-	// this loop.
+	// TODO: use this instead of a loop once we drop support for Go 1.22.
 	for {
 		mask := uint32(1) << uint32(s)
-		val := atomic.LoadUint32(&receivedSignals)
-		swapped := atomic.CompareAndSwapUint32(&receivedSignals, val, val|mask)
+		val := receivedSignals.Load()
+		swapped := receivedSignals.CompareAndSwap(val, val|mask)
 		if swapped {
 			break
 		}
 	}
+
+	// Notify the main thread that there was a signal.
+	// This will exit the call to Wait or WaitUntil early.
+	if signalFutex.Swap(1) == 0 {
+		// Changed from 0 to 1, so there may have been a waiting goroutine.
+		// This could be optimized to avoid a syscall when there are no waiting
+		// goroutines.
+		signalFutex.WakeAll()
+	}
 }
 
+// Task waiting for a signal to arrive, or nil if it is running or there are no
+// signals.
+var signalRecvWaiter *task.Task
+
 //go:linkname signal_recv os/signal.signal_recv
 func signal_recv() uint32 {
 	// Function called from os/signal to get the next received signal.
-	val := <-signalChan
-	checkSignals()
-	return val
-}
-
-// Atomically find a signal that previously occured and send it into the
-// signalChan channel. Return true if at least one signal was delivered this
-// way, false otherwise.
-func checkSignals() bool {
-	gotSignals := false
 	for {
-		// Extract the lowest numbered signal number from receivedSignals.
-		val := atomic.LoadUint32(&receivedSignals)
+		val := receivedSignals.Load()
 		if val == 0 {
-			// There is no signal ready to be received by the program (common
-			// case).
-			return gotSignals
+			// There are no signals to receive. Sleep until there are.
+			signalRecvWaiter = task.Current()
+			task.Pause()
+			continue
 		}
-		num := uint32(bits.TrailingZeros32(val))
 
-		// Do a non-blocking send on signalChan.
-		select {
-		case signalChan <- num:
-			// There was room free in the channel, so remove the signal number
-			// from the receivedSignals mask.
-			gotSignals = true
-		default:
-			// Could not send the signal number on the channel. This means
-			// there's still a signal pending. In that case, let it be received
-			// at which point checkSignals is called again to put the next one
-			// in the channel buffer.
-			return gotSignals
-		}
+		// Extract the lowest numbered signal number from receivedSignals.
+		num := uint32(bits.TrailingZeros32(val))
 
 		// Atomically clear the signal number from receivedSignals.
-		// TODO: use atomic.Uint32.Or once we drop support for Go 1.22 instead
-		// of this loop.
+		// TODO: use atomic.Uint32.And once we drop support for Go 1.22 instead
+		// of this loop, like so:
+		//
+		//   receivedSignals.And(^(uint32(1) << num))
+		//
 		for {
 			newVal := val &^ (1 << num)
-			swapped := atomic.CompareAndSwapUint32(&receivedSignals, val, newVal)
+			swapped := receivedSignals.CompareAndSwap(val, newVal)
 			if swapped {
 				break
 			}
-			val = atomic.LoadUint32(&receivedSignals)
+			val = receivedSignals.Load()
 		}
+
+		return num
 	}
 }
 
-//export tinygo_wfi_mask
-func tinygo_wfi_mask(active uint32)
-
-//export tinygo_wfi_sleep
-func tinygo_wfi_sleep(active uint32, timeout uint64) int32
-
-//export tinygo_wfi_wait
-func tinygo_wfi_wait(active uint32) int32
-
-//export tinygo_wfi_unmask
-func tinygo_wfi_unmask()
+// Reactivate the goroutine waiting for signals, if there are any.
+// Return true if it was reactivated (and therefore the scheduler should run
+// again), and false otherwise.
+func checkSignals() bool {
+	if receivedSignals.Load() != 0 && signalRecvWaiter != nil {
+		runqueuePushBack(signalRecvWaiter)
+		signalRecvWaiter = nil
+		return true
+	}
+	return false
+}
 
 func waitForEvents() {
 	if hasSignals {
-		// We could have used pause() here, but that function is impossible to
-		// use in a race-free way:
-		// https://www.cipht.net/2023/11/30/perils-of-pause.html
-		// Therefore we need something better.
-		// Note: this is unsafe with multithreading, because sigprocmask is only
-		// defined for single-threaded applictions.
-		tinygo_wfi_mask(activeSignals)
-		if checkSignals() {
-			tinygo_wfi_unmask()
-			return
+		// Wait as long as the futex value is 0.
+		// This can happen either before or during the call to Wait.
+		// This can be optimized: if the value is nonzero we don't need to do a
+		// futex wait syscall and can instead immediately call checkSignals.
+		signalFutex.Wait(0)
+
+		// Check for signals that arrived before or during the call to Wait.
+		// If there are any signals, the value is 0.
+		if signalFutex.Swap(0) != 0 {
+			checkSignals()
 		}
-		signal := tinygo_wfi_wait(activeSignals)
-		tinygo_signal_handler(signal)
-		checkSignals()
-		tinygo_wfi_unmask()
 	} else {
 		// The program doesn't use signals, so this is a deadlock.
 		runtimePanic("deadlocked: no event source")
diff --git a/src/runtime/signal.c b/src/runtime/signal.c
index ba4338a6d..87af43011 100644
--- a/src/runtime/signal.c
+++ b/src/runtime/signal.c
@@ -30,61 +30,3 @@ void tinygo_signal_disable(uint32_t sig) {
     act.sa_handler = SIG_DFL;
     sigaction(sig, &act, NULL);
 }
-
-// Implement waitForEvents and sleep with signals.
-// Warning: sigprocmask is not defined in a multithreaded program so will need
-// to be replaced with something else once we implement threading on POSIX.
-
-// Signals active before a call to tinygo_wfi_mask.
-static sigset_t active_signals;
-
-static void tinygo_set_signals(sigset_t *mask, uint32_t signals) {
-    sigemptyset(mask);
-    for (int i=0; i<32; i++) {
-        if ((signals & (1<<i)) != 0) {
-            sigaddset(mask, i);
-        }
-    }
-}
-
-// Mask the given signals.
-// This function must always restore the previous signals using
-// tinygo_wfi_unmask, to create a critical section.
-void tinygo_wfi_mask(uint32_t active) {
-    sigset_t mask;
-    tinygo_set_signals(&mask, active);
-
-    sigprocmask(SIG_BLOCK, &mask, &active_signals);
-}
-
-// Wait until a signal becomes pending (or is already pending), and return the
-// signal.
-#if !defined(__APPLE__)
-int tinygo_wfi_sleep(uint32_t active, uint64_t timeout) {
-    sigset_t active_set;
-    tinygo_set_signals(&active_set, active);
-
-    struct timespec ts = {0};
-    ts.tv_sec  = timeout / 1000000000;
-    ts.tv_nsec = timeout % 1000000000;
-
-    int result = sigtimedwait(&active_set, NULL, &ts);
-    return result;
-}
-#endif
-
-// Wait until any of the active signals becomes pending (or returns immediately
-// if one is already pending).
-int tinygo_wfi_wait(uint32_t active) {
-    sigset_t active_set;
-    tinygo_set_signals(&active_set, active);
-
-    int sig = 0;
-    sigwait(&active_set, &sig);
-    return sig;
-}
-
-// Restore previous signal mask.
-void tinygo_wfi_unmask(void) {
-    sigprocmask(SIG_SETMASK, &active_signals, NULL);
-}