collector.h 6.41 KB
Newer Older
1
// -*- c-basic-offset: 2 -*-
2 3 4
/*
 *  This file is part of the KDE libraries
 *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
5
 *  Copyright (C) 2001 Peter Kelly (pmk@post.com)
darin's avatar
darin committed
6
 *  Copyright (C) 2003, 2004, 2005, 2006, 2007 Apple Inc. All rights reserved.
7 8 9 10 11 12 13 14 15 16 17 18 19
 *
 *  This library is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU Lesser General Public
 *  License as published by the Free Software Foundation; either
 *  version 2 of the License, or (at your option) any later version.
 *
 *  This library is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 *  Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public
 *  License along with this library; if not, write to the Free Software
mjs's avatar
mjs committed
20
 *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
21
 *
22 23
 */

darin's avatar
darin committed
24 25
#ifndef KJSCOLLECTOR_H_
#define KJSCOLLECTOR_H_
26

27
#include <string.h>
mjs's avatar
mjs committed
28
#include <wtf/HashCountedSet.h>
mjs's avatar
mjs committed
29

mjs's avatar
mjs committed
30
#define KJS_MEM_LIMIT 500000
31

mjs's avatar
mjs committed
32
namespace KJS {
33

mjs@apple.com's avatar
mjs@apple.com committed
34
  class CollectorBlock;
mjs's avatar
mjs committed
35 36
  class JSCell;
  class JSValue;
mjs@apple.com's avatar
mjs@apple.com committed
37
  class MarkStack;
mjs's avatar
mjs committed
38

39 40 41
  class Collector {
  public:
    static void* allocate(size_t s);
42
    static void* allocateNumber(size_t s);
43
    static bool collect();
darin's avatar
darin committed
44
    static bool isBusy(); // true if an allocation or collection is in progress
mjs's avatar
mjs committed
45

mjs's avatar
mjs committed
46 47 48 49
    static const size_t minExtraCostSize = 256;

    static void reportExtraMemoryCost(size_t cost);

adele's avatar
adele committed
50
    static size_t size();
mjs's avatar
mjs committed
51
    static bool isOutOfMemory() { return memoryFull; }
52

weinig's avatar
weinig committed
53 54
    static void protect(JSValue*);
    static void unprotect(JSValue*);
ggaren's avatar
ggaren committed
55 56
    
    static void collectOnMainThreadOnly(JSValue*);
mjs's avatar
mjs committed
57

adele's avatar
adele committed
58
    static size_t numInterpreters();
mjs's avatar
mjs committed
59 60
    static size_t numProtectedObjects();
    static HashCountedSet<const char*>* rootObjectTypeCounts();
mjs's avatar
mjs committed
61

darin's avatar
darin committed
62
    class Thread;
mjs's avatar
mjs committed
63
    static void registerThread();
ggaren's avatar
ggaren committed
64
    
mjs's avatar
mjs committed
65 66
    static void registerAsMainThread();

mjs's avatar
mjs committed
67 68
    static bool isCellMarked(const JSCell*);
    static void markCell(JSCell*);
mjs@apple.com's avatar
mjs@apple.com committed
69
    static bool cellMayHaveRefs(const JSCell*);
mjs's avatar
mjs committed
70

71
    enum HeapType { PrimaryHeap, NumberHeap };
aroben's avatar
aroben committed
72 73

  private:
74 75
    template <Collector::HeapType heapType> static void* heapAllocate(size_t s);
    template <Collector::HeapType heapType> static size_t sweep(bool);
mjs's avatar
mjs committed
76 77
    static const CollectorBlock* cellBlock(const JSCell*);
    static CollectorBlock* cellBlock(JSCell*);
mjs's avatar
mjs committed
78
    static size_t cellOffset(const JSCell*);
mjs's avatar
mjs committed
79

ggaren's avatar
ggaren committed
80
    Collector();
mjs's avatar
mjs committed
81

mjs's avatar
mjs committed
82
    static void recordExtraCost(size_t);
mjs@apple.com's avatar
mjs@apple.com committed
83 84 85 86 87 88
    static void markProtectedObjects(MarkStack&);
    static void markMainThreadOnlyObjects(MarkStack&);
    static void markCurrentThreadConservatively(MarkStack&);
    static void markOtherThreadConservatively(MarkStack&, Thread*);
    static void markStackObjectsConservatively(MarkStack&);
    static void markStackObjectsConservatively(MarkStack&, void* start, void* end);
mjs's avatar
mjs committed
89

ggaren's avatar
ggaren committed
90
    static size_t mainThreadOnlyObjectCount;
91
    static bool memoryFull;
92
    static void reportOutOfMemoryToAllInterpreters();
93 94
  };

mjs's avatar
mjs committed
95 96 97 98 99 100 101 102 103 104 105 106 107 108
  // tunable parameters
  template<size_t bytesPerWord> struct CellSize;

  // cell size needs to be a power of two for certain optimizations in collector.cpp
  template<> struct CellSize<sizeof(uint32_t)> { static const size_t m_value = 32; }; // 32-bit
  template<> struct CellSize<sizeof(uint64_t)> { static const size_t m_value = 64; }; // 64-bit
  const size_t BLOCK_SIZE = 16 * 4096; // 64k
  
  // derived constants
  const size_t BLOCK_OFFSET_MASK = BLOCK_SIZE - 1;
  const size_t BLOCK_MASK = ~BLOCK_OFFSET_MASK;
  const size_t MINIMUM_CELL_SIZE = CellSize<sizeof(void*)>::m_value;
  const size_t CELL_ARRAY_LENGTH = (MINIMUM_CELL_SIZE / sizeof(double)) + (MINIMUM_CELL_SIZE % sizeof(double) != 0 ? sizeof(double) : 0);
  const size_t CELL_SIZE = CELL_ARRAY_LENGTH * sizeof(double);
mjs's avatar
mjs committed
109
  const size_t SMALL_CELL_SIZE = CELL_SIZE / 2;
mjs's avatar
mjs committed
110
  const size_t CELL_MASK = CELL_SIZE - 1;
mjs's avatar
mjs committed
111
  const size_t CELL_ALIGN_MASK = ~CELL_MASK;
mjs@apple.com's avatar
mjs@apple.com committed
112
  const size_t CELLS_PER_BLOCK = (BLOCK_SIZE * 8 - sizeof(uint32_t) * 8 - sizeof(uint32_t) * 8 - sizeof(void *) * 8 - 2 * (7 + 3 * 8)) / (CELL_SIZE * 8 + 2);
mjs's avatar
mjs committed
113
  const size_t SMALL_CELLS_PER_BLOCK = 2 * CELLS_PER_BLOCK;
mjs's avatar
mjs committed
114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134
  const size_t BITMAP_SIZE = (CELLS_PER_BLOCK + 7) / 8;
  const size_t BITMAP_WORDS = (BITMAP_SIZE + 3) / sizeof(uint32_t);
  
  struct CollectorBitmap {
    uint32_t bits[BITMAP_WORDS];
    bool get(size_t n) const { return !!(bits[n >> 5] & (1 << (n & 0x1F))); } 
    void set(size_t n) { bits[n >> 5] |= (1 << (n & 0x1F)); } 
    void clear(size_t n) { bits[n >> 5] &= ~(1 << (n & 0x1F)); } 
    void clearAll() { memset(bits, 0, sizeof(bits)); }
  };
  
  struct CollectorCell {
    union {
      double memory[CELL_ARRAY_LENGTH];
      struct {
        void* zeroIfFree;
        ptrdiff_t next;
      } freeCell;
    } u;
  };

mjs's avatar
mjs committed
135 136 137 138 139 140 141 142 143 144
  struct SmallCollectorCell {
    union {
      double memory[CELL_ARRAY_LENGTH / 2];
      struct {
        void* zeroIfFree;
        ptrdiff_t next;
      } freeCell;
    } u;
  };

mjs's avatar
mjs committed
145 146
  class CollectorBlock {
  public:
mjs's avatar
mjs committed
147 148 149
    CollectorCell cells[CELLS_PER_BLOCK];
    uint32_t usedCells;
    CollectorCell* freeList;
mjs@apple.com's avatar
mjs@apple.com committed
150
    uint32_t mayHaveRefs;
mjs's avatar
mjs committed
151 152 153 154
    CollectorBitmap marked;
    CollectorBitmap collectOnMainThreadOnly;
  };

mjs's avatar
mjs committed
155 156 157 158 159
  class SmallCellCollectorBlock {
  public:
    SmallCollectorCell cells[SMALL_CELLS_PER_BLOCK];
    uint32_t usedCells;
    SmallCollectorCell* freeList;
mjs@apple.com's avatar
mjs@apple.com committed
160
    uint32_t mayHaveRefs;
mjs's avatar
mjs committed
161 162 163 164
    CollectorBitmap marked;
    CollectorBitmap collectOnMainThreadOnly;
  };

mjs's avatar
mjs committed
165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189
  inline const CollectorBlock* Collector::cellBlock(const JSCell* cell)
  {
    return reinterpret_cast<const CollectorBlock*>(reinterpret_cast<uintptr_t>(cell) & BLOCK_MASK);
  }

  inline CollectorBlock* Collector::cellBlock(JSCell* cell)
  {
    return const_cast<CollectorBlock*>(cellBlock(const_cast<const JSCell*>(cell)));
  }

  inline size_t Collector::cellOffset(const JSCell* cell)
  {
    return (reinterpret_cast<uintptr_t>(cell) & BLOCK_OFFSET_MASK) / CELL_SIZE;
  }

  inline bool Collector::isCellMarked(const JSCell* cell)
  {
    return cellBlock(cell)->marked.get(cellOffset(cell));
  }

  inline void Collector::markCell(JSCell* cell)
  {
    cellBlock(cell)->marked.set(cellOffset(cell));
  }

mjs@apple.com's avatar
mjs@apple.com committed
190 191 192 193 194
  inline bool Collector::cellMayHaveRefs(const JSCell* cell)
  {
    return cellBlock(cell)->mayHaveRefs;
  }

mjs's avatar
mjs committed
195 196 197 198 199 200
  inline void Collector::reportExtraMemoryCost(size_t cost)
  { 
    if (cost > minExtraCostSize) 
      recordExtraCost(cost / (CELL_SIZE * 2)); 
  }

weinig's avatar
weinig committed
201
} // namespace KJS
202

weinig's avatar
weinig committed
203
#endif /* KJSCOLLECTOR_H_ */