Io Garbage Collection
Io uses a colored garbage collector, which is an incremental garbage collector, based on Djikstra's three-color algorithm.
Djikstra's three-color algorithm
Io uses Djikstra's three-color algorithm to implement its garbage collection. Here is an excerpt that sums up well what this algorithm does:
Djikstra's three-color algorithm. In this algorithm, at any given time, every object is either Black, Grey or White. Black designates objects which may or may not be reachable, until we finish enumerating all reachable objects, at which point it designates garbage objects. White designates objects which are known to be reachable, and which don't point to any Black objects. All other objects are Grey.
Object mark
An object mark indicates the "color" of an object, regarding to garbage collection.
The IoObject?_mark (from IoObject?_inline.h) marks an objects, which means that :
- If it is white, it will be gray
- If it is gray, it will be black
Every object Tag contains a markFunc pointer that references a function that should mark the content of the object when the ob ject itself is marked.
Basically, the most important functions are located in the IoState?_collector.c file, where the three following functions allow to change an object color by moving it from one group to another : IoState?_makeGrayFromWhite_, IoState?_makeGrayFromBlack_ and IoState?_makeBlackFromGray_
A collector cycle
At first, the lobby is "grayed", which means that every object it contains is also grayed. Then the permanently retained values (IoState?->retainedValues) are also "grayed".
Then the "gray" objects are marked (IoObjectGroup?_markValues), and eventually the "white" objects are freed (IoObjectGroup?_freeValues).
This is rather simple, but it is important to ensure that all referenced objects get marked during a cycle, otherwise they will be freed.