Chrome V8 Garbage Collector and Write Barrier

자바스크립트 엔진은 오브젝트들에 대한 레퍼런스들을 추적하고 레퍼런스들이 없어지면 가비지 컬렉팅한다.

크롬 V8은 2개의 가비지 컬렉터가 있는데 하나는 Minor GC라 하며 전체 메모리 공간 중 Young Space라 불리는 메모리 공간이 부족할 때 활동하는 가비지 컬렉터이다. 따라서 상대적으로 빈번히 GC를 실행한다. 하나는 Major GC이며 가끔씩 Young Space 뿐만 아니라 Heap Space 전체를 통째로 가비지 컬렉팅할 때 동작한다. 이번 글은 주로 Minor GC에 대해 다룰 것이다.

 

Minor GC는 Young Space라 불리는 지역을 관리하는데 Young Space는 새로 생성된 Object들이 존재하는 Heap Space이다. Minor GC는 이 Young Space를 다시 두개의 Space로 나누어 관리하는데 하나는 From-Space이고 하나는 To-Space이다. From-Space는 현재 사용 중인 Space이며 따라서 새로 생성된 object들은 Young Space의 From-Space에 위치하게 된다. 

 

반대로 To-Space는 가비지 컬렉팅이 동작하기 전까지는 전혀 쓰이지 않다가 가비지 컬렉팅시 사용이 되는데 이는 Minor GC가 Mark and Copy 방식으로 가비지 컬렉팅을 하기 때문이다. Mark and Copy방식은 reachable한 오브젝트들을 To-Space로 옮겨 빠르게 가비지 컬렉팅한다. 가비지 컬렉팅이 끝나면 To-Space와 From-Space가 서로 역할을 바꾼다. 그런 다음 다시 현재 Space가 꽉 차면 다시 반대쪽 Space로 Mark and Copy를 진행한다.

그림: https://slideplayer.com/slide/8257976/

만약 특정 Heap-Object가 두 번의 가비지 컬렉팅 과정에서 아직도 reachable하다면 해당 오브젝트는 Minor GC가 관리하는 Young Space가 아닌 Major GC가 관리하는 Old Space로 올려보낸다. Old-Space에 존재하는 오브젝트들은 비교적 오래 쓰이는 오브젝트들이 모일 것이고 이런 오브젝트들을 매번 가비지 컬렉팅 때마다 체크하는 것은 상당히 비효율적이므로 이렇게 Old Space로 옮겨 가끔식 만 Major GC가 관리하게 한다.

 

그림: https://v8.dev/blog/trash-talk

 

그런데 여기서 만약 Minor GC가 Young Space에 있는 오브젝트만 옮긴다면 Old-Space에 있는 오브젝트들은 어떻게 To-Space로 이동한 오브젝트들을 가리킬 수 있을까? 아래 그림에서 보는것과 같이 Old-Space에 있는 Object는 From-Space를 가리키다가 To-Space로 이동한 오브젝트의 주소를 가리켜야 한다. 같은 Young-Space에 있는 오브젝트들은 가비지 컬렉터가 옮기면서 reference들을 rewrite 할 수 있지만 Old-Space는 건들지 않고 있기 때문에 rewrite 해 줄수 없다.

그렇다고 Young Space만 가비지 컬렉팅 하는게 목적인데 Old-Space를 싹 뒤지며 reference를 다시 써줄 수도 없는 노릇이다. 그건 Minor GC가 아니라 Major GC를 작동시키는 것 과 다를바 없는 비효율적인 작업이다.

이를 해결하는 방법은 WriteBarrier. 다 만약 Old-Space의 오브젝트가 Young-Space에 존재하는 오브젝트를 참조할 순간이 생기면 해당 Young-Space에 존재하는 특수한 테이블에 Old-Space의 오브젝트가 참조한다는 정보를 기록을 하는데 이런 방법을 WriteBarrier라 한다. V8에서는 Young-Space에 있는 이 특수한 테이블을 remembered set이라 부른다. 이런 식으로 Minor GC는 Young-Space의 한 Object를 가비지 컬렉팅할 때 remembered-set에 기록된 reference들을 rewrite 한다. ( V8에서 Remembered Set이라 이름붙이긴 했지만 그 방식은 Bit Table을 사용하는 것 같이 보인다. 따라서 정확히는 Card Marking이라고 봐야 할 것 같다. )

let old_obj = Object; // 0x40100  in Old-Space
let new_obj1 = {a:1};//0x10040 in Young-FromSpace
old_obj.a = new_obj; //old_obj.a ( [0x40110] -> 0x10040 )
let new_obj2 = {b:1};//0x10080 in Young-FromSpace
old_obj.b = new_obj; //old_obj.b ( [0x40120] -> 0x10080 )

 

 

V8에서 WriteBarrier는 Minor GC가 Young-Space를 가비지 컬렉팅 할 때 Old-Space가 Young-Space를 가리키는 레퍼런스 문제를 해결하기 위한 것이다. 따라서 Old-Space -> Young-Space 참조가 아닌 경우라면 WriteBarrier가 필요하지 않다. 따라서 아래 v8 코드에서 볼 수 있듯이 각각 YoungSpace, OldSpace인지를 체크한 다음 remembered set에 기록한다.

 

- v8/src/heap/heap-write-barrier-inl.h

inline void GenerationalBarrierInternal(HeapObject object, Address slot,
                                        HeapObject value) {
  DCHECK(Heap_PageFlagsAreConsistent(object));
  heap_internals::MemoryChunk* value_chunk =
      heap_internals::MemoryChunk::FromHeapObject(value);
  heap_internals::MemoryChunk* object_chunk =
      heap_internals::MemoryChunk::FromHeapObject(object);

  if (!value_chunk->InYoungGeneration() || object_chunk->InYoungGeneration()) {
    return;
  }

  Heap_GenerationalBarrierSlow(object, slot, value);
}

 

그렇다면 만약 WriteBarrier가 제 기능을 못 하면 어떻게 될까?

최신 웹 브라우져들은 JIT가 탑재되어 있고 JIT는 자바스크립트 코드를 어셈블리로 컴파일할 때 이런 WriteBarrier코드 역시 같이 다루어 주어야 한다. 즉 store operation이 Old-Space -> Young-Space 참조인 경우 remembered set에 저장하는 기능을 JIT Compiled된 코드에 넣어주어야 한다. 하지만 JIT는 그 특성으로 인해 Type Confusion 버그가 발생하기 굉장히 쉽고 실제로 JIT Compile 과정에서 필드 타입을 HeapObject인지 아닌지를 잘못 다루어 WriteBarrier 코드가 제거되어 버리는 사례가 종종 있었던 걸로 기억한다.

 

WriteBarrier코드가 작동하지 않으면 Remembered set에 reference를 기록하지 못하므로 가비지 컬렉팅 이후에는 아래와 같이 Old-Space에 있는 오브젝트가 휑하니 남은 이전 From-Space를 가리키게 된다. 

이런 버그가 발생 했을 때의 exploit은 개념은 간단하지만 Reliable하게 exploit 하기는 대단히 어렵다.

WriteBarrier가 제거되어 버려서 Old-Space의 Object가 Young-Space에 존재하는 한 Object를 remembered-set에 기록하지 않은 채 참조하고 있는 상황을 가정해보자.

exploit을 위해선 우선 To-Space로 갔다가 다시 From-Space로 다시 되돌아가야 한다. 강제로 Minor GC가 호출되게 메모리를 소모하면 To-Space로 간 뒤 From-Space로 돌아가는데 Old-Space에 존재하는 오브젝트는 From-Space의 어딘가를 휑하니 가리키고 있을 것이다. 그 가리키는 공간을 적절한 오브젝트 값으로 채워 넣으면 아래 그림에서 obj.a 필드를 Type Confusion을 이용한 Exploit에 사용할 수 있다. 물론 처음엔 메모리의 정확한 주소를 모르니 Segfault가 나지 않게 적절한 방법으로 From-Space를 채워 넣어야 한다. 특히 Chrome의 경우 From-Space에서 To-Space로 가는 동안 Exploit 레이아웃이 상당히 변할 수 있어 Exploit을 시도하는 공격자는 메모리 레이아웃을 Reliable하게 유지할수 있는 방법으로 Exploit을 진행해야 한다.

 

---

Javascript Engine traces all the references for all the objects and garbage collects them if there is no reference remained. 

Chrome V8 has 2 garbage collectors. One is called Minor GC and it garbage collects special memory space called Young-Space whenever the memory space lacks memory so Minog GC runs relatively frequently. Another one is called Major GC and it manages not only Young-Space but whole heap space. This post will mainly talk about Minor GC.

 

Minor GC manages YoungSpace. The Young Space is a heap space for newly created objects. Minor GC again manages YoungSpace with two divided spaces, one is From-Space and the other one is To-Space. From-Space would be a memory space that is currently used so newly created object would actually be placed in here.

 

On the other hand, To-Space is not used at all before Minor GC runs because Minor GC uses Mark and Copy as a garbage collecting algorithm. Mark and Copy can trace all the reachable objects from the root and can place them to To-Space quickly. After then, previous To-Space will be From-Space this time and if it becomes full again, then Minor GC will again migrate objects to the opposite space.

 

If one heap object is reachable after two of garbage collecting, then the object will be evacuated to Old-Space, a space that is managed by Major GC, by Minor GC. All the objects that exist in Old-Space will tend to survive longer so it would be inefficient to check those objects for every garbage collecting. That's why V8 migrates long-survived objects to Old-Space and manages them with only Major GC.

 

But how can all the objects in Old-Space point to the objects moved to Young-ToSpace if Minor GC only handles Youns Space object? Minor GC can rewrite references for Young-Space objects because Minor GC will iterate all the reachable objects in Young-Space while moving them. But if Minor checks all the objects in Old-Space to rewrite references then that would be as expensive operation as running Major GC.

 

 

To solve this, Whenever javascript tries to set a reference in an Old-Space object to Young-Space objects, V8 records information that some Old-Space object has a reference to that Young-Space object in a table for Young-Space. This method is called WriteBarrier. The reference table for Young-Space is called remembered set in V8 world. If one object in From-Space of Young Space is recorded in the remembered set like this, Minor GC can know places that have reference to From-Space object and can rewrite the reference.

let old_obj = Object; // 0x40100  in Old-Space
let new_obj1 = {a:1};//0x10040 in Young-FromSpace
old_obj.a = new_obj; //old_obj.a ( [0x40110] -> 0x10040 )
let new_obj2 = {b:1};//0x10080 in Young-FromSpace
old_obj.b = new_obj; //old_obj.b ( [0x40120] -> 0x10080 )

 

 

V8 needs WriteBarrier only when Minor GC garbage collects Young-Space and there is a reference from Old-Space to Young-Space. If a reference is not a type of Old-Space -> Young-Space reference, then it doesn't need to use WriteBarrier. As we can see below code of V8, V8 checks first whether it is a reference of YoungSpace -> OldSpace and records the information in the remembered set if that is the case.

 

- v8/src/heap/heap-write-barrier-inl.h

inline void GenerationalBarrierInternal(HeapObject object, Address slot,
                                        HeapObject value) {
  DCHECK(Heap_PageFlagsAreConsistent(object));
  heap_internals::MemoryChunk* value_chunk =
      heap_internals::MemoryChunk::FromHeapObject(value);
  heap_internals::MemoryChunk* object_chunk =
      heap_internals::MemoryChunk::FromHeapObject(object);

  if (!value_chunk->InYoungGeneration() || object_chunk->InYoungGeneration()) {
    return;
  }

  Heap_GenerationalBarrierSlow(object, slot, value);
}

Then what would happen if the WriteBarrier doesn't function appropriately?

Modern web browsers usually have JIT Compiler and JIT Compiler should handle WriteBarrier operation when it creates machine code from javascript. JIT Compiler should put functionality that If the store operation to an Old-Space object is a type of Old-Space -> Young-Space reference then machine code should be able to the information to a remembered set. But JIT Compiler is naturally prone to cause Type Confusion bugs and actually I remembered that there were sometimes bugs that remove WriteBarrier failing to check whether a type of a property field is HeapObject or not.

 

If WriteBarrier doesn't work, JIT Compiled code can't record reference information in a remembered set so an object in Old-Space can point to invalid previous From-Space after Minor GC operation.

Exploiting this kind of bugs can be easy in some point of view and also can be hard in some point of view. It first needs to go to To-Space and then move back to From-Space.  If Javascript code consumes memory intentionally then Minor GC will operate and can come back to From-Space. If there is WriteBarrier, One of the properties of an object in Old-Space will point to somewhere in From-Space like a dangling pointer. If an attacker can fill that location with an appropriate object value like the figure below , then obj.a can be used for Type Confusion Exploit. But as we don't know the exact memory address of From-Space, it would be important to prevent Segfault when we try to fill them. Especially there are so many running functionalities in Chrome so the exploit memory layout can be seriously unstable when it arrives back in From-Space. So an attacker should try to find a somewhat good way to get reliability.

 

- ref:

v8.dev/blog/trash-talk

Trash talk: the Orinoco garbage collector · V8