hphp/util/arena.h

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-2013 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
  22 #include "hphp/util/tiny-vector.h"
  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
  40  * kMinBytes, and all allocations are kMinBytes-aligned.  This mirrors
  41  * the way stack alignment works in gcc, which should be good enough.
  42  *
  43  * Allocations larger than kChunkBytes are acquired directly from
  44  * malloc, and don't (currently) get freed with frames.
  45  *
  46  * The Arena typedef is for convenience when you want a default
  47  * configuration.  Use ArenaImpl if you want something specific.
  48  */
  49 template<size_t kChunkBytes> class ArenaImpl;
  50 typedef ArenaImpl<4096> Arena;
  51
  52 //////////////////////////////////////////////////////////////////////
  53
  54 template<size_t kChunkBytes>
  55 class ArenaImpl {
  56   static const size_t kMinBytes = 16;
  57
  58  public:
  59   ArenaImpl();
  60   ~ArenaImpl();
  61
  62   void* alloc(size_t nbytes);
  63
  64   /*
  65    * Return the amount of memory this arena has handed out via alloc().
  66    */
  67   size_t size() const;
  68
  69   /*
  70    * Return the amount of memory the arena has allocated, but not yet
  71    * handed out via alloc().  This can be used to estimate memory
  72    * usage ignoring arena overhead.
  73    *
  74    * Note that this is only an estimate, because we will include
  75    * fragmentation on the ends of slabs or due to alignment.
  76    */
  77   size_t slackEstimate() const { return kChunkBytes - m_frame.offset; }
  78
  79   /*
  80    * Framed arena allocation.
  81    *
  82    * Nesting allocations between beginFrame() and endFrame() will
  83    * release memory in a stack-like fashion.  Calling endFrame() more
  84    * times than beginFrame() will break things.
  85    *
  86    * Chunks allocated larger than kChunkBytes are not freed until the
  87    * entire arena is destroyed.
  88    *
  89    * Memory is not released back to malloc until the entire arena is
  90    * destroyed.
  91    */
  92   void beginFrame();
  93   void endFrame();
  94
  95  private:
  96   // copying Arenas will end badly.
  97   ArenaImpl(const ArenaImpl&);
  98   ArenaImpl& operator=(const ArenaImpl&);
  99
 100  private:
 101   struct Frame {
 102     Frame*   prev;
 103     uint32_t index;
 104     uint32_t offset;
 105   };
 106
 107  private:
 108   void* allocSlow(size_t nbytes);
 109   void createSlab();
 110
 111  private:
 112   char* m_current;
 113   Frame m_frame;
 114   TinyVector<char*> m_ptrs; // inlines 1 pointer, may not be optimal
 115   PointerList<char> m_externalPtrs;
 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 //////////////////////////////////////////////////////////////////////
 151
 152 } // HPHP
 153
 154 // These global-operator-new declarations cannot be in a namespace,
 155 // but since they take Arena arguments we won't overload anything else.
 156
 157 template<size_t kChunkBytes>
 158 inline void* operator new(size_t nbytes,
 159                           HPHP::ArenaImpl<kChunkBytes>& a) {
 160   return a.alloc(nbytes);
 161 }
 162
 163 template<size_t kChunkBytes>
 164 inline void* operator new[](size_t nbytes,
 165                             HPHP::ArenaImpl<kChunkBytes>& a) {
 166   return a.alloc(nbytes);
 167 }
 168
 169 //////////////////////////////////////////////////////////////////////
 170
 171 #endif