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