KCompletion

kzoneallocator.cpp
1 /*
2  This file is part of the KDE libraries
3 
4  SPDX-FileCopyrightText: 1999 Waldo Bastian <[email protected]>
5  SPDX-FileCopyrightText: 2002 Michael Matz <[email protected]>
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 
25 class KZoneAllocator::MemBlock
26 {
27 public:
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 
53 class KZoneAllocator::Private
54 {
55 public:
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. @internal */
69  MemBlock *currentBlock;
70  /** Store block size from constructor. @internal */
71  quintptr blockSize;
72  /** Store offset into current block; size-offset is free. @internal */
73  quintptr blockOffset;
74  /** base-2 log of the block size. @internal */
75  unsigned int log2;
76  /** Count total number of allocated blocks. @internal */
77  unsigned int num_blocks;
78  /** Collection of lists of blocks, for lookups. @internal */
79  MemList **hashList;
80  /** Count of hashes. @internal */
81  unsigned int hashSize;
82  /** Flag the hashes as in need of reorganization. @internal */
83  bool hashDirty;
84 };
85 
86 KZoneAllocator::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 
99 KZoneAllocator::~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, "zone still contained %u blocks", count);
121  }
122 #endif
123  delete d;
124 }
125 
126 void 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(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  @param b block to add
144  @internal
145 */
146 void 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 */
169 void 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(d->hashList, 0, 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  @param b block to delete
198  @internal
199 */
200 void 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];
214  for (; it != endit; ++it) {
215  if (*it == b) {
216  list->erase(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 
238 void *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(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 
259 void 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  }
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(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 
293 void 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(d->currentBlock->newer);
313  }
314  d->blockOffset = ((char *)ptr) - d->currentBlock->begin;
315 }
void append(const T &value)
void ref()
KIOFILEWIDGETS_EXPORT QStringList list(const QString &fileClass)
const QList< QKeySequence > & begin()
QList::iterator erase(QList::iterator pos)
QList::iterator begin()
QList::iterator end()
QAction * next(const QObject *recvr, const char *slot, QObject *parent)
const QList< QKeySequence > & end()
This file is part of the KDE documentation.
Documentation copyright © 1996-2022 The KDE developers.
Generated on Sun Jun 26 2022 04:11:17 by doxygen 1.8.17 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.