collector.cpp
00001 // -*- c-basic-offset: 2 -*- 00002 /* 00003 * This file is part of the KDE libraries 00004 * Copyright (C) 2003 Apple Computer, Inc. 00005 * 00006 * This library is free software; you can redistribute it and/or 00007 * modify it under the terms of the GNU Lesser General Public 00008 * License as published by the Free Software Foundation; either 00009 * version 2 of the License, or (at your option) any later version. 00010 * 00011 * This library is distributed in the hope that it will be useful, 00012 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00014 * Lesser General Public License for more details. 00015 * 00016 * You should have received a copy of the GNU Lesser General Public 00017 * License along with this library; if not, write to the Free Software 00018 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 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 // tunable parameters 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 // derived constants 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 // collect if needed 00086 if (++heap.numAllocationsSinceLastCollect >= ALLOCATIONS_PER_COLLECTION) { 00087 collect(); 00088 } 00089 00090 if (s > (unsigned)CELL_SIZE) { 00091 // oversize allocator 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 // slab allocator 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 // didn't find one, need to allocate a new block 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 // find a free spot in the block and detach it from the free list 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 // last cell in this block 00145 targetBlock->freeList = NULL; 00146 } else { 00147 // all next pointers are initially 0, meaning "next cell" 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 // MARK: first mark all referenced objects recursively 00163 // starting out from the set of root objects 00164 if (InterpreterImp::s_hook) { 00165 InterpreterImp *scr = InterpreterImp::s_hook; 00166 do { 00167 //fprintf( stderr, "[kjs-collector] Collector marking interpreter %p\n",(void*)scr); 00168 scr->mark(); 00169 scr = scr->next; 00170 } while (scr != InterpreterImp::s_hook); 00171 } 00172 00173 // mark any other objects that we wouldn't delete anyway 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 // SWEEP: delete everything with a zero refcount (garbage) and unmark everything else 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 //fprintf( stderr, "[kjs-collector] Collector::deleting ValueImp %p (%s)\n", (void*)imp, typeid(*imp).name()); 00226 00227 // prevent double free 00228 imp->_flags |= ValueImp::VI_DESTRUCTED; 00229 00230 // emulate destructing part of 'operator delete()' 00231 imp->~ValueImp(); 00232 curBlock->usedCells--; 00233 heap.numLiveObjects--; 00234 deleted = true; 00235 00236 // put it on the free list 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 // swap with the last block so we compact as we go 00257 heap.blocks[block] = heap.blocks[heap.usedBlocks - 1]; 00258 heap.usedBlocks--; 00259 block--; // Don't move forward a step in this case 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 // swap with the last oversize cell so we compact as we go 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 } // namespace KJS