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, 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 : 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 : GC_err_printf("start: %p, appr. length: %ld", base,
61 : (unsigned long)GC_size(base));
62 0 : }
63 :
64 : GC_INNER void (*GC_print_heap_obj)(ptr_t p) = GC_default_print_heap_obj_proc;
65 :
66 : #ifdef PRINT_BLACK_LIST
67 : STATIC void GC_print_source_ptr(ptr_t p)
68 : {
69 : ptr_t base = GC_base(p);
70 : if (0 == base) {
71 : if (0 == p) {
72 : GC_err_printf("in register");
73 : } else {
74 : GC_err_printf("in root set");
75 : }
76 : } else {
77 : GC_err_printf("in object at ");
78 : /* FIXME: We can't call the debug version of GC_print_heap_obj */
79 : /* (with PRINT_CALL_CHAIN) here because the lock is held and */
80 : /* the world is stopped. */
81 : GC_default_print_heap_obj_proc(base);
82 : }
83 : }
84 : #endif
85 :
86 163 : GC_INNER void GC_bl_init_no_interiors(void)
87 : {
88 163 : if (GC_incomplete_normal_bl == 0) {
89 163 : GC_old_normal_bl = (word *)GC_scratch_alloc(sizeof(page_hash_table));
90 163 : GC_incomplete_normal_bl = (word *)GC_scratch_alloc(
91 : sizeof(page_hash_table));
92 163 : if (GC_old_normal_bl == 0 || GC_incomplete_normal_bl == 0) {
93 0 : GC_err_printf("Insufficient memory for black list\n");
94 0 : EXIT();
95 : }
96 163 : GC_clear_bl(GC_old_normal_bl);
97 163 : GC_clear_bl(GC_incomplete_normal_bl);
98 : }
99 163 : }
100 :
101 163 : GC_INNER void GC_bl_init(void)
102 : {
103 163 : if (!GC_all_interior_pointers) {
104 163 : GC_bl_init_no_interiors();
105 : }
106 163 : GC_old_stack_bl = (word *)GC_scratch_alloc(sizeof(page_hash_table));
107 163 : GC_incomplete_stack_bl = (word *)GC_scratch_alloc(sizeof(page_hash_table));
108 163 : if (GC_old_stack_bl == 0 || GC_incomplete_stack_bl == 0) {
109 0 : GC_err_printf("Insufficient memory for black list\n");
110 0 : EXIT();
111 : }
112 163 : GC_clear_bl(GC_old_stack_bl);
113 163 : GC_clear_bl(GC_incomplete_stack_bl);
114 163 : }
115 :
116 1156 : STATIC void GC_clear_bl(word *doomed)
117 : {
118 1156 : BZERO(doomed, sizeof(page_hash_table));
119 1156 : }
120 :
121 0 : STATIC void GC_copy_bl(word *old, word *new)
122 : {
123 0 : BCOPY(old, new, sizeof(page_hash_table));
124 0 : }
125 :
126 : static word total_stack_black_listed(void);
127 :
128 : /* Signal the completion of a collection. Turn the incomplete black */
129 : /* lists into new black lists, etc. */
130 252 : GC_INNER void GC_promote_black_lists(void)
131 : {
132 252 : word * very_old_normal_bl = GC_old_normal_bl;
133 252 : word * very_old_stack_bl = GC_old_stack_bl;
134 :
135 252 : GC_old_normal_bl = GC_incomplete_normal_bl;
136 252 : GC_old_stack_bl = GC_incomplete_stack_bl;
137 252 : if (!GC_all_interior_pointers) {
138 252 : GC_clear_bl(very_old_normal_bl);
139 : }
140 252 : GC_clear_bl(very_old_stack_bl);
141 252 : GC_incomplete_normal_bl = very_old_normal_bl;
142 252 : GC_incomplete_stack_bl = very_old_stack_bl;
143 252 : GC_total_stack_black_listed = total_stack_black_listed();
144 252 : if (GC_print_stats == VERBOSE)
145 0 : GC_log_printf("%ld bytes in heap blacklisted for interior pointers\n",
146 : (unsigned long)GC_total_stack_black_listed);
147 252 : if (GC_total_stack_black_listed != 0) {
148 4 : GC_black_list_spacing =
149 4 : HBLKSIZE*(GC_heapsize/GC_total_stack_black_listed);
150 : }
151 252 : if (GC_black_list_spacing < 3 * HBLKSIZE) {
152 0 : GC_black_list_spacing = 3 * HBLKSIZE;
153 : }
154 252 : if (GC_black_list_spacing > MAXHINCR * HBLKSIZE) {
155 1 : GC_black_list_spacing = MAXHINCR * HBLKSIZE;
156 : /* Makes it easier to allocate really huge blocks, which otherwise */
157 : /* may have problems with nonuniform blacklist distributions. */
158 : /* This way we should always succeed immediately after growing the */
159 : /* heap. */
160 : }
161 252 : }
162 :
163 0 : GC_INNER void GC_unpromote_black_lists(void)
164 : {
165 0 : if (!GC_all_interior_pointers) {
166 0 : GC_copy_bl(GC_old_normal_bl, GC_incomplete_normal_bl);
167 : }
168 0 : GC_copy_bl(GC_old_stack_bl, GC_incomplete_stack_bl);
169 0 : }
170 :
171 : /* P is not a valid pointer reference, but it falls inside */
172 : /* the plausible heap bounds. */
173 : /* Add it to the normal incomplete black list if appropriate. */
174 : #ifdef PRINT_BLACK_LIST
175 : GC_INNER void GC_add_to_black_list_normal(word p, ptr_t source)
176 : #else
177 965770 : GC_INNER void GC_add_to_black_list_normal(word p)
178 : #endif
179 : {
180 965770 : if (GC_modws_valid_offsets[p & (sizeof(word)-1)]) {
181 964826 : word index = PHT_HASH((word)p);
182 :
183 964826 : if (HDR(p) == 0 || get_pht_entry_from_index(GC_old_normal_bl, index)) {
184 : # ifdef PRINT_BLACK_LIST
185 : if (!get_pht_entry_from_index(GC_incomplete_normal_bl, index)) {
186 : GC_err_printf("Black listing (normal) %p referenced from %p ",
187 : (ptr_t)p, source);
188 : GC_print_source_ptr(source);
189 : GC_err_puts("\n");
190 : }
191 : # endif
192 963895 : set_pht_entry_from_index(GC_incomplete_normal_bl, index);
193 : } /* else this is probably just an interior pointer to an allocated */
194 : /* object, and isn't worth black listing. */
195 : }
196 965770 : }
197 :
198 : /* And the same for false pointers from the stack. */
199 : #ifdef PRINT_BLACK_LIST
200 : GC_INNER void GC_add_to_black_list_stack(word p, ptr_t source)
201 : #else
202 5574 : GC_INNER void GC_add_to_black_list_stack(word p)
203 : #endif
204 : {
205 5574 : word index = PHT_HASH((word)p);
206 :
207 5574 : if (HDR(p) == 0 || get_pht_entry_from_index(GC_old_stack_bl, index)) {
208 : # ifdef PRINT_BLACK_LIST
209 : if (!get_pht_entry_from_index(GC_incomplete_stack_bl, index)) {
210 : GC_err_printf("Black listing (stack) %p referenced from %p ",
211 : (ptr_t)p, source);
212 : GC_print_source_ptr(source);
213 : GC_err_puts("\n");
214 : }
215 : # endif
216 5573 : set_pht_entry_from_index(GC_incomplete_stack_bl, index);
217 : }
218 5574 : }
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 34212 : struct hblk * GC_is_black_listed(struct hblk *h, word len)
229 : {
230 34212 : word index = PHT_HASH((word)h);
231 : word i;
232 : word nblocks;
233 :
234 102604 : if (!GC_all_interior_pointers
235 34212 : && (get_pht_entry_from_index(GC_old_normal_bl, index)
236 34180 : || get_pht_entry_from_index(GC_incomplete_normal_bl, index))) {
237 66 : return (h+1);
238 : }
239 :
240 34146 : nblocks = divHBLKSZ(len);
241 34146 : for (i = 0;;) {
242 103170 : if (GC_old_stack_bl[divWORDSZ(index)] == 0
243 34352 : && GC_incomplete_stack_bl[divWORDSZ(index)] == 0) {
244 : /* An easy case */
245 34200 : i += WORDSZ - modWORDSZ(index);
246 : } else {
247 831 : if (get_pht_entry_from_index(GC_old_stack_bl, index)
248 413 : || get_pht_entry_from_index(GC_incomplete_stack_bl, index)) {
249 11 : return(h+i+1);
250 : }
251 407 : i++;
252 : }
253 34607 : if (i >= nblocks) break;
254 472 : index = PHT_HASH((word)(h+i));
255 472 : }
256 34135 : 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 479 : STATIC word GC_number_stack_black_listed(struct hblk *start,
263 : struct hblk *endp1)
264 : {
265 : register struct hblk * h;
266 479 : word result = 0;
267 :
268 140578 : for (h = start; h < endp1; h++) {
269 140099 : word index = PHT_HASH((word)h);
270 :
271 140099 : if (get_pht_entry_from_index(GC_old_stack_bl, index)) result++;
272 : }
273 479 : return(result);
274 : }
275 :
276 : /* Return the total number of (stack) black-listed bytes. */
277 252 : static word total_stack_black_listed(void)
278 : {
279 : register unsigned i;
280 252 : word total = 0;
281 :
282 731 : for (i = 0; i < GC_n_heap_sects; i++) {
283 479 : struct hblk * start = (struct hblk *) GC_heap_sects[i].hs_start;
284 479 : struct hblk * endp1 = start + GC_heap_sects[i].hs_bytes/HBLKSIZE;
285 :
286 479 : total += GC_number_stack_black_listed(start, endp1);
287 : }
288 252 : return(total * HBLKSIZE);
289 : }
|
