diff options
| -rw-r--r-- | source/blender/blenlib/BLI_linear_allocator.hh | 173 | ||||
| -rw-r--r-- | tests/gtests/blenlib/BLI_linear_allocator_test.cc | 113 | ||||
| -rw-r--r-- | tests/gtests/blenlib/CMakeLists.txt | 1 |
3 files changed, 287 insertions, 0 deletions
diff --git a/source/blender/blenlib/BLI_linear_allocator.hh b/source/blender/blenlib/BLI_linear_allocator.hh new file mode 100644 index 00000000000..cebf878580c --- /dev/null +++ b/source/blender/blenlib/BLI_linear_allocator.hh @@ -0,0 +1,173 @@ +/* + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ + +/** \file + * \ingroup bli + * + * A linear allocator is the simplest form of an allocator. It never reuses any memory, and + * therefore does not need a deallocation method. It simply hands out consecutive buffers of + * memory. When the current buffer is full, it reallocates a new larger buffer and continues. + */ + +#ifndef __BLI_LINEAR_ALLOCATOR_HH__ +#define __BLI_LINEAR_ALLOCATOR_HH__ + +#include "BLI_string_ref.hh" +#include "BLI_utility_mixins.hh" +#include "BLI_vector.hh" + +namespace BLI { + +template<typename Allocator = GuardedAllocator> class LinearAllocator : NonCopyable, NonMovable { + private: + Allocator m_allocator; + Vector<void *> m_owned_buffers; + Vector<ArrayRef<char>> m_unused_borrowed_buffers; + + uintptr_t m_current_begin; + uintptr_t m_current_end; + uint m_next_min_alloc_size; + +#ifdef DEBUG + uint m_debug_allocated_amount = 0; +#endif + + public: + LinearAllocator() + { + m_current_begin = 0; + m_current_end = 0; + m_next_min_alloc_size = 64; + } + + ~LinearAllocator() + { + for (void *ptr : m_owned_buffers) { + m_allocator.deallocate(ptr); + } + } + + void provide_buffer(void *buffer, uint size) + { + m_unused_borrowed_buffers.append(ArrayRef<char>((char *)buffer, size)); + } + + template<uint Size, uint Alignment> + void provide_buffer(AlignedBuffer<Size, Alignment> &aligned_buffer) + { + this->provide_buffer(aligned_buffer.ptr(), Size); + } + + template<typename T> T *allocate() + { + return (T *)this->allocate(sizeof(T), alignof(T)); + } + + template<typename T> MutableArrayRef<T> allocate_array(uint length) + { + return MutableArrayRef<T>((T *)this->allocate(sizeof(T) * length), length); + } + + void *allocate(uint size, uint alignment = 4) + { + BLI_assert(alignment >= 1); + BLI_assert(is_power_of_2_i(alignment)); + +#ifdef DEBUG + m_debug_allocated_amount += size; +#endif + + uintptr_t alignment_mask = alignment - 1; + uintptr_t potential_allocation_begin = (m_current_begin + alignment_mask) & ~alignment_mask; + uintptr_t potential_allocation_end = potential_allocation_begin + size; + + if (potential_allocation_end <= m_current_end) { + m_current_begin = potential_allocation_end; + return (void *)potential_allocation_begin; + } + else { + this->allocate_new_buffer(size + alignment); + return this->allocate(size, alignment); + } + }; + + StringRefNull copy_string(StringRef str) + { + uint alloc_size = str.size() + 1; + char *buffer = (char *)this->allocate(alloc_size, 1); + str.copy(buffer, alloc_size); + return StringRefNull((const char *)buffer); + } + + template<typename T, typename... Args> T *construct(Args &&... args) + { + void *buffer = this->allocate(sizeof(T), alignof(T)); + T *value = new (buffer) T(std::forward<Args>(args)...); + return value; + } + + template<typename T, typename... Args> + ArrayRef<T *> construct_elements_and_pointer_array(uint n, Args &&... args) + { + void *pointer_buffer = this->allocate(n * sizeof(T *), alignof(T *)); + void *element_buffer = this->allocate(n * sizeof(T), alignof(T)); + + MutableArrayRef<T *> pointers((T **)pointer_buffer, n); + T *elements = (T *)element_buffer; + + for (uint i : IndexRange(n)) { + pointers[i] = elements + i; + } + for (uint i : IndexRange(n)) { + new (elements + i) T(std::forward<Args>(args)...); + } + + return pointers; + } + + template<typename T> MutableArrayRef<T> construct_array_copy(ArrayRef<T> source) + { + T *buffer = (T *)this->allocate(source.byte_size(), alignof(T)); + uninitialized_copy_n(source.begin(), source.size(), buffer); + return MutableArrayRef<T>(buffer, source.size()); + } + + private: + void allocate_new_buffer(uint min_allocation_size) + { + for (uint i : m_unused_borrowed_buffers.index_range()) { + ArrayRef<char> buffer = m_unused_borrowed_buffers[i]; + if (buffer.size() >= min_allocation_size) { + m_unused_borrowed_buffers.remove_and_reorder(i); + m_current_begin = (uintptr_t)buffer.begin(); + m_current_end = (uintptr_t)buffer.end(); + return; + } + } + + uint size_in_bytes = power_of_2_min_u(std::max(min_allocation_size, m_next_min_alloc_size)); + m_next_min_alloc_size = size_in_bytes * 2; + + void *buffer = m_allocator.allocate(size_in_bytes, __func__); + m_owned_buffers.append(buffer); + m_current_begin = (uintptr_t)buffer; + m_current_end = m_current_begin + size_in_bytes; + } +}; + +} // namespace BLI + +#endif /* __BLI_LINEAR_ALLOCATOR_HH__ */ diff --git a/tests/gtests/blenlib/BLI_linear_allocator_test.cc b/tests/gtests/blenlib/BLI_linear_allocator_test.cc new file mode 100644 index 00000000000..0c67d1e76c9 --- /dev/null +++ b/tests/gtests/blenlib/BLI_linear_allocator_test.cc @@ -0,0 +1,113 @@ +#include "BLI_linear_allocator.hh" +#include "testing/testing.h" + +using namespace BLI; + +static bool is_aligned(void *ptr, uint alignment) +{ + BLI_assert(is_power_of_2_i(alignment)); + return (POINTER_AS_UINT(ptr) & (alignment - 1)) == 0; +} + +TEST(linear_allocator, AllocationAlignment) +{ + LinearAllocator<> allocator; + + EXPECT_TRUE(is_aligned(allocator.allocate(10, 4), 4)); + EXPECT_TRUE(is_aligned(allocator.allocate(10, 4), 4)); + EXPECT_TRUE(is_aligned(allocator.allocate(10, 4), 4)); + EXPECT_TRUE(is_aligned(allocator.allocate(10, 8), 8)); + EXPECT_TRUE(is_aligned(allocator.allocate(10, 4), 4)); + EXPECT_TRUE(is_aligned(allocator.allocate(10, 16), 16)); + EXPECT_TRUE(is_aligned(allocator.allocate(10, 4), 4)); + EXPECT_TRUE(is_aligned(allocator.allocate(10, 64), 64)); + EXPECT_TRUE(is_aligned(allocator.allocate(10, 64), 64)); + EXPECT_TRUE(is_aligned(allocator.allocate(10, 8), 8)); + EXPECT_TRUE(is_aligned(allocator.allocate(10, 128), 128)); +} + +TEST(linear_allocator, PackedAllocation) +{ + LinearAllocator<> allocator; + BLI::AlignedBuffer<256, 32> buffer; + allocator.provide_buffer(buffer); + + uintptr_t ptr1 = (uintptr_t)allocator.allocate(10, 4); /* 0 - 10 */ + uintptr_t ptr2 = (uintptr_t)allocator.allocate(10, 4); /* 12 - 22 */ + uintptr_t ptr3 = (uintptr_t)allocator.allocate(8, 32); /* 32 - 40 */ + uintptr_t ptr4 = (uintptr_t)allocator.allocate(16, 8); /* 40 - 56 */ + uintptr_t ptr5 = (uintptr_t)allocator.allocate(1, 8); /* 56 - 57 */ + uintptr_t ptr6 = (uintptr_t)allocator.allocate(1, 4); /* 60 - 61 */ + uintptr_t ptr7 = (uintptr_t)allocator.allocate(1, 1); /* 61 - 62 */ + + EXPECT_EQ(ptr2 - ptr1, 12); /* 12 - 0 = 12 */ + EXPECT_EQ(ptr3 - ptr2, 20); /* 32 - 12 = 20 */ + EXPECT_EQ(ptr4 - ptr3, 8); /* 40 - 32 = 8 */ + EXPECT_EQ(ptr5 - ptr4, 16); /* 56 - 40 = 16 */ + EXPECT_EQ(ptr6 - ptr5, 4); /* 60 - 56 = 4 */ + EXPECT_EQ(ptr7 - ptr6, 1); /* 61 - 60 = 1 */ +} + +TEST(linear_allocator, CopyString) +{ + LinearAllocator<> allocator; + BLI::AlignedBuffer<256, 1> buffer; + allocator.provide_buffer(buffer); + + StringRefNull ref1 = allocator.copy_string("Hello"); + StringRefNull ref2 = allocator.copy_string("World"); + + EXPECT_EQ(ref1, "Hello"); + EXPECT_EQ(ref2, "World"); + EXPECT_EQ(ref2.data() - ref1.data(), 6); +} + +TEST(linear_allocator, AllocateArray) +{ + LinearAllocator<> allocator; + + MutableArrayRef<int> array = allocator.allocate_array<int>(5); + EXPECT_EQ(array.size(), 5); +} + +TEST(linear_allocator, Construct) +{ + LinearAllocator<> allocator; + + std::array<int, 5> values = {1, 2, 3, 4, 5}; + Vector<int> *vector = allocator.construct<Vector<int>>(values); + EXPECT_EQ(vector->size(), 5); + EXPECT_EQ((*vector)[3], 4); + vector->~Vector(); +} + +TEST(linear_allocator, ConstructElementsAndPointerArray) +{ + LinearAllocator<> allocator; + + std::array<int, 7> values = {1, 2, 3, 4, 5, 6, 7}; + ArrayRef<Vector<int> *> vectors = allocator.construct_elements_and_pointer_array<Vector<int>>( + 5, values); + + EXPECT_EQ(vectors.size(), 5); + EXPECT_EQ(vectors[3]->size(), 7); + EXPECT_EQ((*vectors[2])[5], 6); + + for (Vector<int> *vector : vectors) { + vector->~Vector(); + } +} + +TEST(linear_allocator, ConstructArrayCopy) +{ + LinearAllocator<> allocator; + + Vector<int> values = {1, 2, 3}; + MutableArrayRef<int> array1 = allocator.construct_array_copy(values.as_ref()); + MutableArrayRef<int> array2 = allocator.construct_array_copy(values.as_ref()); + EXPECT_NE(array1.begin(), array2.begin()); + EXPECT_EQ(array1.size(), 3); + EXPECT_EQ(array2.size(), 3); + EXPECT_EQ(array1[1], 2); + EXPECT_EQ(array2[2], 3); +} diff --git a/tests/gtests/blenlib/CMakeLists.txt b/tests/gtests/blenlib/CMakeLists.txt index 119b54fa0d4..a0621448630 100644 --- a/tests/gtests/blenlib/CMakeLists.txt +++ b/tests/gtests/blenlib/CMakeLists.txt @@ -52,6 +52,7 @@ BLENDER_TEST(BLI_heap "bf_blenlib") BLENDER_TEST(BLI_heap_simple "bf_blenlib") BLENDER_TEST(BLI_index_range "bf_blenlib") BLENDER_TEST(BLI_kdopbvh "bf_blenlib;bf_intern_numaapi") +BLENDER_TEST(BLI_linear_allocator "bf_blenlib") BLENDER_TEST(BLI_linklist_lockfree "bf_blenlib;bf_intern_numaapi") BLENDER_TEST(BLI_listbase "bf_blenlib") BLENDER_TEST(BLI_map "bf_blenlib") |