kjs/collector.h

   1 // -*- c-basic-offset: 2 -*-
   2 /*
   3  *  This file is part of the KDE libraries
   4  *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
   5  *  Copyright (C) 2001 Peter Kelly (pmk@post.com)
   6  *  Copyright (C) 2003, 2004, 2005, 2006, 2007 Apple Inc. All rights reserved.
   7  *  Copyright (C) 2007 Maksim Orlovich (maksim@kde.org)
   8  *
   9  *  This library is free software; you can redistribute it and/or
  10  *  modify it under the terms of the GNU Lesser General Public
  11  *  License as published by the Free Software Foundation; either
  12  *  version 2 of the License, or (at your option) any later version.
  13  *
  14  *  This library is distributed in the hope that it will be useful,
  15  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  17  *  Lesser General Public License for more details.
  18  *
  19  *  You should have received a copy of the GNU Lesser General Public
  20  *  License along with this library; if not, write to the Free Software
  21  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  22  *
  23  */
  24
  25 #ifndef KJSCOLLECTOR_H_
  26 #define KJSCOLLECTOR_H_
  27
  28 #include <wtf/HashCountedSet.h>
  29 #include <cstring>
  30
  31 #define KJS_MEM_LIMIT 500000
  32
  33 namespace KJS {
  34   class JSCell;
  35   class JSValue;
  36   class CollectorBlock;
  37
  38   /**
  39    * @short Garbage collector.
  40    */
  41   class KJS_EXPORT Collector {
  42     // disallow direct construction/destruction
  43     Collector();
  44   public:
  45     /**
  46      * Register an object with the collector. The following assumptions are
  47      * made:
  48      * @li the operator new() of the object class is overloaded.
  49      * @li operator delete() has been overloaded as well and does not free
  50      * the memory on its own.
  51      *
  52      * @param s Size of the memory to be registered.
  53      * @return A pointer to the allocated memory.
  54      */
  55     static void* allocate(size_t s);
  56     /**
  57      * Run the garbage collection. This involves calling the delete operator
  58      * on each object and freeing the used memory.
  59      */
  60     static bool collect();
  61
  62     static const size_t minExtraCostSize = 256;
  63
  64     static void reportExtraMemoryCost(size_t cost);
  65
  66     static size_t size();
  67     static bool isOutOfMemory() { return memoryFull; }
  68
  69 #ifdef KJS_DEBUG_MEM
  70     /**
  71      * Check that nothing is left when the last interpreter gets deleted
  72      */
  73     static void finalCheck();
  74 #endif
  75
  76     static void protect(JSValue *);
  77     static void unprotect(JSValue *);
  78
  79     static size_t numInterpreters();
  80     static size_t numProtectedObjects();
  81     static HashCountedSet<const char*>* rootObjectTypeCounts();
  82
  83     class Thread;
  84     static void registerThread();
  85
  86     static bool isCellMarked(const JSCell*);
  87     static void markCell(JSCell*);
  88
  89   private:
  90     static const CollectorBlock* cellBlock(const JSCell*);
  91     static CollectorBlock* cellBlock(JSCell*);
  92     static size_t cellOffset(const JSCell*);
  93
  94     static void recordExtraCost(size_t);
  95     static void markProtectedObjects();
  96     static void markCurrentThreadConservatively();
  97     static void markOtherThreadConservatively(Thread*);
  98     static void markStackObjectsConservatively();
  99     static void markStackObjectsConservatively(void *start, void *end);
 100
 101     static bool memoryFull;
 102     static void reportOutOfMemoryToAllInterpreters();
 103   };
 104
 105   // tunable parameters
 106   template<size_t bytesPerWord> struct CellSize;
 107
 108   // cell size needs to be a power of two for certain optimizations in collector.cpp
 109   // below also assume it's divisible by 8, and that block size is divisible by it
 110   template<> struct CellSize<4> { static const size_t m_value = 32; }; // 32-bit
 111   template<> struct CellSize<8> { static const size_t m_value = 64; }; // 64-bit
 112   const size_t BLOCK_SIZE = 16 * 4096; // 64k
 113
 114   const size_t BLOCK_OFFSET_MASK = BLOCK_SIZE - 1;
 115   const size_t BLOCK_MASK = ~BLOCK_OFFSET_MASK;
 116
 117   const size_t CELL_SIZE = CellSize<sizeof(void*)>::m_value;
 118   const size_t CELL_ARRAY_LENGTH = (CELL_SIZE / sizeof(double));
 119   const size_t CELL_MASK = CELL_SIZE - 1;
 120
 121   // For each block, we can have at /most/ BLOCK_SIZE/CELL_SIZE entries.
 122   // Sice the bitmap accordingly, don't try to be fancy
 123   const size_t BITMAP_SIZE = (BLOCK_SIZE / CELL_SIZE + 7) / 8;
 124   const size_t BITMAP_WORDS = (BITMAP_SIZE + 3) / sizeof(uint32_t);
 125
 126   // In each block, we have 3 bitmaps (mark for all blocks, extension + allocd for oversize cell blocks),
 127   // as well as an int and a pointer
 128   const size_t BLOCK_METADATA_SIZE = 3 * 4 * BITMAP_WORDS + sizeof(uint32_t) + sizeof(void*);
 129   const size_t CELLS_PER_BLOCK     = (BLOCK_SIZE - BLOCK_METADATA_SIZE) / CELL_SIZE;
 130
 131   struct CollectorBitmap {
 132     uint32_t bits[BITMAP_WORDS];
 133     bool get(size_t n) const { return !!(bits[n >> 5] & (1 << (n & 0x1F))); }
 134     void set(size_t n) { bits[n >> 5] |= (1 << (n & 0x1F)); }
 135     void clear(size_t n) { bits[n >> 5] &= ~(1 << (n & 0x1F)); }
 136     void clearAll() { std::memset(bits, 0, sizeof(bits)); }
 137   };
 138
 139   struct CollectorCell {
 140     union {
 141       double memory[CELL_ARRAY_LENGTH];
 142       struct {
 143         void* zeroIfFree;
 144         ptrdiff_t next;
 145       } freeCell;
 146     } u;
 147   };
 148
 149   class CollectorBlock {
 150   public:
 151     CollectorCell cells[CELLS_PER_BLOCK];
 152     uint32_t usedCells;
 153     CollectorCell* freeList;
 154     CollectorBitmap marked;
 155     CollectorBitmap allocd;
 156     CollectorBitmap trailer;
 157   };
 158
 159   inline const CollectorBlock* Collector::cellBlock(const JSCell* cell)
 160   {
 161     return reinterpret_cast<const CollectorBlock*>(reinterpret_cast<uintptr_t>(cell) & BLOCK_MASK);
 162   }
 163
 164   inline CollectorBlock* Collector::cellBlock(JSCell* cell)
 165   {
 166     return const_cast<CollectorBlock*>(cellBlock(const_cast<const JSCell*>(cell)));
 167   }
 168
 169   inline size_t Collector::cellOffset(const JSCell* cell)
 170   {
 171     return (reinterpret_cast<uintptr_t>(cell) & BLOCK_OFFSET_MASK) / CELL_SIZE;
 172   }
 173
 174   inline bool Collector::isCellMarked(const JSCell* cell)
 175   {
 176     return cellBlock(cell)->marked.get(cellOffset(cell));
 177   }
 178
 179   inline void Collector::markCell(JSCell* cell)
 180   {
 181     cellBlock(cell)->marked.set(cellOffset(cell));
 182   }
 183
 184   inline void Collector::reportExtraMemoryCost(size_t cost)
 185   {
 186     if (cost > minExtraCostSize)
 187       recordExtraCost(cost / (CELL_SIZE * 2));
 188   }
 189 }
 190
 191 #endif /* _KJSCOLLECTOR_H_ */