kjs Library API Documentation

collector.cpp

00001 // -*- c-basic-offset: 2 -*-
00002 /*
00003  *  This file is part of the KDE libraries
00004  *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
00005  *  Copyright (C) 2001 Peter Kelly (pmk@post.com)
00006  *
00007  *  This library is free software; you can redistribute it and/or
00008  *  modify it under the terms of the GNU Lesser General Public
00009  *  License as published by the Free Software Foundation; either
00010  *  version 2 of the License, or (at your option) any later version.
00011  *
00012  *  This library is distributed in the hope that it will be useful,
00013  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
00014  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00015  *  Lesser General Public License for more details.
00016  *
00017  *  You should have received a copy of the GNU Lesser General Public
00018  *  License along with this library; if not, write to the Free Software
00019  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00020  *
00021  */
00022 
00023 #include "collector.h"
00024 #include "internal.h"
00025 
00026 #include <stdio.h>
00027 #include <string.h>
00028 #include <assert.h>
00029 #ifdef KJS_DEBUG_MEM
00030 #include <typeinfo>
00031 #endif
00032 
00033 namespace KJS {
00034 
00035   class CollectorBlock {
00036   public:
00037     CollectorBlock(int s);
00038     ~CollectorBlock();
00039     int size;
00040     int filled;
00041     ValueImp** mem;
00042     CollectorBlock *prev, *next;
00043   };
00044 
00045 } // namespace
00046 
00047 using namespace KJS;
00048 
00049 CollectorBlock::CollectorBlock(int s)
00050   : size(s),
00051     filled(0),
00052     prev(0L),
00053     next(0L)
00054 {
00055   mem = new ValueImp*[size];
00056 }
00057 
00058 CollectorBlock::~CollectorBlock()
00059 {
00060   delete [] mem;
00061   mem = 0L;
00062 }
00063 
00064 CollectorBlock* Collector::root = 0L;
00065 CollectorBlock* Collector::currentBlock = 0L;
00066 unsigned long Collector::filled = 0;
00067 unsigned long Collector::softLimit = KJS_MEM_INCREMENT;
00068 
00069 bool Collector::memLimitReached = false;
00070 
00071 #ifdef KJS_DEBUG_MEM
00072 bool Collector::collecting = false;
00073 #endif
00074 
00075 void* Collector::allocate(size_t s)
00076 {
00077   if (s == 0)
00078     return 0L;
00079 
00080   // Try and deal with memory requirements in a scalable way. Simple scripts
00081   // should only require small amounts of memory, but for complex scripts we don't
00082   // want to end up running the garbage collector hundreds of times a second.
00083   if (filled >= softLimit) {
00084     collect();
00085     if (softLimit/(1+filled) < 2 && softLimit < KJS_MEM_LIMIT) {
00086       // Even after collection we are still using more than half of the limit,
00087       // so increase the limit
00088       softLimit = (unsigned long) (softLimit * 1.4);
00089     }
00090   }
00091 
00092   ValueImp *m = static_cast<ValueImp*>(malloc(s));
00093 #ifdef KJS_DEBUG_MEM
00094   //fprintf( stderr, "allocate: size=%d valueimp=%p\n",s,m);
00095 #endif
00096 
00097   // VI_CREATED and VI_GCALLOWED being unset ensure that value
00098   // is protected from GC before any constructors are run
00099   static_cast<ValueImp*>(m)->_flags = 0;
00100 
00101   if (!root) {
00102     root = new CollectorBlock(BlockSize);
00103     currentBlock = root;
00104   }
00105 
00106   CollectorBlock *block = currentBlock;
00107   if (!block)
00108     block = root;
00109 
00110   // search for a block with space left
00111   while (block->next && block->filled == block->size)
00112     block = block->next;
00113 
00114   if (block->filled >= block->size) {
00115 #ifdef KJS_DEBUG_MEM
00116     //fprintf( stderr, "allocating new block of size %d\n", block->size);
00117 #endif
00118     CollectorBlock *tmp = new CollectorBlock(BlockSize);
00119     block->next = tmp;
00120     tmp->prev = block;
00121     block = tmp;
00122   }
00123   currentBlock = block;
00124   // fill free spot in the block
00125   *(block->mem + block->filled) = m;
00126   filled++;
00127   block->filled++;
00128 
00129   if (softLimit >= KJS_MEM_LIMIT) {
00130     memLimitReached = true;
00131     fprintf(stderr,"Out of memory");
00132   }
00133 
00134   return m;
00135 }
00136 
00140 bool Collector::collect()
00141 {
00142 #ifdef KJS_DEBUG_MEM
00143   fprintf(stderr,"Collector::collect()\n");
00144 #endif
00145   bool deleted = false;
00146   // MARK: first unmark everything
00147   CollectorBlock *block = root;
00148   while (block) {
00149     ValueImp **r = block->mem;
00150     assert(r);
00151     for (int i = 0; i < block->filled; i++, r++)
00152       (*r)->_flags &= ~ValueImp::VI_MARKED;
00153     block = block->next;
00154   }
00155 
00156   // mark all referenced objects recursively
00157   // starting out from the set of root objects
00158   if (InterpreterImp::s_hook) {
00159     InterpreterImp *scr = InterpreterImp::s_hook;
00160     do {
00161       //fprintf( stderr, "Collector marking interpreter %p\n",(void*)scr);
00162       scr->mark();
00163       scr = scr->next;
00164     } while (scr != InterpreterImp::s_hook);
00165   }
00166 
00167   // mark any other objects that we wouldn't delete anyway
00168   block = root;
00169   while (block) {
00170     ValueImp **r = block->mem;
00171     assert(r);
00172     for (int i = 0; i < block->filled; i++, r++)
00173     {
00174       ValueImp *imp = (*r);
00175       // Check for created=true, marked=false and (gcallowed=false or refcount>0)
00176       if ((imp->_flags & (ValueImp::VI_CREATED|ValueImp::VI_MARKED)) == ValueImp::VI_CREATED &&
00177           ( (imp->_flags & ValueImp::VI_GCALLOWED) == 0 || imp->refcount ) ) {
00178         //fprintf( stderr, "Collector marking imp=%p\n",(void*)imp);
00179         imp->mark();
00180       }
00181     }
00182     block = block->next;
00183   }
00184 
00185   // SWEEP: delete everything with a zero refcount (garbage)
00186   // 1st step: destruct all objects
00187   block = root;
00188   while (block) {
00189     ValueImp **r = block->mem;
00190     for (int i = 0; i < block->filled; i++, r++) {
00191       ValueImp *imp = (*r);
00192       // Can delete if marked==false
00193       if ((imp->_flags & (ValueImp::VI_CREATED|ValueImp::VI_MARKED)) == ValueImp::VI_CREATED ) {
00194         // emulate destructing part of 'operator delete()'
00195         //fprintf( stderr, "Collector::deleting ValueImp %p (%s)\n", (void*)imp, typeid(*imp).name());
00196         imp->~ValueImp();
00197       }
00198     }
00199     block = block->next;
00200   }
00201 
00202   // 2nd step: free memory
00203   block = root;
00204   while (block) {
00205     ValueImp **r = block->mem;
00206     int freespot = block->filled;
00207     bool firstfreeset = false;
00208     int del = 0;
00209     for (int i = 0; i < block->filled; i++, r++) {
00210       ValueImp *imp = (*r);
00211       if ((imp->_flags & ValueImp::VI_DESTRUCTED) != 0) {
00212         free(imp);
00213         del++;
00214         if (!firstfreeset) {
00215           firstfreeset = true;
00216           freespot = r - block->mem;
00217         }
00218       } else if (firstfreeset) {
00219          *(block->mem + freespot) = imp;
00220          freespot++;
00221       }
00222     }
00223     filled -= del;
00224     block->filled -= del;
00225     assert(freespot == block->filled);
00226     block = block->next;
00227     if (del)
00228       deleted = true;
00229   }
00230 
00231   // delete the empty containers
00232   block = root;
00233   currentBlock = 0L;
00234   CollectorBlock *last = root;
00235   while (block) {
00236     CollectorBlock *next = block->next;
00237     if (block->filled == 0) {
00238       if (block->prev)
00239         block->prev->next = next;
00240       if (block == root)
00241         root = next;
00242       if (next)
00243         next->prev = block->prev;
00244       assert(block != root);
00245       delete block;
00246     } else if (!currentBlock) {
00247         if (block->filled < block->size)
00248           currentBlock = block;
00249         else
00250           last = block;
00251     }
00252     block = next;
00253   }
00254   if (!currentBlock)
00255     currentBlock = last;
00256 #if 0
00257   // This is useful to track down memory leaks
00258   static int s_count = 0;
00259   fprintf(stderr, "Collector done (was run %d)\n",s_count);
00260   if (s_count++ % 50 == 2)
00261     finalCheck();
00262 #endif
00263   return deleted;
00264 }
00265 
00266 #ifdef KJS_DEBUG_MEM
00267 void Collector::finalCheck()
00268 {
00269   CollectorBlock *block = root;
00270   while (block) {
00271     ValueImp **r = block->mem;
00272     for (int i = 0; i < block->size; i++, r++) {
00273       if (*r ) {
00274         fprintf( stderr, "Collector::finalCheck() still having ValueImp %p (%s)  [marked:%d gcAllowed:%d created:%d refcount:%d]\n",
00275                  (void*)(*r), typeid( **r ).name(),
00276                  (bool)((*r)->_flags & ValueImp::VI_MARKED),
00277                  (bool)((*r)->_flags & ValueImp::VI_GCALLOWED),
00278                  (bool)((*r)->_flags & ValueImp::VI_CREATED),
00279                  (*r)->refcount);
00280       }
00281     }
00282     block = block->next;
00283   }
00284 }
00285 #endif
KDE Logo
This file is part of the documentation for kdelibs Version 3.1.4.
Documentation copyright © 1996-2002 the KDE developers.
Generated on Sun Feb 27 22:15:17 2005 by doxygen 1.3.4 written by Dimitri van Heesch, © 1997-2001