cannam@148: // Copyright (c) 2013-2014 Sandstorm Development Group, Inc. and contributors cannam@148: // Licensed under the MIT License: cannam@148: // cannam@148: // Permission is hereby granted, free of charge, to any person obtaining a copy cannam@148: // of this software and associated documentation files (the "Software"), to deal cannam@148: // in the Software without restriction, including without limitation the rights cannam@148: // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell cannam@148: // copies of the Software, and to permit persons to whom the Software is cannam@148: // furnished to do so, subject to the following conditions: cannam@148: // cannam@148: // The above copyright notice and this permission notice shall be included in cannam@148: // all copies or substantial portions of the Software. cannam@148: // cannam@148: // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR cannam@148: // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, cannam@148: // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE cannam@148: // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER cannam@148: // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, cannam@148: // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN cannam@148: // THE SOFTWARE. cannam@148: cannam@148: #ifndef KJ_ARENA_H_ cannam@148: #define KJ_ARENA_H_ cannam@148: cannam@148: #if defined(__GNUC__) && !KJ_HEADER_WARNINGS cannam@148: #pragma GCC system_header cannam@148: #endif cannam@148: cannam@148: #include "memory.h" cannam@148: #include "array.h" cannam@148: #include "string.h" cannam@148: cannam@148: namespace kj { cannam@148: cannam@148: class Arena { cannam@148: // A class which allows several objects to be allocated in contiguous chunks of memory, then cannam@148: // frees them all at once. cannam@148: // cannam@148: // Allocating from the same Arena in multiple threads concurrently is NOT safe, because making cannam@148: // it safe would require atomic operations that would slow down allocation even when cannam@148: // single-threaded. If you need to use arena allocation in a multithreaded context, consider cannam@148: // allocating thread-local arenas. cannam@148: cannam@148: public: cannam@148: explicit Arena(size_t chunkSizeHint = 1024); cannam@148: // Create an Arena. `chunkSizeHint` hints at where to start when allocating chunks, but is only cannam@148: // a hint -- the Arena will, for example, allocate progressively larger chunks as time goes on, cannam@148: // in order to reduce overall allocation overhead. cannam@148: cannam@148: explicit Arena(ArrayPtr scratch); cannam@148: // Allocates from the given scratch space first, only resorting to the heap when it runs out. cannam@148: cannam@148: KJ_DISALLOW_COPY(Arena); cannam@148: ~Arena() noexcept(false); cannam@148: cannam@148: template cannam@148: T& allocate(Params&&... params); cannam@148: template cannam@148: ArrayPtr allocateArray(size_t size); cannam@148: // Allocate an object or array of type T. If T has a non-trivial destructor, that destructor cannam@148: // will be run during the Arena's destructor. Such destructors are run in opposite order of cannam@148: // allocation. Note that these methods must maintain a list of destructors to call, which has cannam@148: // overhead, but this overhead only applies if T has a non-trivial destructor. cannam@148: cannam@148: template cannam@148: Own allocateOwn(Params&&... params); cannam@148: template cannam@148: Array allocateOwnArray(size_t size); cannam@148: template cannam@148: ArrayBuilder allocateOwnArrayBuilder(size_t capacity); cannam@148: // Allocate an object or array of type T. Destructors are executed when the returned Own cannam@148: // or Array goes out-of-scope, which must happen before the Arena is destroyed. This variant cannam@148: // is useful when you need to control when the destructor is called. This variant also avoids cannam@148: // the need for the Arena itself to keep track of destructors to call later, which may make it cannam@148: // slightly more efficient. cannam@148: cannam@148: template cannam@148: inline T& copy(T&& value) { return allocate>(kj::fwd(value)); } cannam@148: // Allocate a copy of the given value in the arena. This is just a shortcut for calling the cannam@148: // type's copy (or move) constructor. cannam@148: cannam@148: StringPtr copyString(StringPtr content); cannam@148: // Make a copy of the given string inside the arena, and return a pointer to the copy. cannam@148: cannam@148: private: cannam@148: struct ChunkHeader { cannam@148: ChunkHeader* next; cannam@148: byte* pos; // first unallocated byte in this chunk cannam@148: byte* end; // end of this chunk cannam@148: }; cannam@148: struct ObjectHeader { cannam@148: void (*destructor)(void*); cannam@148: ObjectHeader* next; cannam@148: }; cannam@148: cannam@148: size_t nextChunkSize; cannam@148: ChunkHeader* chunkList = nullptr; cannam@148: ObjectHeader* objectList = nullptr; cannam@148: cannam@148: ChunkHeader* currentChunk = nullptr; cannam@148: cannam@148: void cleanup(); cannam@148: // Run all destructors, leaving the above pointers null. If a destructor throws, the State is cannam@148: // left in a consistent state, such that if cleanup() is called again, it will pick up where cannam@148: // it left off. cannam@148: cannam@148: void* allocateBytes(size_t amount, uint alignment, bool hasDisposer); cannam@148: // Allocate the given number of bytes. `hasDisposer` must be true if `setDisposer()` may be cannam@148: // called on this pointer later. cannam@148: cannam@148: void* allocateBytesInternal(size_t amount, uint alignment); cannam@148: // Try to allocate the given number of bytes without taking a lock. Fails if and only if there cannam@148: // is no space left in the current chunk. cannam@148: cannam@148: void setDestructor(void* ptr, void (*destructor)(void*)); cannam@148: // Schedule the given destructor to be executed when the Arena is destroyed. `ptr` must be a cannam@148: // pointer previously returned by an `allocateBytes()` call for which `hasDisposer` was true. cannam@148: cannam@148: template cannam@148: static void destroyArray(void* pointer) { cannam@148: size_t elementCount = *reinterpret_cast(pointer); cannam@148: constexpr size_t prefixSize = kj::max(alignof(T), sizeof(size_t)); cannam@148: DestructorOnlyArrayDisposer::instance.disposeImpl( cannam@148: reinterpret_cast(pointer) + prefixSize, cannam@148: sizeof(T), elementCount, elementCount, &destroyObject); cannam@148: } cannam@148: cannam@148: template cannam@148: static void destroyObject(void* pointer) { cannam@148: dtor(*reinterpret_cast(pointer)); cannam@148: } cannam@148: }; cannam@148: cannam@148: // ======================================================================================= cannam@148: // Inline implementation details cannam@148: cannam@148: template cannam@148: T& Arena::allocate(Params&&... params) { cannam@148: T& result = *reinterpret_cast(allocateBytes( cannam@148: sizeof(T), alignof(T), !__has_trivial_destructor(T))); cannam@148: if (!__has_trivial_constructor(T) || sizeof...(Params) > 0) { cannam@148: ctor(result, kj::fwd(params)...); cannam@148: } cannam@148: if (!__has_trivial_destructor(T)) { cannam@148: setDestructor(&result, &destroyObject); cannam@148: } cannam@148: return result; cannam@148: } cannam@148: cannam@148: template cannam@148: ArrayPtr Arena::allocateArray(size_t size) { cannam@148: if (__has_trivial_destructor(T)) { cannam@148: ArrayPtr result = cannam@148: arrayPtr(reinterpret_cast(allocateBytes( cannam@148: sizeof(T) * size, alignof(T), false)), size); cannam@148: if (!__has_trivial_constructor(T)) { cannam@148: for (size_t i = 0; i < size; i++) { cannam@148: ctor(result[i]); cannam@148: } cannam@148: } cannam@148: return result; cannam@148: } else { cannam@148: // Allocate with a 64-bit prefix in which we store the array size. cannam@148: constexpr size_t prefixSize = kj::max(alignof(T), sizeof(size_t)); cannam@148: void* base = allocateBytes(sizeof(T) * size + prefixSize, alignof(T), true); cannam@148: size_t& tag = *reinterpret_cast(base); cannam@148: ArrayPtr result = cannam@148: arrayPtr(reinterpret_cast(reinterpret_cast(base) + prefixSize), size); cannam@148: setDestructor(base, &destroyArray); cannam@148: cannam@148: if (__has_trivial_constructor(T)) { cannam@148: tag = size; cannam@148: } else { cannam@148: // In case of constructor exceptions, we need the tag to end up storing the number of objects cannam@148: // that were successfully constructed, so that they'll be properly destroyed. cannam@148: tag = 0; cannam@148: for (size_t i = 0; i < size; i++) { cannam@148: ctor(result[i]); cannam@148: tag = i + 1; cannam@148: } cannam@148: } cannam@148: return result; cannam@148: } cannam@148: } cannam@148: cannam@148: template cannam@148: Own Arena::allocateOwn(Params&&... params) { cannam@148: T& result = *reinterpret_cast(allocateBytes(sizeof(T), alignof(T), false)); cannam@148: if (!__has_trivial_constructor(T) || sizeof...(Params) > 0) { cannam@148: ctor(result, kj::fwd(params)...); cannam@148: } cannam@148: return Own(&result, DestructorOnlyDisposer::instance); cannam@148: } cannam@148: cannam@148: template cannam@148: Array Arena::allocateOwnArray(size_t size) { cannam@148: ArrayBuilder result = allocateOwnArrayBuilder(size); cannam@148: for (size_t i = 0; i < size; i++) { cannam@148: result.add(); cannam@148: } cannam@148: return result.finish(); cannam@148: } cannam@148: cannam@148: template cannam@148: ArrayBuilder Arena::allocateOwnArrayBuilder(size_t capacity) { cannam@148: return ArrayBuilder( cannam@148: reinterpret_cast(allocateBytes(sizeof(T) * capacity, alignof(T), false)), cannam@148: capacity, DestructorOnlyArrayDisposer::instance); cannam@148: } cannam@148: cannam@148: } // namespace kj cannam@148: cannam@148: #endif // KJ_ARENA_H_