1# Two-Level Tree Structure for Fast Pointer Lookup 2 3The Boehm-Demers-Weiser conservative Garbage Collector uses a 2-level tree 4data structure to aid in fast pointer identification. This data structure 5is described in a bit more detail here, since 6 7 1. Variations of the data structure are more generally useful. 8 2. It appears to be hard to understand by reading the code. 9 3. Some other collectors appear to use inferior data structures to solve the 10 same problem. 11 4. It is central to fast collector operation. A candidate pointer 12 is divided into three sections, the _high_, _middle_, and _low_ bits. The 13 exact division between these three groups of bits is dependent on the 14 detailed collector configuration. 15 16The high and middle bits are used to look up an entry in the table described 17here. The resulting table entry consists of either a block descriptor 18(`struct hblkhdr *` or `hdr *`) identifying the layout of objects in the 19block, or an indication that this address range corresponds to the middle of 20a large block, together with a hint for locating the actual block descriptor. 21Such a hint consist of a displacement that can be subtracted from the middle 22bits of the candidate pointer without leaving the object. 23 24In either case, the block descriptor (`struct hblkhdr`) refers to a table 25of object starting addresses (the `hb_map` field). The starting address table 26is indexed by the low bits if the candidate pointer. The resulting entry 27contains a displacement to the beginning of the object, or an indication that 28this cannot be a valid object pointer. (If all interior pointer are 29recognized, pointers into large objects are handled specially, 30as appropriate.) 31 32## The Tree 33 34The rest of this discussion focuses on the two level data structure used 35to map the high and middle bits to the block descriptor. 36 37The high bits are used as an index into the `GC_top_index` (really 38`GC_arrays._top_index`) array. Each entry points to a `bottom_index` data 39structure. This structure in turn consists mostly of an array `index` indexed 40by the middle bits of the candidate pointer. The `index` array contains the 41actual `hdr` pointers. 42 43Thus a pointer lookup consists primarily of a handful of memory references, 44and can be quite fast: 45 46 1. The appropriate `bottom_index` pointer is looked up in `GC_top_index`, 47 based on the high bits of the candidate pointer. 48 2. The appropriate `hdr` pointer is looked up in the `bottom_index` 49 structure, based on the middle bits. 50 3. The block layout map pointer is retrieved from the `hdr` structure. (This 51 memory reference is necessary since we try to share block layout maps.) 52 4. The displacement to the beginning of the object is retrieved from the 53 above map. 54 55In order to conserve space, not all `GC_top_index` entries in fact point 56to distinct `bottom_index` structures. If no address with the corresponding 57high bits is part of the heap, then the entry points to `GC_all_nils`, 58a single `bottom_index` structure consisting only of `NULL` `hdr` pointers. 59 60`Bottom_index` structures contain slightly more information than just `hdr` 61pointers. The `asc_link` field is used to link all `bottom_index` structures 62in ascending order for fast traversal. This list is pointed to be 63`GC_all_bottom_indices`. It is maintained with the aid of `key` field that 64contains the high bits corresponding to the `bottom_index`. 65 66## 64-bit addresses 67 68In the case of 64-bit addresses, this picture is complicated slightly by the 69fact that one of the index structures would have to be huge to cover the 70entire address space with a two level tree. We deal with this by turning 71`GC_top_index` into a chained hash table, instead of a simple array. This adds 72a `hash_link` field to the `bottom_index` structure. 73 74The _hash function_ consists of dropping the high bits. This is cheap 75to compute, and guarantees that there will be no collisions if the heap 76is contiguous and not excessively large. 77 78## A picture 79 80The following is an _ASCII_ diagram of the data structure used by GC_base (as 81of GC v3.7, Apr 21, 1994). This was contributed by Dave Barrett. 82 83 84 63 LOG_TOP_SZ[11] LOG_BOTTOM_SZ[10] LOG_HBLKSIZE[13] 85 +------------------+----------------+------------------+------------------+ 86 p:| | TL_HASH(hi) | | HBLKDISPL(p) | 87 +------------------+----------------+------------------+------------------+ 88 \-----------------------HBLKPTR(p)-------------------/ 89 \------------hi-------------------/ 90 \______ ________/ \________ _______/ \________ _______/ 91 V V V 92 | | | 93 GC_top_index[] | | | 94 --- +--------------+ | | | 95 ^ | | | | | 96 | | | | | | 97 TOP +--------------+<--+ | | 98 _SZ +-<| [] | * | | 99 (items)| +--------------+ if 0 < bi< HBLKSIZE | | 100 | | | | then large object | | 101 | | | | starts at the bi'th | | 102 v | | | HBLK before p. | i | 103 --- | +--------------+ | (word- | 104 v | aligned) | 105 bi= |GET_BI(p){->hash_link}->key==hi | | 106 v | | 107 | (bottom_index) \ scratch_alloc'd | | 108 | ( struct bi ) / by get_index() | | 109 --- +->+--------------+ | | 110 ^ | | | | 111 ^ | | | | 112 BOTTOM | | ha=GET_HDR_ADDR(p) | | 113 _SZ(items)+--------------+<----------------------+ +-------+ 114 | +--<| index[] | | 115 | | +--------------+ GC_obj_map: v 116 | | | | from / +-+-+-----+-+-+-+-+ --- 117 v | | | GC_add < 0| | | | | | | | ^ 118 --- | +--------------+ _map_entry \ +-+-+-----+-+-+-+-+ | 119 | | asc_link | +-+-+-----+-+-+-+-+ MAXOBJSZ 120 | +--------------+ +-->| | | j | | | | | +1 121 | | key | | +-+-+-----+-+-+-+-+ | 122 | +--------------+ | +-+-+-----+-+-+-+-+ | 123 | | hash_link | | | | | | | | | | v 124 | +--------------+ | +-+-+-----+-+-+-+-+ --- 125 | | |<--MAX_OFFSET--->| 126 | | (bytes) 127 HDR(p)| GC_find_header(p) | |<--MAP_ENTRIES-->| 128 | \ from | =HBLKSIZE/WORDSZ 129 | (hdr) (struct hblkhdr) / alloc_hdr() | (1024 on Alpha) 130 +-->+----------------------+ | (8/16 bits each) 131 GET_HDR(p)| word hb_sz (words) | | 132 +----------------------+ | 133 | struct hblk *hb_next | | 134 +----------------------+ | 135 |mark_proc hb_mark_proc| | 136 +----------------------+ | 137 | char * hb_map |>-------------+ 138 +----------------------+ 139 | ushort hb_obj_kind | 140 +----------------------+ 141 | hb_last_reclaimed | 142 --- +----------------------+ 143 ^ | | 144 MARK_BITS| hb_marks[] | * if hdr is free, hb_sz is the size of 145 _SZ(words)| | a heap chunk (struct hblk) of at least 146 v | | MININCR*HBLKSIZE bytes (below), 147 --- +----------------------+ otherwise, size of each object in chunk. 148 149 150Dynamic data structures above are interleaved throughout the heap in blocks 151of size `MININCR * HBLKSIZE` bytes as done by `gc_scratch_alloc` which cannot 152be freed; free lists are used (e.g. `alloc_hdr`). `HBLK`'s below are 153collected. 154 155 156 (struct hblk) HDR_BYTES 157 --- +----------------------+ < HBLKSIZE --- (bytes) 158 ^ +-----hb_body----------+ (and WORDSZ) ^ --- --- 159 | | | aligned | ^ ^ 160 | | | | hb_sz | 161 | | | | (words) | 162 | | Object 0 | | | | 163 | | | i |(word- v | 164 | + - - - - - - - - - - -+ --- (bytes)|aligned) --- | 165 | | | ^ | ^ | 166 | | | j (words) | | | 167 n * | Object 1 | v v hb_sz BODY_SZ 168 HBLKSIZE | |--------------- | (words) 169 (bytes) | | v MAX_OFFSET 170 | + - - - - - - - - - - -+ --- (bytes) 171 | | | !ALL_INTERIOR_POINTERS ^ | 172 | | | sets j only for hb_sz | 173 | | Object N | valid object offsets. | | 174 v | | All objects WORDSZ v v 175 --- +----------------------+ aligned. --- --- 176