1 //===-- sanitizer_stack_store.cpp -------------------------------*- 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 #include "sanitizer_stack_store.h"
10 
11 #include "sanitizer_atomic.h"
12 #include "sanitizer_common.h"
13 #include "sanitizer_stacktrace.h"
14 
15 namespace __sanitizer {
16 
17 namespace {
18 struct StackTraceHeader {
19   static constexpr u32 kStackSizeBits = 8;
20 
21   u8 size;
22   u8 tag;
23   explicit StackTraceHeader(const StackTrace &trace)
24       : size(Min<uptr>(trace.size, (1u << 8) - 1)), tag(trace.tag) {
25     CHECK_EQ(trace.tag, static_cast<uptr>(tag));
26   }
27   explicit StackTraceHeader(uptr h)
28       : size(h & ((1 << kStackSizeBits) - 1)), tag(h >> kStackSizeBits) {}
29 
30   uptr ToUptr() const {
31     return static_cast<uptr>(size) | (static_cast<uptr>(tag) << kStackSizeBits);
32   }
33 };
34 }  // namespace
35 
36 StackStore::Id StackStore::Store(const StackTrace &trace) {
37   if (!trace.size && !trace.tag)
38     return 0;
39   StackTraceHeader h(trace);
40   uptr *stack_trace = Alloc(h.size + 1);
41   *stack_trace = h.ToUptr();
42   internal_memcpy(stack_trace + 1, trace.trace, h.size * sizeof(uptr));
43   return reinterpret_cast<StackStore::Id>(stack_trace);
44 }
45 
46 StackTrace StackStore::Load(Id id) const {
47   if (!id)
48     return {};
49   const uptr *stack_trace = reinterpret_cast<const uptr *>(id);
50   StackTraceHeader h(*stack_trace);
51   return StackTrace(stack_trace + 1, h.size, h.tag);
52 }
53 
54 uptr StackStore::Allocated() const {
55   return RoundUpTo(atomic_load_relaxed(&total_frames_) * sizeof(uptr),
56                    GetPageSizeCached()) +
57          sizeof(*this);
58 }
59 
60 uptr *StackStore::Alloc(uptr count) {
61   for (;;) {
62     // Optimisic lock-free allocation, essentially try to bump the
63     // total_frames_.
64     uptr start = atomic_fetch_add(&total_frames_, count, memory_order_relaxed);
65     uptr block_idx = GetBlockIdx(start);
66     if (LIKELY(block_idx == GetBlockIdx(start + count - 1))) {
67       // Fits into the a single block.
68       CHECK_LT(block_idx, ARRAY_SIZE(blocks_));
69       return blocks_[block_idx].GetOrCreate() + GetInBlockIdx(start);
70     }
71 
72     // Retry. We can't use range allocated in two different blocks.
73   }
74 }
75 
76 void StackStore::TestOnlyUnmap() {
77   for (BlockInfo &b : blocks_) b.TestOnlyUnmap();
78   internal_memset(this, 0, sizeof(*this));
79 }
80 
81 uptr *StackStore::BlockInfo::Get() const {
82   // Idiomatic double-checked locking uses memory_order_acquire here. But
83   // relaxed is find for us, justification is similar to
84   // TwoLevelMap::GetOrCreate.
85   return reinterpret_cast<uptr *>(atomic_load_relaxed(&data_));
86 }
87 
88 uptr *StackStore::BlockInfo::Create() {
89   SpinMutexLock l(&mtx_);
90   uptr *ptr = Get();
91   if (!ptr) {
92     ptr = reinterpret_cast<uptr *>(
93         MmapNoReserveOrDie(kBlockSizeBytes, "StackStore"));
94     atomic_store(&data_, reinterpret_cast<uptr>(ptr), memory_order_release);
95   }
96   return ptr;
97 }
98 
99 uptr *StackStore::BlockInfo::GetOrCreate() {
100   uptr *ptr = Get();
101   if (LIKELY(ptr))
102     return ptr;
103   return Create();
104 }
105 
106 void StackStore::BlockInfo::TestOnlyUnmap() {
107   if (uptr *ptr = Get())
108     UnmapOrDie(ptr, StackStore::kBlockSizeBytes);
109 }
110 
111 }  // namespace __sanitizer
112