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#include <cstddef>
31
32#define KJS_MEM_LIMIT 500000
33
34namespace KJS {
35 class JSCell;
36 class JSValue;
37 class CollectorBlock;
38
39 /**
40 * @short Garbage collector.
41 */
42 class KJS_EXPORT Collector {
43 // disallow direct construction/destruction
44 Collector();
45 public:
46 /**
47 * Register an object with the collector. The following assumptions are
48 * made:
49 * @li the operator new() of the object class is overloaded.
50 * @li operator delete() has been overloaded as well and does not free
51 * the memory on its own.
52 *
53 * @param s Size of the memory to be registered.
54 * @return A pointer to the allocated memory.
55 */
56 static void* allocate(size_t s);
57 /**
58 * Run the garbage collection. This involves calling the delete operator
59 * on each object and freeing the used memory.
60 */
61 static bool collect();
62
63 static const size_t minExtraCostSize = 256;
64
65 static void reportExtraMemoryCost(size_t cost);
66
67 static size_t size();
68 static bool isOutOfMemory() { return memoryFull; }
69
70#ifdef KJS_DEBUG_MEM
71 /**
72 * Check that nothing is left when the last interpreter gets deleted
73 */
74 static void finalCheck();
75#endif
76
77 static void protect(JSValue *);
78 static void unprotect(JSValue *);
79
80 static size_t numInterpreters();
81 static size_t numProtectedObjects();
82 static HashCountedSet<const char*>* rootObjectTypeCounts();
83
84 class Thread;
85 static void registerThread();
86
87 static bool isCellMarked(const JSCell*);
88 static void markCell(JSCell*);
89
90 private:
91 static const CollectorBlock* cellBlock(const JSCell*);
92 static CollectorBlock* cellBlock(JSCell*);
93 static size_t cellOffset(const JSCell*);
94
95 static void recordExtraCost(size_t);
96 static void markProtectedObjects();
97 static void markCurrentThreadConservatively();
98 static void markOtherThreadConservatively(Thread*);
99 static void markStackObjectsConservatively();
100 static void markStackObjectsConservatively(void *start, void *end);
101
102 static bool memoryFull;
103 static void reportOutOfMemoryToAllInterpreters();
104 };
105
106 // tunable parameters
107 template<size_t bytesPerWord> struct CellSize;
108
109 // cell size needs to be a power of two for certain optimizations in collector.cpp
110 // below also assume it's divisible by 8, and that block size is divisible by it
111 template<> struct CellSize<4> { static const size_t m_value = 32; }; // 32-bit
112 template<> struct CellSize<8> { static const size_t m_value = 64; }; // 64-bit
113 const size_t BLOCK_SIZE = 16 * 4096; // 64k
114
115 const size_t BLOCK_OFFSET_MASK = BLOCK_SIZE - 1;
116 const size_t BLOCK_MASK = ~BLOCK_OFFSET_MASK;
117
118 const size_t CELL_SIZE = CellSize<sizeof(void*)>::m_value;
119 const size_t CELL_ARRAY_LENGTH = (CELL_SIZE / sizeof(double));
120 const size_t CELL_MASK = CELL_SIZE - 1;
121
122 // For each block, we can have at /most/ BLOCK_SIZE/CELL_SIZE entries.
123 // Sice the bitmap accordingly, don't try to be fancy
124 const size_t BITMAP_SIZE = (BLOCK_SIZE / CELL_SIZE + 7) / 8;
125 const size_t BITMAP_WORDS = (BITMAP_SIZE + 3) / sizeof(uint32_t);
126
127 // In each block, we have 3 bitmaps (mark for all blocks, extension + allocd for oversize cell blocks),
128 // as well as an int and a pointer
129 const size_t BLOCK_METADATA_SIZE = 3 * 4 * BITMAP_WORDS + sizeof(uint32_t) + sizeof(void*);
130 const size_t CELLS_PER_BLOCK = (BLOCK_SIZE - BLOCK_METADATA_SIZE) / CELL_SIZE;
131
132 struct CollectorBitmap {
133 uint32_t bits[BITMAP_WORDS];
134 bool get(size_t n) const { return !!(bits[n >> 5] & (1 << (n & 0x1F))); }
135 void set(size_t n) { bits[n >> 5] |= (1 << (n & 0x1F)); }
136 void clear(size_t n) { bits[n >> 5] &= ~(1 << (n & 0x1F)); }
137 void clearAll() { std::memset(bits, 0, sizeof(bits)); }
138 };
139
140 struct CollectorCell {
141 union {
142 double memory[CELL_ARRAY_LENGTH];
143 struct {
144 void* zeroIfFree;
145 ptrdiff_t next;
146 } freeCell;
147 } u;
148 };
149
150 class CollectorBlock {
151 public:
152 CollectorCell cells[CELLS_PER_BLOCK];
153 uint32_t usedCells;
154 CollectorCell* freeList;
155 CollectorBitmap marked;
156 CollectorBitmap allocd;
157 CollectorBitmap trailer;
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
192#endif /* _KJSCOLLECTOR_H_ */
193