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) : size(s), ref(0), older(nullptr), newer(nullptr)
29  {
30  begin = new char[s];
31  }
32  ~MemBlock()
33  {
34  delete [] begin;
35  }
36  MemBlock(const MemBlock &) = delete;
37  MemBlock &operator=(const MemBlock &) = delete;
38  bool is_in(void *ptr) const
39  {
40  return !(begin > (char *)ptr
41  || (begin + size) <= (char *)ptr);
42  }
43  size_t size;
44  unsigned int ref;
45  char *begin;
46  MemBlock *older;
47  MemBlock *newer;
48 };
49 
50 class KZoneAllocator::Private
51 {
52 public:
53  Private()
54  : currentBlock(nullptr), blockSize(1),
55  blockOffset(0), log2(0), num_blocks(0),
56  hashList(nullptr), hashSize(0), hashDirty(true)
57  {
58  }
59 
61  MemBlock *currentBlock;
63  quintptr blockSize;
65  quintptr blockOffset;
67  unsigned int log2;
69  unsigned int num_blocks;
71  MemList **hashList;
73  unsigned int hashSize;
75  bool hashDirty;
76 };
77 
78 KZoneAllocator::KZoneAllocator(unsigned long _blockSize)
79  : d(new Private)
80 {
81  while (d->blockSize < _blockSize) {
82  d->blockSize <<= 1;
83  d->log2++;
84  }
85 
86  /* Make sure, that a block is allocated at the first time allocate()
87  is called (even with a 0 size). */
88  d->blockOffset = d->blockSize + 1;
89 }
90 
91 KZoneAllocator::~KZoneAllocator()
92 {
93  unsigned int count = 0;
94  if (d->hashList) {
95  /* No need to maintain the different lists in d->hashList[] anymore.
96  I.e. no need to use delBlock(). */
97  for (unsigned int i = 0; i < d->hashSize; i++) {
98  delete d->hashList[i];
99  }
100  delete [] d->hashList;
101  d->hashList = nullptr;
102  }
103  MemBlock *next;
104  for (; d->currentBlock; d->currentBlock = next) {
105  next = d->currentBlock->older;
106  delete d->currentBlock;
107  count++;
108  }
109 #ifndef NDEBUG // as this is called quite late in the app, we don't care
110  // to use qDebug
111  if (count > 1) {
112  fprintf(stderr, "zone still contained %u blocks", count);
113  }
114 #endif
115  delete d;
116 }
117 
118 void KZoneAllocator::insertHash(MemBlock *b)
119 {
120  quintptr adr = ((quintptr)b->begin) & (~(d->blockSize - 1));
121  quintptr end = ((quintptr)b->begin) + d->blockSize;
122  while (adr < end) {
123  quintptr key = adr >> d->log2;
124  key = key & (d->hashSize - 1);
125  if (!d->hashList[key]) {
126  d->hashList[key] = new QList<MemBlock *>;
127  }
128  d->hashList[key]->append(b);
129  adr += d->blockSize;
130  }
131 }
132 
138 void KZoneAllocator::addBlock(MemBlock *b)
139 {
140  b->newer = nullptr;
141  b->older = d->currentBlock;
142  if (d->currentBlock) {
143  b->older->newer = b;
144  }
145  d->currentBlock = b;
146  d->num_blocks++;
147  /* If we either have no d->hashList at all, or since it's last construction
148  there are now many more blocks we reconstruct the list. But don't
149  make it larger than a certain maximum. */
150  if (d->hashList && ((d->num_blocks / 4) > d->hashSize && d->hashSize < 64 * 1024)) {
151  d->hashDirty = true;
152  }
153  /* Only insert this block into the hashlists, if we aren't going to
154  reconstruct them anyway. */
155  if (d->hashList && !d->hashDirty) {
156  insertHash(b);
157  }
158 }
159 
161 void KZoneAllocator::initHash()
162 {
163  if (d->hashList) {
164  for (unsigned int i = 0; i < d->hashSize; i++) {
165  delete d->hashList[i];
166  }
167  delete [] d->hashList;
168  d->hashList = nullptr;
169  }
170  d->hashSize = 1;
171  while (d->hashSize < d->num_blocks) {
172  d->hashSize <<= 1;
173  }
174  if (d->hashSize < 1024) {
175  d->hashSize = 1024;
176  }
177  if (d->hashSize > 64 * 1024) {
178  d->hashSize = 64 * 1024;
179  }
180  d->hashList = new QList<MemBlock *> *[d->hashSize];
181  memset(d->hashList, 0, sizeof(QList<MemBlock *> *) * d->hashSize);
182  d->hashDirty = false;
183  for (MemBlock *b = d->currentBlock; b; b = b->older) {
184  insertHash(b);
185  }
186 }
187 
192 void KZoneAllocator::delBlock(MemBlock *b)
193 {
194  /* Update also the hashlists if we aren't going to reconstruct them
195  soon. */
196  if (d->hashList && !d->hashDirty) {
197  quintptr adr = ((quintptr)b->begin) & (~(d->blockSize - 1));
198  quintptr end = ((quintptr)b->begin) + d->blockSize;
199  while (adr < end) {
200  quintptr key = adr >> d->log2;
201  key = key & (d->hashSize - 1);
202  if (d->hashList[key]) {
203  QList<MemBlock *> *list = d->hashList[key];
204  QList<MemBlock *>::Iterator it = list->begin();
205  QList<MemBlock *>::Iterator endit = list->end();
206  for (; it != endit; ++it)
207  if (*it == b) {
208  list->erase(it);
209  break;
210  }
211  }
212  adr += d->blockSize;
213  }
214  }
215  if (b->older) {
216  b->older->newer = b->newer;
217  }
218  if (b->newer) {
219  b->newer->older = b->older;
220  }
221  if (b == d->currentBlock) {
222  d->currentBlock = nullptr;
223  d->blockOffset = d->blockSize;
224  }
225  delete b;
226  d->num_blocks--;
227 }
228 
229 void *
230 KZoneAllocator::allocate(size_t _size)
231 {
232  // Use the size of (void *) as alignment
233  const size_t alignment = sizeof(void *) - 1;
234  _size = (_size + alignment) & ~alignment;
235 
236  if ((unsigned long) _size + d->blockOffset > d->blockSize) {
237  if (_size > d->blockSize) {
238  qCDebug(KCOMPLETION_LOG, "KZoneAllocator: allocating more than %zu bytes", (size_t)d->blockSize);
239  return nullptr;
240  }
241  addBlock(new MemBlock(d->blockSize));
242  d->blockOffset = 0;
243  //qDebug ("Allocating block #%d (%x)\n", d->num_blocks, d->currentBlock->begin);
244  }
245  void *result = (void *)(d->currentBlock->begin + d->blockOffset);
246  d->currentBlock->ref++;
247  d->blockOffset += _size;
248  return result;
249 }
250 
251 void
252 KZoneAllocator::deallocate(void *ptr)
253 {
254  if (d->hashDirty) {
255  initHash();
256  }
257 
258  quintptr key = (((quintptr)ptr) >> d->log2) & (d->hashSize - 1);
259  const QList<MemBlock *> *list = d->hashList[key];
260  if (!list) {
261  /* Can happen with certain usage pattern of intermixed free_since()
262  and deallocate(). */
263  //qDebug("Uhoh");
264  return;
265  }
267  QList<MemBlock *>::ConstIterator endit = list->end();
268  for (; it != endit; ++it) {
269  MemBlock *cur = *it;
270  if (cur->is_in(ptr)) {
271  if (!--cur->ref) {
272  if (cur != d->currentBlock) {
273  delBlock(cur);
274  } else {
275  d->blockOffset = 0;
276  }
277  }
278  return;
279  }
280  }
281  /* Can happen with certain usage pattern of intermixed free_since()
282  and deallocate(). */
283  //qDebug("Uhoh2");
284 }
285 
286 void
287 KZoneAllocator::free_since(void *ptr)
288 {
289  /* If we have a d->hashList and it's not yet dirty, see, if we will dirty
290  it by removing too many blocks. This will make the below delBlock()s
291  faster. */
292  if (d->hashList && !d->hashDirty) {
293  const MemBlock *b;
294  unsigned int removed = 0;
295  for (b = d->currentBlock; b; b = b->older, removed++)
296  if (b->is_in(ptr)) {
297  break;
298  }
299  if (d->hashSize >= 4 * (d->num_blocks - removed)) {
300  d->hashDirty = true;
301  }
302  }
303  while (d->currentBlock && !d->currentBlock->is_in(ptr)) {
304  d->currentBlock = d->currentBlock->older;
305  delBlock(d->currentBlock->newer);
306  }
307  d->blockOffset = ((char *)ptr) - d->currentBlock->begin;
308 }
MESSAGECORE_EXPORT KMime::Content * next(KMime::Content *node, bool allowChildren=true)
QList::iterator erase(QList::iterator pos)
void ref()
const QList< QKeySequence > & begin()
void append(const T &value)
QList::iterator begin()
KIOFILEWIDGETS_EXPORT QStringList list(const QString &fileClass)
This file is part of the KDE documentation.
Documentation copyright © 1996-2020 The KDE developers.
Generated on Mon Aug 10 2020 22:55:33 by doxygen 1.8.11 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.