Annotation of OpenXM_contrib2/asir2000/gc5.3/blacklst.c, Revision 1.1
1.1 ! noro 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: if (GC_black_list_spacing > MAXHINCR * HBLKSIZE) {
! 149: GC_black_list_spacing = MAXHINCR * HBLKSIZE;
! 150: /* Makes it easier to allocate really huge blocks, which otherwise */
! 151: /* may have problems with nonuniform blacklist distributions. */
! 152: /* This way we should always succeed immediately after growing the */
! 153: /* heap. */
! 154: }
! 155: }
! 156:
! 157: void GC_unpromote_black_lists()
! 158: {
! 159: # ifndef ALL_INTERIOR_POINTERS
! 160: GC_copy_bl(GC_old_normal_bl, GC_incomplete_normal_bl);
! 161: # endif
! 162: GC_copy_bl(GC_old_stack_bl, GC_incomplete_stack_bl);
! 163: }
! 164:
! 165: # ifndef ALL_INTERIOR_POINTERS
! 166: /* P is not a valid pointer reference, but it falls inside */
! 167: /* the plausible heap bounds. */
! 168: /* Add it to the normal incomplete black list if appropriate. */
! 169: #ifdef PRINT_BLACK_LIST
! 170: void GC_add_to_black_list_normal(p, source)
! 171: ptr_t source;
! 172: #else
! 173: void GC_add_to_black_list_normal(p)
! 174: #endif
! 175: word p;
! 176: {
! 177: if (!(GC_modws_valid_offsets[p & (sizeof(word)-1)])) return;
! 178: {
! 179: register int index = PHT_HASH(p);
! 180:
! 181: if (HDR(p) == 0 || get_pht_entry_from_index(GC_old_normal_bl, index)) {
! 182: # ifdef PRINT_BLACK_LIST
! 183: if (!get_pht_entry_from_index(GC_incomplete_normal_bl, index)) {
! 184: GC_err_printf2(
! 185: "Black listing (normal) 0x%lx referenced from 0x%lx ",
! 186: (unsigned long) p, (unsigned long) source);
! 187: GC_print_source_ptr(source);
! 188: GC_err_puts("\n");
! 189: }
! 190: # endif
! 191: set_pht_entry_from_index(GC_incomplete_normal_bl, index);
! 192: } /* else this is probably just an interior pointer to an allocated */
! 193: /* object, and isn't worth black listing. */
! 194: }
! 195: }
! 196: # endif
! 197:
! 198: /* And the same for false pointers from the stack. */
! 199: #ifdef PRINT_BLACK_LIST
! 200: void GC_add_to_black_list_stack(p, source)
! 201: ptr_t source;
! 202: #else
! 203: void GC_add_to_black_list_stack(p)
! 204: #endif
! 205: word p;
! 206: {
! 207: register int index = PHT_HASH(p);
! 208:
! 209: if (HDR(p) == 0 || get_pht_entry_from_index(GC_old_stack_bl, index)) {
! 210: # ifdef PRINT_BLACK_LIST
! 211: if (!get_pht_entry_from_index(GC_incomplete_stack_bl, index)) {
! 212: GC_err_printf2(
! 213: "Black listing (stack) 0x%lx referenced from 0x%lx ",
! 214: (unsigned long)p, (unsigned long)source);
! 215: GC_print_source_ptr(source);
! 216: GC_err_puts("\n");
! 217: }
! 218: # endif
! 219: set_pht_entry_from_index(GC_incomplete_stack_bl, index);
! 220: }
! 221: }
! 222:
! 223: /*
! 224: * Is the block starting at h of size len bytes black listed? If so,
! 225: * return the address of the next plausible r such that (r, len) might not
! 226: * be black listed. (R may not actually be in the heap. We guarantee only
! 227: * that every smaller value of r after h is also black listed.)
! 228: * If (h,len) is not black listed, return 0.
! 229: * Knows about the structure of the black list hash tables.
! 230: */
! 231: struct hblk * GC_is_black_listed(h, len)
! 232: struct hblk * h;
! 233: word len;
! 234: {
! 235: register int index = PHT_HASH((word)h);
! 236: register word i;
! 237: word nblocks = divHBLKSZ(len);
! 238:
! 239: # ifndef ALL_INTERIOR_POINTERS
! 240: if (get_pht_entry_from_index(GC_old_normal_bl, index)
! 241: || get_pht_entry_from_index(GC_incomplete_normal_bl, index)) {
! 242: return(h+1);
! 243: }
! 244: # endif
! 245:
! 246: for (i = 0; ; ) {
! 247: if (GC_old_stack_bl[divWORDSZ(index)] == 0
! 248: && GC_incomplete_stack_bl[divWORDSZ(index)] == 0) {
! 249: /* An easy case */
! 250: i += WORDSZ - modWORDSZ(index);
! 251: } else {
! 252: if (get_pht_entry_from_index(GC_old_stack_bl, index)
! 253: || get_pht_entry_from_index(GC_incomplete_stack_bl, index)) {
! 254: return(h+i+1);
! 255: }
! 256: i++;
! 257: }
! 258: if (i >= nblocks) break;
! 259: index = PHT_HASH((word)(h+i));
! 260: }
! 261: return(0);
! 262: }
! 263:
! 264:
! 265: /* Return the number of blacklisted blocks in a given range. */
! 266: /* Used only for statistical purposes. */
! 267: /* Looks only at the GC_incomplete_stack_bl. */
! 268: word GC_number_stack_black_listed(start, endp1)
! 269: struct hblk *start, *endp1;
! 270: {
! 271: register struct hblk * h;
! 272: word result = 0;
! 273:
! 274: for (h = start; h < endp1; h++) {
! 275: register int index = PHT_HASH((word)h);
! 276:
! 277: if (get_pht_entry_from_index(GC_old_stack_bl, index)) result++;
! 278: }
! 279: return(result);
! 280: }
! 281:
! 282:
! 283: /* Return the total number of (stack) black-listed bytes. */
! 284: static word total_stack_black_listed()
! 285: {
! 286: register unsigned i;
! 287: word total = 0;
! 288:
! 289: for (i = 0; i < GC_n_heap_sects; i++) {
! 290: struct hblk * start = (struct hblk *) GC_heap_sects[i].hs_start;
! 291: word len = (word) GC_heap_sects[i].hs_bytes;
! 292: struct hblk * endp1 = start + len/HBLKSIZE;
! 293:
! 294: total += GC_number_stack_black_listed(start, endp1);
! 295: }
! 296: return(total * HBLKSIZE);
! 297: }
! 298:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>