[WEEK07] 가비지 컬렉션과 메모리 관련 오류들

Garbage Collection

• Garbage Collection(이하 GC)는 heap에서 할당된 저장공간의 자동화된 회수이다: 응용프로그램은 free를 해 줄 필요가 없다
• 파이썬, 루비, 자바 등 많은 동적 언어에서 사용한다.
• C나 C++에도 보수적인Conservative GC 비슷한 무언가가 있지만 모든 garbage를 collect하지는 못한다.
• 묵시적 메모리 관리자는 어떻게 메모리가 free될 수 있는지 알 수 있을까?
  • 일반적으로 우리는 미래에 어떻게 될지 알지 못한다.
  • 하지만 우리는 특정한 블록이 연결된 포인터가 없다면 사용되지 않을 것이라는 것을 알 수 있다.
• 포인터에 대해 특정한 추측을 해야 한다.
  • 메모리 관리자는 포인터와 non-pointer를 구분할 수 있다.
  • 모든 포인터들은 블록의 시작을 가리킨다.
  • 포인터를 숨길 수 없다.

메모리를 그래프로 표현하기

• 우리는 메모리를 directed graph로 볼 수 있다.
  • 각 블록은 그래프의 노드가 된다.
  • 각 포인터는 그래프의 에지가 된다.
  • 힙으로의 포인터를 포함하는 힙 외부의 공간들을 root 노드라고 한다. (예: 레지스터, 스택 상의 공간, 전역변수 등)
  • 노드(블록)이 어떤 노드에 연결되어 있다면 reachable하다.
  • Non-reachable 노드들은 garbage다.

Mark and Sweep Collecting

• malloc/free 패키지 위에서 빌드할 수 있다: space 밖으로 나갈 때까지 malloc을 사용해서 할당한다.
• space 밖으로 나갈 때:
  • 각 블록의 헤드에 추가적인 mark bit를 사용한다.
  • Mark : root에서 시작해 각 reachable 블록에 mark bit을 set한다.
  • Sweep : 모든 블록을 스캔해서 mark되지 않은 블록들을 free한다.

단순한 구현을 위한 가정

• 응용프로그램
  • new(n) : 모든 장소가 clear된 상태에서 새로운 블록을 가리키는 포인터를 return한다.
  • read(b, i) : 레지스터 내의 블록 b의 주소 i를 읽는다.
  • write(b, i, v) : 블록 b의 주소 i에 v를 쓴다.
• 각 블록은 헤더 워드를 가진다.
  • 블록 b에 대해서 b[-1]의 주소를 가진다.
  • 각 collector에서 각각 다른 목적으로 사용한다.
• GC에서 사용되는 인스트럭션
  • is_ptr(p) : p가 포인터인지 결정한다.
  • length(b) : 헤더를 제외한 블록 b의 길이를 return한다.
  • get_roots() : 모든 root들을 return한다.
• 메모리 그래프에서 DFS를 사용해 mark하기

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;
}

• 다음 블록을 찾기 위해 length를 사용해 sweep하기

ptr sweep(ptr p, ptr end) {
   while (p < end) {
      if markBitSet(p)
      	clearMarkBit();
      else if (allocateBitSet(p)) 
         free(p);
      p += length(p);
}

C에서의 보수적인 Mark & Sweep

• C 프로그램을 위한 "보수적인conservative GC"
  • is_ptr()은 한 워드가 포인터인지를 그것이 메모리에서 한 할당된 블록을 가리키는지 확인함으로써 결정한다.
  • 하지만 C 포인터는 블록의 중간을 가리킬 수도 있다.
• 그래서 어떻게 블록의 시작을 찾을래?
  • 모든 할당된 블록들을 추적하기 위해 균형 이진 트리를 사용할 수 있다. (키는 블록의 시작)
  • 균형 트리 포인터는 헤더에 저장될 수 있다. (2개의 추가적인 워드를 사용해야 함)

---

Memory-related perils and pitfalls

• 나쁜 포인터 참조 해제
• 초기화되지 않은 메모리 읽기
• 메모리 덮어쓰기
• 존재하지 않는 변수 참조
• 블록을 여러 번 해제하기
• 자유 블록 참조
• 블록을 해제하지 못함

메모리 버그들을 다루는 방법

• 디버거 (gdb)
• 일관성 체커 자료구조 사용
• 이진 번역기 (valgrind)
• glibc malloc은 확인 코드를 포함한다: setenv MALLOC_CHECK_3