X-Git-Url: http://git.liburcu.org/?p=urcu.git;a=blobdiff_plain;f=urcu.h;h=3eca5ea3c44ccc7135635229c41141d5050df1e2;hp=363021d7832927e288705e42f7c31f4d36486d72;hb=40e140c9f237bbe8c50d4a5355561139f01afb70;hpb=f69f195a06af55b7501ed2f59ed719970727ce5b diff --git a/urcu.h b/urcu.h index 363021d..3eca5ea 100644 --- a/urcu.h +++ b/urcu.h @@ -1,69 +1,316 @@ #ifndef _URCU_H #define _URCU_H +/* + * urcu.h + * + * Userspace RCU header + * + * Copyright February 2009 - Mathieu Desnoyers + * + * Credits for Paul e. McKenney + * for inspiration coming from the Linux kernel RCU and rcu-preempt. + * + * The barrier, mb, rmb, wmb, atomic_inc, smp_read_barrier_depends, ACCESS_ONCE + * and rcu_dereference primitives come from the Linux kernel. + * + * Distributed under GPLv2 + */ + +#include +#include + /* The "volatile" is due to gcc bugs */ #define barrier() __asm__ __volatile__("": : :"memory") +#define likely(x) __builtin_expect(!!(x), 1) +#define unlikely(x) __builtin_expect(!!(x), 0) + /* x86 32/64 specific */ #define mb() asm volatile("mfence":::"memory") #define rmb() asm volatile("lfence":::"memory") #define wmb() asm volatile("sfence" ::: "memory") +/* Assume SMP machine, given we don't have this information */ +#define CONFIG_SMP 1 +#ifdef CONFIG_SMP +#define smp_mb() mb() +#define smp_rmb() rmb() +#define smp_wmb() wmb() +#else +#define smp_mb() barrier() +#define smp_rmb() barrier() +#define smp_wmb() barrier() +#endif -/* x86 32 */ static inline void atomic_inc(int *v) { asm volatile("lock; incl %0" : "+m" (*v)); } +#define xchg(ptr, v) \ + ((__typeof__(*(ptr)))__xchg((unsigned long)(v), (ptr), sizeof(*(ptr)))) + +struct __xchg_dummy { + unsigned long a[100]; +}; +#define __xg(x) ((struct __xchg_dummy *)(x)) + +/* + * Note: no "lock" prefix even on SMP: xchg always implies lock anyway + * Note 2: xchg has side effect, so that attribute volatile is necessary, + * but generally the primitive is invalid, *ptr is output argument. --ANK + */ +static inline unsigned long __xchg(unsigned long x, volatile void *ptr, + int size) +{ + switch (size) { + case 1: + asm volatile("xchgb %b0,%1" + : "=q" (x) + : "m" (*__xg(ptr)), "0" (x) + : "memory"); + break; + case 2: + asm volatile("xchgw %w0,%1" + : "=r" (x) + : "m" (*__xg(ptr)), "0" (x) + : "memory"); + break; + case 4: + asm volatile("xchgl %k0,%1" + : "=r" (x) + : "m" (*__xg(ptr)), "0" (x) + : "memory"); + break; + case 8: + asm volatile("xchgq %0,%1" + : "=r" (x) + : "m" (*__xg(ptr)), "0" (x) + : "memory"); + break; + } + return x; +} + /* Nop everywhere except on alpha. */ #define smp_read_barrier_depends() +/* + * Prevent the compiler from merging or refetching accesses. The compiler + * is also forbidden from reordering successive instances of ACCESS_ONCE(), + * but only when the compiler is aware of some particular ordering. One way + * to make the compiler aware of ordering is to put the two invocations of + * ACCESS_ONCE() in different C statements. + * + * This macro does absolutely -nothing- to prevent the CPU from reordering, + * merging, or refetching absolutely anything at any time. Its main intended + * use is to mediate communication between process-level code and irq/NMI + * handlers, all running on the same CPU. + */ +#define ACCESS_ONCE(x) (*(volatile typeof(x) *)&(x)) + +/** + * rcu_dereference - fetch an RCU-protected pointer in an + * RCU read-side critical section. This pointer may later + * be safely dereferenced. + * + * Inserts memory barriers on architectures that require them + * (currently only the Alpha), and, more importantly, documents + * exactly which pointers are protected by RCU. + */ + +#define rcu_dereference(p) ({ \ + typeof(p) _________p1 = ACCESS_ONCE(p); \ + smp_read_barrier_depends(); \ + (_________p1); \ + }) + #define SIGURCU SIGUSR1 -/* Global quiescent period parity */ -extern int urcu_qparity; +/* + * If a reader is really non-cooperative and refuses to commit its + * urcu_active_readers count to memory (there is no barrier in the reader + * per-se), kick it after a few loops waiting for it. + */ +#define KICK_READER_LOOPS 10000 + +#ifdef DEBUG_YIELD +#include +#include +#include +#include + +#define YIELD_READ (1 << 0) +#define YIELD_WRITE (1 << 1) + +/* Updates without DEBUG_FULL_MB are much slower. Account this in the delay */ +#ifdef DEBUG_FULL_MB +/* maximum sleep delay, in us */ +#define MAX_SLEEP 50 +#else +#define MAX_SLEEP 30000 +#endif + +extern unsigned int yield_active; +extern unsigned int __thread rand_yield; + +static inline void debug_yield_read(void) +{ + if (yield_active & YIELD_READ) + if (rand_r(&rand_yield) & 0x1) + usleep(rand_r(&rand_yield) % MAX_SLEEP); +} + +static inline void debug_yield_write(void) +{ + if (yield_active & YIELD_WRITE) + if (rand_r(&rand_yield) & 0x1) + usleep(rand_r(&rand_yield) % MAX_SLEEP); +} + +static inline void debug_yield_init(void) +{ + rand_yield = time(NULL) ^ pthread_self(); +} +#else +static inline void debug_yield_read(void) +{ +} + +static inline void debug_yield_write(void) +{ +} -extern int __thread urcu_active_readers[2]; +static inline void debug_yield_init(void) +{ + +} +#endif -static inline int get_urcu_qparity(void) +#ifdef DEBUG_FULL_MB +static inline void read_barrier() { - return urcu_qparity; + smp_mb(); } +#else +static inline void read_barrier() +{ + barrier(); +} +#endif + +/* + * The trick here is that RCU_GP_CTR_BIT must be a multiple of 8 so we can use a + * full 8-bits, 16-bits or 32-bits bitmask for the lower order bits. + */ +#define RCU_GP_COUNT (1UL << 0) +/* Use the amount of bits equal to half of the architecture long size */ +#define RCU_GP_CTR_BIT (1UL << (sizeof(long) << 2)) +#define RCU_GP_CTR_NEST_MASK (RCU_GP_CTR_BIT - 1) /* - * returns urcu_parity. + * Global quiescent period counter with low-order bits unused. + * Using a int rather than a char to eliminate false register dependencies + * causing stalls on some architectures. */ -static inline int rcu_read_lock(void) +extern long urcu_gp_ctr; + +extern long __thread urcu_active_readers; + +static inline int rcu_old_gp_ongoing(long *value) { - int urcu_parity = get_urcu_qparity(); - urcu_active_readers[urcu_parity]++; + long v; + + if (value == NULL) + return 0; + /* + * Make sure both tests below are done on the same version of *value + * to insure consistency. + */ + v = ACCESS_ONCE(*value); + return (v & RCU_GP_CTR_NEST_MASK) && + ((v ^ urcu_gp_ctr) & RCU_GP_CTR_BIT); +} + +static inline void rcu_read_lock(void) +{ + long tmp; + + tmp = urcu_active_readers; + /* urcu_gp_ctr = RCU_GP_COUNT | (~RCU_GP_CTR_BIT or RCU_GP_CTR_BIT) */ + /* The data dependency "read urcu_gp_ctr, write urcu_active_readers", + * serializes those two memory operations. */ + if (likely(!(tmp & RCU_GP_CTR_NEST_MASK))) + urcu_active_readers = urcu_gp_ctr; + else + urcu_active_readers = tmp + RCU_GP_COUNT; /* * Increment active readers count before accessing the pointer. * See force_mb_all_threads(). */ - barrier(); - return urcu_parity; + read_barrier(); } -static inline void rcu_read_unlock(int urcu_parity) +static inline void rcu_read_unlock(void) { - barrier(); + read_barrier(); /* * Finish using rcu before decrementing the pointer. * See force_mb_all_threads(). */ - urcu_active_readers[urcu_parity]--; + urcu_active_readers -= RCU_GP_COUNT; } -extern void *urcu_publish_content(void **ptr, void *new); +/** + * rcu_assign_pointer - assign (publicize) a pointer to a newly + * initialized structure that will be dereferenced by RCU read-side + * critical sections. Returns the value assigned. + * + * Inserts memory barriers on architectures that require them + * (pretty much all of them other than x86), and also prevents + * the compiler from reordering the code that initializes the + * structure after the pointer assignment. More importantly, this + * call documents which pointers will be dereferenced by RCU read-side + * code. + */ + +#define rcu_assign_pointer(p, v) \ + ({ \ + if (!__builtin_constant_p(v) || \ + ((v) != NULL)) \ + wmb(); \ + (p) = (v); \ + }) + +#define rcu_xchg_pointer(p, v) \ + ({ \ + if (!__builtin_constant_p(v) || \ + ((v) != NULL)) \ + wmb(); \ + xchg(p, v); \ + }) + +extern void synchronize_rcu(void); + +/* + * Exchanges the pointer and waits for quiescent state. + * The pointer returned can be freed. + */ +#define urcu_publish_content(p, v) \ + ({ \ + void *oldptr; \ + oldptr = rcu_xchg_pointer(p, v); \ + synchronize_rcu(); \ + oldptr; \ + }) /* * Reader thread registration. */ extern void urcu_register_thread(void); -extern void urcu_register_thread(void); +extern void urcu_unregister_thread(void); #endif /* _URCU_H */