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 15 #ifndef GC_HEADERS_H
16 #define GC_HEADERS_H
17 18 #if !defined(GC_PRIVATE_H) && !defined(CPPCHECK)
19 # error gc_hdrs.h should be included from gc_priv.h
20 #endif
21 22 #if CPP_WORDSZ != 32 && CPP_WORDSZ < 36 && !defined(CPPCHECK)
23 # error Get a real machine
24 #endif
25 26 EXTERN_C_BEGIN
27 28 /*
29 * The 2-level tree data structure that is used to find block headers.
30 * If there are more than 32 bits in a pointer, the top level is a hash
31 * table.
32 *
33 * This defines `HDR()`, `GET_HDR()`, and `SET_HDR()`, the main macros
34 * used to retrieve and set object headers.
35 *
36 * We take advantage of a header lookup cache. This is a locally declared
37 * direct mapped cache, used inside the marker. The `HC_GET_HDR()` macro
38 * uses and maintains this cache. Assuming we get reasonable hit rates,
39 * this saves a few memory references from each pointer validation.
40 */
41 42 #if CPP_WORDSZ > 32
43 # define HASH_TL
44 #endif
45 46 /* Define appropriate out-degrees for each of the two tree levels. */
47 #if defined(LARGE_CONFIG) || !defined(SMALL_CONFIG)
48 # define LOG_BOTTOM_SZ 10
49 #else
50 /* Keep top index size reasonable with smaller blocks. */
51 # define LOG_BOTTOM_SZ 11
52 #endif
53 #define BOTTOM_SZ (1 << LOG_BOTTOM_SZ)
54 55 #ifndef HASH_TL
56 # define LOG_TOP_SZ (CPP_WORDSZ - LOG_BOTTOM_SZ - LOG_HBLKSIZE)
57 #else
58 # define LOG_TOP_SZ 11
59 #endif
60 #define TOP_SZ (1 << LOG_TOP_SZ)
61 62 #ifdef COUNT_HDR_CACHE_HITS
63 extern word GC_hdr_cache_hits; /*< used for debugging/profiling */
64 extern word GC_hdr_cache_misses;
65 # define HC_HIT() (void)(++GC_hdr_cache_hits)
66 # define HC_MISS() (void)(++GC_hdr_cache_misses)
67 #else
68 # define HC_HIT() (void)0
69 # define HC_MISS() (void)0
70 #endif
71 72 typedef struct hce {
73 word block_addr; /*< right-shifted by `LOG_HBLKSIZE` */
74 hdr *hce_hdr;
75 } hdr_cache_entry;
76 77 #define HDR_CACHE_SIZE 8 /*< a power of two */
78 79 #define DECLARE_HDR_CACHE hdr_cache_entry hdr_cache[HDR_CACHE_SIZE]
80 81 #define INIT_HDR_CACHE BZERO(hdr_cache, sizeof(hdr_cache))
82 83 #define HCE(h) (hdr_cache + ((ADDR(h) >> LOG_HBLKSIZE) & (HDR_CACHE_SIZE - 1)))
84 85 #define HCE_VALID_FOR(hce, h) ((hce)->block_addr == (ADDR(h) >> LOG_HBLKSIZE))
86 87 #define HCE_HDR(h) ((hce)->hce_hdr)
88 89 #ifdef PRINT_BLACK_LIST
90 /*
91 * Handle a header cache miss. Returns a pointer to the header
92 * corresponding to `p`, if the latter can possibly be a valid object
93 * pointer, and `NULL` otherwise. Guaranteed to return `NULL` for
94 * a pointer past the first page of an object unless both
95 * `GC_all_interior_pointers` is set and `p` is in fact a valid object
96 * pointer. Never returns a pointer to a free `hblk`.
97 */
98 GC_INNER hdr *GC_header_cache_miss(ptr_t p, hdr_cache_entry *hce,
99 ptr_t source);
100 101 # define HEADER_CACHE_MISS(p, hce, source) \
102 GC_header_cache_miss(p, hce, source)
103 #else
104 GC_INNER hdr *GC_header_cache_miss(ptr_t p, hdr_cache_entry *hce);
105 # define HEADER_CACHE_MISS(p, hce, source) GC_header_cache_miss(p, hce)
106 #endif
107 108 /*
109 * Set `hhdr` to the header for `p`. Analogous to `GET_HDR()` below,
110 * except that in the case of large objects, it gets the header for the
111 * object beginning if `GC_all_interior_pointers` is true. Sets `hhdr`
112 * to `NULL` if `p` points to somewhere other than the first page of an
113 * object, and it is not a valid pointer to the object.
114 */
115 #define HC_GET_HDR(p, hhdr, source) \
116 { /*< cannot use `do ... while (0)` here */ \
117 hdr_cache_entry *hce = HCE(p); \
118 if (LIKELY(HCE_VALID_FOR(hce, p))) { \
119 HC_HIT(); \
120 hhdr = hce->hce_hdr; \
121 } else { \
122 hhdr = HEADER_CACHE_MISS(p, hce, source); \
123 if (NULL == hhdr) \
124 break; /*< go to the enclosing loop end */ \
125 } \
126 }
127 128 typedef struct bi {
129 /*
130 * The bottom-level index contains one of three kinds of values:
131 * - 0 means we are not responsible for this block, or this is
132 * a block other than the first one in a free block;
133 * - 1 < (long)`x` <= `MAX_JUMP` means the block starts at least
134 * `x * HBLKSIZE` bytes before the current address;
135 * - a valid pointer points to a `hdr` structure (the above cannot
136 * be valid pointers due to the `GET_MEM()` return convention).
137 */
138 hdr *index[BOTTOM_SZ];
139 140 /*
141 * All indices are linked in the ascending and descending orders,
142 * respectively.
143 */
144 struct bi *asc_link;
145 struct bi *desc_link;
146 147 word key; /*< high-order address bits */
148 #ifdef HASH_TL
149 struct bi *hash_link; /*< hash chain link */
150 #endif
151 } bottom_index;
152 153 #define MAX_JUMP (HBLKSIZE - 1)
154 155 #define HDR_FROM_BI(bi, p) \
156 (bi)->index[(ADDR(p) >> LOG_HBLKSIZE) & (BOTTOM_SZ - 1)]
157 #ifndef HASH_TL
158 # define BI(p) GC_top_index[ADDR(p) >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE)]
159 # define HDR_INNER(p) HDR_FROM_BI(BI(p), p)
160 # ifdef SMALL_CONFIG
161 # define HDR(p) GC_find_header(p)
162 # else
163 # define HDR(p) HDR_INNER(p)
164 # endif
165 # define GET_BI(p, bottom_indx) (void)((bottom_indx) = BI(p))
166 # define GET_HDR(p, hhdr) (void)((hhdr) = HDR(p))
167 # define SET_HDR(p, hhdr) (void)(HDR_INNER(p) = (hhdr))
168 # define GET_HDR_ADDR(p, ha) (void)((ha) = &HDR_INNER(p))
169 #else
170 /* A hash function for the tree top level. */
171 # define TL_HASH(hi) ((hi) & (TOP_SZ - 1))
172 /* Set `bottom_indx` to point to the bottom index for address `p`. */
173 # define GET_BI(p, bottom_indx) \
174 do { \
175 REGISTER word hi = ADDR(p) >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE); \
176 REGISTER bottom_index *_bi = GC_top_index[TL_HASH(hi)]; \
177 while (_bi->key != hi && _bi != GC_all_nils) \
178 _bi = _bi->hash_link; \
179 (bottom_indx) = _bi; \
180 } while (0)
181 # define GET_HDR_ADDR(p, ha) \
182 do { \
183 REGISTER bottom_index *bi; \
184 GET_BI(p, bi); \
185 (ha) = &HDR_FROM_BI(bi, p); \
186 } while (0)
187 # define GET_HDR(p, hhdr) \
188 do { \
189 REGISTER hdr **_ha; \
190 GET_HDR_ADDR(p, _ha); \
191 (hhdr) = *_ha; \
192 } while (0)
193 # define SET_HDR(p, hhdr) \
194 do { \
195 REGISTER bottom_index *bi; \
196 GET_BI(p, bi); \
197 GC_ASSERT(bi != GC_all_nils); \
198 HDR_FROM_BI(bi, p) = (hhdr); \
199 } while (0)
200 # define HDR(p) GC_find_header(p)
201 #endif
202 203 /*
204 * Is the result a forwarding address to someplace closer to the
205 * beginning of the block or `NULL`?
206 */
207 #define IS_FORWARDING_ADDR_OR_NIL(hhdr) ((size_t)ADDR(hhdr) <= MAX_JUMP)
208 209 /*
210 * Get an `HBLKSIZE`-aligned address closer to the beginning of the
211 * block `h`. Assumes that `hhdr` is equal to `HDR(h)`,
212 * `IS_FORWARDING_ADDR(hhdr)` is true and `hhdr` is not `NULL`.
213 * `HDR(result)` is expected to be non-`NULL`.
214 */
215 #define FORWARDED_ADDR(h, hhdr) \
216 ((struct hblk *)(h) - (size_t)(GC_uintptr_t)(hhdr))
217 218 EXTERN_C_END
219 220 #endif /* GC_HEADERS_H */
221