2 * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
3 * Copyright (c) 1991-1994 by Xerox Corporation. All rights reserved.
4 * Copyright (c) 1998-1999 by Silicon Graphics. All rights reserved.
5 * Copyright (c) 1999 by Hewlett-Packard Company. All rights reserved.
7 * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
8 * OR IMPLIED. ANY USE IS AT YOUR OWN RISK.
10 * Permission is hereby granted to use or copy this program
11 * for any purpose, provided the above notices are retained on all copies.
12 * Permission to modify the code and to distribute modified code is granted,
13 * provided the above notices are retained, and a notice that the code was
14 * modified is included with the above copyright notice.
17 #include "private/gc_priv.h"
21 GC_bool GC_use_entire_heap = 0;
24 * Free heap blocks are kept on one of several free lists,
25 * depending on the size of the block. Each free list is doubly linked.
26 * Adjacent free blocks are coalesced.
30 # define MAX_BLACK_LIST_ALLOC (2*HBLKSIZE)
31 /* largest block we will allocate starting on a black */
32 /* listed block. Must be >= HBLKSIZE. */
35 # define UNIQUE_THRESHOLD 32
36 /* Sizes up to this many HBLKs each have their own free list */
37 # define HUGE_THRESHOLD 256
38 /* Sizes of at least this many heap blocks are mapped to a */
39 /* single free list. */
40 # define FL_COMPRESSION 8
41 /* In between sizes map this many distinct sizes to a single */
44 # define N_HBLK_FLS (HUGE_THRESHOLD - UNIQUE_THRESHOLD)/FL_COMPRESSION \
47 STATIC struct hblk * GC_hblkfreelist[N_HBLK_FLS+1] = { 0 };
48 /* List of completely empty heap blocks */
49 /* Linked through hb_next field of */
50 /* header structure associated with */
55 STATIC word GC_free_bytes[N_HBLK_FLS+1] = { 0 };
56 /* Number of free bytes on each list. */
58 /* Return the largest n such that */
59 /* Is GC_large_allocd_bytes + the number of free bytes on lists */
60 /* n .. N_HBLK_FLS > GC_max_large_allocd_bytes. */
61 /* If there is no such n, return 0. */
62 GC_INLINE int GC_enough_large_bytes_left(void)
65 word bytes = GC_large_allocd_bytes;
67 GC_ASSERT(GC_max_large_allocd_bytes <= GC_heapsize);
68 for (n = N_HBLK_FLS; n >= 0; --n) {
69 bytes += GC_free_bytes[n];
70 if (bytes >= GC_max_large_allocd_bytes) return n;
75 # define INCR_FREE_BYTES(n, b) GC_free_bytes[n] += (b);
77 # define FREE_ASSERT(e) GC_ASSERT(e)
79 #else /* USE_MUNMAP */
81 # define INCR_FREE_BYTES(n, b)
82 # define FREE_ASSERT(e)
84 #endif /* USE_MUNMAP */
86 /* Map a number of blocks to the appropriate large block free list index. */
87 STATIC int GC_hblk_fl_from_blocks(word blocks_needed)
89 if (blocks_needed <= UNIQUE_THRESHOLD) return (int)blocks_needed;
90 if (blocks_needed >= HUGE_THRESHOLD) return N_HBLK_FLS;
91 return (int)(blocks_needed - UNIQUE_THRESHOLD)/FL_COMPRESSION
96 # define PHDR(hhdr) HDR(hhdr -> hb_prev)
97 # define NHDR(hhdr) HDR(hhdr -> hb_next)
100 # define IS_MAPPED(hhdr) (((hhdr) -> hb_flags & WAS_UNMAPPED) == 0)
101 # else /* !USE_MUNMAP */
102 # define IS_MAPPED(hhdr) 1
103 # endif /* USE_MUNMAP */
105 # if !defined(NO_DEBUGGING)
106 void GC_print_hblkfreelist(void)
114 for (i = 0; i <= N_HBLK_FLS; ++i) {
115 h = GC_hblkfreelist[i];
117 if (0 != h) GC_printf("Free list %u:\n", i);
119 if (0 != h) GC_printf("Free list %u (Total size %lu):\n",
120 i, (unsigned long)GC_free_bytes[i]);
126 GC_printf("\t%p size %lu %s black listed\n", h, (unsigned long)sz,
127 GC_is_black_listed(h, HBLKSIZE) != 0 ? "start" :
128 GC_is_black_listed(h, hhdr -> hb_sz) != 0 ? "partially" :
134 if (total_free != GC_large_free_bytes) {
135 GC_printf("GC_large_free_bytes = %lu (INCONSISTENT!!)\n",
136 (unsigned long) GC_large_free_bytes);
139 GC_printf("Total of %lu bytes on free list\n", (unsigned long)total_free);
142 /* Return the free list index on which the block described by the header */
143 /* appears, or -1 if it appears nowhere. */
144 static int free_list_index_of(hdr *wanted)
150 for (i = 0; i <= N_HBLK_FLS; ++i) {
151 h = GC_hblkfreelist[i];
154 if (hhdr == wanted) return i;
161 void GC_dump_regions(void)
168 for (i = 0; i < GC_n_heap_sects; ++i) {
169 start = GC_heap_sects[i].hs_start;
170 bytes = GC_heap_sects[i].hs_bytes;
172 /* Merge in contiguous sections. */
173 while (i+1 < GC_n_heap_sects && GC_heap_sects[i+1].hs_start == end) {
175 end = GC_heap_sects[i].hs_start + GC_heap_sects[i].hs_bytes;
177 GC_printf("***Section from %p to %p\n", start, end);
178 for (p = start; p < end;) {
180 if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) {
181 GC_printf("\t%p Missing header!!(%p)\n", p, hhdr);
185 if (HBLK_IS_FREE(hhdr)) {
186 int correct_index = GC_hblk_fl_from_blocks(
187 divHBLKSZ(hhdr -> hb_sz));
190 GC_printf("\t%p\tfree block of size 0x%lx bytes%s\n", p,
191 (unsigned long)(hhdr -> hb_sz),
192 IS_MAPPED(hhdr) ? "" : " (unmapped)");
193 actual_index = free_list_index_of(hhdr);
194 if (-1 == actual_index) {
195 GC_printf("\t\tBlock not on free list %d!!\n",
197 } else if (correct_index != actual_index) {
198 GC_printf("\t\tBlock on list %d, should be on %d!!\n",
199 actual_index, correct_index);
203 GC_printf("\t%p\tused for blocks of size 0x%lx bytes\n", p,
204 (unsigned long)(hhdr -> hb_sz));
205 p += HBLKSIZE * OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz);
211 # endif /* NO_DEBUGGING */
213 /* Initialize hdr for a block containing the indicated size and */
214 /* kind of objects. */
215 /* Return FALSE on failure. */
216 static GC_bool setup_header(hdr * hhdr, struct hblk *block, size_t byte_sz,
217 int kind, unsigned flags)
220 # ifndef MARK_BIT_PER_OBJ
224 /* Set size, kind and mark proc fields */
225 hhdr -> hb_sz = byte_sz;
226 hhdr -> hb_obj_kind = (unsigned char)kind;
227 hhdr -> hb_flags = (unsigned char)flags;
228 hhdr -> hb_block = block;
229 descr = GC_obj_kinds[kind].ok_descriptor;
230 if (GC_obj_kinds[kind].ok_relocate_descr) descr += byte_sz;
231 hhdr -> hb_descr = descr;
233 # ifdef MARK_BIT_PER_OBJ
234 /* Set hb_inv_sz as portably as possible. */
235 /* We set it to the smallest value such that sz * inv_sz > 2**32 */
236 /* This may be more precision than necessary. */
237 if (byte_sz > MAXOBJBYTES) {
238 hhdr -> hb_inv_sz = LARGE_INV_SZ;
242 # if CPP_WORDSZ == 64
243 inv_sz = ((word)1 << 32)/byte_sz;
244 if (((inv_sz*byte_sz) >> 32) == 0) ++inv_sz;
245 # else /* 32 bit words */
246 GC_ASSERT(byte_sz >= 4);
247 inv_sz = ((unsigned)1 << 31)/byte_sz;
249 while (inv_sz*byte_sz > byte_sz) ++inv_sz;
251 hhdr -> hb_inv_sz = inv_sz;
253 # else /* MARK_BIT_PER_GRANULE */
254 hhdr -> hb_large_block = (unsigned char)(byte_sz > MAXOBJBYTES);
255 granules = BYTES_TO_GRANULES(byte_sz);
256 if (EXPECT(!GC_add_map_entry(granules), FALSE)) {
257 /* Make it look like a valid block. */
258 hhdr -> hb_sz = HBLKSIZE;
259 hhdr -> hb_descr = 0;
260 hhdr -> hb_large_block = TRUE;
264 size_t index = (hhdr -> hb_large_block? 0 : granules);
265 hhdr -> hb_map = GC_obj_map[index];
267 # endif /* MARK_BIT_PER_GRANULE */
269 /* Clear mark bits */
270 GC_clear_hdr_marks(hhdr);
272 hhdr -> hb_last_reclaimed = (unsigned short)GC_gc_no;
276 #define FL_UNKNOWN -1
278 * Remove hhdr from the appropriate free list.
279 * We assume it is on the nth free list, or on the size
280 * appropriate free list if n is FL_UNKNOWN.
282 STATIC void GC_remove_from_fl(hdr *hhdr, int n)
286 GC_ASSERT(((hhdr -> hb_sz) & (HBLKSIZE-1)) == 0);
288 /* We always need index to mainatin free counts. */
289 if (FL_UNKNOWN == n) {
290 index = GC_hblk_fl_from_blocks(divHBLKSZ(hhdr -> hb_sz));
295 if (hhdr -> hb_prev == 0) {
297 if (FL_UNKNOWN == n) {
298 index = GC_hblk_fl_from_blocks(divHBLKSZ(hhdr -> hb_sz));
303 GC_ASSERT(HDR(GC_hblkfreelist[index]) == hhdr);
304 GC_hblkfreelist[index] = hhdr -> hb_next;
307 GET_HDR(hhdr -> hb_prev, phdr);
308 phdr -> hb_next = hhdr -> hb_next;
310 FREE_ASSERT(GC_free_bytes[index] >= hhdr -> hb_sz);
311 INCR_FREE_BYTES(index, - (signed_word)(hhdr -> hb_sz));
312 if (0 != hhdr -> hb_next) {
314 GC_ASSERT(!IS_FORWARDING_ADDR_OR_NIL(NHDR(hhdr)));
315 GET_HDR(hhdr -> hb_next, nhdr);
316 nhdr -> hb_prev = hhdr -> hb_prev;
321 * Return a pointer to the free block ending just before h, if any.
323 STATIC struct hblk * GC_free_block_ending_at(struct hblk *h)
325 struct hblk * p = h - 1;
329 while (0 != phdr && IS_FORWARDING_ADDR_OR_NIL(phdr)) {
330 p = FORWARDED_ADDR(p,phdr);
334 if(HBLK_IS_FREE(phdr)) {
340 p = GC_prev_block(h - 1);
343 if (HBLK_IS_FREE(phdr) && (ptr_t)p + phdr -> hb_sz == (ptr_t)h) {
351 * Add hhdr to the appropriate free list.
352 * We maintain individual free lists sorted by address.
354 STATIC void GC_add_to_fl(struct hblk *h, hdr *hhdr)
356 int index = GC_hblk_fl_from_blocks(divHBLKSZ(hhdr -> hb_sz));
357 struct hblk *second = GC_hblkfreelist[index];
359 # if defined(GC_ASSERTIONS) && !defined(USE_MUNMAP)
360 struct hblk *next = (struct hblk *)((word)h + hhdr -> hb_sz);
361 hdr * nexthdr = HDR(next);
362 struct hblk *prev = GC_free_block_ending_at(h);
363 hdr * prevhdr = HDR(prev);
364 GC_ASSERT(nexthdr == 0 || !HBLK_IS_FREE(nexthdr)
365 || (signed_word)GC_heapsize < 0);
366 /* In the last case, blocks may be too large to merge. */
367 GC_ASSERT(prev == 0 || !HBLK_IS_FREE(prevhdr)
368 || (signed_word)GC_heapsize < 0);
370 GC_ASSERT(((hhdr -> hb_sz) & (HBLKSIZE-1)) == 0);
371 GC_hblkfreelist[index] = h;
372 INCR_FREE_BYTES(index, hhdr -> hb_sz);
373 FREE_ASSERT(GC_free_bytes[index] <= GC_large_free_bytes)
374 hhdr -> hb_next = second;
377 GET_HDR(second, second_hdr);
378 second_hdr -> hb_prev = h;
380 hhdr -> hb_flags |= FREE_BLK;
385 # ifndef MUNMAP_THRESHOLD
386 # define MUNMAP_THRESHOLD 6
389 GC_INNER int GC_unmap_threshold = MUNMAP_THRESHOLD;
391 /* Unmap blocks that haven't been recently touched. This is the only way */
392 /* way blocks are ever unmapped. */
393 GC_INNER void GC_unmap_old(void)
399 if (GC_unmap_threshold == 0)
400 return; /* unmapping disabled */
402 for (i = 0; i <= N_HBLK_FLS; ++i) {
403 for (h = GC_hblkfreelist[i]; 0 != h; h = hhdr -> hb_next) {
405 if (!IS_MAPPED(hhdr)) continue;
407 if ((unsigned short)GC_gc_no - hhdr -> hb_last_reclaimed >
408 (unsigned short)GC_unmap_threshold) {
409 GC_unmap((ptr_t)h, hhdr -> hb_sz);
410 hhdr -> hb_flags |= WAS_UNMAPPED;
416 /* Merge all unmapped blocks that are adjacent to other free */
417 /* blocks. This may involve remapping, since all blocks are either */
418 /* fully mapped or fully unmapped. */
419 GC_INNER void GC_merge_unmapped(void)
421 struct hblk * h, *next;
422 hdr * hhdr, *nexthdr;
426 for (i = 0; i <= N_HBLK_FLS; ++i) {
427 h = GC_hblkfreelist[i];
431 next = (struct hblk *)((word)h + size);
432 GET_HDR(next, nexthdr);
433 /* Coalesce with successor, if possible */
434 if (0 != nexthdr && HBLK_IS_FREE(nexthdr)
435 && (signed_word) (size + (nextsize = nexthdr->hb_sz)) > 0
436 /* no pot. overflow */) {
437 /* Note that we usually try to avoid adjacent free blocks */
438 /* that are either both mapped or both unmapped. But that */
439 /* isn't guaranteed to hold since we remap blocks when we */
440 /* split them, and don't merge at that point. It may also */
441 /* not hold if the merged block would be too big. */
442 if (IS_MAPPED(hhdr) && !IS_MAPPED(nexthdr)) {
443 /* make both consistent, so that we can merge */
444 if (size > nextsize) {
445 GC_remap((ptr_t)next, nextsize);
447 GC_unmap((ptr_t)h, size);
448 GC_unmap_gap((ptr_t)h, size, (ptr_t)next, nextsize);
449 hhdr -> hb_flags |= WAS_UNMAPPED;
451 } else if (IS_MAPPED(nexthdr) && !IS_MAPPED(hhdr)) {
452 if (size > nextsize) {
453 GC_unmap((ptr_t)next, nextsize);
454 GC_unmap_gap((ptr_t)h, size, (ptr_t)next, nextsize);
456 GC_remap((ptr_t)h, size);
457 hhdr -> hb_flags &= ~WAS_UNMAPPED;
458 hhdr -> hb_last_reclaimed = nexthdr -> hb_last_reclaimed;
460 } else if (!IS_MAPPED(hhdr) && !IS_MAPPED(nexthdr)) {
461 /* Unmap any gap in the middle */
462 GC_unmap_gap((ptr_t)h, size, (ptr_t)next, nextsize);
464 /* If they are both unmapped, we merge, but leave unmapped. */
465 GC_remove_from_fl(hhdr, i);
466 GC_remove_from_fl(nexthdr, FL_UNKNOWN);
467 hhdr -> hb_sz += nexthdr -> hb_sz;
468 GC_remove_header(next);
469 GC_add_to_fl(h, hhdr);
470 /* Start over at beginning of list */
471 h = GC_hblkfreelist[i];
472 } else /* not mergable with successor */ {
475 } /* while (h != 0) ... */
479 #endif /* USE_MUNMAP */
482 * Return a pointer to a block starting at h of length bytes.
483 * Memory for the block is mapped.
484 * Remove the block from its free list, and return the remainder (if any)
485 * to its appropriate free list.
486 * May fail by returning 0.
487 * The header for the returned block must be set up by the caller.
488 * If the return value is not 0, then hhdr is the header for it.
490 STATIC struct hblk * GC_get_first_part(struct hblk *h, hdr *hhdr,
491 size_t bytes, int index)
493 word total_size = hhdr -> hb_sz;
497 GC_ASSERT((total_size & (HBLKSIZE-1)) == 0);
498 GC_remove_from_fl(hhdr, index);
499 if (total_size == bytes) return h;
500 rest = (struct hblk *)((word)h + bytes);
501 rest_hdr = GC_install_header(rest);
503 /* FIXME: This is likely to be very bad news ... */
504 WARN("Header allocation failed: Dropping block.\n", 0);
507 rest_hdr -> hb_sz = total_size - bytes;
508 rest_hdr -> hb_flags = 0;
509 # ifdef GC_ASSERTIONS
510 /* Mark h not free, to avoid assertion about adjacent free blocks. */
511 hhdr -> hb_flags &= ~FREE_BLK;
513 GC_add_to_fl(rest, rest_hdr);
518 * H is a free block. N points at an address inside it.
519 * A new header for n has already been set up. Fix up h's header
520 * to reflect the fact that it is being split, move it to the
521 * appropriate free list.
522 * N replaces h in the original free list.
524 * Nhdr is not completely filled in, since it is about to allocated.
525 * It may in fact end up on the wrong free list for its size.
526 * That's not a disaster, since n is about to be allocated
528 * (Hence adding it to a free list is silly. But this path is hopefully
529 * rare enough that it doesn't matter. The code is cleaner this way.)
531 STATIC void GC_split_block(struct hblk *h, hdr *hhdr, struct hblk *n,
532 hdr *nhdr, int index /* Index of free list */)
534 word total_size = hhdr -> hb_sz;
535 word h_size = (word)n - (word)h;
536 struct hblk *prev = hhdr -> hb_prev;
537 struct hblk *next = hhdr -> hb_next;
539 /* Replace h with n on its freelist */
540 nhdr -> hb_prev = prev;
541 nhdr -> hb_next = next;
542 nhdr -> hb_sz = total_size - h_size;
543 nhdr -> hb_flags = 0;
545 HDR(prev) -> hb_next = n;
547 GC_hblkfreelist[index] = n;
550 HDR(next) -> hb_prev = n;
552 INCR_FREE_BYTES(index, -(signed_word)h_size);
553 FREE_ASSERT(GC_free_bytes[index] > 0);
555 hhdr -> hb_last_reclaimed = (unsigned short)GC_gc_no;
557 hhdr -> hb_sz = h_size;
558 GC_add_to_fl(h, hhdr);
559 nhdr -> hb_flags |= FREE_BLK;
563 GC_allochblk_nth(size_t sz/* bytes */, int kind, unsigned flags, int n,
567 * Allocate (and return pointer to) a heap block
568 * for objects of size sz bytes, searching the nth free list.
570 * NOTE: We set obj_map field in header correctly.
571 * Caller is responsible for building an object freelist in block.
573 * The client is responsible for clearing the block, if necessary.
575 GC_INNER struct hblk *
576 GC_allochblk(size_t sz, int kind, unsigned flags/* IGNORE_OFF_PAGE or 0 */)
582 int split_limit; /* Highest index of free list whose blocks we */
585 GC_ASSERT((sz & (GRANULE_BYTES - 1)) == 0);
586 blocks = OBJ_SZ_TO_BLOCKS(sz);
587 if ((signed_word)(blocks * HBLKSIZE) < 0) {
590 start_list = GC_hblk_fl_from_blocks(blocks);
591 /* Try for an exact match first. */
592 result = GC_allochblk_nth(sz, kind, flags, start_list, FALSE);
593 if (0 != result) return result;
594 if (GC_use_entire_heap || GC_dont_gc
595 || USED_HEAP_SIZE < GC_requested_heapsize
596 || GC_incremental || !GC_should_collect()) {
597 /* Should use more of the heap, even if it requires splitting. */
598 split_limit = N_HBLK_FLS;
601 /* avoid splitting, since that might require remapping */
604 if (GC_finalizer_bytes_freed > (GC_heapsize >> 4)) {
605 /* If we are deallocating lots of memory from */
606 /* finalizers, fail and collect sooner rather */
610 /* If we have enough large blocks left to cover any */
611 /* previous request for large blocks, we go ahead */
612 /* and split. Assuming a steady state, that should */
613 /* be safe. It means that we can use the full */
614 /* heap if we allocate only small objects. */
615 split_limit = GC_enough_large_bytes_left();
619 if (start_list < UNIQUE_THRESHOLD) {
620 /* No reason to try start_list again, since all blocks are exact */
624 for (i = start_list; i <= split_limit; ++i) {
625 struct hblk * result = GC_allochblk_nth(sz, kind, flags, i, TRUE);
626 if (0 != result) return result;
631 STATIC long GC_large_alloc_warn_suppressed = 0;
632 /* Number of warnings suppressed so far. */
635 * The same, but with search restricted to nth free list.
636 * Flags is IGNORE_OFF_PAGE or zero.
637 * Unlike the above, sz is in bytes.
638 * The may_split flag indicates whether it's OK to split larger blocks.
641 GC_allochblk_nth(size_t sz, int kind, unsigned flags, int n,
645 hdr * hhdr; /* Header corr. to hbp */
646 /* Initialized after loop if hbp !=0 */
647 /* Gcc uninitialized use warning is bogus. */
648 struct hblk *thishbp;
649 hdr * thishdr; /* Header corr. to hbp */
650 signed_word size_needed; /* number of bytes in requested objects */
651 signed_word size_avail; /* bytes available in this block */
653 size_needed = HBLKSIZE * OBJ_SZ_TO_BLOCKS(sz);
655 /* search for a big enough block in free list */
656 hbp = GC_hblkfreelist[n];
657 for(; 0 != hbp; hbp = hhdr -> hb_next) {
659 size_avail = hhdr->hb_sz;
660 if (size_avail < size_needed) continue;
661 if (size_avail != size_needed) {
662 signed_word next_size;
664 if (!may_split) continue;
665 /* If the next heap block is obviously better, go on. */
666 /* This prevents us from disassembling a single large block */
667 /* to get tiny blocks. */
668 thishbp = hhdr -> hb_next;
670 GET_HDR(thishbp, thishdr);
671 next_size = (signed_word)(thishdr -> hb_sz);
672 if (next_size < size_avail
673 && next_size >= size_needed
674 && !GC_is_black_listed(thishbp, (word)size_needed)) {
679 if ( !IS_UNCOLLECTABLE(kind) &&
680 (kind != PTRFREE || size_needed > MAX_BLACK_LIST_ALLOC)) {
681 struct hblk * lasthbp = hbp;
682 ptr_t search_end = (ptr_t)hbp + size_avail - size_needed;
683 signed_word orig_avail = size_avail;
684 signed_word eff_size_needed = ((flags & IGNORE_OFF_PAGE)?
689 while ((ptr_t)lasthbp <= search_end
690 && (thishbp = GC_is_black_listed(lasthbp,
691 (word)eff_size_needed))
695 size_avail -= (ptr_t)lasthbp - (ptr_t)hbp;
697 if (size_avail >= size_needed) {
698 if (thishbp != hbp &&
699 0 != (thishdr = GC_install_header(thishbp))) {
700 /* Make sure it's mapped before we mangle it. */
702 if (!IS_MAPPED(hhdr)) {
703 GC_remap((ptr_t)hbp, hhdr -> hb_sz);
704 hhdr -> hb_flags &= ~WAS_UNMAPPED;
707 /* Split the block at thishbp */
708 GC_split_block(hbp, hhdr, thishbp, thishdr, n);
709 /* Advance to thishbp */
712 /* We must now allocate thishbp, since it may */
713 /* be on the wrong free list. */
715 } else if (size_needed > (signed_word)BL_LIMIT
716 && orig_avail - size_needed
717 > (signed_word)BL_LIMIT) {
718 /* Punt, since anything else risks unreasonable heap growth. */
719 if (++GC_large_alloc_warn_suppressed
720 >= GC_large_alloc_warn_interval) {
721 WARN("Repeated allocation of very large block "
722 "(appr. size %" GC_PRIdPTR "):\n"
723 "\tMay lead to memory leak and poor performance.\n",
725 GC_large_alloc_warn_suppressed = 0;
727 size_avail = orig_avail;
728 } else if (size_avail == 0 && size_needed == HBLKSIZE
729 && IS_MAPPED(hhdr)) {
731 static unsigned count = 0;
733 /* The block is completely blacklisted. We need */
734 /* to drop some such blocks, since otherwise we spend */
735 /* all our time traversing them if pointerfree */
736 /* blocks are unpopular. */
737 /* A dropped block will be reconsidered at next GC. */
738 if ((++count & 3) == 0) {
739 /* Allocate and drop the block in small chunks, to */
740 /* maximize the chance that we will recover some */
742 word total_size = hhdr -> hb_sz;
743 struct hblk * limit = hbp + divHBLKSZ(total_size);
745 struct hblk * prev = hhdr -> hb_prev;
747 GC_large_free_bytes -= total_size;
748 GC_bytes_dropped += total_size;
749 GC_remove_from_fl(hhdr, n);
750 for (h = hbp; h < limit; h++) {
751 if (h == hbp || 0 != (hhdr = GC_install_header(h))) {
755 PTRFREE, 0); /* Can't fail */
756 if (GC_debugging_started) {
761 /* Restore hbp to point at free block */
764 return GC_allochblk_nth(sz, kind, flags, n, may_split);
771 if( size_avail >= size_needed ) {
773 if (!IS_MAPPED(hhdr)) {
774 GC_remap((ptr_t)hbp, hhdr -> hb_sz);
775 hhdr -> hb_flags &= ~WAS_UNMAPPED;
776 /* Note: This may leave adjacent, mapped free blocks. */
779 /* hbp may be on the wrong freelist; the parameter n */
781 hbp = GC_get_first_part(hbp, hhdr, size_needed, n);
786 if (0 == hbp) return 0;
788 /* Add it to map of valid blocks */
789 if (!GC_install_counts(hbp, (word)size_needed)) return(0);
790 /* This leaks memory under very rare conditions. */
793 if (!setup_header(hhdr, hbp, sz, kind, flags)) {
794 GC_remove_counts(hbp, (word)size_needed);
795 return(0); /* ditto */
798 /* Notify virtual dirty bit implementation that we are about to write. */
799 /* Ensure that pointerfree objects are not protected if it's avoidable. */
800 /* This also ensures that newly allocated blocks are treated as dirty. */
801 /* Necessary since we don't protect free blocks. */
802 GC_ASSERT((size_needed & (HBLKSIZE-1)) == 0);
803 GC_remove_protection(hbp, divHBLKSZ(size_needed),
804 (hhdr -> hb_descr == 0) /* pointer-free */);
806 /* We just successfully allocated a block. Restart count of */
807 /* consecutive failures. */
810 GC_large_free_bytes -= size_needed;
812 GC_ASSERT(IS_MAPPED(hhdr));
819 * Coalesce the block with its neighbors if possible.
821 * All mark words are assumed to be cleared.
823 GC_INNER void GC_freehblk(struct hblk *hbp)
825 struct hblk *next, *prev;
826 hdr *hhdr, *prevhdr, *nexthdr;
831 size = HBLKSIZE * OBJ_SZ_TO_BLOCKS(size);
833 ABORT("Deallocating excessively large block. Too large an allocation?");
834 /* Probably possible if we try to allocate more than half the address */
835 /* space at once. If we don't catch it here, strange things happen */
837 GC_remove_counts(hbp, (word)size);
840 hhdr -> hb_last_reclaimed = (unsigned short)GC_gc_no;
843 /* Check for duplicate deallocation in the easy case */
844 if (HBLK_IS_FREE(hhdr)) {
845 GC_printf("Duplicate large block deallocation of %p\n", hbp);
846 ABORT("Duplicate large block deallocation");
849 GC_ASSERT(IS_MAPPED(hhdr));
850 hhdr -> hb_flags |= FREE_BLK;
851 next = (struct hblk *)((word)hbp + size);
852 GET_HDR(next, nexthdr);
853 prev = GC_free_block_ending_at(hbp);
854 /* Coalesce with successor, if possible */
855 if(0 != nexthdr && HBLK_IS_FREE(nexthdr) && IS_MAPPED(nexthdr)
856 && (signed_word)(hhdr -> hb_sz + nexthdr -> hb_sz) > 0
858 GC_remove_from_fl(nexthdr, FL_UNKNOWN);
859 hhdr -> hb_sz += nexthdr -> hb_sz;
860 GC_remove_header(next);
862 /* Coalesce with predecessor, if possible. */
865 if (IS_MAPPED(prevhdr)
866 && (signed_word)(hhdr -> hb_sz + prevhdr -> hb_sz) > 0) {
867 GC_remove_from_fl(prevhdr, FL_UNKNOWN);
868 prevhdr -> hb_sz += hhdr -> hb_sz;
870 prevhdr -> hb_last_reclaimed = (unsigned short)GC_gc_no;
872 GC_remove_header(hbp);
877 /* FIXME: It is not clear we really always want to do these merges */
878 /* with USE_MUNMAP, since it updates ages and hence prevents */
881 GC_large_free_bytes += size;
882 GC_add_to_fl(hbp, hhdr);