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