Debian Codegraph @

gc/doc/tree.md

raw
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. --- ---