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