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