collector.cpp
00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #include "collector.h"
00023
00024 #include "value.h"
00025 #include "internal.h"
00026
00027 #include <collector.h>
00028 #include <value.h>
00029 #include <internal.h>
00030
00031 #ifndef MAX
00032 #define MAX(a,b) ((a) > (b) ? (a) : (b))
00033 #endif
00034
00035 namespace KJS {
00036
00037
00038 const int MINIMUM_CELL_SIZE = 56;
00039 const int BLOCK_SIZE = (8 * 4096);
00040 const int SPARE_EMPTY_BLOCKS = 2;
00041 const int MIN_ARRAY_SIZE = 14;
00042 const int GROWTH_FACTOR = 2;
00043 const int LOW_WATER_FACTOR = 4;
00044 const int ALLOCATIONS_PER_COLLECTION = 1000;
00045
00046
00047 const int CELL_ARRAY_LENGTH = (MINIMUM_CELL_SIZE / sizeof(double)) + (MINIMUM_CELL_SIZE % sizeof(double) != 0 ? sizeof(double) : 0);
00048 const int CELL_SIZE = CELL_ARRAY_LENGTH * sizeof(double);
00049 const int CELLS_PER_BLOCK = ((BLOCK_SIZE * 8 - sizeof(int) * 8 - sizeof(void *) * 8) / (CELL_SIZE * 8));
00050
00051
00052
00053 struct CollectorCell {
00054 double memory[CELL_ARRAY_LENGTH];
00055 };
00056
00057
00058 struct CollectorBlock {
00059 CollectorCell cells[CELLS_PER_BLOCK];
00060 int usedCells;
00061 CollectorCell *freeList;
00062 };
00063
00064 struct CollectorHeap {
00065 CollectorBlock **blocks;
00066 int numBlocks;
00067 int usedBlocks;
00068 int firstBlockWithPossibleSpace;
00069
00070 CollectorCell **oversizeCells;
00071 int numOversizeCells;
00072 int usedOversizeCells;
00073
00074 int numLiveObjects;
00075 int numAllocationsSinceLastCollect;
00076 };
00077
00078 static CollectorHeap heap = {NULL, 0, 0, 0, NULL, 0, 0, 0, 0};
00079
00080 bool Collector::memoryFull = false;
00081
00082 void* Collector::allocate(size_t s)
00083 {
00084 if (s == 0)
00085 return 0L;
00086
00087
00088 if (++heap.numAllocationsSinceLastCollect >= ALLOCATIONS_PER_COLLECTION) {
00089 collect();
00090 }
00091
00092 if (s > (unsigned)CELL_SIZE) {
00093
00094 if (heap.usedOversizeCells == heap.numOversizeCells) {
00095 heap.numOversizeCells = MAX(MIN_ARRAY_SIZE, heap.numOversizeCells * GROWTH_FACTOR);
00096 heap.oversizeCells = (CollectorCell **)realloc(heap.oversizeCells, heap.numOversizeCells * sizeof(CollectorCell *));
00097 }
00098
00099 void *newCell = malloc(s);
00100 heap.oversizeCells[heap.usedOversizeCells] = (CollectorCell *)newCell;
00101 heap.usedOversizeCells++;
00102 heap.numLiveObjects++;
00103
00104 ((ValueImp *)(newCell))->_flags = 0;
00105 return newCell;
00106 }
00107
00108
00109
00110 CollectorBlock *targetBlock = NULL;
00111
00112 int i;
00113 for (i = heap.firstBlockWithPossibleSpace; i < heap.usedBlocks; i++) {
00114 if (heap.blocks[i]->usedCells < CELLS_PER_BLOCK) {
00115 targetBlock = heap.blocks[i];
00116 break;
00117 }
00118 }
00119
00120 heap.firstBlockWithPossibleSpace = i;
00121
00122 if (targetBlock == NULL) {
00123
00124
00125 if (heap.usedBlocks == heap.numBlocks) {
00126 heap.numBlocks = MAX(MIN_ARRAY_SIZE, heap.numBlocks * GROWTH_FACTOR);
00127 heap.blocks = (CollectorBlock **)realloc(heap.blocks, heap.numBlocks * sizeof(CollectorBlock *));
00128 }
00129
00130 targetBlock = (CollectorBlock *)calloc(1, sizeof(CollectorBlock));
00131 targetBlock->freeList = targetBlock->cells;
00132 heap.blocks[heap.usedBlocks] = targetBlock;
00133 heap.usedBlocks++;
00134 }
00135
00136
00137 CollectorCell *newCell = targetBlock->freeList;
00138
00139 ValueImp *imp = (ValueImp*)newCell;
00140 if (imp->_vd != NULL) {
00141 targetBlock->freeList = (CollectorCell*)(imp->_vd);
00142 } else if (targetBlock->usedCells == (CELLS_PER_BLOCK - 1)) {
00143
00144 targetBlock->freeList = NULL;
00145 } else {
00146
00147 targetBlock->freeList = newCell + 1;
00148 }
00149
00150 targetBlock->usedCells++;
00151 heap.numLiveObjects++;
00152
00153 ((ValueImp *)(newCell))->_flags = 0;
00154 return (void *)(newCell);
00155 }
00156
00157 bool Collector::collect()
00158 {
00159 bool deleted = false;
00160
00161
00162
00163 if (InterpreterImp::s_hook) {
00164 InterpreterImp *scr = InterpreterImp::s_hook;
00165 do {
00166
00167 scr->mark();
00168 scr = scr->next;
00169 } while (scr != InterpreterImp::s_hook);
00170 }
00171
00172
00173 for (int block = 0; block < heap.usedBlocks; block++) {
00174
00175 int minimumCellsToProcess = heap.blocks[block]->usedCells;
00176 CollectorBlock *curBlock = heap.blocks[block];
00177
00178 for (int cell = 0; cell < CELLS_PER_BLOCK; cell++) {
00179 if (minimumCellsToProcess < cell) {
00180 goto skip_block_mark;
00181 }
00182
00183 ValueImp *imp = (ValueImp *)(curBlock->cells + cell);
00184
00185 if (!(imp->_flags & ValueImp::VI_DESTRUCTED)) {
00186
00187 if ((imp->_flags & (ValueImp::VI_CREATED|ValueImp::VI_MARKED)) == ValueImp::VI_CREATED &&
00188 ((imp->_flags & ValueImp::VI_GCALLOWED) == 0 || imp->refcount != 0)) {
00189 imp->mark();
00190 }
00191 } else {
00192 minimumCellsToProcess++;
00193 }
00194 }
00195 skip_block_mark: ;
00196 }
00197
00198 for (int cell = 0; cell < heap.usedOversizeCells; cell++) {
00199 ValueImp *imp = (ValueImp *)heap.oversizeCells[cell];
00200 if ((imp->_flags & (ValueImp::VI_CREATED|ValueImp::VI_MARKED)) == ValueImp::VI_CREATED &&
00201 ((imp->_flags & ValueImp::VI_GCALLOWED) == 0 || imp->refcount != 0)) {
00202 imp->mark();
00203 }
00204 }
00205
00206
00207
00208 int emptyBlocks = 0;
00209
00210 for (int block = 0; block < heap.usedBlocks; block++) {
00211 CollectorBlock *curBlock = heap.blocks[block];
00212
00213 int minimumCellsToProcess = curBlock->usedCells;
00214
00215 for (int cell = 0; cell < CELLS_PER_BLOCK; cell++) {
00216 if (minimumCellsToProcess < cell) {
00217 goto skip_block_sweep;
00218 }
00219
00220 ValueImp *imp = (ValueImp *)(curBlock->cells + cell);
00221
00222 if (!(imp->_flags & ValueImp::VI_DESTRUCTED)) {
00223 if (!imp->refcount && imp->_flags == (ValueImp::VI_GCALLOWED | ValueImp::VI_CREATED)) {
00224
00225
00226 imp->~ValueImp();
00227 curBlock->usedCells--;
00228 heap.numLiveObjects--;
00229 deleted = true;
00230
00231
00232 imp->_vd = (ValueImpPrivate*)curBlock->freeList;
00233 curBlock->freeList = (CollectorCell *)imp;
00234
00235 } else {
00236 imp->_flags &= ~ValueImp::VI_MARKED;
00237 }
00238 } else {
00239 minimumCellsToProcess++;
00240 }
00241 }
00242
00243 skip_block_sweep:
00244
00245 if (heap.blocks[block]->usedCells == 0) {
00246 emptyBlocks++;
00247 if (emptyBlocks > SPARE_EMPTY_BLOCKS) {
00248 #ifndef DEBUG_COLLECTOR
00249 free(heap.blocks[block]);
00250 #endif
00251
00252 heap.blocks[block] = heap.blocks[heap.usedBlocks - 1];
00253 heap.usedBlocks--;
00254 block--;
00255
00256 if (heap.numBlocks > MIN_ARRAY_SIZE && heap.usedBlocks < heap.numBlocks / LOW_WATER_FACTOR) {
00257 heap.numBlocks = heap.numBlocks / GROWTH_FACTOR;
00258 heap.blocks = (CollectorBlock **)realloc(heap.blocks, heap.numBlocks * sizeof(CollectorBlock *));
00259 }
00260 }
00261 }
00262 }
00263
00264 if (deleted) {
00265 heap.firstBlockWithPossibleSpace = 0;
00266 }
00267
00268 int cell = 0;
00269 while (cell < heap.usedOversizeCells) {
00270 ValueImp *imp = (ValueImp *)heap.oversizeCells[cell];
00271
00272 if (!imp->refcount &&
00273 imp->_flags == (ValueImp::VI_GCALLOWED | ValueImp::VI_CREATED)) {
00274
00275 imp->~ValueImp();
00276 #ifndef DEBUG_COLLECTOR
00277 free((void *)imp);
00278 #endif
00279
00280
00281 heap.oversizeCells[cell] = heap.oversizeCells[heap.usedOversizeCells - 1];
00282
00283 heap.usedOversizeCells--;
00284 deleted = true;
00285 heap.numLiveObjects--;
00286
00287 if (heap.numOversizeCells > MIN_ARRAY_SIZE && heap.usedOversizeCells < heap.numOversizeCells / LOW_WATER_FACTOR) {
00288 heap.numOversizeCells = heap.numOversizeCells / GROWTH_FACTOR;
00289 heap.oversizeCells = (CollectorCell **)realloc(heap.oversizeCells, heap.numOversizeCells * sizeof(CollectorCell *));
00290 }
00291
00292 } else {
00293 imp->_flags &= ~ValueImp::VI_MARKED;
00294 cell++;
00295 }
00296 }
00297
00298 heap.numAllocationsSinceLastCollect = 0;
00299
00300 memoryFull = (heap.numLiveObjects >= KJS_MEM_LIMIT);
00301
00302 return deleted;
00303 }
00304
00305 int Collector::size()
00306 {
00307 return heap.numLiveObjects;
00308 }
00309
00310 #ifdef KJS_DEBUG_MEM
00311 void Collector::finalCheck()
00312 {
00313 }
00314 #endif
00315
00316 }
This file is part of the documentation for kjs Library Version 3.3.0.
Documentation copyright © 1996-2004 the KDE developers.
Generated on Thu Sep 23 17:12:07 2004 by
doxygen 1.3.8-20040913 written by
Dimitri van Heesch, © 1997-2003