kallocator.cpp00001
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
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
00055
00056 blockOffset = blockSize + 1;
00057 }
00058
00059 KZoneAllocator::~KZoneAllocator()
00060 {
00061 unsigned int count = 0;
00062 if (hashList) {
00063
00064
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
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
00111
00112
00113 if (hashList && ((num_blocks / 4) > hashSize && hashSize < 64*1024))
00114 hashDirty = true;
00115
00116
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
00151
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
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
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
00216
00217
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
00235
00236
00237 }
00238
00239 void
00240 KZoneAllocator::free_since(void *ptr)
00241 {
00242
00243
00244
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 }
|