From: Eric Wong <e@80x24.org>
To: mm@80x24.org
Subject: [REJECT femalloc] xtlifo: reduce spinnning with futex
Date: Mon, 4 Aug 2014 21:26:44 +0000 [thread overview]
Message-ID: <20140804212644.GA23906@dcvr.yhbt.net> (raw)
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
reply other threads:[~2014-08-04 21:26 UTC|newest]
Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20140804212644.GA23906@dcvr.yhbt.net \
--to=e@80x24.org \
--cc=mm@80x24.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox