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