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 29 # if CPP_WORDSZ > 32 30 # define HASH_TL 31 # endif 32 33 /* Define appropriate out-degrees for each of the two tree levels */ 34 # ifdef SMALL_CONFIG 35 # define LOG_BOTTOM_SZ 11 36 /* Keep top index size reasonable with smaller blocks. */ 37 # else 38 # define LOG_BOTTOM_SZ 10 39 # endif 40 # ifndef HASH_TL 41 # define LOG_TOP_SZ (WORDSZ - LOG_BOTTOM_SZ - LOG_HBLKSIZE) 42 # else 43 # define LOG_TOP_SZ 11 44 # endif 45 # define TOP_SZ (1 << LOG_TOP_SZ) 46 # define BOTTOM_SZ (1 << LOG_BOTTOM_SZ) 47 48 typedef struct bi { 49 hdr * index[BOTTOM_SZ]; 50 /* 51 * The bottom level index contains one of three kinds of values: 52 * 0 means we're not responsible for this block. 53 * 1 < (long)X <= MAX_JUMP means the block starts at least 54 * X * HBLKSIZE bytes before the current address. 55 * A valid pointer points to a hdr structure. (The above can't be 56 * valid pointers due to the GET_MEM return convention.) 57 */ 58 struct bi * asc_link; /* All indices are linked in */ 59 /* ascending order. */ 60 word key; /* high order address bits. */ 61 # ifdef HASH_TL 62 struct bi * hash_link; /* Hash chain link. */ 63 # endif 64 } bottom_index; 65 66 /* extern bottom_index GC_all_nils; - really part of GC_arrays */ 67 68 /* extern bottom_index * GC_top_index []; - really part of GC_arrays */ 69 /* Each entry points to a bottom_index. */ 70 /* On a 32 bit machine, it points to */ 71 /* the index for a set of high order */ 72 /* bits equal to the index. For longer */ 73 /* addresses, we hash the high order */ 74 /* bits to compute the index in */ 75 /* GC_top_index, and each entry points */ 76 /* to a hash chain. */ 77 /* The last entry in each chain is */ 78 /* GC_all_nils. */ 79 80 81 # define MAX_JUMP (HBLKSIZE - 1) 82 83 # define HDR_FROM_BI(bi, p) \ 84 ((bi)->index[((word)(p) >> LOG_HBLKSIZE) & (BOTTOM_SZ - 1)]) 85 # ifndef HASH_TL 86 # define BI(p) (GC_top_index \ 87 [(word)(p) >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE)]) 88 # define HDR_INNER(p) HDR_FROM_BI(BI(p),p) 89 # ifdef SMALL_CONFIG 90 # define HDR(p) GC_find_header((ptr_t)(p)) 91 # else 92 # define HDR(p) HDR_INNER(p) 93 # endif 94 # define GET_BI(p, bottom_indx) (bottom_indx) = BI(p) 95 # define GET_HDR(p, hhdr) (hhdr) = HDR(p) 96 # define SET_HDR(p, hhdr) HDR_INNER(p) = (hhdr) 97 # define GET_HDR_ADDR(p, ha) (ha) = &(HDR_INNER(p)) 98 # else /* hash */ 99 /* Hash function for tree top level */ 100 # define TL_HASH(hi) ((hi) & (TOP_SZ - 1)) 101 /* Set bottom_indx to point to the bottom index for address p */ 102 # define GET_BI(p, bottom_indx) \ 103 { \ 104 register word hi = \ 105 (word)(p) >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE); \ 106 register bottom_index * _bi = GC_top_index[TL_HASH(hi)]; \ 107 \ 108 while (_bi -> key != hi && _bi != GC_all_nils) \ 109 _bi = _bi -> hash_link; \ 110 (bottom_indx) = _bi; \ 111 } 112 # define GET_HDR_ADDR(p, ha) \ 113 { \ 114 register bottom_index * bi; \ 115 \ 116 GET_BI(p, bi); \ 117 (ha) = &(HDR_FROM_BI(bi, p)); \ 118 } 119 # define GET_HDR(p, hhdr) { register hdr ** _ha; GET_HDR_ADDR(p, _ha); \ 120 (hhdr) = *_ha; } 121 # define SET_HDR(p, hhdr) { register hdr ** _ha; GET_HDR_ADDR(p, _ha); \ 122 *_ha = (hhdr); } 123 # define HDR(p) GC_find_header((ptr_t)(p)) 124 # endif 125 126 /* Is the result a forwarding address to someplace closer to the */ 127 /* beginning of the block or NIL? */ 128 # define IS_FORWARDING_ADDR_OR_NIL(hhdr) ((unsigned long) (hhdr) <= MAX_JUMP) 129 130 /* Get an HBLKSIZE aligned address closer to the beginning of the block */ 131 /* h. Assumes hhdr == HDR(h) and IS_FORWARDING_ADDR(hhdr). */ 132 # define FORWARDED_ADDR(h, hhdr) ((struct hblk *)(h) - (unsigned long)(hhdr)) 133 # endif /* GC_HEADERS_H */ 134