Changes between Version 20 and Version 21 of GarbageCollectorNotes


Ignore:
Timestamp:
May 19, 2006 1:11:52 PM (9 years ago)
Author:
guest
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • GarbageCollectorNotes

    v20 v21  
    103103The existing GC in GHC is a single threaded one. When the RTS detects memory pressure the GC stops all the Haskell threads and then one thread that does the garbage collection and then resumes all the other suspended threads. On a multiprocessor machine such a design is obviously a bottle neck and it is desirable to garbage collect using multiple parallel threads.  
    104104 
    105 == GC Data Structures == 
    106  
    107 === Blocks and Mega Blocks === 
    108  
    109 The GC allocates memory from the OS in 1 Mb sized chunks, called mega blocks, which it then divides into pages and manages itself. Each 4k page is called a block and is associated with a block descripter (the abbrevaition BD is used a lot). The BDs for all the blocks on the are stroed at the start of the mega block.  
    110  
    111 The BD keeps information about a block. This the BD defintion from blocks.h in the RTS. 
    112  
    113 {{{ 
    114 #!c 
    115 typedef struct bdescr_ { 
    116   StgPtr start;                 /* start addr of memory */ 
    117   StgPtr free;                  /* first free byte of memory */ 
    118   struct bdescr_ *link;         /* used for chaining blocks together */ 
    119   union {  
    120       struct bdescr_ *back;     /* used (occasionally) for doubly-linked lists*/ 
    121       StgWord *bitmap; 
    122   } u; 
    123   unsigned int gen_no;          /* generation */ 
    124   struct step_ *step;           /* step */ 
    125   StgWord32 blocks;             /* no. of blocks (if grp head, 0 otherwise) */ 
    126   StgWord32 flags;              /* block is in to-space */ 
    127 #if SIZEOF_VOID_P == 8 
    128   StgWord32 _padding[2]; 
    129 #else 
    130   StgWord32 _padding[0]; 
    131 #endif 
    132 } bdescr; 
    133 }}} 
    134  
    135 Most of the fields ina BD are self explanatory. Let me add a few quick decriptions however. Each bdescr or BD maintains its start address and a "free" pointer used to indicate the next free location in the block. Each block also knows about what generation it belongs to and has a pointer to the step it belongs to (more about generations and steps later).  
    136  
    137 If a large object is allocated and a block is a part of a large object, then the first block is has a count of the number of blocks that are part of the object. The link list of blocks making up the object is maintained by the link pointer. [This may not be entirely correct - I will come back to this later]. 
    138  
    139 === Generations === 
    140 The GHC GC is a generational collector. The number of generations is set to 2 by default and they are referred to as gen 0 and gen 1. gen 0 has never objects, objects that survive collections in gen 0 are promoted to gen 1. Older objects reside in gen 1.  
    141  
    142 === Command Line Switches === 
    143 The number of generations in an exceution of a compiled haskell program can be changed by by using the command line switch -G<n>, where n is the number of generations. This is an RTS switch and so has to be used as follows -  
    144  
    145 {{{ 
    146 main.exe +RTS -G5 -RTS  
    147 }}} 
    148  
    149 Where main.exe is the compiled program and we want it to have 5 generations. More about the RTS switches can be found here  
    150 [http://www.haskell.org/ghc/docs/latest/html/users_guide/runtime-control.html Runtime Control]. 
    151  
    152 On the topic of command line switches, for a compiler hacker this is also interesting -  
    153 [http://www.haskell.org/ghc/docs/latest/html/users_guide/options-debugging.html Debugging the compiler] 
    154  
    155 === Steps === 
    156 GHC generations are divided into steps. The number of steps per generations is a configurable value as well. The last generation, the oldest one has only one step. By default GHC compiled programs have 2 steps per generation. Since GHC usually has only 2 generations, it has 2 steps in gen 0 and 1 step in gen 1. Steps of a generation are referred to by their index number starting from 0.  
    157  
    158 Garbage collection happens at the level of generations. So when you say that you are collecting gen 0, you are essentially collecting all the steps in gen 0. If you are collecting gen 4, then you are collecting all the steps in gen 0 to gen 4. Objects that survive a collection are promoted into the next higher step, or into the next higher generation if the object is already in the highest step of its generation.  
    159  
    160 The reasoning behing having steps is approximately this - if there were no steps and a surviving a gen0 collection meant automativ promotion to gen1, then it means that at the time when gen0 happened several very new objects (which are potentially shortlived as well) get promoted to gen1. gen1 collections are expensive since higher generations are larger and hence these objects will reside in memory a long time before they get collected. On the other had if gen0 were divided into two steps then a gen0step0 object hops to gen0setp1 on its first survival and needs to survive yet another GC before it is promoted to gen1. [This I think is a very neat idea. My current understanding is that the .Net GC does have steps. Is this correct?] 
    161  
    162 That said, lets look at the data structures. This is what a generation looks like -  
    163 {{{ 
    164 typedef struct generation_ { 
    165   unsigned int   no;                    /* generation number */ 
    166   step *         steps;                 /* steps */ 
    167   unsigned int   n_steps;               /* number of steps */ 
    168   unsigned int   max_blocks;            /* max blocks in step 0 */ 
    169   bdescr        *mut_list;              /* mut objects in this gen (not G0)*/ 
    170  
    171   /* temporary use during GC: */ 
    172   bdescr        *saved_mut_list; 
    173  
    174   /* stats information */ 
    175   unsigned int collections; 
    176   unsigned int failed_promotions; 
    177 } generation; 
    178 }}} 
    179  
    180 This is what a step looks like -  
    181 {{{ 
    182 typedef struct step_ { 
    183   unsigned int         no;              /* step number */ 
    184   bdescr *             blocks;          /* blocks in this step */ 
    185   unsigned int         n_blocks;        /* number of blocks */ 
    186   struct step_ *       to;              /* destination step for live objects */ 
    187   struct generation_ * gen;             /* generation this step belongs to */ 
    188   unsigned int         gen_no;          /* generation number (cached) */ 
    189   bdescr *             large_objects;   /* large objects (doubly linked) */ 
    190   unsigned int         n_large_blocks;  /* no. of blocks used by large objs */ 
    191   int                  is_compacted;    /* compact this step? (old gen only) */ 
    192  
    193   /* During GC, if we are collecting this step, blocks and n_blocks 
    194    * are copied into the following two fields.  After GC, these blocks 
    195    * are freed. */ 
    196   bdescr *     old_blocks;              /* bdescr of first from-space block */ 
    197   unsigned int n_old_blocks;            /* number of blocks in from-space */ 
    198  
    199   /* temporary use during GC: */ 
    200   StgPtr       hp;                      /* next free locn in to-space */ 
    201   StgPtr       hpLim;                   /* end of current to-space block */ 
    202   bdescr *     hp_bd;                   /* bdescr of current to-space block */ 
    203   StgPtr       scavd_hp;                /* ... same as above, but already */ 
    204   StgPtr       scavd_hpLim;             /*     scavenged.  */ 
    205   bdescr *     scan_bd;                 /* block currently being scanned */ 
    206   StgPtr       scan;                    /* scan pointer in current block */ 
    207   bdescr *     new_large_objects;       /* large objects collected so far */ 
    208   bdescr *     scavenged_large_objects; /* live large objs after GC (d-link) */ 
    209   unsigned int n_scavenged_large_blocks;/* size of above */ 
    210   bdescr *     bitmap;                  /* bitmap for compacting collection */ 
    211 } step; 
    212 }}} 
    213  
    214 These definitions can be found in rts\storage.h.  
    215  
    216 Here is a little digram of the data structure formed by the generations and steps. The global variable 'generations' is a an array of pointers to generations. Each generation has 'steps' as a pointer array to its steps.  
    217  
    218 http://www.cs.indiana.edu/~rpjames/HaskellGC/ds/generations-steps.jpg 
    219  
    220 Each step contains a pointer to a link list of blocks that are part of the step. 
    221  
    222 http://www.cs.indiana.edu/~rpjames/HaskellGC/ds/step-blocks.jpg 
    223  
    224  
     105== GcDataStructures ==  
    225106 
    226107== Allocation ==