boehm-gc/doc/barrett_diagram

   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.