Return to barrett_diagram CVS log

Up to [local] / OpenXM_contrib / gc

Annotation of OpenXM_contrib/gc/barrett_diagram, Revision 1.1

1.1     ! maekawa     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.