ghc/docs/NOTES.garbage.collection

   1
   2                         GARBAGE COLLECTION
   3                         ~~~~~~~~~~~~~~~~~~
   4
   5 The following discussion outlines how the GC is organised and what C
   6 the compiler needs to produce to use it.
   7
   8 The files associated with GC are:
   9
  10         StgGC.h                 header file -- macros and externs
  11         StgCreate.lc            GC init routines
  12         StgOverflow.lhc         Overflow routines -- interface to GC
  13         GC2s.lhc                }
  14         GC1s.lhc                } GC control routines
  15         GCdm.lhc                } for each particular GC
  16         GCap.lhc                }
  17         GCevac.lc               Evacuation code fragments (copying GC)
  18         GCscav.lhc              Scavenging code fragments (copying GC)
  19         GCcompact.lhc           Inplace Compacting GC code fragments
  20         GCmark.lhc              Marking code fragments
  21
  22 Other files:
  23
  24     In gctest/
  25         gctest.c                GC Small detail test bed program
  26
  27     In gcstat/
  28                                 Performance evaluation stuff
  29
  30
  31 Basic Requirements of the C code Produced by the Haskell Compiler
  32 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  33
  34 There are two main aspects of the compiler generated code that
  35 interact with GC:
  36
  37 1) Compiled haskell code calls the garbage collection routine when the
  38    heap overflows by entering the appropriate _HEAP_OVERFLOW_... routine.
  39
  40    These routines isolate register usage and calls the GC control
  41    routine that was defined at compile time.
  42
  43    For a description of the heap overflow conventions see:
  44
  45         ~grasp/ghc/compiler/absCSyn/RTSLabels.lhs
  46
  47
  48    The following must be adhered to by the mutator:
  49
  50                 REQUIREMENT                              COLLECTOR
  51      SpA and SpB point to A and B stacks                  all
  52
  53      Hp must point to last word allocated                 dual,comp
  54      All updated closures must "know" their original      dual,comp
  55         size
  56
  57      HpLim must point to one beyond top of root stack     appel
  58      Updated closures in the old generation must "know"   appel
  59         their original size
  60
  61    The GC Control routines have to know about the pointer stack and
  62    Update Stack.
  63
  64 2) The info tables that are pointed to by closures must have the
  65    appropriate GC routines within them. This is achieved by using the
  66    following C Macros to declare them:
  67
  68                 table_name --  the name given to the info table
  69                 entry_code --  the name of the normal evaluation
  70                                entry code required for the closure
  71                 size       --  the No of free var words in the closure
  72                 ptrs       --  the number of pointers in the closure
  73
  74
  75         SPEC_INFO_TABLE(table_name,entry_code,size,ptrs);
  76
  77         Declares an info table with specialiazed code fragments
  78         These are currently available for the following closure
  79         configurations: size, ptrs
  80                 1,0     2,0     3,0     4,0     5,0
  81                 1,1     2,1     3,1
  82                         2,2
  83                                 3,3
  84                                         4,4
  85                                                 5,5
  86                                                         ...
  87                                                                 11,11
  88
  89         GEN_INFO_TABLE(table_name,entry_code,size,ptrs);
  90
  91         Declares an info table that uses generic code fragments and
  92         places data to drive these routines in the info table.
  93         These are available for all combinations of size,ptrs (even
  94         those for which SPEC routines are provided).
  95
  96
  97         STATIC_INFO_TABLE(table_name,entry_code);
  98
  99         Declares an info table suitable for a static closure.
 100
 101
 102         DATA_INFO_TABLE(table_name,entry_code);
 103
 104         Declares an info table suitable for a data closure.
 105         This closure contains no heap pointers and its size
 106         (of data and size field) in its first word
 107
 108                 See NOTES.arbitary-ints
 109
 110
 111         IND_INFO_TABLE(table_name,ind_code);
 112
 113         Declares an info table suitable for an indirection.
 114         But see below !! (ToDo)
 115
 116
 117 Using a Particular Garbage Collection Scheme
 118 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 119
 120 When deciding which collector to use there are two decision points.
 121
 122 At compile time it must be decided which code fragments are going to
 123 be attached to closures. This will limit the possible choice of GC
 124 schemes at run time.
 125
 126 To compile the GC code and compiler-produced C Code for a particular
 127 set of code fragments an appropriate define (-D) directive is given
 128 to the compiler.
 129
 130 Possible directives are:
 131
 132                         Code Fragments          GC Control Routines
 133
 134 -DGC2s                  Copying                 Two Space Collection
 135
 136 -DGC1s                  Marking & Compacting    Inplace Compaction
 137
 138 -DGCdm                  Copying, Marking        DualMode Collection
 139                          & Compaction             (+ TwoSpace and Compaction)
 140 -DGCap                  Copying, Marking        Appels Collector
 141                          & Compaction             (+ Compaction)
 142
 143 If none of these are defined the result will be No Collection Schame.
 144 Heap will be allocated but the program will die if it is ever filled.
 145
 146 Other Directives:
 147
 148 -D_GC_DEBUG             Provides detailed GC debugging trace output
 149                         (if showGCTrace set)
 150
 151 Note that the GC code will eventually be set up already compiled for
 152 the different schemes and all that will be required will be to link
 153 with the appropriate object files. The compiler produced C will still
 154 need to be compiled with the appropriate define.
 155
 156
 157 Trace and Statistics Info
 158 ~~~~~~~~~~~~~~~~~~~~~~~~~
 159
 160 There are a couple of variables that can be set to provide info about
 161 GC.
 162
 163 showGCTrace -- Provides detailed trace of GC and closure movement
 164        TRUE -- Summary about GC invokation and heap location
 165         & 2 -- Detailed trace of copying AND compacting collection
 166         & 4 -- More detail about linked location lists during compaction
 167         & 8 -- Detalied info about marking
 168
 169         The & options are only available if compiled with -D_GC_DEBUG
 170
 171 showGCStats -- Provides summary statistics about GC performance
 172       (ToDo)
 173
 174 ToDo: These should eventually be able to be set by runtime flages
 175
 176
 177 Compiler Extensions Required for Compacting Collection
 178 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 179
 180 There are a number of additional requirements required of the STG
 181 machine and the resulting C code for Inplace Compaction to work.
 182
 183 The most important and awkward arises from the fact that updated nodes
 184 will be scanned. This requires updated nodes (blackholes, indirections
 185 or inplace updates) to know how big the original closure was (so the
 186 location of the next closure can be determined).
 187
 188 Implications (Suggestions -- Still to be done):
 189
 190    Need specialized black holes info pointers which know their size.
 191
 192    Code on the Update Stack needs to know the orig closure size. Either
 193    record this size or have specialised update code fragments.
 194
 195    Updated closures need to know orig size. Possible solns are:
 196
 197         Create dummy garbage closures at the end to fill the hole.
 198
 199         Store size of closure in free space beyond and have GC
 200         routines which look here for the size.
 201
 202         Specialised indirections that know their size.
 203
 204    May be able to search beyond the end of the closure for the next
 205    info pointer. Possibly blanking out the unused portion of the
 206    closure.