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