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