folly/Arena.h

   1 /*
   2  * Copyright 2014 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 #ifndef FOLLY_ARENA_H_
  18 #define FOLLY_ARENA_H_
  19
  20 #include <cassert>
  21 #include <utility>
  22 #include <limits>
  23 #include <boost/intrusive/slist.hpp>
  24
  25 #include "folly/Likely.h"
  26 #include "folly/Malloc.h"
  27
  28 namespace folly {
  29
  30 /**
  31  * Simple arena: allocate memory which gets freed when the arena gets
  32  * destroyed.
  33  *
  34  * The arena itself allocates memory using a custom allocator which provides
  35  * the following interface (same as required by StlAllocator in StlAllocator.h)
  36  *
  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.
  41  *
  42  *   void deallocate(void* ptr);
  43  *      Deallocate a previously allocated block.
  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
  56  * SysAlloc / SysArena.
  57  */
  58 template <class Alloc> struct ArenaAllocatorTraits;
  59 template <class Alloc>
  60 class Arena {
  61  public:
  62   explicit Arena(const Alloc& alloc,
  63                  size_t minBlockSize = kDefaultMinBlockSize,
  64                  size_t sizeLimit = 0)
  65     : allocAndSize_(alloc, minBlockSize)
  66     , ptr_(nullptr)
  67     , end_(nullptr)
  68     , totalAllocatedSize_(0)
  69     , bytesUsed_(0)
  70     , sizeLimit_(sizeLimit) {
  71   }
  72
  73   ~Arena();
  74
  75   void* allocate(size_t size) {
  76     size = roundUp(size);
  77     bytesUsed_ += size;
  78
  79     if (LIKELY(end_ - ptr_ >= size)) {
  80       // Fast path: there's enough room in the current block
  81       char* r = ptr_;
  82       ptr_ += size;
  83       assert(isAligned(r));
  84       return r;
  85     }
  86
  87     // Not enough room in the current block
  88     void* r = allocateSlow(size);
  89     assert(isAligned(r));
  90     return r;
  91   }
  92
  93   void deallocate(void* p) {
  94     // Deallocate? Never!
  95   }
  96
  97   // Transfer ownership of all memory allocated from "other" to "this".
  98   void merge(Arena&& other);
  99
 100   // Gets the total memory used by the arena
 101   size_t totalSize() const {
 102     return totalAllocatedSize_ + sizeof(Arena);
 103   }
 104
 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 {
 110     return bytesUsed_;
 111   }
 112
 113  private:
 114   // not copyable
 115   Arena(const Arena&) = delete;
 116   Arena& operator=(const Arena&) = delete;
 117
 118   // movable
 119   Arena(Arena&&) = default;
 120   Arena& operator=(Arena&&) = default;
 121
 122   struct Block;
 123   typedef boost::intrusive::slist_member_hook<
 124     boost::intrusive::tag<Arena>> BlockLink;
 125
 126   struct Block {
 127     BlockLink link;
 128
 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);
 136
 137     char* start() {
 138       return reinterpret_cast<char*>(this + 1);
 139     }
 140
 141    private:
 142     Block() { }
 143     ~Block() { }
 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.
 147
 148  public:
 149   static constexpr size_t kDefaultMinBlockSize = 4096 - sizeof(Block);
 150
 151  private:
 152   static constexpr size_t maxAlign = alignof(Block);
 153   static constexpr bool isAligned(uintptr_t address) {
 154     return (address & (maxAlign - 1)) == 0;
 155   }
 156   static bool isAligned(void* p) {
 157     return isAligned(reinterpret_cast<uintptr_t>(p));
 158   }
 159
 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);
 163   }
 164
 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<
 168     Block,
 169     boost::intrusive::member_hook<Block, BlockLink, &Block::link>,
 170     boost::intrusive::constant_time_size<false>,
 171     boost::intrusive::cache_last<true>> BlockList;
 172
 173   void* allocateSlow(size_t size);
 174
 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) {
 180     }
 181
 182     size_t minBlockSize;
 183   };
 184
 185   size_t minBlockSize() const {
 186     return allocAndSize_.minBlockSize;
 187   }
 188   Alloc& alloc() { return allocAndSize_; }
 189   const Alloc& alloc() const { return allocAndSize_; }
 190
 191   AllocAndSize allocAndSize_;
 192   BlockList blocks_;
 193   char* ptr_;
 194   char* end_;
 195   size_t totalAllocatedSize_;
 196   size_t bytesUsed_;
 197   size_t sizeLimit_;
 198 };
 199
 200 /**
 201  * By default, don't pad the given size.
 202  */
 203 template <class Alloc>
 204 struct ArenaAllocatorTraits {
 205   static size_t goodSize(const Alloc& alloc, size_t size) {
 206     return size;
 207   }
 208 };
 209
 210 /**
 211  * Arena-compatible allocator that calls malloc() and free(); see
 212  * goodMallocSize() in Malloc.h for goodSize().
 213  */
 214 class SysAlloc {
 215  public:
 216   void* allocate(size_t size) {
 217     return checkedMalloc(size);
 218   }
 219
 220   void deallocate(void* p) {
 221     free(p);
 222   }
 223 };
 224
 225 template <>
 226 struct ArenaAllocatorTraits<SysAlloc> {
 227   static size_t goodSize(const SysAlloc& alloc, size_t size) {
 228     return goodMallocSize(size);
 229   }
 230 };
 231
 232 /**
 233  * Arena that uses the system allocator (malloc / free)
 234  */
 235 class SysArena : public Arena<SysAlloc> {
 236  public:
 237   explicit SysArena(
 238     size_t minBlockSize = kDefaultMinBlockSize,
 239     size_t sizeLimit = 0)
 240       : Arena<SysAlloc>(SysAlloc(), minBlockSize, sizeLimit) {
 241   }
 242 };
 243
 244 }  // namespace folly
 245
 246 #include "folly/Arena-inl.h"
 247
 248 #endif /* FOLLY_ARENA_H_ */