rculfqueue: LGPL-ize
authorMathieu Desnoyers <mathieu.desnoyers@efficios.com>
Sun, 22 Aug 2010 13:21:58 +0000 (09:21 -0400)
committerMathieu Desnoyers <mathieu.desnoyers@efficios.com>
Sun, 22 Aug 2010 13:21:58 +0000 (09:21 -0400)
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Makefile.am
rculfqueue.c [new file with mode: 0644]
tests/Makefile.am
urcu/rculfqueue-static.h [new file with mode: 0644]
urcu/rculfqueue.h

index 44ab874..2e6612d 100644 (file)
@@ -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 (file)
index 0000000..85c7b88
--- /dev/null
@@ -0,0 +1,52 @@
+/*
+ * rculfqueue.c
+ *
+ * Userspace RCU library - Lock-Free RCU Queue
+ *
+ * Copyright 2010 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
+ *
+ * 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);
+}
index 1d9f88f..f85d986 100644 (file)
@@ -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 (file)
index 0000000..ffc5bdb
--- /dev/null
@@ -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 <mathieu.desnoyers@efficios.com>
+ *
+ * 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 <urcu/urcu_ref.h>
+#include <urcu/uatomic_arch.h>
+#include <assert.h>
+/* 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 */
index d5c7428..f229cc7 100644 (file)
 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 <urcu/rculfqueue-static.h>
 
-       /*
-        * 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
 }
This page took 0.039758 seconds and 4 git commands to generate.