• Skip to content
  • Skip to link menu
Trinity API Reference
  • Trinity API Reference
  • kjs
 

kjs

  • kjs
collector.cpp
1/*
2 * This file is part of the KDE libraries
3 * Copyright (C) 2003 Apple Computer, Inc.
4 *
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Lesser General Public
7 * License as published by the Free Software Foundation; either
8 * version 2 of the License, or (at your option) any later version.
9 *
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Lesser General Public License for more details.
14 *
15 * You should have received a copy of the GNU Lesser General Public
16 * License along with this library; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
18 *
19 */
20
21#include "collector.h"
22
23#include "value.h"
24#include "internal.h"
25#include <limits.h>
26#include <typeinfo>
27
28#ifndef MAX
29#define MAX(a,b) ((a) > (b) ? (a) : (b))
30#endif
31
32namespace KJS {
33
34// tunable parameters
35const int MINIMUM_CELL_SIZE = 56;
36const int BLOCK_SIZE = (8 * 4096);
37const int SPARE_EMPTY_BLOCKS = 2;
38const int MIN_ARRAY_SIZE = 14;
39const int GROWTH_FACTOR = 2;
40const int LOW_WATER_FACTOR = 4;
41const int ALLOCATIONS_PER_COLLECTION = 1000;
42
43// derived constants
44const int CELL_ARRAY_LENGTH = (MINIMUM_CELL_SIZE / sizeof(double)) + (MINIMUM_CELL_SIZE % sizeof(double) != 0 ? sizeof(double) : 0);
45const int CELL_SIZE = CELL_ARRAY_LENGTH * sizeof(double);
46const int CELLS_PER_BLOCK = ((BLOCK_SIZE * 8 - sizeof(int) * 8 - sizeof(void *) * 8) / (CELL_SIZE * 8));
47
48
49
50struct CollectorCell {
51 double memory[CELL_ARRAY_LENGTH];
52};
53
54
55struct CollectorBlock {
56 CollectorCell cells[CELLS_PER_BLOCK];
57 int usedCells;
58 CollectorCell *freeList;
59};
60
61struct CollectorHeap {
62 CollectorBlock **blocks;
63 int numBlocks;
64 int usedBlocks;
65 int firstBlockWithPossibleSpace;
66
67 CollectorCell **oversizeCells;
68 int numOversizeCells;
69 int usedOversizeCells;
70
71 int numLiveObjects;
72 int numAllocationsSinceLastCollect;
73};
74
75static CollectorHeap heap = {NULL, 0, 0, 0, NULL, 0, 0, 0, 0};
76
77bool Collector::memoryFull = false;
78
79void* Collector::allocate(size_t s)
80{
81 if (s == 0)
82 return 0L;
83
84 // collect if needed
85 if (++heap.numAllocationsSinceLastCollect >= ALLOCATIONS_PER_COLLECTION) {
86 collect();
87 }
88
89 if (s > (unsigned)CELL_SIZE) {
90 // oversize allocator
91 if (heap.usedOversizeCells == heap.numOversizeCells) {
92 heap.numOversizeCells = MAX(MIN_ARRAY_SIZE, heap.numOversizeCells * GROWTH_FACTOR);
93 heap.oversizeCells = (CollectorCell **)realloc(heap.oversizeCells, heap.numOversizeCells * sizeof(CollectorCell *));
94 }
95
96 void *newCell = malloc(s);
97 heap.oversizeCells[heap.usedOversizeCells] = (CollectorCell *)newCell;
98 heap.usedOversizeCells++;
99 heap.numLiveObjects++;
100
101 ((ValueImp *)(newCell))->_flags = 0;
102 return newCell;
103 }
104
105 // slab allocator
106
107 CollectorBlock *targetBlock = NULL;
108
109 int i;
110 for (i = heap.firstBlockWithPossibleSpace; i < heap.usedBlocks; i++) {
111 if (heap.blocks[i]->usedCells < CELLS_PER_BLOCK) {
112 targetBlock = heap.blocks[i];
113 break;
114 }
115 }
116
117 heap.firstBlockWithPossibleSpace = i;
118
119 if (targetBlock == NULL) {
120 // didn't find one, need to allocate a new block
121
122 if (heap.usedBlocks == heap.numBlocks) {
123 static const size_t maxNumBlocks = ULONG_MAX / sizeof(CollectorBlock*) / GROWTH_FACTOR;
124 if ((size_t)heap.numBlocks > maxNumBlocks)
125 return 0L;
126 heap.numBlocks = MAX(MIN_ARRAY_SIZE, heap.numBlocks * GROWTH_FACTOR);
127 heap.blocks = (CollectorBlock **)realloc(heap.blocks, heap.numBlocks * sizeof(CollectorBlock *));
128 }
129
130 targetBlock = (CollectorBlock *)calloc(1, sizeof(CollectorBlock));
131 targetBlock->freeList = targetBlock->cells;
132 heap.blocks[heap.usedBlocks] = targetBlock;
133 heap.usedBlocks++;
134 }
135
136 // find a free spot in the block and detach it from the free list
137 CollectorCell *newCell = targetBlock->freeList;
138
139 ValueImp *imp = (ValueImp*)newCell;
140 if (imp->_vd != NULL) {
141 targetBlock->freeList = (CollectorCell*)(imp->_vd);
142 } else if (targetBlock->usedCells == (CELLS_PER_BLOCK - 1)) {
143 // last cell in this block
144 targetBlock->freeList = NULL;
145 } else {
146 // all next pointers are initially 0, meaning "next cell"
147 targetBlock->freeList = newCell + 1;
148 }
149
150 targetBlock->usedCells++;
151 heap.numLiveObjects++;
152
153 ((ValueImp *)(newCell))->_flags = 0;
154 return (void *)(newCell);
155}
156
157bool Collector::collect()
158{
159 bool deleted = false;
160
161 // MARK: first mark all referenced objects recursively
162 // starting out from the set of root objects
163 if (InterpreterImp::s_hook) {
164 InterpreterImp *scr = InterpreterImp::s_hook;
165 do {
166 //fprintf( stderr, "[kjs-collector] Collector marking interpreter %p\n",(void*)scr);
167 scr->mark();
168 scr = scr->next;
169 } while (scr != InterpreterImp::s_hook);
170 }
171
172 // mark any other objects that we wouldn't delete anyway
173 for (int block = 0; block < heap.usedBlocks; block++) {
174
175 int minimumCellsToProcess = heap.blocks[block]->usedCells;
176 CollectorBlock *curBlock = heap.blocks[block];
177
178 for (int cell = 0; cell < CELLS_PER_BLOCK; cell++) {
179 if (minimumCellsToProcess < cell) {
180 goto skip_block_mark;
181 }
182
183 ValueImp *imp = (ValueImp *)(curBlock->cells + cell);
184
185 if (!(imp->_flags & ValueImp::VI_DESTRUCTED)) {
186
187 if ((imp->_flags & (ValueImp::VI_CREATED|ValueImp::VI_MARKED)) == ValueImp::VI_CREATED &&
188 ((imp->_flags & ValueImp::VI_GCALLOWED) == 0 || imp->refcount != 0)) {
189 imp->mark();
190 }
191 } else {
192 minimumCellsToProcess++;
193 }
194 }
195 skip_block_mark: ;
196 }
197
198 for (int cell = 0; cell < heap.usedOversizeCells; cell++) {
199 ValueImp *imp = (ValueImp *)heap.oversizeCells[cell];
200 if ((imp->_flags & (ValueImp::VI_CREATED|ValueImp::VI_MARKED)) == ValueImp::VI_CREATED &&
201 ((imp->_flags & ValueImp::VI_GCALLOWED) == 0 || imp->refcount != 0)) {
202 imp->mark();
203 }
204 }
205
206 // SWEEP: delete everything with a zero refcount (garbage) and unmark everything else
207
208 int emptyBlocks = 0;
209
210 for (int block = 0; block < heap.usedBlocks; block++) {
211 CollectorBlock *curBlock = heap.blocks[block];
212
213 int minimumCellsToProcess = curBlock->usedCells;
214
215 for (int cell = 0; cell < CELLS_PER_BLOCK; cell++) {
216 if (minimumCellsToProcess < cell) {
217 goto skip_block_sweep;
218 }
219
220 ValueImp *imp = (ValueImp *)(curBlock->cells + cell);
221
222 if (!(imp->_flags & ValueImp::VI_DESTRUCTED)) {
223 if (!imp->refcount && imp->_flags == (ValueImp::VI_GCALLOWED | ValueImp::VI_CREATED)) {
224 //fprintf( stderr, "[kjs-collector] Collector::deleting ValueImp %p (%s)\n", (void*)imp, typeid(*imp).name());
225
226 // prevent double free
227 imp->_flags |= ValueImp::VI_DESTRUCTED;
228
229 // emulate destructing part of 'operator delete()'
230 imp->~ValueImp();
231 curBlock->usedCells--;
232 heap.numLiveObjects--;
233 deleted = true;
234
235 // put it on the free list
236 imp->_vd = (ValueImpPrivate*)curBlock->freeList;
237 curBlock->freeList = (CollectorCell *)imp;
238
239 } else {
240 imp->_flags &= ~ValueImp::VI_MARKED;
241 }
242 } else {
243 minimumCellsToProcess++;
244 }
245 }
246
247 skip_block_sweep:
248
249 if (heap.blocks[block]->usedCells == 0) {
250 emptyBlocks++;
251 if (emptyBlocks > SPARE_EMPTY_BLOCKS) {
252#ifndef DEBUG_COLLECTOR
253 free(heap.blocks[block]);
254#endif
255 // swap with the last block so we compact as we go
256 heap.blocks[block] = heap.blocks[heap.usedBlocks - 1];
257 heap.usedBlocks--;
258 block--; // Don't move forward a step in this case
259
260 if (heap.numBlocks > MIN_ARRAY_SIZE && heap.usedBlocks < heap.numBlocks / LOW_WATER_FACTOR) {
261 heap.numBlocks = heap.numBlocks / GROWTH_FACTOR;
262 heap.blocks = (CollectorBlock **)realloc(heap.blocks, heap.numBlocks * sizeof(CollectorBlock *));
263 }
264 }
265 }
266 }
267
268 if (deleted) {
269 heap.firstBlockWithPossibleSpace = 0;
270 }
271
272 int cell = 0;
273 while (cell < heap.usedOversizeCells) {
274 ValueImp *imp = (ValueImp *)heap.oversizeCells[cell];
275
276 if (!imp->refcount &&
277 imp->_flags == (ValueImp::VI_GCALLOWED | ValueImp::VI_CREATED)) {
278
279 imp->~ValueImp();
280#ifndef DEBUG_COLLECTOR
281 free((void *)imp);
282#endif
283
284 // swap with the last oversize cell so we compact as we go
285 heap.oversizeCells[cell] = heap.oversizeCells[heap.usedOversizeCells - 1];
286
287 heap.usedOversizeCells--;
288 deleted = true;
289 heap.numLiveObjects--;
290
291 if (heap.numOversizeCells > MIN_ARRAY_SIZE && heap.usedOversizeCells < heap.numOversizeCells / LOW_WATER_FACTOR) {
292 heap.numOversizeCells = heap.numOversizeCells / GROWTH_FACTOR;
293 heap.oversizeCells = (CollectorCell **)realloc(heap.oversizeCells, heap.numOversizeCells * sizeof(CollectorCell *));
294 }
295
296 } else {
297 imp->_flags &= ~ValueImp::VI_MARKED;
298 cell++;
299 }
300 }
301
302 heap.numAllocationsSinceLastCollect = 0;
303
304 memoryFull = (heap.numLiveObjects >= KJS_MEM_LIMIT);
305
306 return deleted;
307}
308
309int Collector::size()
310{
311 return heap.numLiveObjects;
312}
313
314#ifdef KJS_DEBUG_MEM
315void Collector::finalCheck()
316{
317}
318#endif
319
320} // namespace KJS
KJS::Collector::allocate
static void * allocate(size_t s)
Register an object with the collector.
Definition: collector.cpp:79
KJS::Collector::collect
static bool collect()
Run the garbage collection.
Definition: collector.cpp:157
KJS::ValueImp
ValueImp is the base type for all primitives (Undefined, Null, Boolean, String, Number) and objects i...
Definition: value.h:78

kjs

Skip menu "kjs"
  • Main Page
  • Class Hierarchy
  • Alphabetical List
  • Class List
  • File List
  • Class Members
  • Related Pages

kjs

Skip menu "kjs"
  • arts
  • dcop
  • dnssd
  • interfaces
  •   kspeech
  •     interface
  •     library
  •   tdetexteditor
  • kate
  • kded
  • kdoctools
  • kimgio
  • kjs
  • libtdemid
  • libtdescreensaver
  • tdeabc
  • tdecmshell
  • tdecore
  • tdefx
  • tdehtml
  • tdeinit
  • tdeio
  •   bookmarks
  •   httpfilter
  •   kpasswdserver
  •   kssl
  •   tdefile
  •   tdeio
  •   tdeioexec
  • tdeioslave
  •   http
  • tdemdi
  •   tdemdi
  • tdenewstuff
  • tdeparts
  • tdeprint
  • tderandr
  • tderesources
  • tdespell2
  • tdesu
  • tdeui
  • tdeunittest
  • tdeutils
  • tdewallet
Generated for kjs by doxygen 1.9.4
This website is maintained by Timothy Pearson.