1//===-- sanitizer_stack_store.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#ifndef SANITIZER_STACK_STORE_H
10#define SANITIZER_STACK_STORE_H
11
12#include "sanitizer_atomic.h"
13#include "sanitizer_common.h"
14#include "sanitizer_internal_defs.h"
15#include "sanitizer_mutex.h"
16#include "sanitizer_stacktrace.h"
17
18namespace __sanitizer {
19
20class StackStore {
21 static constexpr uptr kBlockSizeFrames = 0x100000;
22 static constexpr uptr kBlockCount = 0x1000;
23 static constexpr uptr kBlockSizeBytes = kBlockSizeFrames * sizeof(uptr);
24
25 public:
26 enum class Compression : u8 {
27 None = 0,
28 Delta,
29 LZW,
30 };
31
32 constexpr StackStore() = default;
33
34 using Id = u32; // Enough for 2^32 * sizeof(uptr) bytes of traces.
35 static_assert(u64(kBlockCount) * kBlockSizeFrames == 1ull << (sizeof(Id) * 8),
36 "");
37
38 Id Store(const StackTrace &trace,
39 uptr *pack /* number of blocks completed by this call */);
40 StackTrace Load(Id id);
41 uptr Allocated() const;
42
43 // Packs all blocks which don't expect any more writes. A block is going to be
44 // packed once. As soon trace from that block was requested, it will unpack
45 // and stay unpacked after that.
46 // Returns the number of released bytes.
47 uptr Pack(Compression type);
48
49 void LockAll();
50 void UnlockAll();
51
52 void TestOnlyUnmap();
53
54 private:
55 friend class StackStoreTest;
56 static constexpr uptr GetBlockIdx(uptr frame_idx) {
57 return frame_idx / kBlockSizeFrames;
58 }
59
60 static constexpr uptr GetInBlockIdx(uptr frame_idx) {
61 return frame_idx % kBlockSizeFrames;
62 }
63
64 static constexpr uptr IdToOffset(Id id) {
65 CHECK_NE(id, 0);
66 return id - 1; // Avoid zero as id.
67 }
68
69 static constexpr uptr OffsetToId(Id id) {
70 // This makes UINT32_MAX to 0 and it will be retrived as and empty stack.
71 // But this is not a problem as we will not be able to store anything after
72 // that anyway.
73 return id + 1; // Avoid zero as id.
74 }
75
76 uptr *Alloc(uptr count, uptr *idx, uptr *pack);
77
78 void *Map(uptr size, const char *mem_type);
79 void Unmap(void *addr, uptr size);
80
81 // Total number of allocated frames.
82 atomic_uintptr_t total_frames_ = {};
83
84 // Tracks total allocated memory in bytes.
85 atomic_uintptr_t allocated_ = {};
86
87 // Each block will hold pointer to exactly kBlockSizeFrames.
88 class BlockInfo {
89 atomic_uintptr_t data_;
90 // Counter to track store progress to know when we can Pack() the block.
91 atomic_uint32_t stored_;
92 // Protects alloc of new blocks.
93 mutable StaticSpinMutex mtx_;
94
95 enum class State : u8 {
96 Storing = 0,
97 Packed,
98 Unpacked,
99 };
100 State state SANITIZER_GUARDED_BY(mtx_);
101
102 uptr *Create(StackStore *store);
103
104 public:
105 uptr *Get() const;
106 uptr *GetOrCreate(StackStore *store);
107 uptr *GetOrUnpack(StackStore *store);
108 uptr Pack(Compression type, StackStore *store);
109 void TestOnlyUnmap(StackStore *store);
110 bool Stored(uptr n);
111 bool IsPacked() const;
112 void Lock() SANITIZER_NO_THREAD_SAFETY_ANALYSIS { mtx_.Lock(); }
113 void Unlock() SANITIZER_NO_THREAD_SAFETY_ANALYSIS { mtx_.Unlock(); }
114 };
115
116 BlockInfo blocks_[kBlockCount] = {};
117};
118
119} // namespace __sanitizer
120
121#endif // SANITIZER_STACK_STORE_H
122