blob: 204066b9f1e576398932246134a29a390e85d4a7 [file]
// Copyright 2026 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#ifndef SRC_MEMORY_SAMPLER_INSTRUMENTATION_ALLOCATION_TABLE_H_
#define SRC_MEMORY_SAMPLER_INSTRUMENTATION_ALLOCATION_TABLE_H_
#include <atomic>
#include <cstddef>
#include <cstdint>
#include <mutex>
#include <unordered_set>
namespace memory_sampler {
// Thread-safe set of live sampled allocation addresses.
//
// Most deallocations in a sampled process were never sampled on allocation.
// To avoid acquiring a global mutex on every unsampled `free()`, this table
// stores sampled addresses in a fixed-size lock-free set-associative table
// (`sizeof(uintptr_t) * kWaysPerBucket * kNumBuckets`), where each
// `kWaysPerBucket`-way bucket fits in a single 64-byte cache line.
//
// If a bucket fills beyond `kWaysPerBucket` concurrent live sampled
// allocations, additional addresses spill into a mutex-guarded overflow set.
// Per-bucket atomic counters track the number of overflow entries per bucket
// so unsampled deallocations that miss their bucket can skip acquiring the
// mutex whenever that specific bucket has no overflow entries.
class AllocationTable {
public:
AllocationTable() = default;
AllocationTable(const AllocationTable&) = delete;
AllocationTable& operator=(const AllocationTable&) = delete;
// Records `address` as a live sampled allocation. No-op if `address` is
// `nullptr`. `address` must not already be present in the table (guaranteed
// by Scudo invoking the deallocation hook before releasing a chunk for
// reuse).
void Insert(void* address);
// Removes `address` if it is currently recorded and returns `true`; returns
// `false` if `address` was not recorded.
bool TryRemove(void* address);
// Clears all recorded allocations from both the lock-free buckets and the
// overflow set. Any heap nodes in the overflow set are freed outside the
// internal lock.
void Clear();
private:
friend struct AllocationTableTestPeer;
static constexpr size_t kNumBuckets = 128;
static constexpr size_t kWaysPerBucket = 8;
static_assert((kNumBuckets & (kNumBuckets - 1)) == 0, "kNumBuckets must be a power of two");
struct alignas(64) Bucket {
std::atomic<uintptr_t> ways[kWaysPerBucket]{};
};
static_assert(sizeof(Bucket) == 64, "Bucket should fit in one cache line");
static constexpr size_t GetBucketIndex(uintptr_t addr) {
uint64_t x = addr;
x ^= x >> 33u;
x *= 0xff51afd7ed558ccdULL;
x ^= x >> 33u;
return static_cast<size_t>(x & (kNumBuckets - 1));
}
Bucket buckets_[kNumBuckets]{};
// Fallback storage for addresses whose target bucket was full at insertion
// time. `overflow_allocations_` is guarded by `lock_`, and
// `overflow_counts_[i]` tracks the number of entries in
// `overflow_allocations_` that hash to bucket `i` (updated under `lock_` with
// release ordering and read with acquire ordering) so `TryRemove` can skip
// acquiring `lock_` whenever its target bucket has no overflow entries.
std::atomic<uint32_t> overflow_counts_[kNumBuckets]{};
std::mutex lock_;
std::unordered_set<void*> overflow_allocations_;
};
} // namespace memory_sampler
#endif // SRC_MEMORY_SAMPLER_INSTRUMENTATION_ALLOCATION_TABLE_H_