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