Home | History | Annotate | Download | only in sanitizer_common 
      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
     74