diff options
author | Dmitry Vyukov <dvyukov@google.com> | 2013-01-14 08:23:34 +0000 |
---|---|---|
committer | Dmitry Vyukov <dvyukov@google.com> | 2013-01-14 08:23:34 +0000 |
commit | b48224c8d19cac76f2af1eba158b9ae26ed1608a (patch) | |
tree | 3becc249e254f2314835124783b9fed767361628 /lib/sanitizer_common/sanitizer_lfstack.h | |
parent | d164ed175a61529589938b3db3cab076a19acf67 (diff) |
asan/tsan: faster memory allocator
1. Increase size classes from 32k to 128k
2. Use lock-free stack in central cache
3. Use blocking mutex when allocate new memory with mmap
git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@172388 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/sanitizer_common/sanitizer_lfstack.h')
-rw-r--r-- | lib/sanitizer_common/sanitizer_lfstack.h | 73 |
1 files changed, 73 insertions, 0 deletions
diff --git a/lib/sanitizer_common/sanitizer_lfstack.h b/lib/sanitizer_common/sanitizer_lfstack.h new file mode 100644 index 000000000..6790879a1 --- /dev/null +++ b/lib/sanitizer_common/sanitizer_lfstack.h @@ -0,0 +1,73 @@ +//===-- sanitizer_lfstack.h -=-----------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Lock-free stack. +// Uses 32/17 bits as ABA-counter on 32/64-bit platforms. +// The memory passed to Push() must not be ever munmap'ed. +// The type T must contain T *next field. +// +//===----------------------------------------------------------------------===// + +#ifndef SANITIZER_LFSTACK_H +#define SANITIZER_LFSTACK_H + +#include "sanitizer_internal_defs.h" +#include "sanitizer_common.h" +#include "sanitizer_atomic.h" + +namespace __sanitizer { + +template<typename T> +struct LFStack { + void Clear() { + atomic_store(&head_, 0, memory_order_relaxed); + } + + bool Empty() const { + return (atomic_load(&head_, memory_order_relaxed) & kPtrMask) == 0; + } + + void Push(T *p) { + u64 cmp = atomic_load(&head_, memory_order_relaxed); + for (;;) { + u64 cnt = (cmp & kCounterBits) + kCounterInc; + u64 xch = (u64)(uptr)p | cnt; + p->next = (T*)(uptr)(cmp & kPtrMask); + if (atomic_compare_exchange_weak(&head_, &cmp, xch, + memory_order_release)) + break; + } + } + + T *Pop() { + u64 cmp = atomic_load(&head_, memory_order_acquire); + for (;;) { + T *cur = (T*)(uptr)(cmp & kPtrMask); + if (cur == 0) + return 0; + T *nxt = cur->next; + u64 cnt = (cmp & kCounterBits); + u64 xch = (u64)(uptr)nxt | cnt; + if (atomic_compare_exchange_weak(&head_, &cmp, xch, + memory_order_acquire)) + return cur; + } + } + + // private: + static const int kCounterBits = FIRST_32_SECOND_64(32, 17); + static const u64 kPtrMask = ((u64)-1) >> kCounterBits; + static const u64 kCounterMask = ~kPtrMask; + static const u64 kCounterInc = kPtrMask + 1; + + atomic_uint64_t head_; +}; +} + +#endif // #ifndef SANITIZER_LFSTACK_H |