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

kjs

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

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.8.1.2
This website is maintained by Timothy Pearson.