source/blog/posts/2009/04/understanding-the-current-gc-the-end.rst

   1 Title: Understanding the current GC, the end
   2 Tags: en, d, dgc, understanding the current gc, druntime, gc, mark-sweep, mark, sweep
   3
   4 In this post I will take a closer look at the ``Gcx.mark()`` and
   5 ``Gcx.fullcollect()`` functions.
   6
   7 This is a simplified version of the **mark** algorithm::
   8
   9     mark(from, to)
  10         changes = 0
  11         while from < to
  12             pool = findPool(from)
  13             offset = from - pool.baseAddr
  14             page_index = offset / PAGESIZE
  15             bin_size = pool.pagetable[page_index]
  16             bit_index = find_bit_index(bin_size, pool, offset)
  17             if not pool.mark.test(bit_index)
  18                 pool.mark.set(bit_index)
  19                 if not pool.noscan.test(bit_index)
  20                     pool.scan.set(bit_index)
  21                     changes = true
  22             from++
  23             anychanges |= changes // anychanges is global
  24
  25 In the original version, there are some optimizations_ and the
  26 ``find_bit_index()`` function doesn't exist (it does some bit masking to find
  27 the right bit index for the bit set). But everything else is pretty much the
  28 same.
  29
  30 So far, is evident that the algorithm don't mark the whole heap in one step,
  31 because it doesn't follow pointers. It just marks a consecutive chunk of
  32 memory, assuming that pointers can be at any place in that memory, as long as
  33 they are aligned (from increments in word-sized steps).
  34
  35 ``fullcollect()`` is the one in charge of following pointers, and marking
  36 chunks of memory. It does it in an iterative way (that's why ``mark()`` informs
  37 about ``anychanges`` (when new pointer should be followed to mark them, or,
  38 speaking in the `tri-colour abstraction`_, when grey cells are found).
  39
  40 ``fullcollect()`` is huge, so I'll split it up in smaller pieces for the sake
  41 of clarity. Let's see what are the basic blocks (see the `second part of this
  42 series`_)::
  43
  44     fullcollect()
  45         thread_suspendAll()
  46         clear_mark_bits()
  47         mark_free_list()
  48         rt_scanStaticData(mark)
  49         thread_scanAll(mark, stackTop)
  50         mark_root_set()
  51         mark_heap()
  52         thread_resumeAll()
  53         sweep()
  54
  55 Generaly speaking, all the functions that have some *CamelCasing* are real
  56 functions and the ones that are *all_lowercase* and made up by me.
  57
  58 Let's see each function.
  59
  60 ``thread_suspendAll()``
  61     This is part of the threads runtime (found in
  62     ``src/common/core/thread.d``). A simple peak at it shows it uses
  63     ``SIGUSR1`` to stop the thread. When the signal is caught it pushes all the
  64     registers into the stack to be sure any pointers there are scanned in the
  65     future. The threads waits for ``SIGUSR2`` to resume.
  66
  67 ``clear_mark_bits()``
  68     ::
  69
  70         foreach pool in pooltable
  71             pool.mark.zero()
  72             pool.scan.zero()
  73             pool.freebits.zero()
  74
  75 ``mark_free_list()``
  76     ::
  77
  78         foreach n in B_16 .. B_PAGE
  79             foreach node in bucket
  80                 pool = findPool(node)
  81                 pool.freebits.set(find_bit_index(pool, node))
  82                 pool.mark.set(find_bit_index(pool, node))
  83
  84 ``rt_scanStaticData(mark)``
  85     This function, as the name suggests, uses the provided mark function
  86     callback to scan the program's static data.
  87
  88 ``thread_scanAll(mark, stackTop)``
  89     This is another threads runtime function, used to mark the suspended
  90     threads stacks. I does some calculation about the stack bottom and top, and
  91     calls ``mark(bottom, top)``, so at this point we have marked all reachable
  92     memory from the stack(s).
  93
  94 ``mark_root_set()``
  95     ::
  96
  97         mark(roots, roots + nroots)
  98         foreach range in ranges
  99             mark(range.pbot, range.ptop)
 100
 101 ``mark_heap()``
 102     This is where most of the marking work is done. The code is **really**
 103     ugly, very hard to read (mainly because of bad variable names) but what it
 104     does it's relatively simple, here is the simplified algorithm::
 105
 106         // anychanges is global and was set by the mark()ing of the
 107         // stacks and root set
 108         while anychanges
 109             anychanges = 0
 110             foreach pool in pooltable
 111                 foreach bit_pos in pool.scan
 112                     if not pool.scan.test(bit_pos)
 113                         continue
 114                     pool.scan.clear(bit_pos) // mark as already scanned
 115                     bin_size = find_bin_for_bit(pool, bit_pos)
 116                     bin_base_addr = find_base_addr_for_bit(pool, bit_pos)
 117                     if bin_size < B_PAGE // small object
 118                         bin_top_addr = bin_base_addr + bin_size
 119                     else if bin_size in [B_PAGE, B_PAGEPLUS] // big object
 120                         page_num = (bin_base_addr - pool.baseAddr) / PAGESIZE
 121                         if bin == B_PAGEPLUS // search for the base page
 122                             while pool.pagetable[page_num - 1] != B_PAGE
 123                                 page_num--
 124                         n_pages = 1
 125                         while page_num + n_pages < pool.ncommitted
 126                                 and pool.pagetable[page_num + n_pages] == B_PAGEPLUS
 127                             n_pages++
 128                         bin_top_addr = bin_base_addr + n_pages * PAGESIZE
 129                     mark(bin_base_addr, bin_top_addr)
 130
 131     The original algorithm has some optimizations for proccessing bits in
 132     clusters (skips groups of bins without the scan bit) and some kind-of
 133     bugs_ too.
 134
 135     Again, the functions in ``all_lower_case`` don't really exist, some pointer
 136     arithmetics are done in place for finding those values.
 137
 138     Note that the pools are iterated over and over again until there are no
 139     unvisited bins. I guess this is a fair price to pay for not having a mark
 140     stack (but I'm not really sure =).
 141
 142 ``thread_resumeAll()``
 143     This is, again, part of the threads runtime and resume all the paused
 144     threads by signaling a ``SIGUSR2`` to them.
 145
 146 ``sweep()``
 147     ::
 148
 149         mark_unmarked_free()
 150         rebuild_free_list()
 151
 152 ``mark_unmarked_free()``
 153     This (invented) function looks for unmarked bins and set the ``freebits``
 154     bit on them if they are small objects (bin size smaller than ``B_PAGE``) or
 155     mark the entire page as free (``B_FREE``) in case of large objects.
 156
 157     This step is in charge of executing destructors too (through
 158     ``rt_finalize()`` the runtime function).
 159
 160 ``rebuild_free_list()``
 161     This (also invented) function first clear the free list (``bucket``) and
 162     then rebuild it using the information collected in the previous step.
 163
 164     As usual, only bins with size smaller than ``B_PAGE`` are linked to the
 165     free list, except if the pages they belong to have all the bins freed, in
 166     which case the page is marked with the special ``B_FREE`` bin size. The
 167     same goes for big objects freed in the previous step.
 168
 169     I think rebuilding the whole free list is not necessary, the new free bins
 170     could be just linked to the existing free list. I guess this step exists to
 171     help reducing fragmentation, since the rebuilt free list group bins
 172     belonging to the same page together.
 173
 174
 175 .. _optimizations: http://proj.llucax.com.ar/blog/dgc/blog/post/7bdad55d
 176 .. _`tri-colour abstraction`: http://en.wikipedia.org/wiki/Garbage_collection_(computer_science)#Tri-colour_marking
 177 .. _`second part of this series`: http://proj.llucax.com.ar/blog/dgc/blog/post/526122be
 178 .. _bugs: http://www.dsource.org/projects/druntime/ticket/20
 179
 180 .. vim: set et sw=4 sts=4 :