blacklst.c 10.1 KB
Newer Older
1
/*
eg's avatar
eg committed
2 3 4 5 6 7 8 9 10 11 12 13
 * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
 * Copyright (c) 1991-1994 by Xerox Corporation.  All rights reserved.
 *
 * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
 * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
 *
 * Permission is hereby granted to use or copy this program
 * for any purpose,  provided the above notices are retained on all copies.
 * Permission to modify the code and to distribute modified code is granted,
 * provided the above notices are retained, and a notice that the code was
 * modified is included with the above copyright notice.
 */
14 15

#include "private/gc_priv.h"
eg's avatar
eg committed
16 17 18 19 20 21 22 23

/*
 * We maintain several hash tables of hblks that have had false hits.
 * Each contains one bit per hash bucket;  If any page in the bucket
 * has had a false hit, we assume that all of them have.
 * See the definition of page_hash_table in gc_private.h.
 * False hits from the stack(s) are much more dangerous than false hits
 * 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.
eg's avatar
eg committed
25
 */
26

eg's avatar
eg committed
27 28
/*
 * Externally callable routines are:
29

eg's avatar
eg committed
30 31 32 33 34 35 36 37
 * GC_add_to_black_list_normal
 * GC_add_to_black_list_stack
 * GC_promote_black_lists
 * GC_is_black_listed
 *
 * All require that the allocator lock is held.
 */

38 39 40 41 42 43 44 45 46 47
/* Pointers to individual tables.  We replace one table by another by   */
/* switching these pointers.                                            */
STATIC word * GC_old_normal_bl = NULL;
                /* Nonstack false references seen at last full          */
                /* collection.                                          */
STATIC word * GC_incomplete_normal_bl = NULL;
                /* Nonstack false references seen since last            */
                /* full collection.                                     */
STATIC word * GC_old_stack_bl = NULL;
STATIC word * GC_incomplete_stack_bl = NULL;
eg's avatar
eg committed
48

49 50
STATIC word GC_total_stack_black_listed = 0;
                        /* Number of bytes on stack blacklist.  */
eg's avatar
eg committed
51

52 53
GC_INNER word GC_black_list_spacing = MINHINCR * HBLKSIZE;
                        /* Initial rough guess. */
eg's avatar
eg committed
54

55
STATIC void GC_clear_bl(word *);
eg's avatar
eg committed
56

57
GC_INNER void GC_default_print_heap_obj_proc(ptr_t p)
eg's avatar
eg committed
58 59
{
    ptr_t base = GC_base(p);
60
    int kind = HDR(base)->hb_obj_kind;
eg's avatar
eg committed
61

62 63 64 65
    GC_err_printf("object at %p of appr. %lu bytes (%s)\n",
                  (void *)base, (unsigned long)GC_size(base),
                  kind == PTRFREE ? "atomic" :
                    IS_UNCOLLECTABLE(kind) ? "uncollectable" : "composite");
eg's avatar
eg committed
66 67
}

68
GC_INNER void (*GC_print_heap_obj)(ptr_t p) = GC_default_print_heap_obj_proc;
eg's avatar
eg committed
69

70
#ifdef PRINT_BLACK_LIST
71 72 73 74 75
  STATIC void GC_print_blacklisted_ptr(word p, ptr_t source,
                                       const char *kind_str)
  {
    ptr_t base = GC_base(source);

eg's avatar
eg committed
76
    if (0 == base) {
77 78 79
        GC_err_printf("Black listing (%s) %p referenced from %p in %s\n",
                      kind_str, (void *)p, (void *)source,
                      NULL != source ? "root set" : "register");
eg's avatar
eg committed
80
    } else {
81 82 83 84 85 86 87
        /* FIXME: We can't call the debug version of GC_print_heap_obj  */
        /* (with PRINT_CALL_CHAIN) here because the lock is held and    */
        /* the world is stopped.                                        */
        GC_err_printf("Black listing (%s) %p referenced from %p in"
                      " object at %p of appr. %lu bytes\n",
                      kind_str, (void *)p, (void *)source,
                      (void *)base, (unsigned long)GC_size(base));
eg's avatar
eg committed
88
    }
89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104
  }
#endif /* PRINT_BLACK_LIST */

GC_INNER void GC_bl_init_no_interiors(void)
{
  if (GC_incomplete_normal_bl == 0) {
    GC_old_normal_bl = (word *)GC_scratch_alloc(sizeof(page_hash_table));
    GC_incomplete_normal_bl = (word *)GC_scratch_alloc(
                                                  sizeof(page_hash_table));
    if (GC_old_normal_bl == 0 || GC_incomplete_normal_bl == 0) {
      GC_err_printf("Insufficient memory for black list\n");
      EXIT();
    }
    GC_clear_bl(GC_old_normal_bl);
    GC_clear_bl(GC_incomplete_normal_bl);
  }
eg's avatar
eg committed
105 106
}

107
GC_INNER void GC_bl_init(void)
eg's avatar
eg committed
108 109
{
    if (!GC_all_interior_pointers) {
110
      GC_bl_init_no_interiors();
eg's avatar
eg committed
111
    }
112 113 114
    GC_ASSERT(NULL == GC_old_stack_bl && NULL == GC_incomplete_stack_bl);
    GC_old_stack_bl = (word *)GC_scratch_alloc(sizeof(page_hash_table));
    GC_incomplete_stack_bl = (word *)GC_scratch_alloc(sizeof(page_hash_table));
eg's avatar
eg committed
115
    if (GC_old_stack_bl == 0 || GC_incomplete_stack_bl == 0) {
eg's avatar
eg committed
116
        GC_err_printf("Insufficient memory for black list\n");
eg's avatar
eg committed
117 118 119 120 121
        EXIT();
    }
    GC_clear_bl(GC_old_stack_bl);
    GC_clear_bl(GC_incomplete_stack_bl);
}
122 123

STATIC void GC_clear_bl(word *doomed)
eg's avatar
eg committed
124 125 126 127
{
    BZERO(doomed, sizeof(page_hash_table));
}

128
STATIC void GC_copy_bl(word *old, word *new)
eg's avatar
eg committed
129 130 131 132
{
    BCOPY(old, new, sizeof(page_hash_table));
}

eg's avatar
eg committed
133
static word total_stack_black_listed(void);
eg's avatar
eg committed
134

135 136 137
/* Signal the completion of a collection.  Turn the incomplete black    */
/* lists into new black lists, etc.                                     */
GC_INNER void GC_promote_black_lists(void)
eg's avatar
eg committed
138 139 140
{
    word * very_old_normal_bl = GC_old_normal_bl;
    word * very_old_stack_bl = GC_old_stack_bl;
141

eg's avatar
eg committed
142 143 144 145 146 147 148 149 150
    GC_old_normal_bl = GC_incomplete_normal_bl;
    GC_old_stack_bl = GC_incomplete_stack_bl;
    if (!GC_all_interior_pointers) {
      GC_clear_bl(very_old_normal_bl);
    }
    GC_clear_bl(very_old_stack_bl);
    GC_incomplete_normal_bl = very_old_normal_bl;
    GC_incomplete_stack_bl = very_old_stack_bl;
    GC_total_stack_black_listed = total_stack_black_listed();
151 152 153
    GC_VERBOSE_LOG_PRINTF(
                "%lu bytes in heap blacklisted for interior pointers\n",
                (unsigned long)GC_total_stack_black_listed);
eg's avatar
eg committed
154 155
    if (GC_total_stack_black_listed != 0) {
        GC_black_list_spacing =
156
                HBLKSIZE*(GC_heapsize/GC_total_stack_black_listed);
eg's avatar
eg committed
157 158
    }
    if (GC_black_list_spacing < 3 * HBLKSIZE) {
159
        GC_black_list_spacing = 3 * HBLKSIZE;
eg's avatar
eg committed
160 161
    }
    if (GC_black_list_spacing > MAXHINCR * HBLKSIZE) {
162 163 164 165 166
        GC_black_list_spacing = MAXHINCR * HBLKSIZE;
        /* Makes it easier to allocate really huge blocks, which otherwise */
        /* may have problems with nonuniform blacklist distributions.      */
        /* This way we should always succeed immediately after growing the */
        /* heap.                                                           */
eg's avatar
eg committed
167 168 169
    }
}

170
GC_INNER void GC_unpromote_black_lists(void)
eg's avatar
eg committed
171 172 173 174 175 176 177
{
    if (!GC_all_interior_pointers) {
      GC_copy_bl(GC_old_normal_bl, GC_incomplete_normal_bl);
    }
    GC_copy_bl(GC_old_stack_bl, GC_incomplete_stack_bl);
}

178 179 180
/* P is not a valid pointer reference, but it falls inside      */
/* the plausible heap bounds.                                   */
/* Add it to the normal incomplete black list if appropriate.   */
eg's avatar
eg committed
181
#ifdef PRINT_BLACK_LIST
182
  GC_INNER void GC_add_to_black_list_normal(word p, ptr_t source)
eg's avatar
eg committed
183
#else
184
  GC_INNER void GC_add_to_black_list_normal(word p)
eg's avatar
eg committed
185 186
#endif
{
187 188 189 190 191 192 193 194 195 196 197 198 199
  if (GC_modws_valid_offsets[p & (sizeof(word)-1)]) {
    word index = PHT_HASH((word)p);

    if (HDR(p) == 0 || get_pht_entry_from_index(GC_old_normal_bl, index)) {
#     ifdef PRINT_BLACK_LIST
        if (!get_pht_entry_from_index(GC_incomplete_normal_bl, index)) {
          GC_print_blacklisted_ptr(p, source, "normal");
        }
#     endif
      set_pht_entry_from_index(GC_incomplete_normal_bl, index);
    } /* else this is probably just an interior pointer to an allocated */
      /* object, and isn't worth black listing.                         */
  }
eg's avatar
eg committed
200 201 202 203
}

/* And the same for false pointers from the stack. */
#ifdef PRINT_BLACK_LIST
204
  GC_INNER void GC_add_to_black_list_stack(word p, ptr_t source)
eg's avatar
eg committed
205
#else
206
  GC_INNER void GC_add_to_black_list_stack(word p)
eg's avatar
eg committed
207 208
#endif
{
209 210 211 212 213 214 215 216 217 218
  word index = PHT_HASH((word)p);

  if (HDR(p) == 0 || get_pht_entry_from_index(GC_old_stack_bl, index)) {
#   ifdef PRINT_BLACK_LIST
      if (!get_pht_entry_from_index(GC_incomplete_stack_bl, index)) {
        GC_print_blacklisted_ptr(p, source, "stack");
      }
#   endif
    set_pht_entry_from_index(GC_incomplete_stack_bl, index);
  }
eg's avatar
eg committed
219 220 221 222 223 224 225 226 227 228
}

/*
 * Is the block starting at h of size len bytes black listed?   If so,
 * return the address of the next plausible r such that (r, len) might not
 * be black listed.  (R may not actually be in the heap.  We guarantee only
 * that every smaller value of r after h is also black listed.)
 * If (h,len) is not black listed, return 0.
 * Knows about the structure of the black list hash tables.
 */
eg's avatar
eg committed
229
struct hblk * GC_is_black_listed(struct hblk *h, word len)
eg's avatar
eg committed
230
{
231 232
    word index = PHT_HASH((word)h);
    word i;
233
    word nblocks;
eg's avatar
eg committed
234

235 236 237 238
    if (!GC_all_interior_pointers
        && (get_pht_entry_from_index(GC_old_normal_bl, index)
            || get_pht_entry_from_index(GC_incomplete_normal_bl, index))) {
      return (h+1);
eg's avatar
eg committed
239
    }
240 241 242

    nblocks = divHBLKSZ(len);
    for (i = 0;;) {
eg's avatar
eg committed
243 244 245
        if (GC_old_stack_bl[divWORDSZ(index)] == 0
            && GC_incomplete_stack_bl[divWORDSZ(index)] == 0) {
            /* An easy case */
246
          i += WORDSZ - modWORDSZ(index);
eg's avatar
eg committed
247 248 249 250 251 252 253 254 255 256 257 258 259
        } else {
          if (get_pht_entry_from_index(GC_old_stack_bl, index)
              || get_pht_entry_from_index(GC_incomplete_stack_bl, index)) {
            return(h+i+1);
          }
          i++;
        }
        if (i >= nblocks) break;
        index = PHT_HASH((word)(h+i));
    }
    return(0);
}

260 261 262 263 264
/* Return the number of blacklisted blocks in a given range.    */
/* Used only for statistical purposes.                          */
/* Looks only at the GC_incomplete_stack_bl.                    */
STATIC word GC_number_stack_black_listed(struct hblk *start,
                                         struct hblk *endp1)
eg's avatar
eg committed
265 266 267
{
    register struct hblk * h;
    word result = 0;
268 269

    for (h = start; (word)h < (word)endp1; h++) {
270
        word index = PHT_HASH((word)h);
271

eg's avatar
eg committed
272 273 274 275 276 277
        if (get_pht_entry_from_index(GC_old_stack_bl, index)) result++;
    }
    return(result);
}

/* Return the total number of (stack) black-listed bytes. */
eg's avatar
eg committed
278
static word total_stack_black_listed(void)
eg's avatar
eg committed
279 280 281
{
    register unsigned i;
    word total = 0;
282

eg's avatar
eg committed
283
    for (i = 0; i < GC_n_heap_sects; i++) {
284 285 286 287
        struct hblk * start = (struct hblk *) GC_heap_sects[i].hs_start;
        struct hblk * endp1 = start + divHBLKSZ(GC_heap_sects[i].hs_bytes);

        total += GC_number_stack_black_listed(start, endp1);
eg's avatar
eg committed
288 289 290
    }
    return(total * HBLKSIZE);
}