• 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 
32 namespace KJS {
33 
34 // tunable parameters
35 const int MINIMUM_CELL_SIZE = 56;
36 const int BLOCK_SIZE = (8 * 4096);
37 const int SPARE_EMPTY_BLOCKS = 2;
38 const int MIN_ARRAY_SIZE = 14;
39 const int GROWTH_FACTOR = 2;
40 const int LOW_WATER_FACTOR = 4;
41 const int ALLOCATIONS_PER_COLLECTION = 1000;
42 
43 // derived constants
44 const int CELL_ARRAY_LENGTH = (MINIMUM_CELL_SIZE / sizeof(double)) + (MINIMUM_CELL_SIZE % sizeof(double) != 0 ? sizeof(double) : 0);
45 const int CELL_SIZE = CELL_ARRAY_LENGTH * sizeof(double);
46 const int CELLS_PER_BLOCK = ((BLOCK_SIZE * 8 - sizeof(int) * 8 - sizeof(void *) * 8) / (CELL_SIZE * 8));
47 
48 
49 
50 struct CollectorCell {
51  double memory[CELL_ARRAY_LENGTH];
52 };
53 
54 
55 struct CollectorBlock {
56  CollectorCell cells[CELLS_PER_BLOCK];
57  int usedCells;
58  CollectorCell *freeList;
59 };
60 
61 struct 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 
75 static CollectorHeap heap = {NULL, 0, 0, 0, NULL, 0, 0, 0, 0};
76 
77 bool Collector::memoryFull = false;
78 
79 void* 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 
157 bool 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 
309 int Collector::size()
310 {
311  return heap.numLiveObjects;
312 }
313 
314 #ifdef KJS_DEBUG_MEM
315 void 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.1
This website is maintained by Timothy Pearson.