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$ 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 TQValueList<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 TQValueList<MemBlock *> *[hashSize]; 00138 memset (hashList, 0, sizeof(TQValueList<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 TQValueList<MemBlock *> *list = hashList[key]; 00160 TQValueList<MemBlock *>::Iterator it = list->begin(); 00161 TQValueList<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 TQValueList<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 TQValueList<MemBlock*>::ConstIterator it = list->begin(); 00221 TQValueList<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 }