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