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 | |
32 | namespace kj { |
33 | |
34 | class 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 | |
43 | public: |
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 | |
84 | private: |
85 | struct { |
86 | ChunkHeader* ; |
87 | byte* ; // first unallocated byte in this chunk |
88 | byte* ; // end of this chunk |
89 | }; |
90 | struct { |
91 | void (*)(void*); |
92 | ObjectHeader* ; |
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 | |
136 | template <typename T, typename... Params> |
137 | T& 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 | |
149 | template <typename T> |
150 | ArrayPtr<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 | |
185 | template <typename T, typename... Params> |
186 | Own<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 | |
194 | template <typename T> |
195 | Array<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 | |
203 | template <typename T> |
204 | ArrayBuilder<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 | |