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