| 1 |
//===-- sanitizer_stack_store.cpp -------------------------------*- 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 |
#include "sanitizer_stack_store.h" |
| 10 |
|
| 11 |
#include "sanitizer_atomic.h" |
| 12 |
#include "sanitizer_common.h" |
| 13 |
#include "sanitizer_internal_defs.h" |
| 14 |
#include "sanitizer_leb128.h" |
| 15 |
#include "sanitizer_lzw.h" |
| 16 |
#include "sanitizer_placement_new.h" |
| 17 |
#include "sanitizer_stacktrace.h" |
| 18 |
|
| 19 |
namespace __sanitizer { |
| 20 |
|
| 21 |
namespace { |
| 22 |
struct StackTraceHeader { |
| 23 |
static constexpr u32 kStackSizeBits = 8; |
| 24 |
|
| 25 |
u8 size; |
| 26 |
u8 tag; |
| 27 |
explicit StackTraceHeader(const StackTrace &trace) |
| 28 |
: size(Min<uptr>(trace.size, (1u << 8) - 1)), tag(trace.tag) { |
| 29 |
CHECK_EQ(trace.tag, static_cast<uptr>(tag)); |
| 30 |
} |
| 31 |
explicit StackTraceHeader(uptr h) |
| 32 |
: size(h & ((1 << kStackSizeBits) - 1)), tag(h >> kStackSizeBits) {} |
| 33 |
|
| 34 |
uptr ToUptr() const { |
| 35 |
return static_cast<uptr>(size) | (static_cast<uptr>(tag) << kStackSizeBits); |
| 36 |
} |
| 37 |
}; |
| 38 |
} // namespace |
| 39 |
|
| 40 |
StackStore::Id StackStore::Store(const StackTrace &trace, uptr *pack) { |
| 41 |
if (!trace.size && !trace.tag) |
| 42 |
return 0; |
| 43 |
StackTraceHeader h(trace); |
| 44 |
uptr idx = 0; |
| 45 |
*pack = 0; |
| 46 |
uptr *stack_trace = Alloc(h.size + 1, &idx, pack); |
| 47 |
// No more space. |
| 48 |
if (stack_trace == nullptr) |
| 49 |
return 0; |
| 50 |
*stack_trace = h.ToUptr(); |
| 51 |
internal_memcpy(stack_trace + 1, trace.trace, h.size * sizeof(uptr)); |
| 52 |
*pack += blocks_[GetBlockIdx(idx)].Stored(h.size + 1); |
| 53 |
return OffsetToId(idx); |
| 54 |
} |
| 55 |
|
| 56 |
StackTrace StackStore::Load(Id id) { |
| 57 |
if (!id) |
| 58 |
return {}; |
| 59 |
uptr idx = IdToOffset(id); |
| 60 |
uptr block_idx = GetBlockIdx(idx); |
| 61 |
CHECK_LT(block_idx, ARRAY_SIZE(blocks_)); |
| 62 |
const uptr *stack_trace = blocks_[block_idx].GetOrUnpack(this); |
| 63 |
if (!stack_trace) |
| 64 |
return {}; |
| 65 |
stack_trace += GetInBlockIdx(idx); |
| 66 |
StackTraceHeader h(*stack_trace); |
| 67 |
return StackTrace(stack_trace + 1, h.size, h.tag); |
| 68 |
} |
| 69 |
|
| 70 |
uptr StackStore::Allocated() const { |
| 71 |
return atomic_load_relaxed(&allocated_) + sizeof(*this); |
| 72 |
} |
| 73 |
|
| 74 |
uptr *StackStore::Alloc(uptr count, uptr *idx, uptr *pack) { |
| 75 |
for (;;) { |
| 76 |
// Optimisic lock-free allocation, essentially try to bump the |
| 77 |
// total_frames_. |
| 78 |
uptr start = atomic_fetch_add(&total_frames_, count, memory_order_relaxed); |
| 79 |
uptr block_idx = GetBlockIdx(start); |
| 80 |
uptr last_idx = GetBlockIdx(start + count - 1); |
| 81 |
if (LIKELY(block_idx == last_idx)) { |
| 82 |
// Fits into a single block. |
| 83 |
// No more available blocks. Indicate inability to allocate more memory. |
| 84 |
if (block_idx >= ARRAY_SIZE(blocks_)) |
| 85 |
return nullptr; |
| 86 |
*idx = start; |
| 87 |
return blocks_[block_idx].GetOrCreate(this) + GetInBlockIdx(start); |
| 88 |
} |
| 89 |
|
| 90 |
// Retry. We can't use range allocated in two different blocks. |
| 91 |
CHECK_LE(count, kBlockSizeFrames); |
| 92 |
uptr in_first = kBlockSizeFrames - GetInBlockIdx(start); |
| 93 |
// Mark tail/head of these blocks as "stored".to avoid waiting before we can |
| 94 |
// Pack(). |
| 95 |
*pack += blocks_[block_idx].Stored(in_first); |
| 96 |
*pack += blocks_[last_idx].Stored(count - in_first); |
| 97 |
} |
| 98 |
} |
| 99 |
|
| 100 |
void *StackStore::Map(uptr size, const char *mem_type) { |
| 101 |
atomic_fetch_add(&allocated_, size, memory_order_relaxed); |
| 102 |
return MmapNoReserveOrDie(size, mem_type); |
| 103 |
} |
| 104 |
|
| 105 |
void StackStore::Unmap(void *addr, uptr size) { |
| 106 |
atomic_fetch_sub(&allocated_, size, memory_order_relaxed); |
| 107 |
UnmapOrDie(addr, size); |
| 108 |
} |
| 109 |
|
| 110 |
uptr StackStore::Pack(Compression type) { |
| 111 |
uptr res = 0; |
| 112 |
for (BlockInfo &b : blocks_) res += b.Pack(type, this); |
| 113 |
return res; |
| 114 |
} |
| 115 |
|
| 116 |
void StackStore::LockAll() { |
| 117 |
for (BlockInfo &b : blocks_) b.Lock(); |
| 118 |
} |
| 119 |
|
| 120 |
void StackStore::UnlockAll() { |
| 121 |
for (BlockInfo &b : blocks_) b.Unlock(); |
| 122 |
} |
| 123 |
|
| 124 |
void StackStore::TestOnlyUnmap() { |
| 125 |
for (BlockInfo &b : blocks_) b.TestOnlyUnmap(this); |
| 126 |
internal_memset(this, 0, sizeof(*this)); |
| 127 |
} |
| 128 |
|
| 129 |
uptr *StackStore::BlockInfo::Get() const { |
| 130 |
// Idiomatic double-checked locking uses memory_order_acquire here. But |
| 131 |
// relaxed is fine for us, justification is similar to |
| 132 |
// TwoLevelMap::GetOrCreate. |
| 133 |
return reinterpret_cast<uptr *>(atomic_load_relaxed(&data_)); |
| 134 |
} |
| 135 |
|
| 136 |
uptr *StackStore::BlockInfo::Create(StackStore *store) { |
| 137 |
SpinMutexLock l(&mtx_); |
| 138 |
uptr *ptr = Get(); |
| 139 |
if (!ptr) { |
| 140 |
ptr = reinterpret_cast<uptr *>(store->Map(kBlockSizeBytes, "StackStore")); |
| 141 |
atomic_store(&data_, reinterpret_cast<uptr>(ptr), memory_order_release); |
| 142 |
} |
| 143 |
return ptr; |
| 144 |
} |
| 145 |
|
| 146 |
uptr *StackStore::BlockInfo::GetOrCreate(StackStore *store) { |
| 147 |
uptr *ptr = Get(); |
| 148 |
if (LIKELY(ptr)) |
| 149 |
return ptr; |
| 150 |
return Create(store); |
| 151 |
} |
| 152 |
|
| 153 |
class SLeb128Encoder { |
| 154 |
public: |
| 155 |
SLeb128Encoder(u8 *begin, u8 *end) : begin(begin), end(end) {} |
| 156 |
|
| 157 |
bool operator==(const SLeb128Encoder &other) const { |
| 158 |
return begin == other.begin; |
| 159 |
} |
| 160 |
|
| 161 |
bool operator!=(const SLeb128Encoder &other) const { |
| 162 |
return begin != other.begin; |
| 163 |
} |
| 164 |
|
| 165 |
SLeb128Encoder &operator=(uptr v) { |
| 166 |
sptr diff = v - previous; |
| 167 |
begin = EncodeSLEB128(diff, begin, end); |
| 168 |
previous = v; |
| 169 |
return *this; |
| 170 |
} |
| 171 |
SLeb128Encoder &operator*() { return *this; } |
| 172 |
SLeb128Encoder &operator++() { return *this; } |
| 173 |
|
| 174 |
u8 *base() const { return begin; } |
| 175 |
|
| 176 |
private: |
| 177 |
u8 *begin; |
| 178 |
u8 *end; |
| 179 |
uptr previous = 0; |
| 180 |
}; |
| 181 |
|
| 182 |
class SLeb128Decoder { |
| 183 |
public: |
| 184 |
SLeb128Decoder(const u8 *begin, const u8 *end) : begin(begin), end(end) {} |
| 185 |
|
| 186 |
bool operator==(const SLeb128Decoder &other) const { |
| 187 |
return begin == other.begin; |
| 188 |
} |
| 189 |
|
| 190 |
bool operator!=(const SLeb128Decoder &other) const { |
| 191 |
return begin != other.begin; |
| 192 |
} |
| 193 |
|
| 194 |
uptr operator*() { |
| 195 |
sptr diff; |
| 196 |
begin = DecodeSLEB128(begin, end, &diff); |
| 197 |
previous += diff; |
| 198 |
return previous; |
| 199 |
} |
| 200 |
SLeb128Decoder &operator++() { return *this; } |
| 201 |
|
| 202 |
SLeb128Decoder operator++(int) { return *this; } |
| 203 |
|
| 204 |
private: |
| 205 |
const u8 *begin; |
| 206 |
const u8 *end; |
| 207 |
uptr previous = 0; |
| 208 |
}; |
| 209 |
|
| 210 |
static u8 *CompressDelta(const uptr *from, const uptr *from_end, u8 *to, |
| 211 |
u8 *to_end) { |
| 212 |
SLeb128Encoder encoder(to, to_end); |
| 213 |
for (; from != from_end; ++from, ++encoder) *encoder = *from; |
| 214 |
return encoder.base(); |
| 215 |
} |
| 216 |
|
| 217 |
static uptr *UncompressDelta(const u8 *from, const u8 *from_end, uptr *to, |
| 218 |
uptr *to_end) { |
| 219 |
SLeb128Decoder decoder(from, from_end); |
| 220 |
SLeb128Decoder end(from_end, from_end); |
| 221 |
for (; decoder != end; ++to, ++decoder) *to = *decoder; |
| 222 |
CHECK_EQ(to, to_end); |
| 223 |
return to; |
| 224 |
} |
| 225 |
|
| 226 |
static u8 *CompressLzw(const uptr *from, const uptr *from_end, u8 *to, |
| 227 |
u8 *to_end) { |
| 228 |
SLeb128Encoder encoder(to, to_end); |
| 229 |
encoder = LzwEncode<uptr>(from, from_end, encoder); |
| 230 |
return encoder.base(); |
| 231 |
} |
| 232 |
|
| 233 |
static uptr *UncompressLzw(const u8 *from, const u8 *from_end, uptr *to, |
| 234 |
uptr *to_end) { |
| 235 |
SLeb128Decoder decoder(from, from_end); |
| 236 |
SLeb128Decoder end(from_end, from_end); |
| 237 |
to = LzwDecode<uptr>(decoder, end, to); |
| 238 |
CHECK_EQ(to, to_end); |
| 239 |
return to; |
| 240 |
} |
| 241 |
|
| 242 |
#if defined(_MSC_VER) && !defined(__clang__) |
| 243 |
# pragma warning(push) |
| 244 |
// Disable 'nonstandard extension used: zero-sized array in struct/union'. |
| 245 |
# pragma warning(disable : 4200) |
| 246 |
#endif |
| 247 |
namespace { |
| 248 |
struct PackedHeader { |
| 249 |
uptr size; |
| 250 |
StackStore::Compression type; |
| 251 |
u8 data[]; |
| 252 |
}; |
| 253 |
} // namespace |
| 254 |
#if defined(_MSC_VER) && !defined(__clang__) |
| 255 |
# pragma warning(pop) |
| 256 |
#endif |
| 257 |
|
| 258 |
uptr *StackStore::BlockInfo::GetOrUnpack(StackStore *store) { |
| 259 |
SpinMutexLock l(&mtx_); |
| 260 |
switch (state) { |
| 261 |
case State::Storing: |
| 262 |
state = State::Unpacked; |
| 263 |
FALLTHROUGH; |
| 264 |
case State::Unpacked: |
| 265 |
return Get(); |
| 266 |
case State::Packed: |
| 267 |
break; |
| 268 |
} |
| 269 |
|
| 270 |
u8 *ptr = reinterpret_cast<u8 *>(Get()); |
| 271 |
CHECK_NE(nullptr, ptr); |
| 272 |
const PackedHeader *header = reinterpret_cast<const PackedHeader *>(ptr); |
| 273 |
CHECK_LE(header->size, kBlockSizeBytes); |
| 274 |
CHECK_GE(header->size, sizeof(PackedHeader)); |
| 275 |
|
| 276 |
uptr packed_size_aligned = RoundUpTo(header->size, GetPageSizeCached()); |
| 277 |
|
| 278 |
uptr *unpacked = |
| 279 |
reinterpret_cast<uptr *>(store->Map(kBlockSizeBytes, "StackStoreUnpack")); |
| 280 |
|
| 281 |
uptr *unpacked_end; |
| 282 |
switch (header->type) { |
| 283 |
case Compression::Delta: |
| 284 |
unpacked_end = UncompressDelta(header->data, ptr + header->size, unpacked, |
| 285 |
unpacked + kBlockSizeFrames); |
| 286 |
break; |
| 287 |
case Compression::LZW: |
| 288 |
unpacked_end = UncompressLzw(header->data, ptr + header->size, unpacked, |
| 289 |
unpacked + kBlockSizeFrames); |
| 290 |
break; |
| 291 |
default: |
| 292 |
UNREACHABLE("Unexpected type"); |
| 293 |
break; |
| 294 |
} |
| 295 |
|
| 296 |
CHECK_EQ(kBlockSizeFrames, unpacked_end - unpacked); |
| 297 |
|
| 298 |
MprotectReadOnly(reinterpret_cast<uptr>(unpacked), kBlockSizeBytes); |
| 299 |
atomic_store(&data_, reinterpret_cast<uptr>(unpacked), memory_order_release); |
| 300 |
store->Unmap(ptr, packed_size_aligned); |
| 301 |
|
| 302 |
state = State::Unpacked; |
| 303 |
return Get(); |
| 304 |
} |
| 305 |
|
| 306 |
uptr StackStore::BlockInfo::Pack(Compression type, StackStore *store) { |
| 307 |
if (type == Compression::None) |
| 308 |
return 0; |
| 309 |
|
| 310 |
SpinMutexLock l(&mtx_); |
| 311 |
switch (state) { |
| 312 |
case State::Unpacked: |
| 313 |
case State::Packed: |
| 314 |
return 0; |
| 315 |
case State::Storing: |
| 316 |
break; |
| 317 |
} |
| 318 |
|
| 319 |
uptr *ptr = Get(); |
| 320 |
if (!ptr || !Stored(0)) |
| 321 |
return 0; |
| 322 |
|
| 323 |
u8 *packed = |
| 324 |
reinterpret_cast<u8 *>(store->Map(kBlockSizeBytes, "StackStorePack")); |
| 325 |
PackedHeader *header = reinterpret_cast<PackedHeader *>(packed); |
| 326 |
u8 *alloc_end = packed + kBlockSizeBytes; |
| 327 |
|
| 328 |
u8 *packed_end = nullptr; |
| 329 |
switch (type) { |
| 330 |
case Compression::Delta: |
| 331 |
packed_end = |
| 332 |
CompressDelta(ptr, ptr + kBlockSizeFrames, header->data, alloc_end); |
| 333 |
break; |
| 334 |
case Compression::LZW: |
| 335 |
packed_end = |
| 336 |
CompressLzw(ptr, ptr + kBlockSizeFrames, header->data, alloc_end); |
| 337 |
break; |
| 338 |
default: |
| 339 |
UNREACHABLE("Unexpected type"); |
| 340 |
break; |
| 341 |
} |
| 342 |
|
| 343 |
header->type = type; |
| 344 |
header->size = packed_end - packed; |
| 345 |
|
| 346 |
VPrintf(1, "Packed block of %zu KiB to %zu KiB\n", kBlockSizeBytes >> 10, |
| 347 |
header->size >> 10); |
| 348 |
|
| 349 |
if (kBlockSizeBytes - header->size < kBlockSizeBytes / 8) { |
| 350 |
VPrintf(1, "Undo and keep block unpacked\n"); |
| 351 |
MprotectReadOnly(reinterpret_cast<uptr>(ptr), kBlockSizeBytes); |
| 352 |
store->Unmap(packed, kBlockSizeBytes); |
| 353 |
state = State::Unpacked; |
| 354 |
return 0; |
| 355 |
} |
| 356 |
|
| 357 |
uptr packed_size_aligned = RoundUpTo(header->size, GetPageSizeCached()); |
| 358 |
store->Unmap(packed + packed_size_aligned, |
| 359 |
kBlockSizeBytes - packed_size_aligned); |
| 360 |
MprotectReadOnly(reinterpret_cast<uptr>(packed), packed_size_aligned); |
| 361 |
|
| 362 |
atomic_store(&data_, reinterpret_cast<uptr>(packed), memory_order_release); |
| 363 |
store->Unmap(ptr, kBlockSizeBytes); |
| 364 |
|
| 365 |
state = State::Packed; |
| 366 |
return kBlockSizeBytes - packed_size_aligned; |
| 367 |
} |
| 368 |
|
| 369 |
void StackStore::BlockInfo::TestOnlyUnmap(StackStore *store) { |
| 370 |
if (uptr *ptr = Get()) |
| 371 |
store->Unmap(ptr, kBlockSizeBytes); |
| 372 |
} |
| 373 |
|
| 374 |
bool StackStore::BlockInfo::Stored(uptr n) { |
| 375 |
return n + atomic_fetch_add(&stored_, n, memory_order_release) == |
| 376 |
kBlockSizeFrames; |
| 377 |
} |
| 378 |
|
| 379 |
bool StackStore::BlockInfo::IsPacked() const { |
| 380 |
SpinMutexLock l(&mtx_); |
| 381 |
return state == State::Packed; |
| 382 |
} |
| 383 |
|
| 384 |
} // namespace __sanitizer |