From cb3f3d6bce4faeb41e4109e12fa722f73a6f6c13 Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Wed, 18 Aug 2010 10:55:14 -0400 Subject: [PATCH] Wait-free stack: rcu-less implementation Don't have to hold a rcu read lock anymore. pop side is blocking and holds a mutex. Signed-off-by: Mathieu Desnoyers --- Makefile.am | 3 +- tests/test_urcu_wfs.c | 33 ++++------- urcu/rcuwfstack.h | 133 ------------------------------------------ urcu/wfstack.h | 129 ++++++++++++++++++++++++++++++++++++++++ 4 files changed, 142 insertions(+), 156 deletions(-) delete mode 100644 urcu/rcuwfstack.h create mode 100644 urcu/wfstack.h diff --git a/Makefile.am b/Makefile.am index 8875538..88214ab 100644 --- a/Makefile.am +++ b/Makefile.am @@ -7,7 +7,8 @@ SUBDIRS = . tests include_HEADERS = urcu.h $(top_srcdir)/urcu-*.h nobase_dist_include_HEADERS = urcu/compiler.h urcu/hlist.h urcu/list.h \ urcu/rculist.h urcu/rcuhlist.h urcu/system.h urcu/urcu-futex.h \ - urcu/uatomic_generic.h urcu/arch_generic.h + urcu/uatomic_generic.h urcu/arch_generic.h urcu/wfstack.h \ + urcu/wfqueue.h urcu/rculfstack.h urcu/rculfqueue.h nobase_nodist_include_HEADERS = urcu/arch.h urcu/uatomic_arch.h urcu/config.h EXTRA_DIST = $(top_srcdir)/urcu/arch_*.h $(top_srcdir)/urcu/uatomic_arch_*.h \ diff --git a/tests/test_urcu_wfs.c b/tests/test_urcu_wfs.c index 73655c1..f50b140 100644 --- a/tests/test_urcu_wfs.c +++ b/tests/test_urcu_wfs.c @@ -62,8 +62,7 @@ static inline pid_t gettid(void) #define _LGPL_SOURCE #endif #include -#include -#include +#include static volatile int test_go, test_stop; @@ -154,7 +153,7 @@ static unsigned long long __thread nr_successful_enqueues; static unsigned int nr_enqueuers; static unsigned int nr_dequeuers; -static struct rcu_wfs_stack s; +static struct wfs_stack s; void *thr_enqueuer(void *_count) { @@ -165,19 +164,17 @@ void *thr_enqueuer(void *_count) set_affinity(); - rcu_register_thread(); - while (!test_go) { } smp_mb(); for (;;) { - struct rcu_wfs_node *node = malloc(sizeof(*node)); + struct wfs_node *node = malloc(sizeof(*node)); if (!node) goto fail; - rcu_wfs_node_init(node); - rcu_wfs_push(&s, node); + wfs_node_init(node); + wfs_push(&s, node); nr_successful_enqueues++; if (unlikely(wdelay)) @@ -188,8 +185,6 @@ fail: break; } - rcu_unregister_thread(); - count[0] = nr_enqueues; count[1] = nr_successful_enqueues; printf_verbose("enqueuer thread_end, thread id : %lx, tid %lu, " @@ -209,19 +204,16 @@ void *thr_dequeuer(void *_count) set_affinity(); - rcu_defer_register_thread(); - rcu_register_thread(); - while (!test_go) { } smp_mb(); for (;;) { - struct rcu_wfs_node *node = rcu_wfs_pop_blocking(&s); + struct wfs_node *node = wfs_pop_blocking(&s); if (node) { - defer_rcu(free, node); + free(node); nr_successful_dequeues++; } @@ -232,9 +224,6 @@ void *thr_dequeuer(void *_count) loop_sleep(rduration); } - rcu_unregister_thread(); - rcu_defer_unregister_thread(); - printf_verbose("dequeuer thread_end, thread id : %lx, tid %lu, " "dequeues %llu, successful_dequeues %llu\n", pthread_self(), (unsigned long)gettid(), nr_dequeues, @@ -244,12 +233,12 @@ void *thr_dequeuer(void *_count) return ((void*)2); } -void test_end(struct rcu_wfs_stack *s, unsigned long long *nr_dequeues) +void test_end(struct wfs_stack *s, unsigned long long *nr_dequeues) { - struct rcu_wfs_node *node; + struct wfs_node *node; do { - node = rcu_wfs_pop_blocking(s); + node = wfs_pop_blocking(s); if (node) { free(node); (*nr_dequeues)++; @@ -348,7 +337,7 @@ int main(int argc, char **argv) tid_dequeuer = malloc(sizeof(*tid_dequeuer) * nr_dequeuers); count_enqueuer = malloc(2 * sizeof(*count_enqueuer) * nr_enqueuers); count_dequeuer = malloc(2 * sizeof(*count_dequeuer) * nr_dequeuers); - rcu_wfs_init(&s); + wfs_init(&s); next_aff = 0; diff --git a/urcu/rcuwfstack.h b/urcu/rcuwfstack.h deleted file mode 100644 index 71ecce8..0000000 --- a/urcu/rcuwfstack.h +++ /dev/null @@ -1,133 +0,0 @@ -#ifndef _URCU_RCUWFSTACK_H -#define _URCU_RCUWFSTACK_H - -/* - * rcuwfstack.h - * - * Userspace RCU library - RCU Stack with Wait-Free push, Blocking pop. - * - * Copyright 2010 - Mathieu Desnoyers - * - * This library is free software; you can redistribute it and/or - * modify it under the terms of the GNU Lesser General Public - * License as published by the Free Software Foundation; either - * version 2.1 of the License, or (at your option) any later version. - * - * This library is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - * Lesser General Public License for more details. - * - * You should have received a copy of the GNU Lesser General Public - * License along with this library; if not, write to the Free Software - * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA - */ - -#include - -#ifdef __cplusplus -extern "C" { -#endif - -#if (!defined(_GNU_SOURCE) && !defined(_LGPL_SOURCE)) -#error "Dynamic loader LGPL wrappers not implemented yet" -#endif - -#define RCU_WF_STACK_END ((void *)0x1UL) -#define RCU_WFS_ADAPT_ATTEMPTS 10 /* Retry if being set */ -#define RCU_WFS_WAIT 10 /* Wait 10 ms if being set */ - -extern int rcu_wfs_futex; - -struct rcu_wfs_node { - struct rcu_wfs_node *next; -}; - -struct rcu_wfs_stack { - struct rcu_wfs_node *head; -}; - -void rcu_wfs_node_init(struct rcu_wfs_node *node) -{ - node->next = NULL; -} - -void rcu_wfs_init(struct rcu_wfs_stack *s) -{ - s->head = RCU_WF_STACK_END; -} - -void rcu_wfs_push(struct rcu_wfs_stack *s, struct rcu_wfs_node *node) -{ - struct rcu_wfs_node *old_head; - - assert(node->next == NULL); - /* - * uatomic_xchg() implicit memory barrier orders earlier stores to node - * (setting it to NULL) before publication. - */ - old_head = uatomic_xchg(&s->head, node); - /* - * At this point, dequeuers see a NULL node->next, they should busy-wait - * until node->next is set to old_head. - */ - STORE_SHARED(node->next, old_head); -} - -/* - * The caller must wait for a grace period before: - * - freeing the returned node. - * - modifying the ->next pointer of the returned node. (be careful with unions) - * - passing the returned node back to push() on the same stack they got it - * from. - * - * Returns NULL if stack is empty. - * - * cmpxchg is protected from ABA races by holding a RCU read lock between - * s->head read and cmpxchg modifying s->head and requiring that dequeuers wait - * for a grace period before freeing the returned node. - */ -struct rcu_wfs_node * -rcu_wfs_pop_blocking(struct rcu_wfs_stack *s) -{ - int attempt = 0; - - for (;;) { - struct rcu_wfs_node *head; - - rcu_read_lock(); - head = rcu_dereference(s->head); - if (head != RCU_WF_STACK_END) { - struct rcu_wfs_node *next = rcu_dereference(head->next); - - /* Retry while head is being set by push(). */ - if (!next) { - rcu_read_unlock(); - if (++attempt >= RCU_WFS_ADAPT_ATTEMPTS) { - /* Sleep for 10ms */ - poll(NULL, 0, RCU_WFS_WAIT); - attempt = 0; - } - continue; - } - if (uatomic_cmpxchg(&s->head, head, next) == head) { - rcu_read_unlock(); - return head; - } else { - /* Concurrent modification. Retry. */ - rcu_read_unlock(); - continue; - } - } else { - /* Empty stack */ - rcu_read_unlock(); - return NULL; - } - } -} - -#ifdef __cplusplus -} -#endif - -#endif /* _URCU_RCUWFSTACK_H */ diff --git a/urcu/wfstack.h b/urcu/wfstack.h new file mode 100644 index 0000000..b3ee2e7 --- /dev/null +++ b/urcu/wfstack.h @@ -0,0 +1,129 @@ +#ifndef _URCU_WFSTACK_H +#define _URCU_WFSTACK_H + +/* + * rcuwfstack.h + * + * Userspace RCU library - Stack with Wait-Free push, Blocking pop. + * + * Copyright 2010 - Mathieu Desnoyers + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#include +#include +#include + +#ifdef __cplusplus +extern "C" { +#endif + +#if (!defined(_GNU_SOURCE) && !defined(_LGPL_SOURCE)) +#error "Dynamic loader LGPL wrappers not implemented yet" +#endif + +#define WF_STACK_END ((void *)0x1UL) +#define WFS_ADAPT_ATTEMPTS 10 /* Retry if being set */ +#define WFS_WAIT 10 /* Wait 10 ms if being set */ + +struct wfs_node { + struct wfs_node *next; +}; + +struct wfs_stack { + struct wfs_node *head; + pthread_mutex_t lock; +}; + +void wfs_node_init(struct wfs_node *node) +{ + node->next = NULL; +} + +void wfs_init(struct wfs_stack *s) +{ + int ret; + + s->head = WF_STACK_END; + ret = pthread_mutex_init(&s->lock, NULL); + assert(!ret); +} + +void wfs_push(struct wfs_stack *s, struct wfs_node *node) +{ + struct wfs_node *old_head; + + assert(node->next == NULL); + /* + * uatomic_xchg() implicit memory barrier orders earlier stores to node + * (setting it to NULL) before publication. + */ + old_head = uatomic_xchg(&s->head, node); + /* + * At this point, dequeuers see a NULL node->next, they should busy-wait + * until node->next is set to old_head. + */ + STORE_SHARED(node->next, old_head); +} + +/* + * Returns NULL if stack is empty. + */ +struct wfs_node * +__wfs_pop_blocking(struct wfs_stack *s) +{ + struct wfs_node *head, *next; + int attempt = 0; + +retry: + head = LOAD_SHARED(s->head); + if (head == WF_STACK_END) + return NULL; + /* + * Adaptative busy-looping waiting for push to complete. + */ + while ((next = LOAD_SHARED(head->next)) == NULL) { + if (++attempt >= WFS_ADAPT_ATTEMPTS) { + poll(NULL, 0, WFS_WAIT); /* Wait for 10ms */ + attempt = 0; + } else + cpu_relax(); + } + if (uatomic_cmpxchg(&s->head, head, next) == head) + return head; + else + goto retry; /* Concurrent modification. Retry. */ +} + +struct wfs_node * +wfs_pop_blocking(struct wfs_stack *s) +{ + struct wfs_node *retnode; + int ret; + + ret = pthread_mutex_lock(&s->lock); + assert(!ret); + retnode = __wfs_pop_blocking(s); + ret = pthread_mutex_unlock(&s->lock); + assert(!ret); + return retnode; +} + +#ifdef __cplusplus +} +#endif + +#endif /* _URCU_WFSTACK_H */ -- 2.34.1