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