Mercurial > emacs
diff gc/allchblk.c @ 51488:5de98dce4bd1
*** empty log message ***
author | Dave Love <fx@gnu.org> |
---|---|
date | Thu, 05 Jun 2003 17:49:22 +0000 |
parents | |
children |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/gc/allchblk.c Thu Jun 05 17:49:22 2003 +0000 @@ -0,0 +1,821 @@ +/* + * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers + * Copyright (c) 1991-1994 by Xerox Corporation. All rights reserved. + * Copyright (c) 1998-1999 by Silicon Graphics. All rights reserved. + * Copyright (c) 1999 by Hewlett-Packard Company. All rights reserved. + * + * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED + * OR IMPLIED. ANY USE IS AT YOUR OWN RISK. + * + * Permission is hereby granted to use or copy this program + * for any purpose, provided the above notices are retained on all copies. + * Permission to modify the code and to distribute modified code is granted, + * provided the above notices are retained, and a notice that the code was + * modified is included with the above copyright notice. + */ + +/* #define DEBUG */ +#include <stdio.h> +#include "private/gc_priv.h" + +GC_bool GC_use_entire_heap = 0; + +/* + * Free heap blocks are kept on one of several free lists, + * depending on the size of the block. Each free list is doubly linked. + * Adjacent free blocks are coalesced. + */ + + +# define MAX_BLACK_LIST_ALLOC (2*HBLKSIZE) + /* largest block we will allocate starting on a black */ + /* listed block. Must be >= HBLKSIZE. */ + + +# define UNIQUE_THRESHOLD 32 + /* Sizes up to this many HBLKs each have their own free list */ +# define HUGE_THRESHOLD 256 + /* Sizes of at least this many heap blocks are mapped to a */ + /* single free list. */ +# define FL_COMPRESSION 8 + /* In between sizes map this many distinct sizes to a single */ + /* bin. */ + +# define N_HBLK_FLS (HUGE_THRESHOLD - UNIQUE_THRESHOLD)/FL_COMPRESSION \ + + UNIQUE_THRESHOLD + +struct hblk * GC_hblkfreelist[N_HBLK_FLS+1] = { 0 }; + +#ifndef USE_MUNMAP + + word GC_free_bytes[N_HBLK_FLS+1] = { 0 }; + /* Number of free bytes on each list. */ + + /* Is bytes + the number of free bytes on lists n .. N_HBLK_FLS */ + /* > GC_max_large_allocd_bytes? */ +# ifdef __GNUC__ + __inline__ +# endif + static GC_bool GC_enough_large_bytes_left(bytes,n) + word bytes; + int n; + { + int i; + for (i = N_HBLK_FLS; i >= n; --i) { + bytes += GC_free_bytes[i]; + if (bytes > GC_max_large_allocd_bytes) return TRUE; + } + return FALSE; + } + +# define INCR_FREE_BYTES(n, b) GC_free_bytes[n] += (b); + +# define FREE_ASSERT(e) GC_ASSERT(e) + +#else /* USE_MUNMAP */ + +# define INCR_FREE_BYTES(n, b) +# define FREE_ASSERT(e) + +#endif /* USE_MUNMAP */ + +/* Map a number of blocks to the appropriate large block free list index. */ +int GC_hblk_fl_from_blocks(blocks_needed) +word blocks_needed; +{ + if (blocks_needed <= UNIQUE_THRESHOLD) return blocks_needed; + if (blocks_needed >= HUGE_THRESHOLD) return N_HBLK_FLS; + return (blocks_needed - UNIQUE_THRESHOLD)/FL_COMPRESSION + + UNIQUE_THRESHOLD; + +} + +# define PHDR(hhdr) HDR(hhdr -> hb_prev) +# define NHDR(hhdr) HDR(hhdr -> hb_next) + +# ifdef USE_MUNMAP +# define IS_MAPPED(hhdr) (((hhdr) -> hb_flags & WAS_UNMAPPED) == 0) +# else /* !USE_MMAP */ +# define IS_MAPPED(hhdr) 1 +# endif /* USE_MUNMAP */ + +# if !defined(NO_DEBUGGING) +void GC_print_hblkfreelist() +{ + struct hblk * h; + word total_free = 0; + hdr * hhdr; + word sz; + int i; + + for (i = 0; i <= N_HBLK_FLS; ++i) { + h = GC_hblkfreelist[i]; +# ifdef USE_MUNMAP + if (0 != h) GC_printf1("Free list %ld (Total size %ld):\n", + (unsigned long)i); +# else + if (0 != h) GC_printf2("Free list %ld (Total size %ld):\n", + (unsigned long)i, + (unsigned long)GC_free_bytes[i]); +# endif + while (h != 0) { + hhdr = HDR(h); + sz = hhdr -> hb_sz; + GC_printf2("\t0x%lx size %lu ", (unsigned long)h, (unsigned long)sz); + total_free += sz; + if (GC_is_black_listed(h, HBLKSIZE) != 0) { + GC_printf0("start black listed\n"); + } else if (GC_is_black_listed(h, hhdr -> hb_sz) != 0) { + GC_printf0("partially black listed\n"); + } else { + GC_printf0("not black listed\n"); + } + h = hhdr -> hb_next; + } + } + if (total_free != GC_large_free_bytes) { + GC_printf1("GC_large_free_bytes = %lu (INCONSISTENT!!)\n", + (unsigned long) GC_large_free_bytes); + } + GC_printf1("Total of %lu bytes on free list\n", (unsigned long)total_free); +} + +/* Return the free list index on which the block described by the header */ +/* appears, or -1 if it appears nowhere. */ +int free_list_index_of(wanted) +hdr * wanted; +{ + struct hblk * h; + hdr * hhdr; + int i; + + for (i = 0; i <= N_HBLK_FLS; ++i) { + h = GC_hblkfreelist[i]; + while (h != 0) { + hhdr = HDR(h); + if (hhdr == wanted) return i; + h = hhdr -> hb_next; + } + } + return -1; +} + +void GC_dump_regions() +{ + unsigned i; + ptr_t start, end; + ptr_t p; + size_t bytes; + hdr *hhdr; + for (i = 0; i < GC_n_heap_sects; ++i) { + start = GC_heap_sects[i].hs_start; + bytes = GC_heap_sects[i].hs_bytes; + end = start + bytes; + /* Merge in contiguous sections. */ + while (i+1 < GC_n_heap_sects && GC_heap_sects[i+1].hs_start == end) { + ++i; + end = GC_heap_sects[i].hs_start + GC_heap_sects[i].hs_bytes; + } + GC_printf2("***Section from 0x%lx to 0x%lx\n", start, end); + for (p = start; p < end;) { + hhdr = HDR(p); + GC_printf1("\t0x%lx ", (unsigned long)p); + if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) { + GC_printf1("Missing header!!\n", hhdr); + p += HBLKSIZE; + continue; + } + if (HBLK_IS_FREE(hhdr)) { + int correct_index = GC_hblk_fl_from_blocks( + divHBLKSZ(hhdr -> hb_sz)); + int actual_index; + + GC_printf1("\tfree block of size 0x%lx bytes", + (unsigned long)(hhdr -> hb_sz)); + if (IS_MAPPED(hhdr)) { + GC_printf0("\n"); + } else { + GC_printf0("(unmapped)\n"); + } + actual_index = free_list_index_of(hhdr); + if (-1 == actual_index) { + GC_printf1("\t\tBlock not on free list %ld!!\n", + correct_index); + } else if (correct_index != actual_index) { + GC_printf2("\t\tBlock on list %ld, should be on %ld!!\n", + actual_index, correct_index); + } + p += hhdr -> hb_sz; + } else { + GC_printf1("\tused for blocks of size 0x%lx bytes\n", + (unsigned long)WORDS_TO_BYTES(hhdr -> hb_sz)); + p += HBLKSIZE * OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz); + } + } + } +} + +# endif /* NO_DEBUGGING */ + +/* Initialize hdr for a block containing the indicated size and */ +/* kind of objects. */ +/* Return FALSE on failure. */ +static GC_bool setup_header(hhdr, sz, kind, flags) +register hdr * hhdr; +word sz; /* object size in words */ +int kind; +unsigned char flags; +{ + register word descr; + + /* Add description of valid object pointers */ + if (!GC_add_map_entry(sz)) return(FALSE); + hhdr -> hb_map = GC_obj_map[sz > MAXOBJSZ? 0 : sz]; + + /* Set size, kind and mark proc fields */ + hhdr -> hb_sz = sz; + hhdr -> hb_obj_kind = kind; + hhdr -> hb_flags = flags; + descr = GC_obj_kinds[kind].ok_descriptor; + if (GC_obj_kinds[kind].ok_relocate_descr) descr += WORDS_TO_BYTES(sz); + hhdr -> hb_descr = descr; + + /* Clear mark bits */ + GC_clear_hdr_marks(hhdr); + + hhdr -> hb_last_reclaimed = (unsigned short)GC_gc_no; + return(TRUE); +} + +#define FL_UNKNOWN -1 +/* + * Remove hhdr from the appropriate free list. + * We assume it is on the nth free list, or on the size + * appropriate free list if n is FL_UNKNOWN. + */ +void GC_remove_from_fl(hhdr, n) +hdr * hhdr; +int n; +{ + int index; + + GC_ASSERT(((hhdr -> hb_sz) & (HBLKSIZE-1)) == 0); +# ifndef USE_MUNMAP + /* We always need index to mainatin free counts. */ + if (FL_UNKNOWN == n) { + index = GC_hblk_fl_from_blocks(divHBLKSZ(hhdr -> hb_sz)); + } else { + index = n; + } +# endif + if (hhdr -> hb_prev == 0) { +# ifdef USE_MUNMAP + if (FL_UNKNOWN == n) { + index = GC_hblk_fl_from_blocks(divHBLKSZ(hhdr -> hb_sz)); + } else { + index = n; + } +# endif + GC_ASSERT(HDR(GC_hblkfreelist[index]) == hhdr); + GC_hblkfreelist[index] = hhdr -> hb_next; + } else { + hdr *phdr; + GET_HDR(hhdr -> hb_prev, phdr); + phdr -> hb_next = hhdr -> hb_next; + } + INCR_FREE_BYTES(index, - (signed_word)(hhdr -> hb_sz)); + FREE_ASSERT(GC_free_bytes[index] >= 0); + if (0 != hhdr -> hb_next) { + hdr * nhdr; + GC_ASSERT(!IS_FORWARDING_ADDR_OR_NIL(NHDR(hhdr))); + GET_HDR(hhdr -> hb_next, nhdr); + nhdr -> hb_prev = hhdr -> hb_prev; + } +} + +/* + * Return a pointer to the free block ending just before h, if any. + */ +struct hblk * GC_free_block_ending_at(h) +struct hblk *h; +{ + struct hblk * p = h - 1; + hdr * phdr; + + GET_HDR(p, phdr); + while (0 != phdr && IS_FORWARDING_ADDR_OR_NIL(phdr)) { + p = FORWARDED_ADDR(p,phdr); + phdr = HDR(p); + } + if (0 != phdr) { + if(HBLK_IS_FREE(phdr)) { + return p; + } else { + return 0; + } + } + p = GC_prev_block(h - 1); + if (0 != p) { + phdr = HDR(p); + if (HBLK_IS_FREE(phdr) && (ptr_t)p + phdr -> hb_sz == (ptr_t)h) { + return p; + } + } + return 0; +} + +/* + * Add hhdr to the appropriate free list. + * We maintain individual free lists sorted by address. + */ +void GC_add_to_fl(h, hhdr) +struct hblk *h; +hdr * hhdr; +{ + int index = GC_hblk_fl_from_blocks(divHBLKSZ(hhdr -> hb_sz)); + struct hblk *second = GC_hblkfreelist[index]; + hdr * second_hdr; +# ifdef GC_ASSERTIONS + struct hblk *next = (struct hblk *)((word)h + hhdr -> hb_sz); + hdr * nexthdr = HDR(next); + struct hblk *prev = GC_free_block_ending_at(h); + hdr * prevhdr = HDR(prev); + GC_ASSERT(nexthdr == 0 || !HBLK_IS_FREE(nexthdr) || !IS_MAPPED(nexthdr)); + GC_ASSERT(prev == 0 || !HBLK_IS_FREE(prevhdr) || !IS_MAPPED(prevhdr)); +# endif + GC_ASSERT(((hhdr -> hb_sz) & (HBLKSIZE-1)) == 0); + GC_hblkfreelist[index] = h; + INCR_FREE_BYTES(index, hhdr -> hb_sz); + FREE_ASSERT(GC_free_bytes[index] <= GC_large_free_bytes) + hhdr -> hb_next = second; + hhdr -> hb_prev = 0; + if (0 != second) { + GET_HDR(second, second_hdr); + second_hdr -> hb_prev = h; + } + GC_invalidate_map(hhdr); +} + +#ifdef USE_MUNMAP + +/* Unmap blocks that haven't been recently touched. This is the only way */ +/* way blocks are ever unmapped. */ +void GC_unmap_old(void) +{ + struct hblk * h; + hdr * hhdr; + word sz; + unsigned short last_rec, threshold; + int i; +# define UNMAP_THRESHOLD 6 + + for (i = 0; i <= N_HBLK_FLS; ++i) { + for (h = GC_hblkfreelist[i]; 0 != h; h = hhdr -> hb_next) { + hhdr = HDR(h); + if (!IS_MAPPED(hhdr)) continue; + threshold = (unsigned short)(GC_gc_no - UNMAP_THRESHOLD); + last_rec = hhdr -> hb_last_reclaimed; + if (last_rec > GC_gc_no + || last_rec < threshold && threshold < GC_gc_no + /* not recently wrapped */) { + sz = hhdr -> hb_sz; + GC_unmap((ptr_t)h, sz); + hhdr -> hb_flags |= WAS_UNMAPPED; + } + } + } +} + +/* Merge all unmapped blocks that are adjacent to other free */ +/* blocks. This may involve remapping, since all blocks are either */ +/* fully mapped or fully unmapped. */ +void GC_merge_unmapped(void) +{ + struct hblk * h, *next; + hdr * hhdr, *nexthdr; + word size, nextsize; + int i; + + for (i = 0; i <= N_HBLK_FLS; ++i) { + h = GC_hblkfreelist[i]; + while (h != 0) { + GET_HDR(h, hhdr); + size = hhdr->hb_sz; + next = (struct hblk *)((word)h + size); + GET_HDR(next, nexthdr); + /* Coalesce with successor, if possible */ + if (0 != nexthdr && HBLK_IS_FREE(nexthdr)) { + nextsize = nexthdr -> hb_sz; + if (IS_MAPPED(hhdr)) { + GC_ASSERT(!IS_MAPPED(nexthdr)); + /* make both consistent, so that we can merge */ + if (size > nextsize) { + GC_remap((ptr_t)next, nextsize); + } else { + GC_unmap((ptr_t)h, size); + hhdr -> hb_flags |= WAS_UNMAPPED; + } + } else if (IS_MAPPED(nexthdr)) { + GC_ASSERT(!IS_MAPPED(hhdr)); + if (size > nextsize) { + GC_unmap((ptr_t)next, nextsize); + } else { + GC_remap((ptr_t)h, size); + hhdr -> hb_flags &= ~WAS_UNMAPPED; + } + } else { + /* Unmap any gap in the middle */ + GC_unmap_gap((ptr_t)h, size, (ptr_t)next, nexthdr -> hb_sz); + } + /* If they are both unmapped, we merge, but leave unmapped. */ + GC_remove_from_fl(hhdr, i); + GC_remove_from_fl(nexthdr, FL_UNKNOWN); + hhdr -> hb_sz += nexthdr -> hb_sz; + GC_remove_header(next); + GC_add_to_fl(h, hhdr); + /* Start over at beginning of list */ + h = GC_hblkfreelist[i]; + } else /* not mergable with successor */ { + h = hhdr -> hb_next; + } + } /* while (h != 0) ... */ + } /* for ... */ +} + +#endif /* USE_MUNMAP */ + +/* + * Return a pointer to a block starting at h of length bytes. + * Memory for the block is mapped. + * Remove the block from its free list, and return the remainder (if any) + * to its appropriate free list. + * May fail by returning 0. + * The header for the returned block must be set up by the caller. + * If the return value is not 0, then hhdr is the header for it. + */ +struct hblk * GC_get_first_part(h, hhdr, bytes, index) +struct hblk *h; +hdr * hhdr; +word bytes; +int index; +{ + word total_size = hhdr -> hb_sz; + struct hblk * rest; + hdr * rest_hdr; + + GC_ASSERT((total_size & (HBLKSIZE-1)) == 0); + GC_remove_from_fl(hhdr, index); + if (total_size == bytes) return h; + rest = (struct hblk *)((word)h + bytes); + rest_hdr = GC_install_header(rest); + if (0 == rest_hdr) return(0); + rest_hdr -> hb_sz = total_size - bytes; + rest_hdr -> hb_flags = 0; +# ifdef GC_ASSERTIONS + /* Mark h not free, to avoid assertion about adjacent free blocks. */ + hhdr -> hb_map = 0; +# endif + GC_add_to_fl(rest, rest_hdr); + return h; +} + +/* + * H is a free block. N points at an address inside it. + * A new header for n has already been set up. Fix up h's header + * to reflect the fact that it is being split, move it to the + * appropriate free list. + * N replaces h in the original free list. + * + * Nhdr is not completely filled in, since it is about to allocated. + * It may in fact end up on the wrong free list for its size. + * (Hence adding it to a free list is silly. But this path is hopefully + * rare enough that it doesn't matter. The code is cleaner this way.) + */ +void GC_split_block(h, hhdr, n, nhdr, index) +struct hblk *h; +hdr * hhdr; +struct hblk *n; +hdr * nhdr; +int index; /* Index of free list */ +{ + word total_size = hhdr -> hb_sz; + word h_size = (word)n - (word)h; + struct hblk *prev = hhdr -> hb_prev; + struct hblk *next = hhdr -> hb_next; + + /* Replace h with n on its freelist */ + nhdr -> hb_prev = prev; + nhdr -> hb_next = next; + nhdr -> hb_sz = total_size - h_size; + nhdr -> hb_flags = 0; + if (0 != prev) { + HDR(prev) -> hb_next = n; + } else { + GC_hblkfreelist[index] = n; + } + if (0 != next) { + HDR(next) -> hb_prev = n; + } + INCR_FREE_BYTES(index, -(signed_word)h_size); + FREE_ASSERT(GC_free_bytes[index] > 0); +# ifdef GC_ASSERTIONS + nhdr -> hb_map = 0; /* Don't fail test for consecutive */ + /* free blocks in GC_add_to_fl. */ +# endif +# ifdef USE_MUNMAP + hhdr -> hb_last_reclaimed = GC_gc_no; +# endif + hhdr -> hb_sz = h_size; + GC_add_to_fl(h, hhdr); + GC_invalidate_map(nhdr); +} + +struct hblk * GC_allochblk_nth(); + +/* + * Allocate (and return pointer to) a heap block + * for objects of size sz words, searching the nth free list. + * + * NOTE: We set obj_map field in header correctly. + * Caller is responsible for building an object freelist in block. + * + * Unlike older versions of the collectors, the client is responsible + * for clearing the block, if necessary. + */ +struct hblk * +GC_allochblk(sz, kind, flags) +word sz; +int kind; +unsigned flags; /* IGNORE_OFF_PAGE or 0 */ +{ + word blocks = OBJ_SZ_TO_BLOCKS(sz); + int start_list = GC_hblk_fl_from_blocks(blocks); + int i; + for (i = start_list; i <= N_HBLK_FLS; ++i) { + struct hblk * result = GC_allochblk_nth(sz, kind, flags, i); + if (0 != result) { + return result; + } + } + return 0; +} +/* + * The same, but with search restricted to nth free list. + */ +struct hblk * +GC_allochblk_nth(sz, kind, flags, n) +word sz; +int kind; +unsigned char flags; /* IGNORE_OFF_PAGE or 0 */ +int n; +{ + register struct hblk *hbp; + register hdr * hhdr; /* Header corr. to hbp */ + register struct hblk *thishbp; + register hdr * thishdr; /* Header corr. to hbp */ + signed_word size_needed; /* number of bytes in requested objects */ + signed_word size_avail; /* bytes available in this block */ + + size_needed = HBLKSIZE * OBJ_SZ_TO_BLOCKS(sz); + + /* search for a big enough block in free list */ + hbp = GC_hblkfreelist[n]; + for(; 0 != hbp; hbp = hhdr -> hb_next) { + GET_HDR(hbp, hhdr); + size_avail = hhdr->hb_sz; + if (size_avail < size_needed) continue; + if (!GC_use_entire_heap + && size_avail != size_needed + && USED_HEAP_SIZE >= GC_requested_heapsize + && !TRUE_INCREMENTAL && GC_should_collect()) { +# ifdef USE_MUNMAP + continue; +# else + /* If we have enough large blocks left to cover any */ + /* previous request for large blocks, we go ahead */ + /* and split. Assuming a steady state, that should */ + /* be safe. It means that we can use the full */ + /* heap if we allocate only small objects. */ + if (!GC_enough_large_bytes_left(GC_large_allocd_bytes, n)) { + continue; + } + /* If we are deallocating lots of memory from */ + /* finalizers, fail and collect sooner rather */ + /* than later. */ + if (GC_finalizer_mem_freed > (GC_heapsize >> 4)) { + continue; + } +# endif /* !USE_MUNMAP */ + } + /* If the next heap block is obviously better, go on. */ + /* This prevents us from disassembling a single large block */ + /* to get tiny blocks. */ + { + signed_word next_size; + + thishbp = hhdr -> hb_next; + if (thishbp != 0) { + GET_HDR(thishbp, thishdr); + next_size = (signed_word)(thishdr -> hb_sz); + if (next_size < size_avail + && next_size >= size_needed + && !GC_is_black_listed(thishbp, (word)size_needed)) { + continue; + } + } + } + if ( !IS_UNCOLLECTABLE(kind) && + (kind != PTRFREE || size_needed > MAX_BLACK_LIST_ALLOC)) { + struct hblk * lasthbp = hbp; + ptr_t search_end = (ptr_t)hbp + size_avail - size_needed; + signed_word orig_avail = size_avail; + signed_word eff_size_needed = ((flags & IGNORE_OFF_PAGE)? + HBLKSIZE + : size_needed); + + + while ((ptr_t)lasthbp <= search_end + && (thishbp = GC_is_black_listed(lasthbp, + (word)eff_size_needed)) + != 0) { + lasthbp = thishbp; + } + size_avail -= (ptr_t)lasthbp - (ptr_t)hbp; + thishbp = lasthbp; + if (size_avail >= size_needed) { + if (thishbp != hbp && + 0 != (thishdr = GC_install_header(thishbp))) { + /* Make sure it's mapped before we mangle it. */ +# ifdef USE_MUNMAP + if (!IS_MAPPED(hhdr)) { + GC_remap((ptr_t)hbp, hhdr -> hb_sz); + hhdr -> hb_flags &= ~WAS_UNMAPPED; + } +# endif + /* Split the block at thishbp */ + GC_split_block(hbp, hhdr, thishbp, thishdr, n); + /* Advance to thishbp */ + hbp = thishbp; + hhdr = thishdr; + /* We must now allocate thishbp, since it may */ + /* be on the wrong free list. */ + } + } else if (size_needed > (signed_word)BL_LIMIT + && orig_avail - size_needed + > (signed_word)BL_LIMIT) { + /* Punt, since anything else risks unreasonable heap growth. */ + if (++GC_large_alloc_warn_suppressed + >= GC_large_alloc_warn_interval) { + WARN("Repeated allocation of very large block " + "(appr. size %ld):\n" + "\tMay lead to memory leak and poor performance.\n", + size_needed); + GC_large_alloc_warn_suppressed = 0; + } + size_avail = orig_avail; + } else if (size_avail == 0 && size_needed == HBLKSIZE + && IS_MAPPED(hhdr)) { + if (!GC_find_leak) { + static unsigned count = 0; + + /* The block is completely blacklisted. We need */ + /* to drop some such blocks, since otherwise we spend */ + /* all our time traversing them if pointerfree */ + /* blocks are unpopular. */ + /* A dropped block will be reconsidered at next GC. */ + if ((++count & 3) == 0) { + /* Allocate and drop the block in small chunks, to */ + /* maximize the chance that we will recover some */ + /* later. */ + word total_size = hhdr -> hb_sz; + struct hblk * limit = hbp + divHBLKSZ(total_size); + struct hblk * h; + struct hblk * prev = hhdr -> hb_prev; + + GC_words_wasted += total_size; + GC_large_free_bytes -= total_size; + GC_remove_from_fl(hhdr, n); + for (h = hbp; h < limit; h++) { + if (h == hbp || 0 != (hhdr = GC_install_header(h))) { + (void) setup_header( + hhdr, + BYTES_TO_WORDS(HBLKSIZE), + PTRFREE, 0); /* Cant fail */ + if (GC_debugging_started) { + BZERO(h, HBLKSIZE); + } + } + } + /* Restore hbp to point at free block */ + hbp = prev; + if (0 == hbp) { + return GC_allochblk_nth(sz, kind, flags, n); + } + hhdr = HDR(hbp); + } + } + } + } + if( size_avail >= size_needed ) { +# ifdef USE_MUNMAP + if (!IS_MAPPED(hhdr)) { + GC_remap((ptr_t)hbp, hhdr -> hb_sz); + hhdr -> hb_flags &= ~WAS_UNMAPPED; + } +# endif + /* hbp may be on the wrong freelist; the parameter n */ + /* is important. */ + hbp = GC_get_first_part(hbp, hhdr, size_needed, n); + break; + } + } + + if (0 == hbp) return 0; + + /* Add it to map of valid blocks */ + if (!GC_install_counts(hbp, (word)size_needed)) return(0); + /* This leaks memory under very rare conditions. */ + + /* Set up header */ + if (!setup_header(hhdr, sz, kind, flags)) { + GC_remove_counts(hbp, (word)size_needed); + return(0); /* ditto */ + } + + /* Notify virtual dirty bit implementation that we are about to write. */ + /* Ensure that pointerfree objects are not protected if it's avoidable. */ + GC_remove_protection(hbp, divHBLKSZ(size_needed), + (hhdr -> hb_descr == 0) /* pointer-free */); + + /* We just successfully allocated a block. Restart count of */ + /* consecutive failures. */ + { + extern unsigned GC_fail_count; + + GC_fail_count = 0; + } + + GC_large_free_bytes -= size_needed; + + GC_ASSERT(IS_MAPPED(hhdr)); + return( hbp ); +} + +struct hblk * GC_freehblk_ptr = 0; /* Search position hint for GC_freehblk */ + +/* + * Free a heap block. + * + * Coalesce the block with its neighbors if possible. + * + * All mark words are assumed to be cleared. + */ +void +GC_freehblk(hbp) +struct hblk *hbp; +{ +struct hblk *next, *prev; +hdr *hhdr, *prevhdr, *nexthdr; +signed_word size; + + + GET_HDR(hbp, hhdr); + size = hhdr->hb_sz; + size = HBLKSIZE * OBJ_SZ_TO_BLOCKS(size); + GC_remove_counts(hbp, (word)size); + hhdr->hb_sz = size; + + /* Check for duplicate deallocation in the easy case */ + if (HBLK_IS_FREE(hhdr)) { + GC_printf1("Duplicate large block deallocation of 0x%lx\n", + (unsigned long) hbp); + ABORT("Duplicate large block deallocation"); + } + + GC_ASSERT(IS_MAPPED(hhdr)); + GC_invalidate_map(hhdr); + next = (struct hblk *)((word)hbp + size); + GET_HDR(next, nexthdr); + prev = GC_free_block_ending_at(hbp); + /* Coalesce with successor, if possible */ + if(0 != nexthdr && HBLK_IS_FREE(nexthdr) && IS_MAPPED(nexthdr)) { + GC_remove_from_fl(nexthdr, FL_UNKNOWN); + hhdr -> hb_sz += nexthdr -> hb_sz; + GC_remove_header(next); + } + /* Coalesce with predecessor, if possible. */ + if (0 != prev) { + prevhdr = HDR(prev); + if (IS_MAPPED(prevhdr)) { + GC_remove_from_fl(prevhdr, FL_UNKNOWN); + prevhdr -> hb_sz += hhdr -> hb_sz; + GC_remove_header(hbp); + hbp = prev; + hhdr = prevhdr; + } + } + + GC_large_free_bytes += size; + GC_add_to_fl(hbp, hhdr); +} +