KHtml

arena.cpp
1 /*
2  * Copyright (C) 1998-2000 Netscape Communications Corporation.
3  *
4  * Other contributors:
5  * Nick Blievers <[email protected]>
6  * Jeff Hostetler <[email protected]>
7  * Tom Rini <[email protected]>
8  * Raffaele Sena <[email protected]>
9  *
10  * This library is free software; you can redistribute it and/or
11  * modify it under the terms of the GNU Lesser General Public
12  * License as published by the Free Software Foundation; either
13  * version 2.1 of the License, or (at your option) any later version.
14  *
15  * This library is distributed in the hope that it will be useful,
16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18  * Lesser General Public License for more details.
19  *
20  * You should have received a copy of the GNU Lesser General Public
21  * License along with this library; if not, write to the Free Software
22  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
23  *
24  * Alternatively, the contents of this file may be used under the terms
25  * of either the Mozilla Public License Version 1.1, found at
26  * http://www.mozilla.org/MPL/ (the "MPL") or the GNU General Public
27  * License Version 2.0, found at http://www.fsf.org/copyleft/gpl.html
28  * (the "GPL"), in which case the provisions of the MPL or the GPL are
29  * applicable instead of those above. If you wish to allow use of your
30  * version of this file only under the terms of one of those two
31  * licenses (the MPL or the GPL) and not to allow others to use your
32  * version of this file under the LGPL, indicate your decision by
33  * deletingthe provisions above and replace them with the notice and
34  * other provisions required by the MPL or the GPL, as the case may be.
35  * If you do not delete the provisions above, a recipient may use your
36  * version of this file under any of the LGPL, the MPL or the GPL.
37  */
38 
39 /*
40  * Lifetime-based fast allocation, inspired by much prior art, including
41  * "Fast Allocation and Deallocation of Memory Based on Object Lifetimes"
42  * David R. Hanson, Software -- Practice and Experience, Vol. 20(1).
43  */
44 
45 #include "arena.h"
46 
47 #include <stdlib.h>
48 #include <string.h>
49 
50 #if HAVE_GETPAGESIZE
51 #include <unistd.h>
52 #define POOL_SIZE qMax(8192u, 2*( unsigned ) getpagesize())
53 #else
54 #define POOL_SIZE 8192
55 #endif
56 
57 //#define DEBUG_ARENA_MALLOC
58 #ifdef DEBUG_ARENA_MALLOC
59 #include <assert.h>
60 #include <stdio.h>
61 #endif
62 
63 namespace khtml
64 {
65 
66 #ifdef DEBUG_ARENA_MALLOC
67 static int i = 0;
68 #endif
69 
70 #define FREELIST_MAX 50
71 #define LARGE_ALLOCATION_CEIL(pool) (pool)->arenasize * 256
72 #define MAX_DISCRETE_ALLOCATION(pool) (pool)->arenasize * 64
73 static Arena *arena_freelist = nullptr;
74 static int freelist_count = 0;
75 
76 #define ARENA_DEFAULT_ALIGN sizeof(double)
77 #define BIT(n) ((unsigned int)1 << (n))
78 #define BITMASK(n) (BIT(n) - 1)
79 #define CEILING_LOG2(_log2,_n) \
80  unsigned int j_ = (unsigned int)(_n); \
81  (_log2) = 0; \
82  if ((j_) & ((j_)-1)) \
83  (_log2) += 1; \
84  if ((j_) >> 16) \
85  (_log2) += 16, (j_) >>= 16; \
86  if ((j_) >> 8) \
87  (_log2) += 8, (j_) >>= 8; \
88  if ((j_) >> 4) \
89  (_log2) += 4, (j_) >>= 4; \
90  if ((j_) >> 2) \
91  (_log2) += 2, (j_) >>= 2; \
92  if ((j_) >> 1) \
93  (_log2) += 1;
94 
95 int CeilingLog2(unsigned int i)
96 {
97  int log2;
98  CEILING_LOG2(log2, i);
99  return log2;
100 }
101 
102 void InitArenaPool(ArenaPool *pool, const char * /*name*/,
103  unsigned int /*size*/, unsigned int align)
104 {
105  unsigned int size = POOL_SIZE;
106  if (align == 0) {
107  align = ARENA_DEFAULT_ALIGN;
108  }
109  pool->mask = BITMASK(CeilingLog2(align));
110  pool->first.next = nullptr;
111  pool->first.base = pool->first.avail = pool->first.limit =
112  (uword)ARENA_ALIGN(pool, &pool->first + 1);
113  pool->current = &pool->first;
114  pool->arenasize = size;
115  pool->largealloc = LARGE_ALLOCATION_CEIL(pool);
116  pool->cumul = freelist_count * size;
117 }
118 
119 /*
120  ** ArenaAllocate() -- allocate space from an arena pool
121  **
122  ** Description: ArenaAllocate() allocates space from an arena
123  ** pool.
124  **
125  ** First try to satisfy the request from arenas starting at
126  ** pool->current.
127  **
128  ** If there is not enough space in the arena pool->current, try
129  ** to claim an arena, on a first fit basis, from the global
130  ** freelist (arena_freelist).
131  **
132  ** If no arena in arena_freelist is suitable, then try to
133  ** allocate a new arena from the heap.
134  **
135  ** Returns: pointer to allocated space or NULL
136  **
137  */
138 void *ArenaAllocate(ArenaPool *pool, unsigned int nb)
139 {
140  Arena *a;
141  char *rp; /* returned pointer */
142 
143 #ifdef DEBUG_ARENA_MALLOC
144  assert((nb & pool->mask) == 0);
145 #endif
146 
147  nb = (uword)ARENA_ALIGN(pool, nb); /* force alignment */
148 
149  /* attempt to allocate from arenas at pool->current */
150  {
151  a = pool->current;
152  do {
153  if (a->avail + nb <= a->limit) {
154  pool->current = a;
155  rp = (char *)a->avail;
156  a->avail += nb;
157  VALGRIND_MEMPOOL_ALLOC(a->base, rp, nb);
158  return rp;
159  }
160  } while (nullptr != (a = a->next));
161  }
162 
163  /* attempt to allocate from arena_freelist */
164  {
165  Arena *p; /* previous pointer, for unlinking from freelist */
166 
167  for (a = p = arena_freelist; a != nullptr; p = a, a = a->next) {
168  if (a->base + nb <= a->limit) {
169  if (p == arena_freelist) {
170  arena_freelist = a->next;
171  } else {
172  p->next = a->next;
173  }
174  a->avail = a->base;
175  rp = (char *)a->avail;
176  a->avail += nb;
177  VALGRIND_MEMPOOL_ALLOC(a->base, rp, nb);
178  /* the newly allocated arena is linked after pool->current
179  * and becomes pool->current */
180  a->next = pool->current->next;
181  pool->current->next = a;
182  pool->current = a;
183  if (nullptr == pool->first.next) {
184  pool->first.next = a;
185  }
186  freelist_count--;
187  return (rp);
188  }
189  }
190  }
191 
192  /* attempt to allocate from the heap */
193  {
194  unsigned int sz;
195 #if HAVE_MMAP
196  if (pool->cumul > pool->largealloc) {
197  // High memory pressure. Switch to a fractional allocation strategy
198  // so that malloc gets a chance to successfully trim us down when it's over.
199  sz = qMin(pool->cumul / 12, MAX_DISCRETE_ALLOCATION(pool));
200 #ifdef DEBUG_ARENA_MALLOC
201  printf("allocating %d bytes (fractional strategy)\n", sz);
202 #endif
203  } else
204 #endif
205  sz = pool->arenasize > nb ? pool->arenasize : nb;
206  sz += sizeof * a + pool->mask; /* header and alignment slop */
207  pool->cumul += sz;
208 #ifdef DEBUG_ARENA_MALLOC
209  i++;
210  printf("Malloc: %d\n", i);
211 #endif
212  a = (Arena *)malloc(sz);
213  if (a) {
214  a->limit = (uword)a + sz;
215  a->base = a->avail = (uword)ARENA_ALIGN(pool, a + 1);
216  VALGRIND_CREATE_MEMPOOL(a->base, 0, 0);
217  rp = (char *)a->avail;
218  a->avail += nb;
219  VALGRIND_MEMPOOL_ALLOC(a->base, rp, nb);
220 
221  /* the newly allocated arena is linked after pool->current
222  * and becomes pool->current */
223  a->next = pool->current->next;
224  pool->current->next = a;
225  pool->current = a;
226  if (!pool->first.next) {
227  pool->first.next = a;
228  }
229  return (rp);
230  }
231  }
232 
233  /* we got to here, and there's no memory to allocate */
234  return (nullptr);
235 } /* --- end ArenaAllocate() --- */
236 
237 /*
238  * Free tail arenas linked after head, which may not be the true list head.
239  * Reset pool->current to point to head in case it pointed at a tail arena.
240  */
241 static void FreeArenaList(ArenaPool *pool, Arena *head, bool reallyFree)
242 {
243  Arena **ap, *a;
244 
245  ap = &head->next;
246  a = *ap;
247  if (!a) {
248  return;
249  }
250 
251 #ifdef DEBUG_ARENA_MALLOC
252  printf("****** Freeing arena pool. Total allocated memory: %d\n", pool->cumul);
253 
254  do {
255  assert(a->base <= a->avail && a->avail <= a->limit);
256  a->avail = a->base;
257  CLEAR_UNUSED(a);
258  } while ((a = a->next) != 0);
259  a = *ap;
260 #endif
261 
262  if (freelist_count >= FREELIST_MAX) {
263  reallyFree = true;
264  }
265 
266  if (reallyFree) {
267  do {
268  *ap = a->next;
269  VALGRIND_DESTROY_MEMPOOL(a->base);
270  CLEAR_ARENA(a);
271 #ifdef DEBUG_ARENA_MALLOC
272  if (a) {
273  i--;
274  printf("Free: %d\n", i);
275  }
276 #endif
277  free(a); a = nullptr;
278  } while ((a = *ap) != nullptr);
279  } else {
280  /* Insert as much of the arena chain as we can hold at the front of the freelist. */
281  do {
282  ap = &(*ap)->next;
283  freelist_count++;
284  } while (*ap && freelist_count < FREELIST_MAX);
285 
286  /* Get rid of excess */
287  if (*ap) {
288  Arena *xa, *n;
289  for (xa = *ap; xa; xa = n) {
290  VALGRIND_DESTROY_MEMPOOL(xa->base);
291  n = xa->next;
292 #ifdef DEBUG_ARENA_MALLOC
293  i--;
294  printf("Free: %d\n", i);
295 #endif
296  CLEAR_ARENA(xa);
297  free(xa);
298  }
299  }
300  *ap = arena_freelist;
301  arena_freelist = a;
302  head->next = nullptr;
303  }
304  pool->current = head;
305 }
306 
307 void ArenaRelease(ArenaPool *pool, char *mark)
308 {
309  Arena *a;
310 
311  for (a = pool->first.next; a; a = a->next) {
312  if (UPTRDIFF(mark, a->base) < UPTRDIFF(a->avail, a->base)) {
313  a->avail = (uword)ARENA_ALIGN(pool, mark);
314  FreeArenaList(pool, a, false);
315  return;
316  }
317  }
318 }
319 
320 void FreeArenaPool(ArenaPool *pool)
321 {
322  FreeArenaList(pool, &pool->first, false);
323 }
324 
325 void FinishArenaPool(ArenaPool *pool)
326 {
327  FreeArenaList(pool, &pool->first, true);
328 }
329 
330 void ArenaFinish()
331 {
332  Arena *a, *next;
333 #ifdef DEBUG_ARENA_MALLOC
334  printf("releasing global Arena freelist\n");
335 #endif
336  for (a = arena_freelist; a; a = next) {
337  next = a->next;
338  free(a); a = nullptr;
339  }
340  freelist_count = 0;
341  arena_freelist = nullptr;
342 }
343 
344 } // namespace
This file is part of the HTML rendering engine for KDE.
MESSAGECORE_EXPORT KMime::Content * next(KMime::Content *node, bool allowChildren=true)
This file is part of the KDE documentation.
Documentation copyright © 1996-2021 The KDE developers.
Generated on Sat Oct 16 2021 22:47:50 by doxygen 1.8.11 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.