[3] Allocation sinking re-adds candidates the inline-frame check demoted

The filter ran first, then the worklist quietly put the candidates back

aa07769

High. non-monotone filter 뒤에 monotone worklist를 배치하면, filter가 보장하던 성질이 그대로 무너집니다. phase에 남아 있는 주석 자체가 그 결과를 설명하고 있습니다. GC stack walk가 사이에 끼어든 코드에 의해 이미 재사용된 frame slot을 읽게 됩니다. 유발하려면 closure-call 또는 varargs inline frame이 필요하며, 그 escape site가 다른 frame에 있어야 합니다.

Object allocation sinking은 컴파일러 최적화 기법 중 하나입니다. 객체가 생성된 영역 밖으로 escape하지 않는다면, 할당 자체를 제거하고 실제로 관찰될 수 있는 지점에서만 다시 생성합니다. WebKit의 DFG는 이 작업을 ObjectAllocationSinkingPhase에서 수행합니다. 이때 다시 생성되는 객체는 Materialize 노드로 emit되면서 CodeOrigin을 함께 갖게 되는데, CodeOrigin은 해당 코드가 어느 inlined function frame에 속하는지를 런타임에 알려주는 bytecode 위치입니다. 한편 closure call과 varargs call의 inlined frame은 callee와 argument count를 컴파일 타임 상수가 아니라 동적인 stack slot에 보관합니다. 그래서 materialization 지점에서 stack walk를 수행하려면, 그 frame의 slot들이 여전히 살아 있는 상태여야 합니다.

관전 포인트: inlined closure나 varargs call 안에서 할당이 이루어지도록 배치하고 다른 frame에서 escape시키는 script를 작성하면, GC stack walk가 이미 재사용된 stack 데이터를 frame metadata로 해석하게 됩니다.

Patch Details

determineSinkCandidates()의 실행 순서가 변경되었습니다. 기존에는 InlineCallFrame 안전성 검사가 먼저 수행되었습니다. 이 검사는 할당이 closure-call이나 varargs inline frame 안에서 시작되면서 escape site는 다른 frame에 놓인 candidate를 제거합니다. 그 뒤에야 closure rule #2 worklist가 dependencies map을 따라 m_sinkCandidates를 fixpoint까지 확장했습니다("sink candidate가 local allocation에 저장되면 그 allocation 역시 sink candidate가 된다"). 패치 이후에는 rule #2가 먼저 수행되고, InlineCallFrame 검사가 최종 판정자 역할을 맡습니다. 여기에 rule #1이 추가되었습니다. demote된 allocation에 의존하는 대상을 전이적으로 함께 demote해서, candidate를 제거한 뒤에도 집합이 어긋나지 않도록 합니다. materialization loop 안에는 ASSERT(!shouldDemote(allocation, where))가 추가되었습니다. regression test 두 개도 함께 포함되었습니다.

non-monotone filter 뒤에 monotone fixpoint pass가 배치되어, filter가 보장하던 성질이 스스로 관측할 수 없는 확장에 의해 조용히 무효화되는 패턴.

  Before                                After
  ------                                -----
  InlineCallFrame check (filter)        closure rule #2 to fixpoint
      demotes P                              |
        |                               InlineCallFrame check
  closure rule #2 to fixpoint             demotes P, final
      re-adds P, or adds it for               |
      the first time                    rule #1 demotes anything
        |                               depending on P
        v                                     |
  Materialize P at the escape site      ASSERT(!shouldDemote(...))
  carrying an inlined closure/varargs    in the materialization loop
  CodeOrigin -> GC stack walk reads
  slots the intervening code reused

Background

이 코드가 있는 위치. ObjectAllocationSinkingPhase는 DFG의 SSA 수준 escape/points-to 분석입니다. SSA optimization pass들과 code generation 사이에 위치하며, 그 결과는 런타임의 inline-frame 재구성 기계로 전달됩니다.

Materialization과 code origin. 어떤 할당을 sink할 수 있다고 판단하면, phase는 객체가 escape하는 프로그램 지점마다 Materialize* 노드를 emit합니다. 각 노드는 자신이 의미상 속한 inlined call chain을 기술하는 CodeOrigin / CallSiteIndex를 지니고, 런타임은 이 metadata를 사용해 virtual frame을 재구성합니다.

Inline call frame. InlineCallFrame은 inline된 함수 하나의 activation을 기술합니다. 대부분의 inlined call에서는 callee와 argument count가 컴파일 타임 상수이므로 frame descriptor만으로 복원할 수 있습니다. 다만 isClosureCall과 isVarargs() frame은 그렇지 않습니다. callee slot과 argument-count slot이 동적인 stack 위치에 있어, 살아 있는 machine stack에서 직접 읽어야 합니다.

Stack walking. StackVisitor는 machine stack으로부터 논리적인 JavaScript call stack을 재구성하며, collector는 GC마다 stack walk를 수행합니다. 이 동작이 의미를 가지려면, 읽어 들이는 frame들이 아직 덮어써지지 않은 상태여야 합니다.

Analysis

누락된 invariant는 결합 순서입니다. candidate 집합에 대해서는 InlineCallFrame 검사가 마지막 결정권을 가져야 합니다. non-monotone filter 뒤에 단조 증가하는 closure pass를 두면, filter가 세워 놓은 성질이 그대로 무너집니다. 이 순서 때문에 서로 다른 두 개의 구멍이 생겼고, 추가된 test 두 개가 각각 하나씩을 담당합니다.

첫 번째는 never inspected 유형입니다. candidate C가 부모 allocation P에 저장되면 rule #2가 P를 승격시킵니다. 이 승격이 검사보다 나중에 일어나므로, P는 shouldDemote()로 한 번도 검사되지 않습니다. P가 closure-call이나 varargs inline frame에서 시작되고 다른 곳에서 escape하는 경우에도 마찬가지입니다(...closure-rule-promoted-parent.js). 두 번째는 undone 유형입니다. 검사는 P를 정상적으로 제거하지만, 이어서 rule #2의 worklist가 자신의 invariant를 다시 세우는 과정에서 P를 재추가합니다. 결과적으로 demotion이 조용히 되돌려집니다(...closure-rules.js).

두 경우 모두 P에 대한 Materialize* 노드가 escape site에 emit되면서, inlined closure 또는 varargs frame의 의미상 origin을 그대로 지니게 됩니다. diff에 남아 있는 phase 자체의 주석이 그 결과를 설명합니다. 사이에 끼어든 코드가 frame의 slot을 이미 재사용했기 때문에 그 지점에서는 "we can't do the stack walk" 상태이며, "we do a stack walk when we GC"라고 적혀 있습니다. commit message는 문제가 되는 slot을 구체적으로 지목합니다. closure-call의 callee slot과 varargs의 argument-count slot이며, 이 frame 종류에서는 상수가 아니라 동적으로 결정되는 값입니다. test에서는 spread call clobber(...arr)이 해당 stack 영역에 자기 데이터를 남기는, 사이에 끼어드는 코드에 해당합니다.

결과적으로 frame 재구성 과정에서 type confusion이 발생합니다. collector가 시작한 stack walk가 재사용된 stack 데이터를 frame metadata로 읽게 되기 때문입니다. commit message는 문제의 InlineCallFrame 검사의 출처를 208291@main으로 지목합니다. 제공된 context에는 해당 변경이 포함되어 있지 않으므로, 이 출처 표기는 그대로 인용합니다.

이 vulnerability로 인해 런타임은 스스로 재구성한 call stack을 신뢰하기 어려워집니다. collector가 조건 없이 의존하는 기계이기도 합니다. 추가된 ASSERT 덕분에 같은 문제가 다시 발생하더라도, 조용한 miscompile 대신 사용 지점에서 debug build trap으로 드러나게 됩니다.

Audit directions

fixpoint pass와 결합된 filter. 안전성 filter와 monotone worklist가 같은 집합을 다룬다면, filter는 마지막에 수행되거나 확장 단계마다 다시 적용되어야 합니다. 그렇지 않으면 worklist가 filter의 제거 결과를 그대로 되살리며, 코드 어디에도 그 사실이 드러나지 않습니다. 여러 rule에 걸쳐 candidate 집합이나 must-handle 집합을 유지하는 다른 DFG phase들을 점검해 볼 필요가 있습니다(ObjectAllocationSinkingPhase와 나란히 있는 escape 분석들, PutStackSinkingPhase, SSA 변환 helper 등). 확인 대상은 fixpoint loop보다 먼저 평가되는 안전성 predicate입니다. 코드 리뷰에서의 신호는 같은 컨테이너에 대한 filtering pass 뒤에 등장하는 do { changed = ... } while (changed) loop입니다.
code motion 지점에서의 CodeOrigin 정합성. 노드를 새로운 프로그램 지점으로 옮기는 phase는, 그 지점에서도 노드의 CodeOrigin이 여전히 살아 있는 machine stack을 기술한다고 암묵적으로 주장하는 셈입니다. origin을 지닌 노드를 재배치하는 phase를 모두 나열한 뒤, 각각을 closure-call과 varargs frame 종류에 대해 따로 확인하는 편이 좋습니다. 이 두 종류만 metadata를 상수로부터 복원할 수 없기 때문입니다.