libsanitizer/sanitizer_common/sanitizer_lfstack.h

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