• Skip to content
  • Skip to link menu
Trinity API Reference
  • Trinity API Reference
  • kjs
 

kjs

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

kjs

Skip menu "kjs"
  • Main Page
  • Class Hierarchy
  • Alphabetical List
  • Class List
  • File List
  • Class Members
  • Related Pages

kjs

Skip menu "kjs"
  • arts
  • dcop
  • dnssd
  • interfaces
  •   kspeech
  •     interface
  •     library
  •   tdetexteditor
  • kate
  • kded
  • kdoctools
  • kimgio
  • kjs
  • libtdemid
  • libtdescreensaver
  • tdeabc
  • tdecmshell
  • tdecore
  • tdefx
  • tdehtml
  • tdeinit
  • tdeio
  •   bookmarks
  •   httpfilter
  •   kpasswdserver
  •   kssl
  •   tdefile
  •   tdeio
  •   tdeioexec
  • tdeioslave
  •   http
  • tdemdi
  •   tdemdi
  • tdenewstuff
  • tdeparts
  • tdeprint
  • tderandr
  • tderesources
  • tdespell2
  • tdesu
  • tdeui
  • tdeunittest
  • tdeutils
  • tdewallet
Generated for kjs by doxygen 1.7.6.1
This website is maintained by Timothy Pearson.