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