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  *
   8  *  This library is free software; you can redistribute it and/or
   9  *  modify it under the terms of the GNU Lesser General Public
  10  *  License as published by the Free Software Foundation; either
  11  *  version 2 of the License, or (at your option) any later version.
  12  *
  13  *  This library is distributed in the hope that it will be useful,
  14  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16  *  Lesser General Public License for more details.
  17  *
  18  *  You should have received a copy of the GNU Lesser General Public
  19  *  License along with this library; if not, write to the Free Software
  20  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  21  *
  22  */
  23
  24 #ifndef KJSCOLLECTOR_H_
  25 #define KJSCOLLECTOR_H_
  26
  27 #include <string.h>
  28 #include <wtf/HashCountedSet.h>
  29 #include <wtf/Platform.h>
  30
  31 namespace KJS {
  32
  33   class JSCell;
  34   class JSValue;
  35   class CollectorBlock;
  36
  37   class Collector {
  38   public:
  39     static void* allocate(size_t s);
  40     static void* allocateNumber(size_t s);
  41     static bool collect();
  42     static bool isBusy(); // true if an allocation or collection is in progress
  43
  44     static const size_t minExtraCostSize = 256;
  45
  46     static void reportExtraMemoryCost(size_t cost);
  47
  48     static size_t size();
  49
  50     static void protect(JSValue*);
  51     static void unprotect(JSValue*);
  52
  53     static void collectOnMainThreadOnly(JSValue*);
  54
  55     static size_t globalObjectCount();
  56     static size_t protectedObjectCount();
  57     static size_t protectedGlobalObjectCount();
  58     static HashCountedSet<const char*>* protectedObjectTypeCounts();
  59
  60     class Thread;
  61     static void registerThread();
  62
  63     static void registerAsMainThread();
  64
  65     static bool isCellMarked(const JSCell*);
  66     static void markCell(JSCell*);
  67
  68     enum HeapType { PrimaryHeap, NumberHeap };
  69
  70   private:
  71     template <Collector::HeapType heapType> static void* heapAllocate(size_t s);
  72     template <Collector::HeapType heapType> static size_t sweep(bool);
  73     static const CollectorBlock* cellBlock(const JSCell*);
  74     static CollectorBlock* cellBlock(JSCell*);
  75     static size_t cellOffset(const JSCell*);
  76
  77     Collector();
  78
  79     static void recordExtraCost(size_t);
  80     static void markProtectedObjects();
  81     static void markMainThreadOnlyObjects();
  82     static void markCurrentThreadConservatively();
  83     static void markOtherThreadConservatively(Thread*);
  84     static void markStackObjectsConservatively();
  85     static void markStackObjectsConservatively(void* start, void* end);
  86
  87     static size_t mainThreadOnlyObjectCount;
  88     static bool memoryFull;
  89     static void reportOutOfMemoryToAllExecStates();
  90   };
  91
  92   // tunable parameters
  93   template<size_t bytesPerWord> struct CellSize;
  94
  95   // cell size needs to be a power of two for certain optimizations in collector.cpp
  96   template<> struct CellSize<sizeof(uint32_t)> { static const size_t m_value = 32; }; // 32-bit
  97   template<> struct CellSize<sizeof(uint64_t)> { static const size_t m_value = 64; }; // 64-bit
  98   const size_t BLOCK_SIZE = 16 * 4096; // 64k
  99
 100   // derived constants
 101   const size_t BLOCK_OFFSET_MASK = BLOCK_SIZE - 1;
 102   const size_t BLOCK_MASK = ~BLOCK_OFFSET_MASK;
 103   const size_t MINIMUM_CELL_SIZE = CellSize<sizeof(void*)>::m_value;
 104   const size_t CELL_ARRAY_LENGTH = (MINIMUM_CELL_SIZE / sizeof(double)) + (MINIMUM_CELL_SIZE % sizeof(double) != 0 ? sizeof(double) : 0);
 105   const size_t CELL_SIZE = CELL_ARRAY_LENGTH * sizeof(double);
 106   const size_t SMALL_CELL_SIZE = CELL_SIZE / 2;
 107   const size_t CELL_MASK = CELL_SIZE - 1;
 108   const size_t CELL_ALIGN_MASK = ~CELL_MASK;
 109   const size_t CELLS_PER_BLOCK = (BLOCK_SIZE * 8 - sizeof(uint32_t) * 8 - sizeof(void *) * 8 - 2 * (7 + 3 * 8)) / (CELL_SIZE * 8 + 2);
 110   const size_t SMALL_CELLS_PER_BLOCK = 2 * CELLS_PER_BLOCK;
 111   const size_t BITMAP_SIZE = (CELLS_PER_BLOCK + 7) / 8;
 112   const size_t BITMAP_WORDS = (BITMAP_SIZE + 3) / sizeof(uint32_t);
 113
 114   struct CollectorBitmap {
 115     uint32_t bits[BITMAP_WORDS];
 116     bool get(size_t n) const { return !!(bits[n >> 5] & (1 << (n & 0x1F))); }
 117     void set(size_t n) { bits[n >> 5] |= (1 << (n & 0x1F)); }
 118     void clear(size_t n) { bits[n >> 5] &= ~(1 << (n & 0x1F)); }
 119     void clearAll() { memset(bits, 0, sizeof(bits)); }
 120   };
 121
 122   struct CollectorCell {
 123     union {
 124       double memory[CELL_ARRAY_LENGTH];
 125       struct {
 126         void* zeroIfFree;
 127         ptrdiff_t next;
 128       } freeCell;
 129     } u;
 130   };
 131
 132   struct SmallCollectorCell {
 133     union {
 134       double memory[CELL_ARRAY_LENGTH / 2];
 135       struct {
 136         void* zeroIfFree;
 137         ptrdiff_t next;
 138       } freeCell;
 139     } u;
 140   };
 141
 142   class CollectorBlock {
 143   public:
 144     CollectorCell cells[CELLS_PER_BLOCK];
 145     uint32_t usedCells;
 146     CollectorCell* freeList;
 147     CollectorBitmap marked;
 148     CollectorBitmap collectOnMainThreadOnly;
 149   };
 150
 151   class SmallCellCollectorBlock {
 152   public:
 153     SmallCollectorCell cells[SMALL_CELLS_PER_BLOCK];
 154     uint32_t usedCells;
 155     SmallCollectorCell* freeList;
 156     CollectorBitmap marked;
 157     CollectorBitmap collectOnMainThreadOnly;
 158   };
 159
 160   inline const CollectorBlock* Collector::cellBlock(const JSCell* cell)
 161   {
 162     return reinterpret_cast<const CollectorBlock*>(reinterpret_cast<uintptr_t>(cell) & BLOCK_MASK);
 163   }
 164
 165   inline CollectorBlock* Collector::cellBlock(JSCell* cell)
 166   {
 167     return const_cast<CollectorBlock*>(cellBlock(const_cast<const JSCell*>(cell)));
 168   }
 169
 170   inline size_t Collector::cellOffset(const JSCell* cell)
 171   {
 172     return (reinterpret_cast<uintptr_t>(cell) & BLOCK_OFFSET_MASK) / CELL_SIZE;
 173   }
 174
 175   inline bool Collector::isCellMarked(const JSCell* cell)
 176   {
 177     return cellBlock(cell)->marked.get(cellOffset(cell));
 178   }
 179
 180   inline void Collector::markCell(JSCell* cell)
 181   {
 182     cellBlock(cell)->marked.set(cellOffset(cell));
 183   }
 184
 185   inline void Collector::reportExtraMemoryCost(size_t cost)
 186   {
 187     if (cost > minExtraCostSize)
 188       recordExtraCost(cost / (CELL_SIZE * 2));
 189   }
 190
 191 } // namespace KJS
 192
 193 #endif /* KJSCOLLECTOR_H_ */