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