| 1 | This is an ASCII diagram of the data structure used to check pointer
|
|---|
| 2 | validity. It was provided by Dave Barrett <barrett@asgard.cs.colorado.edu>,
|
|---|
| 3 | and should be of use to others attempting to understand the code.
|
|---|
| 4 | The data structure in GC4.X is essentially the same. -HB
|
|---|
| 5 |
|
|---|
| 6 |
|
|---|
| 7 |
|
|---|
| 8 |
|
|---|
| 9 | Data Structure used by GC_base in gc3.7:
|
|---|
| 10 | 21-Apr-94
|
|---|
| 11 |
|
|---|
| 12 |
|
|---|
| 13 |
|
|---|
| 14 |
|
|---|
| 15 | 63 LOG_TOP_SZ[11] LOG_BOTTOM_SZ[10] LOG_HBLKSIZE[13]
|
|---|
| 16 | +------------------+----------------+------------------+------------------+
|
|---|
| 17 | p:| | TL_HASH(hi) | | HBLKDISPL(p) |
|
|---|
| 18 | +------------------+----------------+------------------+------------------+
|
|---|
| 19 | \-----------------------HBLKPTR(p)-------------------/
|
|---|
| 20 | \------------hi-------------------/
|
|---|
| 21 | \______ ________/ \________ _______/ \________ _______/
|
|---|
| 22 | V V V
|
|---|
| 23 | | | |
|
|---|
| 24 | GC_top_index[] | | |
|
|---|
| 25 | --- +--------------+ | | |
|
|---|
| 26 | ^ | | | | |
|
|---|
| 27 | | | | | | |
|
|---|
| 28 | TOP +--------------+<--+ | |
|
|---|
| 29 | _SZ +-<| [] | * | |
|
|---|
| 30 | (items)| +--------------+ if 0 < bi< HBLKSIZE | |
|
|---|
| 31 | | | | | then large object | |
|
|---|
| 32 | | | | | starts at the bi'th | |
|
|---|
| 33 | v | | | HBLK before p. | i |
|
|---|
| 34 | --- | +--------------+ | (word- |
|
|---|
| 35 | v | aligned) |
|
|---|
| 36 | bi= |GET_BI(p){->hash_link}->key==hi | |
|
|---|
| 37 | v | |
|
|---|
| 38 | | (bottom_index) \ scratch_alloc'd | |
|
|---|
| 39 | | ( struct bi ) / by get_index() | |
|
|---|
| 40 | --- +->+--------------+ | |
|
|---|
| 41 | ^ | | | |
|
|---|
| 42 | ^ | | | |
|
|---|
| 43 | BOTTOM | | ha=GET_HDR_ADDR(p) | |
|
|---|
| 44 | _SZ(items)+--------------+<----------------------+ +-------+
|
|---|
| 45 | | +--<| index[] | |
|
|---|
| 46 | | | +--------------+ GC_obj_map: v
|
|---|
| 47 | | | | | from / +-+-+-----+-+-+-+-+ ---
|
|---|
| 48 | v | | | GC_add < 0| | | | | | | | ^
|
|---|
| 49 | --- | +--------------+ _map_entry \ +-+-+-----+-+-+-+-+ |
|
|---|
| 50 | | | asc_link | +-+-+-----+-+-+-+-+ MAXOBJSZ
|
|---|
| 51 | | +--------------+ +-->| | | j | | | | | +1
|
|---|
| 52 | | | key | | +-+-+-----+-+-+-+-+ |
|
|---|
| 53 | | +--------------+ | +-+-+-----+-+-+-+-+ |
|
|---|
| 54 | | | hash_link | | | | | | | | | | v
|
|---|
| 55 | | +--------------+ | +-+-+-----+-+-+-+-+ ---
|
|---|
| 56 | | | |<--MAX_OFFSET--->|
|
|---|
| 57 | | | (bytes)
|
|---|
| 58 | HDR(p)| GC_find_header(p) | |<--MAP_ENTRIES-->|
|
|---|
| 59 | | \ from | =HBLKSIZE/WORDSZ
|
|---|
| 60 | | (hdr) (struct hblkhdr) / alloc_hdr() | (1024 on Alpha)
|
|---|
| 61 | +-->+----------------------+ | (8/16 bits each)
|
|---|
| 62 | GET_HDR(p)| word hb_sz (words) | |
|
|---|
| 63 | +----------------------+ |
|
|---|
| 64 | | struct hblk *hb_next | |
|
|---|
| 65 | +----------------------+ |
|
|---|
| 66 | |mark_proc hb_mark_proc| |
|
|---|
| 67 | +----------------------+ |
|
|---|
| 68 | | char * hb_map |>-------------+
|
|---|
| 69 | +----------------------+
|
|---|
| 70 | | ushort hb_obj_kind |
|
|---|
| 71 | +----------------------+
|
|---|
| 72 | | hb_last_reclaimed |
|
|---|
| 73 | --- +----------------------+
|
|---|
| 74 | ^ | |
|
|---|
| 75 | MARK_BITS| hb_marks[] | *if hdr is free, hb_sz + DISCARD_WORDS
|
|---|
| 76 | _SZ(words)| | is the size of a heap chunk (struct hblk)
|
|---|
| 77 | v | | of at least MININCR*HBLKSIZE bytes (below),
|
|---|
| 78 | --- +----------------------+ otherwise, size of each object in chunk.
|
|---|
| 79 |
|
|---|
| 80 | Dynamic data structures above are interleaved throughout the heap in blocks of
|
|---|
| 81 | size MININCR * HBLKSIZE bytes as done by gc_scratch_alloc which cannot be
|
|---|
| 82 | freed; free lists are used (e.g. alloc_hdr). HBLKs's below are collected.
|
|---|
| 83 |
|
|---|
| 84 | (struct hblk)
|
|---|
| 85 | --- +----------------------+ < HBLKSIZE --- --- DISCARD_
|
|---|
| 86 | ^ |garbage[DISCARD_WORDS]| aligned ^ ^ HDR_BYTES WORDS
|
|---|
| 87 | | | | | v (bytes) (words)
|
|---|
| 88 | | +-----hb_body----------+ < WORDSZ | --- ---
|
|---|
| 89 | | | | aligned | ^ ^
|
|---|
| 90 | | | Object 0 | | hb_sz |
|
|---|
| 91 | | | | i |(word- (words)|
|
|---|
| 92 | | | | (bytes)|aligned) v |
|
|---|
| 93 | | + - - - - - - - - - - -+ --- | --- |
|
|---|
| 94 | | | | ^ | ^ |
|
|---|
| 95 | n * | | j (words) | hb_sz BODY_SZ
|
|---|
| 96 | HBLKSIZE | Object 1 | v v | (words)
|
|---|
| 97 | (bytes) | |--------------- v MAX_OFFSET
|
|---|
| 98 | | + - - - - - - - - - - -+ --- (bytes)
|
|---|
| 99 | | | | !All_INTERIOR_PTRS ^ |
|
|---|
| 100 | | | | sets j only for hb_sz |
|
|---|
| 101 | | | Object N | valid object offsets. | |
|
|---|
| 102 | v | | All objects WORDSZ v v
|
|---|
| 103 | --- +----------------------+ aligned. --- ---
|
|---|
| 104 |
|
|---|
| 105 | DISCARD_WORDS is normally zero. Indeed the collector has not been tested
|
|---|
| 106 | with another value in ages.
|
|---|
