📄 tree.html
字号:
<HTML><HEAD> <TITLE> Two-Level Tree Structure for Fast Pointer Lookup</TITLE> <AUTHOR> Hans-J. Boehm, Silicon Graphics (now at HP)</author></HEAD><BODY><H1>Two-Level Tree Structure for Fast Pointer Lookup</h1><P>The conservative garbage collector described<A HREF="http://www.hpl.hp.com/personal/Hans_Boehm/gc/">here</a>uses a 2-level treedata structure to aid in fast pointer identification.This data structure is described in a bit more detail here, since<OL><LI> Variations of the data structure are more generally useful.<LI> It appears to be hard to understand by reading the code.<LI> Some other collectors appear to use inferior data structures tosolve the same problem.<LI> It is central to fast collector operation.</ol>A candidate pointer is divided into three sections, the <I>high</i>,<I>middle</i>, and <I>low</i> bits. The exact division between thesethree groups of bits is dependent on the detailed collector configuration.<P>The high and middle bits are used to look up an entry in the table describedhere. The resulting table entry consists of either a block descriptor(<TT>struct hblkhdr *</tt> or <TT>hdr *</tt>)identifying the layout of objects in the block, or an indication that thisaddress range corresponds to the middle of a large block, together with ahint for locating the actual block descriptor. Such a hint consistof a displacement that can be subtracted from the middle bits of the candidatepointer without leaving the object.<P>In either case, the block descriptor (<TT>struct hblkhdr</tt>)refers to a table of object starting addresses (the <TT>hb_map</tt> field).The starting address table is indexed by the low bits if the candidate pointer.The resulting entry contains a displacement to the beginning of the object,or an indication that this cannot be a valid object pointer.(If all interior pointer are recognized, pointers into large objectsare handled specially, as appropriate.)<H2>The Tree</h2><P>The rest of this discussion focuses on the two level data structureused to map the high and middle bits to the block descriptor.<P>The high bits are used as an index into the <TT>GC_top_index</tt> (really<TT>GC_arrays._top_index</tt>) array. Each entry points to a<TT>bottom_index</tt> data structure. This structure in turn consistsmostly of an array <TT>index</tt> indexed by the middle bits ofthe candidate pointer. The <TT>index</tt> array contains the actual<TT>hdr</tt> pointers. <P>Thus a pointer lookup consists primarily of a handful of memory references,and can be quite fast:<OL><LI> The appropriate <TT>bottom_index</tt> pointer is looked up in<TT>GC_top_index</tt>, based on the high bits of the candidate pointer.<LI> The appropriate <TT>hdr</tt> pointer is looked up in the<TT>bottom_index</tt> structure, based on the middle bits.<LI> The block layout map pointer is retrieved from the <TT>hdr</tt>structure. (This memory reference is necessary since we try to shareblock layout maps.)<LI> The displacement to the beginning of the object is retrieved from theabove map.</ol><P>In order to conserve space, not all <TT>GC_top_index</tt> entries in factpoint to distinct <TT>bottom_index</tt> structures. If no address withthe corresponding high bits is part of the heap, then the entry pointsto <TT>GC_all_nils</tt>, a single <TT>bottom_index</tt> structure consistingonly of NULL <TT>hdr</tt> pointers.<P><TT>Bottom_index</tt> structures contain slightly more information thanjust <TT>hdr</tt> pointers. The <TT>asc_link</tt> field is used to linkall <TT>bottom_index</tt> structures in ascending order for fast traversal.This list is pointed to be <TT>GC_all_bottom_indices</tt>.It is maintained with the aid of <TT>key</tt> field that contains thehigh bits corresponding to the <TT>bottom_index</tt>.<H2>64 bit addresses</h2><P>In the case of 64 bit addresses, this picture is complicated slightlyby the fact that one of the index structures would have to be huge tocover the entire address space with a two level tree. We deal with thisby turning <TT>GC_top_index</tt> into a chained hash table, instead ofa simple array. This adds a <TT>hash_link</tt> field to the<TT>bottom_index</tt> structure.<P>The "hash function" consists of dropping the high bits. This is cheap tocompute, and guarantees that there will be no collisions if the heapis contiguous and not excessively large.<H2>A picture</h2><P>The following is an ASCII diagram of the data structure.This was contributed by Dave Barrett several years ago.<PRE> Data Structure used by GC_base in gc3.7: 21-Apr-94 63 LOG_TOP_SZ[11] LOG_BOTTOM_SZ[10] LOG_HBLKSIZE[13] +------------------+----------------+------------------+------------------+ p:| | TL_HASH(hi) | | HBLKDISPL(p) | +------------------+----------------+------------------+------------------+ \-----------------------HBLKPTR(p)-------------------/ \------------hi-------------------/ \______ ________/ \________ _______/ \________ _______/ V V V | | | GC_top_index[] | | | --- +--------------+ | | | ^ | | | | | | | | | | | TOP +--------------+<--+ | | _SZ +-<| [] | * | | (items)| +--------------+ if 0 < bi< HBLKSIZE | | | | | | then large object | | | | | | starts at the bi'th | | v | | | HBLK before p. | i | --- | +--------------+ | (word- | v | aligned) | bi= |GET_BI(p){->hash_link}->key==hi | | v | | | (bottom_index) \ scratch_alloc'd | | | ( struct bi ) / by get_index() | | --- +->+--------------+ | | ^ | | | | ^ | | | | BOTTOM | | ha=GET_HDR_ADDR(p) | |_SZ(items)+--------------+<----------------------+ +-------+ | +--<| index[] | | | | +--------------+ GC_obj_map: v | | | | from / +-+-+-----+-+-+-+-+ --- v | | | GC_add < 0| | | | | | | | ^ --- | +--------------+ _map_entry \ +-+-+-----+-+-+-+-+ | | | asc_link | +-+-+-----+-+-+-+-+ MAXOBJSZ | +--------------+ +-->| | | j | | | | | +1 | | key | | +-+-+-----+-+-+-+-+ | | +--------------+ | +-+-+-----+-+-+-+-+ | | | hash_link | | | | | | | | | | v | +--------------+ | +-+-+-----+-+-+-+-+ --- | | |<--MAX_OFFSET--->| | | (bytes)HDR(p)| GC_find_header(p) | |<--MAP_ENTRIES-->| | \ from | =HBLKSIZE/WORDSZ | (hdr) (struct hblkhdr) / alloc_hdr() | (1024 on Alpha) +-->+----------------------+ | (8/16 bits each)GET_HDR(p)| word hb_sz (words) | | +----------------------+ | | struct hblk *hb_next | | +----------------------+ | |mark_proc hb_mark_proc| | +----------------------+ | | char * hb_map |>-------------+ +----------------------+ | ushort hb_obj_kind | +----------------------+ | hb_last_reclaimed | --- +----------------------+ ^ | | MARK_BITS| hb_marks[] | *if hdr is free, hb_sz + DISCARD_WORDS_SZ(words)| | is the size of a heap chunk (struct hblk) v | | of at least MININCR*HBLKSIZE bytes (below), --- +----------------------+ otherwise, size of each object in chunk.Dynamic data structures above are interleaved throughout the heap in blocks of size MININCR * HBLKSIZE bytes as done by gc_scratch_alloc which cannot befreed; free lists are used (e.g. alloc_hdr). HBLK's below are collected. (struct hblk) --- +----------------------+ < HBLKSIZE --- --- DISCARD_ ^ |garbage[DISCARD_WORDS]| aligned ^ ^ HDR_BYTES WORDS | | | | v (bytes) (words) | +-----hb_body----------+ < WORDSZ | --- --- | | | aligned | ^ ^ | | Object 0 | | hb_sz | | | | i |(word- (words)| | | | (bytes)|aligned) v | | + - - - - - - - - - - -+ --- | --- | | | | ^ | ^ | n * | | j (words) | hb_sz BODY_SZ HBLKSIZE | Object 1 | v v | (words) (bytes) | |--------------- v MAX_OFFSET | + - - - - - - - - - - -+ --- (bytes) | | | !All_INTERIOR_PTRS ^ | | | | sets j only for hb_sz | | | Object N | valid object offsets. | | v | | All objects WORDSZ v v --- +----------------------+ aligned. --- ---DISCARD_WORDS is normally zero. Indeed the collector has not been testedwith another value in ages.</pre></body>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -