arena.h (8202B)
1 // Copyright (c) 2013-2014 Sandstorm Development Group, Inc. and contributors 2 // Licensed under the MIT License: 3 // 4 // Permission is hereby granted, free of charge, to any person obtaining a copy 5 // of this software and associated documentation files (the "Software"), to deal 6 // in the Software without restriction, including without limitation the rights 7 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 8 // copies of the Software, and to permit persons to whom the Software is 9 // furnished to do so, subject to the following conditions: 10 // 11 // The above copyright notice and this permission notice shall be included in 12 // all copies or substantial portions of the Software. 13 // 14 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 15 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 16 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 17 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 18 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 19 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 20 // THE SOFTWARE. 21 22 #pragma once 23 24 #include "memory.h" 25 #include "array.h" 26 #include "string.h" 27 28 KJ_BEGIN_HEADER 29 30 namespace kj { 31 32 class Arena { 33 // A class which allows several objects to be allocated in contiguous chunks of memory, then 34 // frees them all at once. 35 // 36 // Allocating from the same Arena in multiple threads concurrently is NOT safe, because making 37 // it safe would require atomic operations that would slow down allocation even when 38 // single-threaded. If you need to use arena allocation in a multithreaded context, consider 39 // allocating thread-local arenas. 40 41 public: 42 explicit Arena(size_t chunkSizeHint = 1024); 43 // Create an Arena. `chunkSizeHint` hints at where to start when allocating chunks, but is only 44 // a hint -- the Arena will, for example, allocate progressively larger chunks as time goes on, 45 // in order to reduce overall allocation overhead. 46 47 explicit Arena(ArrayPtr<byte> scratch); 48 // Allocates from the given scratch space first, only resorting to the heap when it runs out. 49 50 KJ_DISALLOW_COPY(Arena); 51 ~Arena() noexcept(false); 52 53 template <typename T, typename... Params> 54 T& allocate(Params&&... params); 55 template <typename T> 56 ArrayPtr<T> allocateArray(size_t size); 57 // Allocate an object or array of type T. If T has a non-trivial destructor, that destructor 58 // will be run during the Arena's destructor. Such destructors are run in opposite order of 59 // allocation. Note that these methods must maintain a list of destructors to call, which has 60 // overhead, but this overhead only applies if T has a non-trivial destructor. 61 62 template <typename T, typename... Params> 63 Own<T> allocateOwn(Params&&... params); 64 template <typename T> 65 Array<T> allocateOwnArray(size_t size); 66 template <typename T> 67 ArrayBuilder<T> allocateOwnArrayBuilder(size_t capacity); 68 // Allocate an object or array of type T. Destructors are executed when the returned Own<T> 69 // or Array<T> goes out-of-scope, which must happen before the Arena is destroyed. This variant 70 // is useful when you need to control when the destructor is called. This variant also avoids 71 // the need for the Arena itself to keep track of destructors to call later, which may make it 72 // slightly more efficient. 73 74 template <typename T> 75 inline T& copy(T&& value) { return allocate<Decay<T>>(kj::fwd<T>(value)); } 76 // Allocate a copy of the given value in the arena. This is just a shortcut for calling the 77 // type's copy (or move) constructor. 78 79 StringPtr copyString(StringPtr content); 80 // Make a copy of the given string inside the arena, and return a pointer to the copy. 81 82 private: 83 struct ChunkHeader { 84 ChunkHeader* next; 85 byte* pos; // first unallocated byte in this chunk 86 byte* end; // end of this chunk 87 }; 88 struct ObjectHeader { 89 void (*destructor)(void*); 90 ObjectHeader* next; 91 }; 92 93 size_t nextChunkSize; 94 ChunkHeader* chunkList = nullptr; 95 ObjectHeader* objectList = nullptr; 96 97 ChunkHeader* currentChunk = nullptr; 98 99 void cleanup(); 100 // Run all destructors, leaving the above pointers null. If a destructor throws, the State is 101 // left in a consistent state, such that if cleanup() is called again, it will pick up where 102 // it left off. 103 104 void* allocateBytes(size_t amount, uint alignment, bool hasDisposer); 105 // Allocate the given number of bytes. `hasDisposer` must be true if `setDisposer()` may be 106 // called on this pointer later. 107 108 void* allocateBytesInternal(size_t amount, uint alignment); 109 // Try to allocate the given number of bytes without taking a lock. Fails if and only if there 110 // is no space left in the current chunk. 111 112 void setDestructor(void* ptr, void (*destructor)(void*)); 113 // Schedule the given destructor to be executed when the Arena is destroyed. `ptr` must be a 114 // pointer previously returned by an `allocateBytes()` call for which `hasDisposer` was true. 115 116 template <typename T> 117 static void destroyArray(void* pointer) { 118 size_t elementCount = *reinterpret_cast<size_t*>(pointer); 119 constexpr size_t prefixSize = kj::max(alignof(T), sizeof(size_t)); 120 DestructorOnlyArrayDisposer::instance.disposeImpl( 121 reinterpret_cast<byte*>(pointer) + prefixSize, 122 sizeof(T), elementCount, elementCount, &destroyObject<T>); 123 } 124 125 template <typename T> 126 static void destroyObject(void* pointer) { 127 dtor(*reinterpret_cast<T*>(pointer)); 128 } 129 }; 130 131 // ======================================================================================= 132 // Inline implementation details 133 134 template <typename T, typename... Params> 135 T& Arena::allocate(Params&&... params) { 136 T& result = *reinterpret_cast<T*>(allocateBytes( 137 sizeof(T), alignof(T), !__has_trivial_destructor(T))); 138 if (!__has_trivial_constructor(T) || sizeof...(Params) > 0) { 139 ctor(result, kj::fwd<Params>(params)...); 140 } 141 if (!__has_trivial_destructor(T)) { 142 setDestructor(&result, &destroyObject<T>); 143 } 144 return result; 145 } 146 147 template <typename T> 148 ArrayPtr<T> Arena::allocateArray(size_t size) { 149 if (__has_trivial_destructor(T)) { 150 ArrayPtr<T> result = 151 arrayPtr(reinterpret_cast<T*>(allocateBytes( 152 sizeof(T) * size, alignof(T), false)), size); 153 if (!__has_trivial_constructor(T)) { 154 for (size_t i = 0; i < size; i++) { 155 ctor(result[i]); 156 } 157 } 158 return result; 159 } else { 160 // Allocate with a 64-bit prefix in which we store the array size. 161 constexpr size_t prefixSize = kj::max(alignof(T), sizeof(size_t)); 162 void* base = allocateBytes(sizeof(T) * size + prefixSize, alignof(T), true); 163 size_t& tag = *reinterpret_cast<size_t*>(base); 164 ArrayPtr<T> result = 165 arrayPtr(reinterpret_cast<T*>(reinterpret_cast<byte*>(base) + prefixSize), size); 166 setDestructor(base, &destroyArray<T>); 167 168 if (__has_trivial_constructor(T)) { 169 tag = size; 170 } else { 171 // In case of constructor exceptions, we need the tag to end up storing the number of objects 172 // that were successfully constructed, so that they'll be properly destroyed. 173 tag = 0; 174 for (size_t i = 0; i < size; i++) { 175 ctor(result[i]); 176 tag = i + 1; 177 } 178 } 179 return result; 180 } 181 } 182 183 template <typename T, typename... Params> 184 Own<T> Arena::allocateOwn(Params&&... params) { 185 T& result = *reinterpret_cast<T*>(allocateBytes(sizeof(T), alignof(T), false)); 186 if (!__has_trivial_constructor(T) || sizeof...(Params) > 0) { 187 ctor(result, kj::fwd<Params>(params)...); 188 } 189 return Own<T>(&result, DestructorOnlyDisposer<T>::instance); 190 } 191 192 template <typename T> 193 Array<T> Arena::allocateOwnArray(size_t size) { 194 ArrayBuilder<T> result = allocateOwnArrayBuilder<T>(size); 195 for (size_t i = 0; i < size; i++) { 196 result.add(); 197 } 198 return result.finish(); 199 } 200 201 template <typename T> 202 ArrayBuilder<T> Arena::allocateOwnArrayBuilder(size_t capacity) { 203 return ArrayBuilder<T>( 204 reinterpret_cast<T*>(allocateBytes(sizeof(T) * capacity, alignof(T), false)), 205 capacity, DestructorOnlyArrayDisposer::instance); 206 } 207 208 } // namespace kj 209 210 KJ_END_HEADER