| 1 |
# Two-Level Tree Structure for Fast Pointer Lookup |
| 2 |
|
| 3 |
The Boehm-Demers-Weiser conservative Garbage Collector uses a 2-level tree |
| 4 |
data structure to aid in fast pointer identification. This data structure |
| 5 |
is 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 |
|
| 16 |
The high and middle bits are used to look up an entry in the table described |
| 17 |
here. The resulting table entry consists of either a block descriptor |
| 18 |
(`struct hblkhdr *` or `hdr *`) identifying the layout of objects in the |
| 19 |
block, or an indication that this address range corresponds to the middle of |
| 20 |
a large block, together with a hint for locating the actual block descriptor. |
| 21 |
Such a hint consist of a displacement that can be subtracted from the middle |
| 22 |
bits of the candidate pointer without leaving the object. |
| 23 |
|
| 24 |
In either case, the block descriptor (`struct hblkhdr`) refers to a table |
| 25 |
of object starting addresses (the `hb_map` field). The starting address table |
| 26 |
is indexed by the low bits if the candidate pointer. The resulting entry |
| 27 |
contains a displacement to the beginning of the object, or an indication that |
| 28 |
this cannot be a valid object pointer. (If all interior pointer are |
| 29 |
recognized, pointers into large objects are handled specially, |
| 30 |
as appropriate.) |
| 31 |
|
| 32 |
## The Tree |
| 33 |
|
| 34 |
The rest of this discussion focuses on the two level data structure used |
| 35 |
to map the high and middle bits to the block descriptor. |
| 36 |
|
| 37 |
The 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 |
| 39 |
structure. This structure in turn consists mostly of an array `index` indexed |
| 40 |
by the middle bits of the candidate pointer. The `index` array contains the |
| 41 |
actual `hdr` pointers. |
| 42 |
|
| 43 |
Thus a pointer lookup consists primarily of a handful of memory references, |
| 44 |
and 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 |
|
| 55 |
In order to conserve space, not all `GC_top_index` entries in fact point |
| 56 |
to distinct `bottom_index` structures. If no address with the corresponding |
| 57 |
high bits is part of the heap, then the entry points to `GC_all_nils`, |
| 58 |
a single `bottom_index` structure consisting only of `NULL` `hdr` pointers. |
| 59 |
|
| 60 |
`Bottom_index` structures contain slightly more information than just `hdr` |
| 61 |
pointers. The `asc_link` field is used to link all `bottom_index` structures |
| 62 |
in 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 |
| 64 |
contains the high bits corresponding to the `bottom_index`. |
| 65 |
|
| 66 |
## 64-bit addresses |
| 67 |
|
| 68 |
In the case of 64-bit addresses, this picture is complicated slightly by the |
| 69 |
fact that one of the index structures would have to be huge to cover the |
| 70 |
entire 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 |
| 72 |
a `hash_link` field to the `bottom_index` structure. |
| 73 |
|
| 74 |
The _hash function_ consists of dropping the high bits. This is cheap |
| 75 |
to compute, and guarantees that there will be no collisions if the heap |
| 76 |
is contiguous and not excessively large. |
| 77 |
|
| 78 |
## A picture |
| 79 |
|
| 80 |
The following is an _ASCII_ diagram of the data structure used by GC_base. This was |
| 81 |
contributed originally 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_SZ +--------------+<--+ | | |
| 98 |
(items)+-<| [] | * | | |
| 99 |
| | +--------------+ 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) \ GC_scratch_alloc'd | | |
| 108 |
| (struct bi) / by get_index() | | |
| 109 |
--- +->+--------------+ | | |
| 110 |
^ | | | | |
| 111 |
| | | | | |
| 112 |
BOTTOM_SZ | | ha=GET_HDR_ADDR(p) | | |
| 113 |
(items) +--------------+<----------------------+ +-------+ |
| 114 |
| +--<| index[] | | |
| 115 |
| | +--------------+ GC_obj_map: v |
| 116 |
| | | | from / +-+-+-----+-+-+-+-+ --- |
| 117 |
v | | | GC_add_map_entry <0| | | | | | | | ^ |
| 118 |
--- | +--------------+ \ +-+-+-----+-+-+-+-+ | |
| 119 |
| | asc_link | +-+-+-----+-+-+-+-+ MAXOBJGRANULES |
| 120 |
| +--------------+ +-->| | | j | | | | | +1 |
| 121 |
| | key | | +-+-+-----+-+-+-+-+ | |
| 122 |
| +--------------+ | +-+-+-----+-+-+-+-+ | |
| 123 |
| | hash_link | | | | | | | | | | v |
| 124 |
| +--------------+ | +-+-+-----+-+-+-+-+ --- |
| 125 |
| | |<----MAP_LEN---->| |
| 126 |
| | =HBLKSIZE/GRANULE_BYTES |
| 127 |
HDR(p)| GC_find_header(p) | (1024 elements on Alpha) |
| 128 |
| \ from | (16 bits each) |
| 129 |
| (hdr) (struct hblkhdr) / alloc_hdr() | |
| 130 |
+--->+----------------------+ | |
| 131 |
GET_HDR(p)| struct hblk *hb_next | | |
| 132 |
+----------------------+ | |
| 133 |
| ... | | |
| 134 |
+----------------------+ | |
| 135 |
| uchar hb_obj_kind | | |
| 136 |
+----------------------+ | |
| 137 |
| uchar hb_flags | | |
| 138 |
+----------------------+ | |
| 139 |
| hb_last_reclaimed | | |
| 140 |
+----------------------+ | |
| 141 |
| size_t hb_sz | | |
| 142 |
+----------------------+ | |
| 143 |
| word hb_descr | | |
| 144 |
+----------------------+ | |
| 145 |
| ushort *hb_map |>------------+ |
| 146 |
+----------------------+ |
| 147 |
| AO_t hb_n_marks | |
| 148 |
--- +----------------------+ |
| 149 |
^ | | |
| 150 |
| | | * if hdr is free, hb_sz is the size |
| 151 |
MARK_BITS_SZ| char/word hb_marks[] | of a heap chunk (struct hblk) of at |
| 152 |
| | | least MINHINCR*HBLKSIZE bytes (below); |
| 153 |
v | | otherwise, size of each object in chunk. |
| 154 |
--- +----------------------+ |
| 155 |
|
| 156 |
|
| 157 |
Dynamic data structures above are interleaved throughout the heap in blocks |
| 158 |
of size `MINHINCR * HBLKSIZE` bytes as done by `GC_scratch_alloc` which cannot |
| 159 |
be freed; free lists are used (e.g. `alloc_hdr`). `hblk`'s below are |
| 160 |
collected. |
| 161 |
|
| 162 |
|
| 163 |
(struct hblk) |
| 164 |
--- +----------------------+ < HBLKSIZE --- |
| 165 |
^ +-----hb_body----------+ (and WORDSZ- ^ --- --- |
| 166 |
| | | aligned) | ^ ^ |
| 167 |
| | | | | | |
| 168 |
| | | | hb_sz | |
| 169 |
| | Object 0 | | | | |
| 170 |
| | | i |(word- v | |
| 171 |
| + - - - - - - - - - - -+ --- (bytes)|aligned) --- | |
| 172 |
| | | ^ | ^ | |
| 173 |
| | | j (words) | | | |
| 174 |
n * | Object 1 | v v hb_sz HBLKSIZE/BYTES_PER_WORD |
| 175 |
HBLKSIZE | |--------------- | (words) |
| 176 |
(bytes) | | v | |
| 177 |
| + - - - - - - - - - - -+ --- | |
| 178 |
| | | !ALL_INTERIOR_POINTERS ^ | |
| 179 |
| | | sets j only for hb_sz | |
| 180 |
| | Object N | valid object offsets. | | |
| 181 |
v | | All objects WORDSZ- v v |
| 182 |
--- +----------------------+ aligned. --- --- |