Annotation of OpenXM_contrib2/asir2000/gc/blacklst.c, Revision 1.2
1.1 noro 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:
66: void GC_print_source_ptr(p)
67: ptr_t p;
68: {
69: ptr_t base = GC_base(p);
70: if (0 == base) {
71: if (0 == p) {
72: GC_err_printf0("in register");
73: } else {
74: GC_err_printf0("in root set");
75: }
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: }
1.2 ! noro 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: }
1.1 noro 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:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to blacklst.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM_contrib2 / asir2000 / gc