git.gag.com Git - fw/sdcc/blob - support/gc/allchblk.c

   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) 1998-1999 by Silicon Graphics.  All rights reserved.
   5  *
   6  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
   7  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
   8  *
   9  * Permission is hereby granted to use or copy this program
  10  * for any purpose,  provided the above notices are retained on all copies.
  11  * Permission to modify the code and to distribute modified code is granted,
  12  * provided the above notices are retained, and a notice that the code was
  13  * modified is included with the above copyright notice.
  14  */
  15
  16 #define DEBUG
  17 #undef DEBUG
  18 #include <stdio.h>
  19 #include "gc_priv.h"
  20
  21
  22 /*
  23  * Free heap blocks are kept on one of several free lists,
  24  * depending on the size of the block.  Each free list is doubly linked.
  25  * Adjacent free blocks are coalesced.
  26  */
  27
  28
  29 # define MAX_BLACK_LIST_ALLOC (2*HBLKSIZE)
  30                 /* largest block we will allocate starting on a black   */
  31                 /* listed block.  Must be >= HBLKSIZE.                  */
  32
  33
  34 # define UNIQUE_THRESHOLD 32
  35         /* Sizes up to this many HBLKs each have their own free list    */
  36 # define HUGE_THRESHOLD 256
  37         /* Sizes of at least this many heap blocks are mapped to a      */
  38         /* single free list.                                            */
  39 # define FL_COMPRESSION 8
  40         /* In between sizes map this many distinct sizes to a single    */
  41         /* bin.                                                         */
  42
  43 # define N_HBLK_FLS (HUGE_THRESHOLD - UNIQUE_THRESHOLD)/FL_COMPRESSION \
  44                                  + UNIQUE_THRESHOLD
  45
  46 struct hblk * GC_hblkfreelist[N_HBLK_FLS+1] = { 0 };
  47
  48 /* Map a number of blocks to the appropriate large block free list index. */
  49 int GC_hblk_fl_from_blocks(blocks_needed)
  50 word blocks_needed;
  51 {
  52     if (blocks_needed <= UNIQUE_THRESHOLD) return blocks_needed;
  53     if (blocks_needed >= HUGE_THRESHOLD) return N_HBLK_FLS;
  54     return (blocks_needed - UNIQUE_THRESHOLD)/FL_COMPRESSION
  55                                         + UNIQUE_THRESHOLD;
  56
  57 }
  58
  59 # define HBLK_IS_FREE(hdr) ((hdr) -> hb_map == GC_invalid_map)
  60 # define PHDR(hhdr) HDR(hhdr -> hb_prev)
  61 # define NHDR(hhdr) HDR(hhdr -> hb_next)
  62
  63 # ifdef USE_MUNMAP
  64 #   define IS_MAPPED(hhdr) (((hhdr) -> hb_flags & WAS_UNMAPPED) == 0)
  65 # else  /* !USE_MMAP */
  66 #   define IS_MAPPED(hhdr) 1
  67 # endif /* USE_MUNMAP */
  68
  69 # if !defined(NO_DEBUGGING)
  70 void GC_print_hblkfreelist()
  71 {
  72     struct hblk * h;
  73     word total_free = 0;
  74     hdr * hhdr;
  75     word sz;
  76     int i;
  77
  78     for (i = 0; i <= N_HBLK_FLS; ++i) {
  79       h = GC_hblkfreelist[i];
  80       if (0 != h) GC_printf1("Free list %ld:\n", (unsigned long)i);
  81       while (h != 0) {
  82         hhdr = HDR(h);
  83         sz = hhdr -> hb_sz;
  84         GC_printf2("\t0x%lx size %lu ", (unsigned long)h, (unsigned long)sz);
  85         total_free += sz;
  86         if (GC_is_black_listed(h, HBLKSIZE) != 0) {
  87              GC_printf0("start black listed\n");
  88         } else if (GC_is_black_listed(h, hhdr -> hb_sz) != 0) {
  89              GC_printf0("partially black listed\n");
  90         } else {
  91              GC_printf0("not black listed\n");
  92         }
  93         h = hhdr -> hb_next;
  94       }
  95     }
  96     if (total_free != GC_large_free_bytes) {
  97         GC_printf1("GC_large_free_bytes = %lu (INCONSISTENT!!)\n",
  98                    (unsigned long) GC_large_free_bytes);
  99     }
 100     GC_printf1("Total of %lu bytes on free list\n", (unsigned long)total_free);
 101 }
 102
 103 /* Return the free list index on which the block described by the header */
 104 /* appears, or -1 if it appears nowhere.                                 */
 105 int free_list_index_of(wanted)
 106 hdr * wanted;
 107 {
 108     struct hblk * h;
 109     hdr * hhdr;
 110     int i;
 111
 112     for (i = 0; i <= N_HBLK_FLS; ++i) {
 113       h = GC_hblkfreelist[i];
 114       while (h != 0) {
 115         hhdr = HDR(h);
 116         if (hhdr == wanted) return i;
 117         h = hhdr -> hb_next;
 118       }
 119     }
 120     return -1;
 121 }
 122
 123 void GC_dump_regions()
 124 {
 125     int i;
 126     ptr_t start, end;
 127     ptr_t p;
 128     size_t bytes;
 129     hdr *hhdr;
 130     for (i = 0; i < GC_n_heap_sects; ++i) {
 131         start = GC_heap_sects[i].hs_start;
 132         bytes = GC_heap_sects[i].hs_bytes;
 133         end = start + bytes;
 134         /* Merge in contiguous sections.        */
 135           while (i+1 < GC_n_heap_sects && GC_heap_sects[i+1].hs_start == end) {
 136             ++i;
 137             end = GC_heap_sects[i].hs_start + GC_heap_sects[i].hs_bytes;
 138           }
 139         GC_printf2("***Section from 0x%lx to 0x%lx\n", start, end);
 140         for (p = start; p < end;) {
 141             hhdr = HDR(p);
 142             GC_printf1("\t0x%lx ", (unsigned long)p);
 143             if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) {
 144                 GC_printf1("Missing header!!\n", hhdr);
 145                 p += HBLKSIZE;
 146                 continue;
 147             }
 148             if (HBLK_IS_FREE(hhdr)) {
 149                 int correct_index = GC_hblk_fl_from_blocks(
 150                                         divHBLKSZ(hhdr -> hb_sz));
 151                 int actual_index;
 152
 153                 GC_printf1("\tfree block of size 0x%lx bytes",
 154                            (unsigned long)(hhdr -> hb_sz));
 155                 if (IS_MAPPED(hhdr)) {
 156                     GC_printf0("\n");
 157                 } else {
 158                     GC_printf0("(unmapped)\n");
 159                 }
 160                 actual_index = free_list_index_of(hhdr);
 161                 if (-1 == actual_index) {
 162                     GC_printf1("\t\tBlock not on free list %ld!!\n",
 163                                 correct_index);
 164                 } else if (correct_index != actual_index) {
 165                     GC_printf2("\t\tBlock on list %ld, should be on %ld!!\n",
 166                                actual_index, correct_index);
 167                 }
 168                 p += hhdr -> hb_sz;
 169             } else {
 170                 GC_printf1("\tused for blocks of size 0x%lx bytes\n",
 171                            (unsigned long)WORDS_TO_BYTES(hhdr -> hb_sz));
 172                 p += HBLKSIZE * OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz);
 173             }
 174         }
 175     }
 176 }
 177
 178 # endif /* NO_DEBUGGING */
 179
 180 /* Initialize hdr for a block containing the indicated size and         */
 181 /* kind of objects.                                                     */
 182 /* Return FALSE on failure.                                             */
 183 static GC_bool setup_header(hhdr, sz, kind, flags)
 184 register hdr * hhdr;
 185 word sz;        /* object size in words */
 186 int kind;
 187 unsigned char flags;
 188 {
 189     register word descr;
 190
 191     /* Add description of valid object pointers */
 192       if (!GC_add_map_entry(sz)) return(FALSE);
 193       hhdr -> hb_map = GC_obj_map[sz > MAXOBJSZ? 0 : sz];
 194
 195     /* Set size, kind and mark proc fields */
 196       hhdr -> hb_sz = sz;
 197       hhdr -> hb_obj_kind = kind;
 198       hhdr -> hb_flags = flags;
 199       descr = GC_obj_kinds[kind].ok_descriptor;
 200       if (GC_obj_kinds[kind].ok_relocate_descr) descr += WORDS_TO_BYTES(sz);
 201       hhdr -> hb_descr = descr;
 202
 203     /* Clear mark bits */
 204       GC_clear_hdr_marks(hhdr);
 205
 206     hhdr -> hb_last_reclaimed = (unsigned short)GC_gc_no;
 207     return(TRUE);
 208 }
 209
 210 #define FL_UNKNOWN -1
 211 /*
 212  * Remove hhdr from the appropriate free list.
 213  * We assume it is on the nth free list, or on the size
 214  * appropriate free list if n is FL_UNKNOWN.
 215  */
 216 void GC_remove_from_fl(hhdr, n)
 217 hdr * hhdr;
 218 int n;
 219 {
 220     GC_ASSERT(((hhdr -> hb_sz) & (HBLKSIZE-1)) == 0);
 221     if (hhdr -> hb_prev == 0) {
 222         int index;
 223         if (FL_UNKNOWN == n) {
 224             index = GC_hblk_fl_from_blocks(divHBLKSZ(hhdr -> hb_sz));
 225         } else {
 226             index = n;
 227         }
 228         GC_ASSERT(HDR(GC_hblkfreelist[index]) == hhdr);
 229         GC_hblkfreelist[index] = hhdr -> hb_next;
 230     } else {
 231         PHDR(hhdr) -> hb_next = hhdr -> hb_next;
 232     }
 233     if (0 != hhdr -> hb_next) {
 234         GC_ASSERT(!IS_FORWARDING_ADDR_OR_NIL(NHDR(hhdr)));
 235         NHDR(hhdr) -> hb_prev = hhdr -> hb_prev;
 236     }
 237 }
 238
 239 /*
 240  * Return a pointer to the free block ending just before h, if any.
 241  */
 242 struct hblk * GC_free_block_ending_at(h)
 243 struct hblk *h;
 244 {
 245     struct hblk * p = h - 1;
 246     hdr * phdr = HDR(p);
 247
 248     while (0 != phdr && IS_FORWARDING_ADDR_OR_NIL(phdr)) {
 249         p = FORWARDED_ADDR(p,phdr);
 250         phdr = HDR(p);
 251     }
 252     if (0 != phdr && HBLK_IS_FREE(phdr)) return p;
 253     p = GC_prev_block(h - 1);
 254     if (0 != p) {
 255       phdr = HDR(p);
 256       if (HBLK_IS_FREE(phdr) && (ptr_t)p + phdr -> hb_sz == (ptr_t)h) {
 257         return p;
 258       }
 259     }
 260     return 0;
 261 }
 262
 263 /*
 264  * Add hhdr to the appropriate free list.
 265  * We maintain individual free lists sorted by address.
 266  */
 267 void GC_add_to_fl(h, hhdr)
 268 struct hblk *h;
 269 hdr * hhdr;
 270 {
 271     int index = GC_hblk_fl_from_blocks(divHBLKSZ(hhdr -> hb_sz));
 272     struct hblk *second = GC_hblkfreelist[index];
 273 #   ifdef GC_ASSERTIONS
 274       struct hblk *next = (struct hblk *)((word)h + hhdr -> hb_sz);
 275       hdr * nexthdr = HDR(next);
 276       struct hblk *prev = GC_free_block_ending_at(h);
 277       hdr * prevhdr = HDR(prev);
 278       GC_ASSERT(nexthdr == 0 || !HBLK_IS_FREE(nexthdr) || !IS_MAPPED(nexthdr));
 279       GC_ASSERT(prev == 0 || !HBLK_IS_FREE(prevhdr) || !IS_MAPPED(prevhdr));
 280 #   endif
 281     GC_ASSERT(((hhdr -> hb_sz) & (HBLKSIZE-1)) == 0);
 282     GC_hblkfreelist[index] = h;
 283     hhdr -> hb_next = second;
 284     hhdr -> hb_prev = 0;
 285     if (0 != second) HDR(second) -> hb_prev = h;
 286     GC_invalidate_map(hhdr);
 287 }
 288
 289 #ifdef USE_MUNMAP
 290
 291 /* Unmap blocks that haven't been recently touched.  This is the only way */
 292 /* way blocks are ever unmapped.                                          */
 293 void GC_unmap_old(void)
 294 {
 295     struct hblk * h;
 296     hdr * hhdr;
 297     word sz;
 298     unsigned short last_rec, threshold;
 299     int i;
 300 #   define UNMAP_THRESHOLD 6
 301
 302     for (i = 0; i <= N_HBLK_FLS; ++i) {
 303       for (h = GC_hblkfreelist[i]; 0 != h; h = hhdr -> hb_next) {
 304         hhdr = HDR(h);
 305         if (!IS_MAPPED(hhdr)) continue;
 306         threshold = (unsigned short)(GC_gc_no - UNMAP_THRESHOLD);
 307         last_rec = hhdr -> hb_last_reclaimed;
 308         if (last_rec > GC_gc_no
 309             || last_rec < threshold && threshold < GC_gc_no
 310                                        /* not recently wrapped */) {
 311           sz = hhdr -> hb_sz;
 312           GC_unmap((ptr_t)h, sz);
 313           hhdr -> hb_flags |= WAS_UNMAPPED;
 314         }
 315       }
 316     }
 317 }
 318
 319 /* Merge all unmapped blocks that are adjacent to other free            */
 320 /* blocks.  This may involve remapping, since all blocks are either     */
 321 /* fully mapped or fully unmapped.                                      */
 322 void GC_merge_unmapped(void)
 323 {
 324     struct hblk * h, *next;
 325     hdr * hhdr, *nexthdr;
 326     word size, nextsize;
 327     int i;
 328
 329     for (i = 0; i <= N_HBLK_FLS; ++i) {
 330       h = GC_hblkfreelist[i];
 331       while (h != 0) {
 332         hhdr = HDR(h);
 333         size = hhdr->hb_sz;
 334         next = (struct hblk *)((word)h + size);
 335         nexthdr = HDR(next);
 336         /* Coalesce with successor, if possible */
 337           if (0 != nexthdr && HBLK_IS_FREE(nexthdr)) {
 338             nextsize = nexthdr -> hb_sz;
 339             if (IS_MAPPED(hhdr)) {
 340               GC_ASSERT(!IS_MAPPED(nexthdr));
 341               /* make both consistent, so that we can merge */
 342                 if (size > nextsize) {
 343                   GC_remap((ptr_t)next, nextsize);
 344                 } else {
 345                   GC_unmap((ptr_t)h, size);
 346                   hhdr -> hb_flags |= WAS_UNMAPPED;
 347                 }
 348             } else if (IS_MAPPED(nexthdr)) {
 349               GC_ASSERT(!IS_MAPPED(hhdr));
 350               if (size > nextsize) {
 351                 GC_unmap((ptr_t)next, nextsize);
 352               } else {
 353                 GC_remap((ptr_t)h, size);
 354                 hhdr -> hb_flags &= ~WAS_UNMAPPED;
 355               }
 356             } else {
 357               /* Unmap any gap in the middle */
 358                 GC_unmap_gap((ptr_t)h, size, (ptr_t)next, nexthdr -> hb_sz);
 359             }
 360             /* If they are both unmapped, we merge, but leave unmapped. */
 361             GC_remove_from_fl(hhdr, i);
 362             GC_remove_from_fl(nexthdr, FL_UNKNOWN);
 363             hhdr -> hb_sz += nexthdr -> hb_sz;
 364             GC_remove_header(next);
 365             GC_add_to_fl(h, hhdr);
 366             /* Start over at beginning of list */
 367             h = GC_hblkfreelist[i];
 368           } else /* not mergable with successor */ {
 369             h = hhdr -> hb_next;
 370           }
 371       } /* while (h != 0) ... */
 372     } /* for ... */
 373 }
 374
 375 #endif /* USE_MUNMAP */
 376
 377 /*
 378  * Return a pointer to a block starting at h of length bytes.
 379  * Memory for the block is mapped.
 380  * Remove the block from its free list, and return the remainder (if any)
 381  * to its appropriate free list.
 382  * May fail by returning 0.
 383  * The header for the returned block must be set up by the caller.
 384  * If the return value is not 0, then hhdr is the header for it.
 385  */
 386 struct hblk * GC_get_first_part(h, hhdr, bytes, index)
 387 struct hblk *h;
 388 hdr * hhdr;
 389 word bytes;
 390 int index;
 391 {
 392     word total_size = hhdr -> hb_sz;
 393     struct hblk * rest;
 394     hdr * rest_hdr;
 395
 396     GC_ASSERT((total_size & (HBLKSIZE-1)) == 0);
 397     GC_remove_from_fl(hhdr, index);
 398     if (total_size == bytes) return h;
 399     rest = (struct hblk *)((word)h + bytes);
 400     if (!GC_install_header(rest)) return(0);
 401     rest_hdr = HDR(rest);
 402     rest_hdr -> hb_sz = total_size - bytes;
 403     rest_hdr -> hb_flags = 0;
 404 #   ifdef GC_ASSERTIONS
 405       // Mark h not free, to avoid assertion about adjacent free blocks.
 406         hhdr -> hb_map = 0;
 407 #   endif
 408     GC_add_to_fl(rest, rest_hdr);
 409     return h;
 410 }
 411
 412 /*
 413  * H is a free block.  N points at an address inside it.
 414  * A new header for n has already been set up.  Fix up h's header
 415  * to reflect the fact that it is being split, move it to the
 416  * appropriate free list.
 417  * N replaces h in the original free list.
 418  *
 419  * Nhdr is not completely filled in, since it is about to allocated.
 420  * It may in fact end up on the wrong free list for its size.
 421  * (Hence adding it to a free list is silly.  But this path is hopefully
 422  * rare enough that it doesn't matter.  The code is cleaner this way.)
 423  */
 424 void GC_split_block(h, hhdr, n, nhdr, index)
 425 struct hblk *h;
 426 hdr * hhdr;
 427 struct hblk *n;
 428 hdr * nhdr;
 429 int index;      /* Index of free list */
 430 {
 431     word total_size = hhdr -> hb_sz;
 432     word h_size = (word)n - (word)h;
 433     struct hblk *prev = hhdr -> hb_prev;
 434     struct hblk *next = hhdr -> hb_next;
 435
 436     /* Replace h with n on its freelist */
 437       nhdr -> hb_prev = prev;
 438       nhdr -> hb_next = next;
 439       nhdr -> hb_sz = total_size - h_size;
 440       nhdr -> hb_flags = 0;
 441       if (0 != prev) {
 442         HDR(prev) -> hb_next = n;
 443       } else {
 444         GC_hblkfreelist[index] = n;
 445       }
 446       if (0 != next) {
 447         HDR(next) -> hb_prev = n;
 448       }
 449 #     ifdef GC_ASSERTIONS
 450         nhdr -> hb_map = 0;     /* Don't fail test for consecutive      */
 451                                 /* free blocks in GC_add_to_fl.         */
 452 #     endif
 453 #   ifdef USE_MUNMAP
 454       hhdr -> hb_last_reclaimed = GC_gc_no;
 455 #   endif
 456     hhdr -> hb_sz = h_size;
 457     GC_add_to_fl(h, hhdr);
 458     GC_invalidate_map(nhdr);
 459 }
 460
 461 struct hblk * GC_allochblk_nth();
 462
 463 /*
 464  * Allocate (and return pointer to) a heap block
 465  *   for objects of size sz words, searching the nth free list.
 466  *
 467  * NOTE: We set obj_map field in header correctly.
 468  *       Caller is responsible for building an object freelist in block.
 469  *
 470  * We clear the block if it is destined for large objects, and if
 471  * kind requires that newly allocated objects be cleared.
 472  */
 473 struct hblk *
 474 GC_allochblk(sz, kind, flags)
 475 word sz;
 476 int kind;
 477 unsigned char flags;  /* IGNORE_OFF_PAGE or 0 */
 478 {
 479     int start_list = GC_hblk_fl_from_blocks(OBJ_SZ_TO_BLOCKS(sz));
 480     int i;
 481     for (i = start_list; i <= N_HBLK_FLS; ++i) {
 482         struct hblk * result = GC_allochblk_nth(sz, kind, flags, i);
 483         if (0 != result) return result;
 484     }
 485     return 0;
 486 }
 487 /*
 488  * The same, but with search restricted to nth free list.
 489  */
 490 struct hblk *
 491 GC_allochblk_nth(sz, kind, flags, n)
 492 word sz;
 493 int kind;
 494 unsigned char flags;  /* IGNORE_OFF_PAGE or 0 */
 495 int n;
 496 {
 497     register struct hblk *hbp;
 498     register hdr * hhdr;                /* Header corr. to hbp */
 499     register struct hblk *thishbp;
 500     register hdr * thishdr;             /* Header corr. to hbp */
 501     signed_word size_needed;    /* number of bytes in requested objects */
 502     signed_word size_avail;     /* bytes available in this block        */
 503
 504     size_needed = HBLKSIZE * OBJ_SZ_TO_BLOCKS(sz);
 505
 506     /* search for a big enough block in free list */
 507         hbp = GC_hblkfreelist[n];
 508         hhdr = HDR(hbp);
 509         for(; 0 != hbp; hbp = hhdr -> hb_next, hhdr = HDR(hbp)) {
 510             size_avail = hhdr->hb_sz;
 511             if (size_avail < size_needed) continue;
 512 #           ifdef PRESERVE_LAST
 513                 if (size_avail != size_needed
 514                     && !GC_incremental && GC_should_collect()) {
 515                     continue;
 516                 }
 517 #           endif
 518             /* If the next heap block is obviously better, go on.       */
 519             /* This prevents us from disassembling a single large block */
 520             /* to get tiny blocks.                                      */
 521             {
 522               signed_word next_size;
 523
 524               thishbp = hhdr -> hb_next;
 525               if (thishbp != 0) {
 526                 thishdr = HDR(thishbp);
 527                 next_size = (signed_word)(thishdr -> hb_sz);
 528                 if (next_size < size_avail
 529                   && next_size >= size_needed
 530                   && !GC_is_black_listed(thishbp, (word)size_needed)) {
 531                   continue;
 532                 }
 533               }
 534             }
 535             if ( !IS_UNCOLLECTABLE(kind) &&
 536                  (kind != PTRFREE || size_needed > MAX_BLACK_LIST_ALLOC)) {
 537               struct hblk * lasthbp = hbp;
 538               ptr_t search_end = (ptr_t)hbp + size_avail - size_needed;
 539               signed_word orig_avail = size_avail;
 540               signed_word eff_size_needed = ((flags & IGNORE_OFF_PAGE)?
 541                                                 HBLKSIZE
 542                                                 : size_needed);
 543
 544
 545               while ((ptr_t)lasthbp <= search_end
 546                      && (thishbp = GC_is_black_listed(lasthbp,
 547                                                       (word)eff_size_needed))) {
 548                 lasthbp = thishbp;
 549               }
 550               size_avail -= (ptr_t)lasthbp - (ptr_t)hbp;
 551               thishbp = lasthbp;
 552               if (size_avail >= size_needed) {
 553                 if (thishbp != hbp && GC_install_header(thishbp)) {
 554                   /* Make sure it's mapped before we mangle it. */
 555 #                   ifdef USE_MUNMAP
 556                       if (!IS_MAPPED(hhdr)) {
 557                         GC_remap((ptr_t)hbp, size_avail);
 558                         hhdr -> hb_flags &= ~WAS_UNMAPPED;
 559                       }
 560 #                   endif
 561                   /* Split the block at thishbp */
 562                       thishdr = HDR(thishbp);
 563                       GC_split_block(hbp, hhdr, thishbp, thishdr, n);
 564                   /* Advance to thishbp */
 565                       hbp = thishbp;
 566                       hhdr = thishdr;
 567                       /* We must now allocate thishbp, since it may     */
 568                       /* be on the wrong free list.                     */
 569                 }
 570               } else if (size_needed > (signed_word)BL_LIMIT
 571                          && orig_avail - size_needed
 572                             > (signed_word)BL_LIMIT) {
 573                 /* Punt, since anything else risks unreasonable heap growth. */
 574                 WARN("Needed to allocate blacklisted block at 0x%lx\n",
 575                      (word)hbp);
 576                 size_avail = orig_avail;
 577               } else if (size_avail == 0 && size_needed == HBLKSIZE
 578                          && IS_MAPPED(hhdr)) {
 579                 if (!GC_find_leak) {
 580                   static unsigned count = 0;
 581
 582                   /* The block is completely blacklisted.  We need      */
 583                   /* to drop some such blocks, since otherwise we spend */
 584                   /* all our time traversing them if pointerfree        */
 585                   /* blocks are unpopular.                              */
 586                   /* A dropped block will be reconsidered at next GC.   */
 587                   if ((++count & 3) == 0) {
 588                     /* Allocate and drop the block in small chunks, to  */
 589                     /* maximize the chance that we will recover some    */
 590                     /* later.                                           */
 591                       word total_size = hhdr -> hb_sz;
 592                       struct hblk * limit = hbp + divHBLKSZ(total_size);
 593                       struct hblk * h;
 594                       struct hblk * prev = hhdr -> hb_prev;
 595
 596                       GC_words_wasted += total_size;
 597                       GC_large_free_bytes -= total_size;
 598                       GC_remove_from_fl(hhdr, n);
 599                       for (h = hbp; h < limit; h++) {
 600                         if (h == hbp || GC_install_header(h)) {
 601                           hhdr = HDR(h);
 602                           (void) setup_header(
 603                                   hhdr,
 604                                   BYTES_TO_WORDS(HBLKSIZE - HDR_BYTES),
 605                                   PTRFREE, 0); /* Cant fail */
 606                           if (GC_debugging_started) {
 607                             BZERO(h + HDR_BYTES, HBLKSIZE - HDR_BYTES);
 608                           }
 609                         }
 610                       }
 611                     /* Restore hbp to point at free block */
 612                       hbp = prev;
 613                       if (0 == hbp) {
 614                         return GC_allochblk_nth(sz, kind, flags, n);
 615                       }
 616                       hhdr = HDR(hbp);
 617                   }
 618                 }
 619               }
 620             }
 621             if( size_avail >= size_needed ) {
 622 #               ifdef USE_MUNMAP
 623                   if (!IS_MAPPED(hhdr)) {
 624                     GC_remap((ptr_t)hbp, size_avail);
 625                     hhdr -> hb_flags &= ~WAS_UNMAPPED;
 626                   }
 627 #               endif
 628                 /* hbp may be on the wrong freelist; the parameter n    */
 629                 /* is important.                                        */
 630                 hbp = GC_get_first_part(hbp, hhdr, size_needed, n);
 631                 break;
 632             }
 633         }
 634
 635     if (0 == hbp) return 0;
 636
 637     /* Notify virtual dirty bit implementation that we are about to write. */
 638         GC_write_hint(hbp);
 639
 640     /* Add it to map of valid blocks */
 641         if (!GC_install_counts(hbp, (word)size_needed)) return(0);
 642         /* This leaks memory under very rare conditions. */
 643
 644     /* Set up header */
 645         if (!setup_header(hhdr, sz, kind, flags)) {
 646             GC_remove_counts(hbp, (word)size_needed);
 647             return(0); /* ditto */
 648         }
 649
 650     /* Clear block if necessary */
 651         if (GC_debugging_started
 652             || sz > MAXOBJSZ && GC_obj_kinds[kind].ok_init) {
 653             BZERO(hbp + HDR_BYTES,  size_needed - HDR_BYTES);
 654         }
 655
 656     /* We just successfully allocated a block.  Restart count of        */
 657     /* consecutive failures.                                            */
 658     {
 659         extern unsigned GC_fail_count;
 660
 661         GC_fail_count = 0;
 662     }
 663
 664     GC_large_free_bytes -= size_needed;
 665
 666     GC_ASSERT(IS_MAPPED(hhdr));
 667     return( hbp );
 668 }
 669
 670 struct hblk * GC_freehblk_ptr = 0;  /* Search position hint for GC_freehblk */
 671
 672 /*
 673  * Free a heap block.
 674  *
 675  * Coalesce the block with its neighbors if possible.
 676  *
 677  * All mark words are assumed to be cleared.
 678  */
 679 void
 680 GC_freehblk(hbp)
 681 struct hblk *hbp;
 682 {
 683 struct hblk *next, *prev;
 684 hdr *hhdr, *prevhdr, *nexthdr;
 685 signed_word size;
 686
 687
 688     hhdr = HDR(hbp);
 689     size = hhdr->hb_sz;
 690     size = HBLKSIZE * OBJ_SZ_TO_BLOCKS(size);
 691     GC_remove_counts(hbp, (word)size);
 692     hhdr->hb_sz = size;
 693
 694     /* Check for duplicate deallocation in the easy case */
 695       if (HBLK_IS_FREE(hhdr)) {
 696         GC_printf1("Duplicate large block deallocation of 0x%lx\n",
 697                    (unsigned long) hbp);
 698       }
 699
 700     GC_ASSERT(IS_MAPPED(hhdr));
 701     GC_invalidate_map(hhdr);
 702     next = (struct hblk *)((word)hbp + size);
 703     nexthdr = HDR(next);
 704     prev = GC_free_block_ending_at(hbp);
 705     /* Coalesce with successor, if possible */
 706       if(0 != nexthdr && HBLK_IS_FREE(nexthdr) && IS_MAPPED(nexthdr)) {
 707         GC_remove_from_fl(nexthdr, FL_UNKNOWN);
 708         hhdr -> hb_sz += nexthdr -> hb_sz;
 709         GC_remove_header(next);
 710       }
 711     /* Coalesce with predecessor, if possible. */
 712       if (0 != prev) {
 713         prevhdr = HDR(prev);
 714         if (IS_MAPPED(prevhdr)) {
 715           GC_remove_from_fl(prevhdr, FL_UNKNOWN);
 716           prevhdr -> hb_sz += hhdr -> hb_sz;
 717           GC_remove_header(hbp);
 718           hbp = prev;
 719           hhdr = prevhdr;
 720         }
 721       }
 722
 723     GC_large_free_bytes += size;
 724     GC_add_to_fl(hbp, hhdr);
 725 }
 726