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
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 int adr = ((
unsigned int)b->begin) & (~(blockSize - 1));
00086
unsigned int end = ((
unsigned int)b->begin) + blockSize;
00087
while (adr < end) {
00088
unsigned int 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
00097
void KZoneAllocator::addBlock(MemBlock *b)
00098 {
00099 b->newer = 0;
00100 b->older = currentBlock;
00101
if (currentBlock)
00102 b->older->newer = b;
00103 currentBlock = b;
00104 num_blocks++;
00105
00106
00107
00108
if (hashList && ((num_blocks / 4) > hashSize && hashSize < 64*1024))
00109 hashDirty =
true;
00110
00111
00112
if (hashList && !hashDirty)
00113 insertHash (b);
00114 }
00115
00116
void KZoneAllocator::initHash()
00117 {
00118
if (hashList) {
00119
for (
unsigned int i = 0; i < hashSize; i++)
00120
delete hashList[i];
00121
delete [] hashList;
00122 hashList = 0;
00123 }
00124 hashSize = 1;
00125
while (hashSize < num_blocks)
00126 hashSize <<= 1;
00127
if (hashSize < 1024)
00128 hashSize = 1024;
00129
if (hashSize > 64*1024)
00130 hashSize = 64*1024;
00131 hashList =
new QValueList<MemBlock *> *[hashSize];
00132 memset (hashList, 0,
sizeof(
QValueList<MemBlock*> *) * hashSize);
00133 hashDirty =
false;
00134
for (MemBlock *b = currentBlock; b; b = b->older)
00135 insertHash(b);
00136 }
00137
00138
void KZoneAllocator::delBlock(MemBlock *b)
00139 {
00140
00141
00142
if (hashList && !hashDirty) {
00143
unsigned int adr = ((
unsigned int)b->begin) & (~(blockSize - 1));
00144
unsigned int end = ((
unsigned int)b->begin) + blockSize;
00145
while (adr <
end) {
00146
unsigned int key = adr >> log2;
00147
key =
key & (hashSize - 1);
00148
if (hashList[
key]) {
00149 QValueList<MemBlock *> *list = hashList[
key];
00150 QValueList<MemBlock *>::Iterator it = list->begin();
00151 QValueList<MemBlock *>::Iterator endit = list->end();
00152
for (; it != endit; ++it)
00153
if (*it == b) {
00154 list->remove(it);
00155
break;
00156 }
00157 }
00158 adr += blockSize;
00159 }
00160 }
00161
if (b->older)
00162 b->older->newer = b->newer;
00163
if (b->newer)
00164 b->newer->older = b->older;
00165
if (b == currentBlock) {
00166 currentBlock = 0;
00167 blockOffset = blockSize;
00168 }
00169
delete b;
00170 num_blocks--;
00171 }
00172
00173
void *
00174 KZoneAllocator::allocate(size_t _size)
00175 {
00176
00177
const size_t alignment =
sizeof(
void *) - 1;
00178 _size = (_size + alignment) & ~alignment;
00179
00180
if ((
unsigned long) _size + blockOffset > blockSize)
00181 {
00182
if (_size > blockSize) {
00183 qDebug(
"KZoneAllocator: allocating more than %lu bytes", blockSize);
00184
return 0;
00185 }
00186 addBlock(
new MemBlock(blockSize));
00187 blockOffset = 0;
00188
00189 }
00190
void *result = (
void *)(currentBlock->begin+blockOffset);
00191 currentBlock->ref++;
00192 blockOffset += _size;
00193
return result;
00194 }
00195
00196
void
00197 KZoneAllocator::deallocate(
void *ptr)
00198 {
00199
if (hashDirty)
00200 initHash();
00201
00202
unsigned int key = (((
unsigned int)ptr) >> log2) & (hashSize - 1);
00203 QValueList<MemBlock *> *list = hashList[key];
00204
if (!list) {
00205
00206
00207
00208
return;
00209 }
00210
QValueList<MemBlock*>::ConstIterator it = list->begin();
00211
QValueList<MemBlock*>::ConstIterator endit = list->end();
00212
for (; it != endit; ++it) {
00213 MemBlock *cur = *it;
00214
if (cur->is_in(ptr)) {
00215
if (!--cur->ref) {
00216
if (cur != currentBlock)
00217 delBlock (cur);
00218
else
00219 blockOffset = 0;
00220 }
00221
return;
00222 }
00223 }
00224
00225
00226
00227 }
00228
00229
void
00230 KZoneAllocator::free_since(
void *ptr)
00231 {
00232
00233
00234
00235
if (hashList && !hashDirty)
00236 {
00237
const MemBlock *b;
00238
unsigned int removed = 0;
00239
for (b = currentBlock; b; b = b->older, removed++)
00240
if (b->is_in (ptr))
00241
break;
00242
if (hashSize >= 4 * (num_blocks - removed))
00243 hashDirty =
true;
00244 }
00245
while (currentBlock && !currentBlock->is_in(ptr)) {
00246 currentBlock = currentBlock->older;
00247 delBlock (currentBlock->newer);
00248 }
00249 blockOffset = ((
char*)ptr) - currentBlock->begin;
00250 }