From 42054d64062da58e44a383d0ed0c1c6bb2ba88e1 Mon Sep 17 00:00:00 2001
From: Thomas Munro <thomas.munro@gmail.com>
Date: Sun, 24 Oct 2021 21:48:26 +1300
Subject: [PATCH 1/3] A basic API for futexes.

A thin wrapper for basic 32 bit futex wait and wake.  Currently, it maps
to native support on Linux, DragonFlyBSD, FreeBSD, OpenBSD and macOS,
with detection via configure/meson.

NetBSD could probably be added, no investigated.  Windows'
WaitOnAddress() can't because it only works between threads.  A
latch-based backend-only fallback implementation is plausible.
---
 configure                    |   4 +-
 configure.ac                 |   5 +
 meson.build                  |   5 +
 src/backend/port/meson.build |   2 +-
 src/include/pg_config.h.in   |  15 +++
 src/include/port/pg_futex.h  | 171 +++++++++++++++++++++++++++++++++++
 6 files changed, 199 insertions(+), 3 deletions(-)
 create mode 100644 src/include/port/pg_futex.h

diff --git a/configure b/configure
index 518c33b73a9..6eb25178dab 100755
--- a/configure
+++ b/configure
@@ -13227,7 +13227,7 @@ fi
 ## Header files
 ##
 
-for ac_header in atomic.h copyfile.h execinfo.h getopt.h ifaddrs.h mbarrier.h sys/epoll.h sys/event.h sys/personality.h sys/prctl.h sys/procctl.h sys/signalfd.h sys/ucred.h termios.h ucred.h xlocale.h
+for ac_header in atomic.h copyfile.h execinfo.h getopt.h ifaddrs.h linux/futex.h mbarrier.h sys/epoll.h sys/event.h sys/futex.h sys/personality.h sys/prctl.h sys/procctl.h sys/signalfd.h sys/ucred.h sys/umtx.h termios.h ucred.h xlocale.h
 do :
   as_ac_Header=`$as_echo "ac_cv_header_$ac_header" | $as_tr_sh`
 ac_fn_c_check_header_mongrel "$LINENO" "$ac_header" "$as_ac_Header" "$ac_includes_default"
@@ -15044,7 +15044,7 @@ fi
 LIBS_including_readline="$LIBS"
 LIBS=`echo "$LIBS" | sed -e 's/-ledit//g' -e 's/-lreadline//g'`
 
-for ac_func in backtrace_symbols copyfile copy_file_range elf_aux_info getauxval getifaddrs getpeerucred inet_pton kqueue mbstowcs_l memset_s posix_fallocate ppoll pthread_is_threaded_np setproctitle setproctitle_fast strchrnul strsignal syncfs sync_file_range uselocale wcstombs_l
+for ac_func in __ulock_wait backtrace_symbols copyfile copy_file_range elf_aux_info getauxval getifaddrs getpeerucred inet_pton kqueue mbstowcs_l memset_s posix_fallocate ppoll pthread_is_threaded_np setproctitle setproctitle_fast strchrnul strsignal syncfs sync_file_range umtx_sleep uselocale wcstombs_l
 do :
   as_ac_var=`$as_echo "ac_cv_func_$ac_func" | $as_tr_sh`
 ac_fn_c_check_func "$LINENO" "$ac_func" "$as_ac_var"
diff --git a/configure.ac b/configure.ac
index 247ae97fa4c..6b4f3e0f2e5 100644
--- a/configure.ac
+++ b/configure.ac
@@ -1438,14 +1438,17 @@ AC_CHECK_HEADERS(m4_normalize([
 	execinfo.h
 	getopt.h
 	ifaddrs.h
+	linux/futex.h
 	mbarrier.h
 	sys/epoll.h
 	sys/event.h
+	sys/futex.h
 	sys/personality.h
 	sys/prctl.h
 	sys/procctl.h
 	sys/signalfd.h
 	sys/ucred.h
+	sys/umtx.h
 	termios.h
 	ucred.h
 	xlocale.h
@@ -1707,6 +1710,7 @@ LIBS_including_readline="$LIBS"
 LIBS=`echo "$LIBS" | sed -e 's/-ledit//g' -e 's/-lreadline//g'`
 
 AC_CHECK_FUNCS(m4_normalize([
+	__ulock_wait
 	backtrace_symbols
 	copyfile
 	copy_file_range
@@ -1727,6 +1731,7 @@ AC_CHECK_FUNCS(m4_normalize([
 	strsignal
 	syncfs
 	sync_file_range
+	umtx_sleep
 	uselocale
 	wcstombs_l
 ]))
diff --git a/meson.build b/meson.build
index e5ce437a5c7..5c9775f1a6e 100644
--- a/meson.build
+++ b/meson.build
@@ -2380,15 +2380,18 @@ header_checks = [
   'execinfo.h',
   'getopt.h',
   'ifaddrs.h',
+  'linux/futex.h',
   'mbarrier.h',
   'strings.h',
   'sys/epoll.h',
   'sys/event.h',
+  'sys/futex.h',
   'sys/personality.h',
   'sys/prctl.h',
   'sys/procctl.h',
   'sys/signalfd.h',
   'sys/ucred.h',
+  'sys/umtx.h',
   'termios.h',
   'ucred.h',
   'xlocale.h',
@@ -2611,6 +2614,7 @@ endif
 # XXX: Might be worth conditioning some checks on the OS, to avoid doing
 # unnecessary checks over and over, particularly on windows.
 func_checks = [
+  ['__ulock_wait'],
   ['backtrace_symbols', {'dependencies': [execinfo_dep]}],
   ['clock_gettime', {'dependencies': [rt_dep], 'define': false}],
   ['copyfile'],
@@ -2654,6 +2658,7 @@ func_checks = [
   ['strsignal'],
   ['sync_file_range'],
   ['syncfs'],
+  ['umtx_sleep'],
   ['uselocale'],
   ['wcstombs_l'],
 ]
diff --git a/src/backend/port/meson.build b/src/backend/port/meson.build
index 7820e86016d..e34499bafb3 100644
--- a/src/backend/port/meson.build
+++ b/src/backend/port/meson.build
@@ -5,7 +5,7 @@ backend_sources += files(
 )
 
 
-if cdata.has('USE_UNNAMED_POSIX_SEMAPHORES') or cdata.has('USE_NAMED_POSIX_SEMAPHORES')
+if cdata.has('USE_UNNAMED_POSIX_SEMAPHORES') or cdata.has('USE_NAMED_POSIX_SEMAPHORES') or cdata.has('USE_FUTEX_SEMAPHORES')
   backend_sources += files('posix_sema.c')
 endif
 
diff --git a/src/include/pg_config.h.in b/src/include/pg_config.h.in
index 07b2f798abd..19cbf6e74ee 100644
--- a/src/include/pg_config.h.in
+++ b/src/include/pg_config.h.in
@@ -265,6 +265,9 @@
 /* Define to 1 if you have the `zstd' library (-lzstd). */
 #undef HAVE_LIBZSTD
 
+/* Define to 1 if you have the <linux/futex.h> header file. */
+#undef HAVE_LINUX_FUTEX_H
+
 /* Define to 1 if you have the <mbarrier.h> header file. */
 #undef HAVE_MBARRIER_H
 
@@ -418,6 +421,9 @@
 /* Define to 1 if you have the <sys/event.h> header file. */
 #undef HAVE_SYS_EVENT_H
 
+/* Define to 1 if you have the <sys/futex.h> header file. */
+#undef HAVE_SYS_FUTEX_H
+
 /* Define to 1 if you have the <sys/personality.h> header file. */
 #undef HAVE_SYS_PERSONALITY_H
 
@@ -439,6 +445,9 @@
 /* Define to 1 if you have the <sys/ucred.h> header file. */
 #undef HAVE_SYS_UCRED_H
 
+/* Define to 1 if you have the <sys/umtx.h> header file. */
+#undef HAVE_SYS_UMTX_H
+
 /* Define to 1 if you have the <termios.h> header file. */
 #undef HAVE_TERMIOS_H
 
@@ -448,6 +457,9 @@
 /* Define to 1 if you have the <ucred.h> header file. */
 #undef HAVE_UCRED_H
 
+/* Define to 1 if you have the `umtx_sleep' function. */
+#undef HAVE_UMTX_SLEEP
+
 /* Define to 1 if the system has the type `union semun'. */
 #undef HAVE_UNION_SEMUN
 
@@ -538,6 +550,9 @@
 /* Define to 1 if your compiler understands _Static_assert. */
 #undef HAVE__STATIC_ASSERT
 
+/* Define to 1 if you have the `__ulock_wait' function. */
+#undef HAVE___ULOCK_WAIT
+
 /* Define as the maximum alignment requirement of any C data type. */
 #undef MAXIMUM_ALIGNOF
 
diff --git a/src/include/port/pg_futex.h b/src/include/port/pg_futex.h
new file mode 100644
index 00000000000..e5ae05d1d5a
--- /dev/null
+++ b/src/include/port/pg_futex.h
@@ -0,0 +1,171 @@
+/*
+ * Minimal wrapper over futex APIs.
+ */
+
+#ifndef PG_FUTEX_H
+#define PG_FUTEX_H
+
+#if defined(HAVE_LINUX_FUTEX_H)
+
+/* https://man7.org/linux/man-pages/man2/futex.2.html */
+
+#include <linux/futex.h>
+#include <sys/syscall.h>
+
+#elif defined(HAVE_SYS_FUTEX_H)
+
+/* https://man.openbsd.org/futex, since OpenBSD 6.2. */
+
+#include <sys/time.h>
+#include <sys/futex.h>
+
+#elif defined(HAVE_SYS_UMTX_H)
+
+/* https://www.freebsd.org/cgi/man.cgi?query=_umtx_op */
+
+#include <sys/types.h>
+#include <sys/umtx.h>
+
+#elif defined(HAVE_UMTX_SLEEP)
+
+/* https://man.dragonflybsd.org/?command=umtx&section=2 */
+
+#include <unistd.h>
+
+#elif defined(HAVE___ULOCK_WAIT)
+
+/*
+ * This interface is undocumented, but provided by libSystem.dylib since
+ * xnu-3789.1.32 (macOS 10.12, 2016) and is used by eg libc++.
+ *
+ * https://github.com/apple/darwin-xnu/blob/main/bsd/kern/sys_ulock.c
+ * https://github.com/apple/darwin-xnu/blob/main/bsd/sys/ulock.h
+ */
+
+#include <stdint.h>
+
+#define UL_COMPARE_AND_WAIT_SHARED		3
+#define ULF_WAKE_ALL					0x00000100
+
+#ifdef __cplusplus
+extern "C"
+{
+#endif
+
+extern int	__ulock_wait(uint32_t operation,
+						 void *addr,
+						 uint64_t value,
+						 uint32_t timeout);
+extern int	__ulock_wake(uint32_t operation,
+						 void *addr,
+						 uint64_t wake_value);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
+
+#ifdef __cplusplus
+extern "C"
+{
+#endif
+
+/*
+ * Wait for someone to call pg_futex_wake() for the same address, with an
+ * initial check that the value pointed to by 'fut' matches 'value' and an
+ * optional timeout.  Returns 0 when woken, and otherwise -1, with errno set to
+ * EAGAIN if the initial value check fails, and otherwise errors including
+ * EINTR, ETIMEDOUT and EFAULT.
+ */
+static int
+pg_futex_wait_u32(volatile void *fut,
+				  uint32 value,
+				  struct timespec *timeout)
+{
+#if defined(HAVE_LINUX_FUTEX_H)
+	if (syscall(SYS_futex, fut, FUTEX_WAIT, value, timeout, 0, 0) == 0)
+		return 0;
+#elif defined(HAVE_SYS_FUTEX_H)
+	if ((errno = futex((void *) fut, FUTEX_WAIT, (int) value, timeout, NULL)) == 0)
+		return 0;
+	if (errno == ECANCELED)
+		errno = EINTR;
+#elif defined(HAVE_SYS_UMTX_H)
+	if (_umtx_op((void *) fut, UMTX_OP_WAIT_UINT, value, 0, timeout) == 0)
+		return 0;
+#elif defined(HAVE_UMTX_SLEEP)
+	if (umtx_sleep((volatile const int *) fut,
+				   (int) value,
+				   timeout ? timeout->tv_sec * 1000000 + timeout->tv_nsec / 1000 : 0) == 0)
+		return 0;
+	if (errno == EBUSY)
+		errno = EAGAIN;
+#elif defined (HAVE___ULOCK_WAIT)
+	if (__ulock_wait(UL_COMPARE_AND_WAIT_SHARED,
+					 (void *) fut,
+					 value,
+					 timeout ? timeout->tv_sec * 1000000 + timeout->tv_nsec / 1000 : 0) >= 0)
+		return 0;
+#else
+	/*
+	 * If we wanted to simulate futexes on systems that don't have them, here
+	 * we could add a link from our PGPROC struct to a shared memory hash
+	 * table using "fut" (ie address) as the key, then compare *fut == value.
+	 * If false, remove link and fail with EAGAIN.  If true, sleep on proc
+	 * latch.  This wouldn't work for DSM segments; for those, we could search
+	 * for matching DSM segment mappings in this process, and convert the key
+	 * to { segment ID, offset }, just like kernels do internally to make
+	 * inter-process futexes work on shared memory, but... ugh.
+	 */
+	errno = ENOSYS;
+#endif
+
+	Assert(errno != 0);
+
+	return -1;
+}
+
+/*
+ * Wake up to nwaiters waiters that currently wait on the same address as
+ * 'fut'.  Returns 0 on success, and -1 on failure, with errno set.  Though
+ * some of these interfaces can tell us how many were woken, they can't all do
+ * that, so we'll hide that information.
+ */
+static int
+pg_futex_wake(volatile void *fut, int nwaiters)
+{
+#if defined(HAVE_LINUX_FUTEX_H)
+	if (syscall(SYS_futex, fut, FUTEX_WAKE, nwaiters, NULL, 0, 0) >= 0)
+		return 0;
+#elif defined(HAVE_SYS_FUTEX_H)
+	if (futex(fut, FUTEX_WAKE, nwaiters, NULL, NULL) >= 0)
+		return 0;
+#elif defined(HAVE_SYS_UMTX_H)
+	if (_umtx_op((void *) fut, UMTX_OP_WAKE, nwaiters, 0, 0) == 0)
+		return 0;
+#elif defined(HAVE_UMTX_SLEEP)
+	if (umtx_wakeup((volatile const int *) fut, nwaiters) == 0)
+		return 0;
+#elif defined (HAVE___ULOCK_WAIT)
+	if (__ulock_wake(UL_COMPARE_AND_WAIT_SHARED | (nwaiters > 1 ? ULF_WAKE_ALL : 0),
+					 (void *) fut,
+					 0) >= 0)
+		return 0;
+	if (errno == ENOENT)
+		return 0;
+#else
+	/* No implementation available. */
+	errno = ENOSYS;
+#endif
+
+	Assert(errno != 0);
+
+	return -1;
+}
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif							/* PG_FUTEX_H */
-- 
2.47.1

