Add a bump allocator.
This CL adds a simple allocator which will provide a chunk of memory of
the given size. It allocates out of slabs of memory.
Change-Id: I9acf59fac88cd6bef260b7ebae7d7b77fd939754
Reviewed-on: https://dawn-review.googlesource.com/c/dawn/+/127302
Reviewed-by: Ben Clayton <bclayton@google.com>
Kokoro: Kokoro <noreply+kokoro@google.com>
Commit-Queue: Dan Sinclair <dsinclair@chromium.org>
diff --git a/src/tint/BUILD.gn b/src/tint/BUILD.gn
index 1e084a2..5240dd2 100644
--- a/src/tint/BUILD.gn
+++ b/src/tint/BUILD.gn
@@ -222,6 +222,7 @@
"utils/bitcast.h",
"utils/bitset.h",
"utils/block_allocator.h",
+ "utils/bump_allocator.h",
"utils/compiler_macros.h",
"utils/concat.h",
"utils/crc32.h",
@@ -1588,6 +1589,7 @@
"utils/bitcast_test.cc",
"utils/bitset_test.cc",
"utils/block_allocator_test.cc",
+ "utils/bump_allocator_test.cc",
"utils/crc32_test.cc",
"utils/defer_test.cc",
"utils/enum_set_test.cc",
diff --git a/src/tint/CMakeLists.txt b/src/tint/CMakeLists.txt
index 4dd1c88..6c7acfb 100644
--- a/src/tint/CMakeLists.txt
+++ b/src/tint/CMakeLists.txt
@@ -517,6 +517,7 @@
utils/bitcast.h
utils/bitset.h
utils/block_allocator.h
+ utils/bump_allocator.h
utils/compiler_macros.h
utils/concat.h
utils/crc32.h
@@ -998,6 +999,7 @@
utils/bitcast_test.cc
utils/bitset_test.cc
utils/block_allocator_test.cc
+ utils/bump_allocator_test.cc
utils/crc32_test.cc
utils/defer_test.cc
utils/enum_set_test.cc
diff --git a/src/tint/utils/bump_allocator.h b/src/tint/utils/bump_allocator.h
new file mode 100644
index 0000000..302f924
--- /dev/null
+++ b/src/tint/utils/bump_allocator.h
@@ -0,0 +1,127 @@
+// Copyright 2023 The Tint Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef SRC_TINT_UTILS_BUMP_ALLOCATOR_H_
+#define SRC_TINT_UTILS_BUMP_ALLOCATOR_H_
+
+#include <array>
+#include <cstring>
+#include <utility>
+
+#include "src/tint/utils/bitcast.h"
+#include "src/tint/utils/math.h"
+
+namespace tint::utils {
+
+constexpr size_t kBlockSize = 64 * 1024;
+
+/// A allocator for chunks of memory. The memory is owned by the BumpAllocator. When the
+/// BumpAllocator is freed all of the allocated memory is freed.
+class BumpAllocator {
+ /// Block is linked list of memory blocks.
+ /// Blocks are allocated out of heap memory.
+ struct Block {
+ uint8_t data[kBlockSize];
+ Block* next;
+ };
+
+ public:
+ /// Constructor
+ BumpAllocator() = default;
+
+ /// Move constructor
+ /// @param rhs the BumpAllocator to move
+ BumpAllocator(BumpAllocator&& rhs) { std::swap(data, rhs.data); }
+
+ /// Move assignment operator
+ /// @param rhs the BumpAllocator to move
+ /// @return this BumpAllocator
+ BumpAllocator& operator=(BumpAllocator&& rhs) {
+ if (this != &rhs) {
+ Reset();
+ std::swap(data, rhs.data);
+ }
+ return *this;
+ }
+
+ /// Destructor
+ ~BumpAllocator() { Reset(); }
+
+ /// Allocates @p size_in_bytes from the current block, or from a newly allocated block if the
+ /// current block is full.
+ /// @param size_in_bytes the number of bytes to allocate
+ /// @returns the pointer to the allocated memory or |nullptr| if the memory can not be allocated
+ char* Allocate(size_t size_in_bytes) {
+ auto& block = data.block;
+ if (block.current_offset + size_in_bytes > kBlockSize) {
+ // Allocate a new block from the heap
+ auto* prev_block = block.current;
+ block.current = new Block;
+ if (!block.current) {
+ return nullptr; // out of memory
+ }
+ block.current->next = nullptr;
+ block.current_offset = 0;
+ if (prev_block) {
+ prev_block->next = block.current;
+ } else {
+ block.root = block.current;
+ }
+ }
+
+ auto* base = &block.current->data[0];
+ auto* ptr = reinterpret_cast<char*>(base + block.current_offset);
+ block.current_offset += size_in_bytes;
+ data.count++;
+ return ptr;
+ }
+
+ /// Frees all allocations from the allocator.
+ void Reset() {
+ auto* block = data.block.root;
+ while (block != nullptr) {
+ auto* next = block->next;
+ delete block;
+ block = next;
+ }
+ data = {};
+ }
+
+ /// @returns the total number of allocations
+ size_t Count() const { return data.count; }
+
+ private:
+ BumpAllocator(const BumpAllocator&) = delete;
+ BumpAllocator& operator=(const BumpAllocator&) = delete;
+
+ struct {
+ struct {
+ /// The root block of the block linked list
+ Block* root = nullptr;
+ /// The current (end) block of the blocked linked list.
+ /// New allocations come from this block
+ Block* current = nullptr;
+ /// The byte offset in #current for the next allocation.
+ /// Initialized with kBlockSize so that the first allocation triggers a block
+ /// allocation.
+ size_t current_offset = kBlockSize;
+ } block;
+
+ size_t count = 0;
+ } data;
+};
+
+} // namespace tint::utils
+
+#endif // SRC_TINT_UTILS_BUMP_ALLOCATOR_H_
diff --git a/src/tint/utils/bump_allocator_test.cc b/src/tint/utils/bump_allocator_test.cc
new file mode 100644
index 0000000..4f22455
--- /dev/null
+++ b/src/tint/utils/bump_allocator_test.cc
@@ -0,0 +1,49 @@
+// Copyright 2023 The Tint Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "src/tint/utils/bump_allocator.h"
+
+#include "gtest/gtest.h"
+
+namespace tint::utils {
+namespace {
+
+using BumpAllocatorTest = testing::Test;
+
+TEST_F(BumpAllocatorTest, Count) {
+ for (size_t n : {0u, 1u, 10u, 16u, 20u, 32u, 50u, 64u, 100u, 256u, 300u, 512u, 500u, 512u}) {
+ BumpAllocator allocator;
+ EXPECT_EQ(allocator.Count(), 0u);
+ for (size_t i = 0; i < n; i++) {
+ allocator.Allocate(5);
+ }
+ EXPECT_EQ(allocator.Count(), n);
+ }
+}
+
+TEST_F(BumpAllocatorTest, MoveConstruct) {
+ for (size_t n : {0u, 1u, 10u, 16u, 20u, 32u, 50u, 64u, 100u, 256u, 300u, 512u, 500u, 512u}) {
+ BumpAllocator allocator_a;
+ for (size_t i = 0; i < n; i++) {
+ allocator_a.Allocate(5);
+ }
+ EXPECT_EQ(allocator_a.Count(), n);
+
+ BumpAllocator allocator_b{std::move(allocator_a)};
+ EXPECT_EQ(allocator_b.Count(), n);
+ }
+}
+
+} // namespace
+} // namespace tint::utils
