2 * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
3 * Copyright (c) 1991-1994 by Xerox Corporation. All rights reserved.
5 * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
6 * OR IMPLIED. ANY USE IS AT YOUR OWN RISK.
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.
15 #include "private/gc_priv.h"
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.
28 * Externally callable routines are:
30 * GC_add_to_black_list_normal
31 * GC_add_to_black_list_stack
32 * GC_promote_black_lists
35 * All require that the allocator lock is held.
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 */
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;
49 STATIC word GC_total_stack_black_listed = 0;
50 /* Number of bytes on stack blacklist. */
52 GC_INNER word GC_black_list_spacing = MINHINCR * HBLKSIZE;
53 /* Initial rough guess. */
55 STATIC void GC_clear_bl(word *);
57 GC_INNER void GC_default_print_heap_obj_proc(ptr_t p)
59 ptr_t base = GC_base(p);
60 GC_err_printf("start: %p, appr. length: %ld", base,
61 (unsigned long)GC_size(base));
64 GC_INNER void (*GC_print_heap_obj)(ptr_t p) = GC_default_print_heap_obj_proc;
66 #ifdef PRINT_BLACK_LIST
67 STATIC void GC_print_source_ptr(ptr_t p)
69 ptr_t base = GC_base(p);
72 GC_err_printf("in register");
74 GC_err_printf("in root set");
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);
86 GC_INNER void GC_bl_init_no_interiors(void)
88 if (GC_incomplete_normal_bl == 0) {
89 GC_old_normal_bl = (word *)GC_scratch_alloc(sizeof(page_hash_table));
90 GC_incomplete_normal_bl = (word *)GC_scratch_alloc(
91 sizeof(page_hash_table));
92 if (GC_old_normal_bl == 0 || GC_incomplete_normal_bl == 0) {
93 GC_err_printf("Insufficient memory for black list\n");
96 GC_clear_bl(GC_old_normal_bl);
97 GC_clear_bl(GC_incomplete_normal_bl);
101 GC_INNER void GC_bl_init(void)
103 if (!GC_all_interior_pointers) {
104 GC_bl_init_no_interiors();
106 GC_old_stack_bl = (word *)GC_scratch_alloc(sizeof(page_hash_table));
107 GC_incomplete_stack_bl = (word *)GC_scratch_alloc(sizeof(page_hash_table));
108 if (GC_old_stack_bl == 0 || GC_incomplete_stack_bl == 0) {
109 GC_err_printf("Insufficient memory for black list\n");
112 GC_clear_bl(GC_old_stack_bl);
113 GC_clear_bl(GC_incomplete_stack_bl);
116 STATIC void GC_clear_bl(word *doomed)
118 BZERO(doomed, sizeof(page_hash_table));
121 STATIC void GC_copy_bl(word *old, word *new)
123 BCOPY(old, new, sizeof(page_hash_table));
126 static word total_stack_black_listed(void);
128 /* Signal the completion of a collection. Turn the incomplete black */
129 /* lists into new black lists, etc. */
130 GC_INNER void GC_promote_black_lists(void)
132 word * very_old_normal_bl = GC_old_normal_bl;
133 word * very_old_stack_bl = GC_old_stack_bl;
135 GC_old_normal_bl = GC_incomplete_normal_bl;
136 GC_old_stack_bl = GC_incomplete_stack_bl;
137 if (!GC_all_interior_pointers) {
138 GC_clear_bl(very_old_normal_bl);
140 GC_clear_bl(very_old_stack_bl);
141 GC_incomplete_normal_bl = very_old_normal_bl;
142 GC_incomplete_stack_bl = very_old_stack_bl;
143 GC_total_stack_black_listed = total_stack_black_listed();
144 if (GC_print_stats == VERBOSE)
145 GC_log_printf("%ld bytes in heap blacklisted for interior pointers\n",
146 (unsigned long)GC_total_stack_black_listed);
147 if (GC_total_stack_black_listed != 0) {
148 GC_black_list_spacing =
149 HBLKSIZE*(GC_heapsize/GC_total_stack_black_listed);
151 if (GC_black_list_spacing < 3 * HBLKSIZE) {
152 GC_black_list_spacing = 3 * HBLKSIZE;
154 if (GC_black_list_spacing > MAXHINCR * HBLKSIZE) {
155 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 */
163 GC_INNER void GC_unpromote_black_lists(void)
165 if (!GC_all_interior_pointers) {
166 GC_copy_bl(GC_old_normal_bl, GC_incomplete_normal_bl);
168 GC_copy_bl(GC_old_stack_bl, GC_incomplete_stack_bl);
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)
177 GC_INNER void GC_add_to_black_list_normal(word p)
180 if (GC_modws_valid_offsets[p & (sizeof(word)-1)]) {
181 word index = PHT_HASH((word)p);
183 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 ",
188 GC_print_source_ptr(source);
192 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. */
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)
202 GC_INNER void GC_add_to_black_list_stack(word p)
205 word index = PHT_HASH((word)p);
207 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 ",
212 GC_print_source_ptr(source);
216 set_pht_entry_from_index(GC_incomplete_stack_bl, index);
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.
228 struct hblk * GC_is_black_listed(struct hblk *h, word len)
230 word index = PHT_HASH((word)h);
234 if (!GC_all_interior_pointers
235 && (get_pht_entry_from_index(GC_old_normal_bl, index)
236 || get_pht_entry_from_index(GC_incomplete_normal_bl, index))) {
240 nblocks = divHBLKSZ(len);
242 if (GC_old_stack_bl[divWORDSZ(index)] == 0
243 && GC_incomplete_stack_bl[divWORDSZ(index)] == 0) {
245 i += WORDSZ - modWORDSZ(index);
247 if (get_pht_entry_from_index(GC_old_stack_bl, index)
248 || get_pht_entry_from_index(GC_incomplete_stack_bl, index)) {
253 if (i >= nblocks) break;
254 index = PHT_HASH((word)(h+i));
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 STATIC word GC_number_stack_black_listed(struct hblk *start,
265 register struct hblk * h;
268 for (h = start; h < endp1; h++) {
269 word index = PHT_HASH((word)h);
271 if (get_pht_entry_from_index(GC_old_stack_bl, index)) result++;
276 /* Return the total number of (stack) black-listed bytes. */
277 static word total_stack_black_listed(void)
282 for (i = 0; i < GC_n_heap_sects; i++) {
283 struct hblk * start = (struct hblk *) GC_heap_sects[i].hs_start;
284 struct hblk * endp1 = start + GC_heap_sects[i].hs_bytes/HBLKSIZE;
286 total += GC_number_stack_black_listed(start, endp1);
288 return(total * HBLKSIZE);