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
34namespace 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 */
57template <class Alloc>
58struct ArenaAllocatorTraits;
59template <class Alloc>
60class 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
211template <class Alloc>
212struct AllocatorHasTrivialDeallocate<Arena<Alloc>> : std::true_type {};
213
214/**
215 * By default, don't pad the given size.
216 */
217template <class Alloc>
218struct ArenaAllocatorTraits {
219 static size_t goodSize(const Alloc& /* alloc */, size_t size) {
220 return size;
221 }
222};
223
224template <>
225struct 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 */
234class 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
243template <>
244struct AllocatorHasTrivialDeallocate<SysArena> : std::true_type {};
245
246template <typename T, typename Alloc>
247using ArenaAllocator = CxxAllocatorAdaptor<T, Arena<Alloc>>;
248
249template <typename T>
250using SysArenaAllocator = ArenaAllocator<T, SysAllocator<void>>;
251
252} // namespace folly
253
254#include <folly/memory/Arena-inl.h>
255