|
This is an ASCII diagram of the data structure used to check pointer |
|
validity. It was provided by Dave Barrett <barrett@asgard.cs.colorado.edu>, |
|
and should be of use to others attempting to understand the code. |
|
The data structure in GC4.X is essentially the same. -HB |
|
|
|
|
|
|
|
|
|
Data Structure used by GC_base in gc3.7: |
|
21-Apr-94 |
|
|
|
|
|
|
|
|
|
63 LOG_TOP_SZ[11] LOG_BOTTOM_SZ[10] LOG_HBLKSIZE[13] |
|
+------------------+----------------+------------------+------------------+ |
|
p:| | TL_HASH(hi) | | HBLKDISPL(p) | |
|
+------------------+----------------+------------------+------------------+ |
|
\-----------------------HBLKPTR(p)-------------------/ |
|
\------------hi-------------------/ |
|
\______ ________/ \________ _______/ \________ _______/ |
|
V V V |
|
| | | |
|
GC_top_index[] | | | |
|
--- +--------------+ | | | |
|
^ | | | | | |
|
| | | | | | |
|
TOP +--------------+<--+ | | |
|
_SZ +-<| [] | * | | |
|
(items)| +--------------+ if 0 < bi< HBLKSIZE | | |
|
| | | | then large object | | |
|
| | | | starts at the bi'th | | |
|
v | | | HBLK before p. | i | |
|
--- | +--------------+ | (word- | |
|
v | aligned) | |
|
bi= |GET_BI(p){->hash_link}->key==hi | | |
|
v | | |
|
| (bottom_index) \ scratch_alloc'd | | |
|
| ( struct bi ) / by get_index() | | |
|
--- +->+--------------+ | | |
|
^ | | | | |
|
^ | | | | |
|
BOTTOM | | ha=GET_HDR_ADDR(p) | | |
|
_SZ(items)+--------------+<----------------------+ +-------+ |
|
| +--<| index[] | | |
|
| | +--------------+ GC_obj_map: v |
|
| | | | from / +-+-+-----+-+-+-+-+ --- |
|
v | | | GC_add < 0| | | | | | | | ^ |
|
--- | +--------------+ _map_entry \ +-+-+-----+-+-+-+-+ | |
|
| | asc_link | +-+-+-----+-+-+-+-+ MAXOBJSZ |
|
| +--------------+ +-->| | | j | | | | | +1 |
|
| | key | | +-+-+-----+-+-+-+-+ | |
|
| +--------------+ | +-+-+-----+-+-+-+-+ | |
|
| | hash_link | | | | | | | | | | v |
|
| +--------------+ | +-+-+-----+-+-+-+-+ --- |
|
| | |<--MAX_OFFSET--->| |
|
| | (bytes) |
|
HDR(p)| GC_find_header(p) | |<--MAP_ENTRIES-->| |
|
| \ from | =HBLKSIZE/WORDSZ |
|
| (hdr) (struct hblkhdr) / alloc_hdr() | (1024 on Alpha) |
|
+-->+----------------------+ | (8/16 bits each) |
|
GET_HDR(p)| word hb_sz (words) | | |
|
+----------------------+ | |
|
| struct hblk *hb_next | | |
|
+----------------------+ | |
|
|mark_proc hb_mark_proc| | |
|
+----------------------+ | |
|
| char * hb_map |>-------------+ |
|
+----------------------+ |
|
| ushort hb_obj_kind | |
|
+----------------------+ |
|
| hb_last_reclaimed | |
|
--- +----------------------+ |
|
^ | | |
|
MARK_BITS| hb_marks[] | *if hdr is free, hb_sz + DISCARD_WORDS |
|
_SZ(words)| | is the size of a heap chunk (struct hblk) |
|
v | | of at least MININCR*HBLKSIZE bytes (below), |
|
--- +----------------------+ otherwise, size of each object in chunk. |
|
|
|
Dynamic data structures above are interleaved throughout the heap in blocks of |
|
size MININCR * HBLKSIZE bytes as done by gc_scratch_alloc which cannot be |
|
freed; free lists are used (e.g. alloc_hdr). HBLKs's below are collected. |
|
|
|
(struct hblk) |
|
--- +----------------------+ < HBLKSIZE --- --- DISCARD_ |
|
^ |garbage[DISCARD_WORDS]| aligned ^ ^ HDR_BYTES WORDS |
|
| | | | v (bytes) (words) |
|
| +-----hb_body----------+ < WORDSZ | --- --- |
|
| | | aligned | ^ ^ |
|
| | Object 0 | | hb_sz | |
|
| | | i |(word- (words)| |
|
| | | (bytes)|aligned) v | |
|
| + - - - - - - - - - - -+ --- | --- | |
|
| | | ^ | ^ | |
|
n * | | j (words) | hb_sz BODY_SZ |
|
HBLKSIZE | Object 1 | v v | (words) |
|
(bytes) | |--------------- v MAX_OFFSET |
|
| + - - - - - - - - - - -+ --- (bytes) |
|
| | | !All_INTERIOR_PTRS ^ | |
|
| | | sets j only for hb_sz | |
|
| | Object N | valid object offsets. | | |
|
v | | All objects WORDSZ v v |
|
--- +----------------------+ aligned. --- --- |
|
|
|
DISCARD_WORDS is normally zero. Indeed the collector has not been tested |
|
with another value in ages. |
|
|