urcu.h

   1 #ifndef _URCU_H
   2 #define _URCU_H
   3
   4 /*
   5  * urcu.h
   6  *
   7  * Userspace RCU header
   8  *
   9  * Copyright February 2009 - Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
  10  *
  11  * Credits for Paul e. McKenney <paulmck@linux.vnet.ibm.com>
  12  * for inspiration coming from the Linux kernel RCU and rcu-preempt.
  13  *
  14  * The barrier, mb, rmb, wmb, atomic_inc, smp_read_barrier_depends, ACCESS_ONCE
  15  * and rcu_dereference primitives come from the Linux kernel.
  16  *
  17  * Distributed under GPLv2
  18  */
  19
  20 #define __USE_GNU
  21 #include <stdlib.h>
  22
  23 /* The "volatile" is due to gcc bugs */
  24 #define barrier() __asm__ __volatile__("": : :"memory")
  25
  26 /* x86 32/64 specific */
  27 #define mb()    asm volatile("mfence":::"memory")
  28 #define rmb()   asm volatile("lfence":::"memory")
  29 #define wmb()   asm volatile("sfence" ::: "memory")
  30
  31 static inline void atomic_inc(int *v)
  32 {
  33         asm volatile("lock; incl %0"
  34                      : "+m" (*v));
  35 }
  36
  37 #define xchg(ptr, v)                                                    \
  38         ((__typeof__(*(ptr)))__xchg((unsigned long)(v), (ptr), sizeof(*(ptr))))
  39
  40 struct __xchg_dummy {
  41         unsigned long a[100];
  42 };
  43 #define __xg(x) ((struct __xchg_dummy *)(x))
  44
  45 /*
  46  * Note: no "lock" prefix even on SMP: xchg always implies lock anyway
  47  * Note 2: xchg has side effect, so that attribute volatile is necessary,
  48  *        but generally the primitive is invalid, *ptr is output argument. --ANK
  49  */
  50 static inline unsigned long __xchg(unsigned long x, volatile void *ptr,
  51                                    int size)
  52 {
  53         switch (size) {
  54         case 1:
  55                 asm volatile("xchgb %b0,%1"
  56                              : "=q" (x)
  57                              : "m" (*__xg(ptr)), "0" (x)
  58                              : "memory");
  59                 break;
  60         case 2:
  61                 asm volatile("xchgw %w0,%1"
  62                              : "=r" (x)
  63                              : "m" (*__xg(ptr)), "0" (x)
  64                              : "memory");
  65                 break;
  66         case 4:
  67                 asm volatile("xchgl %0,%1"
  68                              : "=r" (x)
  69                              : "m" (*__xg(ptr)), "0" (x)
  70                              : "memory");
  71                 break;
  72         }
  73         return x;
  74 }
  75
  76 /* Nop everywhere except on alpha. */
  77 #define smp_read_barrier_depends()
  78
  79 /*
  80  * Prevent the compiler from merging or refetching accesses.  The compiler
  81  * is also forbidden from reordering successive instances of ACCESS_ONCE(),
  82  * but only when the compiler is aware of some particular ordering.  One way
  83  * to make the compiler aware of ordering is to put the two invocations of
  84  * ACCESS_ONCE() in different C statements.
  85  *
  86  * This macro does absolutely -nothing- to prevent the CPU from reordering,
  87  * merging, or refetching absolutely anything at any time.  Its main intended
  88  * use is to mediate communication between process-level code and irq/NMI
  89  * handlers, all running on the same CPU.
  90  */
  91 #define ACCESS_ONCE(x) (*(volatile typeof(x) *)&(x))
  92
  93 /**
  94  * rcu_dereference - fetch an RCU-protected pointer in an
  95  * RCU read-side critical section.  This pointer may later
  96  * be safely dereferenced.
  97  *
  98  * Inserts memory barriers on architectures that require them
  99  * (currently only the Alpha), and, more importantly, documents
 100  * exactly which pointers are protected by RCU.
 101  */
 102
 103 #define rcu_dereference(p)     ({ \
 104                                 typeof(p) _________p1 = ACCESS_ONCE(p); \
 105                                 smp_read_barrier_depends(); \
 106                                 (_________p1); \
 107                                 })
 108
 109 #define SIGURCU SIGUSR1
 110
 111 #ifdef DEBUG_YIELD
 112 #include <sched.h>
 113 #include <time.h>
 114 #include <pthread.h>
 115
 116 #define YIELD_READ      (1 << 0)
 117 #define YIELD_WRITE     (1 << 1)
 118
 119 extern unsigned int yield_active;
 120 extern unsigned int __thread rand_yield;
 121
 122 static inline void debug_yield_read(void)
 123 {
 124         if (yield_active & YIELD_READ)
 125                 if (rand_r(&rand_yield) & 0x1)
 126                         sched_yield();
 127 }
 128
 129 static inline void debug_yield_write(void)
 130 {
 131         if (yield_active & YIELD_WRITE)
 132                 if (rand_r(&rand_yield) & 0x1)
 133                         sched_yield();
 134 }
 135
 136 static inline void debug_yield_init(void)
 137 {
 138         rand_yield = time(NULL) ^ pthread_self();
 139 }
 140 #else
 141 static inline void debug_yield_read(void)
 142 {
 143 }
 144
 145 static inline void debug_yield_write(void)
 146 {
 147 }
 148
 149 static inline void debug_yield_init(void)
 150 {
 151
 152 }
 153 #endif
 154
 155 /*
 156  * Limiting the nesting level to 256 to keep instructions small in the read
 157  * fast-path.
 158  */
 159 #define RCU_GP_COUNT            (1U << 0)
 160 #define RCU_GP_CTR_BIT          (1U << 8)
 161 #define RCU_GP_CTR_NEST_MASK    (RCU_GP_CTR_BIT - 1)
 162
 163 /* Global quiescent period counter with low-order bits unused. */
 164 extern int urcu_gp_ctr;
 165
 166 extern int __thread urcu_active_readers;
 167
 168 static inline int rcu_old_gp_ongoing(int *value)
 169 {
 170         int v;
 171
 172         if (value == NULL)
 173                 return 0;
 174         debug_yield_write();
 175         v = ACCESS_ONCE(*value);
 176         debug_yield_write();
 177         return (v & RCU_GP_CTR_NEST_MASK) &&
 178                  ((v ^ ACCESS_ONCE(urcu_gp_ctr)) & RCU_GP_CTR_BIT);
 179 }
 180
 181 static inline void rcu_read_lock(void)
 182 {
 183         int tmp;
 184
 185         debug_yield_read();
 186         tmp = urcu_active_readers;
 187         debug_yield_read();
 188         if (!(tmp & RCU_GP_CTR_NEST_MASK))
 189                 urcu_active_readers = urcu_gp_ctr + RCU_GP_COUNT;
 190         else
 191                 urcu_active_readers = tmp + RCU_GP_COUNT;
 192         debug_yield_read();
 193         /*
 194          * Increment active readers count before accessing the pointer.
 195          * See force_mb_all_threads().
 196          */
 197         barrier();
 198         debug_yield_read();
 199 }
 200
 201 static inline void rcu_read_unlock(void)
 202 {
 203         debug_yield_read();
 204         barrier();
 205         debug_yield_read();
 206         /*
 207          * Finish using rcu before decrementing the pointer.
 208          * See force_mb_all_threads().
 209          */
 210         urcu_active_readers -= RCU_GP_COUNT;
 211         debug_yield_read();
 212 }
 213
 214 /**
 215  * rcu_assign_pointer - assign (publicize) a pointer to a newly
 216  * initialized structure that will be dereferenced by RCU read-side
 217  * critical sections.  Returns the value assigned.
 218  *
 219  * Inserts memory barriers on architectures that require them
 220  * (pretty much all of them other than x86), and also prevents
 221  * the compiler from reordering the code that initializes the
 222  * structure after the pointer assignment.  More importantly, this
 223  * call documents which pointers will be dereferenced by RCU read-side
 224  * code.
 225  */
 226
 227 #define rcu_assign_pointer(p, v) \
 228         ({ \
 229                 if (!__builtin_constant_p(v) || \
 230                     ((v) != NULL)) \
 231                         wmb(); \
 232                 (p) = (v); \
 233         })
 234
 235 #define rcu_xchg_pointer(p, v) \
 236         ({ \
 237                 if (!__builtin_constant_p(v) || \
 238                     ((v) != NULL)) \
 239                         wmb(); \
 240                 xchg(p, v); \
 241         })
 242
 243 extern void synchronize_rcu(void);
 244
 245 /*
 246  * Exchanges the pointer and waits for quiescent state.
 247  * The pointer returned can be freed.
 248  */
 249 #define urcu_publish_content(p, v) \
 250         ({ \
 251                 void *oldptr; \
 252                 debug_yield_write(); \
 253                 oldptr = rcu_xchg_pointer(p, v); \
 254                 synchronize_rcu(); \
 255                 oldptr; \
 256         })
 257
 258 /*
 259  * Reader thread registration.
 260  */
 261 extern void urcu_register_thread(void);
 262 extern void urcu_unregister_thread(void);
 263
 264 #endif /* _URCU_H */