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