Garbage collection
void foo() {
int *p = malloc(128);
return; /* p block is now garbage */
}위 코드에서 p는 stack에 할당되어있고, malloc(128)은 heap에 할당되어 있다.
이 함수가 return 되면 heap에 할당되어 있는 malloc(128)은 어느 변수도 참조하지 못하는 Garbage가 된다.
이러한 Garbage를 자동으로 free 시켜주는 것을 Garbage collection이 한다.
C에서 Garbage Collection을 구현하려면 몇 가지 어려움이 존재한다.
- memory가 언제 free 되는가?
- 조건에 따라 달라지기 때문에 일반적으로 미래에 어떤 것이 사용될지 알 수 없다.
- 그러나 특정 Block에 대한 Pointer가 없으면 사용할 수 없다는 것을 알 수 있다.
Block에 대한 Pointer가 없다는 정보를 가지고 Garbage Collection을 구현할 수 있다.
구현하기 위해 몇 가지 가정이 있다.
- Memory manager가 pointer인지 아닌지 구분할 수 있다.
- 모든 Pointer는 block의 시작을 가리킨다.
- Pointer를 숨길 수 없다. (Type casting X)
Classical GC Algorithms
Memory as a Graph
- Memory => Directed Graph
- 각 Block은 그래프의 Node다.
- 각 Pointer는 그래프의 edge다.
- Heap에 대한 Pointer를 포함하고 Heap에 있지 않은 것을 Root Node라고 한다.
(registers, locations on the stack, global variables)
Mark and Sweep Collecting
- 할당할 공간이 없을 때까지 malloc하여 메모리 할당한다.
- 할당할 공간이 없을 때:
- 각 block의 head에 있는 mark bit를 사용한다.
- Mark: root에서 시작하여 reachable block에 mark bit를 set 한다.
- Sweep: 모든 block을 스캔하고 mark 되지 않은 block을 free 한다.
Assumptions For a Simple Implementation
- Application
- new(n): Heap에 있는 block을 할당하고 block에 대한 pointer를 반환한다
- read(b, i): b block에서 i번째 해당하는 값을 읽어서 register로 넣는다.
- write(b, i, v): b block의 i번째에 v를 쓴다.
- 각 block은 header word를 가진다.
- block b[-1]에 위치한다.
- collector에서 여러 목적으로 쓰인다.
- Garbage Collector에 사용되는 함수들
- is_ptr(p): p가 pointer인지 값인지 판단
- length(b): header를 제외한 block b의 길이
- get_roots(): root를 반환한다.
Mark bit set
ptr mark(ptr p) {
if (!is_ptr(p)) return; // do nothing if not pointer
if (markBitSet(p)) return; // check if already marked
setMarkBit(p); // set the mark bit
for (i=0; i < length(p); i++) // call mark on all words
mark(p[i]); // in the block
return;
}Sweep
ptr sweep(ptr p, ptr end) {
while (p < end)
if markBitSet(p)
clearMarkBit();
else if (allocateBitSet(p))
free(p);
p += length(p);
}Conservative Mark & Sweep in C
- is_ptr() 함수는 pointer가 memory의 allocated block을 가리키고 있는지 확인함으로써
word가 pointer인지 아닌지 결정한다. - 그런데 C에서 Pointer가 block의 중간을 가리킬 수 있다.
- block의 시작을 어떻게 찾을 수 있는가?
- Balanced binary tree를 사용하여 모든 allocated block을 추적할 수 있다.
- Balanced-tree의 pointer는 header에 저장될 수 있다.
- Left와 Right는 무조건 Pointer라고 가정하고 시작한다.
- 각각의 Pointer를 쫓아가는데 그 Block이 allocated block이라고 가정한다.
- mark 하고 sweep 할 때 allocated 기 때문에 free를 안 한다.
- 실제 가리키고 있는 block이 할당이 안되어 있지만, 할당되었다고 가정하기 때문에
Garbage collecting을 안 하기 때문에 메모리 누수가 발생할 수 있다.
