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