OSDN Git Service

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