Intro
There are two types of programming languages: those that manage memory manually, such as C and C++, and those that manage memory automatically, such as Java and Haskell.
In C programs, the malloc function is used to allocate memory space and the free function is used to release it, but since this is done manually, it is prone to causing bugs, such as memory leakage due to consuming all the memory, or security problems due to double freeing of memory. For example, a memory leak may occur if all the memory is consumed, or a security problem may occur due to double freeing of memory. Releasing the memory once by the free function may cause a buffer overflow, which may crash the application, or a third party may be able to execute arbitrary code when the same value is returned twice by the malloc function.
Garbage collection is one of the most widely used automatic memory management schemes created by American researcher John McCarthy in 1959. Garbage collection traces all objects, classifies them into those that may be used in the future and those that are no longer used, and releases the latter. The last step is to move the objects and release them. Finally, objects are moved to reduce memory. There are two major algorithms used in Garbage collection: reference counting and tracing GC. Here, we will look at the behaviour of these two typical algorithms.
Reference Counting
It is an algorithm that thinks that an object pointed to by a pointer from somewhere will be used in the future, and it always counts the reference count of each object. The reference count of each object is always counted, and when the reference count of an object becomes zero, it is released. The compiler often works to manage this reference count by outputting code that changes the reference count at every point where the pointer can increase or decrease. The disadvantage is that it tends to slow down the execution time because of the extra processing by the compiler and that it cannot be released once the object cycle is completed, i.e, a points to b, and b points to a.
If a points to b and b points to a, neither a nor b will have zero references forever.
To solve the shortcoming, an algorithm called deferred reference counting has been proposed. It distinguishes between pointers from the root (stack, registers, global variables) to an object and pointers from an object to an object, and records only the latter. Only objects that are not directly referenced by the root and have zero references are released.
Tracing GC
A method that continues to allocate until the heap is full, and then detects and frees all unused objects in the heap at once when it is full. It is based on the rule that:
objects pointed to by pointers from the root are not freed,
objects pointed to by pointers from objects that are not freed, are not freed,
and other objects are freed.
The good thing is that the classification is based on whether the object is reachable from the root, so it can be released even if it is a cycle. On the other hand, tracing GC recursively searches for and distinguishes objects that are reachable from the root by pointers, so it takes a long time to execute. The biggest disadvantage is that during GC, the execution of other programs stops. Mark-sweep GC, copying GC, etc. are the basic algorithms in tracing GC.
Many GCs classify each object into three colours. Specifically, they are
White: the colour of the object that is a candidate for memory freeing
Black: objects that are referenced by the root and not referenced by white objects. Not a candidate for memory release.
Gray: Objects that are referenced from the root but have not yet been scanned. Eventually, it will be a black object.
First, move the grey objects into the set of black objects. Move white objects that are referenced by objects referenced by the object to the grey ones. This prevents not only the object but also the objects referenced by it from being freed. Repeat until there is no more grey. Repeat this process until there is no more grey. Then the whole area will be black or white only. The advantage of this is that it can be done at the same time as the search, so no extra execution time is needed.
Mark-sweep GC
First, assign one bit of mark bit to each object. A single GC process consists of a mark phase for searching and a sweep phase for releasing the garbage area.
In the mark phase, the mark bits of all objects are set to 0 at the start of the GC, and the GC process starts from the root object and moves on to the reachable objects. The mark bits of all the objects in the heap are 0 when the GC starts, and the reachable objects from the root object are set to 1. Finally, the GC ends when all the objects are set to 0 or 1. C and C++ have Boehm GC developed as a library, which uses this mark-sweep algorithm.
mark(root):
if markbit(root):
markbit(root) = true
for every object referenced by root:
mark(object)sweep():
for every object in heap:
if markbit(object) = true:
markbit = false
else heap.release(object)
Copying GC
A typical example of Copying GC is Cheney’s algorithm, which uses breadth-first search. The heap is divided into two equal parts, and only one part is used first. When it is full, the GC is invoked, and the reachable (pointed to by the root) object is copied into the other heap (to-space), filling it up. After the copy is finished, the source heap (from-space) is no longer needed, and the program runs with the two heaps switching roles each time GC is performed. Specifically, for every reference in the stack that points to an object in from-space, if the object has not been moved to to-space, the copy is moved to to-space, and if the object has been moved to from-space, the copy is moved to from-space.
The advantage of Copying GC is that it does not cause fragmentation because it fills in the gaps when copying, but it requires extra information such as whether it is a pointer or not, etc. In mark-sweep GC, fragmentation may occur because the list structure of the memory area called free list is required in the sweep phase. Also, compared to manual free, where the time required is proportional to the number of garbage objects, copying GC is proportional to the number of live objects, so it may be faster to use GC than manual management.
initialize:
to_space = N/2
from_space = 0
//store where to allocate object when copy
alloc_pointer = from_space
//keep track of objects that are forwarded but not scanned
scan_pointer = from_spacecollect:
swap(from_space, to_space)
alloc_pointer = to_space
scan_pointer = alloc_pointer for every root in stack:
//root pointer points to copy of root
*root = copy(*root) //scan objects in the to-space
while (scan_pointer < alloc_pointer):
for every reference in children(scan_pointer):
*reference = copy(*reference)
//advance scan pointer to the next object
scan_pointer = scan_pointer + size(scan_pointer)copy(o):
//update root to the copied object address
if o is forwarded:
return forwarding_pointer
//o has no forwarding address
else:
new_address = alloc_pointer
//advance alloc pointer so it points to the next available spot
alloc_pointer = alloc_pointer + size(o)
copy o to new_address
forwarding_address = new_address
return forwarding_address
The advantage of Cheney’s algorithm is that it can reduce the amount of stack consumption because it is not recursive, and the amount of memory consumption is low because the heap is also a queue. There are other algorithms such as Multi-space copying GC, which divides the heap into N parts and performs Copying GC on two parts, Mark-sweep GC on the remaining N-2 parts, and Mark Compact GC, which combines Mark-sweep and Copying GC.
