참고자료
https://www.amazon.com/Garbage-Collection-Handbook-Management-Algorithms/dp/1420082795
http://www.cs.technion.ac.il/~erez/courses/gc/
https://v8.dev/blog/concurrent-marking
# Reference Counting
https://www.cs.technion.ac.il/~erez/courses/gc/lectures/08-reference-counting.pdf
( 이 내용은 CPython 문서를 참고했다. https://devguide.python.org/garbage_collector/ )
Reference가 추가 될 때마다 ref count를 증가시키고, Reference가 사라질 때 마다 ref count를 감소시킨다.
모든 Reference가 사라지면 count가 0이 되고 그 즉시 free 시킬 수 있다.
Cycle Detection
Cycle을 Detection하려면 모든 Reachable한 object를 Traversing하면서 count를 세야 한다.
( Jerryscript , CPython 에선 이런 방식을 쓴다. )
알고리즘
CPython에서는 모든 object에 ref count field가 사실 2개가 존재한다. 하나는 원래 존재하는 ref count field이고 다른 하나는 garbage collecting시 count를 감소시키기 위한 field이다.
또한 모든 object들은 linked list로 연결되어 있다. garbage collection traversing이 끝난 후 sweep 되어야 할 object는 이 linked list에서 빼낸 후 sweep 되어야 할 object끼리 같은 list에 넣는다.
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ +
| *_gc_next | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | PyGC_Head
| *_gc_prev | |
object -----> +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ +
| ob_refcnt | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | PyObject_HEAD
| *ob_type | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ +
| ... |1. gc 가 시작되면 reachable한 object를 Traversing하면서 reference마다 gc_ref를 감소시킨다.
2. Traversing을 하는 도중 gc_ref값이 0이 되는 object들은 gc_next, gc_prev linked list를 수정해 object list에서 꺼낸 후 sweep list에 넣어버린다. ( 아직 Traversing을 진행중이므로 곧바로 free 시킬 수는 없다. 왜냐하면 아직 visit되지 않은 object가 reference로 가리키고 있다면 다시 이 object가 Traversing이 되었는지 확인하러 값을 확인해야 하기 때문이다. 그래서 sweep list에 저장해 놓는다. )
3. Traversing이 끝나면 기존 object list를 돌면서 gc_ref 값을 ref count값으로 복구시켜준다. sweep list에 있는 object들은 모두 free시켜버린다.
# Cheney’s Mark-copy
http://www.cs.technion.ac.il/~erez/courses/gc/lectures/03-copying.pdf
우선 mark-copy를 하려면 Heap Object는 forwardPtr이라는 필드가 사용 가능해야 한다. 하지만 꼭 이걸 헤더에 부가적으로 추가할 필요는 없고 to space로 옮기고 난 후 ( grey가 되고 난 후 ) from space에 남겨진 곳에 type casting으로 forward ptr을 기록하면 된다. 어차피 옮기고 난 후 from space에 남은 object의 데이터들은 쓸모 없기 때문이다.
( Incremental, Concurrent Garbage Collection이 아닌 싱글 스레드 Cheney 알고리즘 자체는 gc-state에 3가지 색깔 값이 필요 없다. NOT_MOVED, MOVED 2 가지 상태면 충분하다 )
- Object.h
enum GC_STATE {
NOT_MOVED,
MOVED
};
class GCObject {
public:
GC_STATE gc_state;
};
class ForwardedObject : GCObject
{
public:
GCObject* forwardPtr;
};
class HeapObject : GCObject
{
public:
int type;
int size;
GCObject* fields[0];
};
- 알고리즘 ( BFS )
2개의 영역으로 분할한다. ( from space , to space )
1. 루트에서 direct로 reachable한 object들(root object들)의 gc-state를 MOVED로 표시 후 to space로 복사하고, 복사한 주사로 field를 update한다. 그리고 from space에 남겨진 object는(위 그림에서 B) ForwardedObject로 casting 한 이후 forwardPtr을 set한다. to-space로 이동한 객체는 worklist에 넣는다.
2. worklist에서 to-space에 있는 object들을 하나하나 꺼내 Reference가 가리키는 object를 모두 방문한다.
- 2-1 만약 gc state가 MOVED라면 ForwardedObject로 casting한 후 forwardPtr 값을 가져와 현재 reference 값을 update한다. 아래 그림에서 D의 경우 C에 대한 reference를 forward ptr을 이용해 update하는 모습이다.
- 2-2 gc state 가 NOT_MOVED 라면 gc-state를 MOVED로 바꾼 후 to-space로 복사하고, 복사한 to-space주소로 field를 update한다. from space에 남겨진 object는 ForwardedObject로 casting 한 이후 forwardPtr을 set한다. to-space로 이동한 객체는 next_worklist에 넣는다.
3. worklist 를 next_worklist로 바꿔치기 한다. ( worklist = next_worklist )
4. worklist가 empty일 때 까지 2~3을 반복
def flip(): # do transition from fromspace to tospace
fromspace, tospace < - tospace, fromspace
free < - tospace
def collect() atomic:
flip()
worklist = []
for fld in Roots:
process(fld, worklist)
while not isEmpty(worklist):
next_worklist = []
for object in worklist:
for fld in object:
process(fld, next_worklist)
work_list = next_worklist
def process(fld, worklist):
fromRef <- *fld
if fromRef->state == MOVED:
# renew field by forwarding-ptr .
*fld <- forwardingAddress(fld)
else:
# move to to-space and set field to new address. and then add it to worklist.
copied = copy(fld)
*fld = copied
worklist.add(copied)
def copy(fromRef):
# copy to to_space and return the address ( address in to_space )
toRef <- free
free <- free + size(fromRef)
move(fromRef, toRef)
forwardingAddress(fromRef) <- toRef
return toRef
- 알고리즘 ( scan, free )
BFS로 worklist를 사용하는 알고리즘은 worklist 크기가 너무 커질 수 있다. 그럴 땐 to-space의 scan 포인터를 이용해 구현할 수 있다.
1. root가 가리키는 object를 to-space의 free pointer 위치로 옮기고 object에 대한 reference를 해당 위치로 update한다. free는 object의 size만큼 update한다. [ free = free + size(object) ]
2. to space에 있는 scan 대상 object ( 아래 그림에서 A) 의 field를 하나하나 BFS 방식의 2.1 , 2.2에서의 작업을 동일하게 진행한다. 모두 옮기고 난 후 scan을 update 해준다 . [ scan = scan + size(scan object)].
3. free와 scan이 같아질 때 까지 2를 반복한다.
# Incremental Garbage Collection
http://www.cs.technion.ac.il/~erez/courses/gc/lectures/03-copying.pdf
https://v8.dev/blog/concurrent-marking
용어 정리
- Incremental Garbage Collection
Stop-The-World 대신 단계적으로 일부분만 garbage collecting하고 다시 Application의 실행을 허용한다.
- Tri Color Abstraction
Black : field들이 참조하는 모든 object들이 Grey 혹은 Black( to-space 로 넘어간 )인 object. Black 역시 to-space에 있다.
Grey : Grey로 Marking 되었지만 ( to-space로 넘어왔지만 ) field가 참조하는 object들은 일부만 Grey 이거나 하나도 Grey가 아닌 상태.
White : 아직 Grey로 Marking 되기 전( to-space로 넘어가지 않은)인 상태
앞으로의 내용은 marking 단계에서 from-spac에서 to-space로 보낼 때 grey worklist를 사용한다고 가정하자. 그리고 grey worklist 에서 grey object를 하나씩 빼내서 참조들을 grey로 바꾼 후 ( grey worklist에 넣은 후 ) 처음에 빼 내었던 grey object는 black으로 바꾼다고 하자.
Black to White Reference 문제와 Write Barrier
- Black to White Reference
아래와 같이 A가 B를 참조하는 상황에서 B를 grey로 변경시켜 놓고 A를 Black으로 바꿔놓았다고 해보자. 따라서 A는 grey worklist에서 빠져나왔고 B는 grey worklist에 들어가 있다.
이 상태에서 Application이 실행 되어 B->C 로의 참조가 삭제되고 A->C 로의 참조가 추가되었다. 이런 상태면 C는 tracing 되지 못하고 from-space에 덩그러니 남아있게 된다.
- Write Barrier
이를 Write Barrier로 해결한다.
어떤 object에 값을 쓸 때 object가 black 상태이고 write할 value가 white라면 그 즉시 바로 grey로 바꿔버리고 worklist에 넣어버린다. 그러면 white object가 tracing되지 못할 일은 없다.
// Called after `object.field = value`.
write_barrier(object, field_offset, value) {
if (color(object) == black && color(value) == white) {
set_color(value, grey);
marking_worklist.push(value);
}
}다른 방법으로는 Black을 다시 Grey로 바꿔버리고 다시 worklist에 집어 넣어 버리는 방법도 있다.
Read From-Space 문제와 Read Barrier
- Read From-Space 문제
이미 To-Space로 이동한 B를 C가 참조하고 있는 상황이라고 하자. 이때 To-Space로 넘어간 B의 Value field값을 1로 바꾼 후 C가 B의 Val값을 읽으면
C-> (FromSpace) B -> Val = 4 값을 읽어오게 된다. To-Space에 있는 진짜 B의 Val field 값은 1인데 이상한 값을 읽는 것이다.
- Read Barrier
이런 경우 ReadBarrier에서 즉시 field를 우선 to-space값으로 update해주고 grey worklist에 현재 object를 넣어버린다.
read_barrier(object, field_offset) {
target = object[field_offset]
if (color(object) == white && color(target) != white) {
object[field_offset] = object[field_offset] -> forwardedPtr;
set_color(object, grey);
marking_worklist.push(object);
}
}
# Generational Garbage Collection
https://www.cs.technion.ac.il/~erez/courses/gc/lectures/04-generations-train.pdf
https://segmentfault.com/a/1190000040681316/en
http://psy-lob-saw.blogspot.com/2014/10/the-jvm-write-barrier-card-marking.html
Young Generation, Minor GC & Old Generation, Major GC
대부분의 Object는 잠시동안 local variable로 쓰이는 등 곧바로 reference를 잃어 버려 가비지 컬렉팅 대상이 된다. 따라서 오랫동안 살아있는 Object를 따로 분리시켜 새로 생성된 Object만을 대상으로 Garbage Collecting을 한다면 훨씬 효율적으로 Garbage Collection을 할 수 있다.
대부분의 Object는 잠시동안 local variable로 쓰이는 등 곧바로 reference를 잃어 버려 가비지 컬렉팅 대상이 된다. 따라서 오랫동안 살아있는 Object를 Old Generation로 따로 분리시킨 후 새로 생성된 Object만(Young Generation)을 대상으로 Garbage Collecting을 한다면 훨씬 적은 수의 Object만 다뤄도 된다. Young Generation를 대상으로 Garbage Collecting하는 걸 보통 Minor GC라 부른다. Old-Generation를 Garbage Collecting할때는 항상 Young-Generation역시 같이 Garbage Collecting하며 이를 보통 Major GC라 부른다. ( *Old-Generation를 GC할때 Young-Generation도 함께 GC하면 이후에 보게될 Write Barrier와 Remembered Set에서 Old-To-Young Reference만 다루면 된다. )
Old to Young Reference 문제와 Write Barrier
- Minor GC에서의 Old to Young Reference 문제
Young Generation만 Garbage Collecting하면 Old-Generation에 있는 Object가 Young-Generation에 있는 Object를 가리킬때 Pointer가 갱신되지 않는 문제가 발생한다. 같은 Young-To-Young Reference는 Minor GC가 Reachable한 Object를 Grey에서 Black으로 바꾸면서 모두 갱신해주기 때문에 신경쓸 필요 없다. 하지만 Old-Generation에 있는 Reference는 Minor GC가 Scan자체를 하지 않으므로 갱신해줄 수 없다. (*Stack Variable은 항상 GC Root 취급이므로 신경쓸 필요 없다. Minor GC이든 Major GC이든 GC Root들은 최우선 Scan대상이다. 따라서 오직 Old-To-Young Reference 만 다루면 된다. )
이런 문제는 Write Barrier에서 Remembered Set, Card Marking을 활용해 해결한다.
- Remembered Set
Remembered Set은 Old-To-Young Reference를 기록하는 테이블이다. Write Barrier에서는 Old Generation Object의 Field에 Young Generation Reference가 Write되면 해당 정보를 Young-Generation의 Remembered Set에 기록한다. Minor GC는 Young-Generation에 있는 Remembered Set을 마치 GC Root처럼 취급하게 되는데 Set에 들어있는 Field가 가리키는 Young-Generation Object를 모두 Grey로 만들면 된다.
// Called after `object.field = value`.
write_barrier(object, field_offset, value) {
if (isOld(object) && isYoung(value) ) {
addToRememberedSet(value, object);
}
}
정보를 기록하는 방법은 2가지가 있는데 첫번째는 Table의 Set에 Field의 주소값을 넣는 방법이다. 이 방식은 모든 Old-To-Young Reference를 Write 할 때마다 Remembered Set에 field를 추가해야 한다.
두번째 방법은 Object의 Field의 주소가 아니라 Object자체를 Remembered Set에 기록하는 방법이다. 이 경우 Old Generation Object의 헤더의 Remembered Bit을 이용해 이미 그 Object가 한번 Remembered Set에 들어갔다면 그 다음부턴 Set에 들어있는지 확인하는 작업을생략할 수 있다.
- Card Marking
Object의 Field나 Object를 Set에 저장해놓는 Remembered Set 방식과는 달리 Card Marking은 메모리 공간을 위한 Dirty Bit를 사용한다. Old-Generation의 메모리를 조금 더 작은 Block단위로 나눈 후 Old-To-Young Reference가 발생할 때 마다 Old Object가 속한 블록에 해당하는 Dirty Bit를 Set한다. Minor GC는 Young-Generation의 Object들을 모두 처리한 후 Dirty Bit가 Set된 Old Generation의 Block들을 다시 Scan해 reference들을 갱신해준다.
Remembered Set을 사용하는 방법과 비교하면 Set에 Object나 Field 주소를 집어 넣는 작업을 하지 않고 Bit Set작업 하나로 끝나므로 Write Barrier 오버헤드가 적다. 하지만 Dirty Bit Table전체를 확인하면서 어떤 어떤 Block이 Dirty한지 확인해야 하고, 만약 어느 Block이 Dirty하다면 그 블록을 전부 Scan해야 하는 오버헤드가 있다.
// Called after `object.field = value`.
write_barrier(object, field_offset, value){
if (isOld(object) && isYoung(value)) {
setDirtyBit(dirty_card, getBlockIndex(getBlockAddr(object)));
}
}
Multi Region Garbage Collection
아래와 같이 여러 Region이 존재하는 환경을 고려해 보자. 이 Region들은 모두 따로 Garbage Collection을 수행한다. 따라서 모든 다른 Region 끼리의 참조는 Region 각각의 Garbage Collector에서 모두 해결해줘야 한다. 예를들어 Region A의 GC가 동작할 때 Region B-> Region A, Region C -> Region A 참조 들을 모두 갱신해줘야 한다.
- Remembered Map for Card Table
이런 환경에서는 Remembered Set이 Object의 주소나 Object Field주소를 저장하는게 아니라 각 Region의 Card Table의 인덱스를 저장한다. Remembered Set은 Map형태로 존재하게 되는데 Region이 Key이고 Map의 Value는 해당 Region의 Card Table 인덱스들의 Set이다. 예를들어 아래 그림에서 Region A의 Remembered Map은 Region B 를 Key로 넣으면 Region B의 Card Table을 위한 Index들의 Set이 존재한다.
( Index Set에 Index를 추가하는 방법은 느린 방법이다. 더 빠른 방법은 Region A에서 다른 Region들을 위한 Card Bit Table들을 유지하면서 Bit를 표시하는 방법이다. 마찬가지로 다른 Region들 역시 자신을 제외한 다른 Region들을 위한 Card Bit Table을 유지하면 된다. )
Multi Region 환경에서는 여러 Region에서 Card Table을 사용하기 때문에 Young Generation/ Old Generation에서 처럼 Old Generation 전용 Card Table 하나로는 이런 환경을 충족시킬 수 없고 이처럼 각 Region별로 다른 모든 Region을 위한 Card Table Index Set을 유지해야 한다.
'Programming & Etc' 카테고리의 다른 글
| Garbage Collection 알고리즘 - 1 (0) | 2021.12.31 |
|---|---|
| Java synchronized 키워드와 Memory Barrier (3) | 2021.11.03 |
| Git Internal (0) | 2021.11.02 |
댓글