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