MMgc/GCAlloc.h

   1 /* -*- Mode: C++; c-basic-offset: 4; indent-tabs-mode: t; tab-width: 4 -*- */
   2 /* ***** BEGIN LICENSE BLOCK *****
   3  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   4  *
   5  * The contents of this file are subject to the Mozilla Public License Version
   6  * 1.1 (the "License"); you may not use this file except in compliance with
   7  * the License. You may obtain a copy of the License at
   8  * http://www.mozilla.org/MPL/
   9  *
  10  * Software distributed under the License is distributed on an "AS IS" basis,
  11  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  12  * for the specific language governing rights and limitations under the
  13  * License.
  14  *
  15  * The Original Code is [Open Source Virtual Machine.].
  16  *
  17  * The Initial Developer of the Original Code is
  18  * Adobe System Incorporated.
  19  * Portions created by the Initial Developer are Copyright (C) 2004-2006
  20  * the Initial Developer. All Rights Reserved.
  21  *
  22  * Contributor(s):
  23  *   Adobe AS3 Team
  24  *
  25  * Alternatively, the contents of this file may be used under the terms of
  26  * either the GNU General Public License Version 2 or later (the "GPL"), or
  27  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  28  * in which case the provisions of the GPL or the LGPL are applicable instead
  29  * of those above. If you wish to allow use of your version of this file only
  30  * under the terms of either the GPL or the LGPL, and not to allow others to
  31  * use your version of this file under the terms of the MPL, indicate your
  32  * decision by deleting the provisions above and replace them with the notice
  33  * and other provisions required by the GPL or the LGPL. If you do not delete
  34  * the provisions above, a recipient may use your version of this file under
  35  * the terms of any one of the MPL, the GPL or the LGPL.
  36  *
  37  * ***** END LICENSE BLOCK ***** */
  38
  39 #ifndef __GCAlloc__
  40 #define __GCAlloc__
  41
  42
  43 namespace MMgc
  44 {
  45         class GCAllocBase {
  46         public:
  47                 virtual ~GCAllocBase();
  48                 virtual void Free(const void* item) = 0;
  49         };
  50
  51         // Some common functionality for GCAlloc and GCLargeAlloc follows.  (Could be
  52         // in a separate header file.)
  53
  54         /**
  55          * Common block header for GCAlloc and GCLargeAlloc.
  56          */
  57         struct GCBlockHeader
  58         {
  59                 GC*                             gc;             // The GC that owns this block
  60                 GCAllocBase*    alloc;  // the allocator that owns this block
  61                 GCBlockHeader*  next;   // The next block in the list of blocks for the allocator
  62                 uint32_t                size;   // Size of objects stored in this block
  63         };
  64
  65         GCBlockHeader* GetBlockHeader(const void* item);
  66
  67         /**
  68          *
  69          * This is a fast, fixed-size memory allocator for garbage-collected
  70          * objects.
  71          *
  72          * Memory is allocated from the system on 4096-byte aligned boundaries,
  73          * which corresponds to the size of an OS page in Windows XP.  Allocation
  74          * of pages is performed via the GCPageAlloc class.
  75          *
  76          * In each 4096-byte block, there is a block header with marked bits,
  77          * finalize bits, the pointer to the next free item and "recycling"
  78          * free item linked list.
  79          *
  80          * The bits of the "marked" bitmap are controlled by the SetMark method.
  81          *
  82          * The bits of the "finalize" bitmap are set when an item is
  83          * allocated.  The value for the finalize bit is passed in as a
  84          * parameter to the allocation call.
  85          *
  86          * When the Sweep method is invoked, all objects that are not marked
  87          * with the specified mark flag are disposed of.  If the corresponding
  88          * finalize bit is set, the GCObject destructor is invoked on that
  89          * item.
  90          *
  91          * When an allocation is requested and there are no more free
  92          * entries, GCAlloc will request that a garbage collection take
  93          * place.  It will allocate new blocks if more than 20% of its
  94          * blocks are used after the collection, targeting a 5:1
  95          * heap size / minimim heap size ratio.
  96          *
  97          */
  98         class GCAlloc : public GCAllocBase
  99         {
 100                 friend class GC;
 101                 friend class GCAllocIterator;
 102
 103                 struct GCBlock;
 104         public:
 105                 enum ItemBit { kMark=1, kQueued=2, kFinalize=4, kHasWeakRef=8, kFreelist=kMark|kQueued };
 106
 107                 GCAlloc(GC* gc, int itemSize, bool containsPointers, bool isRC, int sizeClassIndex);
 108                 ~GCAlloc();
 109
 110 #if defined DEBUG || defined MMGC_MEMORY_PROFILER
 111                 void* Alloc(size_t size, int flags);
 112 #else
 113                 void* Alloc(int flags);
 114 #endif
 115                 virtual void Free(const void* item);
 116
 117                 void Finalize();
 118                 void ClearMarks();
 119 #ifdef _DEBUG
 120                 void CheckMarks();
 121                 void CheckFreelist();
 122 #endif
 123
 124                 static int SetMark(const void *item);
 125
 126                 // Not a hot method
 127                 static int SetFinalize(const void *item);
 128
 129 #ifdef _DEBUG
 130                 static bool IsWhite(const void *item);
 131 #endif // _DEBUG
 132
 133                 static int GetMark(const void *item);
 134
 135                 static void *FindBeginning(const void *item);
 136
 137                 static bool IsMarkedThenMakeQueued(const void *item);
 138
 139                 static bool IsQueued(const void *item);
 140
 141                 static bool IsQueued(GCBlock *block, int index);
 142
 143                 // not a hot method
 144                 static void ClearFinalized(const void *item);
 145
 146                 // not a hot method
 147                 static int IsFinalized(const void *item);
 148
 149                 // not a hot method
 150                 static int HasWeakRef(const void *item);
 151
 152                 // Very hot: called in the inner loop of GC::MarkItem
 153                 static bool ContainsPointers(const void *item);
 154
 155                 // Can be hot - used by PinStackObjects
 156                 static bool IsRCObject(const void *item);
 157
 158                 static bool IsUnmarkedPointer(const void *val);
 159
 160                 REALLY_INLINE uint32_t GetItemSize() { return m_itemSize; }
 161                 REALLY_INLINE int GetNumAlloc() const { return m_numAlloc; }
 162                 REALLY_INLINE int GetMaxAlloc() const { return m_maxAlloc; }
 163                 REALLY_INLINE int GetNumBlocks() const { return m_numBlocks; }
 164
 165                 REALLY_INLINE bool ContainsPointers() const { return containsPointers; }
 166                 REALLY_INLINE bool ContainsRCObjects() const { return containsRCObjects; }
 167
 168                 void GetBitsPages(void **pages);
 169
 170                 // not a hot method
 171                 static void SetHasWeakRef(const void *item, bool to);
 172
 173                 //This method returns the number bytes allocated for GC objects
 174                 size_t GetBytesInUse();
 175
 176                 //This method is for more fine grained allocation details
 177                 //It reports the total number of bytes requested (i.e. ask size) and
 178                 //the number of bytes actually allocated.  The latter is the same
 179                 //number as reported by GetBytesInUse()
 180                 void GetUsageInfo(size_t& totalAskSize, size_t& totalAllocated);
 181
 182 #ifdef MMGC_MEMORY_PROFILER
 183                 size_t GetTotalAskSize() { return m_totalAskSize; }
 184 #endif
 185
 186         private:
 187                 const static int kBlockSize = 4096;
 188
 189                 const static short kFlagNeedsSweeping = 1;      // set if the block had finalized objects and needs to be swept
 190                 const static short kFlagWeakRefs = 2;           // set if the block may have weak refs and we should check during free
 191
 192                 // Objects on the free list all have a next pointer in the first word and
 193                 // the object index within its block as the second word.  Only the low 16 bits
 194                 // of the second word are significant: the reference counter messes around
 195                 // with the high 16 bits during pinning; it may pin dead objects.  Those that
 196                 // use the index must be careful to mask off the high bits.
 197
 198                 struct GCBlock : GCBlockHeader
 199                 {
 200                         GCBlock* prev;                  // the previous block on the list of all blocks ('next' is in the block header)
 201                         void*  firstFree;       // first item on free list
 202                         GCBlock *prevFree;              // the previous block on the lists of blocks with free or sweepable objects
 203                         GCBlock *nextFree;              // the next block on the lists of blocks with free or sweepable objects
 204                         uint32_t* bits;                 // the header bits for this block
 205                         short numFree;                  // the number of free objects in this block
 206                         uint8_t slowFlags;              // flags for special circumstances: kFlagNeedsSweeping, etc
 207                         bool finalizeState:1;   // whether we've been visited during the Finalize stage
 208                         char   *items;                  // pointer to the array of objects in the block
 209
 210                         int GetCount() const;
 211                         uint32_t *GetBits() const;
 212                         void FreeSweptItem(const void *item, int index);
 213                         int needsSweeping();
 214                         void setNeedsSweeping(int v);
 215                 };
 216
 217                 static GCBlock *GetBlock(const void *item);
 218
 219 #ifdef MMGC_MEMORY_INFO
 220                 static void VerifyFreeBlockIntegrity(const void* item, uint32_t size, uint32_t limit=~0U);
 221 #endif
 222
 223                 // The list of chunk blocks
 224                 GCBlock* m_firstBlock;
 225                 GCBlock* m_lastBlock;
 226
 227                 // The lowest priority block that has free items
 228                 GCBlock* m_firstFree;
 229
 230                 // List of blocks that need sweeping
 231                 GCBlock* m_needsSweeping;
 232
 233                 // Quick list of free objects.  See comment in GCAlloc.cpp for general information.
 234
 235                 void *m_qList;                          // Linked list of some free objects for this allocator
 236                 int   m_qBudget;                        // Number of items we can yet free before obtaining a larger budget
 237                 int       m_qBudgetObtained;    // Quick list budget actually obtained from the GC for this allocator
 238
 239                 int    m_itemsPerBlock;
 240                 uint32_t    m_itemSize;
 241                 int m_numBitmapBytes;
 242                 int m_sizeClassIndex;
 243
 244 #ifdef MMGC_MEMORY_PROFILER
 245                 size_t m_totalAskSize;
 246 #endif
 247
 248                 bool m_bitsInPage;
 249
 250                 int    m_maxAlloc;
 251                 int    m_numAlloc;
 252                 int    m_numBlocks;
 253
 254                 // fast divide numbers
 255                 uint16_t multiple;
 256                 uint16_t shift;
 257
 258                 bool containsPointers;
 259                 bool containsRCObjects;
 260                 bool m_finalized;
 261
 262 #ifdef _DEBUG
 263                 bool IsOnEitherList(GCBlock *b);
 264                 void VerifyNotFree(GCBlock* b, const void *item);
 265 #endif
 266
 267                 GCBlock* CreateChunk(int flags);
 268                 void UnlinkChunk(GCBlock *b);
 269                 void FreeChunk(GCBlock* b);
 270
 271                 // not a hot method
 272                 void AddToFreeList(GCBlock *b);
 273
 274                 // not a hot method
 275                 void RemoveFromFreeList(GCBlock *b);
 276
 277                 // not a hot method
 278                 void AddToSweepList(GCBlock *b);
 279
 280                 // not a hot method
 281                 void RemoveFromSweepList(GCBlock *b);
 282
 283 #if defined DEBUG || defined MMGC_MEMORY_PROFILER
 284                 void* AllocSlow(size_t askSize, int flags);
 285                 void* AllocFromQuickList(size_t askSize, int flags);
 286 #else
 287                 void* AllocSlow(int flags);
 288                 void* AllocFromQuickList(int flags);
 289 #endif
 290                 void FillQuickList(GCBlock* b);
 291                 void CoalesceQuickList();
 292                 void QuickListBudgetExhausted();
 293                 void FreeSlow(GCBlock* b, int index, const void* item);
 294                 void ClearNonRCObject(void* item, size_t size);
 295
 296                 bool Sweep(GCBlock *b);
 297                 void SweepGuts(GCBlock *b);
 298
 299                 void ClearMarks(GCAlloc::GCBlock* block);
 300                 void SweepNeedsSweeping();
 301
 302 #ifdef _DEBUG
 303                 static int ConservativeGetMark(const void *item, bool bogusPointerReturnValue);
 304 #endif
 305
 306                 // very hot
 307                 static int GetIndex(const GCBlock *block, const void *item);
 308
 309                 static int SetBit(GCBlock *block, int index, int bit);
 310
 311                 static int GetBit(GCBlock *block, int index, int bit);
 312
 313                 static void ClearBits(GCBlock *block, int index, int bits);
 314
 315                 static void Clear4BitsAndSet(GCBlock *block, int index, int bit);
 316
 317                 // not a hot method
 318                 static void ClearQueued(const void *item);
 319
 320 #ifdef _DEBUG
 321                 static bool IsPointerIntoGCObject(const void *item);
 322
 323                 static bool IsWhite(GCBlock *block, int index);
 324 #endif
 325
 326                 void ComputeMultiplyShift(uint16_t d, uint16_t &muli, uint16_t &shft);
 327
 328         protected:
 329                 GC *m_gc;
 330
 331         public:
 332                 static GCBlock* Next(GCBlock* b);
 333         };
 334
 335         /**
 336          * A utility class used by the marker to handle mark stack overflow: it abstracts
 337          * iterating across marked, non-free objects in one allocator instance.
 338          *
 339          * No blocks must be added or removed during the iteration.  If an object's
 340          * bits are changed, those changes will visible to the iterator if the object has
 341          * not yet been reached by the iteration.
 342          */
 343         class GCAllocIterator
 344         {
 345         public:
 346                 GCAllocIterator(MMgc::GCAlloc* alloc);
 347
 348                 bool GetNextMarkedObject(void*& out_ptr, uint32_t& out_size);
 349
 350         private:
 351                 GCAlloc* const alloc;
 352                 GCAlloc::GCBlock* block;
 353                 uint32_t idx;
 354                 uint32_t limit;
 355                 uint32_t size;
 356         };
 357 }
 358
 359 #endif /* __GCAlloc__ */