Annotation of OpenXM_contrib/gc/headers.c, Revision 1.1.1.2
1.1 maekawa 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:
25: # include "gc_priv.h"
26:
27: bottom_index * GC_all_bottom_indices = 0;
1.1.1.2 ! maekawa 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. */
1.1 maekawa 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:
53: ptr_t GC_scratch_end_ptr = 0;
54:
55: ptr_t GC_scratch_last_end_ptr = 0;
56: /* End point of last obtained scratch area */
57:
58: ptr_t GC_scratch_alloc(bytes)
59: register word bytes;
60: {
61: register ptr_t result = scratch_free_ptr;
62:
63: # ifdef ALIGN_DOUBLE
64: # define GRANULARITY (2 * sizeof(word))
65: # else
66: # define GRANULARITY sizeof(word)
67: # endif
68: bytes += GRANULARITY-1;
69: bytes &= ~(GRANULARITY-1);
70: scratch_free_ptr += bytes;
71: if (scratch_free_ptr <= GC_scratch_end_ptr) {
72: return(result);
73: }
74: {
75: word bytes_to_get = MINHINCR * HBLKSIZE;
76:
77: if (bytes_to_get <= bytes) {
78: /* Undo the damage, and get memory directly */
79: bytes_to_get = bytes;
80: # ifdef USE_MMAP
81: bytes_to_get += GC_page_size - 1;
82: bytes_to_get &= ~(GC_page_size - 1);
83: # endif
84: result = (ptr_t)GET_MEM(bytes_to_get);
85: scratch_free_ptr -= bytes;
86: GC_scratch_last_end_ptr = result + bytes;
87: return(result);
88: }
89: result = (ptr_t)GET_MEM(bytes_to_get);
90: if (result == 0) {
91: # ifdef PRINTSTATS
92: GC_printf0("Out of memory - trying to allocate less\n");
93: # endif
94: scratch_free_ptr -= bytes;
95: bytes_to_get = bytes;
96: # ifdef USE_MMAP
97: bytes_to_get += GC_page_size - 1;
98: bytes_to_get &= ~(GC_page_size - 1);
99: # endif
100: return((ptr_t)GET_MEM(bytes_to_get));
101: }
102: scratch_free_ptr = result;
103: GC_scratch_end_ptr = scratch_free_ptr + bytes_to_get;
104: GC_scratch_last_end_ptr = GC_scratch_end_ptr;
105: return(GC_scratch_alloc(bytes));
106: }
107: }
108:
109: static hdr * hdr_free_list = 0;
110:
111: /* Return an uninitialized header */
112: static hdr * alloc_hdr()
113: {
114: register hdr * result;
115:
116: if (hdr_free_list == 0) {
117: result = (hdr *) GC_scratch_alloc((word)(sizeof(hdr)));
118: } else {
119: result = hdr_free_list;
120: hdr_free_list = (hdr *) (result -> hb_next);
121: }
122: return(result);
123: }
124:
125: static void free_hdr(hhdr)
126: hdr * hhdr;
127: {
128: hhdr -> hb_next = (struct hblk *) hdr_free_list;
129: hdr_free_list = hhdr;
130: }
131:
132: void GC_init_headers()
133: {
134: register unsigned i;
135:
136: GC_all_nils = (bottom_index *)GC_scratch_alloc((word)sizeof(bottom_index));
137: BZERO(GC_all_nils, sizeof(bottom_index));
138: for (i = 0; i < TOP_SZ; i++) {
139: GC_top_index[i] = GC_all_nils;
140: }
141: }
142:
143: /* Make sure that there is a bottom level index block for address addr */
144: /* Return FALSE on failure. */
145: static GC_bool get_index(addr)
1.1.1.2 ! maekawa 146: word addr;
1.1 maekawa 147: {
1.1.1.2 ! maekawa 148: word hi = (word)(addr) >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE);
! 149: bottom_index * r;
! 150: bottom_index * p;
! 151: bottom_index ** prev;
! 152: bottom_index *pi;
! 153:
1.1 maekawa 154: # ifdef HASH_TL
1.1.1.2 ! maekawa 155: unsigned i = TL_HASH(hi);
! 156: bottom_index * old;
1.1 maekawa 157:
158: old = p = GC_top_index[i];
159: while(p != GC_all_nils) {
160: if (p -> key == hi) return(TRUE);
161: p = p -> hash_link;
162: }
163: r = (bottom_index*)GC_scratch_alloc((word)(sizeof (bottom_index)));
164: if (r == 0) return(FALSE);
165: BZERO(r, sizeof (bottom_index));
166: r -> hash_link = old;
167: GC_top_index[i] = r;
168: # else
169: if (GC_top_index[hi] != GC_all_nils) return(TRUE);
170: r = (bottom_index*)GC_scratch_alloc((word)(sizeof (bottom_index)));
171: if (r == 0) return(FALSE);
172: GC_top_index[hi] = r;
173: BZERO(r, sizeof (bottom_index));
1.1.1.2 ! maekawa 174: # endif
1.1 maekawa 175: r -> key = hi;
176: /* Add it to the list of bottom indices */
1.1.1.2 ! maekawa 177: prev = &GC_all_bottom_indices; /* pointer to p */
! 178: pi = 0; /* bottom_index preceding p */
! 179: while ((p = *prev) != 0 && p -> key < hi) {
! 180: pi = p;
! 181: prev = &(p -> asc_link);
! 182: }
! 183: r -> desc_link = pi;
! 184: if (0 == p) {
! 185: GC_all_bottom_indices_end = r;
! 186: } else {
! 187: p -> desc_link = r;
! 188: }
1.1 maekawa 189: r -> asc_link = p;
190: *prev = r;
191: return(TRUE);
192: }
193:
194: /* Install a header for block h. */
195: /* The header is uninitialized. */
196: /* Returns FALSE on failure. */
197: GC_bool GC_install_header(h)
198: register struct hblk * h;
199: {
200: hdr * result;
201:
202: if (!get_index((word) h)) return(FALSE);
203: result = alloc_hdr();
204: SET_HDR(h, result);
1.1.1.2 ! maekawa 205: # ifdef USE_MUNMAP
! 206: result -> hb_last_reclaimed = GC_gc_no;
! 207: # endif
1.1 maekawa 208: return(result != 0);
209: }
210:
211: /* Set up forwarding counts for block h of size sz */
212: GC_bool GC_install_counts(h, sz)
213: register struct hblk * h;
214: register word sz; /* bytes */
215: {
216: register struct hblk * hbp;
217: register int i;
218:
219: for (hbp = h; (char *)hbp < (char *)h + sz; hbp += BOTTOM_SZ) {
220: if (!get_index((word) hbp)) return(FALSE);
221: }
222: if (!get_index((word)h + sz - 1)) return(FALSE);
223: for (hbp = h + 1; (char *)hbp < (char *)h + sz; hbp += 1) {
224: i = HBLK_PTR_DIFF(hbp, h);
225: SET_HDR(hbp, (hdr *)(i > MAX_JUMP? MAX_JUMP : i));
226: }
227: return(TRUE);
228: }
229:
230: /* Remove the header for block h */
231: void GC_remove_header(h)
232: register struct hblk * h;
233: {
234: hdr ** ha;
235:
236: GET_HDR_ADDR(h, ha);
237: free_hdr(*ha);
238: *ha = 0;
239: }
240:
241: /* Remove forwarding counts for h */
242: void GC_remove_counts(h, sz)
243: register struct hblk * h;
244: register word sz; /* bytes */
245: {
246: register struct hblk * hbp;
247:
248: for (hbp = h+1; (char *)hbp < (char *)h + sz; hbp += 1) {
249: SET_HDR(hbp, 0);
250: }
251: }
252:
253: /* Apply fn to all allocated blocks */
254: /*VARARGS1*/
255: void GC_apply_to_all_blocks(fn, client_data)
256: void (*fn)(/* struct hblk *h, word client_data */);
257: word client_data;
258: {
259: register int j;
260: register bottom_index * index_p;
261:
262: for (index_p = GC_all_bottom_indices; index_p != 0;
263: index_p = index_p -> asc_link) {
264: for (j = BOTTOM_SZ-1; j >= 0;) {
265: if (!IS_FORWARDING_ADDR_OR_NIL(index_p->index[j])) {
266: if (index_p->index[j]->hb_map != GC_invalid_map) {
267: (*fn)(((struct hblk *)
268: (((index_p->key << LOG_BOTTOM_SZ) + (word)j)
269: << LOG_HBLKSIZE)),
270: client_data);
271: }
272: j--;
273: } else if (index_p->index[j] == 0) {
274: j--;
275: } else {
276: j -= (word)(index_p->index[j]);
277: }
278: }
279: }
280: }
281:
282: /* Get the next valid block whose address is at least h */
283: /* Return 0 if there is none. */
1.1.1.2 ! maekawa 284: struct hblk * GC_next_used_block(h)
1.1 maekawa 285: struct hblk * h;
286: {
287: register bottom_index * bi;
288: register word j = ((word)h >> LOG_HBLKSIZE) & (BOTTOM_SZ-1);
289:
290: GET_BI(h, bi);
291: if (bi == GC_all_nils) {
292: register word hi = (word)h >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE);
293: bi = GC_all_bottom_indices;
294: while (bi != 0 && bi -> key < hi) bi = bi -> asc_link;
295: j = 0;
296: }
297: while(bi != 0) {
298: while (j < BOTTOM_SZ) {
1.1.1.2 ! maekawa 299: hdr * hhdr = bi -> index[j];
! 300: if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) {
1.1 maekawa 301: j++;
302: } else {
1.1.1.2 ! maekawa 303: if (hhdr->hb_map != GC_invalid_map) {
1.1 maekawa 304: return((struct hblk *)
305: (((bi -> key << LOG_BOTTOM_SZ) + j)
306: << LOG_HBLKSIZE));
307: } else {
1.1.1.2 ! maekawa 308: j += divHBLKSZ(hhdr -> hb_sz);
1.1 maekawa 309: }
310: }
311: }
312: j = 0;
313: bi = bi -> asc_link;
1.1.1.2 ! maekawa 314: }
! 315: return(0);
! 316: }
! 317:
! 318: /* Get the last (highest address) block whose address is */
! 319: /* at most h. Return 0 if there is none. */
! 320: /* Unlike the above, this may return a free block. */
! 321: struct hblk * GC_prev_block(h)
! 322: struct hblk * h;
! 323: {
! 324: register bottom_index * bi;
! 325: register signed_word j = ((word)h >> LOG_HBLKSIZE) & (BOTTOM_SZ-1);
! 326:
! 327: GET_BI(h, bi);
! 328: if (bi == GC_all_nils) {
! 329: register word hi = (word)h >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE);
! 330: bi = GC_all_bottom_indices_end;
! 331: while (bi != 0 && bi -> key > hi) bi = bi -> desc_link;
! 332: j = BOTTOM_SZ - 1;
! 333: }
! 334: while(bi != 0) {
! 335: while (j >= 0) {
! 336: hdr * hhdr = bi -> index[j];
! 337: if (0 == hhdr) {
! 338: --j;
! 339: } else if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) {
! 340: j -= (signed_word)hhdr;
! 341: } else {
! 342: return((struct hblk *)
! 343: (((bi -> key << LOG_BOTTOM_SZ) + j)
! 344: << LOG_HBLKSIZE));
! 345: }
! 346: }
! 347: j = BOTTOM_SZ - 1;
! 348: bi = bi -> desc_link;
1.1 maekawa 349: }
350: return(0);
351: }
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_contrib / gc