silo/pxqueue.h

   1 #pragma once
   2
   3 #include <iterator>
   4 #include <string>
   5
   6 #include "counter.h"
   7 #include "macros.h"
   8 #include "util.h"
   9
  10 // abstract queue for RCU-like queues
  11
  12 // forward decl
  13 template <typename T, size_t N> struct basic_px_queue;
  14
  15 template <typename T, size_t N>
  16 struct basic_px_group {
  17   basic_px_group()
  18     : next_(nullptr), rcu_tick_(0)
  19   {
  20     static event_counter evt_px_group_creates(
  21         util::cxx_typename<T>::value() + std::string("_px_group_creates"));
  22     ++evt_px_group_creates;
  23   }
  24   ~basic_px_group()
  25   {
  26     static event_counter evt_px_group_deletes(
  27         util::cxx_typename<T>::value() + std::string("_px_group_deletes"));
  28     ++evt_px_group_deletes;
  29   }
  30
  31   // no copying/moving
  32   basic_px_group(const basic_px_group &) = delete;
  33   basic_px_group &operator=(const basic_px_group &) = delete;
  34   basic_px_group(basic_px_group &&) = delete;
  35
  36   static const size_t GroupSize = N;
  37   friend class basic_px_queue<T, N>;
  38
  39 private:
  40   basic_px_group *next_;
  41   typename util::vec<T, GroupSize>::type pxs_;
  42   uint64_t rcu_tick_; // all elements in pxs_ are from this tick,
  43                       // this number is only meaningful if pxs_ is
  44                       // not empty
  45 };
  46
  47 // not thread safe- should guard with lock for concurrent manipulation
  48 template <typename T, size_t N>
  49 struct basic_px_queue {
  50   basic_px_queue()
  51     : head_(nullptr), tail_(nullptr),
  52       freelist_head_(nullptr), freelist_tail_(nullptr),
  53       ngroups_(0) {}
  54
  55   typedef basic_px_group<T, N> px_group;
  56
  57   basic_px_queue(basic_px_queue &&) = default;
  58   basic_px_queue(const basic_px_queue &) = delete;
  59   basic_px_queue &operator=(const basic_px_queue &) = delete;
  60
  61   ~basic_px_queue()
  62   {
  63     reap_chain(head_);
  64     reap_chain(freelist_head_);
  65   }
  66
  67   void
  68   swap(basic_px_queue &other)
  69   {
  70     std::swap(head_, other.head_);
  71     std::swap(tail_, other.tail_);
  72     std::swap(freelist_head_, other.freelist_head_);
  73     std::swap(freelist_tail_, other.freelist_tail_);
  74     std::swap(ngroups_, other.ngroups_);
  75   }
  76
  77   template <typename PtrType, typename ObjType>
  78   class iterator_ : public std::iterator<std::forward_iterator_tag, ObjType> {
  79   public:
  80     inline iterator_() : px_(nullptr), i_() {}
  81     inline iterator_(PtrType *px) : px_(px), i_() {}
  82
  83     // allow iterator to assign to const_iterator
  84     template <typename P, typename O>
  85     inline iterator_(const iterator_<P, O> &o) : px_(o.px_), i_(o.i_) {}
  86
  87     inline ObjType &
  88     operator*() const
  89     {
  90       return px_->pxs_[i_];
  91     }
  92
  93     inline ObjType *
  94     operator->() const
  95     {
  96       return &px_->pxs_[i_];
  97     }
  98
  99     inline uint64_t
 100     tick() const
 101     {
 102       return px_->rcu_tick_;
 103     }
 104
 105     inline bool
 106     operator==(const iterator_ &o) const
 107     {
 108       return px_ == o.px_ && i_ == o.i_;
 109     }
 110
 111     inline bool
 112     operator!=(const iterator_ &o) const
 113     {
 114       return !operator==(o);
 115     }
 116
 117     inline iterator_ &
 118     operator++()
 119     {
 120       ++i_;
 121       if (i_ == px_->pxs_.size()) {
 122         px_ = px_->next_;
 123         i_ = 0;
 124       }
 125       return *this;
 126     }
 127
 128     inline iterator_
 129     operator++(int)
 130     {
 131       iterator_ cur = *this;
 132       ++(*this);
 133       return cur;
 134     }
 135
 136   private:
 137     PtrType *px_;
 138     size_t i_;
 139   };
 140
 141   typedef iterator_<px_group, T> iterator;
 142   typedef iterator_<const px_group, const T> const_iterator;
 143
 144   inline iterator begin() { return iterator(head_); }
 145   inline const_iterator begin() const { return iterator(head_); }
 146
 147   inline iterator end() { return iterator(nullptr); }
 148   inline const_iterator end() const { return iterator(nullptr); }
 149
 150   // enqueue t in epoch rcu_tick
 151   // assumption: rcu_ticks can only go up!
 152   void
 153   enqueue(const T &t, uint64_t rcu_tick)
 154   {
 155     INVARIANT(bool(head_) == bool(tail_));
 156     INVARIANT(bool(head_) == bool(ngroups_));
 157     INVARIANT(!tail_ || tail_->pxs_.size() <= px_group::GroupSize);
 158     INVARIANT(!tail_ || tail_->rcu_tick_ <= rcu_tick);
 159     px_group *g;
 160     if (unlikely(!tail_ ||
 161                  tail_->pxs_.size() == px_group::GroupSize ||
 162                  tail_->rcu_tick_ != rcu_tick)) {
 163       ensure_freelist();
 164       // pop off freelist
 165       g = freelist_head_;
 166       freelist_head_ = g->next_;
 167       if (g == freelist_tail_)
 168         freelist_tail_ = nullptr;
 169       g->next_ = nullptr;
 170       g->pxs_.clear();
 171       g->rcu_tick_ = rcu_tick;
 172       ngroups_++;
 173
 174       // adjust ptrs
 175       if (!head_) {
 176         head_ = tail_ = g;
 177       } else {
 178         tail_->next_ = g;
 179         tail_ = g;
 180       }
 181     } else {
 182       g = tail_;
 183     }
 184     INVARIANT(g->pxs_.size() < px_group::GroupSize);
 185     INVARIANT(g->rcu_tick_ == rcu_tick);
 186     INVARIANT(!g->next_);
 187     INVARIANT(tail_ == g);
 188     g->pxs_.emplace_back(t);
 189     sanity_check();
 190   }
 191
 192   void
 193   ensure_freelist()
 194   {
 195     INVARIANT(bool(freelist_head_) == bool(freelist_tail_));
 196     if (likely(freelist_head_))
 197       return;
 198     const size_t nalloc = 16;
 199     alloc_freelist(nalloc);
 200   }
 201
 202   inline bool
 203   empty() const
 204   {
 205     return !head_;
 206   }
 207
 208 #ifdef CHECK_INVARIANTS
 209   void
 210   sanity_check() const
 211   {
 212     INVARIANT(bool(head_) == bool(tail_));
 213     INVARIANT(!tail_ || ngroups_);
 214     INVARIANT(!tail_ || !tail_->next_);
 215     INVARIANT(bool(freelist_head_) == bool(freelist_tail_));
 216     INVARIANT(!freelist_tail_ || !freelist_tail_->next_);
 217     px_group *p = head_, *pprev = nullptr;
 218     size_t n = 0;
 219     uint64_t prev_tick = 0;
 220     while (p) {
 221       INVARIANT(p->pxs_.size());
 222       INVARIANT(p->pxs_.size() <= px_group::GroupSize);
 223       INVARIANT(prev_tick <= p->rcu_tick_);
 224       prev_tick = p->rcu_tick_;
 225       pprev = p;
 226       p = p->next_;
 227       n++;
 228     }
 229     INVARIANT(n == ngroups_);
 230     INVARIANT(!pprev || tail_ == pprev);
 231     p = freelist_head_;
 232     pprev = nullptr;
 233     while (p) {
 234       pprev = p;
 235       p = p->next_;
 236     }
 237     INVARIANT(!pprev || freelist_tail_ == pprev);
 238   }
 239 #else
 240   inline ALWAYS_INLINE void sanity_check() const {}
 241 #endif
 242
 243   // assumes this instance is EMPTY, accept from source
 244   // all entries <= e
 245   inline void
 246   empty_accept_from(basic_px_queue &source, uint64_t rcu_tick)
 247   {
 248     ALWAYS_ASSERT(empty());
 249     INVARIANT(this != &source);
 250     INVARIANT(!tail_);
 251     px_group *p = source.head_, *pnext;
 252     while (p && p->rcu_tick_ <= rcu_tick) {
 253       pnext = p->next_;
 254       p->next_ = nullptr;
 255       if (!head_) {
 256         head_ = tail_ = p;
 257       } else {
 258         tail_->next_ = p;
 259         tail_ = p;
 260       }
 261       ngroups_++;
 262       source.ngroups_--;
 263       source.head_ = p = pnext;
 264       if (!source.head_)
 265         source.tail_ = nullptr;
 266     }
 267     sanity_check();
 268     source.sanity_check();
 269   }
 270
 271   // transfer *this* elements freelist to dest
 272   void
 273   transfer_freelist(basic_px_queue &dest, ssize_t n = -1)
 274   {
 275     if (!freelist_head_)
 276       return;
 277     if (n < 0) {
 278       freelist_tail_->next_ = dest.freelist_head_;
 279       if (!dest.freelist_tail_)
 280         dest.freelist_tail_ = freelist_tail_;
 281       dest.freelist_head_ = freelist_head_;
 282       freelist_head_ = freelist_tail_ = nullptr;
 283     } else {
 284       px_group *p = freelist_head_;
 285       size_t c = 0;
 286       while (p && c++ < static_cast<size_t>(n)) {
 287         px_group *tmp = p->next_;
 288         p->next_ = dest.freelist_head_;
 289         dest.freelist_head_ = p;
 290         if (!dest.freelist_tail_)
 291           dest.freelist_tail_ = p;
 292         if (p == freelist_tail_)
 293           freelist_tail_ = nullptr;
 294         p = tmp;
 295         freelist_head_ = p;
 296       }
 297     }
 298     sanity_check();
 299   }
 300
 301   void
 302   clear()
 303   {
 304     if (!head_)
 305       return;
 306     tail_->next_ = freelist_head_;
 307     if (!freelist_tail_)
 308       freelist_tail_ = tail_;
 309     freelist_head_ = head_;
 310     head_ = tail_ = nullptr;
 311     ngroups_ = 0;
 312   }
 313
 314   // adds n new groups to the freelist
 315   void
 316   alloc_freelist(size_t n)
 317   {
 318     for (size_t i = 0; i < n; i++) {
 319       px_group *p = new px_group;
 320       if (!freelist_tail_)
 321         freelist_tail_ = p;
 322       p->next_ = freelist_head_;
 323       freelist_head_ = p;
 324     }
 325   }
 326
 327   inline size_t get_ngroups() const { return ngroups_; }
 328
 329   inline bool
 330   get_latest_epoch(uint64_t &e) const
 331   {
 332     if (!tail_)
 333       return false;
 334     e = tail_->rcu_tick_;
 335     return true;
 336   }
 337
 338 private:
 339   void
 340   reap_chain(px_group *px)
 341   {
 342     while (px) {
 343       px_group *tmp = px->next_;
 344       delete px;
 345       px = tmp;
 346     }
 347   }
 348
 349   px_group *head_;
 350   px_group *tail_;
 351   px_group *freelist_head_;
 352   px_group *freelist_tail_;
 353   size_t ngroups_;
 354 };