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 
18 namespace __sanitizer {
19 
20 class 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