1/*
2 This file is part of the KDE libraries
3
4 SPDX-FileCopyrightText: 1999 Waldo Bastian <bastian@kde.org>
5 SPDX-FileCopyrightText: 2002 Michael Matz <matz@kde.org>
6
7 SPDX-License-Identifier: LGPL-2.0-or-later
8*/
9
10/* Fast zone memory allocator with deallocation support, for use as obstack
11 or as general purpose allocator. It does no compaction. If the usage
12 pattern is non-optimal it might waste some memory while running. E.g.
13 allocating many small things at once, and then deallocating only every
14 second one, there is a high chance, that actually no memory is freed.
15 */
16
17#include "kzoneallocator_p.h"
18
19#include <kcompletion_debug.h>
20
21#include <QList>
22
23#include <stdio.h>
24
25class KZoneAllocator::MemBlock
26{
27public:
28 MemBlock(size_t s)
29 : size(s)
30 , ref(0)
31 , older(nullptr)
32 , newer(nullptr)
33 {
34 begin = new char[s];
35 }
36 ~MemBlock()
37 {
38 delete[] begin;
39 }
40 MemBlock(const MemBlock &) = delete;
41 MemBlock &operator=(const MemBlock &) = delete;
42 bool is_in(void *ptr) const
43 {
44 return !(begin > (char *)ptr || (begin + size) <= (char *)ptr);
45 }
46 size_t size;
47 unsigned int ref;
48 char *begin;
49 MemBlock *older;
50 MemBlock *newer;
51};
52
53class KZoneAllocator::Private
54{
55public:
56 Private()
57 : currentBlock(nullptr)
58 , blockSize(1)
59 , blockOffset(0)
60 , log2(0)
61 , num_blocks(0)
62 , hashList(nullptr)
63 , hashSize(0)
64 , hashDirty(true)
65 {
66 }
67
68 /* One block is 'current' to satisfy requests */
69 MemBlock *currentBlock;
70 /* Store block size from constructor */
71 quintptr blockSize;
72 /* Store offset into current block; size-offset is free */
73 quintptr blockOffset;
74 /* base-2 log of the block size */
75 unsigned int log2;
76 /* Count total number of allocated blocks */
77 unsigned int num_blocks;
78 /* Collection of lists of blocks, for lookups */
79 MemList **hashList;
80 /* Count of hashes */
81 unsigned int hashSize;
82 /* Flag the hashes as in need of reorganization */
83 bool hashDirty;
84};
85
86KZoneAllocator::KZoneAllocator(unsigned long _blockSize)
87 : d(new Private)
88{
89 while (d->blockSize < _blockSize) {
90 d->blockSize <<= 1;
91 d->log2++;
92 }
93
94 /* Make sure, that a block is allocated at the first time allocate()
95 is called (even with a 0 size). */
96 d->blockOffset = d->blockSize + 1;
97}
98
99KZoneAllocator::~KZoneAllocator()
100{
101 unsigned int count = 0;
102 if (d->hashList) {
103 /* No need to maintain the different lists in d->hashList[] anymore.
104 I.e. no need to use delBlock(). */
105 for (unsigned int i = 0; i < d->hashSize; i++) {
106 delete d->hashList[i];
107 }
108 delete[] d->hashList;
109 d->hashList = nullptr;
110 }
111 MemBlock *next;
112 for (; d->currentBlock; d->currentBlock = next) {
113 next = d->currentBlock->older;
114 delete d->currentBlock;
115 count++;
116 }
117#ifndef NDEBUG // as this is called quite late in the app, we don't care
118 // to use qDebug
119 if (count > 1) {
120 fprintf(stderr, format: "zone still contained %u blocks", count);
121 }
122#endif
123 delete d;
124}
125
126void KZoneAllocator::insertHash(MemBlock *b)
127{
128 quintptr adr = ((quintptr)b->begin) & (~(d->blockSize - 1));
129 quintptr end = ((quintptr)b->begin) + d->blockSize;
130 while (adr < end) {
131 quintptr key = adr >> d->log2;
132 key = key & (d->hashSize - 1);
133 if (!d->hashList[key]) {
134 d->hashList[key] = new QList<MemBlock *>;
135 }
136 d->hashList[key]->append(t: b);
137 adr += d->blockSize;
138 }
139}
140
141/*! Add a new memory block to the pool of blocks,
142 and reorganize the hash lists if needed.
143 \a b block to add
144 @internal
145*/
146void KZoneAllocator::addBlock(MemBlock *b)
147{
148 b->newer = nullptr;
149 b->older = d->currentBlock;
150 if (d->currentBlock) {
151 b->older->newer = b;
152 }
153 d->currentBlock = b;
154 d->num_blocks++;
155 /* If we either have no d->hashList at all, or since it's last construction
156 there are now many more blocks we reconstruct the list. But don't
157 make it larger than a certain maximum. */
158 if (d->hashList && ((d->num_blocks / 4) > d->hashSize && d->hashSize < 64 * 1024)) {
159 d->hashDirty = true;
160 }
161 /* Only insert this block into the hashlists, if we aren't going to
162 reconstruct them anyway. */
163 if (d->hashList && !d->hashDirty) {
164 insertHash(b);
165 }
166}
167
168/*! Reinitialize hash list. @internal */
169void KZoneAllocator::initHash()
170{
171 if (d->hashList) {
172 for (unsigned int i = 0; i < d->hashSize; i++) {
173 delete d->hashList[i];
174 }
175 delete[] d->hashList;
176 d->hashList = nullptr;
177 }
178 d->hashSize = 1;
179 while (d->hashSize < d->num_blocks) {
180 d->hashSize <<= 1;
181 }
182 if (d->hashSize < 1024) {
183 d->hashSize = 1024;
184 }
185 if (d->hashSize > 64 * 1024) {
186 d->hashSize = 64 * 1024;
187 }
188 d->hashList = new QList<MemBlock *> *[d->hashSize];
189 memset(s: d->hashList, c: 0, n: sizeof(QList<MemBlock *> *) * d->hashSize);
190 d->hashDirty = false;
191 for (MemBlock *b = d->currentBlock; b; b = b->older) {
192 insertHash(b);
193 }
194}
195
196/*! Delete a memory block. This @em really returns the memory to the heap.
197 \a b block to delete
198 @internal
199*/
200void KZoneAllocator::delBlock(MemBlock *b)
201{
202 /* Update also the hashlists if we aren't going to reconstruct them
203 soon. */
204 if (d->hashList && !d->hashDirty) {
205 quintptr adr = ((quintptr)b->begin) & (~(d->blockSize - 1));
206 quintptr end = ((quintptr)b->begin) + d->blockSize;
207 while (adr < end) {
208 quintptr key = adr >> d->log2;
209 key = key & (d->hashSize - 1);
210 if (d->hashList[key]) {
211 QList<MemBlock *> *list = d->hashList[key];
212 QList<MemBlock *>::Iterator it = list->begin();
213 QList<MemBlock *>::Iterator endit = list->end();
214 for (; it != endit; ++it) {
215 if (*it == b) {
216 list->erase(pos: it);
217 break;
218 }
219 }
220 }
221 adr += d->blockSize;
222 }
223 }
224 if (b->older) {
225 b->older->newer = b->newer;
226 }
227 if (b->newer) {
228 b->newer->older = b->older;
229 }
230 if (b == d->currentBlock) {
231 d->currentBlock = nullptr;
232 d->blockOffset = d->blockSize;
233 }
234 delete b;
235 d->num_blocks--;
236}
237
238void *KZoneAllocator::allocate(size_t _size)
239{
240 // Use the size of (void *) as alignment
241 const size_t alignment = sizeof(void *) - 1;
242 _size = (_size + alignment) & ~alignment;
243
244 if ((unsigned long)_size + d->blockOffset > d->blockSize) {
245 if (_size > d->blockSize) {
246 qCDebug(KCOMPLETION_LOG, "KZoneAllocator: allocating more than %zu bytes", (size_t)d->blockSize);
247 return nullptr;
248 }
249 addBlock(b: new MemBlock(d->blockSize));
250 d->blockOffset = 0;
251 // qDebug ("Allocating block #%d (%x)\n", d->num_blocks, d->currentBlock->begin);
252 }
253 void *result = (void *)(d->currentBlock->begin + d->blockOffset);
254 d->currentBlock->ref++;
255 d->blockOffset += _size;
256 return result;
257}
258
259void KZoneAllocator::deallocate(void *ptr)
260{
261 if (d->hashDirty) {
262 initHash();
263 }
264
265 quintptr key = (((quintptr)ptr) >> d->log2) & (d->hashSize - 1);
266 const QList<MemBlock *> *list = d->hashList[key];
267 if (!list) {
268 /* Can happen with certain usage pattern of intermixed free_since()
269 and deallocate(). */
270 // qDebug("Uhoh");
271 return;
272 }
273 QList<MemBlock *>::ConstIterator it = list->begin();
274 QList<MemBlock *>::ConstIterator endit = list->end();
275 for (; it != endit; ++it) {
276 MemBlock *cur = *it;
277 if (cur->is_in(ptr)) {
278 if (!--cur->ref) {
279 if (cur != d->currentBlock) {
280 delBlock(b: cur);
281 } else {
282 d->blockOffset = 0;
283 }
284 }
285 return;
286 }
287 }
288 /* Can happen with certain usage pattern of intermixed free_since()
289 and deallocate(). */
290 // qDebug("Uhoh2");
291}
292
293void KZoneAllocator::free_since(void *ptr)
294{
295 /* If we have a d->hashList and it's not yet dirty, see, if we will dirty
296 it by removing too many blocks. This will make the below delBlock()s
297 faster. */
298 if (d->hashList && !d->hashDirty) {
299 const MemBlock *b;
300 unsigned int removed = 0;
301 for (b = d->currentBlock; b; b = b->older, removed++) {
302 if (b->is_in(ptr)) {
303 break;
304 }
305 }
306 if (d->hashSize >= 4 * (d->num_blocks - removed)) {
307 d->hashDirty = true;
308 }
309 }
310 while (d->currentBlock && !d->currentBlock->is_in(ptr)) {
311 d->currentBlock = d->currentBlock->older;
312 delBlock(b: d->currentBlock->newer);
313 }
314 d->blockOffset = ((char *)ptr) - d->currentBlock->begin;
315}
316

source code of kcompletion/src/kzoneallocator.cpp