gc-7.2/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
  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 STATIC word * GC_old_normal_bl = NULL;
  41                 /* Nonstack false references seen at last full          */
  42                 /* collection.                                          */
  43 STATIC word * GC_incomplete_normal_bl = NULL;
  44                 /* Nonstack false references seen since last            */
  45                 /* full collection.                                     */
  46 STATIC word * GC_old_stack_bl = NULL;
  47 STATIC word * GC_incomplete_stack_bl = NULL;
  48
  49 STATIC word GC_total_stack_black_listed = 0;
  50                         /* Number of bytes on stack blacklist.  */
  51
  52 GC_INNER word GC_black_list_spacing = MINHINCR * HBLKSIZE;
  53                         /* Initial rough guess. */
  54
  55 STATIC void GC_clear_bl(word *);
  56
  57 GC_INNER void GC_default_print_heap_obj_proc(ptr_t p)
  58 {
  59     ptr_t base = GC_base(p);
  60     GC_err_printf("start: %p, appr. length: %ld", base,
  61                   (unsigned long)GC_size(base));
  62 }
  63
  64 GC_INNER void (*GC_print_heap_obj)(ptr_t p) = GC_default_print_heap_obj_proc;
  65
  66 #ifdef PRINT_BLACK_LIST
  67 STATIC void GC_print_source_ptr(ptr_t p)
  68 {
  69     ptr_t base = GC_base(p);
  70     if (0 == base) {
  71         if (0 == p) {
  72             GC_err_printf("in register");
  73         } else {
  74             GC_err_printf("in root set");
  75         }
  76     } else {
  77         GC_err_printf("in object at ");
  78         /* FIXME: We can't call the debug version of GC_print_heap_obj  */
  79         /* (with PRINT_CALL_CHAIN) here because the lock is held and    */
  80         /* the world is stopped.                                        */
  81         GC_default_print_heap_obj_proc(base);
  82     }
  83 }
  84 #endif
  85
  86 GC_INNER void GC_bl_init_no_interiors(void)
  87 {
  88   if (GC_incomplete_normal_bl == 0) {
  89     GC_old_normal_bl = (word *)GC_scratch_alloc(sizeof(page_hash_table));
  90     GC_incomplete_normal_bl = (word *)GC_scratch_alloc(
  91                                                   sizeof(page_hash_table));
  92     if (GC_old_normal_bl == 0 || GC_incomplete_normal_bl == 0) {
  93       GC_err_printf("Insufficient memory for black list\n");
  94       EXIT();
  95     }
  96     GC_clear_bl(GC_old_normal_bl);
  97     GC_clear_bl(GC_incomplete_normal_bl);
  98   }
  99 }
 100
 101 GC_INNER void GC_bl_init(void)
 102 {
 103     if (!GC_all_interior_pointers) {
 104       GC_bl_init_no_interiors();
 105     }
 106     GC_old_stack_bl = (word *)GC_scratch_alloc(sizeof(page_hash_table));
 107     GC_incomplete_stack_bl = (word *)GC_scratch_alloc(sizeof(page_hash_table));
 108     if (GC_old_stack_bl == 0 || GC_incomplete_stack_bl == 0) {
 109         GC_err_printf("Insufficient memory for black list\n");
 110         EXIT();
 111     }
 112     GC_clear_bl(GC_old_stack_bl);
 113     GC_clear_bl(GC_incomplete_stack_bl);
 114 }
 115
 116 STATIC void GC_clear_bl(word *doomed)
 117 {
 118     BZERO(doomed, sizeof(page_hash_table));
 119 }
 120
 121 STATIC void GC_copy_bl(word *old, word *new)
 122 {
 123     BCOPY(old, new, sizeof(page_hash_table));
 124 }
 125
 126 static word total_stack_black_listed(void);
 127
 128 /* Signal the completion of a collection.  Turn the incomplete black    */
 129 /* lists into new black lists, etc.                                     */
 130 GC_INNER void GC_promote_black_lists(void)
 131 {
 132     word * very_old_normal_bl = GC_old_normal_bl;
 133     word * very_old_stack_bl = GC_old_stack_bl;
 134
 135     GC_old_normal_bl = GC_incomplete_normal_bl;
 136     GC_old_stack_bl = GC_incomplete_stack_bl;
 137     if (!GC_all_interior_pointers) {
 138       GC_clear_bl(very_old_normal_bl);
 139     }
 140     GC_clear_bl(very_old_stack_bl);
 141     GC_incomplete_normal_bl = very_old_normal_bl;
 142     GC_incomplete_stack_bl = very_old_stack_bl;
 143     GC_total_stack_black_listed = total_stack_black_listed();
 144     if (GC_print_stats == VERBOSE)
 145         GC_log_printf("%ld bytes in heap blacklisted for interior pointers\n",
 146                       (unsigned long)GC_total_stack_black_listed);
 147     if (GC_total_stack_black_listed != 0) {
 148         GC_black_list_spacing =
 149                 HBLKSIZE*(GC_heapsize/GC_total_stack_black_listed);
 150     }
 151     if (GC_black_list_spacing < 3 * HBLKSIZE) {
 152         GC_black_list_spacing = 3 * HBLKSIZE;
 153     }
 154     if (GC_black_list_spacing > MAXHINCR * HBLKSIZE) {
 155         GC_black_list_spacing = MAXHINCR * HBLKSIZE;
 156         /* Makes it easier to allocate really huge blocks, which otherwise */
 157         /* may have problems with nonuniform blacklist distributions.      */
 158         /* This way we should always succeed immediately after growing the */
 159         /* heap.                                                           */
 160     }
 161 }
 162
 163 GC_INNER void GC_unpromote_black_lists(void)
 164 {
 165     if (!GC_all_interior_pointers) {
 166       GC_copy_bl(GC_old_normal_bl, GC_incomplete_normal_bl);
 167     }
 168     GC_copy_bl(GC_old_stack_bl, GC_incomplete_stack_bl);
 169 }
 170
 171 /* P is not a valid pointer reference, but it falls inside      */
 172 /* the plausible heap bounds.                                   */
 173 /* Add it to the normal incomplete black list if appropriate.   */
 174 #ifdef PRINT_BLACK_LIST
 175   GC_INNER void GC_add_to_black_list_normal(word p, ptr_t source)
 176 #else
 177   GC_INNER void GC_add_to_black_list_normal(word p)
 178 #endif
 179 {
 180   if (GC_modws_valid_offsets[p & (sizeof(word)-1)]) {
 181     word index = PHT_HASH((word)p);
 182
 183     if (HDR(p) == 0 || get_pht_entry_from_index(GC_old_normal_bl, index)) {
 184 #     ifdef PRINT_BLACK_LIST
 185         if (!get_pht_entry_from_index(GC_incomplete_normal_bl, index)) {
 186           GC_err_printf("Black listing (normal) %p referenced from %p ",
 187                         (ptr_t)p, source);
 188           GC_print_source_ptr(source);
 189           GC_err_puts("\n");
 190         }
 191 #     endif
 192       set_pht_entry_from_index(GC_incomplete_normal_bl, index);
 193     } /* else this is probably just an interior pointer to an allocated */
 194       /* object, and isn't worth black listing.                         */
 195   }
 196 }
 197
 198 /* And the same for false pointers from the stack. */
 199 #ifdef PRINT_BLACK_LIST
 200   GC_INNER void GC_add_to_black_list_stack(word p, ptr_t source)
 201 #else
 202   GC_INNER void GC_add_to_black_list_stack(word p)
 203 #endif
 204 {
 205   word index = PHT_HASH((word)p);
 206
 207   if (HDR(p) == 0 || get_pht_entry_from_index(GC_old_stack_bl, index)) {
 208 #   ifdef PRINT_BLACK_LIST
 209       if (!get_pht_entry_from_index(GC_incomplete_stack_bl, index)) {
 210         GC_err_printf("Black listing (stack) %p referenced from %p ",
 211                       (ptr_t)p, source);
 212         GC_print_source_ptr(source);
 213         GC_err_puts("\n");
 214       }
 215 #   endif
 216     set_pht_entry_from_index(GC_incomplete_stack_bl, index);
 217   }
 218 }
 219
 220 /*
 221  * Is the block starting at h of size len bytes black listed?   If so,
 222  * return the address of the next plausible r such that (r, len) might not
 223  * be black listed.  (R may not actually be in the heap.  We guarantee only
 224  * that every smaller value of r after h is also black listed.)
 225  * If (h,len) is not black listed, return 0.
 226  * Knows about the structure of the black list hash tables.
 227  */
 228 struct hblk * GC_is_black_listed(struct hblk *h, word len)
 229 {
 230     word index = PHT_HASH((word)h);
 231     word i;
 232     word nblocks;
 233
 234     if (!GC_all_interior_pointers
 235         && (get_pht_entry_from_index(GC_old_normal_bl, index)
 236             || get_pht_entry_from_index(GC_incomplete_normal_bl, index))) {
 237       return (h+1);
 238     }
 239
 240     nblocks = divHBLKSZ(len);
 241     for (i = 0;;) {
 242         if (GC_old_stack_bl[divWORDSZ(index)] == 0
 243             && GC_incomplete_stack_bl[divWORDSZ(index)] == 0) {
 244             /* An easy case */
 245           i += WORDSZ - modWORDSZ(index);
 246         } else {
 247           if (get_pht_entry_from_index(GC_old_stack_bl, index)
 248               || get_pht_entry_from_index(GC_incomplete_stack_bl, index)) {
 249             return(h+i+1);
 250           }
 251           i++;
 252         }
 253         if (i >= nblocks) break;
 254         index = PHT_HASH((word)(h+i));
 255     }
 256     return(0);
 257 }
 258
 259 /* Return the number of blacklisted blocks in a given range.    */
 260 /* Used only for statistical purposes.                          */
 261 /* Looks only at the GC_incomplete_stack_bl.                    */
 262 STATIC word GC_number_stack_black_listed(struct hblk *start,
 263                                          struct hblk *endp1)
 264 {
 265     register struct hblk * h;
 266     word result = 0;
 267
 268     for (h = start; h < endp1; h++) {
 269         word index = PHT_HASH((word)h);
 270
 271         if (get_pht_entry_from_index(GC_old_stack_bl, index)) result++;
 272     }
 273     return(result);
 274 }
 275
 276 /* Return the total number of (stack) black-listed bytes. */
 277 static word total_stack_black_listed(void)
 278 {
 279     register unsigned i;
 280     word total = 0;
 281
 282     for (i = 0; i < GC_n_heap_sects; i++) {
 283         struct hblk * start = (struct hblk *) GC_heap_sects[i].hs_start;
 284         struct hblk * endp1 = start + GC_heap_sects[i].hs_bytes/HBLKSIZE;
 285
 286         total += GC_number_stack_black_listed(start, endp1);
 287     }
 288     return(total * HBLKSIZE);
 289 }