Adds an `AbidingObjectPool` utility in `quiche/common`. `AbidingObjectPool` is a cache-friendly, thread-local slab object pool that allocates contiguous spans of memory (slabs) and uses an intrusive free-list within unallocated slots for O(1) object reuse. A design doc discussing the architectural decisions is included, as well as microbenchmarks. From a sample run of the microbenchmarks, here are some observations: 1. Throughput Parity in Steady-State * In typical allocation-free cycles, `AbidingObjectPool` operates within **1–3ns** of TCMalloc's highly-optimized thread cache. 2. Superior Compaction & Batch Deallocation * During load surges and drains, `AbidingObjectPool` outperforms TCMalloc by >25% while providing complete physical memory reclamation down to the 1-slab spare cache. 3. Zero Heap Fragmentation * `AbidingObjectPool` completely isolates allocations into homogeneous power-of-two aligned slabs, eliminating the primary driver of TCMalloc Central Cache Freelist (CFL) span retention and cross-object fragmentation. Protected by new code, not yet used. PiperOrigin-RevId: 986738969
diff --git a/build/source_list.bzl b/build/source_list.bzl index 4ddf6e3..5a39141 100644 --- a/build/source_list.bzl +++ b/build/source_list.bzl
@@ -9,6 +9,7 @@ "quic/test_tools/send_algorithm_test_result.proto", ] quiche_core_hdrs = [ + "common/abiding_object_pool.h", "common/btree_scheduler.h", "common/bug_utils.h", "common/bug_utils_test_helper.h", @@ -1129,6 +1130,7 @@ "balsa/header_properties_test.cc", "balsa/simple_buffer_test.cc", "binary_http/binary_http_message_test.cc", + "common/abiding_object_pool_test.cc", "common/btree_scheduler_test.cc", "common/bug_utils_test.cc", "common/capsule_test.cc",
diff --git a/build/source_list.gni b/build/source_list.gni index ab2801d..db07e97 100644 --- a/build/source_list.gni +++ b/build/source_list.gni
@@ -9,6 +9,7 @@ "src/quiche/quic/test_tools/send_algorithm_test_result.proto", ] quiche_core_hdrs = [ + "src/quiche/common/abiding_object_pool.h", "src/quiche/common/btree_scheduler.h", "src/quiche/common/bug_utils.h", "src/quiche/common/bug_utils_test_helper.h", @@ -1131,6 +1132,7 @@ "src/quiche/balsa/header_properties_test.cc", "src/quiche/balsa/simple_buffer_test.cc", "src/quiche/binary_http/binary_http_message_test.cc", + "src/quiche/common/abiding_object_pool_test.cc", "src/quiche/common/btree_scheduler_test.cc", "src/quiche/common/bug_utils_test.cc", "src/quiche/common/capsule_test.cc",
diff --git a/build/source_list.json b/build/source_list.json index 7404e7a..f9e60cf 100644 --- a/build/source_list.json +++ b/build/source_list.json
@@ -8,6 +8,7 @@ "quiche/quic/test_tools/send_algorithm_test_result.proto" ], "quiche_core_hdrs": [ + "quiche/common/abiding_object_pool.h", "quiche/common/btree_scheduler.h", "quiche/common/bug_utils.h", "quiche/common/bug_utils_test_helper.h", @@ -1130,6 +1131,7 @@ "quiche/balsa/header_properties_test.cc", "quiche/balsa/simple_buffer_test.cc", "quiche/binary_http/binary_http_message_test.cc", + "quiche/common/abiding_object_pool_test.cc", "quiche/common/btree_scheduler_test.cc", "quiche/common/bug_utils_test.cc", "quiche/common/capsule_test.cc",
diff --git a/quiche/common/abiding_object_pool.h b/quiche/common/abiding_object_pool.h new file mode 100644 index 0000000..cc4ef5f --- /dev/null +++ b/quiche/common/abiding_object_pool.h
@@ -0,0 +1,345 @@ +// Copyright 2026 The Chromium 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 QUICHE_COMMON_ABIDING_OBJECT_POOL_H_ +#define QUICHE_COMMON_ABIDING_OBJECT_POOL_H_ + +#include <algorithm> +#include <cstddef> +#include <cstdint> +#include <memory> +#include <new> +#include <type_traits> +#include <utility> + +#include "absl/base/config.h" +#include "quiche/common/platform/api/quiche_export.h" +#include "quiche/common/platform/api/quiche_logging.h" + +#ifdef ABSL_HAVE_ADDRESS_SANITIZER +#include <sanitizer/asan_interface.h> +#endif + +namespace quiche { + +// A cache-friendly, thread-local slab object pool with automatic memory +// reclamation and compaction over time. +// +// Slabs are naturally power-of-two aligned for O(1) pointer-to-slab resolution. +// Allocations prioritize the most full non-full slab to concentrate object +// density, allowing emptier slabs to drain to zero and be released to the heap. +// Maintains 1 spare empty slab in reserve to prevent allocation hysteresis +// on slab boundaries. +template <typename T, size_t SlabSizeBytes = 64 * 1024> +class QUICHE_NO_EXPORT AbidingObjectPool { + static_assert((SlabSizeBytes & (SlabSizeBytes - 1)) == 0, + "Slab size must be a power of 2"); + + public: + struct Deleter { + AbidingObjectPool* pool = nullptr; + + template <typename U> + void operator()(U* ptr) const noexcept { + if (ptr == nullptr) { + return; + } + ptr->~U(); + QUICHE_DCHECK(pool != nullptr); + if (pool != nullptr) { + pool->Deallocate(static_cast<void*>(ptr)); + } + } + }; + + template <typename U = T> + using Ptr = std::unique_ptr<U, Deleter>; + + constexpr AbidingObjectPool() = default; + + explicit AbidingObjectPool(size_t initial_slabs) { + for (size_t i = 0; i < initial_slabs; ++i) { + Slab* slab = CreateSlab(); + PushFront(non_full_slabs_, slab); + } + } + + ~AbidingObjectPool() { + while (non_full_slabs_ != nullptr) { + Slab* slab = non_full_slabs_; + RemoveFromList(non_full_slabs_, slab); + DestroySlab(slab); + } + while (full_slabs_ != nullptr) { + Slab* slab = full_slabs_; + RemoveFromList(full_slabs_, slab); + DestroySlab(slab); + } + if (spare_empty_slab_ != nullptr) { + DestroySlab(spare_empty_slab_); + spare_empty_slab_ = nullptr; + } + } + + // Non-copyable and non-movable: Outstanding Ptr instances hold a raw pointer + // to `this` inside their Deleter, so the pool must remain pinned in memory. + AbidingObjectPool(const AbidingObjectPool&) = delete; + AbidingObjectPool& operator=(const AbidingObjectPool&) = delete; + AbidingObjectPool(AbidingObjectPool&&) = delete; + AbidingObjectPool& operator=(AbidingObjectPool&&) = delete; + + // Constructs an instance of Derived (defaults to T) using pooled memory. + template <typename Derived = T, typename... Args> + Ptr<Derived> Create(Args&&... args) { + static_assert(std::is_same_v<T, Derived> || std::is_base_of_v<T, Derived>, + "Derived must inherit from or be T"); + static_assert(sizeof(Derived) <= kSlotSize, + "Derived exceeds allocated slot size"); + static_assert(alignof(Derived) <= kAlignment, + "Derived exceeds alignment constraint"); + + void* slot = Allocate(); + Derived* object = ::new (slot) Derived(std::forward<Args>(args)...); + return Ptr<Derived>(object, Deleter{this}); + } + + size_t total_capacity() const noexcept { + return allocated_slabs_count_ * kSlotsPerSlab; + } + size_t allocated_slabs() const noexcept { return allocated_slabs_count_; } + size_t num_free_slots() const noexcept { return total_free_slots_; } + bool empty() const noexcept { return total_free_slots_ == total_capacity(); } + + private: + // Intrusive node overlaid on unallocated slot memory. + struct FreeNode { + // If non-nullptr, points to the next free slot within the Slab. + FreeNode* next; + }; + + struct Slab { + // Pointers to the next/previous elements in the doubly-linked list. + Slab* prev = nullptr; + Slab* next = nullptr; + // If non-nullptr, points to the first free slot within the Slab. + FreeNode* free_head = nullptr; + // The number of slots that have been handed out so far within this Slab. + size_t allocated_high_watermark = 0; + // The number of slots currently occupied by live objects. + size_t live_objects = 0; + }; + + // Compile-time assertions and layout constants. + + // Disallow small objects; it would be space-inefficient. + static_assert(sizeof(T) >= sizeof(FreeNode), + "Objects stored in AbidingObjectPool should be at least the " + "size of a pointer."); + // Allocations must be aligned at least with `FreeNode`. + static constexpr size_t kAlignment = std::max(alignof(T), alignof(FreeNode)); + // If the type to store is smaller than a pointer, this data structure will + // waste memory. + static constexpr size_t kRawSlotSize = sizeof(T); + // Pads slot size to preserve alignment across consecutive array elements. + static constexpr size_t kSlotSize = + (kRawSlotSize + kAlignment - 1) & ~(kAlignment - 1); + // The first slot is after the slab header. + static constexpr size_t kFirstSlotOffset = + (sizeof(Slab) + kAlignment - 1) & ~(kAlignment - 1); + static constexpr size_t kSlotsPerSlab = + (SlabSizeBytes > kFirstSlotOffset) + ? (SlabSizeBytes - kFirstSlotOffset) / kSlotSize + : 0; + + static_assert(kSlotsPerSlab > 0, "Slab size must fit at least one object"); + + // Helper methods. + + // Calculates the memory address for a given slot index in a given Slab. + static void* SlotAddress(Slab* slab, size_t index) { + auto* base = reinterpret_cast<std::byte*>(slab); + return static_cast<void*>(base + kFirstSlotOffset + (index * kSlotSize)); + } + + // Pushes a Slab on the front of a doubly-linked list. + static void PushFront(Slab*& head, Slab* slab) { + slab->prev = nullptr; + slab->next = head; + if (head != nullptr) { + head->prev = slab; + } + head = slab; + } + + // Removes a Slab from a doubly-linked list. + static void RemoveFromList(Slab*& head, Slab* slab) { + if (slab->prev != nullptr) { + slab->prev->next = slab->next; + } else { + head = slab->next; + } + if (slab->next != nullptr) { + slab->next->prev = slab->prev; + } + slab->prev = nullptr; + slab->next = nullptr; + } + + // Swaps a Slab in a doubly-linked list with the next element. + static void SwapWithNext(Slab*& head, Slab* a) { + Slab* b = a->next; + if (b == nullptr) { + return; + } + Slab* prev = a->prev; + Slab* next = b->next; + + if (prev != nullptr) { + prev->next = b; + } else { + head = b; + } + b->prev = prev; + + b->next = a; + a->prev = b; + + a->next = next; + if (next != nullptr) { + next->prev = a; + } + } + + // Returns the next available slot, allocating a new Slab if necessary. + void* Allocate() { + if (non_full_slabs_ == nullptr) { + Slab* slab = nullptr; + if (spare_empty_slab_ != nullptr) { + slab = spare_empty_slab_; + spare_empty_slab_ = nullptr; + } else { + slab = CreateSlab(); + } + PushFront(non_full_slabs_, slab); + } + Slab* slab = non_full_slabs_; + void* slot = nullptr; + + // 1. Reuse from intrusive freelist if available. + if (slab->free_head != nullptr) { + FreeNode* node = slab->free_head; + +#ifdef ABSL_HAVE_ADDRESS_SANITIZER + ASAN_UNPOISON_MEMORY_REGION(node, kSlotSize); +#endif + + slab->free_head = node->next; + slot = static_cast<void*>(node); + } else { + // 2. Bump-allocate from uninitialized slot range. + QUICHE_DCHECK(slab->allocated_high_watermark < kSlotsPerSlab); + slot = SlotAddress(slab, slab->allocated_high_watermark); + +#ifdef ABSL_HAVE_ADDRESS_SANITIZER + ASAN_UNPOISON_MEMORY_REGION(slot, kSlotSize); +#endif + + ++slab->allocated_high_watermark; + } + + ++slab->live_objects; + --total_free_slots_; + + // If slab reached capacity, move it to full_slabs_. + if (slab->live_objects == kSlotsPerSlab) { + RemoveFromList(non_full_slabs_, slab); + PushFront(full_slabs_, slab); + } + + return slot; + } + + // Deallocates a slot. May result in the owning Slab being freed. + void Deallocate(void* ptr) noexcept { + // The owning slab can be found with a simple bitmask operation. + Slab* slab = reinterpret_cast<Slab*>(reinterpret_cast<uintptr_t>(ptr) & + ~(SlabSizeBytes - 1)); + QUICHE_DCHECK(slab != nullptr); + + auto* node = static_cast<FreeNode*>(ptr); + node->next = slab->free_head; + slab->free_head = node; + +#ifdef ABSL_HAVE_ADDRESS_SANITIZER + ASAN_POISON_MEMORY_REGION(ptr, kSlotSize); +#endif + + const bool was_full = (slab->live_objects == kSlotsPerSlab); + --slab->live_objects; + ++total_free_slots_; + + if (slab->live_objects == 0) { + // Slab has no more live objects. + if (was_full) { + RemoveFromList(full_slabs_, slab); + } else { + RemoveFromList(non_full_slabs_, slab); + } + if (spare_empty_slab_ == nullptr) { + spare_empty_slab_ = slab; + } else { + DestroySlab(slab); + } + return; + } + + if (was_full) { + // Move from full_slabs_ to front of non_full_slabs_ (as the fullest + // partial slab). + RemoveFromList(full_slabs_, slab); + PushFront(non_full_slabs_, slab); + } else { + // Keep non_full_slabs_ ordered by descending live_objects. + while (slab->next != nullptr && + slab->live_objects < slab->next->live_objects) { + SwapWithNext(non_full_slabs_, slab); + } + } + } + + // Allocates memory for and initializes a Slab. + Slab* CreateSlab() { + void* memory = + ::operator new(SlabSizeBytes, std::align_val_t(SlabSizeBytes)); + Slab* slab = ::new (memory) Slab(); + +#ifdef ABSL_HAVE_ADDRESS_SANITIZER + ASAN_POISON_MEMORY_REGION( + reinterpret_cast<std::byte*>(memory) + kFirstSlotOffset, + SlabSizeBytes - kFirstSlotOffset); +#endif + + ++allocated_slabs_count_; + total_free_slots_ += kSlotsPerSlab; + return slab; + } + + // Deallocates memory for a given Slab. + void DestroySlab(Slab* slab) noexcept { + --allocated_slabs_count_; + total_free_slots_ -= kSlotsPerSlab; + slab->~Slab(); + ::operator delete(slab, std::align_val_t(SlabSizeBytes)); + } + + Slab* non_full_slabs_ = nullptr; + Slab* full_slabs_ = nullptr; + Slab* spare_empty_slab_ = nullptr; + size_t allocated_slabs_count_ = 0; + size_t total_free_slots_ = 0; +}; + +} // namespace quiche + +#endif // QUICHE_COMMON_ABIDING_OBJECT_POOL_H_
diff --git a/quiche/common/abiding_object_pool_test.cc b/quiche/common/abiding_object_pool_test.cc new file mode 100644 index 0000000..022bc9e --- /dev/null +++ b/quiche/common/abiding_object_pool_test.cc
@@ -0,0 +1,196 @@ +// Copyright 2026 The Chromium 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 "quiche/common/abiding_object_pool.h" + +#include <cstddef> +#include <cstdint> +#include <string> +#include <utility> +#include <vector> + +#include "quiche/common/platform/api/quiche_test.h" + +namespace quiche { +namespace test { +namespace { + +struct DestructionTracker { + int value; + int* destruction_count; + + DestructionTracker(int val, int* d_count) + : value(val), destruction_count(d_count) {} + + ~DestructionTracker() { + if (destruction_count != nullptr) { + ++(*destruction_count); + } + } +}; + +class Base { + public: + virtual ~Base() = default; + virtual std::string Name() const = 0; + + protected: + const char* name_ = nullptr; + int* destruction_count_ = nullptr; +}; + +class Derived : public Base { + public: + explicit Derived(const char* name, int* destruction_count = nullptr) { + name_ = name; + destruction_count_ = destruction_count; + } + + ~Derived() override { + if (destruction_count_ != nullptr) { + ++(*destruction_count_); + } + } + + std::string Name() const override { return name_ != nullptr ? name_ : ""; } +}; + +struct alignas(64) OveralignedStruct { + uint64_t a; + uint64_t b; +}; + +TEST(AbidingObjectPoolTest, BasicAllocationAndDestruction) { + AbidingObjectPool<DestructionTracker, 1024> pool; + EXPECT_TRUE(pool.empty()); + EXPECT_EQ(pool.allocated_slabs(), 0u); + EXPECT_EQ(pool.total_capacity(), 0u); + + int destructions = 0; + { + auto ptr = pool.Create(42, &destructions); + ASSERT_NE(ptr, nullptr); + EXPECT_EQ(ptr->value, 42); + EXPECT_FALSE(pool.empty()); + EXPECT_EQ(pool.allocated_slabs(), 1u); + EXPECT_GT(pool.total_capacity(), 0u); + EXPECT_EQ(destructions, 0); + } + + EXPECT_EQ(destructions, 1); + EXPECT_TRUE(pool.empty()); + // 1 spare empty slab is retained in reserve. + EXPECT_EQ(pool.allocated_slabs(), 1u); + EXPECT_EQ(pool.num_free_slots(), pool.total_capacity()); +} + +TEST(AbidingObjectPoolTest, FreelistReuse) { + AbidingObjectPool<int64_t, 256> pool; + void* first_address = nullptr; + + { + auto ptr = pool.Create(100); + first_address = static_cast<void*>(ptr.get()); + EXPECT_EQ(*ptr, 100); + } + + // The next allocation should reuse the most recently deallocated slot (LIFO). + { + auto ptr = pool.Create(200); + EXPECT_EQ(static_cast<void*>(ptr.get()), first_address); + EXPECT_EQ(*ptr, 200); + } +} + +TEST(AbidingObjectPoolTest, PolymorphicDerivedCreation) { + AbidingObjectPool<Base, 1024> pool; + int destructions = 0; + + { + AbidingObjectPool<Base, 1024>::Ptr<Derived> derived_ptr = + pool.Create<Derived>("quiche_test", &destructions); + ASSERT_NE(derived_ptr, nullptr); + EXPECT_EQ(derived_ptr->Name(), "quiche_test"); + EXPECT_EQ(destructions, 0); + } + + EXPECT_EQ(destructions, 1); +} + +TEST(AbidingObjectPoolTest, AutomaticSlabDrainingAndCompaction) { + constexpr size_t kSlabSize = 256; + AbidingObjectPool<int64_t, kSlabSize> pool; + + std::vector<AbidingObjectPool<int64_t, kSlabSize>::Ptr<int64_t>> objects; + + // Allocate enough objects to span multiple slabs (5 slabs at ~27 slots/slab). + for (int i = 0; i < 120; ++i) { + objects.push_back(pool.Create(i)); + } + + size_t peak_slabs = pool.allocated_slabs(); + EXPECT_GE(peak_slabs, 4u); + + // Free most objects, leaving 20 active (fits within 1 slab). + objects.resize(20); + + // Excess drained slabs are destroyed, leaving 1 active slab + 1 spare slab. + EXPECT_LT(pool.allocated_slabs(), peak_slabs); + EXPECT_EQ(pool.allocated_slabs(), 2u); + + // Free all remaining objects. + objects.clear(); + // Exactly 1 spare empty slab is retained in cache. + EXPECT_EQ(pool.allocated_slabs(), 1u); + EXPECT_TRUE(pool.empty()); + EXPECT_EQ(pool.num_free_slots(), pool.total_capacity()); +} + +TEST(AbidingObjectPoolTest, Preallocation) { + constexpr size_t kInitialSlabs = 3; + constexpr size_t kSlabSize = 512; + AbidingObjectPool<int64_t, kSlabSize> pool(kInitialSlabs); + + EXPECT_EQ(pool.allocated_slabs(), kInitialSlabs); + EXPECT_GT(pool.total_capacity(), 0u); + EXPECT_EQ(pool.num_free_slots(), pool.total_capacity()); + EXPECT_TRUE(pool.empty()); +} + +TEST(AbidingObjectPoolTest, MovePtrMaintainsDeleter) { + AbidingObjectPool<int64_t, 256> pool; + auto ptr1 = pool.Create(12345); + ASSERT_NE(ptr1, nullptr); + + auto ptr2 = std::move(ptr1); + EXPECT_EQ(ptr1, nullptr); + ASSERT_NE(ptr2, nullptr); + EXPECT_EQ(*ptr2, 12345); + EXPECT_FALSE(pool.empty()); + + ptr2.reset(); + EXPECT_TRUE(pool.empty()); + EXPECT_EQ(pool.allocated_slabs(), 1u); +} + +TEST(AbidingObjectPoolTest, OveralignedObject) { + AbidingObjectPool<OveralignedStruct, 1024> pool; + auto ptr = pool.Create(); + ASSERT_NE(ptr, nullptr); + + auto address = reinterpret_cast<uintptr_t>(ptr.get()); + EXPECT_EQ(address % alignof(OveralignedStruct), 0u); +} + +constinit thread_local AbidingObjectPool<int64_t, 256> kConstinitPool; + +TEST(AbidingObjectPoolTest, ConstinitThreadLocal) { + auto ptr = kConstinitPool.Create(42); + ASSERT_NE(ptr, nullptr); + EXPECT_EQ(*ptr, 42); +} + +} // namespace +} // namespace test +} // namespace quiche