blob: c11df0ddfde438bd429cc39d7bcef795dc0cd63b [file] [log] [blame]
//===-- sanitizer_stack_store.cpp -------------------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
#include "sanitizer_stack_store.h"
#include "sanitizer_atomic.h"
#include "sanitizer_common.h"
#include "sanitizer_internal_defs.h"
#include "sanitizer_leb128.h"
#include "sanitizer_lzw.h"
#include "sanitizer_placement_new.h"
#include "sanitizer_stacktrace.h"
namespace __sanitizer {
namespace {
struct StackTraceHeader {
static constexpr u32 kStackSizeBits = 8;
u8 size;
u8 tag;
explicit StackTraceHeader(const StackTrace &trace)
: size(Min<uptr>(trace.size, (1u << 8) - 1)), tag(trace.tag) {
CHECK_EQ(trace.tag, static_cast<uptr>(tag));
}
explicit StackTraceHeader(uptr h)
: size(h & ((1 << kStackSizeBits) - 1)), tag(h >> kStackSizeBits) {}
uptr ToUptr() const {
return static_cast<uptr>(size) | (static_cast<uptr>(tag) << kStackSizeBits);
}
};
} // namespace
StackStore::Id StackStore::Store(const StackTrace &trace, uptr *pack) {
if (!trace.size && !trace.tag)
return 0;
StackTraceHeader h(trace);
uptr idx = 0;
*pack = 0;
uptr *stack_trace = Alloc(h.size + 1, &idx, pack);
// No more space.
if (stack_trace == nullptr)
return 0;
*stack_trace = h.ToUptr();
internal_memcpy(stack_trace + 1, trace.trace, h.size * sizeof(uptr));
*pack += blocks_[GetBlockIdx(idx)].Stored(h.size + 1);
return OffsetToId(idx);
}
StackTrace StackStore::Load(Id id) {
if (!id)
return {};
uptr idx = IdToOffset(id);
uptr block_idx = GetBlockIdx(idx);
CHECK_LT(block_idx, ARRAY_SIZE(blocks_));
const uptr *stack_trace = blocks_[block_idx].GetOrUnpack(this);
if (!stack_trace)
return {};
stack_trace += GetInBlockIdx(idx);
StackTraceHeader h(*stack_trace);
return StackTrace(stack_trace + 1, h.size, h.tag);
}
uptr StackStore::Allocated() const {
return atomic_load_relaxed(&allocated_) + sizeof(*this);
}
uptr *StackStore::Alloc(uptr count, uptr *idx, uptr *pack) {
for (;;) {
// Optimisic lock-free allocation, essentially try to bump the
// total_frames_.
uptr start = atomic_fetch_add(&total_frames_, count, memory_order_relaxed);
uptr block_idx = GetBlockIdx(start);
uptr last_idx = GetBlockIdx(start + count - 1);
if (LIKELY(block_idx == last_idx)) {
// Fits into a single block.
// No more available blocks. Indicate inability to allocate more memory.
if (block_idx >= ARRAY_SIZE(blocks_))
return nullptr;
*idx = start;
return blocks_[block_idx].GetOrCreate(this) + GetInBlockIdx(start);
}
// Retry. We can't use range allocated in two different blocks.
CHECK_LE(count, kBlockSizeFrames);
uptr in_first = kBlockSizeFrames - GetInBlockIdx(start);
// Mark tail/head of these blocks as "stored".to avoid waiting before we can
// Pack().
*pack += blocks_[block_idx].Stored(in_first);
*pack += blocks_[last_idx].Stored(count - in_first);
}
}
void *StackStore::Map(uptr size, const char *mem_type) {
atomic_fetch_add(&allocated_, size, memory_order_relaxed);
return MmapNoReserveOrDie(size, mem_type);
}
void StackStore::Unmap(void *addr, uptr size) {
atomic_fetch_sub(&allocated_, size, memory_order_relaxed);
UnmapOrDie(addr, size);
}
uptr StackStore::Pack(Compression type) {
uptr res = 0;
for (BlockInfo &b : blocks_) res += b.Pack(type, this);
return res;
}
void StackStore::LockAll() {
for (BlockInfo &b : blocks_) b.Lock();
}
void StackStore::UnlockAll() {
for (BlockInfo &b : blocks_) b.Unlock();
}
void StackStore::TestOnlyUnmap() {
for (BlockInfo &b : blocks_) b.TestOnlyUnmap(this);
internal_memset(this, 0, sizeof(*this));
}
uptr *StackStore::BlockInfo::Get() const {
// Idiomatic double-checked locking uses memory_order_acquire here. But
// relaxed is fine for us, justification is similar to
// TwoLevelMap::GetOrCreate.
return reinterpret_cast<uptr *>(atomic_load_relaxed(&data_));
}
uptr *StackStore::BlockInfo::Create(StackStore *store) {
SpinMutexLock l(&mtx_);
uptr *ptr = Get();
if (!ptr) {
ptr = reinterpret_cast<uptr *>(store->Map(kBlockSizeBytes, "StackStore"));
atomic_store(&data_, reinterpret_cast<uptr>(ptr), memory_order_release);
}
return ptr;
}
uptr *StackStore::BlockInfo::GetOrCreate(StackStore *store) {
uptr *ptr = Get();
if (LIKELY(ptr))
return ptr;
return Create(store);
}
class SLeb128Encoder {
public:
SLeb128Encoder(u8 *begin, u8 *end) : begin(begin), end(end) {}
bool operator==(const SLeb128Encoder &other) const {
return begin == other.begin;
}
bool operator!=(const SLeb128Encoder &other) const {
return begin != other.begin;
}
SLeb128Encoder &operator=(uptr v) {
sptr diff = v - previous;
begin = EncodeSLEB128(diff, begin, end);
previous = v;
return *this;
}
SLeb128Encoder &operator*() { return *this; }
SLeb128Encoder &operator++() { return *this; }
u8 *base() const { return begin; }
private:
u8 *begin;
u8 *end;
uptr previous = 0;
};
class SLeb128Decoder {
public:
SLeb128Decoder(const u8 *begin, const u8 *end) : begin(begin), end(end) {}
bool operator==(const SLeb128Decoder &other) const {
return begin == other.begin;
}
bool operator!=(const SLeb128Decoder &other) const {
return begin != other.begin;
}
uptr operator*() {
sptr diff;
begin = DecodeSLEB128(begin, end, &diff);
previous += diff;
return previous;
}
SLeb128Decoder &operator++() { return *this; }
SLeb128Decoder operator++(int) { return *this; }
private:
const u8 *begin;
const u8 *end;
uptr previous = 0;
};
static u8 *CompressDelta(const uptr *from, const uptr *from_end, u8 *to,
u8 *to_end) {
SLeb128Encoder encoder(to, to_end);
for (; from != from_end; ++from, ++encoder) *encoder = *from;
return encoder.base();
}
static uptr *UncompressDelta(const u8 *from, const u8 *from_end, uptr *to,
uptr *to_end) {
SLeb128Decoder decoder(from, from_end);
SLeb128Decoder end(from_end, from_end);
for (; decoder != end; ++to, ++decoder) *to = *decoder;
CHECK_EQ(to, to_end);
return to;
}
static u8 *CompressLzw(const uptr *from, const uptr *from_end, u8 *to,
u8 *to_end) {
SLeb128Encoder encoder(to, to_end);
encoder = LzwEncode<uptr>(from, from_end, encoder);
return encoder.base();
}
static uptr *UncompressLzw(const u8 *from, const u8 *from_end, uptr *to,
uptr *to_end) {
SLeb128Decoder decoder(from, from_end);
SLeb128Decoder end(from_end, from_end);
to = LzwDecode<uptr>(decoder, end, to);
CHECK_EQ(to, to_end);
return to;
}
#if defined(_MSC_VER) && !defined(__clang__)
# pragma warning(push)
// Disable 'nonstandard extension used: zero-sized array in struct/union'.
# pragma warning(disable : 4200)
#endif
namespace {
struct PackedHeader {
uptr size;
StackStore::Compression type;
u8 data[];
};
} // namespace
#if defined(_MSC_VER) && !defined(__clang__)
# pragma warning(pop)
#endif
uptr *StackStore::BlockInfo::GetOrUnpack(StackStore *store) {
SpinMutexLock l(&mtx_);
switch (state) {
case State::Storing:
state = State::Unpacked;
FALLTHROUGH;
case State::Unpacked:
return Get();
case State::Packed:
break;
}
u8 *ptr = reinterpret_cast<u8 *>(Get());
CHECK_NE(nullptr, ptr);
const PackedHeader *header = reinterpret_cast<const PackedHeader *>(ptr);
CHECK_LE(header->size, kBlockSizeBytes);
CHECK_GE(header->size, sizeof(PackedHeader));
uptr packed_size_aligned = RoundUpTo(header->size, GetPageSizeCached());
uptr *unpacked =
reinterpret_cast<uptr *>(store->Map(kBlockSizeBytes, "StackStoreUnpack"));
uptr *unpacked_end;
switch (header->type) {
case Compression::Delta:
unpacked_end = UncompressDelta(header->data, ptr + header->size, unpacked,
unpacked + kBlockSizeFrames);
break;
case Compression::LZW:
unpacked_end = UncompressLzw(header->data, ptr + header->size, unpacked,
unpacked + kBlockSizeFrames);
break;
default:
UNREACHABLE("Unexpected type");
break;
}
CHECK_EQ(kBlockSizeFrames, unpacked_end - unpacked);
MprotectReadOnly(reinterpret_cast<uptr>(unpacked), kBlockSizeBytes);
atomic_store(&data_, reinterpret_cast<uptr>(unpacked), memory_order_release);
store->Unmap(ptr, packed_size_aligned);
state = State::Unpacked;
return Get();
}
uptr StackStore::BlockInfo::Pack(Compression type, StackStore *store) {
if (type == Compression::None)
return 0;
SpinMutexLock l(&mtx_);
switch (state) {
case State::Unpacked:
case State::Packed:
return 0;
case State::Storing:
break;
}
uptr *ptr = Get();
if (!ptr || !Stored(0))
return 0;
u8 *packed =
reinterpret_cast<u8 *>(store->Map(kBlockSizeBytes, "StackStorePack"));
PackedHeader *header = reinterpret_cast<PackedHeader *>(packed);
u8 *alloc_end = packed + kBlockSizeBytes;
u8 *packed_end = nullptr;
switch (type) {
case Compression::Delta:
packed_end =
CompressDelta(ptr, ptr + kBlockSizeFrames, header->data, alloc_end);
break;
case Compression::LZW:
packed_end =
CompressLzw(ptr, ptr + kBlockSizeFrames, header->data, alloc_end);
break;
default:
UNREACHABLE("Unexpected type");
break;
}
header->type = type;
header->size = packed_end - packed;
VPrintf(1, "Packed block of %zu KiB to %zu KiB\n", kBlockSizeBytes >> 10,
header->size >> 10);
if (kBlockSizeBytes - header->size < kBlockSizeBytes / 8) {
VPrintf(1, "Undo and keep block unpacked\n");
MprotectReadOnly(reinterpret_cast<uptr>(ptr), kBlockSizeBytes);
store->Unmap(packed, kBlockSizeBytes);
state = State::Unpacked;
return 0;
}
uptr packed_size_aligned = RoundUpTo(header->size, GetPageSizeCached());
store->Unmap(packed + packed_size_aligned,
kBlockSizeBytes - packed_size_aligned);
MprotectReadOnly(reinterpret_cast<uptr>(packed), packed_size_aligned);
atomic_store(&data_, reinterpret_cast<uptr>(packed), memory_order_release);
store->Unmap(ptr, kBlockSizeBytes);
state = State::Packed;
return kBlockSizeBytes - packed_size_aligned;
}
void StackStore::BlockInfo::TestOnlyUnmap(StackStore *store) {
if (uptr *ptr = Get())
store->Unmap(ptr, kBlockSizeBytes);
}
bool StackStore::BlockInfo::Stored(uptr n) {
return n + atomic_fetch_add(&stored_, n, memory_order_release) ==
kBlockSizeFrames;
}
bool StackStore::BlockInfo::IsPacked() const {
SpinMutexLock l(&mtx_);
return state == State::Packed;
}
} // namespace __sanitizer