From 4d001e962e4f54d5128ac55bf03fdef77e41aa58 Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Sun, 22 Aug 2010 08:34:03 -0400 Subject: [PATCH] LGPL-ize wfqueue Provide the appropriate wrappers to ensure that non-LGPL applications can use the half-blocking wait-free queue. Signed-off-by: Mathieu Desnoyers --- Makefile.am | 5 +- tests/Makefile.am | 7 +- urcu/wfqueue-static.h | 149 ++++++++++++++++++++++++++++++++++++++++++ urcu/wfqueue.h | 108 ++++-------------------------- wfqueue.c | 49 ++++++++++++++ 5 files changed, 220 insertions(+), 98 deletions(-) create mode 100644 urcu/wfqueue-static.h create mode 100644 wfqueue.c diff --git a/Makefile.am b/Makefile.am index 88214ab..e56803f 100644 --- a/Makefile.am +++ b/Makefile.am @@ -25,7 +25,8 @@ if COMPAT_FUTEX COMPAT+=compat_futex.c endif -lib_LTLIBRARIES = liburcu.la liburcu-qsbr.la liburcu-mb.la liburcu-signal.la liburcu-bp.la liburcu-defer.la +lib_LTLIBRARIES = liburcu.la liburcu-qsbr.la liburcu-mb.la liburcu-signal.la \ + liburcu-bp.la liburcu-defer.la libwfqueue.la liburcu_la_SOURCES = urcu.c urcu-pointer.c $(COMPAT) @@ -40,3 +41,5 @@ liburcu_signal_la_CFLAGS = -DRCU_SIGNAL liburcu_bp_la_SOURCES = urcu-bp.c urcu-pointer.c $(COMPAT) liburcu_defer_la_SOURCES = urcu-defer.c $(COMPAT) + +libwfqueue_la_SOURCES = wfqueue.c $(COMPAT) diff --git a/tests/Makefile.am b/tests/Makefile.am index b7b9ebe..282b8f9 100644 --- a/tests/Makefile.am +++ b/tests/Makefile.am @@ -13,7 +13,8 @@ noinst_PROGRAMS = test_urcu test_urcu_dynamic_link test_urcu_timing \ test_urcu_mb_lgc test_qsbr_dynamic_link test_urcu_defer \ test_uatomic test_urcu_assign test_urcu_assign_dynamic_link \ test_urcu_bp test_urcu_bp_dynamic_link test_cycles_per_loop \ - test_urcu_lfq test_urcu_wfq test_urcu_lfs test_urcu_wfs + test_urcu_lfq test_urcu_wfq test_urcu_lfs test_urcu_wfs \ + test_urcu_wfq_dynlink noinst_HEADERS = rcutorture.h if COMPAT_ARCH @@ -40,6 +41,7 @@ URCU_QSBR_LIB=$(top_builddir)/liburcu-qsbr.la URCU_MB_LIB=$(top_builddir)/liburcu-mb.la URCU_SIGNAL_LIB=$(top_builddir)/liburcu-signal.la URCU_BP_LIB=$(top_builddir)/liburcu-bp.la +WFQUEUE_LIB=$(top_builddir)/libwfqueue.la EXTRA_DIST = $(top_srcdir)/tests/api_*.h @@ -154,6 +156,9 @@ test_urcu_bp_dynamic_link_CFLAGS = -DDYNAMIC_LINK_TEST $(AM_CFLAGS) test_urcu_lfq_SOURCES = test_urcu_lfq.c $(URCU_DEFER) test_urcu_wfq_SOURCES = test_urcu_wfq.c +test_urcu_wfq_dynlink_SOURCES = test_urcu_wfq.c +test_urcu_wfq_dynlink_CFLAGS = -DDYNAMIC_LINK_TEST $(AM_CFLAGS) +test_urcu_wfq_dynlink_LDADD = $(WFQUEUE_LIB) test_urcu_lfs_SOURCES = test_urcu_lfs.c $(URCU_DEFER) test_urcu_wfs_SOURCES = test_urcu_wfs.c $(URCU_DEFER) diff --git a/urcu/wfqueue-static.h b/urcu/wfqueue-static.h new file mode 100644 index 0000000..8a4a7fd --- /dev/null +++ b/urcu/wfqueue-static.h @@ -0,0 +1,149 @@ +#ifndef _URCU_WFQUEUE_STATIC_H +#define _URCU_WFQUEUE_STATIC_H + +/* + * wfqueue-static.h + * + * Userspace RCU library - Queue with Wait-Free Enqueue/Blocking Dequeue + * + * TO BE INCLUDED ONLY IN LGPL-COMPATIBLE CODE. See wfqueue.h for linking + * dynamically with the userspace rcu library. + * + * 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 +#include + +#ifdef __cplusplus +extern "C" { +#endif + +/* + * Queue with wait-free enqueue/blocking dequeue. + * This implementation adds a dummy head node when the queue is empty to ensure + * we can always update the queue locklessly. + * + * Inspired from half-wait-free/half-blocking queue implementation done by + * Paul E. McKenney. + */ + +#define WFQ_ADAPT_ATTEMPTS 10 /* Retry if being set */ +#define WFQ_WAIT 10 /* Wait 10 ms if being set */ + +void _wfq_node_init(struct wfq_node *node) +{ + node->next = NULL; +} + +void _wfq_init(struct wfq_queue *q) +{ + int ret; + + _wfq_node_init(&q->dummy); + /* Set queue head and tail */ + q->head = &q->dummy; + q->tail = &q->dummy.next; + ret = pthread_mutex_init(&q->lock, NULL); + assert(!ret); +} + +void _wfq_enqueue(struct wfq_queue *q, struct wfq_node *node) +{ + struct wfq_node **old_tail; + + /* + * uatomic_xchg() implicit memory barrier orders earlier stores to data + * structure containing node and setting node->next to NULL before + * publication. + */ + old_tail = uatomic_xchg(&q->tail, node); + /* + * At this point, dequeuers see a NULL old_tail->next, which indicates + * that the queue is being appended to. The following store will append + * "node" to the queue from a dequeuer perspective. + */ + STORE_SHARED(*old_tail, node); +} + +/* + * It is valid to reuse and free a dequeued node immediately. + * + * No need to go on a waitqueue here, as there is no possible state in which the + * list could cause dequeue to busy-loop needlessly while waiting for another + * thread to be scheduled. The queue appears empty until tail->next is set by + * enqueue. + */ +struct wfq_node * +__wfq_dequeue_blocking(struct wfq_queue *q) +{ + struct wfq_node *node, *next; + int attempt = 0; + + /* + * Queue is empty if it only contains the dummy node. + */ + if (q->head == &q->dummy && LOAD_SHARED(q->tail) == &q->dummy.next) + return NULL; + node = q->head; + + /* + * Adaptative busy-looping waiting for enqueuer to complete enqueue. + */ + while ((next = LOAD_SHARED(node->next)) == NULL) { + if (++attempt >= WFQ_ADAPT_ATTEMPTS) { + poll(NULL, 0, WFQ_WAIT); /* Wait for 10ms */ + attempt = 0; + } else + cpu_relax(); + } + /* + * Move queue head forward. + */ + q->head = next; + /* + * Requeue dummy node if we just dequeued it. + */ + if (node == &q->dummy) { + _wfq_node_init(node); + _wfq_enqueue(q, node); + return __wfq_dequeue_blocking(q); + } + return node; +} + +struct wfq_node * +_wfq_dequeue_blocking(struct wfq_queue *q) +{ + struct wfq_node *retnode; + int ret; + + ret = pthread_mutex_lock(&q->lock); + assert(!ret); + retnode = __wfq_dequeue_blocking(q); + ret = pthread_mutex_unlock(&q->lock); + assert(!ret); + return retnode; +} + +#ifdef __cplusplus +} +#endif + +#endif /* _URCU_WFQUEUE_STATIC_H */ diff --git a/urcu/wfqueue.h b/urcu/wfqueue.h index 2eaace1..3d32b05 100644 --- a/urcu/wfqueue.h +++ b/urcu/wfqueue.h @@ -31,13 +31,6 @@ extern "C" { #endif -#if (!defined(_GNU_SOURCE) && !defined(_LGPL_SOURCE)) -#error "Dynamic loader LGPL wrappers not implemented yet" -#endif - -#define WFQ_ADAPT_ATTEMPTS 10 /* Retry if being set */ -#define WFQ_WAIT 10 /* Wait 10 ms if being set */ - /* * Queue with wait-free enqueue/blocking dequeue. * This implementation adds a dummy head node when the queue is empty to ensure @@ -57,100 +50,23 @@ struct wfq_queue { pthread_mutex_t lock; }; -void wfq_node_init(struct wfq_node *node) -{ - node->next = NULL; -} +#ifdef _LGPL_SOURCE -void wfq_init(struct wfq_queue *q) -{ - int ret; +#include - wfq_node_init(&q->dummy); - /* Set queue head and tail */ - q->head = &q->dummy; - q->tail = &q->dummy.next; - ret = pthread_mutex_init(&q->lock, NULL); - assert(!ret); -} +#define wfq_node_init _wfq_node_init +#define wfq_init _wfq_init +#define wfq_enqueue _wfq_enqueue +#define wfq_dequeue_blocking _wfq_dequeue_blocking -void wfq_enqueue(struct wfq_queue *q, struct wfq_node *node) -{ - struct wfq_node **old_tail; +#else /* !_LGPL_SOURCE */ - /* - * uatomic_xchg() implicit memory barrier orders earlier stores to data - * structure containing node and setting node->next to NULL before - * publication. - */ - old_tail = uatomic_xchg(&q->tail, node); - /* - * At this point, dequeuers see a NULL old_tail->next, which indicates - * that the queue is being appended to. The following store will append - * "node" to the queue from a dequeuer perspective. - */ - STORE_SHARED(*old_tail, node); -} +extern void wfq_node_init(struct wfq_node *node); +extern void wfq_init(struct wfq_queue *q); +extern void wfq_enqueue(struct wfq_queue *q, struct wfq_node *node); +extern struct wfq_node *wfq_dequeue_blocking(struct wfq_queue *q); -/* - * It is valid to reuse and free a dequeued node immediately. - * - * No need to go on a waitqueue here, as there is no possible state in which the - * list could cause dequeue to busy-loop needlessly while waiting for another - * thread to be scheduled. The queue appears empty until tail->next is set by - * enqueue. - */ -struct wfq_node * -__wfq_dequeue_blocking(struct wfq_queue *q) -{ - struct wfq_node *node, *next; - int attempt = 0; - - /* - * Queue is empty if it only contains the dummy node. - */ - if (q->head == &q->dummy && LOAD_SHARED(q->tail) == &q->dummy.next) - return NULL; - node = q->head; - - /* - * Adaptative busy-looping waiting for enqueuer to complete enqueue. - */ - while ((next = LOAD_SHARED(node->next)) == NULL) { - if (++attempt >= WFQ_ADAPT_ATTEMPTS) { - poll(NULL, 0, WFQ_WAIT); /* Wait for 10ms */ - attempt = 0; - } else - cpu_relax(); - } - /* - * Move queue head forward. - */ - q->head = next; - /* - * Requeue dummy node if we just dequeued it. - */ - if (node == &q->dummy) { - wfq_node_init(node); - wfq_enqueue(q, node); - return __wfq_dequeue_blocking(q); - } - return node; -} - -struct wfq_node * -wfq_dequeue_blocking(struct wfq_queue *q) -{ - struct wfq_node *retnode; - int ret; - - ret = pthread_mutex_lock(&q->lock); - assert(!ret); - retnode = __wfq_dequeue_blocking(q); - ret = pthread_mutex_unlock(&q->lock); - assert(!ret); - return retnode; -} +#endif /* !_LGPL_SOURCE */ #ifdef __cplusplus } diff --git a/wfqueue.c b/wfqueue.c new file mode 100644 index 0000000..d22aa7c --- /dev/null +++ b/wfqueue.c @@ -0,0 +1,49 @@ +/* + * wfqueue.c + * + * Userspace RCU library - Queue with Wait-Free Enqueue/Blocking Dequeue + * + * 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 + */ + +/* Do not #define _LGPL_SOURCE to ensure we can emit the wrapper symbols */ +#include "urcu/wfqueue.h" +#include "urcu/wfqueue-static.h" + +/* + * library wrappers to be used by non-LGPL compatible source code. + */ + +void wfq_node_init(struct wfq_node *node) +{ + _wfq_node_init(node); +} + +void wfq_init(struct wfq_queue *q) +{ + _wfq_init(q); +} + +void wfq_enqueue(struct wfq_queue *q, struct wfq_node *node) +{ + _wfq_enqueue(q, node); +} + +struct wfq_node *wfq_dequeue_blocking(struct wfq_queue *q) +{ + return _wfq_dequeue_blocking(q); +} -- 2.34.1