share/doc/papers/malloc/implementation.ms

   1 .\"
   2 .\" ----------------------------------------------------------------------------
   3 .\" "THE BEER-WARE LICENSE" (Revision 42):
   4 .\" <phk@login.dknet.dk> wrote this file.  As long as you retain this notice you
   5 .\" can do whatever you want with this stuff. If we meet some day, and you think
   6 .\" this stuff is worth it, you can buy me a beer in return.   Poul-Henning Kamp
   7 .\" ----------------------------------------------------------------------------
   8 .\"
   9 .\" $FreeBSD: src/share/doc/papers/malloc/implementation.ms,v 1.8 1999/08/28 00:18:09 peter Exp $
  10 .\" $DragonFly: src/share/doc/papers/malloc/implementation.ms,v 1.2 2003/06/17 04:36:56 dillon Exp $
  11 .\"
  12 .ds RH Implementation
  13 .NH
  14 Implementation
  15 .PP
  16 A new malloc(3) implementation was written to meet the goals,
  17 and to the extent possible to address the shortcomings listed previously.
  18 .PP
  19 The source is 1218 lines of C code, and can be found in FreeBSD 2.2
  20 (and probably later versions as well) as src/lib/libc/stdlib/malloc.c.
  21 .PP
  22 The main data structure is the
  23 .I page-directory
  24 which contains a
  25 .B void*
  26 for each page we have control over.
  27 The value can be one of:
  28 .IP
  29 .B MALLOC_NOT_MINE
  30 Another part of the code may call brk(2) to get a piece of the cake.
  31 Consequently, we cannot rely on the memory we get from the kernel
  32 being one consecutive piece of memory, and therefore we need a way to
  33 mark such pages as "untouchable".
  34 .IP
  35 .B MALLOC_FREE
  36 This is a free page.
  37 .IP
  38 .B MALLOC_FIRST
  39 This is the first page in a (multi-)page allocation.
  40 .IP
  41 .B MALLOC_FOLLOW
  42 This is a subsequent page in a multi-page allocation.
  43 .IP
  44 .B
  45 struct pginfo*
  46 .R
  47 A pointer to a structure describing a partitioned page.
  48 .PP
  49 In addition, there exists a linked list of small data structures that
  50 describe the free space as runs of free pages.
  51 .PP
  52 Notice that these structures are not part of the free pages themselves,
  53 but rather allocated with malloc so that the free pages themselves
  54 are never referenced while they are free.
  55 .PP
  56 When a request for storage comes in, it will be treated as a ``page''
  57 allocation if it is bigger than half a page.
  58 The free list will be searched and the first run of free pages that
  59 can satisfy the request is used.  The first page gets set to
  60 .B MALLOC_FIRST
  61 status.  If more than that one page is needed, the rest of them get
  62 .B MALLOC_FOLLOW
  63 status in the page-directory.
  64 .PP
  65 If there were no pages on the free list, brk(2) will be called, and
  66 the pages will get added to the page-directory with status
  67 .B MALLOC_FREE
  68 and the search restarts.
  69 .PP
  70 Freeing a number of pages is done by changing their state in the
  71 page directory to MALLOC_FREE, and then traversing the free-pages list to
  72 find the right place for this run of pages, possibly collapsing
  73 with the two neighbouring runs into one run and, if possible,
  74 releasing some memory back to the kernel by calling brk(2).
  75 .PP
  76 If the request is less than or equal to half of a page, its size will be
  77 rounded up to the nearest power of two before being processed
  78 and if the request is less than some minimum size, it is rounded up to
  79 that size.
  80 .PP
  81 These sub-page allocations are served from pages which are split up
  82 into some number of equal size chunks.
  83 For each of these pages a
  84 .B
  85 struct pginfo
  86 .R
  87 describes the size of the chunks on this page, how many there are,
  88 how many are free and so on.
  89 The description consist of a bitmap of used chunks, and various counters
  90 and numbers used to keep track of the stuff in the page.
  91 .PP
  92 For each size of sub-page allocation, the pginfo structures for the
  93 pages that have free chunks in them form a list.
  94 The heads of these lists are stored in predetermined slots at
  95 the beginning of the page directory to make access fast.
  96 .PP
  97 To allocate a chunk of some size, the head of the list for the
  98 corresponding size is examined, and a free chunk found.  The number
  99 of free chunks on that page is decreased by one and, if zero, the
 100 pginfo structure is unlinked from the list.
 101 .PP
 102 To free a chunk, the page is derived from the pointer, the page table
 103 for that page contains a pointer to the pginfo structure, where the
 104 free bit is set for the chunk, the number of free chunks increased by
 105 one, and if equal to one, the pginfo structure is linked into the
 106 proper place on the list for this size of chunks.
 107 If the count increases to match the number of chunks on the page, the
 108 pginfo structure is unlinked from the list and free(3)'ed and the
 109 actual page itself is free(3)'ed too.
 110 .PP
 111 To be 100% correct performance-wise these lists should be ordered
 112 according to the recent number of accesses to that page.  This
 113 information is not available and it would essentially mean a reordering
 114 of the list on every memory reference to keep it up-to-date.
 115 Instead they are ordered according to the address of the pages.
 116 Interestingly enough, in practice this comes out to almost the same
 117 thing performance wise.
 118 .PP
 119 It's not that surprising after all, it's the difference between
 120 following the crowd or actively directing where it can go, in both
 121 ways you can end up in the middle of it all.
 122 .PP
 123 The side effect of this compromise is that it also uses less storage,
 124 and the list never has to be reordered, all the ordering happens when
 125 pages are added or deleted.
 126 .PP
 127 It is an interesting twist to the implementation that the
 128 .B
 129 struct pginfo
 130 .R
 131 Is allocated with malloc.
 132 That is, "as with malloc" to be painfully correct.
 133 The code knows the special case where the first (couple) of allocations on
 134 the page is actually the pginfo structure and deals with it accordingly.
 135 This avoids some silly "chicken and egg" issues.
 136 .ds RH Bells and whistles.
 137 .NH
 138 Bells and whistles.
 139 .PP
 140 brk(2) is actually not a very fast system call when you ask for storage.
 141 This is mainly because of the need by the kernel to zero the pages before
 142 handing them over, so therefore this implementation does not release
 143 heap pages until there is a large chunk to release back to the kernel.
 144 Chances are pretty good that we will need it again pretty soon anyway.
 145 Since these pages are not accessed at all, they will soon be paged out
 146 and don't affect anything but swap-space usage.
 147 .PP
 148 The page directory is actually kept in a mmap(2)'ed piece of
 149 anonymous memory.  This avoids some rather silly cases that
 150 would otherwise have to be handled when the page directory
 151 has to be extended.
 152 .PP
 153 One particularly nice feature is that all pointers passed to free(3)
 154 and realloc(3) can be checked conclusively for validity:
 155 First the pointer is masked to find the page.  The page directory
 156 is then examined, it must contain either MALLOC_FIRST, in which
 157 case the pointer must point exactly at the page, or it can contain
 158 a struct pginfo*, in which case the pointer must point to one of
 159 the chunks described by that structure.
 160 Warnings will be printed on
 161 .B stderr
 162 and nothing will be done with
 163 the pointer if it is found to be invalid.
 164 .PP
 165 An environment variable
 166 .B MALLOC_OPTIONS
 167 allows the user some control over the behaviour of malloc.
 168 Some of the more interesting options are:
 169 .IP
 170 .B Abort
 171 If malloc fails to allocate storage, core-dump the process with
 172 a message rather than expect it handle this correctly.
 173 It's amazing how few programs actually handle this condition correctly,
 174 and consequently the havoc they can create is the more creative or
 175 destructive.
 176 .IP
 177 .B Dump
 178 Writes malloc statistics to a file called ``malloc.out'' prior
 179 to process termination.
 180 .IP
 181 .B Hint
 182 Pass a hint to the kernel about pages we no longer need through the
 183 madvise(2) system call.  This can help performance on machines that
 184 page heavily by eliminating unnecessary page-ins and page-outs of
 185 unused data.
 186 .IP
 187 .B Realloc
 188 Always do a free and malloc when realloc(3) is called.
 189 For programs doing garbage collection using realloc(3), this make the
 190 heap collapse faster since malloc will reallocate from the
 191 lowest available address.
 192 The default
 193 is to leave things alone if the size of the allocation is still in
 194 the same size-class.
 195 .IP
 196 .B Junk
 197 will explicitly fill the allocated area with a particular value
 198 to try to detect if programs rely on it being zero.
 199 .IP
 200 .B Zero
 201 will explicitly zero out the allocated chunk of memory, while any
 202 space after the allocation in the chunk will be filled with the
 203 junk value to try to catch out of the chunk references.
 204 .ds RH The road not taken.
 205 .NH
 206 The road not yet taken.
 207 .PP
 208 A couple of avenues were explored that could be interesting in some
 209 set of circumstances.
 210 .PP
 211 Using mmap(2) instead of brk(2) was actually slower, since brk(2)
 212 knows a lot of the things that mmap has to find out first.
 213 .PP
 214 In general there is little room for further improvement of the
 215 time-overhead of the malloc, further improvements will have to
 216 be in the area of improving paging behaviour.
 217 .PP
 218 It is still under consideration to add a feature such that
 219 if realloc is called with two zero arguments, the internal
 220 allocations will be reallocated to perform a garbage collect.
 221 This could be used in certain types of programs to collapse
 222 the memory use, but so far it doesn't seem to be worth the effort.
 223 .PP
 224 Malloc/Free can be a significant point of contention in multi-threaded
 225 programs.  Low-grain locking of the data-structures inside the
 226 implementation should be implemented to avoid excessive spin-waiting.