source/blog/posts/2009/04/understanding-the-current-gc-(part-iii).rst

   1 Title: Understanding the current GC, part III
   2 Tags: en, d, dgc, understanding the current gc, druntime, gc, mark-sweep, allocation
   3
   4 In the `previous post`_ we focused on the ``Gcx`` object, the core of the GC
   5 in druntime (and Phobos and Tango, they are all are based on the same
   6 implementation).  In this post we will focus on **allocation**, which a little
   7 more complex than it should be in my opinion.
   8
   9 It was not an easy task to follow how allocation works. A ``GC.malloc()`` call
  10 spawns into this function calls::
  11
  12     GC.malloc(size, bits)
  13      |
  14      '---> GC.mallocNoSync(size, bits)
  15             |
  16             |---> Gcx.allocPage(bin_size)
  17             |      |
  18             |      '---> Pool.allocPages(n_pages)
  19             |             |
  20             |             '---> Pool.extendPages(n_pages)
  21             |                    |
  22             |                    '---> os_mem_commit(addr, offset, size)
  23             |
  24             |---> Gcx.fullcollectshell()
  25             |
  26             |---> Gcx.newPool(n_pages)
  27             |      |
  28             |      '---> Pool.initialize(n_pages)
  29             |             |
  30             |             |---> os_mem_map(mem_size)
  31             |             |
  32             |             '---> GCBits.alloc(bits_size)
  33             |
  34             '---> Gcx.bigAlloc(size)
  35                    |
  36                    |---> Pool.allocPages(n_pages)
  37                    |      '---> (...)
  38                    |
  39                    |---> Gcx.fullcollectshell()
  40                    |
  41                    |---> Gcx.minimize()
  42                    |      |
  43                    |      '---> Pool.Dtor()
  44                    |             |
  45                    |             |---> os_mem_decommit(addr, offset, size)
  46                    |             |
  47                    |             |---> os_mem_map(addr, size)
  48                    |             |
  49                    |             '---> GCBits.Dtor()
  50                    |
  51                    '---> Gcx.newPool(n_pages)
  52                           '---> (...)
  53
  54 Doesn't look so simple, ugh?
  55
  56 The map/commit differentiation of Windows doesn't exactly help simplicity. Note
  57 that ``Pool.initialize()`` maps the memory (reserve the address space) while
  58 ``Pool.allocPages()`` (through ``Pool.extendPages()``) commit the new memory
  59 (ask the OS to actually reserve the virtual memory). I don't know how good is
  60 this for Windows (or put in another way, how bad could it be for Windows if all
  61 mapped memory gets immediately committed), but it adds a new layer of
  62 complexity (that's not even needed in Posix OSs). The whole branch starting at
  63 ``Gcx.allocPage(bin_size)`` would be gone if this distinction it's not made.
  64 Besides this, it worsen Posix OSs performance, because there are some
  65 non-trivial lookups to handle this non-existing non-committed pages, even when
  66 the ``os_mem_commit()`` and ``os_mem_decommit()`` functions are NOP and can be
  67 optimized out, the lookups are there.
  68
  69 .. admonition:: Mental Note
  70
  71     See if getting rid of the ``commit()``/``decommit()`` stuff improves
  72     Linux performance.
  73
  74 But well, let's forget about this issue for now and live with it. Here is
  75 a summary of what all this functions do.
  76
  77 .. note::
  78
  79     I recommend to give another read to the (updated) `previous posts of
  80     this series`_, specially if you are not familiar with the ``Pool``
  81     concept and implementation.
  82
  83 ``GC.malloc(size, bits)``
  84     This is just a wrapper for multi-threaded code, it takes the ``GCLock`` if
  85     necessary and calls ``GC.mallocNoSync(size, bits)``.
  86
  87 ``GC.mallocNoSync(size, bits)``
  88     This function has 2 different algorithms for small objects (less than
  89     a page of 4KiB) and another for big objects.
  90
  91     It does some common work for both cases, like logging and adding a sentinel
  92     for debugging purposes (if those feature are enabled), finding the bin size
  93     (``bin_size``) that better fits ``size`` (and cache the result as an
  94     optimization for consecutive calls to malloc with the same size) and
  95     setting the ``bits`` (``NO_SCAN``, ``NO_MOVE``, ``FINALIZE``) to the
  96     allocated bin.
  97
  98     Small objects (``bin_size < B_PAGE``)
  99         Looks at the free list (``Gcx.bucket``) trying to find a page with the
 100         minimum bin size that's equals or bigger than ``size``.  If it can't
 101         succeed, it calls ``Gcx.allocPage(bin_size)`` to find room in
 102         uncommitted pages.  If there still no room for the requested amount of
 103         memory, it triggers a collection (``Gcx.fullcollectshell()``). If there
 104         is still no luck, ``Gcx.newPage(1)`` is called to ask the OS for more
 105         memory.  Then it calls again ``Gcx.allocPage(bin_size)`` (remember the
 106         new memory is just mmap'ped but not commit'ed) and if there is no room
 107         in the free list still, an out of memory error is issued.
 108
 109     Big objects (``B_PAGE`` and ``B_PAGEPLUS``)
 110         It simply calls ``Gcx.bigAlloc(size)`` and issue an out of memory error
 111         if that call fails to get the requested memory.
 112
 113 ``Gcx.allocPage(bin_size)``
 114     This function linearly search the ``pooltable`` for a ``Pool`` with an
 115     allocable page (i.e.  a page already mapped by not yet committed). This is
 116     done through a call to ``Pool.allocPages(1)``. If a page is found, its bin
 117     size is set to ``bin_size`` via the ``Pool``'s ``pagetable``, and all the
 118     bins of that page are linked to the free list (``Gcx.bucket``).
 119
 120 ``Pool.allocPages(n_pages)``
 121     Search for ``n_pages`` consecutive free pages (``B_FREE``) in the committed
 122     pages (pages in the ``pagetable`` with index up to ``ncommited``). If
 123     they're not found, ``Pool.extendPages(n_pages)`` is called to commit some
 124     more mapped pages to fulfill the request.
 125
 126 ``Pool.extendPages(n_pages)``
 127     Commit ``n_pages`` already mapped pages (calling ``os_mem_commit()``),
 128     setting them as free (``B_FREE``) and updating the ``ncommited`` attribute.
 129     If there are not that many uncommitted pages, it returns an error.
 130
 131 ``Gcx.newPool(n_pages)``
 132     This function adds a new ``Pool`` to the ``pooltable``. It first adjusts
 133     the ``n_pages`` variable using various rules (for example, it duplicates
 134     the current allocated memory until 8MiB are allocated and then allocates
 135     8MiB pools always, unless more memory is requested in the first place, of
 136     course). Then a new ``Pool`` is created with the adjusted ``n_pages`` value
 137     and it's initialized calling to ``Pool.initialize(n_pages)``, the
 138     ``pooltable`` is resized to fit the new number of pools (``npools``) and
 139     sorted using ``Pool.opCmp()`` (which uses the ``baseAddr`` to compare).
 140     Finally the ``minAddr`` and ``maxAddr`` attributes are updated.
 141
 142 ``Pool.initialize(n_pages)``
 143     Initializes all the ``Pool`` attributes, mapping the requested number of
 144     pages (``n_pages``) using ``os_mem_map()``. All the bit sets (``mark``,
 145     ``scan``, ``freebits``, ``noscan``) are allocated (using
 146     ``GCBits.alloc()``) to ``n_pages * PAGESIZE / 16`` bits and the
 147     ``pagetable``  too, setting all bins to ``B_UNCOMMITTED`` and
 148     ``ncommitted`` to 0.
 149
 150 ``Gcx.bigAlloc(size)``
 151     This is the weirdest function by far. There are very strange things, but
 152     I'll try to explain what I understand from it (what I think it's trying to
 153     do).
 154
 155     It first make a simple lookup in the ``pooltable`` for ``n_pages``
 156     consecutive pages in any existing ``Pool`` (calling
 157     ``Pool.allocPages(n_pages)`` as in ``Gcx.allocPage()``). If this fails, it
 158     runs a ``fullcollectshell()`` (if not ``disabled``) then calls to
 159     ``minimize()`` (to prevent bloat) and then create a new pool (calling
 160     ``newPool()`` followed by ``Pool.allocPages()``). If all that fails, it
 161     returns an error. If something succeed, the bin size for the first page is
 162     set to ``B_PAGE`` and the remaining pages are set to ``B_PAGEPLUS`` (if
 163     any). If there is any unused memory at the end, it's initialized to
 164     0 (to prevent false positives when scanning I guess).
 165
 166     The weird thing about this, is that a lot of lookups into the ``pooltable``
 167     are done in certain condition, but I think they are not needed because
 168     there are no changes that can make new room.
 169
 170     I don't know if this is legacy code that never got updated and have a lot
 171     of useless lookups or if I'm getting something wrong.  **Help is welcome!**
 172
 173 There is not much to say about ``os_mem_xxx()``, ``Gcx.minimize()`` and
 174 ``Gcx.fullcollectshell()`` functions, they were briefly described in the
 175 `previous posts of this series`_. ``Pool.Dtor()`` just undo what was done in
 176 ``Pool.initialize()``.
 177
 178 A final word about the free list (``Gcx.bucket``). It's just a simple linked
 179 list. It uses the first ``size_t`` bytes of the free bin to point to the next
 180 free bin (there's always room for a pointer in a bin because their minimum size
 181 is 16 bytes). A simple structure is used to *easy* this::
 182
 183     struct List {
 184         List *next;
 185     }
 186
 187 Then, the memory cell is casted to this structure to use the next
 188 pointer, like this::
 189
 190     p = gcx.bucket[bin]
 191     gcx.bucket[bin] = (cast(List*) p).next
 192
 193 I really have my doubts if this is even a little less cryptic than::
 194
 195     p = gcx.bucket[bin]
 196     gcx.bucket[bin] = *(cast(void**) p)
 197
 198 But what the hell, this is no really important =)
 199
 200
 201 .. _`previous post`: http://proj.llucax.com.ar/blog/dgc/blog/post/526122be
 202 .. _`previous posts of this series`: http://proj.llucax.com.ar/blog/dgc/blog/tag/understanding%20the%20current%20gc
 203
 204 .. vim: set et sw=4 sts=4 :