KDECore

kallocator.cpp

00001 /*
00002     This file is part of the KDE libraries
00003 
00004     Copyright (C) 1999 Waldo Bastian (bastian@kde.org)
00005     Copyright (C) 2002 Michael Matz (matz@kde.org)
00006 
00007     This library is free software; you can redistribute it and/or
00008     modify it under the terms of the GNU Library 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     Library General Public License for more details.
00016 
00017     You should have received a copy of the GNU Library General Public License
00018     along with this library; see the file COPYING.LIB.  If not, write to
00019     the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
00020     Boston, MA 02110-1301, USA.
00021 */
00022 
00023 /* Fast zone memory allocator with deallocation support, for use as obstack
00024    or as general purpose allocator.  It does no compaction.  If the usage
00025    pattern is non-optimal it might waste some memory while running.  E.g.
00026    allocating many small things at once, and then deallocating only every
00027    second one, there is a high chance, that actually no memory is freed.  */
00028 // $Id: kallocator.cpp 477382 2005-11-03 23:41:16Z adridg $
00029 
00030 #include "kallocator.h"
00031 #include <kdebug.h>
00032 
00033 class KZoneAllocator::MemBlock
00034 {
00035   public:
00036     MemBlock(size_t s) : size(s), ref(0), older(0), newer(0)
00037       { begin = new char[s]; }
00038     ~MemBlock() { delete [] begin; }
00039     bool is_in(void *ptr) const {return !(begin > (char *)ptr
00040                               || (begin + size) <= (char *)ptr); }
00041     size_t size;
00042     unsigned int ref;
00043     char *begin;
00044     MemBlock *older;
00045     MemBlock *newer;
00046 };
00047 
00048 KZoneAllocator::KZoneAllocator(unsigned long _blockSize)
00049 : currentBlock(0), blockSize(1), blockOffset(0), log2(0), num_blocks(0), 
00050   hashList(0), hashSize(0), hashDirty(true)
00051 {
00052   while (blockSize < _blockSize)
00053     blockSize <<= 1, log2++;
00054   /* Make sure, that a block is allocated at the first time allocate()
00055      is called (even with a 0 size).  */
00056   blockOffset = blockSize + 1;
00057 }
00058 
00059 KZoneAllocator::~KZoneAllocator()
00060 {
00061   unsigned int count = 0;
00062   if (hashList) {
00063     /* No need to maintain the different lists in hashList[] anymore.
00064        I.e. no need to use delBlock().  */
00065     for (unsigned int i = 0; i < hashSize; i++)
00066       delete hashList[i];
00067     delete [] hashList;
00068     hashList = 0;
00069   }
00070   MemBlock *next;
00071   for (; currentBlock; currentBlock = next) {
00072     next = currentBlock->older;
00073     delete currentBlock;
00074     count++;
00075   }
00076 #ifndef NDEBUG // as this is called quite late in the app, we don't care
00077            // to use kdDebug
00078   if (count > 1)
00079     qDebug("zone still contained %d blocks", count);
00080 #endif
00081 }
00082 
00083 void KZoneAllocator::insertHash(MemBlock *b)
00084 {
00085   unsigned long adr = ((unsigned long)b->begin) & (~(blockSize - 1));
00086   unsigned long end = ((unsigned long)b->begin) + blockSize;
00087   while (adr < end) {
00088     unsigned long key = adr >> log2;
00089     key = key & (hashSize - 1);
00090     if (!hashList[key])
00091       hashList[key] = new QValueList<MemBlock *>;
00092     hashList[key]->append(b);
00093     adr += blockSize;
00094   }
00095 }
00096 
00102 void KZoneAllocator::addBlock(MemBlock *b)
00103 {
00104   b->newer = 0;
00105   b->older = currentBlock;
00106   if (currentBlock)
00107     b->older->newer = b;
00108   currentBlock = b;
00109   num_blocks++;
00110   /* If we either have no hashList at all, or since it's last construction
00111      there are now many more blocks we reconstruct the list.  But don't
00112      make it larger than a certain maximum.  */
00113   if (hashList && ((num_blocks / 4) > hashSize && hashSize < 64*1024))
00114     hashDirty = true;
00115   /* Only insert this block into the hashlists, if we aren't going to
00116      reconstruct them anyway.  */
00117   if (hashList && !hashDirty)
00118     insertHash (b);
00119 }
00120 
00122 void KZoneAllocator::initHash()
00123 {
00124   if (hashList) {
00125     for (unsigned int i = 0; i < hashSize; i++)
00126       delete hashList[i];
00127     delete [] hashList;
00128     hashList = 0;
00129   }
00130   hashSize = 1;
00131   while (hashSize < num_blocks)
00132     hashSize <<= 1;
00133   if (hashSize < 1024)
00134     hashSize = 1024;
00135   if (hashSize > 64*1024)
00136     hashSize = 64*1024;
00137   hashList = new QValueList<MemBlock *> *[hashSize];
00138   memset (hashList, 0, sizeof(QValueList<MemBlock*> *) * hashSize);
00139   hashDirty = false;
00140   for (MemBlock *b = currentBlock; b; b = b->older)
00141     insertHash(b);
00142 }
00143 
00148 void KZoneAllocator::delBlock(MemBlock *b)
00149 {
00150   /* Update also the hashlists if we aren't going to reconstruct them
00151      soon.  */
00152   if (hashList && !hashDirty) {
00153     unsigned long adr = ((unsigned long)b->begin) & (~(blockSize - 1));
00154     unsigned long end = ((unsigned long)b->begin) + blockSize;
00155     while (adr < end) {
00156       unsigned long key = adr >> log2;
00157       key = key & (hashSize - 1);
00158       if (hashList[key]) {
00159     QValueList<MemBlock *> *list = hashList[key];
00160     QValueList<MemBlock *>::Iterator it = list->begin();
00161     QValueList<MemBlock *>::Iterator endit = list->end();
00162     for (; it != endit; ++it)
00163       if (*it == b) {
00164         list->remove(it);
00165         break;
00166       }
00167       }
00168       adr += blockSize;
00169     }
00170   }
00171   if (b->older)
00172     b->older->newer = b->newer;
00173   if (b->newer)
00174     b->newer->older = b->older;
00175   if (b == currentBlock) {
00176     currentBlock = 0;
00177     blockOffset = blockSize;
00178   }
00179   delete b;
00180   num_blocks--;
00181 }
00182 
00183 void *
00184 KZoneAllocator::allocate(size_t _size)
00185 {
00186    // Use the size of (void *) as alignment
00187    const size_t alignment = sizeof(void *) - 1;
00188    _size = (_size + alignment) & ~alignment;   
00189 
00190    if ((unsigned long) _size + blockOffset > blockSize)
00191    {
00192       if (_size > blockSize) {
00193     qDebug("KZoneAllocator: allocating more than %lu bytes", blockSize);
00194     return 0;
00195       }
00196       addBlock(new MemBlock(blockSize));
00197       blockOffset = 0;
00198       //qDebug ("Allocating block #%d (%x)\n", num_blocks, currentBlock->begin);
00199    }
00200    void *result = (void *)(currentBlock->begin+blockOffset);
00201    currentBlock->ref++;
00202    blockOffset += _size;
00203    return result;
00204 }
00205 
00206 void
00207 KZoneAllocator::deallocate(void *ptr)
00208 {
00209   if (hashDirty)
00210     initHash();
00211 
00212   unsigned long key = (((unsigned long)ptr) >> log2) & (hashSize - 1);
00213   QValueList<MemBlock *> *list = hashList[key];
00214   if (!list) {
00215     /* Can happen with certain usage pattern of intermixed free_since()
00216        and deallocate().  */
00217     //qDebug("Uhoh");
00218     return;
00219   }
00220   QValueList<MemBlock*>::ConstIterator it = list->begin();
00221   QValueList<MemBlock*>::ConstIterator endit = list->end();
00222   for (; it != endit; ++it) {
00223     MemBlock *cur = *it;
00224     if (cur->is_in(ptr)) {
00225       if (!--cur->ref) {
00226     if (cur != currentBlock)
00227       delBlock (cur);
00228     else
00229       blockOffset = 0;
00230       }
00231       return;
00232     }
00233   }
00234   /* Can happen with certain usage pattern of intermixed free_since()
00235      and deallocate().  */
00236   //qDebug("Uhoh2");
00237 }
00238 
00239 void
00240 KZoneAllocator::free_since(void *ptr)
00241 {
00242   /* If we have a hashList and it's not yet dirty, see, if we will dirty
00243      it by removing too many blocks.  This will make the below delBlock()s
00244      faster.  */
00245   if (hashList && !hashDirty)
00246     {
00247       const MemBlock *b;
00248       unsigned int removed = 0;
00249       for (b = currentBlock; b; b = b->older, removed++)
00250     if (b->is_in (ptr))
00251       break;
00252       if (hashSize >= 4 * (num_blocks - removed))
00253         hashDirty = true;
00254     }
00255   while (currentBlock && !currentBlock->is_in(ptr)) {
00256     currentBlock = currentBlock->older;
00257     delBlock (currentBlock->newer);
00258   }
00259   blockOffset = ((char*)ptr) - currentBlock->begin;
00260 }
KDECore

kallocator.cpp

KDECore

API Reference
