blob: d93e2b7437e549ae378d8b40672216457c4afd29 [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.
#include <atomic>
#include <cstddef>
#include <cstdint>
#include <thread>
#include <vector>
#include <gtest/gtest.h>
#include <src/memory/sampler/instrumentation/allocation_table.h>
namespace memory_sampler {
struct AllocationTableTestPeer {
static constexpr size_t kNumBuckets = AllocationTable::kNumBuckets;
static constexpr size_t kWaysPerBucket = AllocationTable::kWaysPerBucket;
static size_t GetBucketIndex(void* address) {
return AllocationTable::GetBucketIndex(reinterpret_cast<uintptr_t>(address));
}
static size_t GetOverflowCount(const AllocationTable& table) {
size_t total = 0;
for (const auto& count : table.overflow_counts_) {
total += count.load(std::memory_order_relaxed);
}
return total;
}
static size_t GetBucketOverflowCount(const AllocationTable& table, size_t bucket_index) {
return table.overflow_counts_[bucket_index].load(std::memory_order_relaxed);
}
};
namespace {
// NOLINTNEXTLINE(performance-no-int-to-ptr)
void* const kTestAddress = reinterpret_cast<void*>(0x1000);
// NOLINTNEXTLINE(performance-no-int-to-ptr)
void* const kOtherAddress = reinterpret_cast<void*>(0x2000);
TEST(AllocationTableTest, InsertAndTryRemoveSingleAddress) {
AllocationTable table;
EXPECT_FALSE(table.TryRemove(kTestAddress));
table.Insert(kTestAddress);
EXPECT_FALSE(table.TryRemove(kOtherAddress));
EXPECT_TRUE(table.TryRemove(kTestAddress));
EXPECT_FALSE(table.TryRemove(kTestAddress));
}
TEST(AllocationTableTest, NullptrIsIgnored) {
AllocationTable table;
table.Insert(nullptr);
EXPECT_FALSE(table.TryRemove(nullptr));
EXPECT_EQ(AllocationTableTestPeer::GetOverflowCount(table), 0u);
}
TEST(AllocationTableTest, ReinsertAfterRemoveSucceeds) {
AllocationTable table;
table.Insert(kTestAddress);
EXPECT_TRUE(table.TryRemove(kTestAddress));
EXPECT_FALSE(table.TryRemove(kTestAddress));
table.Insert(kTestAddress);
EXPECT_TRUE(table.TryRemove(kTestAddress));
EXPECT_FALSE(table.TryRemove(kTestAddress));
}
TEST(AllocationTableTest, BucketOverflowSpillsAndRecovers) {
AllocationTable table;
constexpr size_t kOverflowEntries = 4;
constexpr size_t kTotalRecorded = AllocationTableTestPeer::kWaysPerBucket + kOverflowEntries;
const size_t target_bucket = AllocationTableTestPeer::GetBucketIndex(kTestAddress);
std::vector<void*> colliding_addresses;
void* unrecorded_colliding_address = nullptr;
for (uintptr_t candidate = 0x10000; colliding_addresses.size() < kTotalRecorded + 1;
candidate += 16) {
// NOLINTNEXTLINE(performance-no-int-to-ptr)
void* addr = reinterpret_cast<void*>(candidate);
if (AllocationTableTestPeer::GetBucketIndex(addr) == target_bucket) {
if (colliding_addresses.size() < kTotalRecorded) {
colliding_addresses.push_back(addr);
} else {
unrecorded_colliding_address = addr;
break;
}
}
}
ASSERT_EQ(colliding_addresses.size(), kTotalRecorded);
ASSERT_NE(unrecorded_colliding_address, nullptr);
// Fill the bucket ways without spilling into the overflow set.
for (size_t i = 0; i < AllocationTableTestPeer::kWaysPerBucket; ++i) {
table.Insert(colliding_addresses[i]);
}
EXPECT_EQ(AllocationTableTestPeer::GetOverflowCount(table), 0u);
// Additional colliding allocations spill into the overflow set.
for (size_t i = AllocationTableTestPeer::kWaysPerBucket; i < kTotalRecorded; ++i) {
table.Insert(colliding_addresses[i]);
}
EXPECT_EQ(AllocationTableTestPeer::GetOverflowCount(table), kOverflowEntries);
EXPECT_EQ(AllocationTableTestPeer::GetBucketOverflowCount(table, target_bucket),
kOverflowEntries);
EXPECT_EQ(AllocationTableTestPeer::GetBucketOverflowCount(
table, (target_bucket + 1) % AllocationTableTestPeer::kNumBuckets),
0u);
// Removing an unrecorded address in the same bucket returns false without altering state.
EXPECT_FALSE(table.TryRemove(unrecorded_colliding_address));
EXPECT_EQ(AllocationTableTestPeer::GetOverflowCount(table), kOverflowEntries);
// Removing all colliding addresses (both inline ways and overflow entries) succeeds once each.
for (void* addr : colliding_addresses) {
EXPECT_TRUE(table.TryRemove(addr));
EXPECT_FALSE(table.TryRemove(addr));
}
EXPECT_EQ(AllocationTableTestPeer::GetOverflowCount(table), 0u);
}
TEST(AllocationTableTest, ClearRemovesBucketAndOverflowEntries) {
AllocationTable table;
constexpr size_t kTotalRecorded = AllocationTableTestPeer::kWaysPerBucket + 3;
const size_t target_bucket = AllocationTableTestPeer::GetBucketIndex(kTestAddress);
std::vector<void*> colliding_addresses;
for (uintptr_t candidate = 0x10000; colliding_addresses.size() < kTotalRecorded;
candidate += 16) {
// NOLINTNEXTLINE(performance-no-int-to-ptr)
void* addr = reinterpret_cast<void*>(candidate);
if (AllocationTableTestPeer::GetBucketIndex(addr) == target_bucket) {
colliding_addresses.push_back(addr);
table.Insert(addr);
}
}
ASSERT_EQ(AllocationTableTestPeer::GetOverflowCount(table), 3u);
table.Clear();
EXPECT_EQ(AllocationTableTestPeer::GetOverflowCount(table), 0u);
for (void* addr : colliding_addresses) {
EXPECT_FALSE(table.TryRemove(addr));
}
}
TEST(AllocationTableTest, ConcurrentInsertAndTryRemove) {
AllocationTable table;
constexpr size_t kNumThreads = 8;
constexpr size_t kAddressesPerThread = 4;
constexpr size_t kIterations = 200;
constexpr size_t kTotalColliding = kNumThreads * (kAddressesPerThread + 1);
const size_t target_bucket = AllocationTableTestPeer::GetBucketIndex(kTestAddress);
std::vector<void*> colliding_addresses;
colliding_addresses.reserve(kTotalColliding);
for (uintptr_t candidate = 0x10000; colliding_addresses.size() < kTotalColliding;
candidate += 16) {
// NOLINTNEXTLINE(performance-no-int-to-ptr)
void* addr = reinterpret_cast<void*>(candidate);
if (AllocationTableTestPeer::GetBucketIndex(addr) == target_bucket) {
colliding_addresses.push_back(addr);
}
}
ASSERT_EQ(colliding_addresses.size(), kTotalColliding);
std::atomic<bool> start{false};
std::vector<std::thread> threads;
threads.reserve(kNumThreads);
for (size_t t = 0; t < kNumThreads; ++t) {
threads.emplace_back([&, t]() {
const size_t base = t * (kAddressesPerThread + 1);
void* const unrecorded = colliding_addresses[base + kAddressesPerThread];
while (!start.load(std::memory_order_acquire)) {
}
for (size_t iter = 0; iter < kIterations; ++iter) {
for (size_t i = 0; i < kAddressesPerThread; ++i) {
table.Insert(colliding_addresses[base + i]);
}
EXPECT_FALSE(table.TryRemove(unrecorded));
for (size_t i = 0; i < kAddressesPerThread; ++i) {
EXPECT_TRUE(table.TryRemove(colliding_addresses[base + i]));
EXPECT_FALSE(table.TryRemove(colliding_addresses[base + i]));
}
}
});
}
start.store(true, std::memory_order_release);
for (auto& thread : threads) {
thread.join();
}
EXPECT_EQ(AllocationTableTestPeer::GetOverflowCount(table), 0u);
for (void* addr : colliding_addresses) {
EXPECT_FALSE(table.TryRemove(addr));
}
}
} // namespace
} // namespace memory_sampler