Add SlabAllocator::DeleteEmptySlabs()
SlabAllocator never freed allocated memory until it was deleted
previously. This means for SlabAllocator that grew and then shrunk it
could be holding onto unnecessary memory. Add DeleteEmptySlabs() that
will delete any slabs with zero allocations in them. This will be called
from Device::ReduceMemoryUsage() as a follow up.
Bug: 399826580, 42242057
Change-Id: I0e4d8582ff9a5f440fa67950c595dc2c4a895a50
Reviewed-on: https://dawn-review.googlesource.com/c/dawn/+/228814
Reviewed-by: Corentin Wallez <cwallez@chromium.org>
Reviewed-by: Loko Kung <lokokung@google.com>
Commit-Queue: Kyle Charbonneau <kylechar@google.com>
diff --git a/src/dawn/common/SlabAllocator.cpp b/src/dawn/common/SlabAllocator.cpp
index f668f37..8f3489b 100644
--- a/src/dawn/common/SlabAllocator.cpp
+++ b/src/dawn/common/SlabAllocator.cpp
@@ -29,8 +29,8 @@
#include <algorithm>
#include <cstdlib>
-#include <limits>
#include <new>
+
#include "dawn/common/AlignedAlloc.h"
#include "dawn/common/Assert.h"
#include "dawn/common/Math.h"
@@ -69,9 +69,6 @@
// SlabAllocatorImpl
-SlabAllocatorImpl::Index SlabAllocatorImpl::kInvalidIndex =
- std::numeric_limits<SlabAllocatorImpl::Index>::max();
-
SlabAllocatorImpl::SlabAllocatorImpl(Index blocksPerSlab,
uint32_t objectSize,
uint32_t objectAlignment)
@@ -172,6 +169,41 @@
next = nullptr;
}
+void SlabAllocatorImpl::DeleteEmptySlabs() {
+ auto DeleteEmptyFromList = [](const SentinelSlab& sentinel) {
+ for (Slab* current = sentinel.next; current != nullptr;) {
+ if (current->blocksInUse == 0) {
+ Slab* next = current->next;
+
+ // Remove from list and then delete to avoid dangling pointers.
+ current->Splice();
+ char* allocation = current->allocation;
+ current->~Slab();
+ AlignedFree(allocation);
+
+ current = next;
+ } else {
+ current = current->next;
+ }
+ }
+ };
+ DeleteEmptyFromList(mRecycledSlabs);
+ DeleteEmptyFromList(mAvailableSlabs);
+}
+
+uint32_t SlabAllocatorImpl::CountAllocatedSlabsForTesting() const {
+ auto CountSlabs = [](const SentinelSlab& sentinel) {
+ int count = 0;
+ for (Slab* current = sentinel.next; current != nullptr;) {
+ ++count;
+ current = current->next;
+ }
+ return count;
+ };
+
+ return CountSlabs(mAvailableSlabs) + CountSlabs(mRecycledSlabs) + CountSlabs(mFullSlabs);
+}
+
void* SlabAllocatorImpl::Allocate() {
if (mAvailableSlabs.next == nullptr) {
GetNewSlab();
@@ -208,9 +240,6 @@
slab->Splice();
mRecycledSlabs.Prepend(slab);
}
-
- // TODO(crbug.com/dawn/825): Occasionally prune slabs if |blocksInUse == 0|.
- // Doing so eagerly hurts performance.
}
void SlabAllocatorImpl::GetNewSlab() {
diff --git a/src/dawn/common/SlabAllocator.h b/src/dawn/common/SlabAllocator.h
index 9196c10..978a674 100644
--- a/src/dawn/common/SlabAllocator.h
+++ b/src/dawn/common/SlabAllocator.h
@@ -29,6 +29,7 @@
#define SRC_DAWN_COMMON_SLABALLOCATOR_H_
#include <cstdint>
+#include <limits>
#include <type_traits>
#include <utility>
@@ -72,14 +73,22 @@
// free list.
class SlabAllocatorImpl {
public:
+ SlabAllocatorImpl(SlabAllocatorImpl&& rhs);
+
+ // Deletes any slabs that have zero allocations.
+ void DeleteEmptySlabs();
+
+ uint32_t CountAllocatedSlabsForTesting() const;
+
+ protected:
// Allocations host their current index and the index of the next free block.
// Because this is an index, and not a byte offset, it can be much smaller than a size_t.
// TODO(crbug.com/dawn/825): Is uint8_t sufficient?
using Index = uint16_t;
- SlabAllocatorImpl(SlabAllocatorImpl&& rhs);
+ // The maximum value is reserved to indicate the end of the list.
+ static constexpr Index kInvalidIndex = std::numeric_limits<Index>::max();
- protected:
// This is essentially a singly linked list using indices instead of pointers,
// so we store the index of "this" in |this->index|.
struct IndexLinkNode : PlacementAllocated {
@@ -88,6 +97,8 @@
const Index index; // The index of this block in the slab.
Index nextIndex; // The index of the next available block. kInvalidIndex, if none.
};
+ // The IndexLinkNode destructor is not invoked so it must be trivially destructible.
+ static_assert(std::is_trivially_destructible_v<IndexLinkNode>);
struct Slab : PlacementAllocated {
// A slab is placement-allocated into an aligned pointer from a separate allocation.
@@ -118,9 +129,6 @@
void Deallocate(void* ptr);
private:
- // The maximum value is reserved to indicate the end of the list.
- static Index kInvalidIndex;
-
// Get the IndexLinkNode |offset| slots away.
IndexLinkNode* OffsetFrom(IndexLinkNode* node, std::make_signed_t<Index> offset) const;
diff --git a/src/dawn/tests/unittests/SlabAllocatorTests.cpp b/src/dawn/tests/unittests/SlabAllocatorTests.cpp
index e4e43a9..5d49319 100644
--- a/src/dawn/tests/unittests/SlabAllocatorTests.cpp
+++ b/src/dawn/tests/unittests/SlabAllocatorTests.cpp
@@ -137,6 +137,62 @@
}
}
+// Test DeleteEmptySlabs() when all slabs are empty.
+TEST(SlabAllocatorTests, DeleteAllSlabs) {
+ SlabAllocator<Foo> allocator(5 * sizeof(Foo));
+
+ // Allocate a number of objects.
+ std::set<Foo*> objects;
+ for (int i = 0; i < 11; ++i) {
+ EXPECT_TRUE(objects.insert(allocator.Allocate(i)).second);
+ }
+ EXPECT_EQ(allocator.CountAllocatedSlabsForTesting(), 3u);
+
+ // Deallocate all of the objects.
+ for (Foo* object : objects) {
+ allocator.Deallocate(object);
+ }
+
+ // Allocate and deallocate one slab full of objects so both available and recycled lists are
+ // populated.
+ objects.clear();
+ for (int i = 0; i < 5; ++i) {
+ EXPECT_TRUE(objects.insert(allocator.Allocate(i)).second);
+ }
+ for (Foo* object : objects) {
+ allocator.Deallocate(object);
+ }
+ EXPECT_EQ(allocator.CountAllocatedSlabsForTesting(), 3u);
+
+ allocator.DeleteEmptySlabs();
+ EXPECT_EQ(allocator.CountAllocatedSlabsForTesting(), 0u);
+}
+
+// Test DeleteEmptySlabs() when one slab is empty and one slab has allocations.
+TEST(SlabAllocatorTests, DeleteSomeSlabs) {
+ SlabAllocator<Foo> allocator(5 * sizeof(Foo));
+
+ // Allocate a number of objects.
+ std::set<Foo*> objects;
+ for (int i = 0; i < 6; ++i) {
+ EXPECT_TRUE(objects.insert(allocator.Allocate(i)).second);
+ }
+
+ // Deallocate all of the objects.
+ for (Foo* object : objects) {
+ allocator.Deallocate(object);
+ }
+
+ // Allocate a new object so one slab still has an allocation.
+ Foo* object = allocator.Allocate(6);
+ EXPECT_EQ(allocator.CountAllocatedSlabsForTesting(), 2u);
+
+ allocator.DeleteEmptySlabs();
+ EXPECT_EQ(allocator.CountAllocatedSlabsForTesting(), 1u);
+
+ allocator.Deallocate(object);
+}
+
// Test many allocations and deallocations. Meant to catch corner cases with partially
// empty slabs.
TEST(SlabAllocatorTests, AllocateDeallocateMany) {
