1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
|
/*
* Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
* Copyright (c) 1991-1994 by Xerox Corporation. All rights reserved.
*
* THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
* OR IMPLIED. ANY USE IS AT YOUR OWN RISK.
*
* Permission is hereby granted to use or copy this program
* for any purpose, provided the above notices are retained on all copies.
* Permission to modify the code and to distribute modified code is granted,
* provided the above notices are retained, and a notice that the code was
* modified is included with the above copyright notice.
*/
/* Boehm, July 11, 1995 11:54 am PDT */
# ifndef GC_HEADERS_H
# define GC_HEADERS_H
typedef struct hblkhdr hdr;
# if CPP_WORDSZ != 32 && CPP_WORDSZ < 36
--> Get a real machine.
# endif
/*
* The 2 level tree data structure that is used to find block headers.
* If there are more than 32 bits in a pointer, the top level is a hash
* table.
*
* This defines HDR, GET_HDR, and SET_HDR, the main macros used to
* retrieve and set object headers. We also define some variants to
* retrieve 2 unrelated headers in interleaved fashion. This
* slightly improves scheduling.
*
* Since 5.0 alpha 5, we can also take advantage of a header lookup
* cache. This is a locally declared direct mapped cache, used inside
* the marker. The HC_GET_HDR and HC_GET_HDR2 macros use and maintain this
* cache. Assuming we get reasonable hit rates, this shaves a few
* memory references from each pointer validation.
*/
# if CPP_WORDSZ > 32
# define HASH_TL
# endif
/* Define appropriate out-degrees for each of the two tree levels */
# ifdef SMALL_CONFIG
# define LOG_BOTTOM_SZ 11
/* Keep top index size reasonable with smaller blocks. */
# else
# define LOG_BOTTOM_SZ 10
# endif
# ifndef HASH_TL
# define LOG_TOP_SZ (WORDSZ - LOG_BOTTOM_SZ - LOG_HBLKSIZE)
# else
# define LOG_TOP_SZ 11
# endif
# define TOP_SZ (1 << LOG_TOP_SZ)
# define BOTTOM_SZ (1 << LOG_BOTTOM_SZ)
#ifndef SMALL_CONFIG
# define USE_HDR_CACHE
#endif
/* #define COUNT_HDR_CACHE_HITS */
extern hdr * GC_invalid_header; /* header for an imaginary block */
/* containing no objects. */
/* Check whether p and corresponding hhdr point to long or invalid */
/* object. If so, advance them to */
/* beginning of block, or set hhdr to GC_invalid_header. */
#define ADVANCE(p, hhdr, source) \
if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) { \
p = GC_FIND_START(p, hhdr, (word)source); \
if (p == 0) { \
hhdr = GC_invalid_header; \
} else { \
hhdr = GC_find_header(p); \
} \
}
#ifdef USE_HDR_CACHE
# ifdef COUNT_HDR_CACHE_HITS
extern word GC_hdr_cache_hits;
extern word GC_hdr_cache_misses;
# define HC_HIT() ++GC_hdr_cache_hits
# define HC_MISS() ++GC_hdr_cache_misses
# else
# define HC_HIT()
# define HC_MISS()
# endif
typedef struct hce {
word block_addr; /* right shifted by LOG_HBLKSIZE */
hdr * hce_hdr;
} hdr_cache_entry;
# define HDR_CACHE_SIZE 8 /* power of 2 */
# define DECLARE_HDR_CACHE \
hdr_cache_entry hdr_cache[HDR_CACHE_SIZE]
# define INIT_HDR_CACHE BZERO(hdr_cache, sizeof(hdr_cache));
# define HCE(h) hdr_cache + (((word)(h) >> LOG_HBLKSIZE) & (HDR_CACHE_SIZE-1))
# define HCE_VALID_FOR(hce,h) ((hce) -> block_addr == \
((word)(h) >> LOG_HBLKSIZE))
# define HCE_HDR(h) ((hce) -> hce_hdr)
/* Analogous to GET_HDR, except that in the case of large objects, it */
/* Returns the header for the object beginning, and updates p. */
/* Returns &GC_bad_header instead of 0. All of this saves a branch */
/* in the fast path. */
# define HC_GET_HDR(p, hhdr, source) \
{ \
hdr_cache_entry * hce = HCE(p); \
if (HCE_VALID_FOR(hce, p)) { \
HC_HIT(); \
hhdr = hce -> hce_hdr; \
} else { \
HC_MISS(); \
GET_HDR(p, hhdr); \
ADVANCE(p, hhdr, source); \
hce -> block_addr = (word)(p) >> LOG_HBLKSIZE; \
hce -> hce_hdr = hhdr; \
} \
}
# define HC_GET_HDR2(p1, hhdr1, source1, p2, hhdr2, source2) \
{ \
hdr_cache_entry * hce1 = HCE(p1); \
hdr_cache_entry * hce2 = HCE(p2); \
if (HCE_VALID_FOR(hce1, p1)) { \
HC_HIT(); \
hhdr1 = hce1 -> hce_hdr; \
} else { \
HC_MISS(); \
GET_HDR(p1, hhdr1); \
ADVANCE(p1, hhdr1, source1); \
hce1 -> block_addr = (word)(p1) >> LOG_HBLKSIZE; \
hce1 -> hce_hdr = hhdr1; \
} \
if (HCE_VALID_FOR(hce2, p2)) { \
HC_HIT(); \
hhdr2 = hce2 -> hce_hdr; \
} else { \
HC_MISS(); \
GET_HDR(p2, hhdr2); \
ADVANCE(p2, hhdr2, source2); \
hce2 -> block_addr = (word)(p2) >> LOG_HBLKSIZE; \
hce2 -> hce_hdr = hhdr2; \
} \
}
#else /* !USE_HDR_CACHE */
# define DECLARE_HDR_CACHE
# define INIT_HDR_CACHE
# define HC_GET_HDR(p, hhdr, source) \
{ \
GET_HDR(p, hhdr); \
ADVANCE(p, hhdr, source); \
}
# define HC_GET_HDR2(p1, hhdr1, source1, p2, hhdr2, source2) \
{ \
GET_HDR2(p1, hhdr1, p2, hhdr2); \
ADVANCE(p1, hhdr1, source1); \
ADVANCE(p2, hhdr2, source2); \
}
#endif
typedef struct bi {
hdr * index[BOTTOM_SZ];
/*
* The bottom level index contains one of three kinds of values:
* 0 means we're not responsible for this block,
* or this is a block other than the first one in a free block.
* 1 < (long)X <= MAX_JUMP means the block starts at least
* X * HBLKSIZE bytes before the current address.
* A valid pointer points to a hdr structure. (The above can't be
* valid pointers due to the GET_MEM return convention.)
*/
struct bi * asc_link; /* All indices are linked in */
/* ascending order... */
struct bi * desc_link; /* ... and in descending order. */
word key; /* high order address bits. */
# ifdef HASH_TL
struct bi * hash_link; /* Hash chain link. */
# endif
} bottom_index;
/* extern bottom_index GC_all_nils; - really part of GC_arrays */
/* extern bottom_index * GC_top_index []; - really part of GC_arrays */
/* Each entry points to a bottom_index. */
/* On a 32 bit machine, it points to */
/* the index for a set of high order */
/* bits equal to the index. For longer */
/* addresses, we hash the high order */
/* bits to compute the index in */
/* GC_top_index, and each entry points */
/* to a hash chain. */
/* The last entry in each chain is */
/* GC_all_nils. */
# define MAX_JUMP (HBLKSIZE - 1)
# define HDR_FROM_BI(bi, p) \
((bi)->index[((word)(p) >> LOG_HBLKSIZE) & (BOTTOM_SZ - 1)])
# ifndef HASH_TL
# define BI(p) (GC_top_index \
[(word)(p) >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE)])
# define HDR_INNER(p) HDR_FROM_BI(BI(p),p)
# ifdef SMALL_CONFIG
# define HDR(p) GC_find_header((ptr_t)(p))
# else
# define HDR(p) HDR_INNER(p)
# endif
# define GET_BI(p, bottom_indx) (bottom_indx) = BI(p)
# define GET_HDR(p, hhdr) (hhdr) = HDR(p)
# define SET_HDR(p, hhdr) HDR_INNER(p) = (hhdr)
# define GET_HDR_ADDR(p, ha) (ha) = &(HDR_INNER(p))
# define GET_HDR2(p1, hhdr1, p2, hhdr2) \
{ GET_HDR(p1, hhdr1); GET_HDR(p2, hhdr2); }
# else /* hash */
/* Hash function for tree top level */
# define TL_HASH(hi) ((hi) & (TOP_SZ - 1))
/* Set bottom_indx to point to the bottom index for address p */
# define GET_BI(p, bottom_indx) \
{ \
register word hi = \
(word)(p) >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE); \
register bottom_index * _bi = GC_top_index[TL_HASH(hi)]; \
\
while (_bi -> key != hi && _bi != GC_all_nils) \
_bi = _bi -> hash_link; \
(bottom_indx) = _bi; \
}
# define GET_HDR_ADDR(p, ha) \
{ \
register bottom_index * bi; \
\
GET_BI(p, bi); \
(ha) = &(HDR_FROM_BI(bi, p)); \
}
# define GET_HDR(p, hhdr) { register hdr ** _ha; GET_HDR_ADDR(p, _ha); \
(hhdr) = *_ha; }
# define SET_HDR(p, hhdr) { register hdr ** _ha; GET_HDR_ADDR(p, _ha); \
*_ha = (hhdr); }
# define HDR(p) GC_find_header((ptr_t)(p))
/* And some interleaved versions for two pointers at once. */
/* This hopefully helps scheduling on processors like IA64. */
# define GET_BI2(p1, bottom_indx1, p2, bottom_indx2) \
{ \
register word hi1 = \
(word)(p1) >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE); \
register word hi2 = \
(word)(p2) >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE); \
register bottom_index * _bi1 = GC_top_index[TL_HASH(hi1)]; \
register bottom_index * _bi2 = GC_top_index[TL_HASH(hi2)]; \
\
while (_bi1 -> key != hi1 && _bi1 != GC_all_nils) \
_bi1 = _bi1 -> hash_link; \
while (_bi2 -> key != hi2 && _bi2 != GC_all_nils) \
_bi2 = _bi2 -> hash_link; \
(bottom_indx1) = _bi1; \
(bottom_indx2) = _bi2; \
}
# define GET_HDR_ADDR2(p1, ha1, p2, ha2) \
{ \
register bottom_index * bi1; \
register bottom_index * bi2; \
\
GET_BI2(p1, bi1, p2, bi2); \
(ha1) = &(HDR_FROM_BI(bi1, p1)); \
(ha2) = &(HDR_FROM_BI(bi2, p2)); \
}
# define GET_HDR2(p1, hhdr1, p2, hhdr2) \
{ register hdr ** _ha1; \
register hdr ** _ha2; \
GET_HDR_ADDR2(p1, _ha1, p2, _ha2); \
(hhdr1) = *_ha1; \
(hhdr2) = *_ha2; \
}
# endif
/* Is the result a forwarding address to someplace closer to the */
/* beginning of the block or NIL? */
# define IS_FORWARDING_ADDR_OR_NIL(hhdr) ((unsigned long) (hhdr) <= MAX_JUMP)
/* Get an HBLKSIZE aligned address closer to the beginning of the block */
/* h. Assumes hhdr == HDR(h) and IS_FORWARDING_ADDR(hhdr). */
# define FORWARDED_ADDR(h, hhdr) ((struct hblk *)(h) - (unsigned long)(hhdr))
# endif /* GC_HEADERS_H */
|
