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 <limits>
  22 #include <stdexcept>
  23 #include <utility>
  24 #include <boost/intrusive/slist.hpp>
  25
  26 #include <folly/Conv.h>
  27 #include <folly/Likely.h>
  28 #include <folly/Malloc.h>
  29 #include <folly/Memory.h>
  30
  31 namespace folly {
  32
  33 /**
  34  * Simple arena: allocate memory which gets freed when the arena gets
  35  * destroyed.
  36  *
  37  * The arena itself allocates memory using a custom allocator which provides
  38  * the following interface (same as required by StlAllocator in StlAllocator.h)
  39  *
  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.
  44  *
  45  *   void deallocate(void* ptr);
  46  *      Deallocate a previously allocated block.
  47  *
  48  * You may also specialize ArenaAllocatorTraits for your allocator type to
  49  * provide:
  50  *
  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.
  57  *
  58  * An implementation that uses malloc() / free() is defined below, see SysArena.
  59  */
  60 template <class Alloc> struct ArenaAllocatorTraits;
  61 template <class Alloc>
  62 class Arena {
  63  public:
  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)
  69     , ptr_(nullptr)
  70     , end_(nullptr)
  71     , totalAllocatedSize_(0)
  72     , bytesUsed_(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_));
  78     }
  79   }
  80
  81   ~Arena();
  82
  83   void* allocate(size_t size) {
  84     size = roundUp(size);
  85     bytesUsed_ += size;
  86
  87     if (LIKELY(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) {
 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  private:
 122   // not copyable
 123   Arena(const Arena&) = delete;
 124   Arena& operator=(const Arena&) = delete;
 125
 126   // movable
 127   Arena(Arena&&) = default;
 128   Arena& operator=(Arena&&) = default;
 129
 130   struct Block;
 131   typedef boost::intrusive::slist_member_hook<
 132     boost::intrusive::tag<Arena>> BlockLink;
 133
 134   struct Block {
 135     BlockLink link;
 136
 137     // Allocate a block with at least size bytes of storage.
 138     // If allowSlack is true, allocate more than size bytes if convenient
 139     // (via ArenaAllocatorTraits::goodSize()) as we'll try to pack small
 140     // allocations in this block.
 141     static std::pair<Block*, size_t> allocate(
 142         Alloc& alloc, size_t size, bool allowSlack);
 143     void deallocate(Alloc& alloc);
 144
 145     char* start() {
 146       return reinterpret_cast<char*>(this + 1);
 147     }
 148
 149    private:
 150     Block() { }
 151     ~Block() { }
 152   } __attribute__((__aligned__));
 153   // This should be alignas(std::max_align_t) but neither alignas nor
 154   // max_align_t are supported by gcc 4.6.2.
 155
 156  public:
 157   static constexpr size_t kDefaultMinBlockSize = 4096 - sizeof(Block);
 158   static constexpr size_t kNoSizeLimit = 0;
 159   static constexpr size_t kDefaultMaxAlign = alignof(Block);
 160   static constexpr size_t kBlockOverhead = sizeof(Block);
 161
 162  private:
 163   bool isAligned(uintptr_t address) const {
 164     return (address & (maxAlign_ - 1)) == 0;
 165   }
 166   bool isAligned(void* p) const {
 167     return isAligned(reinterpret_cast<uintptr_t>(p));
 168   }
 169
 170   // Round up size so it's properly aligned
 171   size_t roundUp(size_t size) const {
 172     return (size + maxAlign_ - 1) & ~(maxAlign_ - 1);
 173   }
 174
 175   // cache_last<true> makes the list keep a pointer to the last element, so we
 176   // have push_back() and constant time splice_after()
 177   typedef boost::intrusive::slist<
 178     Block,
 179     boost::intrusive::member_hook<Block, BlockLink, &Block::link>,
 180     boost::intrusive::constant_time_size<false>,
 181     boost::intrusive::cache_last<true>> BlockList;
 182
 183   void* allocateSlow(size_t size);
 184
 185   // Empty member optimization: package Alloc with a non-empty member
 186   // in case Alloc is empty (as it is in the case of SysAlloc).
 187   struct AllocAndSize : public Alloc {
 188     explicit AllocAndSize(const Alloc& a, size_t s)
 189       : Alloc(a), minBlockSize(s) {
 190     }
 191
 192     size_t minBlockSize;
 193   };
 194
 195   size_t minBlockSize() const {
 196     return allocAndSize_.minBlockSize;
 197   }
 198   Alloc& alloc() { return allocAndSize_; }
 199   const Alloc& alloc() const { return allocAndSize_; }
 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
 211 template <class Alloc>
 212 struct IsArenaAllocator<Arena<Alloc>> : std::true_type { };
 213
 214 /**
 215  * By default, don't pad the given size.
 216  */
 217 template <class Alloc>
 218 struct ArenaAllocatorTraits {
 219   static size_t goodSize(const Alloc& alloc, size_t size) {
 220     return size;
 221   }
 222 };
 223
 224 template <>
 225 struct ArenaAllocatorTraits<SysAlloc> {
 226   static size_t goodSize(const SysAlloc& alloc, size_t size) {
 227     return goodMallocSize(size);
 228   }
 229 };
 230
 231 /**
 232  * Arena that uses the system allocator (malloc / free)
 233  */
 234 class SysArena : public Arena<SysAlloc> {
 235  public:
 236   explicit SysArena(size_t minBlockSize = kDefaultMinBlockSize,
 237                     size_t sizeLimit = kNoSizeLimit,
 238                     size_t maxAlign = kDefaultMaxAlign)
 239     : Arena<SysAlloc>(SysAlloc(), minBlockSize, sizeLimit, maxAlign) {
 240   }
 241 };
 242
 243 template <>
 244 struct IsArenaAllocator<SysArena> : std::true_type { };
 245
 246 }  // namespace folly
 247
 248 #include <folly/Arena-inl.h>
 249
 250 #endif /* FOLLY_ARENA_H_ */