From: Paul E. McKenney Date: Fri, 3 Jun 2011 16:47:56 +0000 (-0400) Subject: Make defer_rcu() usable from library using multiple URCU implementations X-Git-Tag: v0.6.0~42 X-Git-Url: https://git.liburcu.org/?p=urcu.git;a=commitdiff_plain;h=0376e7b2f8d26778ebc4750b34e718c062c92764 Make defer_rcu() usable from library using multiple URCU implementations [ Edit: minor tab to whitespace cleanup ] Signed-off-by: Paul E. McKenney Signed-off-by: Mathieu Desnoyers --- diff --git a/Makefile.am b/Makefile.am index 4b70644..1589884 100644 --- a/Makefile.am +++ b/Makefile.am @@ -30,7 +30,7 @@ COMPAT+=compat_futex.c endif lib_LTLIBRARIES = liburcu.la liburcu-qsbr.la liburcu-mb.la liburcu-signal.la \ - liburcu-bp.la liburcu-defer.la \ + liburcu-bp.la \ libwfqueue.la libwfstack.la librculfqueue.la librculfstack.la liburcu_la_SOURCES = urcu.c urcu-pointer.c $(COMPAT) @@ -45,8 +45,6 @@ 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) libwfstack_la_SOURCES = wfstack.c $(COMPAT) librculfqueue_la_SOURCES = rculfqueue.c $(COMPAT) diff --git a/README b/README index 659511f..7d97f19 100644 --- a/README +++ b/README @@ -124,16 +124,15 @@ Writing Usage of liburcu-defer - * #include - * Link with "-lurcu-defer", and also with one of the urcu library - (either urcu, urcu-bp, urcu-mb or urcu-qsbr). + * Follow instructions for either liburcu, liburcu-qsbr, + liburcu-mb, liburcu-signal, or liburcu-bp above. + The liburcu-defer functionality is pulled into each of + those library modules. * Provides defer_rcu() primitive to enqueue delayed callbacks. Queued callbacks are executed in batch periodically after a grace period. Do _not_ use defer_rcu() within a read-side critical section, because it may call synchronize_rcu() if the thread queue is full. - * Provides defer_rcu_ratelimit() primitive, which acts just like - defer_rcu(), but takes an additional rate limiter callback forcing - synchronized callback execution of the limiter returns non-zero. + This can lead to deadlock or worse. * Requires that rcu_defer_barrier() must be called in library destructor if a library queues callbacks and is expected to be unloaded with dlclose(). diff --git a/tests/Makefile.am b/tests/Makefile.am index 8dacb11..5598689 100644 --- a/tests/Makefile.am +++ b/tests/Makefile.am @@ -35,7 +35,7 @@ URCU_MB=$(top_srcdir)/urcu.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfqueue. # URCU_SIGNAL uses urcu.c but -DRCU_SIGNAL must be defined URCU_SIGNAL=$(top_srcdir)/urcu.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfqueue.c $(COMPAT) URCU_BP=$(top_srcdir)/urcu-bp.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfqueue.c $(COMPAT) -URCU_DEFER=$(top_srcdir)/urcu.c $(top_srcdir)/urcu-defer.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfqueue.c $(COMPAT) +URCU_DEFER=$(top_srcdir)/urcu.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfqueue.c $(COMPAT) URCU_LIB=$(top_builddir)/liburcu.la URCU_QSBR_LIB=$(top_builddir)/liburcu-qsbr.la diff --git a/urcu-bp-map.h b/urcu-bp-map.h index 6321802..4abe8dc 100644 --- a/urcu-bp-map.h +++ b/urcu-bp-map.h @@ -58,4 +58,10 @@ #define free_all_cpu_call_rcu_data free_all_cpu_call_rcu_data_bp #define call_rcu call_rcu_bp +#define defer_rcu defer_rcu_bp +#define rcu_defer_register_thread rcu_defer_register_thread_bp +#define rcu_defer_unregister_thread rcu_defer_unregister_thread_bp +#define rcu_defer_barrier rcu_defer_barrier_bp +#define rcu_defer_barrier_thread rcu_defer_barrier_thread_bp + #endif /* _URCU_BP_MAP_H */ diff --git a/urcu-bp.c b/urcu-bp.c index 5474f9f..14b2001 100644 --- a/urcu-bp.c +++ b/urcu-bp.c @@ -379,3 +379,4 @@ void rcu_bp_after_fork_child(void) } #include "urcu-call-rcu-impl.h" +#include "urcu-defer-impl.h" diff --git a/urcu-bp.h b/urcu-bp.h index bc2dbc3..21fe66a 100644 --- a/urcu-bp.h +++ b/urcu-bp.h @@ -118,5 +118,6 @@ static inline void rcu_init(void) #endif #include "urcu-call-rcu.h" +#include "urcu-defer.h" #endif /* _URCU_BP_H */ diff --git a/urcu-defer-impl.h b/urcu-defer-impl.h new file mode 100644 index 0000000..0aedd53 --- /dev/null +++ b/urcu-defer-impl.h @@ -0,0 +1,450 @@ +#ifndef _URCU_DEFER_IMPL_H +#define _URCU_DEFER_IMPL_H + +/* + * urcu-defer-impl.h + * + * Userspace RCU header - memory reclamation. + * + * TO BE INCLUDED ONLY FROM URCU LIBRARY CODE. See urcu-defer.h for linking + * dynamically with the userspace rcu reclamation library. + * + * Copyright (c) 2009 Mathieu Desnoyers + * Copyright (c) 2009 Paul E. McKenney, IBM Corporation. + * + * 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 + * + * IBM's contributions to this file may be relicensed under LGPLv2 or later. + */ + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include "urcu/urcu-futex.h" + +#include +#include +#include +#include +#include + +/* + * Number of entries in the per-thread defer queue. Must be power of 2. + */ +#define DEFER_QUEUE_SIZE (1 << 12) +#define DEFER_QUEUE_MASK (DEFER_QUEUE_SIZE - 1) + +/* + * Typically, data is aligned at least on the architecture size. + * Use lowest bit to indicate that the current callback is changing. + * Assumes that (void *)-2L is not used often. Used to encode non-aligned + * functions and non-aligned data using extra space. + * We encode the (void *)-2L fct as: -2L, fct, data. + * We encode the (void *)-2L data as: -2L, fct, data. + * Here, DQ_FCT_MARK == ~DQ_FCT_BIT. Required for the test order. + */ +#define DQ_FCT_BIT (1 << 0) +#define DQ_IS_FCT_BIT(x) ((unsigned long)(x) & DQ_FCT_BIT) +#define DQ_SET_FCT_BIT(x) \ + (x = (void *)((unsigned long)(x) | DQ_FCT_BIT)) +#define DQ_CLEAR_FCT_BIT(x) \ + (x = (void *)((unsigned long)(x) & ~DQ_FCT_BIT)) +#define DQ_FCT_MARK ((void *)(~DQ_FCT_BIT)) + +/* + * This code section can only be included in LGPL 2.1 compatible source code. + * See below for the function call wrappers which can be used in code meant to + * be only linked with the Userspace RCU library. This comes with a small + * performance degradation on the read-side due to the added function calls. + * This is required to permit relinking with newer versions of the library. + */ + +#ifdef DEBUG_RCU +#define rcu_assert(args...) assert(args) +#else +#define rcu_assert(args...) +#endif + +/* + * defer queue. + * Contains pointers. Encoded to save space when same callback is often used. + * When looking up the next item: + * - if DQ_FCT_BIT is set, set the current callback to DQ_CLEAR_FCT_BIT(ptr) + * - next element contains pointer to data. + * - else if item == DQ_FCT_MARK + * - set the current callback to next element ptr + * - following next element contains pointer to data. + * - else current element contains data + */ +struct defer_queue { + unsigned long head; /* add element at head */ + void *last_fct_in; /* last fct pointer encoded */ + unsigned long tail; /* next element to remove at tail */ + void *last_fct_out; /* last fct pointer encoded */ + void **q; + /* registry information */ + unsigned long last_head; + struct cds_list_head list; /* list of thread queues */ +}; + +/* Do not #define _LGPL_SOURCE to ensure we can emit the wrapper symbols */ +#include "urcu-defer.h" + +void __attribute__((destructor)) rcu_defer_exit(void); + +extern void synchronize_rcu(void); + +/* + * rcu_defer_mutex nests inside defer_thread_mutex. + */ +static pthread_mutex_t rcu_defer_mutex = PTHREAD_MUTEX_INITIALIZER; +static pthread_mutex_t defer_thread_mutex = PTHREAD_MUTEX_INITIALIZER; + +static int defer_thread_futex; + +/* + * Written to only by each individual deferer. Read by both the deferer and + * the reclamation tread. + */ +static struct defer_queue __thread defer_queue; +static CDS_LIST_HEAD(registry_defer); +static pthread_t tid_defer; + +static void mutex_lock_defer(pthread_mutex_t *mutex) +{ + int ret; + +#ifndef DISTRUST_SIGNALS_EXTREME + ret = pthread_mutex_lock(mutex); + if (ret) { + perror("Error in pthread mutex lock"); + exit(-1); + } +#else /* #ifndef DISTRUST_SIGNALS_EXTREME */ + while ((ret = pthread_mutex_trylock(mutex)) != 0) { + if (ret != EBUSY && ret != EINTR) { + printf("ret = %d, errno = %d\n", ret, errno); + perror("Error in pthread mutex lock"); + exit(-1); + } + pthread_testcancel(); + poll(NULL,0,10); + } +#endif /* #else #ifndef DISTRUST_SIGNALS_EXTREME */ +} + +/* + * Wake-up any waiting defer thread. Called from many concurrent threads. + */ +static void wake_up_defer(void) +{ + if (unlikely(uatomic_read(&defer_thread_futex) == -1)) { + uatomic_set(&defer_thread_futex, 0); + futex_noasync(&defer_thread_futex, FUTEX_WAKE, 1, + NULL, NULL, 0); + } +} + +static unsigned long rcu_defer_num_callbacks(void) +{ + unsigned long num_items = 0, head; + struct defer_queue *index; + + mutex_lock_defer(&rcu_defer_mutex); + cds_list_for_each_entry(index, ®istry_defer, list) { + head = CMM_LOAD_SHARED(index->head); + num_items += head - index->tail; + } + mutex_unlock(&rcu_defer_mutex); + return num_items; +} + +/* + * Defer thread waiting. Single thread. + */ +static void wait_defer(void) +{ + uatomic_dec(&defer_thread_futex); + cmm_smp_mb(); /* Write futex before read queue */ + if (rcu_defer_num_callbacks()) { + cmm_smp_mb(); /* Read queue before write futex */ + /* Callbacks are queued, don't wait. */ + uatomic_set(&defer_thread_futex, 0); + } else { + cmm_smp_rmb(); /* Read queue before read futex */ + if (uatomic_read(&defer_thread_futex) == -1) + futex_noasync(&defer_thread_futex, FUTEX_WAIT, -1, + NULL, NULL, 0); + } +} + +/* + * Must be called after Q.S. is reached. + */ +static void rcu_defer_barrier_queue(struct defer_queue *queue, + unsigned long head) +{ + unsigned long i; + void (*fct)(void *p); + void *p; + + /* + * Tail is only modified when lock is held. + * Head is only modified by owner thread. + */ + + for (i = queue->tail; i != head;) { + cmm_smp_rmb(); /* read head before q[]. */ + p = CMM_LOAD_SHARED(queue->q[i++ & DEFER_QUEUE_MASK]); + if (unlikely(DQ_IS_FCT_BIT(p))) { + DQ_CLEAR_FCT_BIT(p); + queue->last_fct_out = p; + p = CMM_LOAD_SHARED(queue->q[i++ & DEFER_QUEUE_MASK]); + } else if (unlikely(p == DQ_FCT_MARK)) { + p = CMM_LOAD_SHARED(queue->q[i++ & DEFER_QUEUE_MASK]); + queue->last_fct_out = p; + p = CMM_LOAD_SHARED(queue->q[i++ & DEFER_QUEUE_MASK]); + } + fct = queue->last_fct_out; + fct(p); + } + cmm_smp_mb(); /* push tail after having used q[] */ + CMM_STORE_SHARED(queue->tail, i); +} + +static void _rcu_defer_barrier_thread(void) +{ + unsigned long head, num_items; + + head = defer_queue.head; + num_items = head - defer_queue.tail; + if (unlikely(!num_items)) + return; + synchronize_rcu(); + rcu_defer_barrier_queue(&defer_queue, head); +} + +void rcu_defer_barrier_thread(void) +{ + mutex_lock_defer(&rcu_defer_mutex); + _rcu_defer_barrier_thread(); + mutex_unlock(&rcu_defer_mutex); +} + +/* + * rcu_defer_barrier - Execute all queued rcu callbacks. + * + * Execute all RCU callbacks queued before rcu_defer_barrier() execution. + * All callbacks queued on the local thread prior to a rcu_defer_barrier() call + * are guaranteed to be executed. + * Callbacks queued by other threads concurrently with rcu_defer_barrier() + * execution are not guaranteed to be executed in the current batch (could + * be left for the next batch). These callbacks queued by other threads are only + * guaranteed to be executed if there is explicit synchronization between + * the thread adding to the queue and the thread issuing the defer_barrier call. + */ + +void rcu_defer_barrier(void) +{ + struct defer_queue *index; + unsigned long num_items = 0; + + if (cds_list_empty(®istry_defer)) + return; + + mutex_lock_defer(&rcu_defer_mutex); + cds_list_for_each_entry(index, ®istry_defer, list) { + index->last_head = CMM_LOAD_SHARED(index->head); + num_items += index->last_head - index->tail; + } + if (likely(!num_items)) { + /* + * We skip the grace period because there are no queued + * callbacks to execute. + */ + goto end; + } + synchronize_rcu(); + cds_list_for_each_entry(index, ®istry_defer, list) + rcu_defer_barrier_queue(index, index->last_head); +end: + mutex_unlock(&rcu_defer_mutex); +} + +/* + * _defer_rcu - Queue a RCU callback. + */ +void _defer_rcu(void (*fct)(void *p), void *p) +{ + unsigned long head, tail; + + /* + * Head is only modified by ourself. Tail can be modified by reclamation + * thread. + */ + head = defer_queue.head; + tail = CMM_LOAD_SHARED(defer_queue.tail); + + /* + * If queue is full, or reached threshold. Empty queue ourself. + * Worse-case: must allow 2 supplementary entries for fct pointer. + */ + if (unlikely(head - tail >= DEFER_QUEUE_SIZE - 2)) { + assert(head - tail <= DEFER_QUEUE_SIZE); + rcu_defer_barrier_thread(); + assert(head - CMM_LOAD_SHARED(defer_queue.tail) == 0); + } + + if (unlikely(defer_queue.last_fct_in != fct)) { + defer_queue.last_fct_in = fct; + if (unlikely(DQ_IS_FCT_BIT(fct) || fct == DQ_FCT_MARK)) { + /* + * If the function to encode is not aligned or the + * marker, write DQ_FCT_MARK followed by the function + * pointer. + */ + _CMM_STORE_SHARED(defer_queue.q[head++ & DEFER_QUEUE_MASK], + DQ_FCT_MARK); + _CMM_STORE_SHARED(defer_queue.q[head++ & DEFER_QUEUE_MASK], + fct); + } else { + DQ_SET_FCT_BIT(fct); + _CMM_STORE_SHARED(defer_queue.q[head++ & DEFER_QUEUE_MASK], + fct); + } + } else { + if (unlikely(DQ_IS_FCT_BIT(p) || p == DQ_FCT_MARK)) { + /* + * If the data to encode is not aligned or the marker, + * write DQ_FCT_MARK followed by the function pointer. + */ + _CMM_STORE_SHARED(defer_queue.q[head++ & DEFER_QUEUE_MASK], + DQ_FCT_MARK); + _CMM_STORE_SHARED(defer_queue.q[head++ & DEFER_QUEUE_MASK], + fct); + } + } + _CMM_STORE_SHARED(defer_queue.q[head++ & DEFER_QUEUE_MASK], p); + cmm_smp_wmb(); /* Publish new pointer before head */ + /* Write q[] before head. */ + CMM_STORE_SHARED(defer_queue.head, head); + cmm_smp_mb(); /* Write queue head before read futex */ + /* + * Wake-up any waiting defer thread. + */ + wake_up_defer(); +} + +void *thr_defer(void *args) +{ + for (;;) { + pthread_testcancel(); + /* + * "Be green". Don't wake up the CPU if there is no RCU work + * to perform whatsoever. Aims at saving laptop battery life by + * leaving the processor in sleep state when idle. + */ + wait_defer(); + /* Sleeping after wait_defer to let many callbacks enqueue */ + poll(NULL,0,100); /* wait for 100ms */ + rcu_defer_barrier(); + } + + return NULL; +} + +/* + * library wrappers to be used by non-LGPL compatible source code. + */ + +void defer_rcu(void (*fct)(void *p), void *p) +{ + _defer_rcu(fct, p); +} + +static void start_defer_thread(void) +{ + int ret; + + ret = pthread_create(&tid_defer, NULL, thr_defer, NULL); + assert(!ret); +} + +static void stop_defer_thread(void) +{ + int ret; + void *tret; + + pthread_cancel(tid_defer); + wake_up_defer(); + ret = pthread_join(tid_defer, &tret); + assert(!ret); +} + +int rcu_defer_register_thread(void) +{ + int was_empty; + + assert(defer_queue.last_head == 0); + assert(defer_queue.q == NULL); + defer_queue.q = malloc(sizeof(void *) * DEFER_QUEUE_SIZE); + if (!defer_queue.q) + return -ENOMEM; + + mutex_lock_defer(&defer_thread_mutex); + mutex_lock_defer(&rcu_defer_mutex); + was_empty = cds_list_empty(®istry_defer); + cds_list_add(&defer_queue.list, ®istry_defer); + mutex_unlock(&rcu_defer_mutex); + + if (was_empty) + start_defer_thread(); + mutex_unlock(&defer_thread_mutex); + return 0; +} + +void rcu_defer_unregister_thread(void) +{ + int is_empty; + + mutex_lock_defer(&defer_thread_mutex); + mutex_lock_defer(&rcu_defer_mutex); + cds_list_del(&defer_queue.list); + _rcu_defer_barrier_thread(); + free(defer_queue.q); + defer_queue.q = NULL; + is_empty = cds_list_empty(®istry_defer); + mutex_unlock(&rcu_defer_mutex); + + if (is_empty) + stop_defer_thread(); + mutex_unlock(&defer_thread_mutex); +} + +void rcu_defer_exit(void) +{ + assert(cds_list_empty(®istry_defer)); +} + +#endif /* _URCU_DEFER_IMPL_H */ diff --git a/urcu-defer-static.h b/urcu-defer-static.h deleted file mode 100644 index 3e5df3e..0000000 --- a/urcu-defer-static.h +++ /dev/null @@ -1,108 +0,0 @@ -#ifndef _URCU_DEFER_STATIC_H -#define _URCU_DEFER_STATIC_H - -/* - * urcu-defer-static.h - * - * Userspace RCU header - memory reclamation. - * - * TO BE INCLUDED ONLY IN LGPL-COMPATIBLE CODE. See urcu-defer.h for linking - * dynamically with the userspace rcu reclamation library. - * - * Copyright (c) 2009 Mathieu Desnoyers - * Copyright (c) 2009 Paul E. McKenney, IBM Corporation. - * - * 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 - * - * IBM's contributions to this file may be relicensed under LGPLv2 or later. - */ - -#include -#include - -#include -#include -#include -#include -#include - -#ifdef __cplusplus -extern "C" { -#endif - -/* - * Number of entries in the per-thread defer queue. Must be power of 2. - */ -#define DEFER_QUEUE_SIZE (1 << 12) -#define DEFER_QUEUE_MASK (DEFER_QUEUE_SIZE - 1) - -/* - * Typically, data is aligned at least on the architecture size. - * Use lowest bit to indicate that the current callback is changing. - * Assumes that (void *)-2L is not used often. Used to encode non-aligned - * functions and non-aligned data using extra space. - * We encode the (void *)-2L fct as: -2L, fct, data. - * We encode the (void *)-2L data as: -2L, fct, data. - * Here, DQ_FCT_MARK == ~DQ_FCT_BIT. Required for the test order. - */ -#define DQ_FCT_BIT (1 << 0) -#define DQ_IS_FCT_BIT(x) ((unsigned long)(x) & DQ_FCT_BIT) -#define DQ_SET_FCT_BIT(x) \ - (x = (void *)((unsigned long)(x) | DQ_FCT_BIT)) -#define DQ_CLEAR_FCT_BIT(x) \ - (x = (void *)((unsigned long)(x) & ~DQ_FCT_BIT)) -#define DQ_FCT_MARK ((void *)(~DQ_FCT_BIT)) - -/* - * This code section can only be included in LGPL 2.1 compatible source code. - * See below for the function call wrappers which can be used in code meant to - * be only linked with the Userspace RCU library. This comes with a small - * performance degradation on the read-side due to the added function calls. - * This is required to permit relinking with newer versions of the library. - */ - -#ifdef DEBUG_RCU -#define rcu_assert(args...) assert(args) -#else -#define rcu_assert(args...) -#endif - -/* - * defer queue. - * Contains pointers. Encoded to save space when same callback is often used. - * When looking up the next item: - * - if DQ_FCT_BIT is set, set the current callback to DQ_CLEAR_FCT_BIT(ptr) - * - next element contains pointer to data. - * - else if item == DQ_FCT_MARK - * - set the current callback to next element ptr - * - following next element contains pointer to data. - * - else current element contains data - */ -struct defer_queue { - unsigned long head; /* add element at head */ - void *last_fct_in; /* last fct pointer encoded */ - unsigned long tail; /* next element to remove at tail */ - void *last_fct_out; /* last fct pointer encoded */ - void **q; - /* registry information */ - unsigned long last_head; - struct cds_list_head list; /* list of thread queues */ -}; - -#ifdef __cplusplus -} -#endif - -#endif /* _URCU_DEFER_STATIC_H */ diff --git a/urcu-defer.c b/urcu-defer.c deleted file mode 100644 index 3f596ae..0000000 --- a/urcu-defer.c +++ /dev/null @@ -1,385 +0,0 @@ -/* - * urcu-defer.c - * - * Userspace RCU library - batch memory reclamation - * - * Copyright (c) 2009 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 -#include -#include -#include -#include -#include -#include -#include - -#include "urcu/urcu-futex.h" -#include "urcu-defer-static.h" -/* Do not #define _LGPL_SOURCE to ensure we can emit the wrapper symbols */ -#include "urcu-defer.h" - -void __attribute__((destructor)) rcu_defer_exit(void); - -extern void synchronize_rcu(void); - -/* - * rcu_defer_mutex nests inside defer_thread_mutex. - */ -static pthread_mutex_t rcu_defer_mutex = PTHREAD_MUTEX_INITIALIZER; -static pthread_mutex_t defer_thread_mutex = PTHREAD_MUTEX_INITIALIZER; - -static int defer_thread_futex; - -/* - * Written to only by each individual deferer. Read by both the deferer and - * the reclamation tread. - */ -static struct defer_queue __thread defer_queue; -static CDS_LIST_HEAD(registry); -static pthread_t tid_defer; - -static void mutex_lock(pthread_mutex_t *mutex) -{ - int ret; - -#ifndef DISTRUST_SIGNALS_EXTREME - ret = pthread_mutex_lock(mutex); - if (ret) { - perror("Error in pthread mutex lock"); - exit(-1); - } -#else /* #ifndef DISTRUST_SIGNALS_EXTREME */ - while ((ret = pthread_mutex_trylock(mutex)) != 0) { - if (ret != EBUSY && ret != EINTR) { - printf("ret = %d, errno = %d\n", ret, errno); - perror("Error in pthread mutex lock"); - exit(-1); - } - pthread_testcancel(); - poll(NULL,0,10); - } -#endif /* #else #ifndef DISTRUST_SIGNALS_EXTREME */ -} - -static void mutex_unlock(pthread_mutex_t *mutex) -{ - int ret; - - ret = pthread_mutex_unlock(mutex); - if (ret) { - perror("Error in pthread mutex unlock"); - exit(-1); - } -} - -/* - * Wake-up any waiting defer thread. Called from many concurrent threads. - */ -static void wake_up_defer(void) -{ - if (unlikely(uatomic_read(&defer_thread_futex) == -1)) { - uatomic_set(&defer_thread_futex, 0); - futex_noasync(&defer_thread_futex, FUTEX_WAKE, 1, - NULL, NULL, 0); - } -} - -static unsigned long rcu_defer_num_callbacks(void) -{ - unsigned long num_items = 0, head; - struct defer_queue *index; - - mutex_lock(&rcu_defer_mutex); - cds_list_for_each_entry(index, ®istry, list) { - head = CMM_LOAD_SHARED(index->head); - num_items += head - index->tail; - } - mutex_unlock(&rcu_defer_mutex); - return num_items; -} - -/* - * Defer thread waiting. Single thread. - */ -static void wait_defer(void) -{ - uatomic_dec(&defer_thread_futex); - cmm_smp_mb(); /* Write futex before read queue */ - if (rcu_defer_num_callbacks()) { - cmm_smp_mb(); /* Read queue before write futex */ - /* Callbacks are queued, don't wait. */ - uatomic_set(&defer_thread_futex, 0); - } else { - cmm_smp_rmb(); /* Read queue before read futex */ - if (uatomic_read(&defer_thread_futex) == -1) - futex_noasync(&defer_thread_futex, FUTEX_WAIT, -1, - NULL, NULL, 0); - } -} - -/* - * Must be called after Q.S. is reached. - */ -static void rcu_defer_barrier_queue(struct defer_queue *queue, - unsigned long head) -{ - unsigned long i; - void (*fct)(void *p); - void *p; - - /* - * Tail is only modified when lock is held. - * Head is only modified by owner thread. - */ - - for (i = queue->tail; i != head;) { - cmm_smp_rmb(); /* read head before q[]. */ - p = CMM_LOAD_SHARED(queue->q[i++ & DEFER_QUEUE_MASK]); - if (unlikely(DQ_IS_FCT_BIT(p))) { - DQ_CLEAR_FCT_BIT(p); - queue->last_fct_out = p; - p = CMM_LOAD_SHARED(queue->q[i++ & DEFER_QUEUE_MASK]); - } else if (unlikely(p == DQ_FCT_MARK)) { - p = CMM_LOAD_SHARED(queue->q[i++ & DEFER_QUEUE_MASK]); - queue->last_fct_out = p; - p = CMM_LOAD_SHARED(queue->q[i++ & DEFER_QUEUE_MASK]); - } - fct = queue->last_fct_out; - fct(p); - } - cmm_smp_mb(); /* push tail after having used q[] */ - CMM_STORE_SHARED(queue->tail, i); -} - -static void _rcu_defer_barrier_thread(void) -{ - unsigned long head, num_items; - - head = defer_queue.head; - num_items = head - defer_queue.tail; - if (unlikely(!num_items)) - return; - synchronize_rcu(); - rcu_defer_barrier_queue(&defer_queue, head); -} - -void rcu_defer_barrier_thread(void) -{ - mutex_lock(&rcu_defer_mutex); - _rcu_defer_barrier_thread(); - mutex_unlock(&rcu_defer_mutex); -} - -/* - * rcu_defer_barrier - Execute all queued rcu callbacks. - * - * Execute all RCU callbacks queued before rcu_defer_barrier() execution. - * All callbacks queued on the local thread prior to a rcu_defer_barrier() call - * are guaranteed to be executed. - * Callbacks queued by other threads concurrently with rcu_defer_barrier() - * execution are not guaranteed to be executed in the current batch (could - * be left for the next batch). These callbacks queued by other threads are only - * guaranteed to be executed if there is explicit synchronization between - * the thread adding to the queue and the thread issuing the defer_barrier call. - */ - -void rcu_defer_barrier(void) -{ - struct defer_queue *index; - unsigned long num_items = 0; - - if (cds_list_empty(®istry)) - return; - - mutex_lock(&rcu_defer_mutex); - cds_list_for_each_entry(index, ®istry, list) { - index->last_head = CMM_LOAD_SHARED(index->head); - num_items += index->last_head - index->tail; - } - if (likely(!num_items)) { - /* - * We skip the grace period because there are no queued - * callbacks to execute. - */ - goto end; - } - synchronize_rcu(); - cds_list_for_each_entry(index, ®istry, list) - rcu_defer_barrier_queue(index, index->last_head); -end: - mutex_unlock(&rcu_defer_mutex); -} - -/* - * _defer_rcu - Queue a RCU callback. - */ -void _defer_rcu(void (*fct)(void *p), void *p) -{ - unsigned long head, tail; - - /* - * Head is only modified by ourself. Tail can be modified by reclamation - * thread. - */ - head = defer_queue.head; - tail = CMM_LOAD_SHARED(defer_queue.tail); - - /* - * If queue is full, or reached threshold. Empty queue ourself. - * Worse-case: must allow 2 supplementary entries for fct pointer. - */ - if (unlikely(head - tail >= DEFER_QUEUE_SIZE - 2)) { - assert(head - tail <= DEFER_QUEUE_SIZE); - rcu_defer_barrier_thread(); - assert(head - CMM_LOAD_SHARED(defer_queue.tail) == 0); - } - - if (unlikely(defer_queue.last_fct_in != fct)) { - defer_queue.last_fct_in = fct; - if (unlikely(DQ_IS_FCT_BIT(fct) || fct == DQ_FCT_MARK)) { - /* - * If the function to encode is not aligned or the - * marker, write DQ_FCT_MARK followed by the function - * pointer. - */ - _CMM_STORE_SHARED(defer_queue.q[head++ & DEFER_QUEUE_MASK], - DQ_FCT_MARK); - _CMM_STORE_SHARED(defer_queue.q[head++ & DEFER_QUEUE_MASK], - fct); - } else { - DQ_SET_FCT_BIT(fct); - _CMM_STORE_SHARED(defer_queue.q[head++ & DEFER_QUEUE_MASK], - fct); - } - } else { - if (unlikely(DQ_IS_FCT_BIT(p) || p == DQ_FCT_MARK)) { - /* - * If the data to encode is not aligned or the marker, - * write DQ_FCT_MARK followed by the function pointer. - */ - _CMM_STORE_SHARED(defer_queue.q[head++ & DEFER_QUEUE_MASK], - DQ_FCT_MARK); - _CMM_STORE_SHARED(defer_queue.q[head++ & DEFER_QUEUE_MASK], - fct); - } - } - _CMM_STORE_SHARED(defer_queue.q[head++ & DEFER_QUEUE_MASK], p); - cmm_smp_wmb(); /* Publish new pointer before head */ - /* Write q[] before head. */ - CMM_STORE_SHARED(defer_queue.head, head); - cmm_smp_mb(); /* Write queue head before read futex */ - /* - * Wake-up any waiting defer thread. - */ - wake_up_defer(); -} - -void *thr_defer(void *args) -{ - for (;;) { - pthread_testcancel(); - /* - * "Be green". Don't wake up the CPU if there is no RCU work - * to perform whatsoever. Aims at saving laptop battery life by - * leaving the processor in sleep state when idle. - */ - wait_defer(); - /* Sleeping after wait_defer to let many callbacks enqueue */ - poll(NULL,0,100); /* wait for 100ms */ - rcu_defer_barrier(); - } - - return NULL; -} - -/* - * library wrappers to be used by non-LGPL compatible source code. - */ - -void defer_rcu(void (*fct)(void *p), void *p) -{ - _defer_rcu(fct, p); -} - -static void start_defer_thread(void) -{ - int ret; - - ret = pthread_create(&tid_defer, NULL, thr_defer, NULL); - assert(!ret); -} - -static void stop_defer_thread(void) -{ - int ret; - void *tret; - - pthread_cancel(tid_defer); - wake_up_defer(); - ret = pthread_join(tid_defer, &tret); - assert(!ret); -} - -int rcu_defer_register_thread(void) -{ - int was_empty; - - assert(defer_queue.last_head == 0); - assert(defer_queue.q == NULL); - defer_queue.q = malloc(sizeof(void *) * DEFER_QUEUE_SIZE); - if (!defer_queue.q) - return -ENOMEM; - - mutex_lock(&defer_thread_mutex); - mutex_lock(&rcu_defer_mutex); - was_empty = cds_list_empty(®istry); - cds_list_add(&defer_queue.list, ®istry); - mutex_unlock(&rcu_defer_mutex); - - if (was_empty) - start_defer_thread(); - mutex_unlock(&defer_thread_mutex); - return 0; -} - -void rcu_defer_unregister_thread(void) -{ - int is_empty; - - mutex_lock(&defer_thread_mutex); - mutex_lock(&rcu_defer_mutex); - cds_list_del(&defer_queue.list); - _rcu_defer_barrier_thread(); - free(defer_queue.q); - defer_queue.q = NULL; - is_empty = cds_list_empty(®istry); - mutex_unlock(&rcu_defer_mutex); - - if (is_empty) - stop_defer_thread(); - mutex_unlock(&defer_thread_mutex); -} - -void rcu_defer_exit(void) -{ - assert(cds_list_empty(®istry)); -} diff --git a/urcu-map.h b/urcu-map.h index eccaac2..b55e304 100644 --- a/urcu-map.h +++ b/urcu-map.h @@ -34,6 +34,10 @@ /* Mapping macros to allow multiple flavors in a single binary. */ +#if !defined(RCU_MEMBARRIER) && !defined(RCU_SIGNAL) && !defined(RCU_MB) +#define RCU_MB +#endif + #ifdef RCU_MEMBARRIER #define rcu_read_lock rcu_read_lock_memb @@ -60,6 +64,12 @@ #define free_all_cpu_call_rcu_data free_all_cpu_call_rcu_data_memb #define call_rcu call_rcu_memb +#define defer_rcu defer_rcu_memb +#define rcu_defer_register_thread rcu_defer_register_thread_memb +#define rcu_defer_unregister_thread rcu_defer_unregister_thread_memb +#define rcu_defer_barrier rcu_defer_barrier_memb +#define rcu_defer_barrier_thread rcu_defer_barrier_thread_memb + #elif defined(RCU_SIGNAL) #define rcu_read_lock rcu_read_lock_sig @@ -86,6 +96,12 @@ #define free_all_cpu_call_rcu_data free_all_cpu_call_rcu_data_sig #define call_rcu call_rcu_sig +#define defer_rcu defer_rcu_sig +#define rcu_defer_register_thread rcu_defer_register_thread_sig +#define rcu_defer_unregister_thread rcu_defer_unregister_thread_sig +#define rcu_defer_barrier rcu_defer_barrier_sig +#define rcu_defer_barrier_thread rcu_defer_barrier_thread_sig + #elif defined(RCU_MB) #define rcu_read_lock rcu_read_lock_mb @@ -112,6 +128,16 @@ #define free_all_cpu_call_rcu_data free_all_cpu_call_rcu_data_mb #define call_rcu call_rcu_mb +#define defer_rcu defer_rcu_mb +#define rcu_defer_register_thread rcu_defer_register_thread_mb +#define rcu_defer_unregister_thread rcu_defer_unregister_thread_mb +#define rcu_defer_barrier rcu_defer_barrier_mb +#define rcu_defer_barrier_thread rcu_defer_barrier_thread_mb + +#else + +#error "Undefined selection" + #endif #endif /* _URCU_MAP_H */ diff --git a/urcu-qsbr-map.h b/urcu-qsbr-map.h index 2bce1b6..0d88d83 100644 --- a/urcu-qsbr-map.h +++ b/urcu-qsbr-map.h @@ -60,4 +60,10 @@ #define create_all_cpu_call_rcu_data create_all_cpu_call_rcu_data_qsbr #define call_rcu call_rcu_qsbr +#define defer_rcu defer_rcu_qsbr +#define rcu_defer_register_thread rcu_defer_register_thread_qsbr +#define rcu_defer_unregister_thread rcu_defer_unregister_thread_qsbr +#define rcu_defer_barrier rcu_defer_barrier_qsbr +#define rcu_defer_barrier_thread rcu_defer_barrier_thread_qsbr + #endif /* _URCU_QSBR_MAP_H */ diff --git a/urcu-qsbr.c b/urcu-qsbr.c index 8dcad33..cf8b5ce 100644 --- a/urcu-qsbr.c +++ b/urcu-qsbr.c @@ -334,3 +334,4 @@ void rcu_exit(void) } #include "urcu-call-rcu-impl.h" +#include "urcu-defer-impl.h" diff --git a/urcu-qsbr.h b/urcu-qsbr.h index 7ef1bfe..a691c52 100644 --- a/urcu-qsbr.h +++ b/urcu-qsbr.h @@ -125,5 +125,6 @@ extern void rcu_unregister_thread(void); #endif #include "urcu-call-rcu.h" +#include "urcu-defer.h" #endif /* _URCU_QSBR_H */ diff --git a/urcu.c b/urcu.c index 4ee9e3b..d356f54 100644 --- a/urcu.c +++ b/urcu.c @@ -434,3 +434,4 @@ void rcu_exit(void) #endif /* #ifdef RCU_SIGNAL */ #include "urcu-call-rcu-impl.h" +#include "urcu-defer-impl.h" diff --git a/urcu.h b/urcu.h index 417e609..15c8c38 100644 --- a/urcu.h +++ b/urcu.h @@ -111,5 +111,6 @@ extern void rcu_init(void); #endif #include "urcu-call-rcu.h" +#include "urcu-defer.h" #endif /* _URCU_H */