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.
21 #include "private/gc_priv.h"
23 GC_bool GC_use_entire_heap = 0;
26 * Free heap blocks are kept on one of several free lists,
27 * depending on the size of the block. Each free list is doubly linked.
28 * Adjacent free blocks are coalesced.
32 # define MAX_BLACK_LIST_ALLOC (2*HBLKSIZE)
33 /* largest block we will allocate starting on a black */
34 /* listed block. Must be >= HBLKSIZE. */
37 # define UNIQUE_THRESHOLD 32
38 /* Sizes up to this many HBLKs each have their own free list */
39 # define HUGE_THRESHOLD 256
40 /* Sizes of at least this many heap blocks are mapped to a */
41 /* single free list. */
42 # define FL_COMPRESSION 8
43 /* In between sizes map this many distinct sizes to a single */
46 # define N_HBLK_FLS (HUGE_THRESHOLD - UNIQUE_THRESHOLD)/FL_COMPRESSION \
49 struct hblk * GC_hblkfreelist[N_HBLK_FLS+1] = { 0 };
53 word GC_free_bytes[N_HBLK_FLS+1] = { 0 };
54 /* Number of free bytes on each list. */
56 /* Return the largest n such that */
57 /* Is GC_large_allocd_bytes + the number of free bytes on lists */
58 /* n .. N_HBLK_FLS > GC_max_large_allocd_bytes. */
59 /* If there is no such n, return 0. */
63 static int GC_enough_large_bytes_left(void)
66 word bytes = GC_large_allocd_bytes;
68 GC_ASSERT(GC_max_large_allocd_bytes <= GC_heapsize);
69 for (n = N_HBLK_FLS; n >= 0; --n) {
70 bytes += GC_free_bytes[n];
71 if (bytes >= GC_max_large_allocd_bytes) return n;
76 # define INCR_FREE_BYTES(n, b) GC_free_bytes[n] += (b);
78 # define FREE_ASSERT(e) GC_ASSERT(e)
80 #else /* USE_MUNMAP */
82 # define INCR_FREE_BYTES(n, b)
83 # define FREE_ASSERT(e)
85 #endif /* USE_MUNMAP */
87 /* Map a number of blocks to the appropriate large block free list index. */
88 int GC_hblk_fl_from_blocks(word blocks_needed)
90 if (blocks_needed <= UNIQUE_THRESHOLD) return (int)blocks_needed;
91 if (blocks_needed >= HUGE_THRESHOLD) return N_HBLK_FLS;
92 return (int)(blocks_needed - UNIQUE_THRESHOLD)/FL_COMPRESSION
97 # define PHDR(hhdr) HDR(hhdr -> hb_prev)
98 # define NHDR(hhdr) HDR(hhdr -> hb_next)
101 # define IS_MAPPED(hhdr) (((hhdr) -> hb_flags & WAS_UNMAPPED) == 0)
102 # else /* !USE_MMAP */
103 # define IS_MAPPED(hhdr) 1
104 # endif /* USE_MUNMAP */
106 # if !defined(NO_DEBUGGING)
107 void GC_print_hblkfreelist()
115 for (i = 0; i <= N_HBLK_FLS; ++i) {
116 h = GC_hblkfreelist[i];
118 if (0 != h) GC_printf("Free list %ld:\n",
121 if (0 != h) GC_printf("Free list %lu (Total size %lu):\n",
122 i, (unsigned long)GC_free_bytes[i]);
127 GC_printf("\t%p size %lu ", h, (unsigned long)sz);
129 if (GC_is_black_listed(h, HBLKSIZE) != 0) {
130 GC_printf("start black listed\n");
131 } else if (GC_is_black_listed(h, hhdr -> hb_sz) != 0) {
132 GC_printf("partially black listed\n");
134 GC_printf("not black listed\n");
140 if (total_free != GC_large_free_bytes) {
141 GC_printf("GC_large_free_bytes = %lu (INCONSISTENT!!)\n",
142 (unsigned long) GC_large_free_bytes);
145 GC_printf("Total of %lu bytes on free list\n", (unsigned long)total_free);
148 /* Return the free list index on which the block described by the header */
149 /* appears, or -1 if it appears nowhere. */
150 int free_list_index_of(hdr *wanted)
156 for (i = 0; i <= N_HBLK_FLS; ++i) {
157 h = GC_hblkfreelist[i];
160 if (hhdr == wanted) return i;
167 void GC_dump_regions()
174 for (i = 0; i < GC_n_heap_sects; ++i) {
175 start = GC_heap_sects[i].hs_start;
176 bytes = GC_heap_sects[i].hs_bytes;
178 /* Merge in contiguous sections. */
179 while (i+1 < GC_n_heap_sects && GC_heap_sects[i+1].hs_start == end) {
181 end = GC_heap_sects[i].hs_start + GC_heap_sects[i].hs_bytes;
183 GC_printf("***Section from %p to %p\n", start, end);
184 for (p = start; p < end;) {
186 GC_printf("\t%p ", p);
187 if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) {
188 GC_printf("Missing header!!(%d)\n", hhdr);
192 if (HBLK_IS_FREE(hhdr)) {
193 int correct_index = GC_hblk_fl_from_blocks(
194 divHBLKSZ(hhdr -> hb_sz));
197 GC_printf("\tfree block of size 0x%lx bytes",
198 (unsigned long)(hhdr -> hb_sz));
199 if (IS_MAPPED(hhdr)) {
202 GC_printf("(unmapped)\n");
204 actual_index = free_list_index_of(hhdr);
205 if (-1 == actual_index) {
206 GC_printf("\t\tBlock not on free list %d!!\n",
208 } else if (correct_index != actual_index) {
209 GC_printf("\t\tBlock on list %d, should be on %d!!\n",
210 actual_index, correct_index);
214 GC_printf("\tused for blocks of size 0x%lx bytes\n",
215 (unsigned long)(hhdr -> hb_sz));
216 p += HBLKSIZE * OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz);
222 # endif /* NO_DEBUGGING */
224 /* Initialize hdr for a block containing the indicated size and */
225 /* kind of objects. */
226 /* Return FALSE on failure. */
227 static GC_bool setup_header(hdr * hhdr, struct hblk *block, size_t byte_sz,
228 int kind, unsigned flags)
233 /* Set size, kind and mark proc fields */
234 hhdr -> hb_sz = byte_sz;
235 hhdr -> hb_obj_kind = (unsigned char)kind;
236 hhdr -> hb_flags = (unsigned char)flags;
237 hhdr -> hb_block = block;
238 descr = GC_obj_kinds[kind].ok_descriptor;
239 if (GC_obj_kinds[kind].ok_relocate_descr) descr += byte_sz;
240 hhdr -> hb_descr = descr;
242 # ifdef MARK_BIT_PER_OBJ
243 /* Set hb_inv_sz as portably as possible. */
244 /* We set it to the smallest value such that sz * inv_sz > 2**32 */
245 /* This may be more precision than necessary. */
246 if (byte_sz > MAXOBJBYTES) {
247 hhdr -> hb_inv_sz = LARGE_INV_SZ;
251 # if CPP_WORDSZ == 64
252 inv_sz = ((word)1 << 32)/byte_sz;
253 if (((inv_sz*byte_sz) >> 32) == 0) ++inv_sz;
254 # else /* 32 bit words */
255 GC_ASSERT(byte_sz >= 4);
256 inv_sz = ((unsigned)1 << 31)/byte_sz;
258 while (inv_sz*byte_sz > byte_sz) ++inv_sz;
260 hhdr -> hb_inv_sz = inv_sz;
262 # else /* MARK_BIT_PER_GRANULE */
263 hhdr -> hb_large_block = (unsigned char)(byte_sz > MAXOBJBYTES);
264 granules = BYTES_TO_GRANULES(byte_sz);
265 if (EXPECT(!GC_add_map_entry(granules), FALSE)) {
266 /* Make it look like a valid block. */
267 hhdr -> hb_sz = HBLKSIZE;
268 hhdr -> hb_descr = 0;
269 hhdr -> hb_large_block = TRUE;
273 size_t index = (hhdr -> hb_large_block? 0 : granules);
274 hhdr -> hb_map = GC_obj_map[index];
276 # endif /* MARK_BIT_PER_GRANULE */
278 /* Clear mark bits */
279 GC_clear_hdr_marks(hhdr);
281 hhdr -> hb_last_reclaimed = (unsigned short)GC_gc_no;
285 #define FL_UNKNOWN -1
287 * Remove hhdr from the appropriate free list.
288 * We assume it is on the nth free list, or on the size
289 * appropriate free list if n is FL_UNKNOWN.
291 void GC_remove_from_fl(hdr *hhdr, int n)
295 GC_ASSERT(((hhdr -> hb_sz) & (HBLKSIZE-1)) == 0);
297 /* We always need index to mainatin free counts. */
298 if (FL_UNKNOWN == n) {
299 index = GC_hblk_fl_from_blocks(divHBLKSZ(hhdr -> hb_sz));
304 if (hhdr -> hb_prev == 0) {
306 if (FL_UNKNOWN == n) {
307 index = GC_hblk_fl_from_blocks(divHBLKSZ(hhdr -> hb_sz));
312 GC_ASSERT(HDR(GC_hblkfreelist[index]) == hhdr);
313 GC_hblkfreelist[index] = hhdr -> hb_next;
316 GET_HDR(hhdr -> hb_prev, phdr);
317 phdr -> hb_next = hhdr -> hb_next;
319 FREE_ASSERT(GC_free_bytes[index] >= hhdr -> hb_sz);
320 INCR_FREE_BYTES(index, - (signed_word)(hhdr -> hb_sz));
321 if (0 != hhdr -> hb_next) {
323 GC_ASSERT(!IS_FORWARDING_ADDR_OR_NIL(NHDR(hhdr)));
324 GET_HDR(hhdr -> hb_next, nhdr);
325 nhdr -> hb_prev = hhdr -> hb_prev;
330 * Return a pointer to the free block ending just before h, if any.
332 struct hblk * GC_free_block_ending_at(struct hblk *h)
334 struct hblk * p = h - 1;
338 while (0 != phdr && IS_FORWARDING_ADDR_OR_NIL(phdr)) {
339 p = FORWARDED_ADDR(p,phdr);
343 if(HBLK_IS_FREE(phdr)) {
349 p = GC_prev_block(h - 1);
352 if (HBLK_IS_FREE(phdr) && (ptr_t)p + phdr -> hb_sz == (ptr_t)h) {
360 * Add hhdr to the appropriate free list.
361 * We maintain individual free lists sorted by address.
363 void GC_add_to_fl(struct hblk *h, hdr *hhdr)
365 int index = GC_hblk_fl_from_blocks(divHBLKSZ(hhdr -> hb_sz));
366 struct hblk *second = GC_hblkfreelist[index];
368 # if defined(GC_ASSERTIONS) && !defined(USE_MUNMAP)
369 struct hblk *next = (struct hblk *)((word)h + hhdr -> hb_sz);
370 hdr * nexthdr = HDR(next);
371 struct hblk *prev = GC_free_block_ending_at(h);
372 hdr * prevhdr = HDR(prev);
373 GC_ASSERT(nexthdr == 0 || !HBLK_IS_FREE(nexthdr)
374 || (signed_word)GC_heapsize < 0);
375 /* In the last case, blocks may be too large to merge. */
376 GC_ASSERT(prev == 0 || !HBLK_IS_FREE(prevhdr)
377 || (signed_word)GC_heapsize < 0);
379 GC_ASSERT(((hhdr -> hb_sz) & (HBLKSIZE-1)) == 0);
380 GC_hblkfreelist[index] = h;
381 INCR_FREE_BYTES(index, hhdr -> hb_sz);
382 FREE_ASSERT(GC_free_bytes[index] <= GC_large_free_bytes)
383 hhdr -> hb_next = second;
386 GET_HDR(second, second_hdr);
387 second_hdr -> hb_prev = h;
389 hhdr -> hb_flags |= FREE_BLK;
394 /* Unmap blocks that haven't been recently touched. This is the only way */
395 /* way blocks are ever unmapped. */
396 void GC_unmap_old(void)
401 unsigned short last_rec, threshold;
403 # ifndef MUNMAP_THRESHOLD
404 # define MUNMAP_THRESHOLD 6
407 for (i = 0; i <= N_HBLK_FLS; ++i) {
408 for (h = GC_hblkfreelist[i]; 0 != h; h = hhdr -> hb_next) {
410 if (!IS_MAPPED(hhdr)) continue;
411 threshold = (unsigned short)(GC_gc_no - MUNMAP_THRESHOLD);
412 last_rec = hhdr -> hb_last_reclaimed;
413 if ((last_rec > GC_gc_no || last_rec < threshold)
414 && threshold < GC_gc_no /* not recently wrapped */) {
416 GC_unmap((ptr_t)h, sz);
417 hhdr -> hb_flags |= WAS_UNMAPPED;
423 /* Merge all unmapped blocks that are adjacent to other free */
424 /* blocks. This may involve remapping, since all blocks are either */
425 /* fully mapped or fully unmapped. */
426 void GC_merge_unmapped(void)
428 struct hblk * h, *next;
429 hdr * hhdr, *nexthdr;
433 for (i = 0; i <= N_HBLK_FLS; ++i) {
434 h = GC_hblkfreelist[i];
438 next = (struct hblk *)((word)h + size);
439 GET_HDR(next, nexthdr);
440 /* Coalesce with successor, if possible */
441 if (0 != nexthdr && HBLK_IS_FREE(nexthdr)
442 && (signed_word) (size + (nextsize = nexthdr->hb_sz)) > 0
443 /* no pot. overflow */) {
444 if (IS_MAPPED(hhdr)) {
445 GC_ASSERT(!IS_MAPPED(nexthdr));
446 /* make both consistent, so that we can merge */
447 if (size > nextsize) {
448 GC_remap((ptr_t)next, nextsize);
450 GC_unmap((ptr_t)h, size);
451 hhdr -> hb_flags |= WAS_UNMAPPED;
453 } else if (IS_MAPPED(nexthdr)) {
454 GC_ASSERT(!IS_MAPPED(hhdr));
455 if (size > nextsize) {
456 GC_unmap((ptr_t)next, nextsize);
458 GC_remap((ptr_t)h, size);
459 hhdr -> hb_flags &= ~WAS_UNMAPPED;
460 hhdr -> hb_last_reclaimed = nexthdr -> hb_last_reclaimed;
463 /* Unmap any gap in the middle */
464 GC_unmap_gap((ptr_t)h, size, (ptr_t)next, nexthdr -> hb_sz);
466 /* If they are both unmapped, we merge, but leave unmapped. */
467 GC_remove_from_fl(hhdr, i);
468 GC_remove_from_fl(nexthdr, FL_UNKNOWN);
469 hhdr -> hb_sz += nexthdr -> hb_sz;
470 GC_remove_header(next);
471 GC_add_to_fl(h, hhdr);
472 /* Start over at beginning of list */
473 h = GC_hblkfreelist[i];
474 } else /* not mergable with successor */ {
477 } /* while (h != 0) ... */
481 #endif /* USE_MUNMAP */
484 * Return a pointer to a block starting at h of length bytes.
485 * Memory for the block is mapped.
486 * Remove the block from its free list, and return the remainder (if any)
487 * to its appropriate free list.
488 * May fail by returning 0.
489 * The header for the returned block must be set up by the caller.
490 * If the return value is not 0, then hhdr is the header for it.
492 struct hblk * GC_get_first_part(struct hblk *h, hdr *hhdr,
493 size_t bytes, int index)
495 word total_size = hhdr -> hb_sz;
499 GC_ASSERT((total_size & (HBLKSIZE-1)) == 0);
500 GC_remove_from_fl(hhdr, index);
501 if (total_size == bytes) return h;
502 rest = (struct hblk *)((word)h + bytes);
503 rest_hdr = GC_install_header(rest);
505 /* FIXME: This is likely to be very bad news ... */
506 WARN("Header allocation failed: Dropping block.\n", 0);
509 rest_hdr -> hb_sz = total_size - bytes;
510 rest_hdr -> hb_flags = 0;
511 # ifdef GC_ASSERTIONS
512 /* Mark h not free, to avoid assertion about adjacent free blocks. */
513 hhdr -> hb_flags &= ~FREE_BLK;
515 GC_add_to_fl(rest, rest_hdr);
520 * H is a free block. N points at an address inside it.
521 * A new header for n has already been set up. Fix up h's header
522 * to reflect the fact that it is being split, move it to the
523 * appropriate free list.
524 * N replaces h in the original free list.
526 * Nhdr is not completely filled in, since it is about to allocated.
527 * It may in fact end up on the wrong free list for its size.
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 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);
554 # ifdef GC_ASSERTIONS
555 nhdr -> hb_flags &= ~FREE_BLK;
556 /* Don't fail test for consecutive */
557 /* free blocks in GC_add_to_fl. */
560 hhdr -> hb_last_reclaimed = (unsigned short)GC_gc_no;
562 hhdr -> hb_sz = h_size;
563 GC_add_to_fl(h, hhdr);
564 nhdr -> hb_flags |= FREE_BLK;
568 GC_allochblk_nth(size_t sz/* bytes */, int kind, unsigned flags, int n,
572 * Allocate (and return pointer to) a heap block
573 * for objects of size sz bytes, searching the nth free list.
575 * NOTE: We set obj_map field in header correctly.
576 * Caller is responsible for building an object freelist in block.
578 * The client is responsible for clearing the block, if necessary.
581 GC_allochblk(size_t sz, int kind, unsigned flags/* IGNORE_OFF_PAGE or 0 */)
587 int split_limit; /* Highest index of free list whose blocks we */
590 GC_ASSERT((sz & (GRANULE_BYTES - 1)) == 0);
591 blocks = OBJ_SZ_TO_BLOCKS(sz);
592 if ((signed_word)(blocks * HBLKSIZE) < 0) {
595 start_list = GC_hblk_fl_from_blocks(blocks);
596 /* Try for an exact match first. */
597 result = GC_allochblk_nth(sz, kind, flags, start_list, FALSE);
598 if (0 != result) return result;
599 if (GC_use_entire_heap || GC_dont_gc
600 || USED_HEAP_SIZE < GC_requested_heapsize
601 || TRUE_INCREMENTAL || !GC_should_collect()) {
602 /* Should use more of the heap, even if it requires splitting. */
603 split_limit = N_HBLK_FLS;
606 /* avoid splitting, since that might require remapping */
609 if (GC_finalizer_bytes_freed > (GC_heapsize >> 4)) {
610 /* If we are deallocating lots of memory from */
611 /* finalizers, fail and collect sooner rather */
615 /* If we have enough large blocks left to cover any */
616 /* previous request for large blocks, we go ahead */
617 /* and split. Assuming a steady state, that should */
618 /* be safe. It means that we can use the full */
619 /* heap if we allocate only small objects. */
620 split_limit = GC_enough_large_bytes_left();
624 if (start_list < UNIQUE_THRESHOLD) {
625 /* No reason to try start_list again, since all blocks are exact */
629 for (i = start_list; i <= split_limit; ++i) {
630 struct hblk * result = GC_allochblk_nth(sz, kind, flags, i, TRUE);
631 if (0 != result) return result;
636 * The same, but with search restricted to nth free list.
637 * Flags is IGNORE_OFF_PAGE or zero.
638 * Unlike the above, sz is in bytes.
639 * The may_split flag indicates whether it's OK to split larger blocks.
642 GC_allochblk_nth(size_t sz, int kind, unsigned flags, int n, GC_bool may_split)
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 %ld):\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); /* Cant 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 GC_remove_protection(hbp, divHBLKSZ(size_needed),
801 (hhdr -> hb_descr == 0) /* pointer-free */);
803 /* We just successfully allocated a block. Restart count of */
804 /* consecutive failures. */
806 extern unsigned GC_fail_count;
811 GC_large_free_bytes -= size_needed;
813 GC_ASSERT(IS_MAPPED(hhdr));
817 struct hblk * GC_freehblk_ptr = 0; /* Search position hint for GC_freehblk */
822 * Coalesce the block with its neighbors if possible.
824 * All mark words are assumed to be cleared.
827 GC_freehblk(struct hblk *hbp)
829 struct hblk *next, *prev;
830 hdr *hhdr, *prevhdr, *nexthdr;
836 size = HBLKSIZE * OBJ_SZ_TO_BLOCKS(size);
838 ABORT("Deallocating excessively large block. Too large an allocation?");
839 /* Probably possible if we try to allocate more than half the address */
840 /* space at once. If we dont catch it here, strange things happen */
842 GC_remove_counts(hbp, (word)size);
845 hhdr -> hb_last_reclaimed = (unsigned short)GC_gc_no;
848 /* Check for duplicate deallocation in the easy case */
849 if (HBLK_IS_FREE(hhdr)) {
850 GC_printf("Duplicate large block deallocation of %p\n", hbp);
851 ABORT("Duplicate large block deallocation");
854 GC_ASSERT(IS_MAPPED(hhdr));
855 hhdr -> hb_flags |= FREE_BLK;
856 next = (struct hblk *)((word)hbp + size);
857 GET_HDR(next, nexthdr);
858 prev = GC_free_block_ending_at(hbp);
859 /* Coalesce with successor, if possible */
860 if(0 != nexthdr && HBLK_IS_FREE(nexthdr) && IS_MAPPED(nexthdr)
861 && (signed_word)(hhdr -> hb_sz + nexthdr -> hb_sz) > 0
863 GC_remove_from_fl(nexthdr, FL_UNKNOWN);
864 hhdr -> hb_sz += nexthdr -> hb_sz;
865 GC_remove_header(next);
867 /* Coalesce with predecessor, if possible. */
870 if (IS_MAPPED(prevhdr)
871 && (signed_word)(hhdr -> hb_sz + prevhdr -> hb_sz) > 0) {
872 GC_remove_from_fl(prevhdr, FL_UNKNOWN);
873 prevhdr -> hb_sz += hhdr -> hb_sz;
875 prevhdr -> hb_last_reclaimed = (unsigned short)GC_gc_no;
877 GC_remove_header(hbp);
882 /* FIXME: It is not clear we really always want to do these merges */
883 /* with -DUSE_MUNMAP, since it updates ages and hence prevents */
886 GC_large_free_bytes += size;
887 GC_add_to_fl(hbp, hhdr);