KDECore
kallocator.cpp
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030 #include "kallocator.h"
00031 #include "kdebug.h"
00032 #include <QList>
00033
00034 class KZoneAllocator::MemBlock
00035 {
00036 public:
00037 MemBlock(size_t s) : size(s), ref(0), older(0), newer(0)
00038 { begin = new char[s]; }
00039 ~MemBlock() { delete [] begin; }
00040 bool is_in(void *ptr) const {return !(begin > (char *)ptr
00041 || (begin + size) <= (char *)ptr); }
00042 size_t size;
00043 unsigned int ref;
00044 char *begin;
00045 MemBlock *older;
00046 MemBlock *newer;
00047 };
00048
00049 class KZoneAllocator::Private
00050 {
00051 public:
00052 Private()
00053 : currentBlock(0), blockSize(1),
00054 blockOffset(0), log2(0), num_blocks(0),
00055 hashList(0), hashSize(0), hashDirty(true)
00056 {
00057 }
00058
00060 MemBlock *currentBlock;
00062 unsigned long blockSize;
00064 unsigned long blockOffset;
00066 unsigned int log2;
00068 unsigned int num_blocks;
00070 MemList **hashList;
00072 unsigned int hashSize;
00074 bool hashDirty;
00075 };
00076
00077 KZoneAllocator::KZoneAllocator(unsigned long _blockSize)
00078 : d( new Private )
00079 {
00080 while (d->blockSize < _blockSize) {
00081 d->blockSize <<= 1;
00082 d->log2++;
00083 }
00084
00085
00086
00087 d->blockOffset = d->blockSize + 1;
00088 }
00089
00090 KZoneAllocator::~KZoneAllocator()
00091 {
00092 unsigned int count = 0;
00093 if (d->hashList) {
00094
00095
00096 for (unsigned int i = 0; i < d->hashSize; i++)
00097 delete d->hashList[i];
00098 delete [] d->hashList;
00099 d->hashList = 0;
00100 }
00101 MemBlock *next;
00102 for (; d->currentBlock; d->currentBlock = next) {
00103 next = d->currentBlock->older;
00104 delete d->currentBlock;
00105 count++;
00106 }
00107 #ifndef NDEBUG // as this is called quite late in the app, we don't care
00108
00109 if (count > 1)
00110 qDebug("zone still contained %d blocks", count);
00111 #endif
00112 delete d;
00113 }
00114
00115 void KZoneAllocator::insertHash(MemBlock *b)
00116 {
00117 unsigned long adr = ((unsigned long)b->begin) & (~(d->blockSize - 1));
00118 unsigned long end = ((unsigned long)b->begin) + d->blockSize;
00119 while (adr < end) {
00120 unsigned long key = adr >> d->log2;
00121 key = key & (d->hashSize - 1);
00122 if (!d->hashList[key])
00123 d->hashList[key] = new QList<MemBlock *>;
00124 d->hashList[key]->append(b);
00125 adr += d->blockSize;
00126 }
00127 }
00128
00134 void KZoneAllocator::addBlock(MemBlock *b)
00135 {
00136 b->newer = 0;
00137 b->older = d->currentBlock;
00138 if (d->currentBlock)
00139 b->older->newer = b;
00140 d->currentBlock = b;
00141 d->num_blocks++;
00142
00143
00144
00145 if (d->hashList && ((d->num_blocks / 4) > d->hashSize && d->hashSize < 64*1024))
00146 d->hashDirty = true;
00147
00148
00149 if (d->hashList && !d->hashDirty)
00150 insertHash (b);
00151 }
00152
00154 void KZoneAllocator::initHash()
00155 {
00156 if (d->hashList) {
00157 for (unsigned int i = 0; i < d->hashSize; i++)
00158 delete d->hashList[i];
00159 delete [] d->hashList;
00160 d->hashList = 0;
00161 }
00162 d->hashSize = 1;
00163 while (d->hashSize < d->num_blocks)
00164 d->hashSize <<= 1;
00165 if (d->hashSize < 1024)
00166 d->hashSize = 1024;
00167 if (d->hashSize > 64*1024)
00168 d->hashSize = 64*1024;
00169 d->hashList = new QList<MemBlock *> *[d->hashSize];
00170 memset (d->hashList, 0, sizeof(QList<MemBlock*> *) * d->hashSize);
00171 d->hashDirty = false;
00172 for (MemBlock *b = d->currentBlock; b; b = b->older)
00173 insertHash(b);
00174 }
00175
00180 void KZoneAllocator::delBlock(MemBlock *b)
00181 {
00182
00183
00184 if (d->hashList && !d->hashDirty) {
00185 unsigned long adr = ((unsigned long)b->begin) & (~(d->blockSize - 1));
00186 unsigned long end = ((unsigned long)b->begin) + d->blockSize;
00187 while (adr < end) {
00188 unsigned long key = adr >> d->log2;
00189 key = key & (d->hashSize - 1);
00190 if (d->hashList[key]) {
00191 QList<MemBlock *> *list = d->hashList[key];
00192 QList<MemBlock *>::Iterator it = list->begin();
00193 QList<MemBlock *>::Iterator endit = list->end();
00194 for (; it != endit; ++it)
00195 if (*it == b) {
00196 list->erase(it);
00197 break;
00198 }
00199 }
00200 adr += d->blockSize;
00201 }
00202 }
00203 if (b->older)
00204 b->older->newer = b->newer;
00205 if (b->newer)
00206 b->newer->older = b->older;
00207 if (b == d->currentBlock) {
00208 d->currentBlock = 0;
00209 d->blockOffset = d->blockSize;
00210 }
00211 delete b;
00212 d->num_blocks--;
00213 }
00214
00215 void *
00216 KZoneAllocator::allocate(size_t _size)
00217 {
00218
00219 const size_t alignment = sizeof(void *) - 1;
00220 _size = (_size + alignment) & ~alignment;
00221
00222 if ((unsigned long) _size + d->blockOffset > d->blockSize)
00223 {
00224 if (_size > d->blockSize) {
00225 qDebug("KZoneAllocator: allocating more than %lu bytes", d->blockSize);
00226 return 0;
00227 }
00228 addBlock(new MemBlock(d->blockSize));
00229 d->blockOffset = 0;
00230
00231 }
00232 void *result = (void *)(d->currentBlock->begin+d->blockOffset);
00233 d->currentBlock->ref++;
00234 d->blockOffset += _size;
00235 return result;
00236 }
00237
00238 void
00239 KZoneAllocator::deallocate(void *ptr)
00240 {
00241 if (d->hashDirty)
00242 initHash();
00243
00244 unsigned long key = (((unsigned long)ptr) >> d->log2) & (d->hashSize - 1);
00245 const QList<MemBlock *> *list = d->hashList[key];
00246 if (!list) {
00247
00248
00249
00250 return;
00251 }
00252 QList<MemBlock*>::ConstIterator it = list->begin();
00253 QList<MemBlock*>::ConstIterator endit = list->end();
00254 for (; it != endit; ++it) {
00255 MemBlock *cur = *it;
00256 if (cur->is_in(ptr)) {
00257 if (!--cur->ref) {
00258 if (cur != d->currentBlock)
00259 delBlock (cur);
00260 else
00261 d->blockOffset = 0;
00262 }
00263 return;
00264 }
00265 }
00266
00267
00268
00269 }
00270
00271 void
00272 KZoneAllocator::free_since(void *ptr)
00273 {
00274
00275
00276
00277 if (d->hashList && !d->hashDirty)
00278 {
00279 const MemBlock *b;
00280 unsigned int removed = 0;
00281 for (b = d->currentBlock; b; b = b->older, removed++)
00282 if (b->is_in (ptr))
00283 break;
00284 if (d->hashSize >= 4 * (d->num_blocks - removed))
00285 d->hashDirty = true;
00286 }
00287 while (d->currentBlock && !d->currentBlock->is_in(ptr)) {
00288 d->currentBlock = d->currentBlock->older;
00289 delBlock (d->currentBlock->newer);
00290 }
00291 d->blockOffset = ((char*)ptr) - d->currentBlock->begin;
00292 }