Annotation of OpenXM_contrib2/asir2000/gc/include/private/gc_hdrs.h, Revision 1.4
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, July 11, 1995 11:54 am PDT */
15: # ifndef GC_HEADERS_H
16: # define GC_HEADERS_H
17: typedef struct hblkhdr hdr;
18:
19: # if CPP_WORDSZ != 32 && CPP_WORDSZ < 36
20: --> Get a real machine.
21: # endif
22:
23: /*
24: * The 2 level tree data structure that is used to find block headers.
25: * If there are more than 32 bits in a pointer, the top level is a hash
26: * table.
1.2 noro 27: *
28: * This defines HDR, GET_HDR, and SET_HDR, the main macros used to
1.4 ! noro 29: * retrieve and set object headers.
1.2 noro 30: *
31: * Since 5.0 alpha 5, we can also take advantage of a header lookup
32: * cache. This is a locally declared direct mapped cache, used inside
1.4 ! noro 33: * the marker. The HC_GET_HDR macro uses and maintains this
1.2 noro 34: * cache. Assuming we get reasonable hit rates, this shaves a few
35: * memory references from each pointer validation.
1.1 noro 36: */
37:
38: # if CPP_WORDSZ > 32
39: # define HASH_TL
40: # endif
41:
42: /* Define appropriate out-degrees for each of the two tree levels */
43: # ifdef SMALL_CONFIG
44: # define LOG_BOTTOM_SZ 11
45: /* Keep top index size reasonable with smaller blocks. */
46: # else
47: # define LOG_BOTTOM_SZ 10
48: # endif
49: # ifndef HASH_TL
50: # define LOG_TOP_SZ (WORDSZ - LOG_BOTTOM_SZ - LOG_HBLKSIZE)
51: # else
52: # define LOG_TOP_SZ 11
53: # endif
54: # define TOP_SZ (1 << LOG_TOP_SZ)
55: # define BOTTOM_SZ (1 << LOG_BOTTOM_SZ)
56:
1.2 noro 57: #ifndef SMALL_CONFIG
58: # define USE_HDR_CACHE
59: #endif
60:
61: /* #define COUNT_HDR_CACHE_HITS */
62:
63: extern hdr * GC_invalid_header; /* header for an imaginary block */
64: /* containing no objects. */
65:
66:
67: /* Check whether p and corresponding hhdr point to long or invalid */
1.4 ! noro 68: /* object. If so, advance hhdr to */
1.2 noro 69: /* beginning of block, or set hhdr to GC_invalid_header. */
70: #define ADVANCE(p, hhdr, source) \
1.4 ! noro 71: { \
! 72: hdr * new_hdr = GC_invalid_header; \
! 73: p = GC_find_start(p, hhdr, &new_hdr); \
! 74: hhdr = new_hdr; \
1.2 noro 75: }
76:
77: #ifdef USE_HDR_CACHE
78:
79: # ifdef COUNT_HDR_CACHE_HITS
80: extern word GC_hdr_cache_hits;
81: extern word GC_hdr_cache_misses;
82: # define HC_HIT() ++GC_hdr_cache_hits
83: # define HC_MISS() ++GC_hdr_cache_misses
84: # else
85: # define HC_HIT()
86: # define HC_MISS()
87: # endif
88:
89: typedef struct hce {
90: word block_addr; /* right shifted by LOG_HBLKSIZE */
91: hdr * hce_hdr;
92: } hdr_cache_entry;
93:
94: # define HDR_CACHE_SIZE 8 /* power of 2 */
95:
96: # define DECLARE_HDR_CACHE \
97: hdr_cache_entry hdr_cache[HDR_CACHE_SIZE]
98:
99: # define INIT_HDR_CACHE BZERO(hdr_cache, sizeof(hdr_cache));
100:
101: # define HCE(h) hdr_cache + (((word)(h) >> LOG_HBLKSIZE) & (HDR_CACHE_SIZE-1))
102:
103: # define HCE_VALID_FOR(hce,h) ((hce) -> block_addr == \
104: ((word)(h) >> LOG_HBLKSIZE))
105:
106: # define HCE_HDR(h) ((hce) -> hce_hdr)
107:
108:
109: /* Analogous to GET_HDR, except that in the case of large objects, it */
110: /* Returns the header for the object beginning, and updates p. */
111: /* Returns &GC_bad_header instead of 0. All of this saves a branch */
112: /* in the fast path. */
113: # define HC_GET_HDR(p, hhdr, source) \
114: { \
115: hdr_cache_entry * hce = HCE(p); \
116: if (HCE_VALID_FOR(hce, p)) { \
117: HC_HIT(); \
118: hhdr = hce -> hce_hdr; \
119: } else { \
120: HC_MISS(); \
121: GET_HDR(p, hhdr); \
1.4 ! noro 122: if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) { \
! 123: ADVANCE(p, hhdr, source); \
! 124: } else { \
! 125: hce -> block_addr = (word)(p) >> LOG_HBLKSIZE; \
! 126: hce -> hce_hdr = hhdr; \
! 127: } \
1.2 noro 128: } \
129: }
130:
131: #else /* !USE_HDR_CACHE */
132:
133: # define DECLARE_HDR_CACHE
134:
135: # define INIT_HDR_CACHE
136:
137: # define HC_GET_HDR(p, hhdr, source) \
138: { \
139: GET_HDR(p, hhdr); \
1.4 ! noro 140: if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) { \
! 141: ADVANCE(p, hhdr, source); \
! 142: } \
1.2 noro 143: }
144: #endif
145:
1.1 noro 146: typedef struct bi {
147: hdr * index[BOTTOM_SZ];
148: /*
149: * The bottom level index contains one of three kinds of values:
150: * 0 means we're not responsible for this block,
151: * or this is a block other than the first one in a free block.
152: * 1 < (long)X <= MAX_JUMP means the block starts at least
153: * X * HBLKSIZE bytes before the current address.
154: * A valid pointer points to a hdr structure. (The above can't be
155: * valid pointers due to the GET_MEM return convention.)
156: */
157: struct bi * asc_link; /* All indices are linked in */
158: /* ascending order... */
159: struct bi * desc_link; /* ... and in descending order. */
160: word key; /* high order address bits. */
161: # ifdef HASH_TL
162: struct bi * hash_link; /* Hash chain link. */
163: # endif
164: } bottom_index;
165:
166: /* extern bottom_index GC_all_nils; - really part of GC_arrays */
167:
168: /* extern bottom_index * GC_top_index []; - really part of GC_arrays */
169: /* Each entry points to a bottom_index. */
170: /* On a 32 bit machine, it points to */
171: /* the index for a set of high order */
172: /* bits equal to the index. For longer */
173: /* addresses, we hash the high order */
174: /* bits to compute the index in */
175: /* GC_top_index, and each entry points */
176: /* to a hash chain. */
177: /* The last entry in each chain is */
178: /* GC_all_nils. */
179:
180:
181: # define MAX_JUMP (HBLKSIZE - 1)
182:
183: # define HDR_FROM_BI(bi, p) \
184: ((bi)->index[((word)(p) >> LOG_HBLKSIZE) & (BOTTOM_SZ - 1)])
185: # ifndef HASH_TL
186: # define BI(p) (GC_top_index \
187: [(word)(p) >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE)])
188: # define HDR_INNER(p) HDR_FROM_BI(BI(p),p)
189: # ifdef SMALL_CONFIG
190: # define HDR(p) GC_find_header((ptr_t)(p))
191: # else
192: # define HDR(p) HDR_INNER(p)
193: # endif
194: # define GET_BI(p, bottom_indx) (bottom_indx) = BI(p)
195: # define GET_HDR(p, hhdr) (hhdr) = HDR(p)
196: # define SET_HDR(p, hhdr) HDR_INNER(p) = (hhdr)
197: # define GET_HDR_ADDR(p, ha) (ha) = &(HDR_INNER(p))
198: # else /* hash */
199: /* Hash function for tree top level */
200: # define TL_HASH(hi) ((hi) & (TOP_SZ - 1))
201: /* Set bottom_indx to point to the bottom index for address p */
202: # define GET_BI(p, bottom_indx) \
203: { \
204: register word hi = \
205: (word)(p) >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE); \
206: register bottom_index * _bi = GC_top_index[TL_HASH(hi)]; \
207: \
208: while (_bi -> key != hi && _bi != GC_all_nils) \
209: _bi = _bi -> hash_link; \
210: (bottom_indx) = _bi; \
211: }
212: # define GET_HDR_ADDR(p, ha) \
213: { \
214: register bottom_index * bi; \
215: \
216: GET_BI(p, bi); \
217: (ha) = &(HDR_FROM_BI(bi, p)); \
218: }
219: # define GET_HDR(p, hhdr) { register hdr ** _ha; GET_HDR_ADDR(p, _ha); \
220: (hhdr) = *_ha; }
221: # define SET_HDR(p, hhdr) { register hdr ** _ha; GET_HDR_ADDR(p, _ha); \
222: *_ha = (hhdr); }
223: # define HDR(p) GC_find_header((ptr_t)(p))
224: # endif
225:
226: /* Is the result a forwarding address to someplace closer to the */
227: /* beginning of the block or NIL? */
228: # define IS_FORWARDING_ADDR_OR_NIL(hhdr) ((unsigned long) (hhdr) <= MAX_JUMP)
229:
230: /* Get an HBLKSIZE aligned address closer to the beginning of the block */
231: /* h. Assumes hhdr == HDR(h) and IS_FORWARDING_ADDR(hhdr). */
232: # define FORWARDED_ADDR(h, hhdr) ((struct hblk *)(h) - (unsigned long)(hhdr))
233: # endif /* GC_HEADERS_H */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to gc_hdrs.h CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM_contrib2 / asir2000 / gc / include / private