diff options
| author | upstream source tree <ports@midipix.org> | 2015-03-15 20:14:05 -0400 |
|---|---|---|
| committer | upstream source tree <ports@midipix.org> | 2015-03-15 20:14:05 -0400 |
| commit | 554fd8c5195424bdbcabf5de30fdc183aba391bd (patch) | |
| tree | 976dc5ab7fddf506dadce60ae936f43f58787092 /boehm-gc/doc/barrett_diagram | |
| download | cbb-gcc-4.6.4-554fd8c5195424bdbcabf5de30fdc183aba391bd.tar.bz2 cbb-gcc-4.6.4-554fd8c5195424bdbcabf5de30fdc183aba391bd.tar.xz | |
obtained gcc-4.6.4.tar.bz2 from upstream website;upstream
verified gcc-4.6.4.tar.bz2.sig;
imported gcc-4.6.4 source tree from verified upstream tarball.
downloading a git-generated archive based on the 'upstream' tag
should provide you with a source tree that is binary identical
to the one extracted from the above tarball.
if you have obtained the source via the command 'git clone',
however, do note that line-endings of files in your working
directory might differ from line-endings of the respective
files in the upstream repository.
Diffstat (limited to 'boehm-gc/doc/barrett_diagram')
| -rw-r--r-- | boehm-gc/doc/barrett_diagram | 106 |
1 files changed, 106 insertions, 0 deletions
diff --git a/boehm-gc/doc/barrett_diagram b/boehm-gc/doc/barrett_diagram new file mode 100644 index 000000000..27e80dc15 --- /dev/null +++ b/boehm-gc/doc/barrett_diagram @@ -0,0 +1,106 @@ +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. |