folly/memory/Arena.h

   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/memory/Malloc.h>
  32
  33 namespace folly {
  34
  35 /**
  36  * Simple arena: allocate memory which gets freed when the arena gets
  37  * destroyed.
  38  *
  39  * The arena itself allocates memory using a custom allocator which provides
  40  * the following interface (same as required by StlAllocator in StlAllocator.h)
  41  *
  42  *   void* allocate(size_t size);
  43  *      Allocate a block of size bytes, properly aligned to the maximum
  44  *      alignment required on your system; throw std::bad_alloc if the
  45  *      allocation can't be satisfied.
  46  *
  47  *   void deallocate(void* ptr);
  48  *      Deallocate a previously allocated block.
  49  *
  50  * You may also specialize ArenaAllocatorTraits for your allocator type to
  51  * provide:
  52  *
  53  *   size_t goodSize(const Allocator& alloc, size_t size) const;
  54  *      Return a size (>= the provided size) that is considered "good" for your
  55  *      allocator (for example, if your allocator allocates memory in 4MB
  56  *      chunks, size should be rounded up to 4MB).  The provided value is
  57  *      guaranteed to be rounded up to a multiple of the maximum alignment
  58  *      required on your system; the returned value must be also.
  59  *
  60  * An implementation that uses malloc() / free() is defined below, see SysArena.
  61  */
  62 template <class Alloc> struct ArenaAllocatorTraits;
  63 template <class Alloc>
  64 class Arena {
  65  public:
  66   explicit Arena(const Alloc& alloc,
  67                  size_t minBlockSize = kDefaultMinBlockSize,
  68                  size_t sizeLimit = kNoSizeLimit,
  69                  size_t maxAlign = kDefaultMaxAlign)
  70     : allocAndSize_(alloc, minBlockSize)
  71     , ptr_(nullptr)
  72     , end_(nullptr)
  73     , totalAllocatedSize_(0)
  74     , bytesUsed_(0)
  75     , sizeLimit_(sizeLimit)
  76     , maxAlign_(maxAlign) {
  77     if ((maxAlign_ & (maxAlign_ - 1)) || maxAlign_ > alignof(Block)) {
  78       throw std::invalid_argument(
  79           folly::to<std::string>("Invalid maxAlign: ", maxAlign_));
  80     }
  81   }
  82
  83   ~Arena();
  84
  85   void* allocate(size_t size) {
  86     size = roundUp(size);
  87     bytesUsed_ += size;
  88
  89     assert(ptr_ <= end_);
  90     if (LIKELY((size_t)(end_ - ptr_) >= size)) {
  91       // Fast path: there's enough room in the current block
  92       char* r = ptr_;
  93       ptr_ += size;
  94       assert(isAligned(r));
  95       return r;
  96     }
  97
  98     // Not enough room in the current block
  99     void* r = allocateSlow(size);
 100     assert(isAligned(r));
 101     return r;
 102   }
 103
 104   void deallocate(void* /* p */) {
 105     // Deallocate? Never!
 106   }
 107
 108   // Transfer ownership of all memory allocated from "other" to "this".
 109   void merge(Arena&& other);
 110
 111   // Gets the total memory used by the arena
 112   size_t totalSize() const {
 113     return totalAllocatedSize_ + sizeof(Arena);
 114   }
 115
 116   // Gets the total number of "used" bytes, i.e. bytes that the arena users
 117   // allocated via the calls to `allocate`. Doesn't include fragmentation, e.g.
 118   // if block size is 4KB and you allocate 2 objects of 3KB in size,
 119   // `bytesUsed()` will be 6KB, while `totalSize()` will be 8KB+.
 120   size_t bytesUsed() const {
 121     return bytesUsed_;
 122   }
 123
 124   // not copyable
 125   Arena(const Arena&) = delete;
 126   Arena& operator=(const Arena&) = delete;
 127
 128   // movable
 129   Arena(Arena&&) = default;
 130   Arena& operator=(Arena&&) = default;
 131
 132  private:
 133   struct Block;
 134   typedef boost::intrusive::slist_member_hook<
 135     boost::intrusive::tag<Arena>> BlockLink;
 136
 137   struct alignas(max_align_v) Block {
 138     BlockLink link;
 139
 140     // Allocate a block with at least size bytes of storage.
 141     // If allowSlack is true, allocate more than size bytes if convenient
 142     // (via ArenaAllocatorTraits::goodSize()) as we'll try to pack small
 143     // allocations in this block.
 144     static std::pair<Block*, size_t> allocate(
 145         Alloc& alloc, size_t size, bool allowSlack);
 146     void deallocate(Alloc& alloc);
 147
 148     char* start() {
 149       return reinterpret_cast<char*>(this + 1);
 150     }
 151
 152    private:
 153     Block() = default;
 154     ~Block() = default;
 155   };
 156
 157  public:
 158   static constexpr size_t kDefaultMinBlockSize = 4096 - sizeof(Block);
 159   static constexpr size_t kNoSizeLimit = 0;
 160   static constexpr size_t kDefaultMaxAlign = alignof(Block);
 161   static constexpr size_t kBlockOverhead = sizeof(Block);
 162
 163  private:
 164   bool isAligned(uintptr_t address) const {
 165     return (address & (maxAlign_ - 1)) == 0;
 166   }
 167   bool isAligned(void* p) const {
 168     return isAligned(reinterpret_cast<uintptr_t>(p));
 169   }
 170
 171   // Round up size so it's properly aligned
 172   size_t roundUp(size_t size) const {
 173     return (size + maxAlign_ - 1) & ~(maxAlign_ - 1);
 174   }
 175
 176   // cache_last<true> makes the list keep a pointer to the last element, so we
 177   // have push_back() and constant time splice_after()
 178   typedef boost::intrusive::slist<
 179     Block,
 180     boost::intrusive::member_hook<Block, BlockLink, &Block::link>,
 181     boost::intrusive::constant_time_size<false>,
 182     boost::intrusive::cache_last<true>> BlockList;
 183
 184   void* allocateSlow(size_t size);
 185
 186   // Empty member optimization: package Alloc with a non-empty member
 187   // in case Alloc is empty (as it is in the case of SysAlloc).
 188   struct AllocAndSize : public Alloc {
 189     explicit AllocAndSize(const Alloc& a, size_t s)
 190       : Alloc(a), minBlockSize(s) {
 191     }
 192
 193     size_t minBlockSize;
 194   };
 195
 196   size_t minBlockSize() const {
 197     return allocAndSize_.minBlockSize;
 198   }
 199   Alloc& alloc() { return allocAndSize_; }
 200   const Alloc& alloc() const { return allocAndSize_; }
 201
 202   AllocAndSize allocAndSize_;
 203   BlockList blocks_;
 204   char* ptr_;
 205   char* end_;
 206   size_t totalAllocatedSize_;
 207   size_t bytesUsed_;
 208   const size_t sizeLimit_;
 209   const size_t maxAlign_;
 210 };
 211
 212 template <class Alloc>
 213 struct IsArenaAllocator<Arena<Alloc>> : std::true_type { };
 214
 215 /**
 216  * By default, don't pad the given size.
 217  */
 218 template <class Alloc>
 219 struct ArenaAllocatorTraits {
 220   static size_t goodSize(const Alloc& /* alloc */, size_t size) { return size; }
 221 };
 222
 223 template <>
 224 struct ArenaAllocatorTraits<SysAlloc> {
 225   static size_t goodSize(const SysAlloc& /* alloc */, size_t size) {
 226     return goodMallocSize(size);
 227   }
 228 };
 229
 230 /**
 231  * Arena that uses the system allocator (malloc / free)
 232  */
 233 class SysArena : public Arena<SysAlloc> {
 234  public:
 235   explicit SysArena(size_t minBlockSize = kDefaultMinBlockSize,
 236                     size_t sizeLimit = kNoSizeLimit,
 237                     size_t maxAlign = kDefaultMaxAlign)
 238     : Arena<SysAlloc>(SysAlloc(), minBlockSize, sizeLimit, maxAlign) {
 239   }
 240 };
 241
 242 template <>
 243 struct IsArenaAllocator<SysArena> : std::true_type { };
 244
 245 } // namespace folly
 246
 247 #include <folly/memory/Arena-inl.h>