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