Dalvik VM: Precise GC or Conservative GC ?
Dalvik VM이 garbage collection을 하는 과정 중 모든 thread의 stack frame을 뒤져서 레지스터가 가리키는 객체들을 marking한다. (marking한다는 것은 이 객체가 살아있으므로 GC하지 않겠다라고 표시하는 것이라고 알아두자. 더 자세한 내용은 추후 다른 글에서 다루어보도록 하자)
위 그림을 보면서 이해해보도록 하자. Thread는 curFrame에 현재 stack frame 주소를 가지고 있다. stack frame은 register 값들을 저장하고 있는데 위 그림에서는 rvalue라고 표현하고 있다. 레지스터는 object에 대한 reference를 가지고 있을 수 있다. 이 경우 해당 object는 현재 사용되고 있는 것이므로 GC 과정에 없어지지 않도록 살아있음을 표시하는 marking을 한다. 이 그림에서는 object에 직접 marking하는 것으로 표현하고 있지만 실제로는 HeapBitmap이라고 하는 bit vector에 marking한다.
Register에 저장된 값이 object에 대한 reference인지 아니면 다른 값 (예를 들면, 상수 값) 인지 어떻게 판단할 수 있을까? 이 판단 방법에 따라 Precise GC 혹은 Conservative GC의 구분이 이루어진다.
Precise GC란 어떤 방법에 의해서든 object에 대한 reference 값을 정확하게 파악하여 잘못된 marking이 이루어지지 않게 하는 방법이다. 이와 달리 Conservative GC는 레지스터의 값의 패턴을 대충 파악하여 이 값이 object reference로 판단할만하면 marking하는 방식이다. 그러므로, 레지스터 값이 object에 대한 reference가 아닌데도 잘못 marking하는 경우가 생길 수 있다.
Dalvik VM은 위 코드와 같이 register의 값(rval)이 0이 아니고 하위 2 bits의 값이 0이면 이를 object에 대한 reference로 가정하고 marking을 시도한다. 이런 방식으로 동작해도 실제 GC 과정에는 별로 문제가 없다고 한다. 물론, 잘못된 영역을 marking해서 쓰레기로 처리되어야 할 object가 살아남는 경우도 발생할 수 있지만 별로 문제시 삼지않는다. (Android Platform Group에서 논의된 내용을 참고하시길)
현재 최신 버전의 Dalvik VM은 precise GC도 지원하는 것으로 보인다. 이를 위해 code verification 과정 중에 RegisterMap이라는 정보를 만들어낸다. RegisterMap은 method가 실행 시 특정 시점에 레지스터가 가진 값이 object에 대한 reference인지 나타내는 비트 값을 가진다. (Java의 StackMap과 유사한 개념이다.) 간단한 예를 들어보자.
int i = 10;
int a = i + 10; // (1) 0 0 0 0 0 0 0 0
SomeObject p = new SomeObject ();
callSomeMethod(p); // (2) 1 0 0 0 0 0 0 0
위와 같은 코드가 현재 callSomeMethod(p)까지 실행 중이다. 레지스터는 8개가 있다고 가정하자. (1)번 주석은 해당 라인의 코드가 실행될 때의 RegisterMap 값이다. 모든 비트가 0으로 이 stack frame의 레지스터 값은 object에 대한 reference가 하나도 없음을 알 수 있다. (2)번 주석의 경우는 1개의 비트가 1로 첫 번째 레지스터의 값이 object에 대한 reference임을 알 수 있다.
이처럼 precise GC를 처리하면 실행 성능에는 큰 차이가 없으나 엉뚱한 object를 marking하는 문제를 없앨 수 있다. 또한, compaction과 같은 발전된 GC 기능을 구현하기 위해서는 꼭 구현되어야 할 기능이다. 하지만, RegisterMap 정보를 추가적으로 만들어내므로 DEX 파일의 크기가 약 9% 정도 커지므로 주의하도록 한다.
Dalvik VM을 실행 시 -Xgenregmap 옵션을 지정해주면 code verification 과정 중에 dvmGenerateRegisterMapV 함수를 호출하여 RegisterMap을 생성한다.
참고자료:
위 그림을 보면서 이해해보도록 하자. Thread는 curFrame에 현재 stack frame 주소를 가지고 있다. stack frame은 register 값들을 저장하고 있는데 위 그림에서는 rvalue라고 표현하고 있다. 레지스터는 object에 대한 reference를 가지고 있을 수 있다. 이 경우 해당 object는 현재 사용되고 있는 것이므로 GC 과정에 없어지지 않도록 살아있음을 표시하는 marking을 한다. 이 그림에서는 object에 직접 marking하는 것으로 표현하고 있지만 실제로는 HeapBitmap이라고 하는 bit vector에 marking한다.
Register에 저장된 값이 object에 대한 reference인지 아니면 다른 값 (예를 들면, 상수 값) 인지 어떻게 판단할 수 있을까? 이 판단 방법에 따라 Precise GC 혹은 Conservative GC의 구분이 이루어진다.
Precise GC란 어떤 방법에 의해서든 object에 대한 reference 값을 정확하게 파악하여 잘못된 marking이 이루어지지 않게 하는 방법이다. 이와 달리 Conservative GC는 레지스터의 값의 패턴을 대충 파악하여 이 값이 object reference로 판단할만하면 marking하는 방식이다. 그러므로, 레지스터 값이 object에 대한 reference가 아닌데도 잘못 marking하는 경우가 생길 수 있다.
Dalvik VM은 위 코드와 같이 register의 값(rval)이 0이 아니고 하위 2 bits의 값이 0이면 이를 object에 대한 reference로 가정하고 marking을 시도한다. 이런 방식으로 동작해도 실제 GC 과정에는 별로 문제가 없다고 한다. 물론, 잘못된 영역을 marking해서 쓰레기로 처리되어야 할 object가 살아남는 경우도 발생할 수 있지만 별로 문제시 삼지않는다. (Android Platform Group에서 논의된 내용을 참고하시길)
현재 최신 버전의 Dalvik VM은 precise GC도 지원하는 것으로 보인다. 이를 위해 code verification 과정 중에 RegisterMap이라는 정보를 만들어낸다. RegisterMap은 method가 실행 시 특정 시점에 레지스터가 가진 값이 object에 대한 reference인지 나타내는 비트 값을 가진다. (Java의 StackMap과 유사한 개념이다.) 간단한 예를 들어보자.
int i = 10;
int a = i + 10; // (1) 0 0 0 0 0 0 0 0
SomeObject p = new SomeObject ();
callSomeMethod(p); // (2) 1 0 0 0 0 0 0 0
위와 같은 코드가 현재 callSomeMethod(p)까지 실행 중이다. 레지스터는 8개가 있다고 가정하자. (1)번 주석은 해당 라인의 코드가 실행될 때의 RegisterMap 값이다. 모든 비트가 0으로 이 stack frame의 레지스터 값은 object에 대한 reference가 하나도 없음을 알 수 있다. (2)번 주석의 경우는 1개의 비트가 1로 첫 번째 레지스터의 값이 object에 대한 reference임을 알 수 있다.
이처럼 precise GC를 처리하면 실행 성능에는 큰 차이가 없으나 엉뚱한 object를 marking하는 문제를 없앨 수 있다. 또한, compaction과 같은 발전된 GC 기능을 구현하기 위해서는 꼭 구현되어야 할 기능이다. 하지만, RegisterMap 정보를 추가적으로 만들어내므로 DEX 파일의 크기가 약 9% 정도 커지므로 주의하도록 한다.
Dalvik VM을 실행 시 -Xgenregmap 옵션을 지정해주면 code verification 과정 중에 dvmGenerateRegisterMapV 함수를 호출하여 RegisterMap을 생성한다.
참고자료:
- Wikipedia garbage collection 자료
- Android platform group discussion: distinguish object reference and primitive ...
- Dalvik VM Thread.c 파일의 gcScanInterpStackReferences 함수
- Android Developers Blog: Track memory allocations
댓글
댓글 쓰기