hphp/util/arena.h

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-2015 Facebook, Inc. (http://www.facebook.com)     |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15 */
  16 #ifndef incl_HPHP_UTIL_ARENA_H_
  17 #define incl_HPHP_UTIL_ARENA_H_
  18
  19 #include <vector>
  20 #include <cstdlib>
  21 #include <cstring>
  22
  23 #include "hphp/util/pointer-list.h"
  24
  25 namespace HPHP {
  26
  27 //////////////////////////////////////////////////////////////////////
  28
  29 /**
  30  * Arena/ArenaImpl is an allocator that frees all memory when the
  31  * arena instance is destroyed.  No destructors of allocated objects
  32  * will be called!  It is a bump-pointer allocator.
  33  *
  34  * At various points in the lifetime of the arena, you can introduce a
  35  * new `frame' by calling beginFrame.  This is essentially a marker of
  36  * the current allocator state, which you can pop back to by calling
  37  * endFrame.
  38  *
  39  * Allocations smaller than kMinBytes bytes are rounded up to kMinBytes, and
  40  * all allocations are kMinBytes-aligned.
  41  *
  42  * Allocations larger than kChunkBytes are acquired directly from
  43  * malloc, and don't (currently) get freed with frames.
  44  *
  45  * The Arena typedef is for convenience when you want a default
  46  * configuration.  Use ArenaImpl if you want something specific.
  47  */
  48 template<size_t kChunkBytes> class ArenaImpl;
  49 typedef ArenaImpl<4096> Arena;
  50
  51 //////////////////////////////////////////////////////////////////////
  52
  53 template<size_t kChunkBytes>
  54 class ArenaImpl {
  55   static const size_t kMinBytes = 8;
  56
  57  public:
  58   ArenaImpl();
  59   ~ArenaImpl();
  60
  61   void* alloc(size_t nbytes);
  62
  63   /*
  64    * Return the amount of memory this arena has handed out via alloc().
  65    */
  66   size_t size() const;
  67
  68   /*
  69    * Return the amount of memory the arena has allocated, but not yet
  70    * handed out via alloc().  This can be used to estimate memory
  71    * usage ignoring arena overhead.
  72    *
  73    * Note that this is only an estimate, because we will include
  74    * fragmentation on the ends of slabs or due to alignment.
  75    */
  76   size_t slackEstimate() const { return kChunkBytes - m_frame.offset; }
  77
  78   /*
  79    * Framed arena allocation.
  80    *
  81    * Nesting allocations between beginFrame() and endFrame() will
  82    * release memory in a stack-like fashion.  Calling endFrame() more
  83    * times than beginFrame() will break things.
  84    *
  85    * Chunks allocated larger than kChunkBytes are not freed until the
  86    * entire arena is destroyed.
  87    *
  88    * Memory is not released back to malloc until the entire arena is
  89    * destroyed.
  90    */
  91   void beginFrame();
  92   void endFrame();
  93
  94  private:
  95   // copying Arenas will end badly.
  96   ArenaImpl(const ArenaImpl&);
  97   ArenaImpl& operator=(const ArenaImpl&);
  98
  99  private:
 100   struct Frame {
 101     Frame*   prev;
 102     uint32_t index;
 103     uint32_t offset;
 104   };
 105
 106  private:
 107   void* allocSlow(size_t nbytes);
 108   void createSlab();
 109
 110  private:
 111   char* m_current;
 112   Frame m_frame;
 113   std::vector<char*> m_ptrs;
 114   PointerList<char> m_externalPtrs;
 115   bool m_bypassSlabAlloc;
 116 #ifdef DEBUG
 117   size_t m_externalAllocSize;
 118 #endif
 119 };
 120
 121 //////////////////////////////////////////////////////////////////////
 122
 123 template<size_t kChunkBytes>
 124 inline void* ArenaImpl<kChunkBytes>::alloc(size_t nbytes) {
 125   nbytes = (nbytes + (kMinBytes - 1)) & ~(kMinBytes - 1); // round up
 126   size_t newOff = m_frame.offset + nbytes;
 127   if (newOff <= kChunkBytes) {
 128     char* ptr = m_current + m_frame.offset;
 129     m_frame.offset = newOff;
 130     return ptr;
 131   }
 132   return allocSlow(nbytes);
 133 }
 134
 135 template<size_t kChunkBytes>
 136 inline void ArenaImpl<kChunkBytes>::beginFrame() {
 137   Frame curFrame = m_frame; // don't include the Frame allocation
 138   Frame* oldFrame = static_cast<Frame*>(alloc(sizeof(Frame)));
 139   *oldFrame = curFrame;
 140   m_frame.prev = oldFrame;
 141 }
 142
 143 template<size_t kChunkBytes>
 144 inline void ArenaImpl<kChunkBytes>::endFrame() {
 145   assert(m_frame.prev);
 146   m_frame = *m_frame.prev;
 147   m_current = m_ptrs[m_frame.index];
 148 }
 149
 150 void SetArenaSlabAllocBypass(bool f);
 151
 152 //////////////////////////////////////////////////////////////////////
 153
 154 } // HPHP
 155
 156 // These global-operator-new declarations cannot be in a namespace,
 157 // but since they take Arena arguments we won't overload anything else.
 158
 159 template<size_t kChunkBytes>
 160 inline void* operator new(size_t nbytes,
 161                           HPHP::ArenaImpl<kChunkBytes>& a) {
 162   return a.alloc(nbytes);
 163 }
 164
 165 template<size_t kChunkBytes>
 166 inline void* operator new[](size_t nbytes,
 167                             HPHP::ArenaImpl<kChunkBytes>& a) {
 168   return a.alloc(nbytes);
 169 }
 170
 171 //////////////////////////////////////////////////////////////////////
 172
 173 #endif