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