[REJECT femalloc] xtlifo: reduce spinnning with futex

[REJECT femalloc] xtlifo: reduce spinnning with futex

[Eric Wong]

I'm probably going to drop the LIFO stack of arenas entirely and use
thread-local arenas, but for the sake of documentation, I attempted to
use a futex to reduce spinning on arena contention.

diff --git a/xtlifo.h b/xtlifo.h
index 4d6d219..ccb8dc2 100644
--- a/xtlifo.h
+++ b/xtlifo.h
@@ -11,9 +11,27 @@
  * (n.b. ck is 2-clause BSD)
  */
 
+#include <assert.h>
+#include <unistd.h>
+#include <errno.h>
 #include <ck_stack.h>
 #include <ck_spinlock.h>
 #include <urcu/uatomic.h>
+#include <urcu/compiler.h>
+#include <linux/futex.h>
+#include <sys/syscall.h>
+
+static inline int futex_wait(int *addr, int val) {
+  int rc = syscall(SYS_futex, addr, FUTEX_WAIT_PRIVATE, val, 0, 0, 0);
+  if (caa_unlikely(rc != 0))
+    assert(errno == EINTR);
+  return rc;
+}
+
+static inline void futex_wake(int *addr) {
+  int rc = syscall(SYS_futex, addr, FUTEX_WAKE_PRIVATE, 1, 0, 0, 0);
+  assert(rc >= 0);
+}
 
 /* push, pop */
 struct xtlifo {
@@ -23,7 +41,12 @@ struct xtlifo {
       struct ck_stack_entry *head;
       ck_spinlock_t lock;
     };
+    struct {
+      int padding; /* FIXME: this is broken on 32-bit */
+      int ftx;
+    } f;
   };
+  int contended;
 };
 
 #ifdef CK_F_STACK_POP_MPMC
@@ -40,10 +63,12 @@ static inline void xtlifo_init(struct xtlifo *lifo) {
     lifo->head = 0;
     ck_spinlock_init(&lifo->lock);
   }
+  lifo->contended = 0;
 }
 
 static inline struct ck_stack_entry *xtlifo_trypop(struct xtlifo *lifo) {
   struct ck_stack_entry *e;
+
   if (LFLIFO) {
     if (ck_stack_trypop_mpmc(&lifo->stack, &e))
       return e;
@@ -59,6 +84,33 @@ static inline struct ck_stack_entry *xtlifo_trypop(struct xtlifo *lifo) {
   }
 }
 
+/*
+ * n.b. due to the ABA problem, we may get spurious wakeups.
+ * This is probably unavoidable.  Of course, too many wakeups is
+ * preferable to missing wakeups and deadlocking.
+ */
+static void xtlifo_wait_for_push(struct xtlifo *lifo) {
+  /* this reaches into the ck_stack generation counter */
+  int val = uatomic_read(&lifo->f.ftx);
+
+  /* check the pointer did not just get set */
+  if (val)
+    return;
+
+  /* declare we are busy so the pusher can wake us up */
+  cmm_smp_mb__before_uatomic_inc();
+  uatomic_inc(&lifo->contended);
+  cmm_smp_mb__after_uatomic_inc();
+
+  /* wait for the stack head to change */
+  futex_wait(&lifo->f.ftx, val);
+
+  /* prevent unnecessary syscalls from the pusher */
+  cmm_smp_mb__before_uatomic_dec();
+  uatomic_dec(&lifo->contended);
+  cmm_smp_mb__after_uatomic_dec();
+}
+
 static inline struct ck_stack_entry *xtlifo_pop(struct xtlifo *lifo) {
   struct ck_stack_entry *e;
 
@@ -67,7 +119,7 @@ static inline struct ck_stack_entry *xtlifo_pop(struct xtlifo *lifo) {
       e = ck_stack_pop_mpmc(&lifo->stack);
       if (e)
         return e;
-      caa_cpu_relax();
+      xtlifo_wait_for_push(lifo);
     }
   }
   else {
@@ -82,8 +134,16 @@ static inline struct ck_stack_entry *xtlifo_pop(struct xtlifo *lifo) {
 }
 
 static inline void xtlifo_push(struct xtlifo *lifo, struct ck_stack_entry *e) {
-  if (LFLIFO)
+  if (LFLIFO) {
     ck_stack_push_mpmc(&lifo->stack, e);
+
+    /*
+     * Try to only make a syscall if we have waiters.
+     * Syscall avoidance is best-effort.
+     */
+    if (uatomic_read(&lifo->contended));
+      futex_wake(&lifo->f.ftx);
+  }
   else {
     ck_spinlock_lock(&lifo->lock);
     ck_stack_push_spnc(&lifo->stack, e);
-- 
EW