[tint][utils] Add support for large allocations
From the BumpAllocator.
Bug: chromium:1491912
Change-Id: I632fea8de1451358aa24f8a8d05c07d7f6823d7d
Reviewed-on: https://dawn-review.googlesource.com/c/dawn/+/155826
Reviewed-by: Antonio Maiorano <amaiorano@google.com>
Kokoro: Ben Clayton <bclayton@google.com>
diff --git a/src/tint/utils/memory/BUILD.cmake b/src/tint/utils/memory/BUILD.cmake
index a29c41c..1b07cd1 100644
--- a/src/tint/utils/memory/BUILD.cmake
+++ b/src/tint/utils/memory/BUILD.cmake
@@ -33,6 +33,7 @@
)
tint_target_add_dependencies(tint_utils_memory lib
+ tint_utils_macros
tint_utils_math
)
@@ -47,6 +48,7 @@
)
tint_target_add_dependencies(tint_utils_memory_test test
+ tint_utils_macros
tint_utils_math
tint_utils_memory
)
diff --git a/src/tint/utils/memory/BUILD.gn b/src/tint/utils/memory/BUILD.gn
index 36728c7..f517e37 100644
--- a/src/tint/utils/memory/BUILD.gn
+++ b/src/tint/utils/memory/BUILD.gn
@@ -36,7 +36,10 @@
"bump_allocator.h",
"memory.cc",
]
- deps = [ "${tint_src_dir}/utils/math" ]
+ deps = [
+ "${tint_src_dir}/utils/macros",
+ "${tint_src_dir}/utils/math",
+ ]
}
if (tint_build_unittests) {
tint_unittests_source_set("unittests") {
@@ -48,6 +51,7 @@
]
deps = [
"${tint_src_dir}:gmock_and_gtest",
+ "${tint_src_dir}/utils/macros",
"${tint_src_dir}/utils/math",
"${tint_src_dir}/utils/memory",
]
diff --git a/src/tint/utils/memory/bump_allocator.h b/src/tint/utils/memory/bump_allocator.h
index 5d4f594..6775d05 100644
--- a/src/tint/utils/memory/bump_allocator.h
+++ b/src/tint/utils/memory/bump_allocator.h
@@ -15,10 +15,13 @@
#ifndef SRC_TINT_UTILS_MEMORY_BUMP_ALLOCATOR_H_
#define SRC_TINT_UTILS_MEMORY_BUMP_ALLOCATOR_H_
+#include <algorithm>
#include <array>
+#include <cstddef>
#include <cstring>
#include <utility>
+#include "src/tint/utils/macros/compiler.h"
#include "src/tint/utils/math/math.h"
#include "src/tint/utils/memory/bitcast.h"
@@ -27,16 +30,17 @@
/// 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 {
- static constexpr size_t kBlockSize = 64 * 1024;
-
- /// Block is linked list of memory blocks.
+ /// BlockHeader is linked list of memory blocks.
/// Blocks are allocated out of heap memory.
- struct Block {
- uint8_t data[kBlockSize];
- Block* next;
+ struct BlockHeader {
+ BlockHeader* next;
};
public:
+ /// The default size for a block's data. Allocations can be greater than this, but smaller
+ /// allocations will use this size.
+ static constexpr size_t kDefaultBlockDataSize = 64 * 1024;
+
/// Constructor
BumpAllocator() = default;
@@ -61,38 +65,43 @@
/// 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) {
+ /// @returns the pointer to the allocated memory or `nullptr` if the memory can not be allocated
+ std::byte* Allocate(size_t size_in_bytes) {
+ if (TINT_UNLIKELY(data.current_offset + size_in_bytes < size_in_bytes)) {
+ return nullptr; // integer overflow
+ }
+ if (data.current_offset + size_in_bytes > data.current_data_size) {
// Allocate a new block from the heap
- auto* prev_block = block.current;
- block.current = new Block;
- if (!block.current) {
+ auto* prev_block = data.current;
+ size_t data_size = std::max(size_in_bytes, kDefaultBlockDataSize);
+ data.current = Bitcast<BlockHeader*>(new (std::nothrow)
+ std::byte[sizeof(BlockHeader) + data_size]);
+ if (TINT_UNLIKELY(!data.current)) {
return nullptr; // out of memory
}
- block.current->next = nullptr;
- block.current_offset = 0;
+ data.current->next = nullptr;
+ data.current_data_size = data_size;
+ data.current_offset = 0;
if (prev_block) {
- prev_block->next = block.current;
+ prev_block->next = data.current;
} else {
- block.root = block.current;
+ data.root = data.current;
}
}
- auto* base = &block.current->data[0];
- auto* ptr = reinterpret_cast<char*>(base + block.current_offset);
- block.current_offset += size_in_bytes;
+ auto* base = Bitcast<std::byte*>(data.current) + sizeof(BlockHeader);
+ auto* ptr = base + data.current_offset;
+ data.current_offset += size_in_bytes;
data.count++;
return ptr;
}
/// Frees all allocations from the allocator.
void Reset() {
- auto* block = data.block.root;
+ auto* block = data.root;
while (block != nullptr) {
auto* next = block->next;
- delete block;
+ delete[] Bitcast<std::byte*>(block);
block = next;
}
data = {};
@@ -106,18 +115,16 @@
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;
-
+ /// The root block of the block linked list
+ BlockHeader* root = nullptr;
+ /// The current (end) block of the blocked linked list.
+ /// New allocations come from this block
+ BlockHeader* current = nullptr;
+ /// The byte offset in #current for the next allocation.
+ size_t current_offset = 0;
+ /// The size of the #current, excluding the header size
+ size_t current_data_size = 0;
+ /// Total number of allocations
size_t count = 0;
} data;
};
diff --git a/src/tint/utils/memory/bump_allocator_test.cc b/src/tint/utils/memory/bump_allocator_test.cc
index 4241699..c1cc22a 100644
--- a/src/tint/utils/memory/bump_allocator_test.cc
+++ b/src/tint/utils/memory/bump_allocator_test.cc
@@ -21,6 +21,31 @@
using BumpAllocatorTest = testing::Test;
+TEST_F(BumpAllocatorTest, AllocationSizes) {
+ BumpAllocator allocator;
+ for (size_t n : {1u, 0x10u, 0x100u, 0x1000u, 0x10000u, 0x100000u, //
+ 2u, 0x34u, 0x567u, 0x8912u, 0x34567u, 0x891234u}) {
+ auto ptr = allocator.Allocate(n);
+ memset(ptr, 0x42, n);
+ }
+}
+
+TEST_F(BumpAllocatorTest, AllocationSizesAroundBlockSize) {
+ for (size_t n : {
+ BumpAllocator::kDefaultBlockDataSize - sizeof(void*),
+ BumpAllocator::kDefaultBlockDataSize - 4,
+ BumpAllocator::kDefaultBlockDataSize - 1,
+ BumpAllocator::kDefaultBlockDataSize,
+ BumpAllocator::kDefaultBlockDataSize + 1,
+ BumpAllocator::kDefaultBlockDataSize + 4,
+ BumpAllocator::kDefaultBlockDataSize + sizeof(void*),
+ }) {
+ BumpAllocator allocator;
+ auto* ptr = allocator.Allocate(n);
+ memset(ptr, 0x42, n);
+ }
+}
+
TEST_F(BumpAllocatorTest, Count) {
for (size_t n : {0u, 1u, 10u, 16u, 20u, 32u, 50u, 64u, 100u, 256u, 300u, 512u, 500u, 512u}) {
BumpAllocator allocator;
diff --git a/src/tint/utils/symbol/symbol_table.cc b/src/tint/utils/symbol/symbol_table.cc
index f541b6a..c56c5c0 100644
--- a/src/tint/utils/symbol/symbol_table.cc
+++ b/src/tint/utils/symbol/symbol_table.cc
@@ -37,8 +37,9 @@
}
Symbol SymbolTable::RegisterInternal(std::string_view name) {
- char* name_mem = name_allocator_.Allocate(name.length() + 1);
+ char* name_mem = Bitcast<char*>(name_allocator_.Allocate(name.length() + 1));
if (name_mem == nullptr) {
+ TINT_ICE() << "failed to allocate memory for symbol's string";
return Symbol();
}
