| # kjs Library API Documentation
Overview | Class Hierarchy | Classes | Classes (annotated) | Members | Source Files

# 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

This file is part of the documentation for kdelibs Version 3.1.5.
Documentation copyright © 1996-2002 the KDE developers.
Generated on Wed Jan 28 13:08:18 2004 by doxygen 1.3.4 written by Dimitri van Heesch, © 1997-2001