kjs Library API Documentation

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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 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 // tunable parameters 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 // derived constants 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 // collect if needed 00088 if (++heap.numAllocationsSinceLastCollect >= ALLOCATIONS_PER_COLLECTION) { 00089 collect(); 00090 } 00091 00092 if (s > (unsigned)CELL_SIZE) { 00093 // oversize allocator 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 // slab allocator 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 // didn't find one, need to allocate a new block 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 // find a free spot in the block and detach it from the free list 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 // last cell in this block 00144 targetBlock->freeList = NULL; 00145 } else { 00146 // all next pointers are initially 0, meaning "next cell" 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 // MARK: first mark all referenced objects recursively 00162 // starting out from the set of root objects 00163 if (InterpreterImp::s_hook) { 00164 InterpreterImp *scr = InterpreterImp::s_hook; 00165 do { 00166 //fprintf( stderr, "Collector marking interpreter %p\n",(void*)scr); 00167 scr->mark(); 00168 scr = scr->next; 00169 } while (scr != InterpreterImp::s_hook); 00170 } 00171 00172 // mark any other objects that we wouldn't delete anyway 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 // SWEEP: delete everything with a zero refcount (garbage) and unmark everything else 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 //fprintf( stderr, "Collector::deleting ValueImp %p (%s)\n", (void*)imp, typeid(*imp).name()); 00225 // emulate destructing part of 'operator delete()' 00226 imp->~ValueImp(); 00227 curBlock->usedCells--; 00228 heap.numLiveObjects--; 00229 deleted = true; 00230 00231 // put it on the free list 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 // swap with the last block so we compact as we go 00252 heap.blocks[block] = heap.blocks[heap.usedBlocks - 1]; 00253 heap.usedBlocks--; 00254 block--; // Don't move forward a step in this case 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 // swap with the last oversize cell so we compact as we go 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 } // namespace KJS
KDE Logo
This file is part of the documentation for kjs Library Version 3.2.3.
Documentation copyright © 1996-2004 the KDE developers.
Generated on Fri Aug 20 09:48:57 2004 by doxygen 1.3.7 written by Dimitri van Heesch, © 1997-2003