Annotation of OpenXM_contrib2/asir2000/gc/headers.c, Revision 1.3
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: * Copyright (c) 1996 by Silicon Graphics. All rights reserved.
5: *
6: * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
7: * OR IMPLIED. ANY USE IS AT YOUR OWN RISK.
8: *
9: * Permission is hereby granted to use or copy this program
10: * for any purpose, provided the above notices are retained on all copies.
11: * Permission to modify the code and to distribute modified code is granted,
12: * provided the above notices are retained, and a notice that the code was
13: * modified is included with the above copyright notice.
14: */
15:
16: /*
17: * This implements:
18: * 1. allocation of heap block headers
19: * 2. A map from addresses to heap block addresses to heap block headers
20: *
21: * Access speed is crucial. We implement an index structure based on a 2
22: * level tree.
23: */
24:
1.3 ! noro 25: # include "private/gc_priv.h"
1.1 noro 26:
27: bottom_index * GC_all_bottom_indices = 0;
28: /* Pointer to first (lowest addr) */
29: /* bottom_index. */
30:
31: bottom_index * GC_all_bottom_indices_end = 0;
32: /* Pointer to last (highest addr) */
33: /* bottom_index. */
34:
35: /* Non-macro version of header location routine */
36: hdr * GC_find_header(h)
37: ptr_t h;
38: {
39: # ifdef HASH_TL
40: register hdr * result;
41: GET_HDR(h, result);
42: return(result);
43: # else
44: return(HDR_INNER(h));
45: # endif
46: }
47:
48: /* Routines to dynamically allocate collector data structures that will */
49: /* never be freed. */
50:
51: static ptr_t scratch_free_ptr = 0;
52:
1.2 noro 53: /* GC_scratch_last_end_ptr is end point of last obtained scratch area. */
54: /* GC_scratch_end_ptr is end point of current scratch area. */
1.1 noro 55:
56: ptr_t GC_scratch_alloc(bytes)
57: register word bytes;
58: {
59: register ptr_t result = scratch_free_ptr;
60:
61: # ifdef ALIGN_DOUBLE
62: # define GRANULARITY (2 * sizeof(word))
63: # else
64: # define GRANULARITY sizeof(word)
65: # endif
66: bytes += GRANULARITY-1;
67: bytes &= ~(GRANULARITY-1);
68: scratch_free_ptr += bytes;
69: if (scratch_free_ptr <= GC_scratch_end_ptr) {
70: return(result);
71: }
72: {
73: word bytes_to_get = MINHINCR * HBLKSIZE;
74:
75: if (bytes_to_get <= bytes) {
76: /* Undo the damage, and get memory directly */
77: bytes_to_get = bytes;
78: # ifdef USE_MMAP
79: bytes_to_get += GC_page_size - 1;
80: bytes_to_get &= ~(GC_page_size - 1);
81: # endif
82: result = (ptr_t)GET_MEM(bytes_to_get);
83: scratch_free_ptr -= bytes;
84: GC_scratch_last_end_ptr = result + bytes;
85: return(result);
86: }
87: result = (ptr_t)GET_MEM(bytes_to_get);
88: if (result == 0) {
89: # ifdef PRINTSTATS
90: GC_printf0("Out of memory - trying to allocate less\n");
91: # endif
92: scratch_free_ptr -= bytes;
93: bytes_to_get = bytes;
94: # ifdef USE_MMAP
95: bytes_to_get += GC_page_size - 1;
96: bytes_to_get &= ~(GC_page_size - 1);
97: # endif
98: return((ptr_t)GET_MEM(bytes_to_get));
99: }
100: scratch_free_ptr = result;
101: GC_scratch_end_ptr = scratch_free_ptr + bytes_to_get;
102: GC_scratch_last_end_ptr = GC_scratch_end_ptr;
103: return(GC_scratch_alloc(bytes));
104: }
105: }
106:
107: static hdr * hdr_free_list = 0;
108:
109: /* Return an uninitialized header */
110: static hdr * alloc_hdr()
111: {
112: register hdr * result;
113:
114: if (hdr_free_list == 0) {
115: result = (hdr *) GC_scratch_alloc((word)(sizeof(hdr)));
116: } else {
117: result = hdr_free_list;
118: hdr_free_list = (hdr *) (result -> hb_next);
119: }
120: return(result);
121: }
122:
123: static void free_hdr(hhdr)
124: hdr * hhdr;
125: {
126: hhdr -> hb_next = (struct hblk *) hdr_free_list;
127: hdr_free_list = hhdr;
128: }
1.2 noro 129:
130: hdr * GC_invalid_header;
131:
132: #ifdef USE_HDR_CACHE
133: word GC_hdr_cache_hits = 0;
134: word GC_hdr_cache_misses = 0;
135: #endif
1.1 noro 136:
137: void GC_init_headers()
138: {
139: register unsigned i;
140:
141: GC_all_nils = (bottom_index *)GC_scratch_alloc((word)sizeof(bottom_index));
142: BZERO(GC_all_nils, sizeof(bottom_index));
143: for (i = 0; i < TOP_SZ; i++) {
144: GC_top_index[i] = GC_all_nils;
145: }
1.2 noro 146: GC_invalid_header = alloc_hdr();
147: GC_invalidate_map(GC_invalid_header);
1.1 noro 148: }
149:
150: /* Make sure that there is a bottom level index block for address addr */
151: /* Return FALSE on failure. */
152: static GC_bool get_index(addr)
153: word addr;
154: {
155: word hi = (word)(addr) >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE);
156: bottom_index * r;
157: bottom_index * p;
158: bottom_index ** prev;
159: bottom_index *pi;
160:
161: # ifdef HASH_TL
162: unsigned i = TL_HASH(hi);
163: bottom_index * old;
164:
165: old = p = GC_top_index[i];
166: while(p != GC_all_nils) {
167: if (p -> key == hi) return(TRUE);
168: p = p -> hash_link;
169: }
170: r = (bottom_index*)GC_scratch_alloc((word)(sizeof (bottom_index)));
171: if (r == 0) return(FALSE);
172: BZERO(r, sizeof (bottom_index));
173: r -> hash_link = old;
174: GC_top_index[i] = r;
175: # else
176: if (GC_top_index[hi] != GC_all_nils) return(TRUE);
177: r = (bottom_index*)GC_scratch_alloc((word)(sizeof (bottom_index)));
178: if (r == 0) return(FALSE);
179: GC_top_index[hi] = r;
180: BZERO(r, sizeof (bottom_index));
181: # endif
182: r -> key = hi;
183: /* Add it to the list of bottom indices */
184: prev = &GC_all_bottom_indices; /* pointer to p */
185: pi = 0; /* bottom_index preceding p */
186: while ((p = *prev) != 0 && p -> key < hi) {
187: pi = p;
188: prev = &(p -> asc_link);
189: }
190: r -> desc_link = pi;
191: if (0 == p) {
192: GC_all_bottom_indices_end = r;
193: } else {
194: p -> desc_link = r;
195: }
196: r -> asc_link = p;
197: *prev = r;
198: return(TRUE);
199: }
200:
1.2 noro 201: /* Install a header for block h. */
202: /* The header is uninitialized. */
203: /* Returns the header or 0 on failure. */
204: struct hblkhdr * GC_install_header(h)
1.1 noro 205: register struct hblk * h;
206: {
207: hdr * result;
208:
209: if (!get_index((word) h)) return(FALSE);
210: result = alloc_hdr();
211: SET_HDR(h, result);
212: # ifdef USE_MUNMAP
213: result -> hb_last_reclaimed = GC_gc_no;
214: # endif
1.2 noro 215: return(result);
1.1 noro 216: }
217:
218: /* Set up forwarding counts for block h of size sz */
219: GC_bool GC_install_counts(h, sz)
220: register struct hblk * h;
221: register word sz; /* bytes */
222: {
223: register struct hblk * hbp;
224: register int i;
225:
226: for (hbp = h; (char *)hbp < (char *)h + sz; hbp += BOTTOM_SZ) {
227: if (!get_index((word) hbp)) return(FALSE);
228: }
229: if (!get_index((word)h + sz - 1)) return(FALSE);
230: for (hbp = h + 1; (char *)hbp < (char *)h + sz; hbp += 1) {
231: i = HBLK_PTR_DIFF(hbp, h);
232: SET_HDR(hbp, (hdr *)(i > MAX_JUMP? MAX_JUMP : i));
233: }
234: return(TRUE);
235: }
236:
237: /* Remove the header for block h */
238: void GC_remove_header(h)
239: register struct hblk * h;
240: {
241: hdr ** ha;
242:
243: GET_HDR_ADDR(h, ha);
244: free_hdr(*ha);
245: *ha = 0;
246: }
247:
248: /* Remove forwarding counts for h */
249: void GC_remove_counts(h, sz)
250: register struct hblk * h;
251: register word sz; /* bytes */
252: {
253: register struct hblk * hbp;
254:
255: for (hbp = h+1; (char *)hbp < (char *)h + sz; hbp += 1) {
256: SET_HDR(hbp, 0);
257: }
258: }
259:
260: /* Apply fn to all allocated blocks */
261: /*VARARGS1*/
262: void GC_apply_to_all_blocks(fn, client_data)
1.3 ! noro 263: void (*fn) GC_PROTO((struct hblk *h, word client_data));
1.1 noro 264: word client_data;
265: {
266: register int j;
267: register bottom_index * index_p;
268:
269: for (index_p = GC_all_bottom_indices; index_p != 0;
270: index_p = index_p -> asc_link) {
271: for (j = BOTTOM_SZ-1; j >= 0;) {
272: if (!IS_FORWARDING_ADDR_OR_NIL(index_p->index[j])) {
273: if (index_p->index[j]->hb_map != GC_invalid_map) {
274: (*fn)(((struct hblk *)
275: (((index_p->key << LOG_BOTTOM_SZ) + (word)j)
276: << LOG_HBLKSIZE)),
277: client_data);
278: }
279: j--;
280: } else if (index_p->index[j] == 0) {
281: j--;
282: } else {
283: j -= (word)(index_p->index[j]);
284: }
285: }
286: }
287: }
288:
289: /* Get the next valid block whose address is at least h */
290: /* Return 0 if there is none. */
291: struct hblk * GC_next_used_block(h)
292: struct hblk * h;
293: {
294: register bottom_index * bi;
295: register word j = ((word)h >> LOG_HBLKSIZE) & (BOTTOM_SZ-1);
296:
297: GET_BI(h, bi);
298: if (bi == GC_all_nils) {
299: register word hi = (word)h >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE);
300: bi = GC_all_bottom_indices;
301: while (bi != 0 && bi -> key < hi) bi = bi -> asc_link;
302: j = 0;
303: }
304: while(bi != 0) {
305: while (j < BOTTOM_SZ) {
306: hdr * hhdr = bi -> index[j];
307: if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) {
308: j++;
309: } else {
310: if (hhdr->hb_map != GC_invalid_map) {
311: return((struct hblk *)
312: (((bi -> key << LOG_BOTTOM_SZ) + j)
313: << LOG_HBLKSIZE));
314: } else {
315: j += divHBLKSZ(hhdr -> hb_sz);
316: }
317: }
318: }
319: j = 0;
320: bi = bi -> asc_link;
321: }
322: return(0);
323: }
324:
325: /* Get the last (highest address) block whose address is */
326: /* at most h. Return 0 if there is none. */
327: /* Unlike the above, this may return a free block. */
328: struct hblk * GC_prev_block(h)
329: struct hblk * h;
330: {
331: register bottom_index * bi;
332: register signed_word j = ((word)h >> LOG_HBLKSIZE) & (BOTTOM_SZ-1);
333:
334: GET_BI(h, bi);
335: if (bi == GC_all_nils) {
336: register word hi = (word)h >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE);
337: bi = GC_all_bottom_indices_end;
338: while (bi != 0 && bi -> key > hi) bi = bi -> desc_link;
339: j = BOTTOM_SZ - 1;
340: }
341: while(bi != 0) {
342: while (j >= 0) {
343: hdr * hhdr = bi -> index[j];
344: if (0 == hhdr) {
345: --j;
346: } else if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) {
347: j -= (signed_word)hhdr;
348: } else {
349: return((struct hblk *)
350: (((bi -> key << LOG_BOTTOM_SZ) + j)
351: << LOG_HBLKSIZE));
352: }
353: }
354: j = BOTTOM_SZ - 1;
355: bi = bi -> desc_link;
356: }
357: return(0);
358: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to headers.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM_contrib2 / asir2000 / gc