silo/rcu.h

   1 #ifndef _RCU_H_
   2 #define _RCU_H_
   3
   4 #include <stdint.h>
   5 #include <pthread.h>
   6
   7 #include <map>
   8 #include <vector>
   9 #include <list>
  10 #include <utility>
  11
  12 #include "allocator.h"
  13 #include "counter.h"
  14 #include "spinlock.h"
  15 #include "util.h"
  16 #include "ticker.h"
  17 #include "pxqueue.h"
  18
  19 class rcu {
  20   template <bool> friend class scoped_rcu_base;
  21 public:
  22   class sync;
  23   typedef uint64_t epoch_t;
  24
  25   typedef void (*deleter_t)(void *);
  26   struct delete_entry {
  27       void* ptr;
  28       intptr_t action;
  29
  30       inline delete_entry(void* ptr, size_t sz)
  31           : ptr(ptr), action(-sz) {
  32           INVARIANT(action < 0);
  33       }
  34       inline delete_entry(void* ptr, deleter_t fn)
  35           : ptr(ptr), action(reinterpret_cast<uintptr_t>(fn)) {
  36           INVARIANT(action > 0);
  37       }
  38       void run(rcu::sync& s) {
  39           if (action < 0)
  40               s.dealloc(ptr, -action);
  41           else
  42               (*reinterpret_cast<deleter_t>(action))(ptr);
  43       }
  44       bool operator==(const delete_entry& x) const {
  45           return ptr == x.ptr && action == x.action;
  46       }
  47       bool operator!=(const delete_entry& x) const {
  48           return !(*this == x);
  49       }
  50       bool operator<(const delete_entry& x) const {
  51           return ptr < x.ptr || (ptr == x.ptr && action < x.action);
  52       }
  53   };
  54   typedef basic_px_queue<delete_entry, 4096> px_queue;
  55
  56   template <typename T>
  57   static inline void
  58   deleter(void *p)
  59   {
  60     delete (T *) p;
  61   }
  62
  63   template <typename T>
  64   static inline void
  65   deleter_array(void *p)
  66   {
  67     delete [] (T *) p;
  68   }
  69
  70 #ifdef CHECK_INVARIANTS
  71   static const uint64_t EpochTimeMultiplier = 10; /* 10 * 1 ms */
  72 #else
  73   static const uint64_t EpochTimeMultiplier = 25; /* 25 * 40 ms */
  74 #endif
  75
  76   static_assert(EpochTimeMultiplier >= 1, "XX");
  77
  78   // legacy helpers
  79   static const uint64_t EpochTimeUsec = ticker::tick_us * EpochTimeMultiplier;
  80   static const uint64_t EpochTimeNsec = EpochTimeUsec * 1000;
  81
  82   static const size_t NQueueGroups = 32;
  83
  84   // all RCU threads interact w/ the RCU subsystem via
  85   // a sync struct
  86   //
  87   // this is also serving as a memory allocator for the time being
  88   class sync {
  89     friend class rcu;
  90     template <bool> friend class scoped_rcu_base;
  91   public:
  92     px_queue queue_;
  93     px_queue scratch_;
  94     unsigned depth_; // 0 indicates no rcu region
  95     unsigned last_reaped_epoch_;
  96 #ifdef ENABLE_EVENT_COUNTERS
  97     uint64_t last_reaped_timestamp_us_;
  98     uint64_t last_release_timestamp_us_;
  99 #endif
 100
 101   private:
 102     rcu *impl_;
 103
 104     // local memory allocator
 105     ssize_t pin_cpu_;
 106     void *arenas_[allocator::MAX_ARENAS];
 107     size_t deallocs_[allocator::MAX_ARENAS]; // keeps track of the number of
 108                                              // un-released deallocations
 109
 110   public:
 111
 112     sync(rcu *impl)
 113       : depth_(0)
 114       , last_reaped_epoch_(0)
 115 #ifdef ENABLE_EVENT_COUNTERS
 116       , last_reaped_timestamp_us_(0)
 117       , last_release_timestamp_us_(0)
 118 #endif
 119       , impl_(impl)
 120       , pin_cpu_(-1)
 121     {
 122       ALWAYS_ASSERT(((uintptr_t)this % CACHELINE_SIZE) == 0);
 123       queue_.alloc_freelist(NQueueGroups);
 124       scratch_.alloc_freelist(NQueueGroups);
 125       NDB_MEMSET(&arenas_[0], 0, sizeof(arenas_));
 126       NDB_MEMSET(&deallocs_[0], 0, sizeof(deallocs_));
 127     }
 128
 129     inline void
 130     set_pin_cpu(size_t cpu)
 131     {
 132       pin_cpu_ = cpu;
 133     }
 134
 135     inline ssize_t
 136     get_pin_cpu() const
 137     {
 138       return pin_cpu_;
 139     }
 140
 141     // allocate a block of memory of size sz. caller needs to remember
 142     // the size of the allocation when calling free
 143     void *alloc(size_t sz);
 144
 145     // allocates a block of memory of size sz, with the intention of never
 146     // free-ing it. is meant for reasonably large allocations (order of pages)
 147     void *alloc_static(size_t sz);
 148
 149     void dealloc(void *p, size_t sz);
 150     void dealloc_rcu(void *p, size_t sz);
 151
 152     // try to release local arenas back to the allocator based on some simple
 153     // thresholding heuristics-- is relative expensive operation.  returns true
 154     // if a release was actually performed, false otherwise
 155     bool try_release();
 156
 157     void do_cleanup();
 158
 159     inline unsigned depth() const { return depth_; }
 160
 161   private:
 162
 163     void do_release();
 164
 165     inline void
 166     ensure_arena(size_t arena)
 167     {
 168       if (likely(arenas_[arena]))
 169         return;
 170       INVARIANT(pin_cpu_ >= 0);
 171       arenas_[arena] = allocator::AllocateArenas(pin_cpu_, arena);
 172     }
 173   };
 174
 175   // thin forwarders
 176   inline void *
 177   alloc(size_t sz)
 178   {
 179     return mysync().alloc(sz);
 180   }
 181
 182   inline void *
 183   alloc_static(size_t sz)
 184   {
 185     return mysync().alloc_static(sz);
 186   }
 187
 188   // this releases memory back to the allocator subsystem
 189   // this should NOT be used to free objects!
 190   inline void
 191   dealloc(void *p, size_t sz)
 192   {
 193     return mysync().dealloc(p, sz);
 194   }
 195
 196   void dealloc_rcu(void *p, size_t sz);
 197
 198   inline bool
 199   try_release()
 200   {
 201     return mysync().try_release();
 202   }
 203
 204   inline void
 205   do_cleanup()
 206   {
 207     mysync().do_cleanup();
 208   }
 209
 210   void free_with_fn(void *p, deleter_t fn);
 211
 212   template <typename T>
 213   inline void
 214   free(T *p)
 215   {
 216     free_with_fn(p, deleter<T>);
 217   }
 218
 219   template <typename T>
 220   inline void
 221   free_array(T *p)
 222   {
 223     free_with_fn(p, deleter_array<T>);
 224   }
 225
 226   // the tick is in units of rcu ticks
 227   inline bool
 228   in_rcu_region(uint64_t &rcu_tick) const
 229   {
 230     const sync *s = syncs_.myview();
 231     if (unlikely(!s))
 232       return false;
 233     const bool is_guarded = ticker::s_instance.is_locally_guarded(rcu_tick);
 234     const bool has_depth = s->depth();
 235     if (has_depth && !is_guarded)
 236       INVARIANT(false);
 237     rcu_tick = to_rcu_ticks(rcu_tick);
 238     return has_depth;
 239   }
 240
 241   inline bool
 242   in_rcu_region() const
 243   {
 244     uint64_t rcu_tick;
 245     return in_rcu_region(rcu_tick);
 246   }
 247
 248   // all threads have moved at least to the cleaning tick, so any pointers <
 249   // the cleaning tick can be safely purged
 250   inline uint64_t
 251   cleaning_rcu_tick_exclusive() const
 252   {
 253     return to_rcu_ticks(ticker::s_instance.global_last_tick_exclusive());
 254   }
 255
 256   // pin the current thread to CPU.
 257   //
 258   // this CPU number corresponds to the ones exposed by
 259   // sched.h. note that we currently pin to the numa node
 260   // associated with the cpu. memory allocation, however, is
 261   // CPU-specific
 262   void pin_current_thread(size_t cpu);
 263
 264   void fault_region();
 265
 266   static rcu s_instance CACHE_ALIGNED; // system wide instance
 267
 268   static void Test();
 269
 270 private:
 271
 272   rcu(); // private ctor to enforce singleton
 273
 274   static inline uint64_t constexpr
 275   to_rcu_ticks(uint64_t ticks)
 276   {
 277     return ticks / EpochTimeMultiplier;
 278   }
 279
 280   inline sync &mysync() { return syncs_.my(this); }
 281
 282   percore_lazy<sync> syncs_;
 283 };
 284
 285 template <bool DoCleanup>
 286 class scoped_rcu_base {
 287 public:
 288
 289   // movable, but not copy-constructable
 290   scoped_rcu_base(scoped_rcu_base &&) = default;
 291   scoped_rcu_base(const scoped_rcu_base &) = delete;
 292   scoped_rcu_base &operator=(const scoped_rcu_base &) = delete;
 293
 294   scoped_rcu_base()
 295     : sync_(&rcu::s_instance.mysync()),
 296       guard_(ticker::s_instance)
 297   {
 298     sync_->depth_++;
 299   }
 300
 301   ~scoped_rcu_base()
 302   {
 303     INVARIANT(sync_->depth_);
 304     const unsigned new_depth = --sync_->depth_;
 305     guard_.destroy();
 306     if (new_depth || !DoCleanup)
 307       return;
 308     // out of RCU region now, check if we need to run cleaner
 309     sync_->do_cleanup();
 310   }
 311
 312   inline ticker::guard *
 313   guard()
 314   {
 315     return guard_.obj();
 316   }
 317
 318   inline rcu::sync *
 319   sync()
 320   {
 321     return sync_;
 322   }
 323
 324 private:
 325   rcu::sync *sync_;
 326   unmanaged<ticker::guard> guard_;
 327 };
 328
 329 typedef scoped_rcu_base<true> scoped_rcu_region;
 330
 331 class disabled_rcu_region {};
 332
 333 #endif /* _RCU_H_ */