2 * Copyright 2017 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
18 #define FOLLY_ARENA_H_
24 #include <boost/intrusive/slist.hpp>
26 #include <folly/Conv.h>
27 #include <folly/Likely.h>
28 #include <folly/Malloc.h>
29 #include <folly/Memory.h>
34 * Simple arena: allocate memory which gets freed when the arena gets
37 * The arena itself allocates memory using a custom allocator which provides
38 * the following interface (same as required by StlAllocator in StlAllocator.h)
40 * void* allocate(size_t size);
41 * Allocate a block of size bytes, properly aligned to the maximum
42 * alignment required on your system; throw std::bad_alloc if the
43 * allocation can't be satisfied.
45 * void deallocate(void* ptr);
46 * Deallocate a previously allocated block.
48 * You may also specialize ArenaAllocatorTraits for your allocator type to
51 * size_t goodSize(const Allocator& alloc, size_t size) const;
52 * Return a size (>= the provided size) that is considered "good" for your
53 * allocator (for example, if your allocator allocates memory in 4MB
54 * chunks, size should be rounded up to 4MB). The provided value is
55 * guaranteed to be rounded up to a multiple of the maximum alignment
56 * required on your system; the returned value must be also.
58 * An implementation that uses malloc() / free() is defined below, see SysArena.
60 template <class Alloc> struct ArenaAllocatorTraits;
61 template <class Alloc>
64 explicit Arena(const Alloc& alloc,
65 size_t minBlockSize = kDefaultMinBlockSize,
66 size_t sizeLimit = kNoSizeLimit,
67 size_t maxAlign = kDefaultMaxAlign)
68 : allocAndSize_(alloc, minBlockSize)
71 , totalAllocatedSize_(0)
73 , sizeLimit_(sizeLimit)
74 , maxAlign_(maxAlign) {
75 if ((maxAlign_ & (maxAlign_ - 1)) || maxAlign_ > alignof(Block)) {
76 throw std::invalid_argument(
77 folly::to<std::string>("Invalid maxAlign: ", maxAlign_));
83 void* allocate(size_t size) {
88 if (LIKELY((size_t)(end_ - ptr_) >= size)) {
89 // Fast path: there's enough room in the current block
96 // Not enough room in the current block
97 void* r = allocateSlow(size);
102 void deallocate(void* /* p */) {
103 // Deallocate? Never!
106 // Transfer ownership of all memory allocated from "other" to "this".
107 void merge(Arena&& other);
109 // Gets the total memory used by the arena
110 size_t totalSize() const {
111 return totalAllocatedSize_ + sizeof(Arena);
114 // Gets the total number of "used" bytes, i.e. bytes that the arena users
115 // allocated via the calls to `allocate`. Doesn't include fragmentation, e.g.
116 // if block size is 4KB and you allocate 2 objects of 3KB in size,
117 // `bytesUsed()` will be 6KB, while `totalSize()` will be 8KB+.
118 size_t bytesUsed() const {
123 Arena(const Arena&) = delete;
124 Arena& operator=(const Arena&) = delete;
127 Arena(Arena&&) = default;
128 Arena& operator=(Arena&&) = default;
132 typedef boost::intrusive::slist_member_hook<
133 boost::intrusive::tag<Arena>> BlockLink;
135 struct FOLLY_ALIGNED_MAX Block {
138 // Allocate a block with at least size bytes of storage.
139 // If allowSlack is true, allocate more than size bytes if convenient
140 // (via ArenaAllocatorTraits::goodSize()) as we'll try to pack small
141 // allocations in this block.
142 static std::pair<Block*, size_t> allocate(
143 Alloc& alloc, size_t size, bool allowSlack);
144 void deallocate(Alloc& alloc);
147 return reinterpret_cast<char*>(this + 1);
156 static constexpr size_t kDefaultMinBlockSize = 4096 - sizeof(Block);
157 static constexpr size_t kNoSizeLimit = 0;
158 static constexpr size_t kDefaultMaxAlign = alignof(Block);
159 static constexpr size_t kBlockOverhead = sizeof(Block);
162 bool isAligned(uintptr_t address) const {
163 return (address & (maxAlign_ - 1)) == 0;
165 bool isAligned(void* p) const {
166 return isAligned(reinterpret_cast<uintptr_t>(p));
169 // Round up size so it's properly aligned
170 size_t roundUp(size_t size) const {
171 return (size + maxAlign_ - 1) & ~(maxAlign_ - 1);
174 // cache_last<true> makes the list keep a pointer to the last element, so we
175 // have push_back() and constant time splice_after()
176 typedef boost::intrusive::slist<
178 boost::intrusive::member_hook<Block, BlockLink, &Block::link>,
179 boost::intrusive::constant_time_size<false>,
180 boost::intrusive::cache_last<true>> BlockList;
182 void* allocateSlow(size_t size);
184 // Empty member optimization: package Alloc with a non-empty member
185 // in case Alloc is empty (as it is in the case of SysAlloc).
186 struct AllocAndSize : public Alloc {
187 explicit AllocAndSize(const Alloc& a, size_t s)
188 : Alloc(a), minBlockSize(s) {
194 size_t minBlockSize() const {
195 return allocAndSize_.minBlockSize;
197 Alloc& alloc() { return allocAndSize_; }
198 const Alloc& alloc() const { return allocAndSize_; }
200 AllocAndSize allocAndSize_;
204 size_t totalAllocatedSize_;
206 const size_t sizeLimit_;
207 const size_t maxAlign_;
210 template <class Alloc>
211 struct IsArenaAllocator<Arena<Alloc>> : std::true_type { };
214 * By default, don't pad the given size.
216 template <class Alloc>
217 struct ArenaAllocatorTraits {
218 static size_t goodSize(const Alloc& /* alloc */, size_t size) { return size; }
222 struct ArenaAllocatorTraits<SysAlloc> {
223 static size_t goodSize(const SysAlloc& /* alloc */, size_t size) {
224 return goodMallocSize(size);
229 * Arena that uses the system allocator (malloc / free)
231 class SysArena : public Arena<SysAlloc> {
233 explicit SysArena(size_t minBlockSize = kDefaultMinBlockSize,
234 size_t sizeLimit = kNoSizeLimit,
235 size_t maxAlign = kDefaultMaxAlign)
236 : Arena<SysAlloc>(SysAlloc(), minBlockSize, sizeLimit, maxAlign) {
241 struct IsArenaAllocator<SysArena> : std::true_type { };
245 #include <folly/Arena-inl.h>