1// Copyright (c) 2013-2014 Sandstorm Development Group, Inc. and contributors
2// Licensed under the MIT License:
3//
4// Permission is hereby granted, free of charge, to any person obtaining a copy
5// of this software and associated documentation files (the "Software"), to deal
6// in the Software without restriction, including without limitation the rights
7// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8// copies of the Software, and to permit persons to whom the Software is
9// furnished to do so, subject to the following conditions:
10//
11// The above copyright notice and this permission notice shall be included in
12// all copies or substantial portions of the Software.
13//
14// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
20// THE SOFTWARE.
21
22#pragma once
23
24#if defined(__GNUC__) && !KJ_HEADER_WARNINGS
25#pragma GCC system_header
26#endif
27
28#include "memory.h"
29#include "array.h"
30#include "string.h"
31
32namespace kj {
33
34class Arena {
35 // A class which allows several objects to be allocated in contiguous chunks of memory, then
36 // frees them all at once.
37 //
38 // Allocating from the same Arena in multiple threads concurrently is NOT safe, because making
39 // it safe would require atomic operations that would slow down allocation even when
40 // single-threaded. If you need to use arena allocation in a multithreaded context, consider
41 // allocating thread-local arenas.
42
43public:
44 explicit Arena(size_t chunkSizeHint = 1024);
45 // Create an Arena. `chunkSizeHint` hints at where to start when allocating chunks, but is only
46 // a hint -- the Arena will, for example, allocate progressively larger chunks as time goes on,
47 // in order to reduce overall allocation overhead.
48
49 explicit Arena(ArrayPtr<byte> scratch);
50 // Allocates from the given scratch space first, only resorting to the heap when it runs out.
51
52 KJ_DISALLOW_COPY(Arena);
53 ~Arena() noexcept(false);
54
55 template <typename T, typename... Params>
56 T& allocate(Params&&... params);
57 template <typename T>
58 ArrayPtr<T> allocateArray(size_t size);
59 // Allocate an object or array of type T. If T has a non-trivial destructor, that destructor
60 // will be run during the Arena's destructor. Such destructors are run in opposite order of
61 // allocation. Note that these methods must maintain a list of destructors to call, which has
62 // overhead, but this overhead only applies if T has a non-trivial destructor.
63
64 template <typename T, typename... Params>
65 Own<T> allocateOwn(Params&&... params);
66 template <typename T>
67 Array<T> allocateOwnArray(size_t size);
68 template <typename T>
69 ArrayBuilder<T> allocateOwnArrayBuilder(size_t capacity);
70 // Allocate an object or array of type T. Destructors are executed when the returned Own<T>
71 // or Array<T> goes out-of-scope, which must happen before the Arena is destroyed. This variant
72 // is useful when you need to control when the destructor is called. This variant also avoids
73 // the need for the Arena itself to keep track of destructors to call later, which may make it
74 // slightly more efficient.
75
76 template <typename T>
77 inline T& copy(T&& value) { return allocate<Decay<T>>(kj::fwd<T>(value)); }
78 // Allocate a copy of the given value in the arena. This is just a shortcut for calling the
79 // type's copy (or move) constructor.
80
81 StringPtr copyString(StringPtr content);
82 // Make a copy of the given string inside the arena, and return a pointer to the copy.
83
84private:
85 struct ChunkHeader {
86 ChunkHeader* next;
87 byte* pos; // first unallocated byte in this chunk
88 byte* end; // end of this chunk
89 };
90 struct ObjectHeader {
91 void (*destructor)(void*);
92 ObjectHeader* next;
93 };
94
95 size_t nextChunkSize;
96 ChunkHeader* chunkList = nullptr;
97 ObjectHeader* objectList = nullptr;
98
99 ChunkHeader* currentChunk = nullptr;
100
101 void cleanup();
102 // Run all destructors, leaving the above pointers null. If a destructor throws, the State is
103 // left in a consistent state, such that if cleanup() is called again, it will pick up where
104 // it left off.
105
106 void* allocateBytes(size_t amount, uint alignment, bool hasDisposer);
107 // Allocate the given number of bytes. `hasDisposer` must be true if `setDisposer()` may be
108 // called on this pointer later.
109
110 void* allocateBytesInternal(size_t amount, uint alignment);
111 // Try to allocate the given number of bytes without taking a lock. Fails if and only if there
112 // is no space left in the current chunk.
113
114 void setDestructor(void* ptr, void (*destructor)(void*));
115 // Schedule the given destructor to be executed when the Arena is destroyed. `ptr` must be a
116 // pointer previously returned by an `allocateBytes()` call for which `hasDisposer` was true.
117
118 template <typename T>
119 static void destroyArray(void* pointer) {
120 size_t elementCount = *reinterpret_cast<size_t*>(pointer);
121 constexpr size_t prefixSize = kj::max(alignof(T), sizeof(size_t));
122 DestructorOnlyArrayDisposer::instance.disposeImpl(
123 reinterpret_cast<byte*>(pointer) + prefixSize,
124 sizeof(T), elementCount, elementCount, &destroyObject<T>);
125 }
126
127 template <typename T>
128 static void destroyObject(void* pointer) {
129 dtor(*reinterpret_cast<T*>(pointer));
130 }
131};
132
133// =======================================================================================
134// Inline implementation details
135
136template <typename T, typename... Params>
137T& Arena::allocate(Params&&... params) {
138 T& result = *reinterpret_cast<T*>(allocateBytes(
139 sizeof(T), alignof(T), !__has_trivial_destructor(T)));
140 if (!__has_trivial_constructor(T) || sizeof...(Params) > 0) {
141 ctor(result, kj::fwd<Params>(params)...);
142 }
143 if (!__has_trivial_destructor(T)) {
144 setDestructor(&result, &destroyObject<T>);
145 }
146 return result;
147}
148
149template <typename T>
150ArrayPtr<T> Arena::allocateArray(size_t size) {
151 if (__has_trivial_destructor(T)) {
152 ArrayPtr<T> result =
153 arrayPtr(reinterpret_cast<T*>(allocateBytes(
154 sizeof(T) * size, alignof(T), false)), size);
155 if (!__has_trivial_constructor(T)) {
156 for (size_t i = 0; i < size; i++) {
157 ctor(result[i]);
158 }
159 }
160 return result;
161 } else {
162 // Allocate with a 64-bit prefix in which we store the array size.
163 constexpr size_t prefixSize = kj::max(alignof(T), sizeof(size_t));
164 void* base = allocateBytes(sizeof(T) * size + prefixSize, alignof(T), true);
165 size_t& tag = *reinterpret_cast<size_t*>(base);
166 ArrayPtr<T> result =
167 arrayPtr(reinterpret_cast<T*>(reinterpret_cast<byte*>(base) + prefixSize), size);
168 setDestructor(base, &destroyArray<T>);
169
170 if (__has_trivial_constructor(T)) {
171 tag = size;
172 } else {
173 // In case of constructor exceptions, we need the tag to end up storing the number of objects
174 // that were successfully constructed, so that they'll be properly destroyed.
175 tag = 0;
176 for (size_t i = 0; i < size; i++) {
177 ctor(result[i]);
178 tag = i + 1;
179 }
180 }
181 return result;
182 }
183}
184
185template <typename T, typename... Params>
186Own<T> Arena::allocateOwn(Params&&... params) {
187 T& result = *reinterpret_cast<T*>(allocateBytes(sizeof(T), alignof(T), false));
188 if (!__has_trivial_constructor(T) || sizeof...(Params) > 0) {
189 ctor(result, kj::fwd<Params>(params)...);
190 }
191 return Own<T>(&result, DestructorOnlyDisposer<T>::instance);
192}
193
194template <typename T>
195Array<T> Arena::allocateOwnArray(size_t size) {
196 ArrayBuilder<T> result = allocateOwnArrayBuilder<T>(size);
197 for (size_t i = 0; i < size; i++) {
198 result.add();
199 }
200 return result.finish();
201}
202
203template <typename T>
204ArrayBuilder<T> Arena::allocateOwnArrayBuilder(size_t capacity) {
205 return ArrayBuilder<T>(
206 reinterpret_cast<T*>(allocateBytes(sizeof(T) * capacity, alignof(T), false)),
207 capacity, DestructorOnlyArrayDisposer::instance);
208}
209
210} // namespace kj
211