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 
00027 #ifndef MAX
00028 #define MAX(a,b) ((a) > (b) ? (a) : (b))
00029 #endif
00030 
00031 namespace KJS {
00032 
00033 // tunable parameters
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 // derived constants
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   // collect if needed
00084   if (++heap.numAllocationsSinceLastCollect >= ALLOCATIONS_PER_COLLECTION) {
00085     collect();
00086   }
00087 
00088   if (s > (unsigned)CELL_SIZE) {
00089     // oversize allocator
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   // slab allocator
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     // didn't find one, need to allocate a new block
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   // find a free spot in the block and detach it from the free list
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     // last cell in this block
00140     targetBlock->freeList = NULL;
00141   } else {
00142     // all next pointers are initially 0, meaning "next cell"
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   // MARK: first mark all referenced objects recursively
00158   // starting out from the set of root objects
00159   if (InterpreterImp::s_hook) {
00160     InterpreterImp *scr = InterpreterImp::s_hook;
00161     do {
00162       //fprintf( stderr, "Collector marking interpreter %p\n",(void*)scr);
00163       scr->mark();
00164       scr = scr->next;
00165     } while (scr != InterpreterImp::s_hook);
00166   }
00167 
00168   // mark any other objects that we wouldn't delete anyway
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   // SWEEP: delete everything with a zero refcount (garbage) and unmark everything else
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       //fprintf( stderr, "Collector::deleting ValueImp %p (%s)\n", (void*)imp, typeid(*imp).name());
00221       // emulate destructing part of 'operator delete()'
00222       imp->~ValueImp();
00223       curBlock->usedCells--;
00224       heap.numLiveObjects--;
00225       deleted = true;
00226 
00227       // put it on the free list
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     // swap with the last block so we compact as we go
00248     heap.blocks[block] = heap.blocks[heap.usedBlocks - 1];
00249     heap.usedBlocks--;
00250     block--; // Don't move forward a step in this case
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       // swap with the last oversize cell so we compact as we go
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 } // namespace KJS
KDE Home | KDE Accessibility Home | Description of Access Keys