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