Debian Codegraph @

gc/blacklst.c

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