[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/+/155840
Kokoro: Ben Clayton <bclayton@google.com>
Reviewed-by: Antonio Maiorano <amaiorano@google.com>
diff --git a/src/tint/symbol_table.cc b/src/tint/symbol_table.cc
index cdea0a4..66461a9 100644
--- a/src/tint/symbol_table.cc
+++ b/src/tint/symbol_table.cc
@@ -37,8 +37,10 @@
}
Symbol SymbolTable::RegisterInternal(std::string_view name) {
- char* name_mem = name_allocator_.Allocate(name.length() + 1);
+ char* name_mem = utils::Bitcast<char*>(name_allocator_.Allocate(name.length() + 1));
if (name_mem == nullptr) {
+ tint::diag::List diags;
+ TINT_ICE(Utils, diags) << "failed to allocate memory for symbol's string";
return Symbol();
}
diff --git a/src/tint/utils/bump_allocator.h b/src/tint/utils/bump_allocator.h
index 302f924..6f41c18 100644
--- a/src/tint/utils/bump_allocator.h
+++ b/src/tint/utils/bump_allocator.h
@@ -15,11 +15,14 @@
#ifndef SRC_TINT_UTILS_BUMP_ALLOCATOR_H_
#define SRC_TINT_UTILS_BUMP_ALLOCATOR_H_
+#include <algorithm>
#include <array>
+#include <cstddef>
#include <cstring>
#include <utility>
#include "src/tint/utils/bitcast.h"
+#include "src/tint/utils/compiler_macros.h"
#include "src/tint/utils/math.h"
namespace tint::utils {
@@ -29,14 +32,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 {
- /// 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 +67,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 +117,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/bump_allocator_test.cc b/src/tint/utils/bump_allocator_test.cc
index 4f22455..cd840fe 100644
--- a/src/tint/utils/bump_allocator_test.cc
+++ b/src/tint/utils/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;
