88 lines
2.9 KiB
Markdown
88 lines
2.9 KiB
Markdown
# UNDF: UNDF-2026-000000433
|
||
# JSC-0001: BytecodeBasicBlock::computeImpl() O(B²×T) edge linking via Vector::contains
|
||
|
||
**File:** `Source/JavaScriptCore/bytecode/BytecodeBasicBlock.cpp`
|
||
**Lines:** 181–193 (branch block linking loop)
|
||
**Severity:** HIGH
|
||
**CWE:** CWE-407 (Inefficient Algorithmic Complexity)
|
||
|
||
## Description
|
||
|
||
`BytecodeBasicBlock<OpcodeTraits>::computeImpl()` links bytecode basic
|
||
blocks to their successors. For branch instructions (including switch),
|
||
it collects jump targets into a temporary `Vector<Offset, 1>` called
|
||
`bytecodeOffsetsJumpedTo`, then walks every basic block in the function
|
||
checking membership:
|
||
|
||
```cpp
|
||
// line 181
|
||
Vector<typename InstructionStreamType::Offset, 1> bytecodeOffsetsJumpedTo;
|
||
findJumpTargetsForInstruction(codeBlock, instruction, bytecodeOffsetsJumpedTo);
|
||
|
||
size_t numberOfJumpTargets = bytecodeOffsetsJumpedTo.size();
|
||
for (auto& otherBlock : basicBlocks) { // O(B)
|
||
if (bytecodeOffsetsJumpedTo.contains(otherBlock.leaderOffset())) { // O(T)
|
||
linkBlocks(block, otherBlock);
|
||
--numberOfJumpTargets;
|
||
if (!numberOfJumpTargets)
|
||
break;
|
||
}
|
||
}
|
||
```
|
||
|
||
This entire nested scan runs for every branch block in the function.
|
||
With B basic blocks and T switch targets per branch:
|
||
|
||
- Outer loop (line 137): O(B) iterations over all blocks
|
||
- For each branch block: inner loop O(B) × `Vector::contains` O(T)
|
||
- Total: **O(B² × T)**
|
||
|
||
For a large function with a 1 000-case switch (T=1000) and 200 basic
|
||
blocks (B=200):
|
||
- Slow path: 200 × 200 × 1000 = **40 000 000 comparisons**
|
||
|
||
`Vector::contains` on line 187 is a linear scan
|
||
(`std::find` under the hood) — confirmed by WebKit's `Vector.h`.
|
||
|
||
## Fix
|
||
|
||
Before the inner loop, insert the jump targets into a `HashSet<Offset>`,
|
||
then replace `bytecodeOffsetsJumpedTo.contains(...)` with
|
||
`jumpTargetSet.contains(...)` — O(1) per lookup.
|
||
|
||
```cpp
|
||
HashSet<Offset> jumpTargetSet;
|
||
for (auto offset : bytecodeOffsetsJumpedTo)
|
||
jumpTargetSet.add(offset);
|
||
|
||
for (auto& otherBlock : basicBlocks) {
|
||
if (jumpTargetSet.contains(otherBlock.leaderOffset())) {
|
||
linkBlocks(block, otherBlock);
|
||
...
|
||
}
|
||
}
|
||
```
|
||
|
||
`HashSet` is `WTF::HashSet`, already imported in BytecodeBasicBlock.cpp.
|
||
|
||
## Complexity
|
||
|
||
| Scenario | Before | After |
|
||
|----------|--------|-------|
|
||
| Single branch (T targets, B blocks) | O(B×T) | O(B + T) |
|
||
| Full function (B branches, B blocks, T targets) | O(B²×T) | O(B×(B+T)) |
|
||
| 200 blocks × 1000-case switch | 40 000 000 ops | 200 200 ops |
|
||
|
||
**Speedup:** ~200× for 1000-case switch in 200-block function
|
||
|
||
## Affected Callers
|
||
|
||
- `BytecodeBasicBlock<JSOpcodeTraits>::compute(CodeBlock*, ...)`
|
||
- `BytecodeBasicBlock<JSOpcodeTraits>::compute(UnlinkedCodeBlockGenerator*, ...)`
|
||
- Used by DFG JIT, liveness analysis, register allocation — called every
|
||
time a function is compiled
|
||
|
||
## References
|
||
|
||
- `WTF/HashSet.h` — already in scope via `config.h`
|
||
- `JSC/bytecode/BytecodeBasicBlock.h` — `PredecessorList` typedef
|