Mercurial > emacs
view 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 |
line wrap: on
line source
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.