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.3.0.
Documentation copyright © 1996-2004 the KDE developers.
Generated on Thu Sep 23 17:12:07 2004 by doxygen 1.3.8-20040913 written by Dimitri van Heesch, © 1997-2003