git.gag.com Git - fw/sdcc/blob - support/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(p)
  67 ptr_t p;
  68 {
  69     ptr_t base = GC_base(p);
  70     if (0 == base) {
  71         if (0 == p) {
  72             GC_err_printf0("in register");
  73         } else {
  74             GC_err_printf0("in root set");
  75         }
  76     } else {
  77         GC_err_printf0("in object at ");
  78         (*GC_print_heap_obj)(base);
  79     }
  80 }
  81
  82 void GC_bl_init()
  83 {
  84 # ifndef ALL_INTERIOR_POINTERS
  85     GC_old_normal_bl = (word *)
  86                          GC_scratch_alloc((word)(sizeof (page_hash_table)));
  87     GC_incomplete_normal_bl = (word *)GC_scratch_alloc
  88                                         ((word)(sizeof(page_hash_table)));
  89     if (GC_old_normal_bl == 0 || GC_incomplete_normal_bl == 0) {
  90         GC_err_printf0("Insufficient memory for black list\n");
  91         EXIT();
  92     }
  93     GC_clear_bl(GC_old_normal_bl);
  94     GC_clear_bl(GC_incomplete_normal_bl);
  95 # endif
  96     GC_old_stack_bl = (word *)GC_scratch_alloc((word)(sizeof(page_hash_table)));
  97     GC_incomplete_stack_bl = (word *)GC_scratch_alloc
  98                                         ((word)(sizeof(page_hash_table)));
  99     if (GC_old_stack_bl == 0 || GC_incomplete_stack_bl == 0) {
 100         GC_err_printf0("Insufficient memory for black list\n");
 101         EXIT();
 102     }
 103     GC_clear_bl(GC_old_stack_bl);
 104     GC_clear_bl(GC_incomplete_stack_bl);
 105 }
 106
 107 void GC_clear_bl(doomed)
 108 word *doomed;
 109 {
 110     BZERO(doomed, sizeof(page_hash_table));
 111 }
 112
 113 void GC_copy_bl(old, new)
 114 word *new, *old;
 115 {
 116     BCOPY(old, new, sizeof(page_hash_table));
 117 }
 118
 119 static word total_stack_black_listed();
 120
 121 /* Signal the completion of a collection.  Turn the incomplete black    */
 122 /* lists into new black lists, etc.                                     */
 123 void GC_promote_black_lists()
 124 {
 125     word * very_old_normal_bl = GC_old_normal_bl;
 126     word * very_old_stack_bl = GC_old_stack_bl;
 127
 128     GC_old_normal_bl = GC_incomplete_normal_bl;
 129     GC_old_stack_bl = GC_incomplete_stack_bl;
 130 #   ifndef ALL_INTERIOR_POINTERS
 131       GC_clear_bl(very_old_normal_bl);
 132 #   endif
 133     GC_clear_bl(very_old_stack_bl);
 134     GC_incomplete_normal_bl = very_old_normal_bl;
 135     GC_incomplete_stack_bl = very_old_stack_bl;
 136     GC_total_stack_black_listed = total_stack_black_listed();
 137 #   ifdef PRINTSTATS
 138         GC_printf1("%ld bytes in heap blacklisted for interior pointers\n",
 139                    (unsigned long)GC_total_stack_black_listed);
 140 #   endif
 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 }
 149
 150 void GC_unpromote_black_lists()
 151 {
 152 #   ifndef ALL_INTERIOR_POINTERS
 153       GC_copy_bl(GC_old_normal_bl, GC_incomplete_normal_bl);
 154 #   endif
 155     GC_copy_bl(GC_old_stack_bl, GC_incomplete_stack_bl);
 156 }
 157
 158 # ifndef ALL_INTERIOR_POINTERS
 159 /* P is not a valid pointer reference, but it falls inside      */
 160 /* the plausible heap bounds.                                   */
 161 /* Add it to the normal incomplete black list if appropriate.   */
 162 #ifdef PRINT_BLACK_LIST
 163   void GC_add_to_black_list_normal(p, source)
 164   ptr_t source;
 165 #else
 166   void GC_add_to_black_list_normal(p)
 167 #endif
 168 word p;
 169 {
 170     if (!(GC_modws_valid_offsets[p & (sizeof(word)-1)])) return;
 171     {
 172         register int index = PHT_HASH(p);
 173
 174         if (HDR(p) == 0 || get_pht_entry_from_index(GC_old_normal_bl, index)) {
 175 #           ifdef PRINT_BLACK_LIST
 176                 if (!get_pht_entry_from_index(GC_incomplete_normal_bl, index)) {
 177                   GC_err_printf2(
 178                         "Black listing (normal) 0x%lx referenced from 0x%lx ",
 179                         (unsigned long) p, (unsigned long) source);
 180                   GC_print_source_ptr(source);
 181                   GC_err_puts("\n");
 182                 }
 183 #           endif
 184             set_pht_entry_from_index(GC_incomplete_normal_bl, index);
 185         } /* else this is probably just an interior pointer to an allocated */
 186           /* object, and isn't worth black listing.                         */
 187     }
 188 }
 189 # endif
 190
 191 /* And the same for false pointers from the stack. */
 192 #ifdef PRINT_BLACK_LIST
 193   void GC_add_to_black_list_stack(p, source)
 194   ptr_t source;
 195 #else
 196   void GC_add_to_black_list_stack(p)
 197 #endif
 198 word p;
 199 {
 200     register int index = PHT_HASH(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_printf2(
 206                         "Black listing (stack) 0x%lx referenced from 0x%lx ",
 207                         (unsigned long)p, (unsigned long)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(h, len)
 225 struct hblk * h;
 226 word len;
 227 {
 228     register int index = PHT_HASH((word)h);
 229     register word i;
 230     word nblocks = divHBLKSZ(len);
 231
 232 #   ifndef ALL_INTERIOR_POINTERS
 233       if (get_pht_entry_from_index(GC_old_normal_bl, index)
 234           || get_pht_entry_from_index(GC_incomplete_normal_bl, index)) {
 235         return(h+1);
 236       }
 237 #   endif
 238
 239     for (i = 0; ; ) {
 240         if (GC_old_stack_bl[divWORDSZ(index)] == 0
 241             && GC_incomplete_stack_bl[divWORDSZ(index)] == 0) {
 242             /* An easy case */
 243             i += WORDSZ - modWORDSZ(index);
 244         } else {
 245           if (get_pht_entry_from_index(GC_old_stack_bl, index)
 246               || get_pht_entry_from_index(GC_incomplete_stack_bl, index)) {
 247             return(h+i+1);
 248           }
 249           i++;
 250         }
 251         if (i >= nblocks) break;
 252         index = PHT_HASH((word)(h+i));
 253     }
 254     return(0);
 255 }
 256
 257
 258 /* Return the number of blacklisted blocks in a given range.    */
 259 /* Used only for statistical purposes.                          */
 260 /* Looks only at the GC_incomplete_stack_bl.                    */
 261 word GC_number_stack_black_listed(start, endp1)
 262 struct hblk *start, *endp1;
 263 {
 264     register struct hblk * h;
 265     word result = 0;
 266
 267     for (h = start; h < endp1; h++) {
 268         register int index = PHT_HASH((word)h);
 269
 270         if (get_pht_entry_from_index(GC_old_stack_bl, index)) result++;
 271     }
 272     return(result);
 273 }
 274
 275
 276 /* Return the total number of (stack) black-listed bytes. */
 277 static word total_stack_black_listed()
 278 {
 279     register unsigned i;
 280     word total = 0;
 281
 282     for (i = 0; i < GC_n_heap_sects; i++) {
 283         struct hblk * start = (struct hblk *) GC_heap_sects[i].hs_start;
 284         word len = (word) GC_heap_sects[i].hs_bytes;
 285         struct hblk * endp1 = start + len/HBLKSIZE;
 286
 287         total += GC_number_stack_black_listed(start, endp1);
 288     }
 289     return(total * HBLKSIZE);
 290 }
 291