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 
00028 #ifndef MAX
00029 #define MAX(a,b) ((a) > (b) ? (a) : (b))
00030 #endif
00031 
00032 namespace KJS {
00033 
00034 // tunable parameters
00035 const int MINIMUM_CELL_SIZE = 56;
00036 const int BLOCK_SIZE = (8 * 4096);
00037 const int SPARE_EMPTY_BLOCKS = 2;
00038 const int MIN_ARRAY_SIZE = 14;
00039 const int GROWTH_FACTOR = 2;
00040 const int LOW_WATER_FACTOR = 4;
00041 const int ALLOCATIONS_PER_COLLECTION = 1000;
00042 
00043 // derived constants
00044 const int CELL_ARRAY_LENGTH = (MINIMUM_CELL_SIZE / sizeof(double)) + (MINIMUM_CELL_SIZE % sizeof(double) != 0 ? sizeof(double) : 0);
00045 const int CELL_SIZE = CELL_ARRAY_LENGTH * sizeof(double);
00046 const int CELLS_PER_BLOCK = ((BLOCK_SIZE * 8 - sizeof(int) * 8 - sizeof(void *) * 8) / (CELL_SIZE * 8));
00047 
00048 
00049 
00050 struct CollectorCell {
00051   double memory[CELL_ARRAY_LENGTH];
00052 };
00053 
00054 
00055 struct CollectorBlock {
00056   CollectorCell cells[CELLS_PER_BLOCK];
00057   int usedCells;
00058   CollectorCell *freeList;
00059 };
00060 
00061 struct CollectorHeap {
00062   CollectorBlock **blocks;
00063   int numBlocks;
00064   int usedBlocks;
00065   int firstBlockWithPossibleSpace;
00066 
00067   CollectorCell **oversizeCells;
00068   int numOversizeCells;
00069   int usedOversizeCells;
00070 
00071   int numLiveObjects;
00072   int numAllocationsSinceLastCollect;
00073 };
00074 
00075 static CollectorHeap heap = {NULL, 0, 0, 0, NULL, 0, 0, 0, 0};
00076 
00077 bool Collector::memoryFull = false;
00078 
00079 void* Collector::allocate(size_t s)
00080 {
00081   if (s == 0)
00082     return 0L;
00083 
00084   // collect if needed
00085   if (++heap.numAllocationsSinceLastCollect >= ALLOCATIONS_PER_COLLECTION) {
00086     collect();
00087   }
00088 
00089   if (s > (unsigned)CELL_SIZE) {
00090     // oversize allocator
00091     if (heap.usedOversizeCells == heap.numOversizeCells) {
00092       heap.numOversizeCells = MAX(MIN_ARRAY_SIZE, heap.numOversizeCells * GROWTH_FACTOR);
00093       heap.oversizeCells = (CollectorCell **)realloc(heap.oversizeCells, heap.numOversizeCells * sizeof(CollectorCell *));
00094     }
00095 
00096     void *newCell = malloc(s);
00097     heap.oversizeCells[heap.usedOversizeCells] = (CollectorCell *)newCell;
00098     heap.usedOversizeCells++;
00099     heap.numLiveObjects++;
00100 
00101     ((ValueImp *)(newCell))->_flags = 0;
00102     return newCell;
00103   }
00104 
00105   // slab allocator
00106 
00107   CollectorBlock *targetBlock = NULL;
00108 
00109   int i;
00110   for (i = heap.firstBlockWithPossibleSpace; i < heap.usedBlocks; i++) {
00111     if (heap.blocks[i]->usedCells < CELLS_PER_BLOCK) {
00112       targetBlock = heap.blocks[i];
00113       break;
00114     }
00115   }
00116 
00117   heap.firstBlockWithPossibleSpace = i;
00118 
00119   if (targetBlock == NULL) {
00120     // didn't find one, need to allocate a new block
00121 
00122     if (heap.usedBlocks == heap.numBlocks) {
00123       static const size_t maxNumBlocks = ULONG_MAX / sizeof(CollectorBlock*) / GROWTH_FACTOR;
00124       if (heap.numBlocks > maxNumBlocks)
00125           return 0L;
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 Home | KDE Accessibility Home | Description of Access Keys