![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to barrett_diagram CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM_contrib2 / asir2000 / gc / doc|
Return to barrett_diagram CVS log | Up to [local] / OpenXM_contrib2 / asir2000 / gc / doc |
1.1 ! noro 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.