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. 27 * 28 * This defines HDR, GET_HDR, and SET_HDR, the main macros used to 29 * retrieve and set object headers. 30 * 31 * We take advantage of a header lookup 32 * cache. This is a locally declared direct mapped cache, used inside 33 * the marker. The HC_GET_HDR macro uses and maintains this 34 * cache. Assuming we get reasonable hit rates, this shaves a few 35 * memory references from each pointer validation. 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 57 #ifndef SMALL_CONFIG 58 # define USE_HDR_CACHE 59 #endif 60 61 /* #define COUNT_HDR_CACHE_HITS */ 62 63 # ifdef COUNT_HDR_CACHE_HITS 64 extern word GC_hdr_cache_hits; 65 extern word GC_hdr_cache_misses; 66 # define HC_HIT() ++GC_hdr_cache_hits 67 # define HC_MISS() ++GC_hdr_cache_misses 68 # else 69 # define HC_HIT() 70 # define HC_MISS() 71 # endif 72 73 typedef struct hce { 74 word block_addr; /* right shifted by LOG_HBLKSIZE */ 75 hdr * hce_hdr; 76 } hdr_cache_entry; 77 78 # define HDR_CACHE_SIZE 8 /* power of 2 */ 79 80 # define DECLARE_HDR_CACHE \ 81 hdr_cache_entry hdr_cache[HDR_CACHE_SIZE] 82 83 # define INIT_HDR_CACHE BZERO(hdr_cache, sizeof(hdr_cache)) 84 85 # define HCE(h) hdr_cache + (((word)(h) >> LOG_HBLKSIZE) & (HDR_CACHE_SIZE-1)) 86 87 # define HCE_VALID_FOR(hce,h) ((hce) -> block_addr == \ 88 ((word)(h) >> LOG_HBLKSIZE)) 89 90 # define HCE_HDR(h) ((hce) -> hce_hdr) 91 92 #ifdef PRINT_BLACK_LIST 93 hdr * GC_header_cache_miss(ptr_t p, hdr_cache_entry *hce, ptr_t source); 94 # define HEADER_CACHE_MISS(p, hce, source) \ 95 GC_header_cache_miss(p, hce, source) 96 #else 97 hdr * GC_header_cache_miss(ptr_t p, hdr_cache_entry *hce); 98 # define HEADER_CACHE_MISS(p, hce, source) GC_header_cache_miss(p, hce) 99 #endif 100 101 /* Set hhdr to the header for p. Analogous to GET_HDR below, */ 102 /* except that in the case of large objects, it */ 103 /* gets the header for the object beginning, if GC_all_interior_ptrs */ 104 /* is set. */ 105 /* Returns zero if p points to somewhere other than the first page */ 106 /* of an object, and it is not a valid pointer to the object. */ 107 # define HC_GET_HDR(p, hhdr, source, exit_label) \ 108 { \ 109 hdr_cache_entry * hce = HCE(p); \ 110 if (EXPECT(HCE_VALID_FOR(hce, p), 1)) { \ 111 HC_HIT(); \ 112 hhdr = hce -> hce_hdr; \ 113 } else { \ 114 hhdr = HEADER_CACHE_MISS(p, hce, source); \ 115 if (0 == hhdr) goto exit_label; \ 116 } \ 117 } 118 119 typedef struct bi { 120 hdr * index[BOTTOM_SZ]; 121 /* 122 * The bottom level index contains one of three kinds of values: 123 * 0 means we're not responsible for this block, 124 * or this is a block other than the first one in a free block. 125 * 1 < (long)X <= MAX_JUMP means the block starts at least 126 * X * HBLKSIZE bytes before the current address. 127 * A valid pointer points to a hdr structure. (The above can't be 128 * valid pointers due to the GET_MEM return convention.) 129 */ 130 struct bi * asc_link; /* All indices are linked in */ 131 /* ascending order... */ 132 struct bi * desc_link; /* ... and in descending order. */ 133 word key; /* high order address bits. */ 134 # ifdef HASH_TL 135 struct bi * hash_link; /* Hash chain link. */ 136 # endif 137 } bottom_index; 138 139 /* extern bottom_index GC_all_nils; - really part of GC_arrays */ 140 141 /* extern bottom_index * GC_top_index []; - really part of GC_arrays */ 142 /* Each entry points to a bottom_index. */ 143 /* On a 32 bit machine, it points to */ 144 /* the index for a set of high order */ 145 /* bits equal to the index. For longer */ 146 /* addresses, we hash the high order */ 147 /* bits to compute the index in */ 148 /* GC_top_index, and each entry points */ 149 /* to a hash chain. */ 150 /* The last entry in each chain is */ 151 /* GC_all_nils. */ 152 153 154 # define MAX_JUMP (HBLKSIZE - 1) 155 156 # define HDR_FROM_BI(bi, p) \ 157 ((bi)->index[((word)(p) >> LOG_HBLKSIZE) & (BOTTOM_SZ - 1)]) 158 # ifndef HASH_TL 159 # define BI(p) (GC_top_index \ 160 [(word)(p) >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE)]) 161 # define HDR_INNER(p) HDR_FROM_BI(BI(p),p) 162 # ifdef SMALL_CONFIG 163 # define HDR(p) GC_find_header((ptr_t)(p)) 164 # else 165 # define HDR(p) HDR_INNER(p) 166 # endif 167 # define GET_BI(p, bottom_indx) (bottom_indx) = BI(p) 168 # define GET_HDR(p, hhdr) (hhdr) = HDR(p) 169 # define SET_HDR(p, hhdr) HDR_INNER(p) = (hhdr) 170 # define GET_HDR_ADDR(p, ha) (ha) = &(HDR_INNER(p)) 171 # else /* hash */ 172 /* Hash function for tree top level */ 173 # define TL_HASH(hi) ((hi) & (TOP_SZ - 1)) 174 /* Set bottom_indx to point to the bottom index for address p */ 175 # define GET_BI(p, bottom_indx) \ 176 { \ 177 register word hi = \ 178 (word)(p) >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE); \ 179 register bottom_index * _bi = GC_top_index[TL_HASH(hi)]; \ 180 \ 181 while (_bi -> key != hi && _bi != GC_all_nils) \ 182 _bi = _bi -> hash_link; \ 183 (bottom_indx) = _bi; \ 184 } 185 # define GET_HDR_ADDR(p, ha) \ 186 { \ 187 register bottom_index * bi; \ 188 \ 189 GET_BI(p, bi); \ 190 (ha) = &(HDR_FROM_BI(bi, p)); \ 191 } 192 # define GET_HDR(p, hhdr) { register hdr ** _ha; GET_HDR_ADDR(p, _ha); \ 193 (hhdr) = *_ha; } 194 # define SET_HDR(p, hhdr) { register hdr ** _ha; GET_HDR_ADDR(p, _ha); \ 195 *_ha = (hhdr); } 196 # define HDR(p) GC_find_header((ptr_t)(p)) 197 # endif 198 199 /* Is the result a forwarding address to someplace closer to the */ 200 /* beginning of the block or NIL? */ 201 # define IS_FORWARDING_ADDR_OR_NIL(hhdr) ((size_t) (hhdr) <= MAX_JUMP) 202 203 /* Get an HBLKSIZE aligned address closer to the beginning of the block */ 204 /* h. Assumes hhdr == HDR(h) and IS_FORWARDING_ADDR(hhdr). */ 205 # define FORWARDED_ADDR(h, hhdr) ((struct hblk *)(h) - (size_t)(hhdr)) 206 # endif /* GC_HEADERS_H */ 207