devel/memory.text

   1 The following is gathered from a shortish discussion on the
   2 guile-devel mailing list.  I plan to implement this in the next
   3 days. -mvo
   4
   5 Improving memory handling in Guile
   6 ----------------------------------
   7
   8 I think we have a problem with the `mallocated' GC trigger.  It is not
   9 maintained reliably and I'm afraid we need to have everybody review
  10 their code to get it right.
  11
  12 I think the current interface with scm_must_malloc, scm_must_free,
  13 scm_done_malloc, scm_done_free is too difficult to use right and too
  14 hard to debug.
  15
  16 Guile itself is full of mtrigger related bugs, I'm afraid.  A typical
  17 one is in fports.c: the buffers for a fport are allocated with
  18 scm_must_malloc and freed with scm_must_free.  The allocation is
  19 reported to the GC, but the freeing never is.  The result is that the
  20 GC thinks that more and more memory is being allocated that it should
  21 be able to free, but that never actually gets freed (although in
  22 reality the program is very well behaved).  As a counter measure to
  23 constant GC, the GC raises its mtrigger setting in a frenzy until it
  24 wraps around, causing a `hallucinating GC' syndrome, effectively
  25 stopping the program dead.
  26
  27 (Watch scm_mtrigger while your favorite long-running Guile program
  28 executes, it will continuously rise.)
  29
  30 The problem is that scm_must_malloc registers the allocated amount
  31 with the GC, but scm_must_free does not de-register it.  For that, one
  32 would currently needs to use scm_done_free, or return an appropriate
  33 number from a smob free routine.
  34
  35 Another problem is that scm_must_malloc is used in places where it is
  36 probably not appropriate since the caller does not know whether that
  37 block memory is really ending up under the control of the GC, or not.
  38 For example scm_do_read_line in rdelim.c uses scm_must_malloc to
  39 allocate a buffer that it returns, and scm_read_line passes this to
  40 scm_take_string.  scm_take_string assumes that the memory has not been
  41 under GC control previously and calls scm_done_malloc to account for
  42 the fact that it now is.  But scm_must_malloc has _already_ increased
  43 scm_mallocated by the proper amount.  Thus, it is now doubly
  44 reflected.
  45
  46 Since the current interface is unsymmetrical (scm_must_malloc
  47 registers, but scm_must_free doesn't de-register), I propose to change
  48 it as follows.  Switching to this new interface will force us and
  49 everybody else to systematically review their code.
  50
  51     - the smob free routine does no longer return the number of bytes
  52       that have been freed.  For the transition period, free routines
  53       are first encourged to return 0, then required, and then their
  54       return type changes to void.
  55
  56     - scm_must_malloc, scm_must_free are deprecated.
  57
  58     - in their place, we have
  59
  60       Function: void *scm_malloc (size_t size);
  61
  62         Allocate SIZE bytes of memory.  When not enough memory is
  63         available, signal an error.  This function runs the GC to free
  64         up some memory when it deems it appropriate.
  65
  66         The memory is allocated by the libc "malloc" function and can
  67         be freed with "free".  We do not introduce a `scm_free'
  68         function to go with scm_malloc to make it easier to pass
  69         memory back and forth between different modules.
  70
  71       [ Note: this function will not consider the memory block to be
  72         under GC control. ]
  73
  74       Function: void *scm_realloc (void *mem, size_t newsize);
  75
  76         Change the size of the memory block at MEM to NEWSIZE.  A new
  77         pointer is returned.  When NEWSIZE is 0 this is the same as
  78         calling scm_free on MEM and NULL is returned.  When MEM is
  79         NULL, this function behaves like scm_malloc and allocates a
  80         new block of size SIZE.
  81
  82         When not enough memory is available, signal an error.  This
  83         function runs the GC to free up some memory when it deems it
  84         appropriate.
  85
  86       Function: void scm_gc_register_collectable_memory
  87                       (void *mem, size_t size, const char *what);
  88
  89         Informs the GC that the memory at MEM of size SIZE can
  90         potentially be freed during a GC.  That is, announce that MEM
  91         is part of a GC controlled object and when the GC happens to
  92         free that object, SIZE bytes will be freed along with it.  The
  93         GC will _not_ free the memory itself, it will just know that
  94         so-and-so much bytes of memory are associated with GC
  95         controlled objects and the memory system figures this into its
  96         decisions when to run a GC.
  97
  98         MEM does not need to come from scm_malloc.  You can only call
  99         this function once for every memory block.
 100
 101         The WHAT argument is used for statistical purposes.  It should
 102         describe the type of object that the memory will be used for
 103         so that users can identify just what strange objects are
 104         eating up their memory.
 105
 106       Function: void scm_gc_unregister_collectable_memory
 107                       (void *mem, size_t size);
 108
 109         Inform the GC that the memory at MEM of size SIZE is no longer
 110         associated with a GC controlled object.  You must take care to
 111         match up every call to scm_gc_register_collectable_memory with
 112         a call to scm_gc_unregister_collectable_memory.  If you don't
 113         do this, the GC might have a wrong impression of what is going
 114         on and run much less efficiently than it could.
 115
 116       Function: void *scm_gc_malloc (size_t size, const char *what);
 117       Function: void *scm_gc_realloc (void *mem, size_t size,
 118                                       const char *what);
 119
 120         Like scm_malloc, but also call scm_gc_register_collectable_memory.
 121
 122       Function: void scm_gc_free (void *mem, size_t size, const char *what);
 123
 124         Like free, but also call scm_gc_unregister_collectable_memory.
 125
 126         Note that you need to explicitely pass the SIZE parameter.
 127         This is done since it should normally be easy to provide this
 128         parameter (for memory that is associated with GC controlled
 129         objects) and this frees us from tracking this value in the GC
 130         itself.  (We don't do this out of lazyness but because it will
 131         keep the memory management overhead very low.)
 132
 133 The normal thing to use is scm_gc_malloc / scm_gc_free.
 134
 135
 136 Cell allocation and initialization
 137 ----------------------------------
 138
 139 The following has been implemented in the unstable branch now.
 140
 141 It can happen that the GC is invoked during the code that initializes
 142 a cell.  The half initialized cell is seen by the GC, which would
 143 normally cause it to crash.  To prevent this, the initialization code
 144 is careful to set the type tag of the cell last, so that the GC will
 145 either see a completely initialized cell, or a cell with type tag
 146 `free_cell'.  However, some slot of that `free' cell might be the only
 147 place where a live object is referenced from (since the compiler might
 148 reuse the stack location or register that held it before it was
 149 stuffed into the cell).  To protect such an object, the contents of
 150 the cell (except the first word) is marked conservatively.
 151
 152 What happened to me was that scm_gc_mark hit upon a completely
 153 uninitialized cell, that was tagged a s a free cell, and still pointed
 154 to the rest of the freelist were it came from.  (It was probably this code
 155
 156      :
 157     SCM_NEWCELL (port);                  // port is a free cell
 158     SCM_DEFER_INTS;
 159     pt = scm_add_to_port_table (port);   // this invokes the GC
 160      :
 161
 162 that caused it.)
 163
 164 scm_gc_mark would conservatively mark the cdr of the free cell, which
 165 resulted in marking the whole free list.  This caused a stack overflow
 166 because the marking didn't happen in a tail-calling manner.  (Even if
 167 it doesn't crash, a lot of unnecessary work is done.)
 168
 169 I propose to change the current practice so that no half initialized
 170 cell is ever seen by the GC.  scm_gc_mark would abort on seeing a free
 171 cell, and scm_mark_locations (and scm_gc_mark_cell_conservatively if
 172 will survive) would not mark a free cell, even if the pointer points
 173 to a valid cell.  scm_gc_sweep would continue to ignore free cells.
 174
 175 To ensure that initialization can not be interrupted by a GC, we
 176 provide new functions/macros to allocate a cell that include
 177 initialization.  For example
 178
 179     SCM scm_newcell_init (scm_bits_t car, scm_bits_t cdr)
 180     {
 181       SCM z;
 182       if (SCM_NULLP (scm_freelist))
 183         z = scm_gc_for_newcell (&scm_master_freelist,
 184                                 &scm_freelist);
 185       else
 186         {
 187           z = scm_freelist;
 188           scm_freelist = SCM_FREE_CELL_CDR (scm_freelist);
 189         }
 190       SCM_SET_CELL_WORD_1 (z, cdr);
 191       SCM_SET_CELL_WORD_0 (z, car);
 192       scm_remember_upto_here (cdr);
 193       return into;
 194     }
 195
 196 For performance, we might turn this into a macro, and find some
 197 specialized ways to make the compiler remember certain values (like
 198 some `asm' statement for GCC).  For a non-threaded Guile, and a
 199 cooperatively threaded one, the scm_remember_upto_here call is not
 200 even needed since we know the the function can not be
 201 interrupted. (Signals can not interrupt the flow of control any
 202 longer).
 203
 204 In the transition period, while SCM_NEWCELL is deprecated, we can make
 205 it always initialize the first slot with scm_tc16_allocated.  Such
 206 cells are marked conservatively by the GC.  SCM_NEWCELL can have
 207 abysmal performance while being deprecated.