15 213 Recitation 5 March 2001 Urs Hengartner Overview Dynamic Memory Allocation Garbage Collection Lab 3 Pointer Arithmetic gc malloc Logistics for Lab 3 Checkpoint 1 next Tuesday Implement correct garbage collector does not need to provide coalescing of freed memory blocks Assigned Wednesday in two weeks Implement coalescing add optimizations Be warned Not much coding 100 and 50 LOC respectively but debugging can be time consuming Dynamic Memory Allocation Memory has to be allocated at runtime if size is unknown at compile time Dynamic allocation int array int malloc len sizeof int C unlike Java requires progammer to explicitly free dynamically allocated memory free array Heap Dynamic memory is allocated on the heap Memory layout simplified 0xFF esp Stack brk Heap 0x00 Garbage Collection Garbage Dynamic memory that can no longer be accessed Example void foo int len int array int malloc len sizeof int memory block array is pointing to becomes garbage after foo returns Let memory management detect garbage and collect free it automatically Detecting Garbage While in foo esp Rest of stack len ra ebp array After leaving foo esp Memory block is reachable by pointer on stack and cannot be collected Rest of stack array Memory block is no longer reachable by pointer on stack and can be collected Removing Garbage Mark and Sweep Algorithm first attempt Scan rootset for pointers pointing to allocated memory block in heap Mark all these memory blocks Free all un marked memory blocks Rootset Pointers in Stack Registers Global variables Are these all the pointers we have to consider No allocated memory blocks in heap could also contain pointers e g in a linked list Mark and Sweep Algorithm Scan rootset for pointers pointing to allocated memory block in heap for each of these pointers call mark block void mark block If memory block block has not already been marked Mark it Scan it for further pointers to allocated memory blocks in heap and call mark for each of them Free all unmarked memory blocks Detecting Pointers How can we detect pointers to allocated memory block in global data stack registers and memory blocks Four bytes aligned value Value between lower and upper bound of heap Things that make detection hard C does not tag pointers anything could be a pointer pointer could be assigned to integer C allows pointer arithmetic that is pointer does not have to point to beginning of allocated memory block in heap but to some random location within such a block Conservative Approach Any four byte aligned value that points to an allocated memory block in the heap is considered to be a pointer thus memory block won t be freed Such a pointer is allowed to point to beginning of allocated memory block or to some random location within an allocated memory block Lab 3 Given gc malloc which allocates memory from its own heap dseg lo dseg hi Todo add garbage collection to gc malloc Possible approach whenever gc malloc fails to satisfy memory request collect garbage and try again Alternative collect garbage upon every call to gc malloc Data structures Free list keeps circular linked list of free blocks Splay Tree keeps tree of allocated blocks Note free list and splay tree are also allocated in the heap managed by gc malloc see Figure 1 dseg lo points to free list and dseg lo sizeof long to root of splay tree Free List Free memory blocks in the heap are kept in a circular linked list Nodes of list consist of header and the actual free memory block Header contains pointer to next and previous free block and size of free block Note order of blocks in list does not correspond to the order implied by the address of a free block Use gc add free and gc remove free to add remove free blocks to from free list Splay Tree I Allocated memory blocks in the heap are kept in a splay tree Nodes of tree consist of header and the actual memory block Header contains pointer to left and right child and size of allocated block Nodes are ordered based on their memory address binary search tree Use insert and delete to add remove blocks to from splay tree Splay Tree II Use contains for querying whether pointer points to allocated memory block in heap either to its beginning or to some location within Notes Size stored in header does not include size of header Size of header of a splay tree node is identical to size of header of a free list node insert remove and contains re balance splay tree that is have to reset pointer to root dseg lo sizeof long after each call Marking How does marking work We could allocate another bit in the header part of a splay tree node and use it as mark Observation size of allocated block is always multiple of eight bytes convention thus lower three bits of size entry in header are always zero Use lowest bit for marking Pointer Arithmetic I Take a look at slides from first recitation Do not use void pointers for pointer arithmetic ptr i is the same as ptr i actual number of bytes added to ptr depends on type of pointer int int ptr 0 char char ptr 0 int ptr int ptr is now 4 char ptr char ptr is now 1 Pointer Arithmetic II Use type casting to convert between different types of pointers list t Tree ptr t char void Example tree is pointer to unmarked node in splay tree thus it can be freed Tree tree put it into free list second argument to gc add free has to be of type list t gc add free dseg lo list t tree gc malloc 15 16 Get callee save registers and current frame pointer 19 Round up requested size to a power of 8 similar to malloc 22 34 Get pointer to free list stored at dseg lo and search for memory block that is big enough first fit 37 49 If there is no such block increase upper boundary of heap dseg hi and put new memory block into free list gc malloc 53 Test whether found or new block is big enough for a split 54 63 If not return entire block Remove it from free list Insert it into splay tree Fix pointer to root of splay tree stored at dseg log sizeof long 66 87 If so split block and return first part Create new free list block consisting of second part and replace found entry with this new block Update size entry in header of found entry and put it into splay tree fix pointer to root How to proceed Make sure you understand everything I just explained Read through handout ask your TA if there is something you don t understand Study malloc c and comments in splay tree c Implement garbage collection algorithm outlined earlier Checkpoint 1 does not require coalescing just call gc add free for
View Full Document
Unlocking...