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
|
/*
* 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.
*/
#ifndef GC_HEADERS_H
#define GC_HEADERS_H
#if CPP_WORDSZ != 32 && CPP_WORDSZ < 36 && !defined(CPPCHECK)
# error Get a real machine
#endif
EXTERN_C_BEGIN
typedef struct hblkhdr hdr;
/*
* 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 take advantage of a header lookup
* cache. This is a locally declared direct mapped cache, used inside
* the marker. The HC_GET_HDR macro uses and maintains 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 */
#if defined(LARGE_CONFIG) || !defined(SMALL_CONFIG)
# define LOG_BOTTOM_SZ 10
#else
# define LOG_BOTTOM_SZ 11
/* Keep top index size reasonable with smaller blocks. */
#endif
#define BOTTOM_SZ (1 << LOG_BOTTOM_SZ)
#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 COUNT_HDR_CACHE_HITS */
#ifdef COUNT_HDR_CACHE_HITS
extern word GC_hdr_cache_hits; /* used for debugging/profiling */
extern word GC_hdr_cache_misses;
# define HC_HIT() (void)(++GC_hdr_cache_hits)
# define HC_MISS() (void)(++GC_hdr_cache_misses)
#else
# define HC_HIT() /* empty */
# define HC_MISS() /* empty */
#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)
#ifdef PRINT_BLACK_LIST
GC_INNER hdr * GC_header_cache_miss(ptr_t p, hdr_cache_entry *hce,
ptr_t source);
# define HEADER_CACHE_MISS(p, hce, source) \
GC_header_cache_miss(p, hce, source)
#else
GC_INNER hdr * GC_header_cache_miss(ptr_t p, hdr_cache_entry *hce);
# define HEADER_CACHE_MISS(p, hce, source) GC_header_cache_miss(p, hce)
#endif
/* Set hhdr to the header for p. Analogous to GET_HDR below, */
/* except that in the case of large objects, it gets the header for */
/* the object beginning if GC_all_interior_pointers is set. */
/* Returns zero if p points to somewhere other than the first page */
/* of an object, and it is not a valid pointer to the object. */
#define HC_GET_HDR(p, hhdr, source) \
{ /* cannot use do-while(0) here */ \
hdr_cache_entry * hce = HCE(p); \
if (EXPECT(HCE_VALID_FOR(hce, p), TRUE)) { \
HC_HIT(); \
hhdr = hce -> hce_hdr; \
} else { \
hhdr = HEADER_CACHE_MISS(p, hce, source); \
if (NULL == hhdr) break; /* go to the enclosing loop end */ \
} \
}
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;
/* 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) (void)((bottom_indx) = BI(p))
# define GET_HDR(p, hhdr) (void)((hhdr) = HDR(p))
# define SET_HDR(p, hhdr) (void)(HDR_INNER(p) = (hhdr))
# define GET_HDR_ADDR(p, ha) (void)((ha) = &HDR_INNER(p))
#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) \
do { \
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; \
} while (0)
# define GET_HDR_ADDR(p, ha) \
do { \
REGISTER bottom_index * bi; \
GET_BI(p, bi); \
(ha) = &HDR_FROM_BI(bi, p); \
} while (0)
# define GET_HDR(p, hhdr) \
do { \
REGISTER hdr ** _ha; \
GET_HDR_ADDR(p, _ha); \
(hhdr) = *_ha; \
} while (0)
# define SET_HDR(p, hhdr) \
do { \
REGISTER hdr ** _ha; \
GET_HDR_ADDR(p, _ha); \
*_ha = (hhdr); \
} while (0)
# define HDR(p) GC_find_header((ptr_t)(p))
#endif
/* Is the result a forwarding address to someplace closer to the */
/* beginning of the block or NULL? */
#define IS_FORWARDING_ADDR_OR_NIL(hhdr) ((size_t) (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) - (size_t)(hhdr))
EXTERN_C_END
#endif /* GC_HEADERS_H */
|
