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

   1 Title: Understanding the current GC
   2 Tags: en, d, dgc, understanding the current gc, druntime, gc, mark-sweep, intro, pool, bin
   3
   4 Oh, yeah! A new year, a new air, and the same thesis =)
   5
   6 After a *little* break, I'm finally starting to analyze the current
   7 D (druntime) GC (basic) implementation in depth.
   8
   9 First I want to say I found the code really, but **really**, hard to read and
  10 follow. Things are split in several parts without apparent reason, which make
  11 it really hard to understand and it's pretty much undocumented.
  12
  13 I hope I can fully understand it in some time to be able to make a full rewrite
  14 of it (in a first pass, conserving the main design).
  15
  16 Overview
  17 ========
  18
  19 I'll start with a big picture overview, and then I'll try to describe each
  20 component with more detail.
  21
  22 The implementation in split in several files:
  23
  24 gcstats.d
  25     I didn't took a look at this one yet, but I guess it's about stats =).
  26
  27 gcbits.d
  28     A custom bitset implementation for collector bit/flags (mark, scan, etc.).
  29
  30 gcalloc.d
  31     A wrapper for memory allocation with several versions (malloc, win32, mmap
  32     and valloc). 4 functions are provided: map, unmap, commit and decommit. The
  33     (de)commit stuff if because (in Sean Kelly's words) Windows has a 2-phase
  34     allocation process. You can reserve the address space via map and unmap,
  35     but the virtual memory isn't actually created until you call commit. So
  36     decommit gets rid of the virtual memory but retains ownership of the
  37     address space.
  38
  39 gcx.d
  40     The real GC implementation, split in 2 main classes/structs: GC and Gcx. GC
  41     seems to be a thin wrapper over Gcx that only provides the allocation logic
  42     (alloc/realloc/free) and Gcx seems to be the responsible for the real GC
  43     work (and holding the memory).
  44
  45 gc.d
  46     This is just a thin wrapper over gcx.d to adapt it to the `druntime GC
  47     interface`__.
  48
  49 __ http://www.dsource.org/projects/druntime/wiki/GarbageCollectorD2_0
  50
  51
  52 The Gcx struct is where most magic happens. It holds the GC memory organized in
  53 pools. It holds the information about roots, the stack and free list, but in
  54 this post I'll focus in the memory pools:
  55
  56
  57 Pool Concept
  58 ============
  59
  60 A pool is a group of pages, each page has a bin size (``Bins``) and host
  61 a fixed number of bins (``PAGESIZE / Bins``, for example, if ``Bins == 1024``
  62 and ``PAGESIZE == 4096``, the page holds 4 bins).
  63
  64 Each bin has some bits of information:
  65
  66 mark
  67     Setted when the Bin is visited by the *mark phase*.
  68
  69 scan
  70     Setted when the Bin is has been visited by the *mark phase* (the ``mark``
  71     bit is set) but it has pointers yet to be scanned.
  72
  73 free
  74     Setted when the Bin is free (linked to a free list).
  75
  76 final
  77     The object stored in this bin has a destructor that must be called when
  78     freed.
  79
  80 noscan
  81     This bin should be not scanned by the collector (it has no pointers).
  82
  83 ::
  84
  85     +----------------------------------------+-----+-----------------+
  86     | Page 0 (bin size: Bins)                | ... | Page (npages-1) |
  87     |                                        |     |                 |
  88     | +--------+-----+---------------------+ |     |                 |
  89     | | Bin 0  | ... | Bin (PAGESIZE/Bins) | |     |                 |
  90     | +--------+-----+---------------------+ |     |                 |
  91     | | mark   | ... |                     | |     |                 |
  92     | | scan   | ... |                     | |     |       ...       |
  93     | | free   | ... |         ...         | |     |                 |
  94     | | final  | ... |                     | |     |                 |
  95     | | noscan | ... |                     | |     |                 |
  96     | +--------+-----+---------------------+ |     |                 |
  97     +----------------------------------------+-----+-----------------+
  98
  99
 100 Pool Implementation
 101 ===================
 102
 103 A single chunk of memory is allocated for the whole pool, the ``baseAddr``
 104 points to the start of the chunk, the ``topAddr``, to the end. A ``pagetable``
 105 holds the bin size (``Bins``) of each page ::
 106
 107     .          ,-- baseAddr                                   topAddr --,
 108                |                   ncommitted = i                       |
 109                |                                                        |
 110                |--- committed pages ---,------ uncommitted pages -------|
 111                V                       |                                V
 112                +--------+--------+-----+--------+-----+-----------------+
 113         memory | Page 0 | Page 1 | ... | Page i | ... | Page (npages-1) |
 114                +--------+--------+-----+--------+-----+-----------------+
 115                    /\       /\      /\     /\      /\          /\
 116                    ||       ||      ||     ||      ||          ||
 117                +--------+--------+-----+--------+-----+-----------------+
 118      pagetable | Bins 0 | Bins 1 | ... | Bins i | ... | Bins (npages-1) |
 119     (bin size) +--------+--------+-----+--------+-----+-----------------+
 120
 121 The bin size can be one of:
 122
 123 ``B_XXX``
 124     The ``XXX`` is a power of 2 from 16 to 4096. The special name ``B_PAGE`` is
 125     used for the size 4096.
 126
 127 ``B_PAGEPLUS``
 128     The whole page is a continuation of a large object (the first page of
 129     a large object has size ``B_PAGE``).
 130
 131 ``B_FREE``
 132     The page is completely free.
 133
 134 ``B_UNCOMMITED``
 135     The page is not committed yet.
 136
 137 ``B_MAX``
 138     Not really a value, used for iteration or allocation. Pages can't have this
 139     value.
 140
 141 The information bits are stored in a custom bit set (``GCBits``). ``npages
 142 * PAGESIZE / 16`` bits are allocated (since the smallest bin is 16 bytes long)
 143 and each bit is *addressed* using this formula::
 144
 145     bit(pointer) = (pointer - baseAddr) / 16
 146
 147 This means that a bit is reserved each 16 bytes. For large bin sizes, a lot of
 148 bits are wasted.
 149
 150 The minimum pool size is 256 pages. With 4096 bytes pages, that is 1 MiB.
 151
 152 The ``GCBits`` implementation deserves another post, it's a little complex and
 153 I still don't understand why.
 154
 155
 156 .. vim: set et sw=4 sts=4 :