| 1 |
721 |
jeremybenn |
This is an ASCII diagram of the data structure used to check pointer
|
| 2 |
|
|
validity. It was provided by Dave Barrett ,
|
| 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.
|
