]>
Commit | Line | Data |
---|---|---|
73ffefd0 TT |
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(ptr_t p) | |
67 | { | |
68 | ptr_t base = GC_base(p); | |
69 | if (0 == base) { | |
70 | GC_err_printf0("in root set"); | |
71 | } else { | |
72 | GC_err_printf0("in object at "); | |
73 | (*GC_print_heap_obj)(base); | |
74 | } | |
75 | } | |
76 | ||
77 | void GC_bl_init() | |
78 | { | |
79 | # ifndef ALL_INTERIOR_POINTERS | |
80 | GC_old_normal_bl = (word *) | |
81 | GC_scratch_alloc((word)(sizeof (page_hash_table))); | |
82 | GC_incomplete_normal_bl = (word *)GC_scratch_alloc | |
83 | ((word)(sizeof(page_hash_table))); | |
84 | if (GC_old_normal_bl == 0 || GC_incomplete_normal_bl == 0) { | |
85 | GC_err_printf0("Insufficient memory for black list\n"); | |
86 | EXIT(); | |
87 | } | |
88 | GC_clear_bl(GC_old_normal_bl); | |
89 | GC_clear_bl(GC_incomplete_normal_bl); | |
90 | # endif | |
91 | GC_old_stack_bl = (word *)GC_scratch_alloc((word)(sizeof(page_hash_table))); | |
92 | GC_incomplete_stack_bl = (word *)GC_scratch_alloc | |
93 | ((word)(sizeof(page_hash_table))); | |
94 | if (GC_old_stack_bl == 0 || GC_incomplete_stack_bl == 0) { | |
95 | GC_err_printf0("Insufficient memory for black list\n"); | |
96 | EXIT(); | |
97 | } | |
98 | GC_clear_bl(GC_old_stack_bl); | |
99 | GC_clear_bl(GC_incomplete_stack_bl); | |
100 | } | |
101 | ||
102 | void GC_clear_bl(doomed) | |
103 | word *doomed; | |
104 | { | |
105 | BZERO(doomed, sizeof(page_hash_table)); | |
106 | } | |
107 | ||
108 | void GC_copy_bl(old, new) | |
109 | word *new, *old; | |
110 | { | |
111 | BCOPY(old, new, sizeof(page_hash_table)); | |
112 | } | |
113 | ||
114 | static word total_stack_black_listed(); | |
115 | ||
116 | /* Signal the completion of a collection. Turn the incomplete black */ | |
117 | /* lists into new black lists, etc. */ | |
118 | void GC_promote_black_lists() | |
119 | { | |
120 | word * very_old_normal_bl = GC_old_normal_bl; | |
121 | word * very_old_stack_bl = GC_old_stack_bl; | |
122 | ||
123 | GC_old_normal_bl = GC_incomplete_normal_bl; | |
124 | GC_old_stack_bl = GC_incomplete_stack_bl; | |
125 | # ifndef ALL_INTERIOR_POINTERS | |
126 | GC_clear_bl(very_old_normal_bl); | |
127 | # endif | |
128 | GC_clear_bl(very_old_stack_bl); | |
129 | GC_incomplete_normal_bl = very_old_normal_bl; | |
130 | GC_incomplete_stack_bl = very_old_stack_bl; | |
131 | GC_total_stack_black_listed = total_stack_black_listed(); | |
132 | # ifdef PRINTSTATS | |
133 | GC_printf1("%ld bytes in heap blacklisted for interior pointers\n", | |
134 | (unsigned long)GC_total_stack_black_listed); | |
135 | # endif | |
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 | } | |
144 | ||
145 | void GC_unpromote_black_lists() | |
146 | { | |
147 | # ifndef ALL_INTERIOR_POINTERS | |
148 | GC_copy_bl(GC_old_normal_bl, GC_incomplete_normal_bl); | |
149 | # endif | |
150 | GC_copy_bl(GC_old_stack_bl, GC_incomplete_stack_bl); | |
151 | } | |
152 | ||
153 | # ifndef ALL_INTERIOR_POINTERS | |
154 | /* P is not a valid pointer reference, but it falls inside */ | |
155 | /* the plausible heap bounds. */ | |
156 | /* Add it to the normal incomplete black list if appropriate. */ | |
157 | #ifdef PRINT_BLACK_LIST | |
158 | void GC_add_to_black_list_normal(p, source) | |
159 | ptr_t source; | |
160 | #else | |
161 | void GC_add_to_black_list_normal(p) | |
162 | #endif | |
163 | word p; | |
164 | { | |
165 | if (!(GC_modws_valid_offsets[p & (sizeof(word)-1)])) return; | |
166 | { | |
167 | register int index = PHT_HASH(p); | |
168 | ||
169 | if (HDR(p) == 0 || get_pht_entry_from_index(GC_old_normal_bl, index)) { | |
170 | # ifdef PRINT_BLACK_LIST | |
171 | if (!get_pht_entry_from_index(GC_incomplete_normal_bl, index)) { | |
172 | GC_err_printf2( | |
173 | "Black listing (normal) 0x%lx referenced from 0x%lx ", | |
174 | (unsigned long) p, (unsigned long) source); | |
175 | GC_print_source_ptr(source); | |
176 | GC_err_puts("\n"); | |
177 | } | |
178 | # endif | |
179 | set_pht_entry_from_index(GC_incomplete_normal_bl, index); | |
180 | } /* else this is probably just an interior pointer to an allocated */ | |
181 | /* object, and isn't worth black listing. */ | |
182 | } | |
183 | } | |
184 | # endif | |
185 | ||
186 | /* And the same for false pointers from the stack. */ | |
187 | #ifdef PRINT_BLACK_LIST | |
188 | void GC_add_to_black_list_stack(p, source) | |
189 | ptr_t source; | |
190 | #else | |
191 | void GC_add_to_black_list_stack(p) | |
192 | #endif | |
193 | word p; | |
194 | { | |
195 | register int index = PHT_HASH(p); | |
196 | ||
197 | if (HDR(p) == 0 || get_pht_entry_from_index(GC_old_stack_bl, index)) { | |
198 | # ifdef PRINT_BLACK_LIST | |
199 | if (!get_pht_entry_from_index(GC_incomplete_stack_bl, index)) { | |
200 | GC_err_printf2( | |
201 | "Black listing (stack) 0x%lx referenced from 0x%lx ", | |
202 | (unsigned long)p, (unsigned long)source); | |
203 | GC_print_source_ptr(source); | |
204 | GC_err_puts("\n"); | |
205 | } | |
206 | # endif | |
207 | set_pht_entry_from_index(GC_incomplete_stack_bl, index); | |
208 | } | |
209 | } | |
210 | ||
211 | /* | |
212 | * Is the block starting at h of size len bytes black listed? If so, | |
213 | * return the address of the next plausible r such that (r, len) might not | |
214 | * be black listed. (R may not actually be in the heap. We guarantee only | |
215 | * that every smaller value of r after h is also black listed.) | |
216 | * If (h,len) is not black listed, return 0. | |
217 | * Knows about the structure of the black list hash tables. | |
218 | */ | |
219 | struct hblk * GC_is_black_listed(h, len) | |
220 | struct hblk * h; | |
221 | word len; | |
222 | { | |
223 | register int index = PHT_HASH((word)h); | |
224 | register word i; | |
225 | word nblocks = divHBLKSZ(len); | |
226 | ||
227 | # ifndef 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 | # endif | |
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. */ | |
256 | word GC_number_stack_black_listed(start, endp1) | |
257 | struct hblk *start, *endp1; | |
258 | { | |
259 | register struct hblk * h; | |
260 | word result = 0; | |
261 | ||
262 | for (h = start; h < endp1; h++) { | |
263 | register int index = PHT_HASH((word)h); | |
264 | ||
265 | if (get_pht_entry_from_index(GC_old_stack_bl, index)) result++; | |
266 | } | |
267 | return(result); | |
268 | } | |
269 | ||
270 | ||
271 | /* Return the total number of (stack) black-listed bytes. */ | |
272 | static word total_stack_black_listed() | |
273 | { | |
274 | register unsigned i; | |
275 | word total = 0; | |
276 | ||
277 | for (i = 0; i < GC_n_heap_sects; i++) { | |
278 | struct hblk * start = (struct hblk *) GC_heap_sects[i].hs_start; | |
279 | word len = (word) GC_heap_sects[i].hs_bytes; | |
280 | struct hblk * endp1 = start + len/HBLKSIZE; | |
281 | ||
282 | total += GC_number_stack_black_listed(start, endp1); | |
283 | } | |
284 | return(total * HBLKSIZE); | |
285 | } | |
286 |