mallocx.c raw
1 /*
2 * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
3 * Copyright (c) 1991-1994 by Xerox Corporation. All rights reserved.
4 * Copyright (c) 1996 by Silicon Graphics. All rights reserved.
5 * Copyright (c) 2000 by Hewlett-Packard Company. All rights reserved.
6 * Copyright (c) 2009-2022 Ivan Maidanski
7 *
8 * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
9 * OR IMPLIED. ANY USE IS AT YOUR OWN RISK.
10 *
11 * Permission is hereby granted to use or copy this program
12 * for any purpose, provided the above notices are retained on all copies.
13 * Permission to modify the code and to distribute modified code is granted,
14 * provided the above notices are retained, and a notice that the code was
15 * modified is included with the above copyright notice.
16 */
17
18 #include "private/gc_priv.h"
19
20 /*
21 * These are extra allocation routines that are likely to be less
22 * frequently used than those in `malloc.c` file. They are separate in
23 * the hope that the `.o` file will be excluded from statically linked
24 * executables. We should probably break this up further.
25 */
26
27 #include <string.h>
28
29 #ifndef MSWINCE
30 # include <errno.h>
31 #endif
32
33 /*
34 * Some externally visible but unadvertised variables to allow access
35 * to free lists from inlined allocators without include `gc_priv.h` file
36 * or introducing dependencies on internal data structure layouts.
37 */
38 #include "private/gc_alloc_ptrs.h"
39 void **const GC_objfreelist_ptr = GC_objfreelist;
40 void **const GC_aobjfreelist_ptr = GC_aobjfreelist;
41 void **const GC_uobjfreelist_ptr = GC_uobjfreelist;
42 #ifdef GC_ATOMIC_UNCOLLECTABLE
43 void **const GC_auobjfreelist_ptr = GC_auobjfreelist;
44 #endif
45
46 GC_API int GC_CALL
47 GC_get_kind_and_size(const void *p, size_t *psize)
48 {
49 const hdr *hhdr = HDR(p);
50
51 if (psize != NULL) {
52 *psize = hhdr->hb_sz;
53 }
54 return hhdr->hb_obj_kind;
55 }
56
57 GC_API GC_ATTR_MALLOC void *GC_CALL
58 GC_generic_or_special_malloc(size_t lb, int kind)
59 {
60 switch (kind) {
61 case PTRFREE:
62 case NORMAL:
63 return GC_malloc_kind(lb, kind);
64 case UNCOLLECTABLE:
65 #ifdef GC_ATOMIC_UNCOLLECTABLE
66 case AUNCOLLECTABLE:
67 #endif
68 return GC_generic_malloc_uncollectable(lb, kind);
69 default:
70 return GC_generic_malloc_aligned(lb, kind, 0 /* `flags` */, 0);
71 }
72 }
73
74 GC_API void *GC_CALL
75 GC_realloc(void *p, size_t lb)
76 {
77 hdr *hhdr;
78 void *result;
79 #if defined(_FORTIFY_SOURCE) && defined(__GNUC__) && !defined(__clang__)
80 /*
81 * Use `cleared_p` instead of `p` as a workaround to avoid passing
82 * `alloc_size(lb)` attribute associated with `p` to `memset`
83 * (including a `memset` call inside `GC_free`).
84 */
85 volatile GC_uintptr_t cleared_p = (GC_uintptr_t)p;
86 #else
87 # define cleared_p p
88 #endif
89 size_t sz; /*< current size in bytes */
90 size_t orig_sz; /*< original `sz` (in bytes) */
91 int obj_kind;
92
93 if (NULL == p) {
94 /* Required by ANSI. */
95 return GC_malloc(lb);
96 }
97 if (0 == lb) /* `&& p != NULL` */ {
98 #ifndef IGNORE_FREE
99 GC_free(p);
100 #endif
101 return NULL;
102 }
103 hhdr = HDR(HBLKPTR(p));
104 sz = hhdr->hb_sz;
105 obj_kind = hhdr->hb_obj_kind;
106 orig_sz = sz;
107
108 if (sz > MAXOBJBYTES) {
109 const struct obj_kind *ok = &GC_obj_kinds[obj_kind];
110 word descr = ok->ok_descriptor;
111
112 /* Round it up to the next whole heap block. */
113 sz = (sz + HBLKSIZE - 1) & ~(HBLKSIZE - 1);
114 #if ALIGNMENT > GC_DS_TAGS
115 /*
116 * An extra byte is not added in case of ignore-off-page allocated
117 * objects not smaller than `HBLKSIZE`.
118 */
119 GC_ASSERT(sz >= HBLKSIZE);
120 if (EXTRA_BYTES != 0 && (hhdr->hb_flags & IGNORE_OFF_PAGE) != 0
121 && obj_kind == NORMAL)
122 descr += ALIGNMENT; /*< or set to 0 */
123 #endif
124 if (ok->ok_relocate_descr) {
125 descr += sz;
126 }
127
128 /*
129 * `GC_realloc` might be changing the block size while
130 * `GC_reclaim_block` or `GC_clear_hdr_marks` is examining it.
131 * The change to the size field is benign, in that `GC_reclaim`
132 * (and `GC_clear_hdr_marks`) would work correctly with either
133 * value, since we are not changing the number of objects in
134 * the block. But seeing a half-updated value (though unlikely
135 * to occur in practice) could be probably bad.
136 * Using unordered atomic accesses on `hb_sz` and `hb_descr`
137 * fields would solve the issue. (The alternate solution might
138 * be to initially overallocate large objects, so we do not
139 * have to adjust the size in `GC_realloc`, if they still fit.
140 * But that is probably more expensive, since we may end up
141 * scanning a bunch of zeros during the collection.)
142 */
143 #ifdef AO_HAVE_store
144 AO_store(&hhdr->hb_sz, sz);
145 AO_store((AO_t *)&hhdr->hb_descr, descr);
146 #else
147 {
148 LOCK();
149 hhdr->hb_sz = sz;
150 hhdr->hb_descr = descr;
151 UNLOCK();
152 }
153 #endif
154
155 #ifdef MARK_BIT_PER_OBJ
156 GC_ASSERT(hhdr->hb_inv_sz == LARGE_INV_SZ);
157 #else
158 GC_ASSERT((hhdr->hb_flags & LARGE_BLOCK) != 0
159 && hhdr->hb_map[ANY_INDEX] == 1);
160 #endif
161 if (IS_UNCOLLECTABLE(obj_kind))
162 GC_non_gc_bytes += (sz - orig_sz);
163 /* Extra area is already cleared by `GC_alloc_large_and_clear`. */
164 }
165 if (ADD_EXTRA_BYTES(lb) <= sz) {
166 if (lb >= (sz >> 1)) {
167 if (orig_sz > lb) {
168 /* Clear unneeded part of object to avoid bogus pointer tracing. */
169 BZERO((ptr_t)cleared_p + lb, orig_sz - lb);
170 }
171 return p;
172 }
173 /*
174 * Shrink it. Note: shrinking of large blocks is not implemented
175 * efficiently.
176 */
177 sz = lb;
178 }
179 result = GC_generic_or_special_malloc((word)lb, obj_kind);
180 if (LIKELY(result != NULL)) {
181 /*
182 * In case of shrink, it could also return original object.
183 * But this gives the client warning of imminent disaster.
184 */
185 BCOPY(p, result, sz);
186 #ifndef IGNORE_FREE
187 GC_free((ptr_t)cleared_p);
188 #endif
189 }
190 return result;
191 #undef cleared_p
192 }
193
194 #if defined(REDIRECT_MALLOC) && !defined(REDIRECT_REALLOC)
195 # define REDIRECT_REALLOC GC_realloc
196 #endif
197
198 #ifdef REDIRECT_REALLOC
199
200 /* As with `malloc`, avoid two levels of extra calls here. */
201 # define GC_debug_realloc_replacement(p, lb) \
202 GC_debug_realloc(p, lb, GC_DBG_EXTRAS)
203
204 # if !defined(REDIRECT_MALLOC_IN_HEADER)
205 void *
206 realloc(void *p, size_t lb)
207 {
208 return REDIRECT_REALLOC(p, lb);
209 }
210 # endif
211
212 # undef GC_debug_realloc_replacement
213 #endif /* REDIRECT_REALLOC */
214
215 GC_API GC_ATTR_MALLOC void *GC_CALL
216 GC_generic_malloc_ignore_off_page(size_t lb, int kind)
217 {
218 return GC_generic_malloc_aligned(lb, kind, IGNORE_OFF_PAGE,
219 0 /* `align_m1` */);
220 }
221
222 GC_API GC_ATTR_MALLOC void *GC_CALL
223 GC_malloc_ignore_off_page(size_t lb)
224 {
225 return GC_generic_malloc_aligned(lb, NORMAL, IGNORE_OFF_PAGE, 0);
226 }
227
228 GC_API GC_ATTR_MALLOC void *GC_CALL
229 GC_malloc_atomic_ignore_off_page(size_t lb)
230 {
231 return GC_generic_malloc_aligned(lb, PTRFREE, IGNORE_OFF_PAGE, 0);
232 }
233
234 /*
235 * Increment `GC_bytes_allocd` from code that does not have direct access
236 * to `GC_arrays`.
237 */
238 void GC_CALL
239 GC_incr_bytes_allocd(size_t n)
240 {
241 GC_bytes_allocd += n;
242 }
243
244 /* The same as `GC_incr_bytes_allocd` but for `GC_bytes_freed`. */
245 void GC_CALL
246 GC_incr_bytes_freed(size_t n)
247 {
248 GC_bytes_freed += n;
249 }
250
251 GC_API size_t GC_CALL
252 GC_get_expl_freed_bytes_since_gc(void)
253 {
254 return (size_t)GC_bytes_freed;
255 }
256
257 #ifdef PARALLEL_MARK
258 /*
259 * Number of bytes of memory allocated since we released the allocator lock.
260 * Instead of reacquiring the allocator lock just to add this in, we add it
261 * in the next time we reacquire the allocator lock. (Atomically adding it
262 * does not work, since we would have to atomically update it in `GC_malloc`,
263 * which is too expensive.)
264 */
265 STATIC volatile AO_t GC_bytes_allocd_tmp = 0;
266 #endif /* PARALLEL_MARK */
267
268 GC_API void GC_CALL
269 GC_generic_malloc_many(size_t lb_adjusted, int kind, void **result)
270 {
271 void *op;
272 void *p;
273 void **opp;
274 /* The value of `lb_adjusted` converted to granules. */
275 size_t lg;
276 word my_bytes_allocd = 0;
277 struct obj_kind *ok;
278 struct hblk **rlh;
279
280 GC_ASSERT(lb_adjusted != 0 && (lb_adjusted & (GC_GRANULE_BYTES - 1)) == 0);
281 /* Currently a single object is always allocated if manual VDB. */
282 /*
283 * TODO: `GC_dirty` should be called for each linked object (but the
284 * last one) to support multiple objects allocation.
285 */
286 if (UNLIKELY(lb_adjusted > MAXOBJBYTES) || GC_manual_vdb) {
287 op = GC_generic_malloc_aligned(lb_adjusted - EXTRA_BYTES, kind,
288 0 /* `flags` */, 0 /* `align_m1` */);
289 if (LIKELY(op != NULL))
290 obj_link(op) = NULL;
291 *result = op;
292 #ifndef NO_MANUAL_VDB
293 if (GC_manual_vdb && GC_is_heap_ptr(result)) {
294 GC_dirty_inner(result);
295 REACHABLE_AFTER_DIRTY(op);
296 }
297 #endif
298 return;
299 }
300 GC_ASSERT(kind < MAXOBJKINDS);
301 lg = BYTES_TO_GRANULES(lb_adjusted);
302 if (UNLIKELY(get_have_errors()))
303 GC_print_all_errors();
304 GC_notify_or_invoke_finalizers();
305 GC_DBG_COLLECT_AT_MALLOC(lb_adjusted - EXTRA_BYTES);
306 if (UNLIKELY(!GC_is_initialized))
307 GC_init();
308 LOCK();
309 /* Do our share of marking work. */
310 if (GC_incremental && !GC_dont_gc) {
311 GC_collect_a_little_inner(1);
312 }
313
314 /* First see if we can reclaim a page of objects waiting to be reclaimed. */
315 ok = &GC_obj_kinds[kind];
316 rlh = ok->ok_reclaim_list;
317 if (rlh != NULL) {
318 struct hblk *hbp;
319 hdr *hhdr;
320
321 while ((hbp = rlh[lg]) != NULL) {
322 hhdr = HDR(hbp);
323 rlh[lg] = hhdr->hb_next;
324 GC_ASSERT(hhdr->hb_sz == lb_adjusted);
325 hhdr->hb_last_reclaimed = (unsigned short)GC_gc_no;
326 #ifdef PARALLEL_MARK
327 if (GC_parallel) {
328 GC_signed_word my_bytes_allocd_tmp
329 = (GC_signed_word)AO_load(&GC_bytes_allocd_tmp);
330 GC_ASSERT(my_bytes_allocd_tmp >= 0);
331 /*
332 * We only decrement it while holding the allocator lock.
333 * Thus, we cannot accidentally adjust it down in more than
334 * one thread simultaneously.
335 */
336 if (my_bytes_allocd_tmp != 0) {
337 (void)AO_fetch_and_add(&GC_bytes_allocd_tmp,
338 (AO_t)(-my_bytes_allocd_tmp));
339 GC_bytes_allocd += (word)my_bytes_allocd_tmp;
340 }
341 GC_acquire_mark_lock();
342 ++GC_fl_builder_count;
343 UNLOCK();
344 GC_release_mark_lock();
345 }
346 #endif
347 op = GC_reclaim_generic(hbp, hhdr, lb_adjusted, ok->ok_init, 0,
348 &my_bytes_allocd);
349 if (op != 0) {
350 #ifdef PARALLEL_MARK
351 if (GC_parallel) {
352 *result = op;
353 (void)AO_fetch_and_add(&GC_bytes_allocd_tmp, (AO_t)my_bytes_allocd);
354 GC_acquire_mark_lock();
355 --GC_fl_builder_count;
356 if (GC_fl_builder_count == 0)
357 GC_notify_all_builder();
358 # ifdef THREAD_SANITIZER
359 GC_release_mark_lock();
360 LOCK();
361 GC_bytes_found += (GC_signed_word)my_bytes_allocd;
362 UNLOCK();
363 # else
364 /* The resulting `GC_bytes_found` may be inaccurate. */
365 GC_bytes_found += (GC_signed_word)my_bytes_allocd;
366 GC_release_mark_lock();
367 # endif
368 (void)GC_clear_stack(0);
369 return;
370 }
371 #endif
372 /* We also reclaimed memory, so we need to adjust that count. */
373 GC_bytes_found += (GC_signed_word)my_bytes_allocd;
374 GC_bytes_allocd += my_bytes_allocd;
375 goto out;
376 }
377 #ifdef PARALLEL_MARK
378 if (GC_parallel) {
379 GC_acquire_mark_lock();
380 --GC_fl_builder_count;
381 if (GC_fl_builder_count == 0)
382 GC_notify_all_builder();
383 GC_release_mark_lock();
384 /*
385 * The allocator lock is needed for access to the reclaim list.
386 * We must decrement `GC_fl_builder_count` before reacquiring
387 * the allocator lock. Hopefully this path is rare.
388 */
389 LOCK();
390
391 /* Reload `rlh` after locking. */
392 rlh = ok->ok_reclaim_list;
393 if (NULL == rlh)
394 break;
395 }
396 #endif
397 }
398 }
399 /*
400 * Next try to use prefix of global free list if there is one.
401 * We do not refill it, but we need to use it up before allocating
402 * a new block ourselves.
403 */
404 opp = &ok->ok_freelist[lg];
405 if ((op = *opp) != NULL) {
406 *opp = NULL;
407 my_bytes_allocd = 0;
408 for (p = op; p != NULL; p = obj_link(p)) {
409 my_bytes_allocd += lb_adjusted;
410 if ((word)my_bytes_allocd >= HBLKSIZE) {
411 *opp = obj_link(p);
412 obj_link(p) = NULL;
413 break;
414 }
415 }
416 GC_bytes_allocd += my_bytes_allocd;
417 goto out;
418 }
419
420 /* Next try to allocate a new block worth of objects of this size. */
421 {
422 struct hblk *h
423 = GC_allochblk(lb_adjusted, kind, 0 /* `flags` */, 0 /* `align_m1` */);
424
425 if (h /* `!= NULL` */) { /*< CPPCHECK */
426 if (IS_UNCOLLECTABLE(kind))
427 GC_set_hdr_marks(HDR(h));
428 GC_bytes_allocd += HBLKSIZE - (HBLKSIZE % lb_adjusted);
429 #ifdef PARALLEL_MARK
430 if (GC_parallel) {
431 GC_acquire_mark_lock();
432 ++GC_fl_builder_count;
433 UNLOCK();
434 GC_release_mark_lock();
435
436 op = GC_build_fl(h, NULL, lg, ok->ok_init || GC_debugging_started);
437 *result = op;
438 GC_acquire_mark_lock();
439 --GC_fl_builder_count;
440 if (GC_fl_builder_count == 0)
441 GC_notify_all_builder();
442 GC_release_mark_lock();
443 (void)GC_clear_stack(0);
444 return;
445 }
446 #endif
447 op = GC_build_fl(h, NULL, lg, ok->ok_init || GC_debugging_started);
448 goto out;
449 }
450 }
451
452 /*
453 * As a last attempt, try allocating a single object.
454 * Note that this may trigger a collection or expand the heap.
455 */
456 op = GC_generic_malloc_inner(lb_adjusted - EXTRA_BYTES, kind,
457 0 /* `flags` */);
458 if (op != NULL)
459 obj_link(op) = NULL;
460
461 out:
462 *result = op;
463 UNLOCK();
464 (void)GC_clear_stack(0);
465 }
466
467 GC_API GC_ATTR_MALLOC void *GC_CALL
468 GC_malloc_many(size_t lb)
469 {
470 void *result;
471 size_t lg, lb_adjusted;
472
473 if (UNLIKELY(0 == lb))
474 lb = 1;
475 lg = ALLOC_REQUEST_GRANS(lb);
476 lb_adjusted = GRANULES_TO_BYTES(lg);
477 GC_generic_malloc_many(lb_adjusted, NORMAL, &result);
478 return result;
479 }
480
481 /*
482 * TODO: The debugging variant of `GC_memalign` and friends is tricky
483 * and currently missing. The major difficulty is: `store_debug_info`
484 * should return the pointer of the object with the requested alignment
485 * (unlike the object header).
486 */
487
488 GC_API GC_ATTR_MALLOC void *GC_CALL
489 GC_memalign(size_t align, size_t lb)
490 {
491 size_t align_m1 = align - 1;
492
493 /* Check the alignment argument. */
494 if (UNLIKELY(0 == align || (align & align_m1) != 0))
495 return NULL;
496
497 /* TODO: Use thread-local allocation. */
498 if (align <= GC_GRANULE_BYTES)
499 return GC_malloc(lb);
500 return GC_malloc_kind_aligned_global(lb, NORMAL, align_m1);
501 }
502
503 GC_API int GC_CALL
504 GC_posix_memalign(void **memptr, size_t align, size_t lb)
505 {
506 void *p;
507 size_t align_minus_one = align - 1; /*< to workaround a cppcheck warning */
508
509 /* Check alignment properly. */
510 if (UNLIKELY(align < sizeof(void *) || (align_minus_one & align) != 0)) {
511 #ifdef MSWINCE
512 return ERROR_INVALID_PARAMETER;
513 #else
514 return EINVAL;
515 #endif
516 }
517
518 p = GC_memalign(align, lb);
519 if (UNLIKELY(NULL == p)) {
520 #ifdef MSWINCE
521 return ERROR_NOT_ENOUGH_MEMORY;
522 #else
523 return ENOMEM;
524 #endif
525 }
526 *memptr = p;
527 return 0; /*< success */
528 }
529
530 #ifndef GC_NO_VALLOC
531 GC_API GC_ATTR_MALLOC void *GC_CALL
532 GC_valloc(size_t lb)
533 {
534 if (UNLIKELY(!GC_is_initialized))
535 GC_init();
536 GC_ASSERT(GC_real_page_size != 0);
537 return GC_memalign(GC_real_page_size, lb);
538 }
539
540 GC_API GC_ATTR_MALLOC void *GC_CALL
541 GC_pvalloc(size_t lb)
542 {
543 if (UNLIKELY(!GC_is_initialized))
544 GC_init();
545 GC_ASSERT(GC_real_page_size != 0);
546 lb = SIZET_SAT_ADD(lb, GC_real_page_size - 1) & ~(GC_real_page_size - 1);
547 return GC_memalign(GC_real_page_size, lb);
548 }
549 #endif /* !GC_NO_VALLOC */
550
551 GC_API GC_ATTR_MALLOC char *GC_CALL
552 GC_strdup(const char *s)
553 {
554 /*
555 * Implementation of a variant of `strdup()` that uses the collector
556 * to allocate a copy of the string.
557 */
558 char *copy;
559 size_t lb;
560 if (s == NULL)
561 return NULL;
562 lb = strlen(s) + 1;
563 copy = (char *)GC_malloc_atomic(lb);
564 if (UNLIKELY(NULL == copy)) {
565 #ifndef MSWINCE
566 errno = ENOMEM;
567 #endif
568 return NULL;
569 }
570 BCOPY(s, copy, lb);
571 return copy;
572 }
573
574 GC_API GC_ATTR_MALLOC char *GC_CALL
575 GC_strndup(const char *str, size_t size)
576 {
577 char *copy;
578 /* Note: `str` is expected to be non-`NULL`. */
579 size_t len = strlen(str);
580 if (UNLIKELY(len > size))
581 len = size;
582 copy = (char *)GC_malloc_atomic(len + 1);
583 if (UNLIKELY(NULL == copy)) {
584 #ifndef MSWINCE
585 errno = ENOMEM;
586 #endif
587 return NULL;
588 }
589 if (LIKELY(len > 0))
590 BCOPY(str, copy, len);
591 copy[len] = '\0';
592 return copy;
593 }
594
595 #ifdef GC_REQUIRE_WCSDUP
596 # include <wchar.h> /*< for `wcslen()` */
597
598 GC_API GC_ATTR_MALLOC wchar_t *GC_CALL
599 GC_wcsdup(const wchar_t *str)
600 {
601 size_t lb = (wcslen(str) + 1) * sizeof(wchar_t);
602 wchar_t *copy = (wchar_t *)GC_malloc_atomic(lb);
603
604 if (UNLIKELY(NULL == copy)) {
605 # ifndef MSWINCE
606 errno = ENOMEM;
607 # endif
608 return NULL;
609 }
610 BCOPY(str, copy, lb);
611 return copy;
612 }
613
614 # if !defined(wcsdup) && defined(REDIRECT_MALLOC) \
615 && !defined(REDIRECT_MALLOC_IN_HEADER)
616 wchar_t *
617 wcsdup(const wchar_t *str)
618 {
619 return GC_wcsdup(str);
620 }
621 # endif
622 #endif /* GC_REQUIRE_WCSDUP */
623
624 #ifndef CPPCHECK
625 GC_API void *GC_CALL
626 GC_malloc_stubborn(size_t lb)
627 {
628 return GC_malloc(lb);
629 }
630
631 GC_API void GC_CALL
632 GC_change_stubborn(const void *p)
633 {
634 UNUSED_ARG(p);
635 }
636 #endif /* !CPPCHECK */
637
638 GC_API void GC_CALL
639 GC_end_stubborn_change(const void *p)
640 {
641 GC_dirty(p); /*< entire object */
642 }
643
644 GC_API void GC_CALL
645 GC_ptr_store_and_dirty(void *p, const void *q)
646 {
647 *(const void **)p = q;
648 GC_dirty(p);
649 REACHABLE_AFTER_DIRTY(q);
650 }
651