[6] Range boundary-point lock discipline follow-up

MediumWebCore DOMRace

621e3bf

Medium 등급인 이유는 이번 commit이 강화하는 lock 자체가 이미 존재하고 있었기 때문입니다. 이번 변경은 Range locking 작업에 대한 review follow-up으로, concurrent reader가 서로 다른 두 상태에서 뽑아낸 start/end pair를 관찰할 수 있는 window를 닫습니다. 이 window가 실제로 위협이 되는지는 GC 측 reader가 synchronized region을 벗어난 뒤에도 bare node pointer를 계속 들고 있는지에 달려 있습니다.

살아있는 DOM Range는 start와 end라는 두 endpoint를 유지하며, 이 둘은 반드시 하나의 관계를 만족해야 합니다. 즉 문서 순서상 start가 end보다 앞서거나 같아야 합니다. 스크립트가 한 endpoint를 다른 endpoint 너머로 설정하면, 스펙은 range를 새로 설정된 endpoint로 collapse하도록 요구합니다. 이 repair는 두 번째 write이며, 두 write는 합쳐서 하나의 논리적 update를 이룹니다. 그 사이에 끼어드는 reader는 inverted range를 보게 되는데, 이는 코드 자체가 invalid로 취급하는 상태입니다. 이 endpoint들은 m_boundaryPointLock으로 보호되며, mutation notification이 호출하는 7개의 static boundary* helper 모두 caller가 이 lock을 들고 있다고 가정합니다. 다만 이번 commit 이전에는 그 가정이 코드상 명시되어 있지 않았습니다.

관전 포인트: 방어적 가치 측면에서 보면, marking thread가 스케줄될 수 있었던 중간 상태 window를 닫고, 명시되지 않았던 lock precondition을 이후 refactor가 조용히 빠뜨릴 수 없는 형태로 바꿔놓습니다.

Unreviewed. Addressing the review comments in the original PR.

Source/WebCore/dom/Range.cpp

Patch Details

Range.cpp 내부에서 서로 다른 두 가지 변경이 이루어졌습니다.

먼저, Range::setStart와 Range::setEnd는 더 이상 하나의 논리적 update를 두 개의 별도 Locker { m_boundaryPointLock } scope에 나누어 수행하지 않습니다. 이전 코드는 lock을 획득한 뒤 m_start(또는 m_end)를 쓰고 lock을 해제한 다음, treeOrder(makeBoundaryPoint(m_start), makeBoundaryPoint(m_end))를 평가했습니다. 그리고 range가 inverted 상태가 되었으면 다시 lock을 획득해 나머지 endpoint를 collapse했습니다. 이제는 순서 비교가 critical section 위쪽으로 옮겨졌고, 들어오는 인자(BoundaryPoint(container.copyRef(), offset))를 현재의 반대편 endpoint와 비교해 계산하며, 그 결과를 bool shouldAlsoSetEnd / bool shouldAlsoSetStart에 저장합니다. 이후 m_start.set(...)과 조건부 m_end = m_start(또는 m_start = m_end)가 하나의 critical section 안에서 함께 일어납니다. 다만 hoisting된 predicate는 여전히 반대편 endpoint를 lock 바깥에서 읽는다는 점에 유의해야 합니다. 이 patch는 write 쪽을 하나의 critical section으로 묶었을 뿐, 그 읽기 부분에 locking을 추가한 것은 아닙니다.

둘째로, 7개의 static boundary-mutation helper — boundaryNodeChildrenChanged, boundaryNodeChildrenWillBeRemoved, boundaryNodeWillBeRemoved, boundaryTextInserted, boundaryTextRemoved, boundaryTextNodesMerged, boundaryTextNodesSplit — 가 이름 없는 Locker<Lock>& 파라미터를 앞에 하나씩 갖게 되었고, 이를 호출하는 Range::nodeChildrenChanged, nodeChildrenWillBeRemoved, nodeWillBeRemoved, textInserted, textRemoved, textNodesMerged, textNodeSplit도 각자의 local locker를 전달합니다. 이는 lock discipline을 코드에 명문화하는 작업입니다. "caller는 m_boundaryPointLock을 들고 있어야 한다"는 규칙을 명시되지 않은 관례가 아니라 각 helper의 signature 일부로 만듭니다. helper 본문의 동작에는 기능적 변화가 없습니다.

여러 필드에 걸친 update가 두 개의 별도 critical section으로 쪼개져, 단일 스레드 관찰자는 도달할 수 없는 중간 상태를 concurrent reader가 관찰할 수 있게 되는 패턴.

Background

Live Range와 그 endpoint. document.createRange()로 얻는 DOM Range는 endpoint를 m_start, m_end라는 두 개의 RangeBoundaryPoint 멤버로 저장합니다. RangeBoundaryPoint는 Ref<Node> m_container, unsigned m_offset, RefPtr<Node> m_childBefore를 가지고 있으며, strong Ref를 들고 있기 때문에 boundary point가 해당 container node를 참조하는 동안 그 node는 계속 살아있게 됩니다.

Mutation notification. DOM tree가 변경되면 Document는 attach된 모든 live range에게 Range::nodeChildrenChanged, nodeChildrenWillBeRemoved, nodeWillBeRemoved, textInserted, textRemoved, textNodesMerged, textNodeSplit을 통해 알립니다. 각각의 함수는 static boundary* helper를 통해 두 boundary point를 모두 fix up합니다.

NODELETE. Range.cpp 안의 일부 helper에 붙는 annotation으로, 객체 destruction을 유발해서는 안 되는 code path를 표시합니다. 이 annotation이 붙은 helper는 정확히 offset만 조정하는 body를 가진 helper들이고, annotation이 없는 helper는 boundary의 container를 재할당합니다.

Non-thread-safe refcounting. WebCore Node의 reference count는 atomic이 아니기 때문에, 일반적으로 main thread만 이를 증가시키거나 감소시킬 수 있습니다.

GC-thread visiting. JSC의 garbage collector는 전용 marking thread에서 heap을 tracing합니다. DOM wrapper는 visitAdditionalChildrenInGCThread를 통해 이 과정에 참여하며, Range의 경우 JSRange::visitAdditionalChildrenInGCThread가 Range::visitNodesInGCThread(visitor)를 호출합니다. Opaque root는 wrapper가 collector에게 "이 native subgraph의 wrapper들을 계속 살려두라"고 알리는 메커니즘입니다.

Lock / Locker. WTF의 mutex와 그에 대응하는 RAII 방식 scoped-acquisition helper입니다. Range는 mutable Lock m_boundaryPointLock을 선언하고 있으며, Locker는 감싸고 있는 scope를 벗어날 때 lock을 해제합니다.

treeOrder. treeOrder(BoundaryPoint, BoundaryPoint)는 두 boundary point 중 어느 쪽이 문서 순서상 먼저인지를 나타내는 std::partial_ordering을 반환하며, is_lteq는 "먼저이거나 같음"을 검사합니다. DOM 스펙은 결과 range가 inverted 상태가 될 경우, setStart/setEnd가 range를 새로 설정된 endpoint로 collapse하도록 요구합니다.

Analysis

근본 원인은 lock-granularity 결함입니다. m_boundaryPointLock은 이미 존재했고 개별 write를 이미 보호하고 있었지만, 하나의 논리적인 two-endpoint update가 두 개의 critical section으로 나뉘어 수행되었고 그 사이에 unlocked gap이 존재했습니다.

  Main thread (pre-patch setStart)      Marking thread
  ────────────────────────────────      ──────────────
  Locker { lock }
    m_start.set(new)   ← drops
      m_start's OLD container ref
  } release
                                        ── scheduled here ──
                                        reads m_start (new)
                                        reads m_end   (stale)
                                        => inverted pair: a state
                                           no single-threaded
                                           caller can observe
  treeOrder(m_start, m_end) -> inverted
  Locker { lock }
    m_end = m_start
  }

어느 reference가 어디서 해제되는지는 정확히 구분해서 봐야 합니다. patch 이전 setStart에서 첫 번째 critical section의 m_start.set(...)은 m_start 자신의 이전 container reference를 해제합니다. m_end는 gap 동안 자신의 Ref<Node>를 그대로 유지하고 있다가, 두 번째 block에서 덮어써질 때 비로소 자신의 이전 container reference를 해제합니다. 따라서 gap에서 노출되는 중간 상태는 (a) inverted된 start/end pair이며, (b) m_start의 이전 container 해제이지, dangling m_end가 아닙니다. patch 이후에는 m_start에 대한 write와 m_end의 조건부 collapse가 하나의 Locker 안에서 함께 일어나므로, 어떤 reader도 그 사이에 스케줄될 수 없습니다.

여기서 문제가 되는 reader는 JSRange::visitAdditionalChildrenInGCThread가 wrapped().visitNodesInGCThread(visitor)를 호출하는 경로입니다. 즉 JSC의 marking thread가 main thread 밖에서 live Range의 boundary point를 읽는 상황입니다. GC 측 reader가 m_boundaryPointLock을 직접 잡는지 여부가 이 window의 실제 위협 수준을 결정하는데, 이번 patch는 Range::visitNodesInGCThread를 건드리지 않습니다. 따라서 진정으로 unsynchronized한 concurrent reader가 남아있는지는 이번 변경이 해결한 문제가 아니라 열린 질문으로 남습니다.

이 patch는 write 쪽 tear만 닫습니다. collapse 여부를 결정하는 predicate는 여전히 반대편 endpoint를 lock 바깥에서 읽습니다. patch 이후 setStart는 lock을 획득하기 전에 makeBoundaryPoint(m_end)를 평가하고, setEnd는 lock을 획득하기 전에 makeBoundaryPoint(m_start)를 평가합니다. 남은 형태는 "한 endpoint를 unlocked 상태로 읽은 뒤, 둘을 locked 상태로 atomic하게 write"하는 구조이지, 완전히 직렬화된 read-modify-write는 아닙니다. 이 잔여 read가 실제로 문제가 되는지는 다른 어떤 thread가 이 필드들을 쓸 수 있는지에 달려 있는데, 이 파일 안의 mutation-notification 경로는 모두 main thread에서 lock을 잡고 write를 수행합니다.

race가 실제로 이빨을 가지는 지점을 정확히 짚어볼 필요가 있습니다. 7개의 boundary helper 중 boundaryNodeChildrenWillBeRemoved, boundaryNodeWillBeRemoved, boundaryTextNodesMerged, boundaryTextNodesSplit 네 개는 NODELETE annotation이 붙어 있지 않습니다. boundaryNodeChildrenChanged, boundaryTextInserted, boundaryTextRemoved와 달리 이 네 개는 boundary의 container를 재할당하는 body를 가지고 있어 node reference를 해제할 수 있습니다. 이 구분이 곧 reference 해제, 즉 stale-pointer read가 일어날 수 있는 지점의 지도에 해당합니다.

발견 경로로 가장 가능성이 높은 것은 code review입니다. 이 변경은 이전 locking patch에 대한 review follow-up의 형태를 띠고 있습니다. 리뷰어가 setStart/setEnd가 하나의 논리적 update를 두 critical section에 걸쳐 수행한다는 점, 그리고 boundary* helper들이 lock precondition을 관례로만 유지하고 있었다는 점을 지적했을 가능성이 높습니다. 원래 locking 작업을 촉발한 race 자체는 JSC의 marking thread에서 도달 가능한 surface를 감사하면서 — 즉 visitAdditionalChildrenInGCThread 구현체를 나열하고 mutable main-thread state를 읽는지 확인하는 방식으로 — 발견되었을 수도 있고, marking thread에서 발생한 crash-report나 ThreadSanitizer signal에서 비롯되었을 수도 있습니다. 둘 중 어느 쪽인지는 여기서 특정되지 않습니다.

이 결함은 WebContent process 안에서 main(mutator) thread와 JSC의 marking thread 사이의 consistency guarantee를 약화시킵니다. 여기서 걸려 있는 가정은, GC thread에서 읽는 DOM state가 읽는 동안 immutable하거나, lock에 의해 하나의 transaction으로 직렬화되어 있어야 한다는 것입니다. 바로 m_boundaryPointLock이 보장하려던 가정입니다. 수정 전에는 unlocked gap에 스케줄된 marking thread가 하나는 갱신되고 하나는 stale한 start/end pair를 읽을 수 있었고, mutator가 첫 번째 critical section에서 해제한 node reference가 reader가 이미 bare pointer로 샘플링해둔 그 node일 수 있었습니다. unpinned node pointer만 들고 있는 reader가 실제로 존재한다면, 이 race를 안정적으로 이기는 attacker는 renderer 안에서 DOM node에 대한 cross-thread stale-pointer read를 확보하게 될 가능성이 있습니다. 다만 이 자체는 WebContent sandbox 안에 머무르며, 별도의 sandbox escape가 여전히 필요합니다.

Insight: 이번 재구성이 가능했던 이유는 predicate를 m_start의 write 이후 값이 아니라 들어오는 인자(BoundaryPoint(container.copyRef(), offset))를 기준으로 평가할 수 있기 때문입니다. 이 equivalence를 인지했기 때문에 작성자는 lock의 범위를 비교 구간까지 넓히는 대신 두 critical section을 하나로 합칠 수 있었습니다. 두 번째 변경 — Locker<Lock>&를 이름 없이 모든 helper에 관통시키는 것 — 은 lock precondition을 type 수준에서 저렴하게 인코딩하는 방법입니다. mutating helper들이 free function으로 존재하는 codebase에서는 이후 refactor가 unlocked path에서 쉽게 이 helper들을 호출할 수 있기 때문입니다. 다만 이 방식이 올바른 lock이 실제로 잡혀 있음을 증명하지는 않습니다. 그 증명은 WTF_GUARDED_BY_LOCK / assertIsHeld가 담당할 몫이지만, 적어도 call site에서 이 요구사항을 놓칠 수 없게 만듭니다.

Audit directions

• 논리적으로 원자적이어야 할 multi-field update가 두 개 이상의 critical section으로 쪼개져, 단일 스레드 caller는 도달할 수 없는 상태를 concurrent reader가 관찰할 수 있게 되는 패턴. 이 패턴이 위험한 이유는 개별 write 각각은 review 단계에서도, per-access 모델로 동작하는 race detector 관점에서도 올바르게 synchronized된 것처럼 보이기 때문입니다. 문제는 오직 그 write들의 조합에서만 드러나며, 그 중간 상태는 코드 자체가 명시적으로 invalid로 취급하는 경우가 많습니다. 좁은 범위: Source/WebCore/dom와 Source/WebCore/editing에서 같은 lock에 대해 Locker 선언이 두 번 이상 등장하는 함수, 또는 Locker scope 다음에 같은 멤버를 unlocked 상태로 읽는 코드를 검색해봐야 합니다. Range::collapse와 FrameSelection의 live-range synchronization이 이번에 변경된 코드와 바로 인접한 지점입니다. code review에서는, 하나의 invariant로 묶인 필드들 — start/end pair, pointer/length pair, buffer/capacity pair — 에 대한 write를 두 개의 lock-acquire 문장이 각각 감싸고 있는 형태가 바로 그 tell입니다. 넓은 범위: release-then-reacquire 형태의 idiom 어디에서나 같은 패턴이 나타날 수 있습니다. 내부에서 lock을 잡는 helper가 연속으로 두 번 호출되는 경우, unlockEarly() 방식의 수동 해제, 두 번째 write 전에 해제되는 scope guard 등이 그렇습니다. "predicate를 계산한 뒤 state를 repair"하는 패턴에서 그 predicate가 두 write 사이에서 평가되는지도 함께 살펴볼 필요가 있습니다. 가장 넓은 범위: concurrent tracer나 reader가 multi-field state를 오직 transaction 경계에서만 관찰해야 한다는 원칙은 V8의 concurrent marking write barrier, Go의 GC write barrier, Java의 ZGC/Shenandoah load barrier, Linux 커널의 RCU reader에도 동일하게 적용됩니다. "tracer가 field A는 state N+1에서, field B는 state N에서 관찰하는 순간이 존재하는가, 그리고 그 아래 어딘가에서 두 필드가 서로 일치한다고 가정하는 코드가 있는가"라는 질문을 함께 던져봐야 합니다.

• 두 번째 thread가 non-thread-safe한 reference counting으로 lifetime이 관리되는 자료구조를 읽는 상황이며, 원래 이 read를 안전하게 만들어줄 pinning primitive를 사용할 수 없는 경우입니다. — 이 경우 pointee를 살아있게 유지하는 유일한 장치는 owning thread가 쥐고 있는 lock뿐입니다. Owning 쪽에서 발생하는 모든 unlocked mutation은 단순한 visibility 문제가 아니라, cross-thread stale-pointer read 후보가 됩니다. Narrow: visitAdditionalChildrenInGCThread를 구현하는 WebCore 클래스들을 나열합니다 (Source/WebCore/bindings/js 전역에서 DEFINE_VISIT_ADDITIONAL_CHILDREN_IN_GC_THREAD를 검색). 각 클래스에 대해, 해당 visitor가 읽는 멤버를 건드리는 모든 mutation 경로가 이 visitor와 직렬화되어 있는지 확인합니다. 이번 commit에서 다뤄지는 인스턴스는 JSRangeCustom.cpp입니다. 여기서 가장 먼저 확인해야 할 것은 Range::visitNodesInGCThread 자체가 m_boundaryPointLock을 획득하는지 여부입니다. Wider: 다른 channel을 통해 main thread 밖에서 읽히는 모든 WebCore state로 범위가 넓어집니다. Opaque-root 계산, WebCoreOpaqueRoot helper, 그리고 Node*/Element*만 쥔 채 background thread가 sampling하는 main-thread 객체가 여기 해당합니다. ref()/deref()가 non-atomic인 타입을 dereference하는 non-main-thread 함수가 있다면, 바로 그 지점이 단서입니다. Widest: reader thread가 자신이 읽는 대상에 대해 strong reference를 확보할 수 없는 경우를 가정합니다. 이 경우 writer의 reference release는 reader의 dereference와 동일한 critical section 안에 있어야 합니다. 이 원칙은 Rust의 Rc와 Arc 구분, COM의 single-threaded apartment, 그리고 boost::intrusive_ptr와 non-atomic counter를 섞어 쓰는 C++ 코드베이스 전반에 적용됩니다.

• Lock precondition이 convention으로만 표현되는 경우입니다 — lock으로 보호되는 state를 mutate하지만, signature에는 lock에 대한 정보가 전혀 없는 free function이나 private helper가 여기 해당합니다. 나중에 추가되는 새로운 call site는 무언가를 획득해야 한다는 신호를 전혀 받지 못합니다. 그 결과 이 규율은 refactor를 거치며 조용히 무너지게 됩니다. Narrow: Source/WebCore/dom에서 static inline void boundary 형태의 free helper를 검색합니다. Lock을 쥔 클래스의 멤버에 대한 reference를 받아 mutate하면서도 Locker& 파라미터나 assertIsHeld 호출이 없는 경우가 대상입니다. 이번 commit에서 변환된 7개의 helper가 준수해야 할 형태의 template에 해당합니다. Wider: WTF Lock 사용자 중 WTF_GUARDED_BY_LOCK annotation이 빠진 guarded member가 있는지 점검합니다. 이 annotation과 Locker& 파라미터 idiom은 동일한 contract를 표현하는 두 가지 방식이며, 둘 다 사용하지 않는 클래스가 다음 unlocked path가 나타날 지점입니다. Range.h의 m_start/m_end가 구체적인 후속 점검 대상입니다. Widest: 타입에 encoding되지도, analyzer에 의해 검사되지도 않는 lock precondition은 결국 comment를 읽지 않은 어떤 caller에 의해 위반됩니다. 이는 Clang thread-safety analysis를 사용할 수 있지만 적용하지 않은 코드베이스, Java의 @GuardedBy에 모두 적용됩니다. 반대로 Rust의 Mutex<T>에서는 encapsulation 덕분에 unlocked path 자체가 표현 불가능해집니다. Code review에서는, 자신이 소유하지 않는 m_ 접두사 state를 mutate하면서도 signature에 lock 관련 근거가 없는 helper가 단서입니다. 가장 넓은 질문은 "이 함수의 새로운 caller가 아무것도 획득하지 않고도 compile될 수 있는가?"입니다.

• Write 쪽만 atomic하게 만들고, 짝을 이루는 read는 unsynchronized 상태로 남겨두는 부분적인 synchronization fix입니다. 기존 클래스에 lock이 새로 도입될 때마다, guarded member에 대한 모든 access가 lock 아래로 들어갔는지, 아니면 write만 들어갔는지 확인해야 합니다. 이번 경우 setStart의 treeOrder(..., makeBoundaryPoint(m_end))와 setEnd의 treeOrder(makeBoundaryPoint(m_start), ...)는 hoisted된 상태입니다. 두 호출 모두 여전히 Locker가 생성되기 전에 실행됩니다. Narrow: Range.cpp에 남아 있는 m_start/m_end 사용 지점을 다시 읽고, 각각을 locked 혹은 unlocked로 분류합니다. Unlocked로 분류된 지점은 다른 thread가 해당 field를 절대 쓰지 않을 때만 안전합니다. Wider: 클래스에 lock이 처음부터 설계된 것이 아니라 나중에 retrofit된 경우라면, lock 도입 이전부터 존재하던 guarded member의 read를 항상 검색해봐야 합니다. Retrofit은 대개 crash report가 가리킨 write는 커버하지만, read는 놓치는 경향이 있습니다. Widest: 보고된 race를 고치기 위해 도입한 lock은 보고된 access만을 커버할 뿐, field 전체를 커버하지 않습니다. Synchronization이 사후에 추가된 어떤 코드베이스를 보더라도 "이 field에 대한 어떤 access가 여전히 lock 밖에 있는가, 그리고 두 번째 writer가 나타나려면 무엇이 필요한가?"라는 질문을 가지고 접근해야 합니다.