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