share/doc/papers/malloc/malloc.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/malloc.ms,v 1.7 1999/08/28 00:18:10 peter Exp $
  10 .\" $DragonFly: src/share/doc/papers/malloc/malloc.ms,v 1.2 2003/06/17 04:36:56 dillon Exp $
  11 .\"
  12 .ds RH Malloc and free
  13 .NH
  14 Malloc and free
  15 .PP
  16 The job of malloc(3) is to turn the rather simple
  17 brk(2) facility into a service programs can
  18 actually use without getting hurt.
  19 .PP
  20 The archetypical malloc(3) implementation keeps track of the memory between
  21 the end of the bss section, as defined by the
  22 .B _end
  23 symbol, and the current brk(2) point using a linked list of chunks of memory.
  24 Each item on the list has a status as either free or used, a pointer
  25 to the next entry and in most cases to the previous as well, to speed
  26 up inserts and deletes in the list.
  27 .PP
  28 When a malloc(3) request comes in, the list is traversed from the
  29 front and if a free chunk big enough to hold the request is found,
  30 it is returned, if the free chunk is bigger than the size requested,
  31 a new free chunk is made from the excess and put back on the list.
  32 .PP
  33 When a chunk is
  34 .B free(3) 'ed,
  35 the chunk is found in the list, its status
  36 is changed to free and if one or both of the surrounding chunks
  37 are free, they are collapsed to one.
  38 .PP
  39 A third kind of request,
  40 .B realloc(3) ,
  41 will resize
  42 a chunk, trying to avoid copying the contents if possible.
  43 It is seldom used, and has only had a significant impact on performance
  44 in a few special situations.
  45 The typical pattern of use is to malloc(3) a chunk of the maximum size
  46 needed, read in the data and adjust the size of the chunk to match the
  47 size of the data read using realloc(3).
  48 .PP
  49 For reasons of efficiency, the original implementation of malloc(3)
  50 put the small structure used to contain the next and previous pointers
  51 plus the state of the chunk right before the chunk itself.
  52 .PP
  53 As a matter of fact, the canonical malloc(3) implementation can be
  54 studied in the ``Old testament'', chapter 8 verse 7 [Kernighan & Ritchie]
  55 .PP
  56 Various optimisations can be applied to the above basic algorithm:
  57 .IP
  58 If in freeing a chunk, we end up with the last chunk on the list being
  59 free, we can return that to the kernel by calling brk(2) with the first
  60 address of that chunk and then make the previous chunk the last on the
  61 chain by terminating its ``next'' pointer.
  62 .IP
  63 A best-fit algorithm can be used instead of first-fit at an expense
  64 of memory, because statistically fewer chances to brk(2) backwards will
  65 present themselves.
  66 .IP
  67 Splitting the list in two, one for used and one for free chunks, to
  68 speed the searching.
  69 .IP
  70 Putting free chunks on one of several free lists, depending on their size,
  71 to speed allocation.
  72 .IP
  73 \&...