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 | |
34 | namespace 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 = 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 (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::(size_t cost) |
186 | { |
187 | if (cost > minExtraCostSize) |
188 | recordExtraCost(cost / (CELL_SIZE * 2)); |
189 | } |
190 | } |
191 | |
192 | #endif /* _KJSCOLLECTOR_H_ */ |
193 | |