CSc 453Compilers and Systems Software24 : Garbage CollectionDepartment of Computer ScienceUniversity of [email protected]° 2009 Christian CollbergIntroductionDynamic Memory ManagementThe run-time system linked in with the generated code shouldcontain routines for allocation/deallocation of dynamicmemory.Pascal, C, C++, Modula-2 Explicit deallocation of dynamicmemory only. I.e. the programmer is required to keeptrack of all allocated memory and when it’s safe tofree it.Eiffel Implicit deallocation only. Dynamic memory whichis no longer used is recycled by the garbagecollector.Ada Implicit or explicit deallocation (implementationdefined).Modula-3 Implicit and explicit deallocation (programmer’schoice).Memory ManagementMemory ManagementIn a language such as C or Pascal, there are three ways toallocate memory:1Static allocation. Global variables are allocated at compiletime, by reserving2Stack allocation. The stack is used to store activation records,which holds procedure call chains and local variables.3Dynamic allocation. The user can create new memory at will,by calling a new or (in unix) malloc procedure.The compiler and run-time system divide the available addressspace (memory) into three sections, one for each type ofallocation:Memory Management. . .1The static section is generated by the compiler and cannot beextended at run-time. Called the uninitialized datasection in unix’s a.out.2The stack. The stack grows and shrinks during execution,according to the depth of the call chain. Infinite recursionoften leads to stack overflow. Large parameters can also resultin the program running out of stack space.3The heap. When the program makes a request for moredynamic memory (by calling malloc, for example), a suitablechunk of memory is allocated on the heap.Memory Management. . .Static allocation – GlobalvariablesStack allocation – Procedurecall chains, Local variables.Dynamic allocation – NEW,malloc, On the heap.Heap(Global Variables)Initialized Data(strings,reals...)Program CodeStackUninitialized DataInterface to Dynamic allocationC, C++: char* malloc(size) and free(char*) arestandard library routines.Pascal: new(pointer var) and dispose(pointer var)are builtin standard procedures.Java: new(class name) is a standard function.LISP: cons creates new cells:nullbcnullabc’(b c) ’(a b c)TailHead(cons ’a ’(b c))Explicit DeallocationExplicit DeallocationPascal’s new/dispose, Modula-2’s ALLOCATE/DEALLOCATE,C’s malloc/free, C++’s new/delete, Ada’snew/uncheckeddeallocation (some implementations).Problem 1: Dangling references: p=malloc(); q=p;free(p);.Problem 2: Memory leaks, Heap fragmentation.free list:free list:163264Large cellSmall cellHeap:12845128Implicit DeallocationImplicit DeallocationLISP, Prolog – Equal-sized cells; No changes to old cells.Eiffel, Modula-3 – Different-sized cells; Frequent changes toold cells.When do we GC?Stop-and-copy Perform a GC whenever we run out ofheapspace (Modula-3).Real-time/Incremental Perform a partial GC for each pointerassignment or new (Eiffel, Modula-3).Concurrent Run the GC in a separate process.Implicit Deallocation. . .Fragmentation – Compact the heap as a part of the GC, oronly when the GC fails to return a large enough block.Algorithms: Reference counts, Mark/ssweep, Copying,Generational.Garbage Collection ProblemsFinding the Object GraphFinding the roots: The dynamic objects in a program form agraph. Most GC algorithms need to traverse thisgraph. The roots of the graph can be in1global variables2registers3local variables/formal parameters on the stack.Hence, the compiler must communicate to the GCwhich registers/variables contain roots.Finding internal pointers: Structured variables (arrays, records,objects) may contain internal pointers. These mustbe known to the GC so that it can traverse thegraph. Hence, the compiler must communicate tothe GC the type of each dynamic object and theinternal structure of each type.Finding the beginning of objects: What happens if the onlypointer to an object points somewhere in the middleof the object? We must either be able to find thebeginning of the object, or make sure the compilerdoes not generate such code.8:AC%r8ExecutionStackforARPforARQforARRtemplateGGlobalsPtrs: [12]Size:96Template for PPtrs: [0]Size:4Template for MAINSize:32Ptrs: [4,12]Template for T1Ptrs: [8]Size: 24Template for T2HeapO: templateO: template8:12:O: template8:Pointer MapsThe internal structure of activation records & structuredvariables is described by run-time templates.Every run-time object has an extra word that points to a typedescriptor (or Temaplate), a structure describing which wordsin the object are pointers. This map is constructed atcompile-time and stored statically in the data segment of theexecutable.Pointer Maps. . .When the GC is invoked, registers may also contain validpointers. The compiler must therefore also generate (for everypoint where the GC may be called) a pointer map thatdescribes which registers hold live pointers at this point. Forthis reason, we usually only allow the GC to run at certainpoints, often the points where new is called.We must also provide pointer maps for every function callpoint. A function P may call Q which calls new whichinvokes the GC. We need to know which words in P’sactivation record that at this point contain live pointers.Pointer Maps. . .How does the GC look up which pointer map belongs to aparticular call to procedure P at a particular address a? Thepointer maps are indexed by the return address of P! So, totraverse the stack of activation records, the GC looks at eachframe, extracts the return address, finds the pointer map forthat address, and extracts each pointer according to the map.GC Algorithms: ReferenceCountsAlgorithm: Reference CountsAn extra field is kept in each object containing a count of thenumber of pointers which point to the object.Each time a pointer is made to point to an object, thatobject’s count has to be incremented.Similarly, every time a pointer no longer points to an object,that object’s count has to be decremented.When we run out of dynamic memory we scan through theheap and put objects with a zero reference count back on thefree-list.Maintaining the reference count is costly. Also, circularstructures (circular linked lists, for example) will not becollected.Every object records the number of pointers pointing to it.When a pointer changes, the corresponding object’s referencecount has to