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