libsanitizer/sanitizer_common/sanitizer_lfstack.h

   1 //===-- sanitizer_lfstack.h -=-----------------------------------*- C++ -*-===//
   2 //
   3 // This file is distributed under the University of Illinois Open Source
   4 // License. See LICENSE.TXT for details.
   5 //
   6 //===----------------------------------------------------------------------===//
   7 //
   8 // Lock-free stack.
   9 // Uses 32/17 bits as ABA-counter on 32/64-bit platforms.
  10 // The memory passed to Push() must not be ever munmap'ed.
  11 // The type T must contain T *next field.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef SANITIZER_LFSTACK_H
  16 #define SANITIZER_LFSTACK_H
  17
  18 #include "sanitizer_internal_defs.h"
  19 #include "sanitizer_common.h"
  20 #include "sanitizer_atomic.h"
  21
  22 namespace __sanitizer {
  23
  24 template<typename T>
  25 struct LFStack {
  26   void Clear() {
  27     atomic_store(&head_, 0, memory_order_relaxed);
  28   }
  29
  30   bool Empty() const {
  31     return (atomic_load(&head_, memory_order_relaxed) & kPtrMask) == 0;
  32   }
  33
  34   void Push(T *p) {
  35     u64 cmp = atomic_load(&head_, memory_order_relaxed);
  36     for (;;) {
  37       u64 cnt = (cmp & kCounterMask) + kCounterInc;
  38       u64 xch = (u64)(uptr)p | cnt;
  39       p->next = (T*)(uptr)(cmp & kPtrMask);
  40       if (atomic_compare_exchange_weak(&head_, &cmp, xch,
  41                                        memory_order_release))
  42         break;
  43     }
  44   }
  45
  46   T *Pop() {
  47     u64 cmp = atomic_load(&head_, memory_order_acquire);
  48     for (;;) {
  49       T *cur = (T*)(uptr)(cmp & kPtrMask);
  50       if (!cur)
  51         return nullptr;
  52       T *nxt = cur->next;
  53       u64 cnt = (cmp & kCounterMask);
  54       u64 xch = (u64)(uptr)nxt | cnt;
  55       if (atomic_compare_exchange_weak(&head_, &cmp, xch,
  56                                        memory_order_acquire))
  57         return cur;
  58     }
  59   }
  60
  61   // private:
  62   static const int kCounterBits = FIRST_32_SECOND_64(32, 17);
  63   static const u64 kPtrMask = ((u64)-1) >> kCounterBits;
  64   static const u64 kCounterMask = ~kPtrMask;
  65   static const u64 kCounterInc = kPtrMask + 1;
  66
  67   atomic_uint64_t head_;
  68 };
  69 } // namespace __sanitizer
  70
  71 #endif // SANITIZER_LFSTACK_H