blacklst.c

   1 /*
   2  * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
   3  * Copyright (c) 1991-1994 by Xerox Corporation.  All rights reserved.
   4  *
   5  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
   6  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
   7  *
   8  * Permission is hereby granted to use or copy this program
   9  * for any purpose,  provided the above notices are retained on all copies.
  10  * Permission to modify the code and to distribute modified code is granted,
  11  * provided the above notices are retained, and a notice that the code was
  12  * modified is included with the above copyright notice.
  13  */
  14 /* Boehm, August 9, 1995 6:09 pm PDT */
  15 # include "private/gc_priv.h"
  16
  17 /*
  18  * We maintain several hash tables of hblks that have had false hits.
  19  * Each contains one bit per hash bucket;  If any page in the bucket
  20  * has had a false hit, we assume that all of them have.
  21  * See the definition of page_hash_table in gc_private.h.
  22  * False hits from the stack(s) are much more dangerous than false hits
  23  * from elsewhere, since the former can pin a large object that spans the
  24  * block, eventhough it does not start on the dangerous block.
  25  */
  26
  27 /*
  28  * Externally callable routines are:
  29
  30  * GC_add_to_black_list_normal
  31  * GC_add_to_black_list_stack
  32  * GC_promote_black_lists
  33  * GC_is_black_listed
  34  *
  35  * All require that the allocator lock is held.
  36  */
  37
  38 /* Pointers to individual tables.  We replace one table by another by   */
  39 /* switching these pointers.                                            */
  40 word * GC_old_normal_bl;
  41                 /* Nonstack false references seen at last full          */
  42                 /* collection.                                          */
  43 word * GC_incomplete_normal_bl;
  44                 /* Nonstack false references seen since last            */
  45                 /* full collection.                                     */
  46 word * GC_old_stack_bl;
  47 word * GC_incomplete_stack_bl;
  48
  49 word GC_total_stack_black_listed;
  50
  51 word GC_black_list_spacing = MINHINCR*HBLKSIZE;  /* Initial rough guess */
  52
  53 void GC_clear_bl(word *);
  54
  55 void GC_default_print_heap_obj_proc(ptr_t p)
  56 {
  57     ptr_t base = GC_base(p);
  58
  59     GC_err_printf("start: %p, appr. length: %ld", base,
  60                   (unsigned long)GC_size(base));
  61 }
  62
  63 void (*GC_print_heap_obj) (ptr_t p) = GC_default_print_heap_obj_proc;
  64
  65 void GC_print_source_ptr(ptr_t p)
  66 {
  67     ptr_t base = GC_base(p);
  68     if (0 == base) {
  69         if (0 == p) {
  70             GC_err_printf("in register");
  71         } else {
  72             GC_err_printf("in root set");
  73         }
  74     } else {
  75         GC_err_printf("in object at ");
  76         (*GC_print_heap_obj)(base);
  77     }
  78 }
  79
  80 void GC_bl_init(void)
  81 {
  82     if (!GC_all_interior_pointers) {
  83       GC_old_normal_bl = (word *)
  84                          GC_scratch_alloc((word)(sizeof (page_hash_table)));
  85       GC_incomplete_normal_bl = (word *)GC_scratch_alloc
  86                                         ((word)(sizeof(page_hash_table)));
  87       if (GC_old_normal_bl == 0 || GC_incomplete_normal_bl == 0) {
  88         GC_err_printf("Insufficient memory for black list\n");
  89         EXIT();
  90       }
  91       GC_clear_bl(GC_old_normal_bl);
  92       GC_clear_bl(GC_incomplete_normal_bl);
  93     }
  94     GC_old_stack_bl = (word *)GC_scratch_alloc((word)(sizeof(page_hash_table)));
  95     GC_incomplete_stack_bl = (word *)GC_scratch_alloc
  96                                         ((word)(sizeof(page_hash_table)));
  97     if (GC_old_stack_bl == 0 || GC_incomplete_stack_bl == 0) {
  98         GC_err_printf("Insufficient memory for black list\n");
  99         EXIT();
 100     }
 101     GC_clear_bl(GC_old_stack_bl);
 102     GC_clear_bl(GC_incomplete_stack_bl);
 103 }
 104
 105 void GC_clear_bl(word *doomed)
 106 {
 107     BZERO(doomed, sizeof(page_hash_table));
 108 }
 109
 110 void GC_copy_bl(word *old, word *new)
 111 {
 112     BCOPY(old, new, sizeof(page_hash_table));
 113 }
 114
 115 static word total_stack_black_listed(void);
 116
 117 /* Signal the completion of a collection.  Turn the incomplete black    */
 118 /* lists into new black lists, etc.                                     */
 119 void GC_promote_black_lists(void)
 120 {
 121     word * very_old_normal_bl = GC_old_normal_bl;
 122     word * very_old_stack_bl = GC_old_stack_bl;
 123
 124     GC_old_normal_bl = GC_incomplete_normal_bl;
 125     GC_old_stack_bl = GC_incomplete_stack_bl;
 126     if (!GC_all_interior_pointers) {
 127       GC_clear_bl(very_old_normal_bl);
 128     }
 129     GC_clear_bl(very_old_stack_bl);
 130     GC_incomplete_normal_bl = very_old_normal_bl;
 131     GC_incomplete_stack_bl = very_old_stack_bl;
 132     GC_total_stack_black_listed = total_stack_black_listed();
 133     if (GC_print_stats == VERBOSE)
 134         GC_log_printf("%ld bytes in heap blacklisted for interior pointers\n",
 135                       (unsigned long)GC_total_stack_black_listed);
 136     if (GC_total_stack_black_listed != 0) {
 137         GC_black_list_spacing =
 138                 HBLKSIZE*(GC_heapsize/GC_total_stack_black_listed);
 139     }
 140     if (GC_black_list_spacing < 3 * HBLKSIZE) {
 141         GC_black_list_spacing = 3 * HBLKSIZE;
 142     }
 143     if (GC_black_list_spacing > MAXHINCR * HBLKSIZE) {
 144         GC_black_list_spacing = MAXHINCR * HBLKSIZE;
 145         /* Makes it easier to allocate really huge blocks, which otherwise */
 146         /* may have problems with nonuniform blacklist distributions.      */
 147         /* This way we should always succeed immediately after growing the */
 148         /* heap.                                                           */
 149     }
 150 }
 151
 152 void GC_unpromote_black_lists(void)
 153 {
 154     if (!GC_all_interior_pointers) {
 155       GC_copy_bl(GC_old_normal_bl, GC_incomplete_normal_bl);
 156     }
 157     GC_copy_bl(GC_old_stack_bl, GC_incomplete_stack_bl);
 158 }
 159
 160 /* P is not a valid pointer reference, but it falls inside      */
 161 /* the plausible heap bounds.                                   */
 162 /* Add it to the normal incomplete black list if appropriate.   */
 163 #ifdef PRINT_BLACK_LIST
 164   void GC_add_to_black_list_normal(word p, ptr_t source)
 165 #else
 166   void GC_add_to_black_list_normal(word p)
 167 #endif
 168 {
 169     if (!(GC_modws_valid_offsets[p & (sizeof(word)-1)])) return;
 170     {
 171         word index = PHT_HASH((word)p);
 172
 173         if (HDR(p) == 0 || get_pht_entry_from_index(GC_old_normal_bl, index)) {
 174 #           ifdef PRINT_BLACK_LIST
 175                 if (!get_pht_entry_from_index(GC_incomplete_normal_bl, index)) {
 176                   GC_err_printf(
 177                         "Black listing (normal) %p referenced from %p ",
 178                         (ptr_t) p, source);
 179                   GC_print_source_ptr(source);
 180                   GC_err_puts("\n");
 181                 }
 182 #           endif
 183             set_pht_entry_from_index(GC_incomplete_normal_bl, index);
 184         } /* else this is probably just an interior pointer to an allocated */
 185           /* object, and isn't worth black listing.                         */
 186     }
 187 }
 188
 189 /* And the same for false pointers from the stack. */
 190 #ifdef PRINT_BLACK_LIST
 191   void GC_add_to_black_list_stack(word p, ptr_t source)
 192   ptr_t source;
 193 #else
 194   void GC_add_to_black_list_stack(word p)
 195 #endif
 196 {
 197     word index = PHT_HASH((word)p);
 198
 199     if (HDR(p) == 0 || get_pht_entry_from_index(GC_old_stack_bl, index)) {
 200 #       ifdef PRINT_BLACK_LIST
 201             if (!get_pht_entry_from_index(GC_incomplete_stack_bl, index)) {
 202                   GC_err_printf(
 203                         "Black listing (stack) %p referenced from %p ",
 204                         (ptr_t)p, source);
 205                   GC_print_source_ptr(source);
 206                   GC_err_puts("\n");
 207             }
 208 #       endif
 209         set_pht_entry_from_index(GC_incomplete_stack_bl, index);
 210     }
 211 }
 212
 213 /*
 214  * Is the block starting at h of size len bytes black listed?   If so,
 215  * return the address of the next plausible r such that (r, len) might not
 216  * be black listed.  (R may not actually be in the heap.  We guarantee only
 217  * that every smaller value of r after h is also black listed.)
 218  * If (h,len) is not black listed, return 0.
 219  * Knows about the structure of the black list hash tables.
 220  */
 221 struct hblk * GC_is_black_listed(struct hblk *h, word len)
 222 {
 223     word index = PHT_HASH((word)h);
 224     word i;
 225     word nblocks = divHBLKSZ(len);
 226
 227     if (!GC_all_interior_pointers) {
 228       if (get_pht_entry_from_index(GC_old_normal_bl, index)
 229           || get_pht_entry_from_index(GC_incomplete_normal_bl, index)) {
 230         return(h+1);
 231       }
 232     }
 233
 234     for (i = 0; ; ) {
 235         if (GC_old_stack_bl[divWORDSZ(index)] == 0
 236             && GC_incomplete_stack_bl[divWORDSZ(index)] == 0) {
 237             /* An easy case */
 238             i += WORDSZ - modWORDSZ(index);
 239         } else {
 240           if (get_pht_entry_from_index(GC_old_stack_bl, index)
 241               || get_pht_entry_from_index(GC_incomplete_stack_bl, index)) {
 242             return(h+i+1);
 243           }
 244           i++;
 245         }
 246         if (i >= nblocks) break;
 247         index = PHT_HASH((word)(h+i));
 248     }
 249     return(0);
 250 }
 251
 252
 253 /* Return the number of blacklisted blocks in a given range.    */
 254 /* Used only for statistical purposes.                          */
 255 /* Looks only at the GC_incomplete_stack_bl.                    */
 256 word GC_number_stack_black_listed(struct hblk *start, struct hblk *endp1)
 257 {
 258     register struct hblk * h;
 259     word result = 0;
 260
 261     for (h = start; h < endp1; h++) {
 262         word index = PHT_HASH((word)h);
 263
 264         if (get_pht_entry_from_index(GC_old_stack_bl, index)) result++;
 265     }
 266     return(result);
 267 }
 268
 269
 270 /* Return the total number of (stack) black-listed bytes. */
 271 static word total_stack_black_listed(void)
 272 {
 273     register unsigned i;
 274     word total = 0;
 275
 276     for (i = 0; i < GC_n_heap_sects; i++) {
 277         struct hblk * start = (struct hblk *) GC_heap_sects[i].hs_start;
 278         size_t len = (word) GC_heap_sects[i].hs_bytes;
 279         struct hblk * endp1 = start + len/HBLKSIZE;
 280
 281         total += GC_number_stack_black_listed(start, endp1);
 282     }
 283     return(total * HBLKSIZE);
 284 }
 285