# Embedded System Final Project - Garbage Collection in Real-time Systems

{%hackmd BJrTq20hE %}

> - Garbage collection on [wiki](https://en.wikipedia.org/wiki/Garbage_collection_(computer_science))

> - Project proposal slides [(link)](https://docs.google.com/presentation/d/1Rev3IbtzkR6yQMpXJXWzWYfV0zfPm-K36ZU40cd-zDc/edit?usp=sharing)
> - Project presentation slides ([link](https://docs.google.com/presentation/d/1Z6PaCcJMwZdO32B5I5pLHhx5Ro4I1W7ZV5vNBq21QRM/edit?usp=sharing))
> - Project Demo ([link](https://ncku365-my.sharepoint.com/:f:/g/personal/p76091624_ncku_edu_tw/ElvwQ5Q-M3pDqC7tO3aTG38BIA71C7-BLqs9ZkkEJ493mw?e=BgumRA))
## Garbage Collector Basics
**Garbage collector:** a dynamic storage allocator that automatically frees allocated blocks that are no longer needed by the program.

The following is reachability graph:
**Root nodes** correspond to locations not in the heap that contain **pointers** into the heap, like **registers**, **local** or **global variables**.

Garbage collectors for languages like Java, which exert tight control over how applications create and use pointers, can maintain an exact representation of the reachability graph and thus can reclaim all garbage.

However, collectors for languages like C and C++ cannot in general maintain exact representations of the reachability graph. Such collectors are known as **conservative garbage collectors**. They are conservative in the sense that each reachable block is correctly
identified as reachable, while some unreachable nodes might be incorrectly identified
as reachable.

### When does GC work?

Collectors can provide their service **on demand**, or they can run as separate threads **in parallel with the application**, continuously updating the reachability graph and reclaiming garbage.

For example, consider how we might incorporate a conservative collector for C programs into an existing `malloc` package, as shown in the figure below:

- The application calls `malloc` in the usual manner whenever it needs heap space. If `malloc` is unable to find a free block that fits, then it calls the garbage collector in hopes of reclaiming some garbage to the free list.

- The collector identifies the garbage blocks and returns them to the heap by calling the `free` function. The key idea is that **the collector calls free instead of the application**.

- When the call to the collector returns, `malloc` tries again to find a free block that fits. If that fails, then it can ask the operating system for additional memory. Eventually, `malloc` returns a pointer to the requested block (if successful) or the `NULL` pointer (if unsuccessful).


## Mark & Sweep Garbage Collectors


Two phases: **mark** and **sweep**
- mark: calls the `mark` function once for each root node

    /* typedef void *ptr ptr.
     * int blockMarked(ptr b). Returns true if block b is already marked.
     * ptr isPtr(ptr p). If p points to some word in an allocated block, 
     * it returns a pointer b to the beginning of that block; otherwise returns NULL .
     */
     
     /* psuedo code */
    void mark(ptr p) {
        if ((b = isPtr(p)) == NULL)
            return;
        if (blockMarked(b))
            return;
        markBolck(b);
        len = length(b);
        for (int i=0; i < len; i++)
            mark(b[i]);
        return;
    }

- sweep: call `sweep` function after finishing marking all reachable blocks

    /* int blockAllocated(ptr b). Returns true if block b is allocated. */
    
    /* psuedo code */
    void sweep(ptr b, ptr end) {
        while (b < end) {
            if (blockMarked(b))
                unmarkBlock(b);
            else if (blockAllocated(b))
                free(b);
            b = nextBlock(b);
        }
        return;
    }

### "Conservative" Mark & Sweep for C Programs
There are some interesting challenges for the implementation of the `isPtr` function:

1. C does not tag memory locations with any type information. Thus, there is no obvious way for `isPtr` to determine if its input parameter `p` is a pointer or not.
2. Even if we were to know that `p` was a pointer, there would be no obvious way for `isPtr` to determine whether `p` points to some location in the payload of an allocated block.

> What is payload?

**A solution to the latter problem:**

Maintain the set of allocated blocks as a **balanced binary search tree** that maintains the invariant that all blocks in the left subtree are located at smaller addresses and all blocks in the right subtree are located in larger addresses.

This requires two additional fields (left and right) in the header of each allocated block, as shown in the figure below. Each field points to the header of some allocated block. The `isPtr(ptr p)` function uses the tree to perform a **binary search** of the allocated blocks. At each step, it relies on the size field in the block header to determine if p falls within the extent of the block.


The fundamental reason that Mark & Sweep collectors for C programs must be conservative is that the C language does **NOT tag memory locations with type information**. Thus, scalars like `ints` or `floats` can masquerade as pointers.

For example, suppose that some reachable allocated block contains an `int` in its payload whose value happens to correspond to an address in the payload of some other allocated block `b`. There is no way for the collector to infer that the data is really an `int`, not a pointer. Therefore, the collector must conservatively mark block `b` as reachable, when in fact it might not be.

### References
- Randal E. Bryant and David R. O'Hallaron. "Computer Systems: A Programmer's Perspective, 3/E".
- Ordinary garbage collector [(jserv/ogc)](https://github.com/jserv/ogc/tree/master/src)
- Garbage Collection 垃圾回收機制，從保守到精準。[(hackmd)](https://hackmd.io/@hPMCWajOS-ORQdEEAQ04-w/ryXx6FDcV#Precise-Garbage-Collector)
- Garbage collector [(hackmd)](https://hackmd.io/@RinHizakura/HyEt1kcSd#Garbage-collector)
- Dynamic Memory Allocation in the Heap [(pdf)](https://cs.wellesley.edu/~cs240/f16/slides/allocator.pdf)

## Baker's Treadmill Algorithm

**Abstract**
* A simple real-time garbage collection algorithm is presented which **does not copy**, thereby **avoiding some of the problems caused by the asynchronous motion of objects**.
* This in-place "treadmill"garbage collection scheme **has approximately the same complexity as other non-moving garbage collectors**, thus making it **usable in a high-level language implementation where some pointers cannot be traced**.

**Introduction**

* **The tricolor marking scheme** and **the use of the allocation pointer as a clock** to measure the "time" until the garbage collection must be finished.

:::info
【Copying GC】[(link)](http://www.cs.cornell.edu/courses/cs312/2003fa/lectures/sec24.htm)
1. It was **space-efficient**, which appeared to be important for an embedded computer with all "real" (non-virtual) memory
2. It **compacted by copying**, which allowed for the simplest allocation strategy—pointer incrementation
3. It had a **single phase**, unlike the 2-phase mark-sweep algorithm.
:::

:::warning
【learn a lesson】
* Compile-time garbage collection should be used whenever possible.
* Stack allocation should be used more often.
* Functional objects should be treated differently from non-functional objects.
* Depth-first copying often causes fewer faults in a virtual memory and/or caching environment.
* The asynchronous movement of objects is detrimental to compiler optimization.
* A **"conservative" garbage collector** works much better without copying, since it can never be sure that all pointers to an object have been found andupdated.
:::
### Tricolor marking


**Procedures**

We use 3 colors to mark the nodes of a rooted directed graph—**white**, **grey** and **black**.
1. At the commencement of marking, all the nodes are white.
2. Mark the root nodes grey.
3. Find a grey node, darken (color grey) all of the nodes it points to, and then blacken it.
4. Repeat **step 3** until there are no grey nodes.
5. When marking is done, we interchange the interpretation of the colors white and black (at this point there are no grey cells), mark the roots grey, and then restart the algorithm.

**What is mutator?**

Basically, it represents user program
> Cited from [here](https://stackoverflow.com/questions/61850560/why-is-the-user-program-called-mutator-in-the-context-of-garbage-collection):
>
> The heap is constantly changing or in simple words - it is constantly "mutated". Your application is to be blamed for this, it requests new chunks of memory all the time throughout its entire lifetime.

### In-place garbage collection

:::warning
【Requirements of tricolor marking】
1. it is easy to enumerate free cells for allocation
2. it is easy to enumerate grey cells
3. it is easy to determine the color of a cell
4. it is easy to changethe color of a cell
5. it is easy to interchange the interpretation of the colors white and black.
:::
> ***Doubly-linked lists*** satisfy these requirements.

**Initialize**
* `free-list`: a doubly-linked list.
* `non-free-list`: a doubly-linked list.

When a cell is allocated ("consed"), it is removed from the `free-list`, and inserted into the `non-free-list`.

**tricolor marking example**

:::info
【non-real-time system】
1. Marking **begins** when the `free-list` becomes empty.
* All cells are on the `non-free-list` at this point ( all cells are white )
2. Marking begins by making the root cells grey
* transferring the root cells from the `white list` to a `grey list`
3. Marking proceeds by unsnapping cells from the `grey list` and snapping them into an initially empty `black list`.
4. The algorithm will **terminate** with:
1. all accessible cells on the `black (non-free) list`
2. all inaccessible cells on the `white (free) list`.
5. Interchange the interpretation of white and black.
> It means that in the begining of marking (step 1), cells in non-free list are all **white**.
>
> After step 2-4, cells in non-free list should be all **black** because **black** cells are reachable from root set and they are need to be freed.
>
> Therefore, for speed and simplicity, the collector doesn't need to move or recolor any cell; instead it just reinterprets the black to mean white, and vice versa.

6. The mutator continues.
:::

【real-time system】

- [ ] The mutator is never allowed to see a white node.
* If the mutator attempts to access a white cell, it first darkens it
* unsnapping it from the `white list` and snapping it into the `grey list`

- [ ] The real-time system will require ==four colors==
* since **unmarked white cells** must be distinguished from cells on the `free list`
* unmarked white cells must use "off-white"(**`ecru`**) instead of the "dead white"
- [ ] At the end of marking, the ecru cells are converted to dead white cells to form the new free list

:::success
It is easy to see that this "in-place" algorithm is **real-time**
* since **the basic operations are all constant-time operations**.
> determining a cell's color, changing a cell's color (including unsnapping and snapping its links), etc.
:::

### The Treadmill Optimization

==linking all the cells into the same large cyclic doubly-linked list==


There are 4 pointers, `bottom`, `top`, `free` and `scan`, delimiting 4 segments, white, grey, black and ecru. ( Define clockwise as forward, and counter-clockwise as backward )
- The `new` list is where allocation of new objects occurs during garbage collection.
- allocation by moving `free` pointer "forward"
- color: **black** ( reachable and scanned )
> scanned means it has finished visiting its offspring.
- At the beginning of garbage collection, the `new` list is empty.
- The `from` list holds objects that were allocated before garbage collection began and which are subject to garbage collection.
- allocation by moving `bottom` pointer "backward"
- color: **ecru** ( unreachable )
- The `to` list holds reachable objects.
- objects are unsnapped (unlinked) from the `from` list and snapped into the `to` list
- color: **black** or **grey** ( reachable but not scanned )
- At the beginning of garbage collection, the `to` list is empty.
- The `free` list holds free blocks.
- color: **white**
- When the cell under the `scan` pointer has been scanned, the `scan` pointer is moved "backward", thus changing a grey cell into a black cell.
- When no more grey objects, i.e. `scan` = `top`, GC is complete. Finally, reclaim garbages by moving `bottom` pointer "forward".

### Costs

- [ ] allocation is no longer a simple pointer-increment operation, but a search of a `free-list` for an amount of storage big enough to satisfy the allocation.
* the free-list must be searched if objects of different sizes are managed
* the in-place algorithm appears to be most useful when managing a homogeneous collection of objects

**solution**
1. **first-fit** technique for managing storage in which allocation could be performed in $O(log(w))$
> $w$ is the maximum number of words allocated dynamically.

### References
- The Treadmill: Real-Time Garbage Collection Without Motion Sickness [(paper)](https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.23.5878&rep=rep1&type=pdf)
- Uniprocessor Garbage Collection Techniques [(paper)](https://www.cs.cmu.edu/~fp/courses/15411-f08/misc/wilson94-gc.pdf)
- An Implementation of Baker's Treadmill Garbage Collector [(txus/libtreadmill)](https://github.com/txus/libtreadmill)
- Golang’s Real-time GC in Theory and Practice [(animation)](https://making.pusher.com/golangs-real-time-gc-in-theory-and-practice/)
- Baker's Treadmill collector - A non-moving collector [(pdf)](https://www.rose-hulman.edu/class/csse/csse490-dsr/200910/Slides/TreadmillGC.pdf)