Understanding Garbage Collection Algorithms in Memory Management

Copying GC and Reference Counting Jonathan Kalechstain Tel Aviv University 11/11/2014

Outline of talk Reminder Copying Garbage Collection Algorithm Reference Counting Algorithm Summary

Recap Last week we went through two algorithms - Mark and Sweep - Mark Compact Mark and Sweep suffers from fragmentation Mark Compact is very costly

Mark & Sweep Traverse live objects & mark black. White objects can be reclaimed. registers Roots stack Heap 4

Mark-Compact During the run objects are allocated and reclaimed. Gradually, the heap gets fragmented. When space is too fragmented to allocate, a compaction algorithm is used. Move all live objects to the beginning of the heap and update all pointers to reference the new locations. The Heap 5

Copying garbage collection Part I Part II B A C Roots D E 6

The collection copies Part I Part II A B C A C Roots D E 7

Roots are updated; Part I reclaimed. Part I Part II A C Roots 8

Algorithm Reminder : New(): ref allocate() if ref = null collect() ref allocate() if ref = null error out of memory return ref

Algorithm (2) createSemispaces(): // This is an initialization function tospace HeapStart extent (HeapEnd HeapStart) / 2 // size of semispace top fromspace HeapStart + extent free tospace tospace fromspace free top

Algorithm (3) atomic allocate(size): newfree free + size if newfree > top //No more room left! Need to collect! returnnull free newfree return free // free is the pointer to the next free space tospace fromspace A C top free

Algorithm (3) atomic allocate(size): newfree free + size if newfree > top //No more room left! Need to collect! returnnull free newfree return free // free is the pointer to the next free space tospace fromspace A C top free

Algorithm (4) If allocate fails, collect is called atomic collect(): flip() initialise(worklist) for each fld in Roots process(fld) while not isEmpty(worklist) ref remove(worklist) for each child in Pointers(ref) process(child)

Algorithm (5) Flip(): flip() makes sure to change the pointers prior to actually moving memory fromspace , tospace tospace,fromspace top tospace+extent free tospace //extent == sizeof(0.5*heap) tospace fromspace fromspace tospace A C A C top top free free

Something about pointers Let N be some address foreach p in Pointers(N) Definitions: 1. The number of fields in N is |N| 2. Pointers(N) = {?|a=&N[i], ? ? ? < ? where N[i] is a pointer} So Pointer(N) is the set of addresses of fields of N who are pointer themselves! N address 1000 1800 5000 2000 1004 2000 null 1008 Here: Pointers(N) = {1000,1004}

Algorithm (6) If allocate fails, collect is called atomic collect(): flip() initialise(worklist) for each fld in Roots process(fld) while not isEmpty(worklist) ref remove(worklist) for each child in Pointers(ref) process(child)

Algorithm (7) roots fld free = 1040 process(fld): fromRef fromRef *fld if fromRef != null *fld forward(fromRef) free = 1000 FA forward(fromRef): toRef forwardingAddress(fromRef) if toRef = null toRef copy(fromRef) return toRef A Copy(fromRef): toRef free free free+size(fromRef) move(fromRef,toRef) forwardingAddress(fromRef) toRef add(worklist,toRef) return toRef 1. fromRef = &A 2. toRef = null 3. toRef = 1000 4. free = free + 40 = 1040 5. FA(fromRef)=1000 6. Return 1000

Algorithm (8) free = 1080 free = 1040 process(fld): fromRef *fld if fromRef != null *fld forward(fromRef) A` FA A forward(fromRef): toRef forwardingAddress(fromRef) if toRef = null toRef copy(fromRef) return toRef ptr1 FA B Copy(fromRef): toRef free free free+size(fromRef) move(fromRef,toRef) forwardingAddress(fromRef) toRef add(worklist,toRef) return toRef 1. fromRef = A.ptr1 2. toRef = null 3. toRef = 1040 4. free = free + 40 = 1080 5. FA(fromRef)=1040 6. Return 1040

Algorithm (5) free = 1080 A ptr1

Definitions A node copied to the to area is considered grey (went through the function process). A node whose pointers were updated is considered black Once a node is black, all it s children are copied and considered grey (or black if they were already scanned)

Back to Algorithm atomic collect(): flip() initialize(worklist) for each fld in Roots process(fld) while not isEmpty(worklist) ref remove(worklist) for each child in Pointers(ref) process(child)

Work List Implementation We assumed that we get nodes by some order Implementation possibilities: - Queue - Stack - Pointer (Cheney ,1970) As we will see, different implementations can have an effect on performance.

Cheneys Worklist Initialize(worklist): scan free isEmpty(worklist): scan = free Remove(worklist): ref scan scan scan + sizeof(next_item) return ref Scan points to the next grey item (copied but not scanned) Free points to next available memory in the to area

Full Running Example Note the colors! White is unvisited Grey is copied but not scanned Black is scanned (and will never be scanned again)

Full Running Example(2) Fromspace L is a linked list L is directly reachable from the roots Tospace

Full Running Example(3) Fromspace Tospace 1. L was copied to To space 2. L points to L` 3. Scan points to start of tospace 4. L` points to A and E 5. Scan of L` next page scan free

Full Running Example(4) Fromspace Tospace scan free Flow: 1. Get next item from remove(worklist) and advance scan. 2. Copy all children, update free and references.

Full Running Example(5) Fromspace Tospace scan free Flow: 1. Get next item from remove(worklist) and advance scan. 2. Copy all children, update free and references.

Full Running Example(6) Fromspace Tospace scan free Flow: 1. Get next item from remove(worklist) and advance scan. 2. Copy all children, update free and references.

Full Running Example(7) Fromspace Tospace scan free Flow: 1. Get next item from remove(worklist) and advance scan. 2. Copy all children, update free and references.

Full Running Example(8) Fromspace Tospace scan free Flow: 1. Get next item from remove(worklist) and advance scan. 2. Copy all children, update free and references.

Correctness Lemma 1 : free is updated a finite number of times Lemma 2 : free += c iff at some later phase scan += c (c is an object and it s byte size) Lemma 3 : The algorithm terminates Lemma 4 : All live objects are copied Lemma 5 : All live object are scanned Theorem 1 : All scanned objects are updated correctly at the end of the algorithm.

Correctness(1) Lemma 1 : free is called a finite number of times - There is a finite number of objects. - Free is updated from the function copy() - When an object is copied, it s forwarding address is updated. - Once a forwarding address is not null, then copy() isn t invoked

Correctness(2) Lemma 2 : free += c if at some later phase scan += c -Let ????? be the n th time free is updated. -Let ????? be the n th time scan is updated. scan free By induction on n. base : for n = 1 free is advanced by some value c. Then, after all roots finished being copied, remove() will advance scan by c. atomic collect(): flip() initialise(worklist) for each r in Roots while not isEmpty(worklist) ref remove(worklist) for each fld in ref Initialize(worklist): Remove(worklist): ref scan scan scan + sizeof(next_item) return ref process(r) process(fld)

Correctness(3) Lemma 2 : free += c if at some later phase scan += c Step : Let s assume at some point ?????+1 = ????? + ? By the hypothesis, at some point ????? = ????? At some point, because ????? < ?????|? ?+1, we will enter remove and commit ?????+1= ?????+ ? Remove(worklist): ref scan scan scan + sizeof(next_item) return ref atomic collect(): flip() initialise(worklist) for each r in Roots while not isEmpty(worklist) ref remove(worklist) for each fld in ref process(r) process(fld)

Correctness(4) Lemma 3 : The algorithm terminates -Follows immediately from lemmas (1+2) isEmpty(worklist): scan = free atomic collect(): flip() initialise(worklist) for each fld in Roots process(fld) while not isEmpty(worklist) ref remove(worklist) for each child in Pointers(ref) process(child)

Correctness(5) Lemma 4 : All live objects are copied By induction on d, the distance from the roots base: d = 1, at the beginning all roots are processed and therefore copied. step: assume for some d. Lets observe some object o of distance d+1. Let s look at o s father s. s was discovered, copied (i.h) and by lemma 1 scanned. When s was scanned o had to be copied Lemma 5 : All live object are scanned -Follows immediately from lemmas (1+4)

Correctness(6) Theorem 1 : All scanned objects are updated correctly at the end of the algorithm. - When an object is scanned, all it s pointers are either copied and updated, or either updated from the forwarding address. - From lemma 5, all live objects are copied and scanned

Traversal Order & Locality In the example and algorithm we saw, the traversal was BFS. The only extra memory required was a pointer. Is BFS better than DFS ?

Traversal Order & Locality(2) 1 2 3 4 5 6 7 8 9 Page 1 Page 2 Page 3 BFS 1 2 3 4 5 6 7 8 9 DFS 1 2 4 7 8 5 3 6 9

Traversal Order & Locality(3) BFS tends to separate children from parents. DFS keeps them more closely. Cache misses and page faults are important. DFS requires a stack and more space. Compromise?

Pros/cons of copying GC Easy allocation Avoid external fragmentation Can reorder objects to decrease future page faults and cache misses Easy to Implement Uses half the size of heap, requires more collections for same size heap.

Reference counting Recall that we would like to know if an object is reachable from the roots. Associate a reference count field with each object: how many pointers reference this object. When nothing points to an object, it can be deleted. Very simple, used in many systems. 43

Basic Reference Counting Each object has an RC field, new objects get o.RC:=1. When p that points to o1 is modified to point to o2 we execute: o1.RC--, o2.RC++. if then o1.RC==0: Delete o1. Decrement o.RC for all children of o1. Recursively delete objects whose RC is decremented to 0. p o1 o2 44

Reference counting Algorithm is direct Reference update is part of the mutator s responsibility. Because there can by many mutators, the writing function must be atomic. 45

Easy Reference Counting New(): ref allocate() if ref = null error Out of memory rc(ref) 0 return ref addReference(ref): if ref != null rc(ref) rc(ref) + 1 deleteReference(ref): if ref != null rc(ref) rc(ref) 1 if rc(ref) = 0 for each fld in Pointers(ref) deleteReference(*fld) free(ref) atomic Write(src,i,ref): addReference(ref) deleteReference(src[i]) src[i] ref 46

Example L RC=1 ptrA ptrB D B C A RC=1 RC=1 RC=2 RC=1 ptrA ptrA ptrA ptrA ptrB ptrB ptrB ptrB 47

Example L RC=1 ptrA ptrB D B C A RC=2 RC=0 RC=1 RC=0 ptrA ptrA ptrA ptrA ptrB ptrB ptrB ptrB L.ptrA = D 48

Example L RC=1 ptrA ptrB D C RC=1 RC=0 ptrA ptrA ptrB ptrB L.ptrB = null 49

Example L RC=1 ptrA ptrB D RC=1 ptrA ptrB 50