lib/sanitizer_common/sanitizer_lfstack.h

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