Store one status byte per bucket in WTF::HashTable
Component: WTF HashTable | 53bedf6
Source/WTF/wtf/HashMap.h
Source/JavaScriptCore/dfg/DFGLazyJSValue.cpp
WTF::HashTable은 open addressing 방식의 hash table입니다. HashMap과 HashSet은 물론, atom string, DFG CSE, JIT thunk, DOM cache 같은 내부 cache 상당수가 이 구현 위에서 동작합니다.
기존에는 key 타입마다 sentinel 값 두 개를 예약해 두었습니다. 하나는 empty, 다른 하나는 deleted를 뜻하며, 실제로 저장되는 key는 이 값과 같아질 수 없었습니다. 그리고 table은 bucket에 이 sentinel 값을 직접 기록하는 방식으로 bucket 상태를 관리했습니다.
한편 translator는 저장된 key와 다른 타입으로 조회와 삽입을 수행할 수 있게 해 주는 장치입니다. 새 bucket을 채우는 일은 translator의 translate()가 담당합니다. 이때 bucket에는 이미 유효한 sentinel 객체가 들어 있었으므로, translator는 그 위에 단순히 대입만 해도 문제가 없었습니다.
이번 commit에서는 bucket마다 별도의 status byte를 두도록 변경되었습니다. 이 byte는 empty, deleted, 또는 key hash의 7 bit 중 하나를 나타냅니다. 조회 시에는 bucket storage에 접근하기 전에 이 byte 배열을 먼저 탐색합니다.
결과적으로 타입별 sentinel이 더 이상 필요하지 않게 되었습니다. 새로 확보한 bucket의 메모리도 실제로 초기화되지 않은 상태로 둘 수 있습니다. 그래서 JSC, WTF, WebCore 전반의 translator가 raw storage를 가리키는 T*를 받아 그 자리에서 객체를 생성하도록 수정되었습니다.
Before: After:
buckets[]: key/value pairs status[]: 1 byte per bucket
empty = sentinel key 0x00 = empty
deleted = sentinel key 0x01 = deleted
lookup loads full bucket/probe 0x80|h7 = full, 7 hash bits
translate(T& slot, ...) translate(T* raw, ...)
slot = value (assign over new (NotNull, raw) T(value)
sentinel)
Significance
miss와 collision이 cache line 하나 안에서 처리되면서, Speedometer 3는 약 1%, MotionMark는 0.5%, JetStream 3는 최대 0.8% 개선되었습니다. 예약된 sentinel key 값을 둘러싸고 오랫동안 이어져 온 버그 유형도 함께 사라집니다. 다만 commit message에 따르면 반대 측면도 있습니다. 새 bucket에 대입하는 코드가 실제 garbage bit를 건드릴 가능성이 이전보다 훨씬 높아졌습니다.
Audit directions
- 이번 commit에서 누락된 translator가 있는지 살펴볼 필요가 있습니다. out-of-tree 코드, GTK/WPE/Win port, 사용 빈도가 낮은 translator가 대상입니다. 이 중 refcounted 타입(
String,RefPtr,Weak)을 raw storage에 여전히 대입하는 코드가 있다면, attacker 영향을 받는 stale pointer를 release하게 됩니다. 전형적인 UAF 또는 type confusion primitive로 이어질 가능성이 있습니다. translate()의 exception safety와 re-entrancy도 점검이 필요합니다. 객체 생성 중 exception이 발생하거나 같은 table로 재진입하는 경우(ensure의functor(), Weak/GC callback)를 가정할 수 있습니다. 이 경우 생성이 끝나기 전에 bucket이 full로 표시되거나, 삽입 도중 rehash가 발생할 가능성이 있습니다.- add, remove, rehash, shrink, 소멸 과정에서
status[]와 bucket 데이터 사이의 순서를 확인해야 합니다. deleted에서 empty로의 전환, tombstone 집계, 그리고 table 크기에 따라 달라지는 index bit와 7-bit tag collision이 겹치는 경우도 함께 살펴볼 필요가 있습니다. - JSC가 main thread 밖에서 읽는 table(DFG compiler thread, GC marking, concurrent JIT)도 대상입니다. status와 bucket 데이터 사이에 torn visibility가 관찰될 가능성이 있습니다. 변경된 iteration 순서에 의존하는 코드가 있는지도 확인이 필요합니다.
- 기존에 허용되지 않던 key(
nullptr, 0, -1)가 이제 유효한 값이 되었습니다. sentinel을 "없음"의 의미로 사용하던 코드나, 제거된isValidKey()assertion에 의존하던 코드(SmallMap)는 동작이 달라질 수 있습니다. - status와 bucket을 함께 담는 allocation layout의 크기 계산과 overflow 처리도 점검 대상입니다. 아직 sentinel을 사용하는
RobinHoodHashTable의 복사된 iterator 역시 함께 살펴볼 필요가 있습니다.