]>
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 | ||
20bbd3cd TT |
66 | void GC_print_source_ptr(p) |
67 | ptr_t p; | |
73ffefd0 TT |
68 | { |
69 | ptr_t base = GC_base(p); | |
70 | if (0 == base) { | |
20bbd3cd TT |
71 | if (0 == p) { |
72 | GC_err_printf0("in register"); | |
73 | } else { | |
74 | GC_err_printf0("in root set"); | |
75 | } | |
73ffefd0 TT |
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 | } | |
20bbd3cd TT |
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 | } | |
73ffefd0 TT |
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 |