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 "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 void GC_default_print_heap_obj_proc(p)
  56 ptr_t p;
  57 {
  58     ptr_t base = GC_base(p);
  59
  60     GC_err_printf2("start: 0x%lx, appr. length: %ld", base, GC_size(base));
  61 }
  62
  63 void (*GC_print_heap_obj)(/* char * s, ptr_t p */) =
  64                                 GC_default_print_heap_obj_proc;
  65
  66 void GC_print_source_ptr(ptr_t p)
  67 {
  68     ptr_t base = GC_base(p);
  69     if (0 == base) {
  70         GC_err_printf0("in root set");
  71     } else {
  72         GC_err_printf0("in object at ");
  73         (*GC_print_heap_obj)(base);
  74     }
  75 }
  76
  77 void GC_bl_init()
  78 {
  79 # ifndef ALL_INTERIOR_POINTERS
  80     GC_old_normal_bl = (word *)
  81                          GC_scratch_alloc((word)(sizeof (page_hash_table)));
  82     GC_incomplete_normal_bl = (word *)GC_scratch_alloc
  83                                         ((word)(sizeof(page_hash_table)));
  84     if (GC_old_normal_bl == 0 || GC_incomplete_normal_bl == 0) {
  85         GC_err_printf0("Insufficient memory for black list\n");
  86         EXIT();
  87     }
  88     GC_clear_bl(GC_old_normal_bl);
  89     GC_clear_bl(GC_incomplete_normal_bl);
  90 # endif
  91     GC_old_stack_bl = (word *)GC_scratch_alloc((word)(sizeof(page_hash_table)));
  92     GC_incomplete_stack_bl = (word *)GC_scratch_alloc
  93                                         ((word)(sizeof(page_hash_table)));
  94     if (GC_old_stack_bl == 0 || GC_incomplete_stack_bl == 0) {
  95         GC_err_printf0("Insufficient memory for black list\n");
  96         EXIT();
  97     }
  98     GC_clear_bl(GC_old_stack_bl);
  99     GC_clear_bl(GC_incomplete_stack_bl);
 100 }
 101
 102 void GC_clear_bl(doomed)
 103 word *doomed;
 104 {
 105     BZERO(doomed, sizeof(page_hash_table));
 106 }
 107
 108 void GC_copy_bl(old, new)
 109 word *new, *old;
 110 {
 111     BCOPY(old, new, sizeof(page_hash_table));
 112 }
 113
 114 static word total_stack_black_listed();
 115
 116 /* Signal the completion of a collection.  Turn the incomplete black    */
 117 /* lists into new black lists, etc.                                     */
 118 void GC_promote_black_lists()
 119 {
 120     word * very_old_normal_bl = GC_old_normal_bl;
 121     word * very_old_stack_bl = GC_old_stack_bl;
 122
 123     GC_old_normal_bl = GC_incomplete_normal_bl;
 124     GC_old_stack_bl = GC_incomplete_stack_bl;
 125 #   ifndef ALL_INTERIOR_POINTERS
 126       GC_clear_bl(very_old_normal_bl);
 127 #   endif
 128     GC_clear_bl(very_old_stack_bl);
 129     GC_incomplete_normal_bl = very_old_normal_bl;
 130     GC_incomplete_stack_bl = very_old_stack_bl;
 131     GC_total_stack_black_listed = total_stack_black_listed();
 132 #   ifdef PRINTSTATS
 133         GC_printf1("%ld bytes in heap blacklisted for interior pointers\n",
 134                    (unsigned long)GC_total_stack_black_listed);
 135 #   endif
 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 }
 144
 145 void GC_unpromote_black_lists()
 146 {
 147 #   ifndef ALL_INTERIOR_POINTERS
 148       GC_copy_bl(GC_old_normal_bl, GC_incomplete_normal_bl);
 149 #   endif
 150     GC_copy_bl(GC_old_stack_bl, GC_incomplete_stack_bl);
 151 }
 152
 153 # ifndef ALL_INTERIOR_POINTERS
 154 /* P is not a valid pointer reference, but it falls inside      */
 155 /* the plausible heap bounds.                                   */
 156 /* Add it to the normal incomplete black list if appropriate.   */
 157 #ifdef PRINT_BLACK_LIST
 158   void GC_add_to_black_list_normal(p, source)
 159   ptr_t source;
 160 #else
 161   void GC_add_to_black_list_normal(p)
 162 #endif
 163 word p;
 164 {
 165     if (!(GC_modws_valid_offsets[p & (sizeof(word)-1)])) return;
 166     {
 167         register int index = PHT_HASH(p);
 168
 169         if (HDR(p) == 0 || get_pht_entry_from_index(GC_old_normal_bl, index)) {
 170 #           ifdef PRINT_BLACK_LIST
 171                 if (!get_pht_entry_from_index(GC_incomplete_normal_bl, index)) {
 172                   GC_err_printf2(
 173                         "Black listing (normal) 0x%lx referenced from 0x%lx ",
 174                         (unsigned long) p, (unsigned long) source);
 175                   GC_print_source_ptr(source);
 176                   GC_err_puts("\n");
 177                 }
 178 #           endif
 179             set_pht_entry_from_index(GC_incomplete_normal_bl, index);
 180         } /* else this is probably just an interior pointer to an allocated */
 181           /* object, and isn't worth black listing.                         */
 182     }
 183 }
 184 # endif
 185
 186 /* And the same for false pointers from the stack. */
 187 #ifdef PRINT_BLACK_LIST
 188   void GC_add_to_black_list_stack(p, source)
 189   ptr_t source;
 190 #else
 191   void GC_add_to_black_list_stack(p)
 192 #endif
 193 word p;
 194 {
 195     register int index = PHT_HASH(p);
 196
 197     if (HDR(p) == 0 || get_pht_entry_from_index(GC_old_stack_bl, index)) {
 198 #       ifdef PRINT_BLACK_LIST
 199             if (!get_pht_entry_from_index(GC_incomplete_stack_bl, index)) {
 200                   GC_err_printf2(
 201                         "Black listing (stack) 0x%lx referenced from 0x%lx ",
 202                         (unsigned long)p, (unsigned long)source);
 203                   GC_print_source_ptr(source);
 204                   GC_err_puts("\n");
 205             }
 206 #       endif
 207         set_pht_entry_from_index(GC_incomplete_stack_bl, index);
 208     }
 209 }
 210
 211 /*
 212  * Is the block starting at h of size len bytes black listed?   If so,
 213  * return the address of the next plausible r such that (r, len) might not
 214  * be black listed.  (R may not actually be in the heap.  We guarantee only
 215  * that every smaller value of r after h is also black listed.)
 216  * If (h,len) is not black listed, return 0.
 217  * Knows about the structure of the black list hash tables.
 218  */
 219 struct hblk * GC_is_black_listed(h, len)
 220 struct hblk * h;
 221 word len;
 222 {
 223     register int index = PHT_HASH((word)h);
 224     register word i;
 225     word nblocks = divHBLKSZ(len);
 226
 227 #   ifndef 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 #   endif
 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(start, endp1)
 257 struct hblk *start, *endp1;
 258 {
 259     register struct hblk * h;
 260     word result = 0;
 261
 262     for (h = start; h < endp1; h++) {
 263         register int index = PHT_HASH((word)h);
 264
 265         if (get_pht_entry_from_index(GC_old_stack_bl, index)) result++;
 266     }
 267     return(result);
 268 }
 269
 270
 271 /* Return the total number of (stack) black-listed bytes. */
 272 static word total_stack_black_listed()
 273 {
 274     register unsigned i;
 275     word total = 0;
 276
 277     for (i = 0; i < GC_n_heap_sects; i++) {
 278         struct hblk * start = (struct hblk *) GC_heap_sects[i].hs_start;
 279         word len = (word) GC_heap_sects[i].hs_bytes;
 280         struct hblk * endp1 = start + len/HBLKSIZE;
 281
 282         total += GC_number_stack_black_listed(start, endp1);
 283     }
 284     return(total * HBLKSIZE);
 285 }
 286