]>
Commit | Line | Data |
---|---|---|
f54d4287 BM |
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. |