1 /* GLIB sliced memory - fast concurrent memory chunk allocator
2 * Copyright (C) 2005 Tim Janik
3 *
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License as published by the Free Software Foundation; either
7 * version 2.1 of the License, or (at your option) any later version.
8 *
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Lesser General Public License for more details.
13 *
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with this library; if not, see <http://www.gnu.org/licenses/>.
16 */
17 /* MT safe */
18
19 #include "config.h"
20 #include "glibconfig.h"
21
22 #if defined(HAVE_POSIX_MEMALIGN) && !defined(_XOPEN_SOURCE)
23 #define _XOPEN_SOURCE 600 /* posix_memalign() */
24 #endif
25 #include <stdlib.h> /* posix_memalign() */
26 #include <string.h>
27 #include <errno.h>
28
29 #ifdef G_OS_UNIX
30 #include <unistd.h> /* sysconf() */
31 #endif
32 #ifdef G_OS_WIN32
33 #include <windows.h>
34 #include <process.h>
35 #endif
36
37 #include <stdio.h> /* fputs */
38
39 #include "gslice.h"
40
41 #include "gmain.h"
42 #include "gmem.h" /* gslice.h */
43 #include "gstrfuncs.h"
44 #include "gutils.h"
45 #include "gtrashstack.h"
46 #include "gtestutils.h"
47 #include "gthread.h"
48 #include "gthreadprivate.h"
49 #include "glib_trace.h"
50 #include "gprintf.h"
51
52 #include "gvalgrind.h"
53
54 #include "gmemdfx.h"
55
56 #if defined(G_MEM_DFX)
57
58 #define DFX_TRACE(probe) probe
59
60 #else
61
62 #define DFX_TRACE(probe)
63
64 #endif
65
66 /**
67 * SECTION:memory_slices
68 * @title: Memory Slices
69 * @short_description: efficient way to allocate groups of equal-sized
70 * chunks of memory
71 *
72 * Memory slices provide a space-efficient and multi-processing scalable
73 * way to allocate equal-sized pieces of memory, just like the original
74 * #GMemChunks (from GLib 2.8), while avoiding their excessive
75 * memory-waste, scalability and performance problems.
76 *
77 * To achieve these goals, the slice allocator uses a sophisticated,
78 * layered design that has been inspired by Bonwick's slab allocator
79 * ([Bonwick94](http://citeseer.ist.psu.edu/bonwick94slab.html)
80 * Jeff Bonwick, The slab allocator: An object-caching kernel
81 * memory allocator. USENIX 1994, and
82 * [Bonwick01](http://citeseer.ist.psu.edu/bonwick01magazines.html)
83 * Bonwick and Jonathan Adams, Magazines and vmem: Extending the
84 * slab allocator to many cpu's and arbitrary resources. USENIX 2001)
85 *
86 * It uses posix_memalign() to optimize allocations of many equally-sized
87 * chunks, and has per-thread free lists (the so-called magazine layer)
88 * to quickly satisfy allocation requests of already known structure sizes.
89 * This is accompanied by extra caching logic to keep freed memory around
90 * for some time before returning it to the system. Memory that is unused
91 * due to alignment constraints is used for cache colorization (random
92 * distribution of chunk addresses) to improve CPU cache utilization. The
93 * caching layer of the slice allocator adapts itself to high lock contention
94 * to improve scalability.
95 *
96 * The slice allocator can allocate blocks as small as two pointers, and
97 * unlike malloc(), it does not reserve extra space per block. For large block
98 * sizes, g_slice_new() and g_slice_alloc() will automatically delegate to the
99 * system malloc() implementation. For newly written code it is recommended
100 * to use the new `g_slice` API instead of g_malloc() and
101 * friends, as long as objects are not resized during their lifetime and the
102 * object size used at allocation time is still available when freeing.
103 *
104 * Here is an example for using the slice allocator:
105 * |[<!-- language="C" -->
106 * gchar *mem[10000];
107 * gint i;
108 *
109 * // Allocate 10000 blocks.
110 * for (i = 0; i < 10000; i++)
111 * {
112 * mem[i] = g_slice_alloc (50);
113 *
114 * // Fill in the memory with some junk.
115 * for (j = 0; j < 50; j++)
116 * mem[i][j] = i * j;
117 * }
118 *
119 * // Now free all of the blocks.
120 * for (i = 0; i < 10000; i++)
121 * g_slice_free1 (50, mem[i]);
122 * ]|
123 *
124 * And here is an example for using the using the slice allocator
125 * with data structures:
126 * |[<!-- language="C" -->
127 * GRealArray *array;
128 *
129 * // Allocate one block, using the g_slice_new() macro.
130 * array = g_slice_new (GRealArray);
131 *
132 * // We can now use array just like a normal pointer to a structure.
133 * array->data = NULL;
134 * array->len = 0;
135 * array->alloc = 0;
136 * array->zero_terminated = (zero_terminated ? 1 : 0);
137 * array->clear = (clear ? 1 : 0);
138 * array->elt_size = elt_size;
139 *
140 * // We can free the block, so it can be reused.
141 * g_slice_free (GRealArray, array);
142 * ]|
143 */
144
145 /* the GSlice allocator is split up into 4 layers, roughly modelled after the slab
146 * allocator and magazine extensions as outlined in:
147 * + [Bonwick94] Jeff Bonwick, The slab allocator: An object-caching kernel
148 * memory allocator. USENIX 1994, http://citeseer.ist.psu.edu/bonwick94slab.html
149 * + [Bonwick01] Bonwick and Jonathan Adams, Magazines and vmem: Extending the
150 * slab allocator to many cpu's and arbitrary resources.
151 * USENIX 2001, http://citeseer.ist.psu.edu/bonwick01magazines.html
152 * the layers are:
153 * - the thread magazines. for each (aligned) chunk size, a magazine (a list)
154 * of recently freed and soon to be allocated chunks is maintained per thread.
155 * this way, most alloc/free requests can be quickly satisfied from per-thread
156 * free lists which only require one g_private_get() call to retrieve the
157 * thread handle.
158 * - the magazine cache. allocating and freeing chunks to/from threads only
159 * occurs at magazine sizes from a global depot of magazines. the depot
160 * maintaines a 15 second working set of allocated magazines, so full
161 * magazines are not allocated and released too often.
162 * the chunk size dependent magazine sizes automatically adapt (within limits,
163 * see [3]) to lock contention to properly scale performance across a variety
164 * of SMP systems.
165 * - the slab allocator. this allocator allocates slabs (blocks of memory) close
166 * to the system page size or multiples thereof which have to be page aligned.
167 * the blocks are divided into smaller chunks which are used to satisfy
168 * allocations from the upper layers. the space provided by the reminder of
169 * the chunk size division is used for cache colorization (random distribution
170 * of chunk addresses) to improve processor cache utilization. multiple slabs
171 * with the same chunk size are kept in a partially sorted ring to allow O(1)
172 * freeing and allocation of chunks (as long as the allocation of an entirely
173 * new slab can be avoided).
174 * - the page allocator. on most modern systems, posix_memalign(3) or
175 * memalign(3) should be available, so this is used to allocate blocks with
176 * system page size based alignments and sizes or multiples thereof.
177 * if no memalign variant is provided, valloc() is used instead and
178 * block sizes are limited to the system page size (no multiples thereof).
179 * as a fallback, on system without even valloc(), a malloc(3)-based page
180 * allocator with alloc-only behaviour is used.
181 *
182 * NOTES:
183 * [1] some systems memalign(3) implementations may rely on boundary tagging for
184 * the handed out memory chunks. to avoid excessive page-wise fragmentation,
185 * we reserve 2 * sizeof (void*) per block size for the systems memalign(3),
186 * specified in NATIVE_MALLOC_PADDING.
187 * [2] using the slab allocator alone already provides for a fast and efficient
188 * allocator, it doesn't properly scale beyond single-threaded uses though.
189 * also, the slab allocator implements eager free(3)-ing, i.e. does not
190 * provide any form of caching or working set maintenance. so if used alone,
191 * it's vulnerable to trashing for sequences of balanced (alloc, free) pairs
192 * at certain thresholds.
193 * [3] magazine sizes are bound by an implementation specific minimum size and
194 * a chunk size specific maximum to limit magazine storage sizes to roughly
195 * 16KB.
196 * [4] allocating ca. 8 chunks per block/page keeps a good balance between
197 * external and internal fragmentation (<= 12.5%). [Bonwick94]
198 */
199
200 /* --- macros and constants --- */
201 #define LARGEALIGNMENT (256)
202 #define P2ALIGNMENT (2 * sizeof (gsize)) /* fits 2 pointers (assumed to be 2 * GLIB_SIZEOF_SIZE_T below) */
203 #define ALIGN(size, base) ((base) * (gsize) (((size) + (base) - 1) / (base)))
204 #define NATIVE_MALLOC_PADDING P2ALIGNMENT /* per-page padding left for native malloc(3) see [1] */
205 #define SLAB_INFO_SIZE P2ALIGN (sizeof (SlabInfo) + NATIVE_MALLOC_PADDING)
206 #define MAX_MAGAZINE_SIZE (256) /* see [3] and allocator_get_magazine_threshold() for this */
207 #define MIN_MAGAZINE_SIZE (4)
208 #define MAX_STAMP_COUNTER (7) /* distributes the load of gettimeofday() */
209 #define MAX_SLAB_CHUNK_SIZE(al) (((al)->max_page_size - SLAB_INFO_SIZE) / 8) /* we want at last 8 chunks per page, see [4] */
210 #define MAX_SLAB_INDEX(al) (SLAB_INDEX (al, MAX_SLAB_CHUNK_SIZE (al)) + 1)
211 #define SLAB_INDEX(al, asize) ((asize) / P2ALIGNMENT - 1) /* asize must be P2ALIGNMENT aligned */
212 #define SLAB_CHUNK_SIZE(al, ix) (((ix) + 1) * P2ALIGNMENT)
213 #define SLAB_BPAGE_SIZE(al,csz) (8 * (csz) + SLAB_INFO_SIZE)
214
215 /* optimized version of ALIGN (size, P2ALIGNMENT) */
216 #if GLIB_SIZEOF_SIZE_T * 2 == 8 /* P2ALIGNMENT */
217 #define P2ALIGN(size) (((size) + 0x7) & ~(gsize) 0x7)
218 #elif GLIB_SIZEOF_SIZE_T * 2 == 16 /* P2ALIGNMENT */
219 #define P2ALIGN(size) (((size) + 0xf) & ~(gsize) 0xf)
220 #else
221 #define P2ALIGN(size) ALIGN (size, P2ALIGNMENT)
222 #endif
223
224 /* special helpers to avoid gmessage.c dependency */
225 static void mem_error (const char *format, ...) G_GNUC_PRINTF (1,2);
226 #define mem_assert(cond) do { if (G_LIKELY (cond)) ; else mem_error ("assertion failed: %s", #cond); } while (0)
227
228 /* --- structures --- */
229 typedef struct _ChunkLink ChunkLink;
230 typedef struct _SlabInfo SlabInfo;
231 typedef struct _CachedMagazine CachedMagazine;
232 struct _ChunkLink {
233 ChunkLink *next;
234 ChunkLink *data;
235 };
236 struct _SlabInfo {
237 ChunkLink *chunks;
238 guint n_allocated;
239 SlabInfo *next, *prev;
240 };
241 typedef struct {
242 ChunkLink *chunks;
243 gsize count; /* approximative chunks list length */
244 } Magazine;
245 typedef struct {
246 Magazine *magazine1; /* array of MAX_SLAB_INDEX (allocator) */
247 Magazine *magazine2; /* array of MAX_SLAB_INDEX (allocator) */
248 } ThreadMemory;
249 typedef struct {
250 gboolean always_malloc;
251 gboolean bypass_magazines;
252 gboolean debug_blocks;
253 gsize working_set_msecs;
254 guint color_increment;
255 } SliceConfig;
256 typedef struct {
257 /* const after initialization */
258 gsize min_page_size, max_page_size;
259 SliceConfig config;
260 gsize max_slab_chunk_size_for_magazine_cache;
261 /* magazine cache */
262 GMutex magazine_mutex;
263 ChunkLink **magazines; /* array of MAX_SLAB_INDEX (allocator) */
264 guint *contention_counters; /* array of MAX_SLAB_INDEX (allocator) */
265 gint mutex_counter;
266 guint stamp_counter;
267 guint last_stamp;
268 /* slab allocator */
269 GMutex slab_mutex;
270 SlabInfo **slab_stack; /* array of MAX_SLAB_INDEX (allocator) */
271 guint color_accu;
272 } Allocator;
273
274 /* --- g-slice prototypes --- */
275 static gpointer slab_allocator_alloc_chunk (gsize chunk_size);
276 static void slab_allocator_free_chunk (gsize chunk_size,
277 gpointer mem);
278 static void private_thread_memory_cleanup (gpointer data);
279 static gpointer allocator_memalign (gsize alignment,
280 gsize memsize);
281 static void allocator_memfree (gsize memsize,
282 gpointer mem);
283 static inline void magazine_cache_update_stamp (void);
284 static inline gsize allocator_get_magazine_threshold (Allocator *allocator,
285 guint ix);
286
287 /* --- g-slice memory checker --- */
288 static void smc_notify_alloc (void *pointer,
289 size_t size);
290 static int smc_notify_free (void *pointer,
291 size_t size);
292
293 /* --- variables --- */
294 static GPrivate private_thread_memory = G_PRIVATE_INIT (private_thread_memory_cleanup);
295 static gsize sys_page_size = 0;
296 static Allocator allocator[1] = { { 0, }, };
297 static SliceConfig slice_config = {
298 FALSE, /* always_malloc */
299 FALSE, /* bypass_magazines */
300 FALSE, /* debug_blocks */
301 15 * 1000, /* working_set_msecs */
302 1, /* color increment, alt: 0x7fffffff */
303 };
304 static GMutex smc_tree_mutex; /* mutex for G_SLICE=debug-blocks */
305
306 /* --- auxiliary functions --- */
307 void
g_slice_set_config(GSliceConfig ckey,gint64 value)308 g_slice_set_config (GSliceConfig ckey,
309 gint64 value)
310 {
311 g_return_if_fail (sys_page_size == 0);
312 switch (ckey)
313 {
314 case G_SLICE_CONFIG_ALWAYS_MALLOC:
315 slice_config.always_malloc = value != 0;
316 break;
317 case G_SLICE_CONFIG_BYPASS_MAGAZINES:
318 slice_config.bypass_magazines = value != 0;
319 break;
320 case G_SLICE_CONFIG_WORKING_SET_MSECS:
321 slice_config.working_set_msecs = value;
322 break;
323 case G_SLICE_CONFIG_COLOR_INCREMENT:
324 slice_config.color_increment = value;
325 break;
326 default: ;
327 }
328 }
329
330 gint64
g_slice_get_config(GSliceConfig ckey)331 g_slice_get_config (GSliceConfig ckey)
332 {
333 switch (ckey)
334 {
335 case G_SLICE_CONFIG_ALWAYS_MALLOC:
336 return slice_config.always_malloc;
337 case G_SLICE_CONFIG_BYPASS_MAGAZINES:
338 return slice_config.bypass_magazines;
339 case G_SLICE_CONFIG_WORKING_SET_MSECS:
340 return slice_config.working_set_msecs;
341 case G_SLICE_CONFIG_CHUNK_SIZES:
342 return MAX_SLAB_INDEX (allocator);
343 case G_SLICE_CONFIG_COLOR_INCREMENT:
344 return slice_config.color_increment;
345 default:
346 return 0;
347 }
348 }
349
350 gint64*
g_slice_get_config_state(GSliceConfig ckey,gint64 address,guint * n_values)351 g_slice_get_config_state (GSliceConfig ckey,
352 gint64 address,
353 guint *n_values)
354 {
355 guint i = 0;
356 g_return_val_if_fail (n_values != NULL, NULL);
357 *n_values = 0;
358 switch (ckey)
359 {
360 gint64 array[64];
361 case G_SLICE_CONFIG_CONTENTION_COUNTER:
362 array[i++] = SLAB_CHUNK_SIZE (allocator, address);
363 array[i++] = allocator->contention_counters[address];
364 array[i++] = allocator_get_magazine_threshold (allocator, address);
365 *n_values = i;
366 return g_memdup2 (array, sizeof (array[0]) * *n_values);
367 default:
368 return NULL;
369 }
370 }
371
372 static void
slice_config_init(SliceConfig * config)373 slice_config_init (SliceConfig *config)
374 {
375 const gchar *val;
376 gchar *val_allocated = NULL;
377
378 *config = slice_config;
379
380 /* Note that the empty string (`G_SLICE=""`) is treated differently from the
381 * envvar being unset. In the latter case, we also check whether running under
382 * valgrind. */
383 #ifndef G_OS_WIN32
384 val = g_getenv ("G_SLICE");
385 #else
386 /* The win32 implementation of g_getenv() has to do UTF-8 ↔ UTF-16 conversions
387 * which use the slice allocator, leading to deadlock. Use a simple in-place
388 * implementation here instead.
389 *
390 * Ignore references to other environment variables: only support values which
391 * are a combination of always-malloc and debug-blocks. */
392 {
393
394 wchar_t wvalue[128]; /* at least big enough for `always-malloc,debug-blocks` */
395 int len;
396
397 len = GetEnvironmentVariableW (L"G_SLICE", wvalue, G_N_ELEMENTS (wvalue));
398
399 if (len == 0)
400 {
401 if (GetLastError () == ERROR_ENVVAR_NOT_FOUND)
402 val = NULL;
403 else
404 val = "";
405 }
406 else if (len >= G_N_ELEMENTS (wvalue))
407 {
408 /* @wvalue isn’t big enough. Give up. */
409 g_warning ("Unsupported G_SLICE value");
410 val = NULL;
411 }
412 else
413 {
414 /* it’s safe to use g_utf16_to_utf8() here as it only allocates using
415 * malloc() rather than GSlice */
416 val = val_allocated = g_utf16_to_utf8 (wvalue, -1, NULL, NULL, NULL);
417 }
418
419 }
420 #endif /* G_OS_WIN32 */
421
422 if (val != NULL)
423 {
424 gint flags;
425 const GDebugKey keys[] = {
426 { "always-malloc", 1 << 0 },
427 { "debug-blocks", 1 << 1 },
428 };
429
430 flags = g_parse_debug_string (val, keys, G_N_ELEMENTS (keys));
431 if (flags & (1 << 0))
432 config->always_malloc = TRUE;
433 if (flags & (1 << 1))
434 config->debug_blocks = TRUE;
435 }
436 else
437 {
438 /* G_SLICE was not specified, so check if valgrind is running and
439 * disable ourselves if it is.
440 *
441 * This way it's possible to force gslice to be enabled under
442 * valgrind just by setting G_SLICE to the empty string.
443 */
444 #ifdef ENABLE_VALGRIND
445 if (RUNNING_ON_VALGRIND)
446 config->always_malloc = TRUE;
447 #endif
448 }
449
450 g_free (val_allocated);
451 }
452
453 static void
g_slice_init_nomessage(void)454 g_slice_init_nomessage (void)
455 {
456 /* we may not use g_error() or friends here */
457 mem_assert (sys_page_size == 0);
458 mem_assert (MIN_MAGAZINE_SIZE >= 4);
459
460 #ifdef G_OS_WIN32
461 {
462 SYSTEM_INFO system_info;
463 GetSystemInfo (&system_info);
464 sys_page_size = system_info.dwPageSize;
465 }
466 #else
467 sys_page_size = sysconf (_SC_PAGESIZE); /* = sysconf (_SC_PAGE_SIZE); = getpagesize(); */
468 #endif
469 mem_assert (sys_page_size >= 2 * LARGEALIGNMENT);
470 mem_assert ((sys_page_size & (sys_page_size - 1)) == 0);
471 slice_config_init (&allocator->config);
472 allocator->min_page_size = sys_page_size;
473 #if HAVE_POSIX_MEMALIGN || HAVE_MEMALIGN
474 /* allow allocation of pages up to 8KB (with 8KB alignment).
475 * this is useful because many medium to large sized structures
476 * fit less than 8 times (see [4]) into 4KB pages.
477 * we allow very small page sizes here, to reduce wastage in
478 * threads if only small allocations are required (this does
479 * bear the risk of increasing allocation times and fragmentation
480 * though).
481 */
482 allocator->min_page_size = MAX (allocator->min_page_size, 4096);
483 allocator->max_page_size = MAX (allocator->min_page_size, 8192);
484 allocator->min_page_size = MIN (allocator->min_page_size, 128);
485 #else
486 /* we can only align to system page size */
487 allocator->max_page_size = sys_page_size;
488 #endif
489 if (allocator->config.always_malloc)
490 {
491 allocator->contention_counters = NULL;
492 allocator->magazines = NULL;
493 allocator->slab_stack = NULL;
494 }
495 else
496 {
497 allocator->contention_counters = g_new0 (guint, MAX_SLAB_INDEX (allocator));
498 allocator->magazines = g_new0 (ChunkLink*, MAX_SLAB_INDEX (allocator));
499 allocator->slab_stack = g_new0 (SlabInfo*, MAX_SLAB_INDEX (allocator));
500 }
501
502 allocator->mutex_counter = 0;
503 allocator->stamp_counter = MAX_STAMP_COUNTER; /* force initial update */
504 allocator->last_stamp = 0;
505 allocator->color_accu = 0;
506 magazine_cache_update_stamp();
507 /* values cached for performance reasons */
508 allocator->max_slab_chunk_size_for_magazine_cache = MAX_SLAB_CHUNK_SIZE (allocator);
509 if (allocator->config.always_malloc || allocator->config.bypass_magazines)
510 allocator->max_slab_chunk_size_for_magazine_cache = 0; /* non-optimized cases */
511 }
512
513 static inline guint
allocator_categorize(gsize aligned_chunk_size)514 allocator_categorize (gsize aligned_chunk_size)
515 {
516 /* speed up the likely path */
517 if (G_LIKELY (aligned_chunk_size && aligned_chunk_size <= allocator->max_slab_chunk_size_for_magazine_cache))
518 return 1; /* use magazine cache */
519
520 if (!allocator->config.always_malloc &&
521 aligned_chunk_size &&
522 aligned_chunk_size <= MAX_SLAB_CHUNK_SIZE (allocator))
523 {
524 if (allocator->config.bypass_magazines)
525 return 2; /* use slab allocator, see [2] */
526 return 1; /* use magazine cache */
527 }
528 return 0; /* use malloc() */
529 }
530
531 static inline void
g_mutex_lock_a(GMutex * mutex,guint * contention_counter)532 g_mutex_lock_a (GMutex *mutex,
533 guint *contention_counter)
534 {
535 gboolean contention = FALSE;
536 if (!g_mutex_trylock (mutex))
537 {
538 g_mutex_lock (mutex);
539 contention = TRUE;
540 }
541 if (contention)
542 {
543 allocator->mutex_counter++;
544 if (allocator->mutex_counter >= 1) /* quickly adapt to contention */
545 {
546 allocator->mutex_counter = 0;
547 *contention_counter = MIN (*contention_counter + 1, MAX_MAGAZINE_SIZE);
548 }
549 }
550 else /* !contention */
551 {
552 allocator->mutex_counter--;
553 if (allocator->mutex_counter < -11) /* moderately recover magazine sizes */
554 {
555 allocator->mutex_counter = 0;
556 *contention_counter = MAX (*contention_counter, 1) - 1;
557 }
558 }
559 }
560
561 static inline ThreadMemory*
thread_memory_from_self(void)562 thread_memory_from_self (void)
563 {
564 ThreadMemory *tmem = g_private_get (&private_thread_memory);
565 if (G_UNLIKELY (!tmem))
566 {
567 static GMutex init_mutex;
568 guint n_magazines;
569
570 g_mutex_lock (&init_mutex);
571 if G_UNLIKELY (sys_page_size == 0)
572 g_slice_init_nomessage ();
573 g_mutex_unlock (&init_mutex);
574
575 n_magazines = MAX_SLAB_INDEX (allocator);
576 tmem = g_private_set_alloc0 (&private_thread_memory, sizeof (ThreadMemory) + sizeof (Magazine) * 2 * n_magazines);
577 tmem->magazine1 = (Magazine*) (tmem + 1);
578 tmem->magazine2 = &tmem->magazine1[n_magazines];
579 }
580 return tmem;
581 }
582
583 static inline ChunkLink*
magazine_chain_pop_head(ChunkLink ** magazine_chunks)584 magazine_chain_pop_head (ChunkLink **magazine_chunks)
585 {
586 /* magazine chains are linked via ChunkLink->next.
587 * each ChunkLink->data of the toplevel chain may point to a subchain,
588 * linked via ChunkLink->next. ChunkLink->data of the subchains just
589 * contains uninitialized junk.
590 */
591 ChunkLink *chunk = (*magazine_chunks)->data;
592 if (G_UNLIKELY (chunk))
593 {
594 /* allocating from freed list */
595 (*magazine_chunks)->data = chunk->next;
596 }
597 else
598 {
599 chunk = *magazine_chunks;
600 *magazine_chunks = chunk->next;
601 }
602 return chunk;
603 }
604
605 #if 0 /* useful for debugging */
606 static guint
607 magazine_count (ChunkLink *head)
608 {
609 guint count = 0;
610 if (!head)
611 return 0;
612 while (head)
613 {
614 ChunkLink *child = head->data;
615 count += 1;
616 for (child = head->data; child; child = child->next)
617 count += 1;
618 head = head->next;
619 }
620 return count;
621 }
622 #endif
623
624 static inline gsize
allocator_get_magazine_threshold(Allocator * allocator,guint ix)625 allocator_get_magazine_threshold (Allocator *allocator,
626 guint ix)
627 {
628 /* the magazine size calculated here has a lower bound of MIN_MAGAZINE_SIZE,
629 * which is required by the implementation. also, for moderately sized chunks
630 * (say >= 64 bytes), magazine sizes shouldn't be much smaller then the number
631 * of chunks available per page/2 to avoid excessive traffic in the magazine
632 * cache for small to medium sized structures.
633 * the upper bound of the magazine size is effectively provided by
634 * MAX_MAGAZINE_SIZE. for larger chunks, this number is scaled down so that
635 * the content of a single magazine doesn't exceed ca. 16KB.
636 */
637 gsize chunk_size = SLAB_CHUNK_SIZE (allocator, ix);
638 guint threshold = MAX (MIN_MAGAZINE_SIZE, allocator->max_page_size / MAX (5 * chunk_size, 5 * 32));
639 guint contention_counter = allocator->contention_counters[ix];
640 if (G_UNLIKELY (contention_counter)) /* single CPU bias */
641 {
642 /* adapt contention counter thresholds to chunk sizes */
643 contention_counter = contention_counter * 64 / chunk_size;
644 threshold = MAX (threshold, contention_counter);
645 }
646 return threshold;
647 }
648
649 /* --- magazine cache --- */
650 static inline void
magazine_cache_update_stamp(void)651 magazine_cache_update_stamp (void)
652 {
653 if (allocator->stamp_counter >= MAX_STAMP_COUNTER)
654 {
655 gint64 now_us = g_get_real_time ();
656 allocator->last_stamp = now_us / 1000; /* milli seconds */
657 allocator->stamp_counter = 0;
658 }
659 else
660 allocator->stamp_counter++;
661 }
662
663 static inline ChunkLink*
magazine_chain_prepare_fields(ChunkLink * magazine_chunks)664 magazine_chain_prepare_fields (ChunkLink *magazine_chunks)
665 {
666 ChunkLink *chunk1;
667 ChunkLink *chunk2;
668 ChunkLink *chunk3;
669 ChunkLink *chunk4;
670 /* checked upon initialization: mem_assert (MIN_MAGAZINE_SIZE >= 4); */
671 /* ensure a magazine with at least 4 unused data pointers */
672 chunk1 = magazine_chain_pop_head (&magazine_chunks);
673 chunk2 = magazine_chain_pop_head (&magazine_chunks);
674 chunk3 = magazine_chain_pop_head (&magazine_chunks);
675 chunk4 = magazine_chain_pop_head (&magazine_chunks);
676 chunk4->next = magazine_chunks;
677 chunk3->next = chunk4;
678 chunk2->next = chunk3;
679 chunk1->next = chunk2;
680 return chunk1;
681 }
682
683 /* access the first 3 fields of a specially prepared magazine chain */
684 #define magazine_chain_prev(mc) ((mc)->data)
685 #define magazine_chain_stamp(mc) ((mc)->next->data)
686 #define magazine_chain_uint_stamp(mc) GPOINTER_TO_UINT ((mc)->next->data)
687 #define magazine_chain_next(mc) ((mc)->next->next->data)
688 #define magazine_chain_count(mc) ((mc)->next->next->next->data)
689
690 #ifdef OHOS_OPT_PERFORMANCE
691 /*
692 * ohos.opt.performance.0004
693 * fix glib cache too large problem. when thread exit, release mem no user.
694 */
695 static void
magazine_cache_trim(Allocator * allocator,guint ix,guint stamp,gboolean release)696 magazine_cache_trim (Allocator *allocator,
697 guint ix,
698 guint stamp,
699 gboolean release)
700 {
701 /* g_mutex_lock (allocator->mutex); done by caller */
702 /* trim magazine cache from tail */
703 ChunkLink *current = magazine_chain_prev (allocator->magazines[ix]);
704 ChunkLink *trash = NULL;
705 while (!G_APPROX_VALUE(stamp, magazine_chain_uint_stamp (current),
706 allocator->config.working_set_msecs) || release)
707 {
708 /* unlink */
709 ChunkLink *prev = magazine_chain_prev (current);
710 ChunkLink *next = magazine_chain_next (current);
711 magazine_chain_next (prev) = next;
712 magazine_chain_prev (next) = prev;
713 /* clear special fields, put on trash stack */
714 magazine_chain_next (current) = NULL;
715 magazine_chain_count (current) = NULL;
716 magazine_chain_stamp (current) = NULL;
717 magazine_chain_prev (current) = trash;
718 trash = current;
719 /* fixup list head if required */
720 if (current == allocator->magazines[ix])
721 {
722 allocator->magazines[ix] = NULL;
723 break;
724 }
725 current = prev;
726 }
727 g_mutex_unlock (&allocator->magazine_mutex);
728 /* free trash */
729 if (trash)
730 {
731 const gsize chunk_size = SLAB_CHUNK_SIZE (allocator, ix);
732 g_mutex_lock (&allocator->slab_mutex);
733 while (trash)
734 {
735 current = trash;
736 trash = magazine_chain_prev (current);
737 magazine_chain_prev (current) = NULL; /* clear special field */
738 while (current)
739 {
740 ChunkLink *chunk = magazine_chain_pop_head (¤t);
741 slab_allocator_free_chunk (chunk_size, chunk);
742 }
743 }
744 g_mutex_unlock (&allocator->slab_mutex);
745 }
746 }
747 #else
748 static void
magazine_cache_trim(Allocator * allocator,guint ix,guint stamp)749 magazine_cache_trim (Allocator *allocator,
750 guint ix,
751 guint stamp)
752 {
753 /* g_mutex_lock (allocator->mutex); done by caller */
754 /* trim magazine cache from tail */
755 ChunkLink *current = magazine_chain_prev (allocator->magazines[ix]);
756 ChunkLink *trash = NULL;
757 while (!G_APPROX_VALUE(stamp, magazine_chain_uint_stamp (current),
758 allocator->config.working_set_msecs))
759 {
760 /* unlink */
761 ChunkLink *prev = magazine_chain_prev (current);
762 ChunkLink *next = magazine_chain_next (current);
763 magazine_chain_next (prev) = next;
764 magazine_chain_prev (next) = prev;
765 /* clear special fields, put on trash stack */
766 magazine_chain_next (current) = NULL;
767 magazine_chain_count (current) = NULL;
768 magazine_chain_stamp (current) = NULL;
769 magazine_chain_prev (current) = trash;
770 trash = current;
771 /* fixup list head if required */
772 if (current == allocator->magazines[ix])
773 {
774 allocator->magazines[ix] = NULL;
775 break;
776 }
777 current = prev;
778 }
779 g_mutex_unlock (&allocator->magazine_mutex);
780 /* free trash */
781 if (trash)
782 {
783 const gsize chunk_size = SLAB_CHUNK_SIZE (allocator, ix);
784 g_mutex_lock (&allocator->slab_mutex);
785 while (trash)
786 {
787 current = trash;
788 trash = magazine_chain_prev (current);
789 magazine_chain_prev (current) = NULL; /* clear special field */
790 while (current)
791 {
792 ChunkLink *chunk = magazine_chain_pop_head (¤t);
793 slab_allocator_free_chunk (chunk_size, chunk);
794 }
795 }
796 g_mutex_unlock (&allocator->slab_mutex);
797 }
798 }
799 #endif
800
801 #ifdef OHOS_OPT_PERFORMANCE
802 /*
803 * ohos.opt.performance.0004
804 * fix glib cache too large problem. when thread exit, release mem no user.
805 */
806 static void
magazine_cache_push_magazine(guint ix,ChunkLink * magazine_chunks,gsize count,gboolean release)807 magazine_cache_push_magazine (guint ix,
808 ChunkLink *magazine_chunks,
809 gsize count,
810 gboolean release) /* must be >= MIN_MAGAZINE_SIZE */
811 {
812 ChunkLink *current = magazine_chain_prepare_fields (magazine_chunks);
813 ChunkLink *next, *prev;
814 g_mutex_lock (&allocator->magazine_mutex);
815 /* add magazine at head */
816 next = allocator->magazines[ix];
817 if (next)
818 prev = magazine_chain_prev (next);
819 else
820 next = prev = current;
821 magazine_chain_next (prev) = current;
822 magazine_chain_prev (next) = current;
823 magazine_chain_prev (current) = prev;
824 magazine_chain_next (current) = next;
825 magazine_chain_count (current) = (gpointer) count;
826 /* stamp magazine */
827 magazine_cache_update_stamp();
828 magazine_chain_stamp (current) = GUINT_TO_POINTER (allocator->last_stamp);
829 allocator->magazines[ix] = current;
830 /* free old magazines beyond a certain threshold */
831 magazine_cache_trim (allocator, ix, allocator->last_stamp, release);
832 /* g_mutex_unlock (allocator->mutex); was done by magazine_cache_trim() */
833 }
834 #else
835 static void
magazine_cache_push_magazine(guint ix,ChunkLink * magazine_chunks,gsize count)836 magazine_cache_push_magazine (guint ix,
837 ChunkLink *magazine_chunks,
838 gsize count) /* must be >= MIN_MAGAZINE_SIZE */
839 {
840 ChunkLink *current = magazine_chain_prepare_fields (magazine_chunks);
841 ChunkLink *next, *prev;
842 g_mutex_lock (&allocator->magazine_mutex);
843 /* add magazine at head */
844 next = allocator->magazines[ix];
845 if (next)
846 prev = magazine_chain_prev (next);
847 else
848 next = prev = current;
849 magazine_chain_next (prev) = current;
850 magazine_chain_prev (next) = current;
851 magazine_chain_prev (current) = prev;
852 magazine_chain_next (current) = next;
853 magazine_chain_count (current) = (gpointer) count;
854 /* stamp magazine */
855 magazine_cache_update_stamp();
856 magazine_chain_stamp (current) = GUINT_TO_POINTER (allocator->last_stamp);
857 allocator->magazines[ix] = current;
858 /* free old magazines beyond a certain threshold */
859 magazine_cache_trim (allocator, ix, allocator->last_stamp);
860 /* g_mutex_unlock (allocator->mutex); was done by magazine_cache_trim() */
861 }
862 #endif
863 static ChunkLink*
magazine_cache_pop_magazine(guint ix,gsize * countp)864 magazine_cache_pop_magazine (guint ix,
865 gsize *countp)
866 {
867 g_mutex_lock_a (&allocator->magazine_mutex, &allocator->contention_counters[ix]);
868 if (!allocator->magazines[ix])
869 {
870 guint magazine_threshold = allocator_get_magazine_threshold (allocator, ix);
871 gsize i, chunk_size = SLAB_CHUNK_SIZE (allocator, ix);
872 ChunkLink *chunk, *head;
873 g_mutex_unlock (&allocator->magazine_mutex);
874 g_mutex_lock (&allocator->slab_mutex);
875 head = slab_allocator_alloc_chunk (chunk_size);
876 head->data = NULL;
877 chunk = head;
878 for (i = 1; i < magazine_threshold; i++)
879 {
880 chunk->next = slab_allocator_alloc_chunk (chunk_size);
881 chunk = chunk->next;
882 chunk->data = NULL;
883 }
884 chunk->next = NULL;
885 g_mutex_unlock (&allocator->slab_mutex);
886 *countp = i;
887 return head;
888 }
889 else
890 {
891 ChunkLink *current = allocator->magazines[ix];
892 ChunkLink *prev = magazine_chain_prev (current);
893 ChunkLink *next = magazine_chain_next (current);
894 /* unlink */
895 magazine_chain_next (prev) = next;
896 magazine_chain_prev (next) = prev;
897 allocator->magazines[ix] = next == current ? NULL : next;
898 g_mutex_unlock (&allocator->magazine_mutex);
899 /* clear special fields and hand out */
900 *countp = (gsize) magazine_chain_count (current);
901 magazine_chain_prev (current) = NULL;
902 magazine_chain_next (current) = NULL;
903 magazine_chain_count (current) = NULL;
904 magazine_chain_stamp (current) = NULL;
905 return current;
906 }
907 }
908
909 /* --- thread magazines --- */
910 static void
private_thread_memory_cleanup(gpointer data)911 private_thread_memory_cleanup (gpointer data)
912 {
913 ThreadMemory *tmem = data;
914 const guint n_magazines = MAX_SLAB_INDEX (allocator);
915 guint ix;
916 for (ix = 0; ix < n_magazines; ix++)
917 {
918 Magazine *mags[2];
919 guint j;
920 mags[0] = &tmem->magazine1[ix];
921 mags[1] = &tmem->magazine2[ix];
922 for (j = 0; j < 2; j++)
923 {
924 Magazine *mag = mags[j];
925 if (mag->count >= MIN_MAGAZINE_SIZE)
926 #ifdef OHOS_OPT_PERFORMANCE
927 /*
928 * ohos.opt.performance.0004
929 * fix glib cache too large problem. when thread exit, release mem no user.
930 */
931 magazine_cache_push_magazine (ix, mag->chunks, mag->count, TRUE);
932 #else
933 magazine_cache_push_magazine (ix, mag->chunks, mag->count);
934 #endif
935 else
936 {
937 const gsize chunk_size = SLAB_CHUNK_SIZE (allocator, ix);
938 g_mutex_lock (&allocator->slab_mutex);
939 while (mag->chunks)
940 {
941 ChunkLink *chunk = magazine_chain_pop_head (&mag->chunks);
942 slab_allocator_free_chunk (chunk_size, chunk);
943 }
944 g_mutex_unlock (&allocator->slab_mutex);
945 }
946 }
947 }
948 g_free (tmem);
949 }
950
951 static void
thread_memory_magazine1_reload(ThreadMemory * tmem,guint ix)952 thread_memory_magazine1_reload (ThreadMemory *tmem,
953 guint ix)
954 {
955 Magazine *mag = &tmem->magazine1[ix];
956 mem_assert (mag->chunks == NULL); /* ensure that we may reset mag->count */
957 mag->count = 0;
958 mag->chunks = magazine_cache_pop_magazine (ix, &mag->count);
959 }
960
961 static void
thread_memory_magazine2_unload(ThreadMemory * tmem,guint ix)962 thread_memory_magazine2_unload (ThreadMemory *tmem,
963 guint ix)
964 {
965 Magazine *mag = &tmem->magazine2[ix];
966 #ifdef OHOS_OPT_PERFORMANCE
967 /*
968 * ohos.opt.performance.0004
969 * fix glib cache too large problem. when thread exit, release mem no user.
970 */
971 magazine_cache_push_magazine (ix, mag->chunks, mag->count, FALSE);
972 #else
973 magazine_cache_push_magazine (ix, mag->chunks, mag->count);
974 #endif
975 mag->chunks = NULL;
976 mag->count = 0;
977 }
978
979 static inline void
thread_memory_swap_magazines(ThreadMemory * tmem,guint ix)980 thread_memory_swap_magazines (ThreadMemory *tmem,
981 guint ix)
982 {
983 Magazine xmag = tmem->magazine1[ix];
984 tmem->magazine1[ix] = tmem->magazine2[ix];
985 tmem->magazine2[ix] = xmag;
986 }
987
988 static inline gboolean
thread_memory_magazine1_is_empty(ThreadMemory * tmem,guint ix)989 thread_memory_magazine1_is_empty (ThreadMemory *tmem,
990 guint ix)
991 {
992 return tmem->magazine1[ix].chunks == NULL;
993 }
994
995 static inline gboolean
thread_memory_magazine2_is_full(ThreadMemory * tmem,guint ix)996 thread_memory_magazine2_is_full (ThreadMemory *tmem,
997 guint ix)
998 {
999 return tmem->magazine2[ix].count >= allocator_get_magazine_threshold (allocator, ix);
1000 }
1001
1002 static inline gpointer
thread_memory_magazine1_alloc(ThreadMemory * tmem,guint ix)1003 thread_memory_magazine1_alloc (ThreadMemory *tmem,
1004 guint ix)
1005 {
1006 Magazine *mag = &tmem->magazine1[ix];
1007 ChunkLink *chunk = magazine_chain_pop_head (&mag->chunks);
1008 if (G_LIKELY (mag->count > 0))
1009 mag->count--;
1010 return chunk;
1011 }
1012
1013 static inline void
thread_memory_magazine2_free(ThreadMemory * tmem,guint ix,gpointer mem)1014 thread_memory_magazine2_free (ThreadMemory *tmem,
1015 guint ix,
1016 gpointer mem)
1017 {
1018 Magazine *mag = &tmem->magazine2[ix];
1019 ChunkLink *chunk = mem;
1020 chunk->data = NULL;
1021 chunk->next = mag->chunks;
1022 mag->chunks = chunk;
1023 mag->count++;
1024 }
1025
1026 /* --- API functions --- */
1027
1028 /**
1029 * g_slice_new:
1030 * @type: the type to allocate, typically a structure name
1031 *
1032 * A convenience macro to allocate a block of memory from the
1033 * slice allocator.
1034 *
1035 * It calls g_slice_alloc() with `sizeof (@type)` and casts the
1036 * returned pointer to a pointer of the given type, avoiding a type
1037 * cast in the source code. Note that the underlying slice allocation
1038 * mechanism can be changed with the [`G_SLICE=always-malloc`][G_SLICE]
1039 * environment variable.
1040 *
1041 * This can never return %NULL as the minimum allocation size from
1042 * `sizeof (@type)` is 1 byte.
1043 *
1044 * Returns: (not nullable): a pointer to the allocated block, cast to a pointer
1045 * to @type
1046 *
1047 * Since: 2.10
1048 */
1049
1050 /**
1051 * g_slice_new0:
1052 * @type: the type to allocate, typically a structure name
1053 *
1054 * A convenience macro to allocate a block of memory from the
1055 * slice allocator and set the memory to 0.
1056 *
1057 * It calls g_slice_alloc0() with `sizeof (@type)`
1058 * and casts the returned pointer to a pointer of the given type,
1059 * avoiding a type cast in the source code.
1060 * Note that the underlying slice allocation mechanism can
1061 * be changed with the [`G_SLICE=always-malloc`][G_SLICE]
1062 * environment variable.
1063 *
1064 * This can never return %NULL as the minimum allocation size from
1065 * `sizeof (@type)` is 1 byte.
1066 *
1067 * Returns: (not nullable): a pointer to the allocated block, cast to a pointer
1068 * to @type
1069 *
1070 * Since: 2.10
1071 */
1072
1073 /**
1074 * g_slice_dup:
1075 * @type: the type to duplicate, typically a structure name
1076 * @mem: (not nullable): the memory to copy into the allocated block
1077 *
1078 * A convenience macro to duplicate a block of memory using
1079 * the slice allocator.
1080 *
1081 * It calls g_slice_copy() with `sizeof (@type)`
1082 * and casts the returned pointer to a pointer of the given type,
1083 * avoiding a type cast in the source code.
1084 * Note that the underlying slice allocation mechanism can
1085 * be changed with the [`G_SLICE=always-malloc`][G_SLICE]
1086 * environment variable.
1087 *
1088 * This can never return %NULL.
1089 *
1090 * Returns: (not nullable): a pointer to the allocated block, cast to a pointer
1091 * to @type
1092 *
1093 * Since: 2.14
1094 */
1095
1096 /**
1097 * g_slice_free:
1098 * @type: the type of the block to free, typically a structure name
1099 * @mem: a pointer to the block to free
1100 *
1101 * A convenience macro to free a block of memory that has
1102 * been allocated from the slice allocator.
1103 *
1104 * It calls g_slice_free1() using `sizeof (type)`
1105 * as the block size.
1106 * Note that the exact release behaviour can be changed with the
1107 * [`G_DEBUG=gc-friendly`][G_DEBUG] environment variable, also see
1108 * [`G_SLICE`][G_SLICE] for related debugging options.
1109 *
1110 * If @mem is %NULL, this macro does nothing.
1111 *
1112 * Since: 2.10
1113 */
1114
1115 /**
1116 * g_slice_free_chain:
1117 * @type: the type of the @mem_chain blocks
1118 * @mem_chain: a pointer to the first block of the chain
1119 * @next: the field name of the next pointer in @type
1120 *
1121 * Frees a linked list of memory blocks of structure type @type.
1122 * The memory blocks must be equal-sized, allocated via
1123 * g_slice_alloc() or g_slice_alloc0() and linked together by
1124 * a @next pointer (similar to #GSList). The name of the
1125 * @next field in @type is passed as third argument.
1126 * Note that the exact release behaviour can be changed with the
1127 * [`G_DEBUG=gc-friendly`][G_DEBUG] environment variable, also see
1128 * [`G_SLICE`][G_SLICE] for related debugging options.
1129 *
1130 * If @mem_chain is %NULL, this function does nothing.
1131 *
1132 * Since: 2.10
1133 */
1134
1135 /**
1136 * g_slice_alloc:
1137 * @block_size: the number of bytes to allocate
1138 *
1139 * Allocates a block of memory from the slice allocator.
1140 * The block address handed out can be expected to be aligned
1141 * to at least 1 * sizeof (void*),
1142 * though in general slices are 2 * sizeof (void*) bytes aligned,
1143 * if a malloc() fallback implementation is used instead,
1144 * the alignment may be reduced in a libc dependent fashion.
1145 * Note that the underlying slice allocation mechanism can
1146 * be changed with the [`G_SLICE=always-malloc`][G_SLICE]
1147 * environment variable.
1148 *
1149 * Returns: a pointer to the allocated memory block, which will be %NULL if and
1150 * only if @mem_size is 0
1151 *
1152 * Since: 2.10
1153 */
1154 gpointer
g_slice_alloc(gsize mem_size)1155 g_slice_alloc (gsize mem_size)
1156 {
1157 ThreadMemory *tmem;
1158 gsize chunk_size;
1159 gpointer mem;
1160 guint acat;
1161
1162 /* This gets the private structure for this thread. If the private
1163 * structure does not yet exist, it is created.
1164 *
1165 * This has a side effect of causing GSlice to be initialised, so it
1166 * must come first.
1167 */
1168 tmem = thread_memory_from_self ();
1169
1170 chunk_size = P2ALIGN (mem_size);
1171 acat = allocator_categorize (chunk_size);
1172 if (G_LIKELY (acat == 1)) /* allocate through magazine layer */
1173 {
1174 guint ix = SLAB_INDEX (allocator, chunk_size);
1175 if (G_UNLIKELY (thread_memory_magazine1_is_empty (tmem, ix)))
1176 {
1177 thread_memory_swap_magazines (tmem, ix);
1178 if (G_UNLIKELY (thread_memory_magazine1_is_empty (tmem, ix)))
1179 thread_memory_magazine1_reload (tmem, ix);
1180 }
1181 mem = thread_memory_magazine1_alloc (tmem, ix);
1182 }
1183 else if (acat == 2) /* allocate through slab allocator */
1184 {
1185 g_mutex_lock (&allocator->slab_mutex);
1186 mem = slab_allocator_alloc_chunk (chunk_size);
1187 g_mutex_unlock (&allocator->slab_mutex);
1188 }
1189 else /* delegate to system malloc */
1190 mem = g_malloc (mem_size);
1191 if (G_UNLIKELY (allocator->config.debug_blocks))
1192 smc_notify_alloc (mem, mem_size);
1193
1194 TRACE (GLIB_SLICE_ALLOC((void*)mem, mem_size));
1195 DFX_TRACE(GMemAllocDfx((void *)mem, (unsigned int)mem_size));
1196 return mem;
1197 }
1198
1199 /**
1200 * g_slice_alloc0:
1201 * @block_size: the number of bytes to allocate
1202 *
1203 * Allocates a block of memory via g_slice_alloc() and initializes
1204 * the returned memory to 0. Note that the underlying slice allocation
1205 * mechanism can be changed with the [`G_SLICE=always-malloc`][G_SLICE]
1206 * environment variable.
1207 *
1208 * Returns: a pointer to the allocated block, which will be %NULL if and only
1209 * if @mem_size is 0
1210 *
1211 * Since: 2.10
1212 */
1213 gpointer
g_slice_alloc0(gsize mem_size)1214 g_slice_alloc0 (gsize mem_size)
1215 {
1216 gpointer mem = g_slice_alloc (mem_size);
1217 if (mem)
1218 memset (mem, 0, mem_size);
1219 return mem;
1220 }
1221
1222 /**
1223 * g_slice_copy:
1224 * @block_size: the number of bytes to allocate
1225 * @mem_block: the memory to copy
1226 *
1227 * Allocates a block of memory from the slice allocator
1228 * and copies @block_size bytes into it from @mem_block.
1229 *
1230 * @mem_block must be non-%NULL if @block_size is non-zero.
1231 *
1232 * Returns: a pointer to the allocated memory block, which will be %NULL if and
1233 * only if @mem_size is 0
1234 *
1235 * Since: 2.14
1236 */
1237 gpointer
g_slice_copy(gsize mem_size,gconstpointer mem_block)1238 g_slice_copy (gsize mem_size,
1239 gconstpointer mem_block)
1240 {
1241 gpointer mem = g_slice_alloc (mem_size);
1242 if (mem)
1243 memcpy (mem, mem_block, mem_size);
1244 return mem;
1245 }
1246
1247 /**
1248 * g_slice_free1:
1249 * @block_size: the size of the block
1250 * @mem_block: a pointer to the block to free
1251 *
1252 * Frees a block of memory.
1253 *
1254 * The memory must have been allocated via g_slice_alloc() or
1255 * g_slice_alloc0() and the @block_size has to match the size
1256 * specified upon allocation. Note that the exact release behaviour
1257 * can be changed with the [`G_DEBUG=gc-friendly`][G_DEBUG] environment
1258 * variable, also see [`G_SLICE`][G_SLICE] for related debugging options.
1259 *
1260 * If @mem_block is %NULL, this function does nothing.
1261 *
1262 * Since: 2.10
1263 */
1264 void
g_slice_free1(gsize mem_size,gpointer mem_block)1265 g_slice_free1 (gsize mem_size,
1266 gpointer mem_block)
1267 {
1268 gsize chunk_size = P2ALIGN (mem_size);
1269 guint acat = allocator_categorize (chunk_size);
1270 if (G_UNLIKELY (!mem_block))
1271 return;
1272 if (G_UNLIKELY (allocator->config.debug_blocks) &&
1273 !smc_notify_free (mem_block, mem_size))
1274 abort();
1275 if (G_LIKELY (acat == 1)) /* allocate through magazine layer */
1276 {
1277 ThreadMemory *tmem = thread_memory_from_self();
1278 guint ix = SLAB_INDEX (allocator, chunk_size);
1279 if (G_UNLIKELY (thread_memory_magazine2_is_full (tmem, ix)))
1280 {
1281 thread_memory_swap_magazines (tmem, ix);
1282 if (G_UNLIKELY (thread_memory_magazine2_is_full (tmem, ix)))
1283 thread_memory_magazine2_unload (tmem, ix);
1284 }
1285 if (G_UNLIKELY (g_mem_gc_friendly))
1286 memset (mem_block, 0, chunk_size);
1287 thread_memory_magazine2_free (tmem, ix, mem_block);
1288 }
1289 else if (acat == 2) /* allocate through slab allocator */
1290 {
1291 if (G_UNLIKELY (g_mem_gc_friendly))
1292 memset (mem_block, 0, chunk_size);
1293 g_mutex_lock (&allocator->slab_mutex);
1294 slab_allocator_free_chunk (chunk_size, mem_block);
1295 g_mutex_unlock (&allocator->slab_mutex);
1296 }
1297 else /* delegate to system malloc */
1298 {
1299 if (G_UNLIKELY (g_mem_gc_friendly))
1300 memset (mem_block, 0, mem_size);
1301 g_free (mem_block);
1302 }
1303 TRACE (GLIB_SLICE_FREE((void*)mem_block, mem_size));
1304 DFX_TRACE(GMemFreeDfx((void *)mem_block));
1305 }
1306
1307 /**
1308 * g_slice_free_chain_with_offset:
1309 * @block_size: the size of the blocks
1310 * @mem_chain: a pointer to the first block of the chain
1311 * @next_offset: the offset of the @next field in the blocks
1312 *
1313 * Frees a linked list of memory blocks of structure type @type.
1314 *
1315 * The memory blocks must be equal-sized, allocated via
1316 * g_slice_alloc() or g_slice_alloc0() and linked together by a
1317 * @next pointer (similar to #GSList). The offset of the @next
1318 * field in each block is passed as third argument.
1319 * Note that the exact release behaviour can be changed with the
1320 * [`G_DEBUG=gc-friendly`][G_DEBUG] environment variable, also see
1321 * [`G_SLICE`][G_SLICE] for related debugging options.
1322 *
1323 * If @mem_chain is %NULL, this function does nothing.
1324 *
1325 * Since: 2.10
1326 */
1327 void
g_slice_free_chain_with_offset(gsize mem_size,gpointer mem_chain,gsize next_offset)1328 g_slice_free_chain_with_offset (gsize mem_size,
1329 gpointer mem_chain,
1330 gsize next_offset)
1331 {
1332 DFX_TRACE(GChainMemFreeDfx((void *)mem_chain, next_offset));
1333 gpointer slice = mem_chain;
1334 /* while the thread magazines and the magazine cache are implemented so that
1335 * they can easily be extended to allow for free lists containing more free
1336 * lists for the first level nodes, which would allow O(1) freeing in this
1337 * function, the benefit of such an extension is questionable, because:
1338 * - the magazine size counts will become mere lower bounds which confuses
1339 * the code adapting to lock contention;
1340 * - freeing a single node to the thread magazines is very fast, so this
1341 * O(list_length) operation is multiplied by a fairly small factor;
1342 * - memory usage histograms on larger applications seem to indicate that
1343 * the amount of released multi node lists is negligible in comparison
1344 * to single node releases.
1345 * - the major performance bottle neck, namely g_private_get() or
1346 * g_mutex_lock()/g_mutex_unlock() has already been moved out of the
1347 * inner loop for freeing chained slices.
1348 */
1349 gsize chunk_size = P2ALIGN (mem_size);
1350 guint acat = allocator_categorize (chunk_size);
1351 if (G_LIKELY (acat == 1)) /* allocate through magazine layer */
1352 {
1353 ThreadMemory *tmem = thread_memory_from_self();
1354 guint ix = SLAB_INDEX (allocator, chunk_size);
1355 while (slice)
1356 {
1357 guint8 *current = slice;
1358 slice = *(gpointer*) (current + next_offset);
1359 if (G_UNLIKELY (allocator->config.debug_blocks) &&
1360 !smc_notify_free (current, mem_size))
1361 abort();
1362 if (G_UNLIKELY (thread_memory_magazine2_is_full (tmem, ix)))
1363 {
1364 thread_memory_swap_magazines (tmem, ix);
1365 if (G_UNLIKELY (thread_memory_magazine2_is_full (tmem, ix)))
1366 thread_memory_magazine2_unload (tmem, ix);
1367 }
1368 if (G_UNLIKELY (g_mem_gc_friendly))
1369 memset (current, 0, chunk_size);
1370 thread_memory_magazine2_free (tmem, ix, current);
1371 }
1372 }
1373 else if (acat == 2) /* allocate through slab allocator */
1374 {
1375 g_mutex_lock (&allocator->slab_mutex);
1376 while (slice)
1377 {
1378 guint8 *current = slice;
1379 slice = *(gpointer*) (current + next_offset);
1380 if (G_UNLIKELY (allocator->config.debug_blocks) &&
1381 !smc_notify_free (current, mem_size))
1382 abort();
1383 if (G_UNLIKELY (g_mem_gc_friendly))
1384 memset (current, 0, chunk_size);
1385 slab_allocator_free_chunk (chunk_size, current);
1386 }
1387 g_mutex_unlock (&allocator->slab_mutex);
1388 }
1389 else /* delegate to system malloc */
1390 while (slice)
1391 {
1392 guint8 *current = slice;
1393 slice = *(gpointer*) (current + next_offset);
1394 if (G_UNLIKELY (allocator->config.debug_blocks) &&
1395 !smc_notify_free (current, mem_size))
1396 abort();
1397 if (G_UNLIKELY (g_mem_gc_friendly))
1398 memset (current, 0, mem_size);
1399 g_free (current);
1400 }
1401 }
1402
1403 /* --- single page allocator --- */
1404 static void
allocator_slab_stack_push(Allocator * allocator,guint ix,SlabInfo * sinfo)1405 allocator_slab_stack_push (Allocator *allocator,
1406 guint ix,
1407 SlabInfo *sinfo)
1408 {
1409 /* insert slab at slab ring head */
1410 if (!allocator->slab_stack[ix])
1411 {
1412 sinfo->next = sinfo;
1413 sinfo->prev = sinfo;
1414 }
1415 else
1416 {
1417 SlabInfo *next = allocator->slab_stack[ix], *prev = next->prev;
1418 next->prev = sinfo;
1419 prev->next = sinfo;
1420 sinfo->next = next;
1421 sinfo->prev = prev;
1422 }
1423 allocator->slab_stack[ix] = sinfo;
1424 }
1425
1426 static gsize
allocator_aligned_page_size(Allocator * allocator,gsize n_bytes)1427 allocator_aligned_page_size (Allocator *allocator,
1428 gsize n_bytes)
1429 {
1430 gsize val = 1 << g_bit_storage (n_bytes - 1);
1431 val = MAX (val, allocator->min_page_size);
1432 return val;
1433 }
1434
1435 static void
allocator_add_slab(Allocator * allocator,guint ix,gsize chunk_size)1436 allocator_add_slab (Allocator *allocator,
1437 guint ix,
1438 gsize chunk_size)
1439 {
1440 ChunkLink *chunk;
1441 SlabInfo *sinfo;
1442 gsize addr, padding, n_chunks, color = 0;
1443 gsize page_size;
1444 int errsv;
1445 gpointer aligned_memory;
1446 guint8 *mem;
1447 guint i;
1448
1449 page_size = allocator_aligned_page_size (allocator, SLAB_BPAGE_SIZE (allocator, chunk_size));
1450 /* allocate 1 page for the chunks and the slab */
1451 aligned_memory = allocator_memalign (page_size, page_size - NATIVE_MALLOC_PADDING);
1452 errsv = errno;
1453 mem = aligned_memory;
1454
1455 if (!mem)
1456 {
1457 const gchar *syserr = strerror (errsv);
1458 mem_error ("failed to allocate %u bytes (alignment: %u): %s\n",
1459 (guint) (page_size - NATIVE_MALLOC_PADDING), (guint) page_size, syserr);
1460 }
1461 /* mask page address */
1462 addr = ((gsize) mem / page_size) * page_size;
1463 /* assert alignment */
1464 mem_assert (aligned_memory == (gpointer) addr);
1465 /* basic slab info setup */
1466 sinfo = (SlabInfo*) (mem + page_size - SLAB_INFO_SIZE);
1467 sinfo->n_allocated = 0;
1468 sinfo->chunks = NULL;
1469 /* figure cache colorization */
1470 n_chunks = ((guint8*) sinfo - mem) / chunk_size;
1471 padding = ((guint8*) sinfo - mem) - n_chunks * chunk_size;
1472 if (padding)
1473 {
1474 color = (allocator->color_accu * P2ALIGNMENT) % padding;
1475 allocator->color_accu += allocator->config.color_increment;
1476 }
1477 /* add chunks to free list */
1478 chunk = (ChunkLink*) (mem + color);
1479 sinfo->chunks = chunk;
1480 for (i = 0; i < n_chunks - 1; i++)
1481 {
1482 chunk->next = (ChunkLink*) ((guint8*) chunk + chunk_size);
1483 chunk = chunk->next;
1484 }
1485 chunk->next = NULL; /* last chunk */
1486 /* add slab to slab ring */
1487 allocator_slab_stack_push (allocator, ix, sinfo);
1488 }
1489
1490 static gpointer
slab_allocator_alloc_chunk(gsize chunk_size)1491 slab_allocator_alloc_chunk (gsize chunk_size)
1492 {
1493 ChunkLink *chunk;
1494 guint ix = SLAB_INDEX (allocator, chunk_size);
1495 /* ensure non-empty slab */
1496 if (!allocator->slab_stack[ix] || !allocator->slab_stack[ix]->chunks)
1497 allocator_add_slab (allocator, ix, chunk_size);
1498 /* allocate chunk */
1499 chunk = allocator->slab_stack[ix]->chunks;
1500 allocator->slab_stack[ix]->chunks = chunk->next;
1501 allocator->slab_stack[ix]->n_allocated++;
1502 /* rotate empty slabs */
1503 if (!allocator->slab_stack[ix]->chunks)
1504 allocator->slab_stack[ix] = allocator->slab_stack[ix]->next;
1505 return chunk;
1506 }
1507
1508 static void
slab_allocator_free_chunk(gsize chunk_size,gpointer mem)1509 slab_allocator_free_chunk (gsize chunk_size,
1510 gpointer mem)
1511 {
1512 ChunkLink *chunk;
1513 gboolean was_empty;
1514 guint ix = SLAB_INDEX (allocator, chunk_size);
1515 gsize page_size = allocator_aligned_page_size (allocator, SLAB_BPAGE_SIZE (allocator, chunk_size));
1516 gsize addr = ((gsize) mem / page_size) * page_size;
1517 /* mask page address */
1518 guint8 *page = (guint8*) addr;
1519 SlabInfo *sinfo = (SlabInfo*) (page + page_size - SLAB_INFO_SIZE);
1520 /* assert valid chunk count */
1521 mem_assert (sinfo->n_allocated > 0);
1522 /* add chunk to free list */
1523 was_empty = sinfo->chunks == NULL;
1524 chunk = (ChunkLink*) mem;
1525 chunk->next = sinfo->chunks;
1526 sinfo->chunks = chunk;
1527 sinfo->n_allocated--;
1528 /* keep slab ring partially sorted, empty slabs at end */
1529 if (was_empty)
1530 {
1531 /* unlink slab */
1532 SlabInfo *next = sinfo->next, *prev = sinfo->prev;
1533 next->prev = prev;
1534 prev->next = next;
1535 if (allocator->slab_stack[ix] == sinfo)
1536 allocator->slab_stack[ix] = next == sinfo ? NULL : next;
1537 /* insert slab at head */
1538 allocator_slab_stack_push (allocator, ix, sinfo);
1539 }
1540 /* eagerly free complete unused slabs */
1541 if (!sinfo->n_allocated)
1542 {
1543 /* unlink slab */
1544 SlabInfo *next = sinfo->next, *prev = sinfo->prev;
1545 next->prev = prev;
1546 prev->next = next;
1547 if (allocator->slab_stack[ix] == sinfo)
1548 allocator->slab_stack[ix] = next == sinfo ? NULL : next;
1549 /* free slab */
1550 allocator_memfree (page_size, page);
1551 }
1552 }
1553
1554 /* --- memalign implementation --- */
1555 #ifdef HAVE_MALLOC_H
1556 #include <malloc.h> /* memalign() */
1557 #endif
1558
1559 /* from config.h:
1560 * define HAVE_POSIX_MEMALIGN 1 // if free(posix_memalign(3)) works, <stdlib.h>
1561 * define HAVE_MEMALIGN 1 // if free(memalign(3)) works, <malloc.h>
1562 * define HAVE_VALLOC 1 // if free(valloc(3)) works, <stdlib.h> or <malloc.h>
1563 * if none is provided, we implement malloc(3)-based alloc-only page alignment
1564 */
1565
1566 #if !(HAVE_POSIX_MEMALIGN || HAVE_MEMALIGN || HAVE_VALLOC)
1567 G_GNUC_BEGIN_IGNORE_DEPRECATIONS
1568 static GTrashStack *compat_valloc_trash = NULL;
1569 G_GNUC_END_IGNORE_DEPRECATIONS
1570 #endif
1571
1572 static gpointer
allocator_memalign(gsize alignment,gsize memsize)1573 allocator_memalign (gsize alignment,
1574 gsize memsize)
1575 {
1576 gpointer aligned_memory = NULL;
1577 gint err = ENOMEM;
1578 #if HAVE_POSIX_MEMALIGN
1579 err = posix_memalign (&aligned_memory, alignment, memsize);
1580 DFX_TRACE(GMemPoolAllocDfx(aligned_memory, alignment, memsize));
1581 #elif HAVE_MEMALIGN
1582 errno = 0;
1583 aligned_memory = memalign (alignment, memsize);
1584 err = errno;
1585 #elif HAVE_VALLOC
1586 errno = 0;
1587 aligned_memory = valloc (memsize);
1588 err = errno;
1589 #else
1590 /* simplistic non-freeing page allocator */
1591 mem_assert (alignment == sys_page_size);
1592 mem_assert (memsize <= sys_page_size);
1593 if (!compat_valloc_trash)
1594 {
1595 const guint n_pages = 16;
1596 guint8 *mem = malloc (n_pages * sys_page_size);
1597 err = errno;
1598 if (mem)
1599 {
1600 gint i = n_pages;
1601 guint8 *amem = (guint8*) ALIGN ((gsize) mem, sys_page_size);
1602 if (amem != mem)
1603 i--; /* mem wasn't page aligned */
1604 G_GNUC_BEGIN_IGNORE_DEPRECATIONS
1605 while (--i >= 0)
1606 g_trash_stack_push (&compat_valloc_trash, amem + i * sys_page_size);
1607 G_GNUC_END_IGNORE_DEPRECATIONS
1608 }
1609 }
1610 G_GNUC_BEGIN_IGNORE_DEPRECATIONS
1611 aligned_memory = g_trash_stack_pop (&compat_valloc_trash);
1612 G_GNUC_END_IGNORE_DEPRECATIONS
1613 #endif
1614 if (!aligned_memory)
1615 errno = err;
1616 return aligned_memory;
1617 }
1618
1619 static void
allocator_memfree(gsize memsize,gpointer mem)1620 allocator_memfree (gsize memsize,
1621 gpointer mem)
1622 {
1623 #if HAVE_POSIX_MEMALIGN || HAVE_MEMALIGN || HAVE_VALLOC
1624 DFX_TRACE(GMemPoolFreeDfx(mem));
1625 free (mem);
1626 #else
1627 mem_assert (memsize <= sys_page_size);
1628 G_GNUC_BEGIN_IGNORE_DEPRECATIONS
1629 g_trash_stack_push (&compat_valloc_trash, mem);
1630 G_GNUC_END_IGNORE_DEPRECATIONS
1631 #endif
1632 }
1633
1634 static void
mem_error(const char * format,...)1635 mem_error (const char *format,
1636 ...)
1637 {
1638 const char *pname;
1639 va_list args;
1640 /* at least, put out "MEMORY-ERROR", in case we segfault during the rest of the function */
1641 fputs ("\n***MEMORY-ERROR***: ", stderr);
1642 pname = g_get_prgname();
1643 g_fprintf (stderr, "%s[%ld]: GSlice: ", pname ? pname : "", (long)getpid());
1644 va_start (args, format);
1645 g_vfprintf (stderr, format, args);
1646 va_end (args);
1647 fputs ("\n", stderr);
1648 abort();
1649 _exit (1);
1650 }
1651
1652 /* --- g-slice memory checker tree --- */
1653 typedef size_t SmcKType; /* key type */
1654 typedef size_t SmcVType; /* value type */
1655 typedef struct {
1656 SmcKType key;
1657 SmcVType value;
1658 } SmcEntry;
1659 static void smc_tree_insert (SmcKType key,
1660 SmcVType value);
1661 static gboolean smc_tree_lookup (SmcKType key,
1662 SmcVType *value_p);
1663 static gboolean smc_tree_remove (SmcKType key);
1664
1665
1666 /* --- g-slice memory checker implementation --- */
1667 static void
smc_notify_alloc(void * pointer,size_t size)1668 smc_notify_alloc (void *pointer,
1669 size_t size)
1670 {
1671 size_t address = (size_t) pointer;
1672 if (pointer)
1673 smc_tree_insert (address, size);
1674 }
1675
1676 #if 0
1677 static void
1678 smc_notify_ignore (void *pointer)
1679 {
1680 size_t address = (size_t) pointer;
1681 if (pointer)
1682 smc_tree_remove (address);
1683 }
1684 #endif
1685
1686 static int
smc_notify_free(void * pointer,size_t size)1687 smc_notify_free (void *pointer,
1688 size_t size)
1689 {
1690 size_t address = (size_t) pointer;
1691 SmcVType real_size;
1692 gboolean found_one;
1693
1694 if (!pointer)
1695 return 1; /* ignore */
1696 found_one = smc_tree_lookup (address, &real_size);
1697 if (!found_one)
1698 {
1699 g_fprintf (stderr, "GSlice: MemChecker: attempt to release non-allocated block: %p size=%" G_GSIZE_FORMAT "\n", pointer, size);
1700 return 0;
1701 }
1702 if (real_size != size && (real_size || size))
1703 {
1704 g_fprintf (stderr, "GSlice: MemChecker: attempt to release block with invalid size: %p size=%" G_GSIZE_FORMAT " invalid-size=%" G_GSIZE_FORMAT "\n", pointer, real_size, size);
1705 return 0;
1706 }
1707 if (!smc_tree_remove (address))
1708 {
1709 g_fprintf (stderr, "GSlice: MemChecker: attempt to release non-allocated block: %p size=%" G_GSIZE_FORMAT "\n", pointer, size);
1710 return 0;
1711 }
1712 return 1; /* all fine */
1713 }
1714
1715 /* --- g-slice memory checker tree implementation --- */
1716 #define SMC_TRUNK_COUNT (4093 /* 16381 */) /* prime, to distribute trunk collisions (big, allocated just once) */
1717 #define SMC_BRANCH_COUNT (511) /* prime, to distribute branch collisions */
1718 #define SMC_TRUNK_EXTENT (SMC_BRANCH_COUNT * 2039) /* key address space per trunk, should distribute uniformly across BRANCH_COUNT */
1719 #define SMC_TRUNK_HASH(k) ((k / SMC_TRUNK_EXTENT) % SMC_TRUNK_COUNT) /* generate new trunk hash per megabyte (roughly) */
1720 #define SMC_BRANCH_HASH(k) (k % SMC_BRANCH_COUNT)
1721
1722 typedef struct {
1723 SmcEntry *entries;
1724 unsigned int n_entries;
1725 } SmcBranch;
1726
1727 static SmcBranch **smc_tree_root = NULL;
1728
1729 static void
smc_tree_abort(int errval)1730 smc_tree_abort (int errval)
1731 {
1732 const char *syserr = strerror (errval);
1733 mem_error ("MemChecker: failure in debugging tree: %s", syserr);
1734 }
1735
1736 static inline SmcEntry*
smc_tree_branch_grow_L(SmcBranch * branch,unsigned int index)1737 smc_tree_branch_grow_L (SmcBranch *branch,
1738 unsigned int index)
1739 {
1740 unsigned int old_size = branch->n_entries * sizeof (branch->entries[0]);
1741 unsigned int new_size = old_size + sizeof (branch->entries[0]);
1742 SmcEntry *entry;
1743 mem_assert (index <= branch->n_entries);
1744 branch->entries = (SmcEntry*) realloc (branch->entries, new_size);
1745 if (!branch->entries)
1746 smc_tree_abort (errno);
1747 entry = branch->entries + index;
1748 memmove (entry + 1, entry, (branch->n_entries - index) * sizeof (entry[0]));
1749 branch->n_entries += 1;
1750 return entry;
1751 }
1752
1753 static inline SmcEntry*
smc_tree_branch_lookup_nearest_L(SmcBranch * branch,SmcKType key)1754 smc_tree_branch_lookup_nearest_L (SmcBranch *branch,
1755 SmcKType key)
1756 {
1757 unsigned int n_nodes = branch->n_entries, offs = 0;
1758 SmcEntry *check = branch->entries;
1759 int cmp = 0;
1760 while (offs < n_nodes)
1761 {
1762 unsigned int i = (offs + n_nodes) >> 1;
1763 check = branch->entries + i;
1764 cmp = key < check->key ? -1 : key != check->key;
1765 if (cmp == 0)
1766 return check; /* return exact match */
1767 else if (cmp < 0)
1768 n_nodes = i;
1769 else /* (cmp > 0) */
1770 offs = i + 1;
1771 }
1772 /* check points at last mismatch, cmp > 0 indicates greater key */
1773 return cmp > 0 ? check + 1 : check; /* return insertion position for inexact match */
1774 }
1775
1776 static void
smc_tree_insert(SmcKType key,SmcVType value)1777 smc_tree_insert (SmcKType key,
1778 SmcVType value)
1779 {
1780 unsigned int ix0, ix1;
1781 SmcEntry *entry;
1782
1783 g_mutex_lock (&smc_tree_mutex);
1784 ix0 = SMC_TRUNK_HASH (key);
1785 ix1 = SMC_BRANCH_HASH (key);
1786 if (!smc_tree_root)
1787 {
1788 smc_tree_root = calloc (SMC_TRUNK_COUNT, sizeof (smc_tree_root[0]));
1789 if (!smc_tree_root)
1790 smc_tree_abort (errno);
1791 }
1792 if (!smc_tree_root[ix0])
1793 {
1794 smc_tree_root[ix0] = calloc (SMC_BRANCH_COUNT, sizeof (smc_tree_root[0][0]));
1795 if (!smc_tree_root[ix0])
1796 smc_tree_abort (errno);
1797 }
1798 entry = smc_tree_branch_lookup_nearest_L (&smc_tree_root[ix0][ix1], key);
1799 if (!entry || /* need create */
1800 entry >= smc_tree_root[ix0][ix1].entries + smc_tree_root[ix0][ix1].n_entries || /* need append */
1801 entry->key != key) /* need insert */
1802 entry = smc_tree_branch_grow_L (&smc_tree_root[ix0][ix1], entry - smc_tree_root[ix0][ix1].entries);
1803 entry->key = key;
1804 entry->value = value;
1805 g_mutex_unlock (&smc_tree_mutex);
1806 }
1807
1808 static gboolean
smc_tree_lookup(SmcKType key,SmcVType * value_p)1809 smc_tree_lookup (SmcKType key,
1810 SmcVType *value_p)
1811 {
1812 SmcEntry *entry = NULL;
1813 unsigned int ix0 = SMC_TRUNK_HASH (key), ix1 = SMC_BRANCH_HASH (key);
1814 gboolean found_one = FALSE;
1815 *value_p = 0;
1816 g_mutex_lock (&smc_tree_mutex);
1817 if (smc_tree_root && smc_tree_root[ix0])
1818 {
1819 entry = smc_tree_branch_lookup_nearest_L (&smc_tree_root[ix0][ix1], key);
1820 if (entry &&
1821 entry < smc_tree_root[ix0][ix1].entries + smc_tree_root[ix0][ix1].n_entries &&
1822 entry->key == key)
1823 {
1824 found_one = TRUE;
1825 *value_p = entry->value;
1826 }
1827 }
1828 g_mutex_unlock (&smc_tree_mutex);
1829 return found_one;
1830 }
1831
1832 static gboolean
smc_tree_remove(SmcKType key)1833 smc_tree_remove (SmcKType key)
1834 {
1835 unsigned int ix0 = SMC_TRUNK_HASH (key), ix1 = SMC_BRANCH_HASH (key);
1836 gboolean found_one = FALSE;
1837 g_mutex_lock (&smc_tree_mutex);
1838 if (smc_tree_root && smc_tree_root[ix0])
1839 {
1840 SmcEntry *entry = smc_tree_branch_lookup_nearest_L (&smc_tree_root[ix0][ix1], key);
1841 if (entry &&
1842 entry < smc_tree_root[ix0][ix1].entries + smc_tree_root[ix0][ix1].n_entries &&
1843 entry->key == key)
1844 {
1845 unsigned int i = entry - smc_tree_root[ix0][ix1].entries;
1846 smc_tree_root[ix0][ix1].n_entries -= 1;
1847 memmove (entry, entry + 1, (smc_tree_root[ix0][ix1].n_entries - i) * sizeof (entry[0]));
1848 if (!smc_tree_root[ix0][ix1].n_entries)
1849 {
1850 /* avoid useless pressure on the memory system */
1851 free (smc_tree_root[ix0][ix1].entries);
1852 smc_tree_root[ix0][ix1].entries = NULL;
1853 }
1854 found_one = TRUE;
1855 }
1856 }
1857 g_mutex_unlock (&smc_tree_mutex);
1858 return found_one;
1859 }
1860
1861 #ifdef G_ENABLE_DEBUG
1862 void
g_slice_debug_tree_statistics(void)1863 g_slice_debug_tree_statistics (void)
1864 {
1865 g_mutex_lock (&smc_tree_mutex);
1866 if (smc_tree_root)
1867 {
1868 unsigned int i, j, t = 0, o = 0, b = 0, su = 0, ex = 0, en = 4294967295u;
1869 double tf, bf;
1870 for (i = 0; i < SMC_TRUNK_COUNT; i++)
1871 if (smc_tree_root[i])
1872 {
1873 t++;
1874 for (j = 0; j < SMC_BRANCH_COUNT; j++)
1875 if (smc_tree_root[i][j].n_entries)
1876 {
1877 b++;
1878 su += smc_tree_root[i][j].n_entries;
1879 en = MIN (en, smc_tree_root[i][j].n_entries);
1880 ex = MAX (ex, smc_tree_root[i][j].n_entries);
1881 }
1882 else if (smc_tree_root[i][j].entries)
1883 o++; /* formerly used, now empty */
1884 }
1885 en = b ? en : 0;
1886 tf = MAX (t, 1.0); /* max(1) to be a valid divisor */
1887 bf = MAX (b, 1.0); /* max(1) to be a valid divisor */
1888 g_fprintf (stderr, "GSlice: MemChecker: %u trunks, %u branches, %u old branches\n", t, b, o);
1889 g_fprintf (stderr, "GSlice: MemChecker: %f branches per trunk, %.2f%% utilization\n",
1890 b / tf,
1891 100.0 - (SMC_BRANCH_COUNT - b / tf) / (0.01 * SMC_BRANCH_COUNT));
1892 g_fprintf (stderr, "GSlice: MemChecker: %f entries per branch, %u minimum, %u maximum\n",
1893 su / bf, en, ex);
1894 }
1895 else
1896 g_fprintf (stderr, "GSlice: MemChecker: root=NULL\n");
1897 g_mutex_unlock (&smc_tree_mutex);
1898
1899 /* sample statistics (beast + GSLice + 24h scripted core & GUI activity):
1900 * PID %CPU %MEM VSZ RSS COMMAND
1901 * 8887 30.3 45.8 456068 414856 beast-0.7.1 empty.bse
1902 * $ cat /proc/8887/statm # total-program-size resident-set-size shared-pages text/code data/stack library dirty-pages
1903 * 114017 103714 2354 344 0 108676 0
1904 * $ cat /proc/8887/status
1905 * Name: beast-0.7.1
1906 * VmSize: 456068 kB
1907 * VmLck: 0 kB
1908 * VmRSS: 414856 kB
1909 * VmData: 434620 kB
1910 * VmStk: 84 kB
1911 * VmExe: 1376 kB
1912 * VmLib: 13036 kB
1913 * VmPTE: 456 kB
1914 * Threads: 3
1915 * (gdb) print g_slice_debug_tree_statistics ()
1916 * GSlice: MemChecker: 422 trunks, 213068 branches, 0 old branches
1917 * GSlice: MemChecker: 504.900474 branches per trunk, 98.81% utilization
1918 * GSlice: MemChecker: 4.965039 entries per branch, 1 minimum, 37 maximum
1919 */
1920 }
1921 #endif /* G_ENABLE_DEBUG */
1922