hphp/util/arena.h

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-present 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 its memory when the arena
  31  * instance is destroyed.  It is a bump-pointer allocator.
  32  *
  33  * There are two main methods to allocate memory from the arena:
  34  *   1) alloc() allocates raw memory for which no destructor is invoked when the
  35  *      arena is destroyed.
  36  *   2) allocD<C>() allocates memory for an object of class C, whose destructor
  37  *      (or a custom callback) is invoked when the arena is destroyed.
  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.
  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> struct ArenaImpl;
  49 typedef ArenaImpl<4096> Arena;
  50
  51 //////////////////////////////////////////////////////////////////////
  52
  53 template<size_t kChunkBytes>
  54 struct ArenaImpl {
  55  public:
  56   ArenaImpl();
  57   ~ArenaImpl();
  58
  59   /*
  60    * Allocate a raw chunk of memory with `nbytes' bytes.  No destructors will be
  61    * called when the arena is destroyed.
  62    */
  63   void* alloc(size_t nbytes);
  64
  65   /*
  66    * Allocate a chunk of memory large enough to hold an object of class C, and
  67    * register a destructor to be invoked when the arena is destroyed.  A custom
  68    * `dtor' to be invoked can be provided, otherwise C's destructor is invoked.
  69    */
  70   template<class C>
  71   C* allocD();
  72
  73   template<class C, class D>
  74   C* allocD(D dtor);
  75
  76   /*
  77    * Return the amount of memory this arena has handed out via alloc().
  78    */
  79   size_t size() const;
  80
  81   /*
  82    * Return the amount of memory the arena has allocated, but not yet
  83    * handed out via alloc().  This can be used to estimate memory
  84    * usage ignoring arena overhead.
  85    *
  86    * Note that this is only an estimate, because we will include
  87    * fragmentation on the ends of slabs or due to alignment.
  88    */
  89   size_t slackEstimate() const { return kChunkBytes - m_offset; }
  90
  91  private:
  92   struct Destroyer {
  93     void* obj;
  94     void (*dtor)(void*);
  95     Destroyer* next;
  96   };
  97
  98   // copying Arenas will end badly.
  99   ArenaImpl(const ArenaImpl&);
 100   ArenaImpl& operator=(const ArenaImpl&);
 101
 102   static const size_t kMinBytes = 8;
 103
 104   void* allocSlow(size_t nbytes);
 105   void createSlab();
 106
 107   char* m_current;
 108   uint32_t m_offset;
 109   std::vector<char*> m_ptrs;
 110   PointerList<char> m_externalPtrs;
 111   Destroyer* m_dtors;
 112   bool m_bypassSlabAlloc;
 113 #ifndef NDEBUG
 114   size_t m_externalAllocSize;
 115 #endif
 116 };
 117
 118 //////////////////////////////////////////////////////////////////////
 119
 120 template<size_t kChunkBytes>
 121 inline void* ArenaImpl<kChunkBytes>::alloc(size_t nbytes) {
 122   nbytes = (nbytes + (kMinBytes - 1)) & ~(kMinBytes - 1); // round up
 123   size_t newOff = m_offset + nbytes;
 124   if (newOff <= kChunkBytes) {
 125     char* ptr = m_current + m_offset;
 126     m_offset = newOff;
 127     return ptr;
 128   }
 129   return allocSlow(nbytes);
 130 }
 131
 132 template<size_t kChunkBytes>
 133 template<class C, class D>
 134 inline C* ArenaImpl<kChunkBytes>::allocD(D dtor) {
 135   auto ptr = (C*)alloc(sizeof(C));
 136   auto dtorPtr = (Destroyer*)alloc(sizeof(Destroyer));
 137   dtorPtr->obj = ptr;
 138   dtorPtr->dtor = dtor;
 139   dtorPtr->next = m_dtors;
 140   m_dtors = dtorPtr;
 141   return ptr;
 142 }
 143
 144 template<size_t kChunkBytes>
 145 template<class C>
 146 inline C* ArenaImpl<kChunkBytes>::allocD() {
 147   return allocD([](void* p) { static_cast<C*>(p)->~C(); });
 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