From 3d02c34dba0edc4a3554a3862a2ae96d77b3b4e8 Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Sun, 22 Aug 2010 09:21:58 -0400 Subject: [PATCH] rculfqueue: LGPL-ize Signed-off-by: Mathieu Desnoyers --- Makefile.am | 8 ++- rculfqueue.c | 52 ++++++++++++++ tests/Makefile.am | 10 ++- urcu/rculfqueue-static.h | 145 +++++++++++++++++++++++++++++++++++++++ urcu/rculfqueue.h | 93 ++++--------------------- 5 files changed, 225 insertions(+), 83 deletions(-) create mode 100644 rculfqueue.c create mode 100644 urcu/rculfqueue-static.h diff --git a/Makefile.am b/Makefile.am index 44ab874..2e6612d 100644 --- a/Makefile.am +++ b/Makefile.am @@ -8,7 +8,9 @@ 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/wfstack.h \ - urcu/wfqueue.h urcu/rculfstack.h urcu/rculfqueue.h + urcu/wfqueue.h urcu/rculfstack.h urcu/rculfqueue.h \ + urcu/wfqueue-static.h urcu/wfstack-static.h \ + urcu/rculfqueue-static.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 \ @@ -26,7 +28,8 @@ COMPAT+=compat_futex.c endif lib_LTLIBRARIES = liburcu.la liburcu-qsbr.la liburcu-mb.la liburcu-signal.la \ - liburcu-bp.la liburcu-defer.la libwfqueue.la libwfstack.la + liburcu-bp.la liburcu-defer.la libwfqueue.la libwfstack.la \ + librculfqueue.la liburcu_la_SOURCES = urcu.c urcu-pointer.c $(COMPAT) @@ -44,3 +47,4 @@ liburcu_defer_la_SOURCES = urcu-defer.c $(COMPAT) libwfqueue_la_SOURCES = wfqueue.c $(COMPAT) libwfstack_la_SOURCES = wfstack.c $(COMPAT) +librculfqueue_la_SOURCES = rculfqueue.c $(COMPAT) diff --git a/rculfqueue.c b/rculfqueue.c new file mode 100644 index 0000000..85c7b88 --- /dev/null +++ b/rculfqueue.c @@ -0,0 +1,52 @@ +/* + * rculfqueue.c + * + * Userspace RCU library - Lock-Free RCU Queue + * + * 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 + */ + +/* Use the urcu symbols to select the appropriate rcu flavor at link time */ +#include "urcu.h" +/* Do not #define _LGPL_SOURCE to ensure we can emit the wrapper symbols */ +#include "urcu/rculfqueue.h" +#include "urcu/rculfqueue-static.h" + +/* + * library wrappers to be used by non-LGPL compatible source code. + */ + +void rcu_lfq_node_init(struct rcu_lfq_node *node) +{ + _rcu_lfq_node_init(node); +} + +void rcu_lfq_init(struct rcu_lfq_queue *q) +{ + _rcu_lfq_init(q); +} + +void rcu_lfq_enqueue(struct rcu_lfq_queue *q, struct rcu_lfq_node *node) +{ + _rcu_lfq_enqueue(q, node); +} + +struct rcu_lfq_node * +rcu_lfq_dequeue(struct rcu_lfq_queue *q, void (*release)(struct urcu_ref *)) +{ + return _rcu_lfq_dequeue(q, release); +} diff --git a/tests/Makefile.am b/tests/Makefile.am index 1d9f88f..f85d986 100644 --- a/tests/Makefile.am +++ b/tests/Makefile.am @@ -14,7 +14,8 @@ noinst_PROGRAMS = test_urcu test_urcu_dynamic_link test_urcu_timing \ 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_wfq_dynlink test_urcu_wfs_dynlink + test_urcu_wfq_dynlink test_urcu_wfs_dynlink \ + test_urcu_lfq_dynlink noinst_HEADERS = rcutorture.h if COMPAT_ARCH @@ -43,6 +44,7 @@ URCU_SIGNAL_LIB=$(top_builddir)/liburcu-signal.la URCU_BP_LIB=$(top_builddir)/liburcu-bp.la WFQUEUE_LIB=$(top_builddir)/libwfqueue.la WFSTACK_LIB=$(top_builddir)/libwfstack.la +RCULFQUEUE_LIB=$(top_builddir)/librculfqueue.la EXTRA_DIST = $(top_srcdir)/tests/api_*.h @@ -156,11 +158,17 @@ test_urcu_bp_dynamic_link_SOURCES = test_urcu_bp.c $(URCU_BP) test_urcu_bp_dynamic_link_CFLAGS = -DDYNAMIC_LINK_TEST $(AM_CFLAGS) test_urcu_lfq_SOURCES = test_urcu_lfq.c $(URCU_DEFER) +test_urcu_lfq_dynlink_SOURCES = test_urcu_lfq.c $(URCU_DEFER) +test_urcu_lfq_dynlink_CFLAGS = -DDYNAMIC_LINK_TEST $(AM_CFLAGS) +test_urcu_lfq_dynlink_LDADD = $(RCULFQUEUE_LIB) + 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 test_urcu_wfs_dynlink_SOURCES = test_urcu_wfs.c test_urcu_wfs_dynlink_CFLAGS = -DDYNAMIC_LINK_TEST $(AM_CFLAGS) diff --git a/urcu/rculfqueue-static.h b/urcu/rculfqueue-static.h new file mode 100644 index 0000000..ffc5bdb --- /dev/null +++ b/urcu/rculfqueue-static.h @@ -0,0 +1,145 @@ +#ifndef _URCU_RCULFQUEUE_STATIC_H +#define _URCU_RCULFQUEUE_STATIC_H + +/* + * rculfqueue-static.h + * + * Userspace RCU library - Lock-Free RCU Queue + * + * Copyright 2010 - Mathieu Desnoyers + * + * TO BE INCLUDED ONLY IN LGPL-COMPATIBLE CODE. See rculfqueue.h for linking + * dynamically with the userspace rcu library. + * + * 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 +/* A urcu implementation header should be already included. */ + +#ifdef __cplusplus +extern "C" { +#endif + +/* + * Lock-free RCU queue using reference counting. Enqueue and dequeue operations + * hold a RCU read lock to deal with cmpxchg ABA problem. This implementation + * keeps a dummy head node to ensure we can always update the queue locklessly. + * Given that this is a queue, the dummy head node must always advance as we + * dequeue entries. Therefore, we keep a reference count on each entry we are + * dequeueing, so they can be kept as dummy head node until the next dequeue, at + * which point their reference count will be decremented. + */ + +#define URCU_LFQ_PERMANENT_REF 128 + +void _rcu_lfq_node_init(struct rcu_lfq_node *node) +{ + node->next = NULL; + urcu_ref_init(&node->ref); +} + +void _rcu_lfq_init(struct rcu_lfq_queue *q) +{ + _rcu_lfq_node_init(&q->init); + /* Make sure the initial node is never freed. */ + urcu_ref_set(&q->init.ref, URCU_LFQ_PERMANENT_REF); + q->head = q->tail = &q->init; +} + +void _rcu_lfq_enqueue(struct rcu_lfq_queue *q, struct rcu_lfq_node *node) +{ + urcu_ref_get(&node->ref); + + /* + * uatomic_cmpxchg() implicit memory barrier orders earlier stores to + * node before publication. + */ + + for (;;) { + struct rcu_lfq_node *tail, *next; + + rcu_read_lock(); + tail = rcu_dereference(q->tail); + /* + * Typically expect tail->next to be NULL. + */ + next = uatomic_cmpxchg(&tail->next, NULL, node); + if (next == NULL) { + /* + * Tail was at the end of queue, we successfully + * appended to it. + * Now move tail (another enqueue might beat + * us to it, that's fine). + */ + uatomic_cmpxchg(&q->tail, tail, node); + rcu_read_unlock(); + return; + } else { + /* + * Failure to append to current tail. Help moving tail + * further and retry. + */ + uatomic_cmpxchg(&q->tail, tail, next); + rcu_read_unlock(); + continue; + } + } +} + +/* + * The entry returned by dequeue must be taken care of by doing a urcu_ref_put, + * which calls the release primitive when the reference count drops to zero. A + * grace period must be waited after execution of the release callback before + * performing the actual memory reclamation or modifying the rcu_lfq_node + * structure. + * In other words, the entry lfq node returned by dequeue must not be + * modified/re-used/freed until the reference count reaches zero and a grace + * period has elapsed (after the refcount reached 0). + */ +struct rcu_lfq_node * +_rcu_lfq_dequeue(struct rcu_lfq_queue *q, void (*release)(struct urcu_ref *)) +{ + for (;;) { + struct rcu_lfq_node *head, *next; + + rcu_read_lock(); + head = rcu_dereference(q->head); + next = rcu_dereference(head->next); + if (next) { + if (uatomic_cmpxchg(&q->head, head, next) == head) { + rcu_read_unlock(); + urcu_ref_put(&head->ref, release); + return next; + } else { + /* Concurrently pushed, retry */ + rcu_read_unlock(); + continue; + } + } else { + /* Empty */ + rcu_read_unlock(); + return NULL; + } + } +} + +#ifdef __cplusplus +} +#endif + +#endif /* _URCU_RCULFQUEUE_STATIC_H */ diff --git a/urcu/rculfqueue.h b/urcu/rculfqueue.h index d5c7428..f229cc7 100644 --- a/urcu/rculfqueue.h +++ b/urcu/rculfqueue.h @@ -30,10 +30,6 @@ extern "C" { #endif -#if (!defined(_GNU_SOURCE) && !defined(_LGPL_SOURCE)) -#error "Dynamic loader LGPL wrappers not implemented yet" -#endif - /* * Lock-free RCU queue using reference counting. Enqueue and dequeue operations * hold a RCU read lock to deal with cmpxchg ABA problem. This implementation @@ -44,8 +40,6 @@ extern "C" { * which point their reference count will be decremented. */ -#define URCU_LFQ_PERMANENT_REF 128 - struct rcu_lfq_node { struct rcu_lfq_node *next; struct urcu_ref ref; @@ -56,59 +50,20 @@ struct rcu_lfq_queue { struct rcu_lfq_node init; /* Dummy initialization node */ }; -void rcu_lfq_node_init(struct rcu_lfq_node *node) -{ - node->next = NULL; - urcu_ref_init(&node->ref); -} - -void rcu_lfq_init(struct rcu_lfq_queue *q) -{ - rcu_lfq_node_init(&q->init); - /* Make sure the initial node is never freed. */ - urcu_ref_set(&q->init.ref, URCU_LFQ_PERMANENT_REF); - q->head = q->tail = &q->init; -} +#ifdef _LGPL_SOURCE -void rcu_lfq_enqueue(struct rcu_lfq_queue *q, struct rcu_lfq_node *node) -{ - urcu_ref_get(&node->ref); +#include - /* - * uatomic_cmpxchg() implicit memory barrier orders earlier stores to - * node before publication. - */ +#define rcu_lfq_node_init _rcu_lfq_node_init +#define rcu_lfq_init _rcu_lfq_init +#define rcu_lfq_enqueue _rcu_lfq_enqueue +#define rcu_lfq_dequeue _rcu_lfq_dequeue - for (;;) { - struct rcu_lfq_node *tail, *next; +#else /* !_LGPL_SOURCE */ - rcu_read_lock(); - tail = rcu_dereference(q->tail); - /* - * Typically expect tail->next to be NULL. - */ - next = uatomic_cmpxchg(&tail->next, NULL, node); - if (next == NULL) { - /* - * Tail was at the end of queue, we successfully - * appended to it. - * Now move tail (another enqueue might beat - * us to it, that's fine). - */ - uatomic_cmpxchg(&q->tail, tail, node); - rcu_read_unlock(); - return; - } else { - /* - * Failure to append to current tail. Help moving tail - * further and retry. - */ - uatomic_cmpxchg(&q->tail, tail, next); - rcu_read_unlock(); - continue; - } - } -} +extern void rcu_lfq_node_init(struct rcu_lfq_node *node); +extern void rcu_lfq_init(struct rcu_lfq_queue *q); +extern void rcu_lfq_enqueue(struct rcu_lfq_queue *q, struct rcu_lfq_node *node); /* * The entry returned by dequeue must be taken care of by doing a urcu_ref_put, @@ -120,32 +75,10 @@ void rcu_lfq_enqueue(struct rcu_lfq_queue *q, struct rcu_lfq_node *node) * modified/re-used/freed until the reference count reaches zero and a grace * period has elapsed (after the refcount reached 0). */ -struct rcu_lfq_node * -rcu_lfq_dequeue(struct rcu_lfq_queue *q, void (*release)(struct urcu_ref *)) -{ - for (;;) { - struct rcu_lfq_node *head, *next; +extern struct rcu_lfq_node * +rcu_lfq_dequeue(struct rcu_lfq_queue *q, void (*release)(struct urcu_ref *)); - rcu_read_lock(); - head = rcu_dereference(q->head); - next = rcu_dereference(head->next); - if (next) { - if (uatomic_cmpxchg(&q->head, head, next) == head) { - rcu_read_unlock(); - urcu_ref_put(&head->ref, release); - return next; - } else { - /* Concurrently pushed, retry */ - rcu_read_unlock(); - continue; - } - } else { - /* Empty */ - rcu_read_unlock(); - return NULL; - } - } -} +#endif /* !_LGPL_SOURCE */ #ifdef __cplusplus } -- 2.34.1