Mercurial > emacs
comparison gc/doc/barrett_diagram @ 51488:5de98dce4bd1
*** empty log message ***
author | Dave Love <fx@gnu.org> |
---|---|
date | Thu, 05 Jun 2003 17:49:22 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
51487:01d68b199093 | 51488:5de98dce4bd1 |
---|---|
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. |