Chrome V8 Map and Map Transition

Chrome 웹 브라우져의 V8은 Map이라는 내부 Object로 오브젝트의 구조 정보를 저장한다. 말하자면 V8에서는 Map이 곧 오브젝트의 class혹은 타입을 의미한다. 만약 두 오브젝트가 똑같은 프로퍼티를 가지고 있다면 같은 Map을 공유하고 다른 프로퍼티를 가지고 있다면 다른 Map을 가지게 된다.

V8 Turbofan은 자바스크립트 코드를 컴파일 할때 타입 피드백을 이용해 컴파일하는데 예를 들어 아래 그림과 같이 my_obj라는 {a:int, b:int} 프로퍼티를 가진 오브젝트가 temp함수의 argument로 사용되었다면 V8은 그 Object의 Map을 피드백으로 저장한다. 피드백으로 저장된 Map정보는 나중에 JIT-Compiler가 컴파일을 진행할 때 타입정보로 이용한다. 자바스크립트 object는 C/C++처럼 struct, class라는 개념은 없지만 동일한 Map을 가지는 Object는 동일한 메모리 구조를 가지므로 C/C++컴파일 처럼고정된 타입을 다루는 머신코드로 컴파일 할 수 있다.

그렇다면 JIT Compile된 함수에 피드백에 쓰인 Map과는 다른 Map을 가지는 오브젝트를 넣어버리면 어떻게 될까? 다른 구조를 가지는 오브젝트를 머신코드가 잘못 참조하면 메모리 Segfault가 나버리니 JIT-Compiler는 이에 대한 대책이 필요하다. 사실 JIT Compiler는 JIT-Compiled된 머신코드들의 첫 부분에 컴파일 때 쓰인 피드백과 동일한 Map인지 검사하는 체크 루틴을 집어넣는다. 따라서 피드백에 쓰인 Map이 아니라면 Map MISS 루틴을 호출해 다시 바이트코드 인터프리터 모드로 되돌아 갈 수 있다.

그림: https://darkwing.moe/2019/12/27/V8%E7%9A%84%E4%BC%98%E5%8C%96%E6%9C%BA%E5%88%B6/

V8에는 Map에 프로퍼티가 추가될 때 마다 새로운 Map으로 전환하는 transition이라는 기능이 있다. Map은 아래 그림과 같이 프로퍼티가 추가될 때 마다 transition을 거친다. 예를들어 HC 0 Map을 가지는 오브젝트에 프로퍼티 a를 추가하면 HC 1이라는 Map이 생겨난다. 그림에서는 a, b, c를 순서대로 추가했더니 HC 1, HC 2, HC 3이라는 Map이 생겨났다. 만약 나중에 추가로 어떤 텅 빈 오브젝트에 a,b,c 프로퍼티를 차례로 추가하면 그 오브젝트는 이미 존재하는 HC 1 Map, HC 2 Map, HC 3 Map을 차례로 사용하게 된다. 위에서 말했듯이 같은 프로퍼티를 쓰는 오브젝트는 같은 Map을 사용하기 때문이다.

그림:https://blog.exodusintel.comblog.exodusintel.com/2019/09/09/patch-gapping-chrome/

 

Map을 관리하는 오브젝트들의 구조는 아래와 같다. 아래 그림에서 hiddenClass가 사실 Map이다. Map에는 Descriptors Array를 가리키는 필드가 있는데 Descriptor는 하나의 프로퍼티를 설명하는 오브젝트이다.

 

그림:https://blog.exodusintel.comblog.exodusintel.com/2019/09/09/patch-gapping-chrome/

 

그렇다면 V8에서는 위와 같은 Transition을 어떻게 관리할까? V8은 Transition을 내부의 Transition Tree를 이용해 관리한다. 아래 파일에서 보이는 TransitionArray class로 Transition Tree를 관리한다. 이 TransitionArray는 모든 Map에 존재하는데 Map + kTransitionsOrPrototypeInfoOffset 위치에 존재한다.

- TransitionArray : v8/src/objects/transitions.h

// TransitionArrays are fixed arrays used to hold map transitions for property,
// constant, and element changes.
// The TransitionArray class exposes a very low-level interface. Most clients
// should use TransitionsAccessors.
// TransitionArrays have the following format:
// [0] Link to next TransitionArray (for weak handling support) (strong ref)
// [1] Smi(0) or WeakFixedArray of prototype transitions (strong ref)
// [2] Number of transitions (can be zero after trimming)
// [3] First transition key (strong ref)
// [4] First transition target (weak ref)
// ...
// [3 + number of transitions * kTransitionSize]: start of slack
class TransitionArray : public WeakFixedArray {
 public:
  DECL_CAST(TransitionArray)

  inline WeakFixedArray GetPrototypeTransitions();
  inline bool HasPrototypeTransitions();
  ...
}

TransitionArray로 Transition상태를 어떻게 표현하는지 구체적으로 나타내면 아래 그림과 같다. TransitionArray는 특정 맵에 프로퍼티가 추가 되었을 시 다른 Map으로의 전이를 "맵핑"으로 저장한다. 이런 식으로 TransitionArray를 관리하면 나중에 똑같은 Map을 가지는 Object가 해당 TransitionArray를 참고해 기존에 존재하는 Map으로 Transition할 수 있다. 예를 들어 이후에

Obj4 = {}; // Map1

Obj4.A = 3;

이라는 코드를 실행시키면 Map 1에서 A를 추가시켰을 때의 Transition이 기록되어 있으므로 Map 2로 전환될 수 있다.

 

* 이 글은 Chrome 80 버전 이전에 연구했던 내용이므로 Type 및 Representation 변화로 인한 Map Transition의 정확한 동작은 약간 다를 수 있음

조금 특이할 수도 있는 점은 V8은 필드의 타입을 뜻하는 Representation이라는 개념을 사용한다. 자바스크립트와 같이 오브젝트의 필드가 동적으로 추가되는 환경에서는 필드의 타입이 일반 smi ( small integer 타입, primitive 타입으로 포인터가 아닌 value 타입이다 ) 인가와  Heap Object ( 즉 포인터가 필요한 타입) 인가에 따라 JIT-Compiler는 필드에 접근하는 코드를 다르게 컴파일해야 한다. 포인터에 접근하는 머신코드와 primitive type에 접근하는 머신코드는 당연히 다르다. 따라서 똑같은 프로퍼티를 추가했다고 하더라도 필드의 타입을 나타내는 Representation의 차이 때문에 새로운 Map으로 Transition하는 경우도 있다.

 

오브젝트에 프로퍼티를 추가했을 때 이런 Map Transition을 다루는 코드는  v8/src/objects/objects.cc 파일의

Object::AddDataProperty 함수에서 다룬다.

 

- v8/src/objects/objects.cc

Maybe<bool> Object::AddDataProperty(LookupIterator* it, Handle<Object> value,
                                    PropertyAttributes attributes,
                                    Maybe<ShouldThrow> should_throw,
                                    StoreOrigin store_origin) {
    ...
    // Migrate to the most up-to-date map that will be able to store |value|
    // under it->name() with |attributes|.
    it->PrepareTransitionToDataProperty(receiver, value, attributes,
                                        store_origin);
    DCHECK_EQ(LookupIterator::TRANSITION, it->state());
    it->ApplyTransitionToDataProperty(receiver);

    // Write the property value.
    it->WriteDataValue(value, true);
    ...
  }

각 함수의 역할에 대해 설명하자면 다음과 같다.

PrepareTransitionToDataProperty: 새 프로퍼티로 Map을 생성

ApplyTransitionToDataProperty : Migration을 실행한 다음 부모 TransitionArray에 새로 생성된 Map을 기록한다.

WriteDataValue : ( 새로운 Map을 가지게 된 ) receiver의 프로퍼티 필드에 value를 써 넣는다.

 

Map은 경우에 따라 Integration(통합)이 되기도 한다. 아래에서 Map 1의 property "a" 의 representation은 처음에 Float이었다가 "a"에 empty object를 저장하면서 Tagged All representation을 가진 Map 2로 transition 한다. 이때 Tagged All은 포괄적인 표현이므로  Map 2으로 Map 1을 대체 가능하고 더 이상 Map 1은 있어봤자 낭비이므로 Deprecated로 처리한다. 이때 Obj1의 Map 1은 store property 연산이 발생시 새로운 Map인 Map 2로 대체한다.

 

만약 Map이 이미 Child를 가지고 있으면 어떻게 될까? 그러면 TransitionArray를 Resursive하게 따라가면서 Child Map까지 Deprecated처리하고 죄다 새로운 Map을 형성해버린다. 

//Represenation 으로 Deprecated된 Map이 이미 Child Map을 가지고 있다면 연쇄적으로 Resursive하게 Child Map까지 Deprecated처리하고 새로운 Map을 형성한다.
 
MyObj = {a:1.1};  // Map 1
Obj1 = {a:2.2}; // Map 1
Obj1.b = 4.2 // Map 2
MyObj.a = {}; // representation 변화로 새로운 맵 Map 3 생성, Map 2 역시 Map 4로 대체

 

흥미롭게도 Map Transition 때문에 발생한 Exploit 가능한 Type Confusion 버그가 있었다.

bugs.chromium.org/p/chromium/issues/detail?id=992914

 

exodus라는 팀에서 이에 대한 자세한 exploit을 써 놨다. ( https://blog.exodusintel.comblog.exodusintel.com/2019/09/09/patch-gapping-chrome/ )

위 블로그에서 쓰인 PoC 코드는 다음과 같다.

function mainSeal() {
 const a = {foo: 1.1};  // a has map M1
 Object.seal(a);        // a transitions from M1 to M2 Map(HOLEY_SEALED_ELEMENTS) -> Array Backing store also becomes SEALED .. non add, non configuraable
 const b = {foo: 2.2};  // b has map M1
 Object.preventExtensions(b); // b transitions from M1 to M3 Map(DICTIONARY_ELEMENTS)
 Object.seal(b);        // b transitions from M3 to M4  (HOLEY_SEALED_ELEMENTS)
 const c = {foo: Object} // c has map M5, which has a tagged `foo` property, causing the maps of `a` and `b` to be deprecated
 b.__proto__ = 0;       // property assignment forces migration of b from deprecated M4 to M6


 a[5] = 1;              // forces migration of a from the deprecated M2 map, v8 incorrectly uses M6 as new map without converting the backing store. M6 has DICTIONARY_ELEMENTS while the backing store remained unconverted.
}

 

버그의 핵심은 deprecated 된 M2 map을 M6 map으로 교체하는 과정에서 backing store은 그대로 놔둔채로 새로운 M6으로 교체 해버려서 그렇다. Object.seal을 할 때 backing store 역시 SEALED 상태가 되는데 이 case를 Map Deprecation & Replacement 코드에서 제대로 다루지 못했다. 따라서 V8은 backing store 교체에 실패하고 map만 M6으로 바꾸어 Type Confusion이 발생하게 된 것이다.

---

Chrome Web Browser V8 manages object property information with an Internal hidden Object called Map and this Map is actually type information about objects. If two objects have the same properties then they will share the same Map and will have different Maps if not.

 

 

In V8 World, Map itself would be type of objects. V8 Turbofan compiles javascript code with type feedback. For example, as we can see below, if temp function is called with my_obj of { a:int, b:int } properties as an argument then V8 stores the Map of my_obj as type feedback so that when V8 compiles javascript code it can refer Map information and translate the javascript code into assembly machine code.

 

 

Then what would happen if we put a strange object with a different Map into the compiled function? All the JIT-compiled code checks if the Map is exactly the same Map with the Map used in type feedback before executes the main code. If the Map is not the same Map with feedback then V8 will turn it back to bytecode interpreter mode calling Map MISS routine.

 

 

Picture:https://darkwing.moe/2019/12/27/V8%E7%9A%84%E4%BC%98%E5%8C%96%E6%9C%BA%E5%88%B6/

As we have seen, Map plays core role in V8 JIT. And there is one more things to explain about Map, Map transition.

When additional properties are added to an object the Map of the object will go through transition. As we can see below, If we add a property named "a" to an object, HC 1 Map would be created, and so on. And if we add properties named "a","b","c" to an empty object later, the object will use existing Map HC 1, HC 2, HC 3 accordingly , because all the objects with same properties share a same Map.

 

Picture: https://blog.exodusintel.comblog.exodusintel.com/2019/09/09/patch-gapping-chrome/

 

Below is the structure of objects that manage Map in V8. HiddenClass means Map in here. There is a reference field which points to DescriptorsArray. DescriptorsArray is an Array of Descriptor and Descriptor is an information object for one property.

 

Picture: https://blog.exodusintel.comblog.exodusintel.com/2019/09/09/patch-gapping-chrome/

 

Then how V8 can manage transition? V8 manages transition with Internal Transition Tree. As we can see in the transitions.h file below, There is TransitionArray class and V8 uses this class to manage Transition Tree. All the Map has TransitionArray in Map + kTransitionsOrPrototypeInfoOffset location.

- TransitionArray : v8/src/objects/transitions.h

// TransitionArrays are fixed arrays used to hold map transitions for property,
// constant, and element changes.
// The TransitionArray class exposes a very low-level interface. Most clients
// should use TransitionsAccessors.
// TransitionArrays have the following format:
// [0] Link to next TransitionArray (for weak handling support) (strong ref)
// [1] Smi(0) or WeakFixedArray of prototype transitions (strong ref)
// [2] Number of transitions (can be zero after trimming)
// [3] First transition key (strong ref)
// [4] First transition target (weak ref)
// ...
// [3 + number of transitions * kTransitionSize]: start of slack
class TransitionArray : public WeakFixedArray {
 public:
  DECL_CAST(TransitionArray)

  inline WeakFixedArray GetPrototypeTransitions();
  inline bool HasPrototypeTransitions();
  ...
}

We can see exactly how V8 can manage Transition with TransitionArray in the below figure. TransitionArray "map" properties to other Map to describe transition to other Maps from the current Map with added properties. By doing so, When a property is added to an object with the same Map, V8 refers to this TransitionArray and makes the object transition to an existing Map. For example, If we execute the following code later,

Obj4 = {}; // Map1

Obj4.A = 3;

There is an existing transition for the property "A" in TransitionArray below, so V8 can just transition it into Map 2 from Map 1 without creating new a Map.

* I studied all the contents in here before Chrome 80 Version so exact operation of Map transition caused by Type and Representation changes can be slightly different

What can be a little bit strange in here is that V8 uses called Representation to describe property field type. JIT Compiled codes which try to access a property field type can be different depending on whether the field is smi type ( small integer type ) or Heap Object ( requiring point to it ). So even though two objects have same properties they could have different Map if they have different Representations on the fields.

 

We can see the codes that handle this transition operation when a new property is added at Object::AddDataProperty function in v8/src/objects/objects.cc file.

 

- v8/src/objects/objects.cc

Maybe<bool> Object::AddDataProperty(LookupIterator* it, Handle<Object> value,
                                    PropertyAttributes attributes,
                                    Maybe<ShouldThrow> should_throw,
                                    StoreOrigin store_origin) {
    ...
    // Migrate to the most up-to-date map that will be able to store |value|
    // under it->name() with |attributes|.
    it->PrepareTransitionToDataProperty(receiver, value, attributes,
                                        store_origin);
    DCHECK_EQ(LookupIterator::TRANSITION, it->state());
    it->ApplyTransitionToDataProperty(receiver);

    // Write the property value.
    it->WriteDataValue(value, true);
    ...
  }

Let's briefly talk about those functions.

PrepareTransitionToDataProperty: Creates new Map with new property

ApplyTransitionToDataProperty : Does Migration ( replaces an existing old map with a new map ) and sets transition data at parent’s( old map ) TransitionArray. 

WriteDataValue : Writes value at the receiver ( which is now maintaining the new Map )

 

In some cases, a Map can be integrated. In the figure below, the representation of the property "a" of Map 3 was Float and then changed to Tagged All after assigning the empty object to "a".  Tagged All is more the comprehensive expression so Map 3 can replace Map 1 and Map 1 would be marked as deprecated. Obj2 also has Map 1 so this would be replaced if some codes try to store value to the property sometimes in the future.

 

Below we can this another example of Map Integration and Transition Tree.

MyObj = {a:1.1};  // Map 1
Obj1 = {a:2.2}; // Map 1
Obj1.b = 4.2 // Map 2
MyObj.a = {}; // representation 변화로 새로운 맵 Map 3 생성, Map 2 역시 Map 4로 대체

Interestingly, There was an exploitable Type Confusion bug caused by Map Transition.

bugs.chromium.org/p/chromium/issues/detail?id=992914

 

( company or team ? ) Exodus detailed the bug and exploit process.

( https://blog.exodusintel.comblog.exodusintel.com/2019/09/09/patch-gapping-chrome/ )

This is Poc code in the blog.

function mainSeal() {
 const a = {foo: 1.1};  // a has map M1
 Object.seal(a);        // a transitions from M1 to M2 Map(HOLEY_SEALED_ELEMENTS) -> Array Backing store also becomes SEALED .. non add, non configuraable
 const b = {foo: 2.2};  // b has map M1
 Object.preventExtensions(b); // b transitions from M1 to M3 Map(DICTIONARY_ELEMENTS)
 Object.seal(b);        // b transitions from M3 to M4  (HOLEY_SEALED_ELEMENTS)
 const c = {foo: Object} // c has map M5, which has a tagged `foo` property, causing the maps of `a` and `b` to be deprecated
 b.__proto__ = 0;       // property assignment forces migration of b from deprecated M4 to M6


 a[5] = 1;              // forces migration of a from the deprecated M2 map, v8 incorrectly uses M6 as new map without converting the backing store. M6 has DICTIONARY_ELEMENTS while the backing store remained unconverted.
}

 

The key idea of this Bug is that when replacing deprecated M2 Map to M6 map, V8 fails to replace backing store while replacing only the old map to the new map. In Object.seal, backing store also be SEALED but V8 doesn't handle this case in Map Deprecation and replacement code. So it fails to replace backing store and leads to Type Confusion.

 

- ref

https://blog.exodusintel.comblog.exodusintel.com/2019/09/09/patch-gapping-chrome/

Patch-gapping Google Chrome - Exodus Intelligence