1 | /* |
2 | * Copyright 2012-present Facebook, Inc. |
3 | * |
4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
5 | * you may not use this file except in compliance with the License. |
6 | * You may obtain a copy of the License at |
7 | * |
8 | * http://www.apache.org/licenses/LICENSE-2.0 |
9 | * |
10 | * Unless required by applicable law or agreed to in writing, software |
11 | * distributed under the License is distributed on an "AS IS" BASIS, |
12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
13 | * See the License for the specific language governing permissions and |
14 | * limitations under the License. |
15 | */ |
16 | |
17 | #pragma once |
18 | #define FOLLY_ARENA_H_ |
19 | |
20 | #include <cassert> |
21 | #include <limits> |
22 | #include <stdexcept> |
23 | #include <utility> |
24 | |
25 | #include <boost/intrusive/slist.hpp> |
26 | |
27 | #include <folly/Conv.h> |
28 | #include <folly/Likely.h> |
29 | #include <folly/Memory.h> |
30 | #include <folly/lang/Align.h> |
31 | #include <folly/lang/Exception.h> |
32 | #include <folly/memory/Malloc.h> |
33 | |
34 | namespace folly { |
35 | |
36 | /** |
37 | * Simple arena: allocate memory which gets freed when the arena gets |
38 | * destroyed. |
39 | * |
40 | * The arena itself allocates memory using a custom allocator which conforms |
41 | * to the C++ concept Allocator. |
42 | * |
43 | * http://en.cppreference.com/w/cpp/concept/Allocator |
44 | * |
45 | * You may also specialize ArenaAllocatorTraits for your allocator type to |
46 | * provide: |
47 | * |
48 | * size_t goodSize(const Allocator& alloc, size_t size) const; |
49 | * Return a size (>= the provided size) that is considered "good" for your |
50 | * allocator (for example, if your allocator allocates memory in 4MB |
51 | * chunks, size should be rounded up to 4MB). The provided value is |
52 | * guaranteed to be rounded up to a multiple of the maximum alignment |
53 | * required on your system; the returned value must be also. |
54 | * |
55 | * An implementation that uses malloc() / free() is defined below, see SysArena. |
56 | */ |
57 | template <class Alloc> |
58 | struct ArenaAllocatorTraits; |
59 | template <class Alloc> |
60 | class Arena { |
61 | public: |
62 | explicit Arena( |
63 | const Alloc& alloc, |
64 | size_t minBlockSize = kDefaultMinBlockSize, |
65 | size_t sizeLimit = kNoSizeLimit, |
66 | size_t maxAlign = kDefaultMaxAlign) |
67 | : allocAndSize_(alloc, minBlockSize), |
68 | ptr_(nullptr), |
69 | end_(nullptr), |
70 | totalAllocatedSize_(0), |
71 | bytesUsed_(0), |
72 | sizeLimit_(sizeLimit), |
73 | maxAlign_(maxAlign) { |
74 | if ((maxAlign_ & (maxAlign_ - 1)) || maxAlign_ > alignof(Block)) { |
75 | throw_exception(std::invalid_argument( |
76 | folly::to<std::string>("Invalid maxAlign: " , maxAlign_))); |
77 | } |
78 | } |
79 | |
80 | ~Arena(); |
81 | |
82 | void* allocate(size_t size) { |
83 | size = roundUp(size); |
84 | bytesUsed_ += size; |
85 | |
86 | assert(ptr_ <= end_); |
87 | if (LIKELY((size_t)(end_ - ptr_) >= size)) { |
88 | // Fast path: there's enough room in the current block |
89 | char* r = ptr_; |
90 | ptr_ += size; |
91 | assert(isAligned(r)); |
92 | return r; |
93 | } |
94 | |
95 | // Not enough room in the current block |
96 | void* r = allocateSlow(size); |
97 | assert(isAligned(r)); |
98 | return r; |
99 | } |
100 | |
101 | void deallocate(void* /* p */, size_t = 0) { |
102 | // Deallocate? Never! |
103 | } |
104 | |
105 | // Transfer ownership of all memory allocated from "other" to "this". |
106 | void merge(Arena&& other); |
107 | |
108 | // Gets the total memory used by the arena |
109 | size_t totalSize() const { |
110 | return totalAllocatedSize_ + sizeof(Arena); |
111 | } |
112 | |
113 | // Gets the total number of "used" bytes, i.e. bytes that the arena users |
114 | // allocated via the calls to `allocate`. Doesn't include fragmentation, e.g. |
115 | // if block size is 4KB and you allocate 2 objects of 3KB in size, |
116 | // `bytesUsed()` will be 6KB, while `totalSize()` will be 8KB+. |
117 | size_t bytesUsed() const { |
118 | return bytesUsed_; |
119 | } |
120 | |
121 | // not copyable or movable |
122 | Arena(const Arena&) = delete; |
123 | Arena& operator=(const Arena&) = delete; |
124 | Arena(Arena&&) = delete; |
125 | Arena& operator=(Arena&&) = delete; |
126 | |
127 | private: |
128 | struct Block; |
129 | typedef boost::intrusive::slist_member_hook<boost::intrusive::tag<Arena>> |
130 | BlockLink; |
131 | |
132 | struct alignas(max_align_v) Block { |
133 | BlockLink link; |
134 | |
135 | // Allocate a block with at least size bytes of storage. |
136 | // If allowSlack is true, allocate more than size bytes if convenient |
137 | // (via ArenaAllocatorTraits::goodSize()) as we'll try to pack small |
138 | // allocations in this block. |
139 | static std::pair<Block*, size_t> |
140 | allocate(Alloc& alloc, size_t size, bool allowSlack); |
141 | void deallocate(Alloc& alloc); |
142 | |
143 | char* start() { |
144 | return reinterpret_cast<char*>(this + 1); |
145 | } |
146 | |
147 | private: |
148 | Block() = default; |
149 | ~Block() = default; |
150 | }; |
151 | |
152 | public: |
153 | static constexpr size_t kDefaultMinBlockSize = 4096 - sizeof(Block); |
154 | static constexpr size_t kNoSizeLimit = 0; |
155 | static constexpr size_t kDefaultMaxAlign = alignof(Block); |
156 | static constexpr size_t kBlockOverhead = sizeof(Block); |
157 | |
158 | private: |
159 | bool isAligned(uintptr_t address) const { |
160 | return (address & (maxAlign_ - 1)) == 0; |
161 | } |
162 | bool isAligned(void* p) const { |
163 | return isAligned(reinterpret_cast<uintptr_t>(p)); |
164 | } |
165 | |
166 | // Round up size so it's properly aligned |
167 | size_t roundUp(size_t size) const { |
168 | return (size + maxAlign_ - 1) & ~(maxAlign_ - 1); |
169 | } |
170 | |
171 | // cache_last<true> makes the list keep a pointer to the last element, so we |
172 | // have push_back() and constant time splice_after() |
173 | typedef boost::intrusive::slist< |
174 | Block, |
175 | boost::intrusive::member_hook<Block, BlockLink, &Block::link>, |
176 | boost::intrusive::constant_time_size<false>, |
177 | boost::intrusive::cache_last<true>> |
178 | BlockList; |
179 | |
180 | void* allocateSlow(size_t size); |
181 | |
182 | // Empty member optimization: package Alloc with a non-empty member |
183 | // in case Alloc is empty (as it is in the case of SysAllocator). |
184 | struct AllocAndSize : public Alloc { |
185 | explicit AllocAndSize(const Alloc& a, size_t s) |
186 | : Alloc(a), minBlockSize(s) {} |
187 | |
188 | size_t minBlockSize; |
189 | }; |
190 | |
191 | size_t minBlockSize() const { |
192 | return allocAndSize_.minBlockSize; |
193 | } |
194 | Alloc& alloc() { |
195 | return allocAndSize_; |
196 | } |
197 | const Alloc& alloc() const { |
198 | return allocAndSize_; |
199 | } |
200 | |
201 | AllocAndSize allocAndSize_; |
202 | BlockList blocks_; |
203 | char* ptr_; |
204 | char* end_; |
205 | size_t totalAllocatedSize_; |
206 | size_t bytesUsed_; |
207 | const size_t sizeLimit_; |
208 | const size_t maxAlign_; |
209 | }; |
210 | |
211 | template <class Alloc> |
212 | struct AllocatorHasTrivialDeallocate<Arena<Alloc>> : std::true_type {}; |
213 | |
214 | /** |
215 | * By default, don't pad the given size. |
216 | */ |
217 | template <class Alloc> |
218 | struct ArenaAllocatorTraits { |
219 | static size_t goodSize(const Alloc& /* alloc */, size_t size) { |
220 | return size; |
221 | } |
222 | }; |
223 | |
224 | template <> |
225 | struct ArenaAllocatorTraits<SysAllocator<void>> { |
226 | static size_t goodSize(const SysAllocator<void>& /* alloc */, size_t size) { |
227 | return goodMallocSize(size); |
228 | } |
229 | }; |
230 | |
231 | /** |
232 | * Arena that uses the system allocator (malloc / free) |
233 | */ |
234 | class SysArena : public Arena<SysAllocator<void>> { |
235 | public: |
236 | explicit SysArena( |
237 | size_t minBlockSize = kDefaultMinBlockSize, |
238 | size_t sizeLimit = kNoSizeLimit, |
239 | size_t maxAlign = kDefaultMaxAlign) |
240 | : Arena<SysAllocator<void>>({}, minBlockSize, sizeLimit, maxAlign) {} |
241 | }; |
242 | |
243 | template <> |
244 | struct AllocatorHasTrivialDeallocate<SysArena> : std::true_type {}; |
245 | |
246 | template <typename T, typename Alloc> |
247 | using ArenaAllocator = CxxAllocatorAdaptor<T, Arena<Alloc>>; |
248 | |
249 | template <typename T> |
250 | using SysArenaAllocator = ArenaAllocator<T, SysAllocator<void>>; |
251 | |
252 | } // namespace folly |
253 | |
254 | #include <folly/memory/Arena-inl.h> |
255 | |