2 * Copyright 2014 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.
17 #ifndef FOLLY_ARENA_H_
18 #define FOLLY_ARENA_H_
23 #include <boost/intrusive/slist.hpp>
25 #include "folly/Likely.h"
26 #include "folly/Malloc.h"
31 * Simple arena: allocate memory which gets freed when the arena gets
34 * The arena itself allocates memory using a custom allocator which provides
35 * the following interface (same as required by StlAllocator in StlAllocator.h)
37 * void* allocate(size_t size);
38 * Allocate a block of size bytes, properly aligned to the maximum
39 * alignment required on your system; throw std::bad_alloc if the
40 * allocation can't be satisfied.
42 * void deallocate(void* ptr);
43 * Deallocate a previously allocated block.
45 * You may also specialize ArenaAllocatorTraits for your allocator type to
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.
55 * An implementation that uses malloc() / free() is defined below, see
56 * SysAlloc / SysArena.
58 template <class Alloc> struct ArenaAllocatorTraits;
59 template <class Alloc>
62 explicit Arena(const Alloc& alloc,
63 size_t minBlockSize = kDefaultMinBlockSize,
65 : allocAndSize_(alloc, minBlockSize)
68 , totalAllocatedSize_(0)
70 , sizeLimit_(sizeLimit) {
75 void* allocate(size_t size) {
79 if (LIKELY(end_ - ptr_ >= size)) {
80 // Fast path: there's enough room in the current block
87 // Not enough room in the current block
88 void* r = allocateSlow(size);
93 void deallocate(void* p) {
97 // Transfer ownership of all memory allocated from "other" to "this".
98 void merge(Arena&& other);
100 // Gets the total memory used by the arena
101 size_t totalSize() const {
102 return totalAllocatedSize_ + sizeof(Arena);
105 // Gets the total number of "used" bytes, i.e. bytes that the arena users
106 // allocated via the calls to `allocate`. Doesn't include fragmentation, e.g.
107 // if block size is 4KB and you allocate 2 objects of 3KB in size,
108 // `bytesUsed()` will be 6KB, while `totalSize()` will be 8KB+.
109 size_t bytesUsed() const {
115 Arena(const Arena&) = delete;
116 Arena& operator=(const Arena&) = delete;
119 Arena(Arena&&) = default;
120 Arena& operator=(Arena&&) = default;
123 typedef boost::intrusive::slist_member_hook<
124 boost::intrusive::tag<Arena>> BlockLink;
129 // Allocate a block with at least size bytes of storage.
130 // If allowSlack is true, allocate more than size bytes if convenient
131 // (via ArenaAllocatorTraits::goodSize()) as we'll try to pack small
132 // allocations in this block.
133 static std::pair<Block*, size_t> allocate(
134 Alloc& alloc, size_t size, bool allowSlack);
135 void deallocate(Alloc& alloc);
138 return reinterpret_cast<char*>(this + 1);
144 } __attribute__((aligned));
145 // This should be alignas(std::max_align_t) but neither alignas nor
146 // max_align_t are supported by gcc 4.6.2.
149 static constexpr size_t kDefaultMinBlockSize = 4096 - sizeof(Block);
152 static constexpr size_t maxAlign = alignof(Block);
153 static constexpr bool isAligned(uintptr_t address) {
154 return (address & (maxAlign - 1)) == 0;
156 static bool isAligned(void* p) {
157 return isAligned(reinterpret_cast<uintptr_t>(p));
160 // Round up size so it's properly aligned
161 static constexpr size_t roundUp(size_t size) {
162 return (size + maxAlign - 1) & ~(maxAlign - 1);
165 // cache_last<true> makes the list keep a pointer to the last element, so we
166 // have push_back() and constant time splice_after()
167 typedef boost::intrusive::slist<
169 boost::intrusive::member_hook<Block, BlockLink, &Block::link>,
170 boost::intrusive::constant_time_size<false>,
171 boost::intrusive::cache_last<true>> BlockList;
173 void* allocateSlow(size_t size);
175 // Empty member optimization: package Alloc with a non-empty member
176 // in case Alloc is empty (as it is in the case of SysAlloc).
177 struct AllocAndSize : public Alloc {
178 explicit AllocAndSize(const Alloc& a, size_t s)
179 : Alloc(a), minBlockSize(s) {
185 size_t minBlockSize() const {
186 return allocAndSize_.minBlockSize;
188 Alloc& alloc() { return allocAndSize_; }
189 const Alloc& alloc() const { return allocAndSize_; }
191 AllocAndSize allocAndSize_;
195 size_t totalAllocatedSize_;
201 * By default, don't pad the given size.
203 template <class Alloc>
204 struct ArenaAllocatorTraits {
205 static size_t goodSize(const Alloc& alloc, size_t size) {
211 * Arena-compatible allocator that calls malloc() and free(); see
212 * goodMallocSize() in Malloc.h for goodSize().
216 void* allocate(size_t size) {
217 return checkedMalloc(size);
220 void deallocate(void* p) {
226 struct ArenaAllocatorTraits<SysAlloc> {
227 static size_t goodSize(const SysAlloc& alloc, size_t size) {
228 return goodMallocSize(size);
233 * Arena that uses the system allocator (malloc / free)
235 class SysArena : public Arena<SysAlloc> {
238 size_t minBlockSize = kDefaultMinBlockSize,
239 size_t sizeLimit = 0)
240 : Arena<SysAlloc>(SysAlloc(), minBlockSize, sizeLimit) {
246 #include "folly/Arena-inl.h"
248 #endif /* FOLLY_ARENA_H_ */