ReviewOS

zig-utils/zig-js

Arrays: securely seed sparse hole indexes

#853
Closed chris opened this 9 days ago ·
9 days ago

Parents: #493, #478, #480 Related: #759, #762, #851

Problem

Dense Array hole bookkeeping uses std.AutoHashMapUnmanaged(usize, void). Zig hashes the exact integer bytes with fixed Wyhash seed 0, while JavaScript can select deleted dense indices below the engine dense cap (2^24). An attacker can therefore precompute same-bucket index families and force collision-heavy native probes behind indexed reads, writes, deletes, enumeration, and Array methods.

Scope

  • Replace the default-context hole set with an exact-integer keyed index using one unpredictable context per sparse-array sidecar.
  • Derive the seed from the owning Array Shape entropy source and store it only in the existing cold sidecar allocation; do not enlarge hot Object state.
  • Use the context for every contains, insert, remove, clear, and finalization path.
  • Publish the sidecar only after the first insertion succeeds; entropy or allocation failure must expose neither an index nor a context.
  • Preserve dense/sparse transitions, elisions, deletion/fill/truncation semantics, enumeration order, backing ownership, moving/concurrent GC, shared-realm locking, OOM behavior, and VM/tree-walker parity.

No-workaround rules

  • No array-length/index cap reduction, deleted-index rejection, deterministic/public/address/time-derived fallback seed, hash-only equality, linear scan presented as hardening, global mutable seed, per-hole entropy request, or retained dead entries.
  • No unrelated named-property, collection, typed-array, public/private ABI, or Array semantic change.

Acceptance

  • Every dense-hole lookup and mutation uses one installed Shape-derived exact-integer context.
  • A fixed-seed default collision family disperses under a keyed context while exact index equality is preserved.
  • First entropy/allocation/insertion failure publishes no hole sidecar/context; retry succeeds normally.
  • Array elision/delete/fill/truncate/enumeration and moving/concurrent GC tests pass in Debug, ReleaseSafe, and TSan/no-GIL coverage.
  • Exact-parent Array Test262 inventory has nonzero accounting and zero regressions; required-VM parity has zero new divergence.
  • Full unit and threadfuzz gates pass.
9 days ago

Implemented and pushed to main in 0a5d1f70.

Evidence:

  • deterministic collision and exhaustive allocation-failure/retry tests: 2/2 Debug
  • hole/elision/deletion coverage: 9/9 Debug and 9/9 ReleaseSafe
  • structured clone: 10/10 Debug
  • Array inventory: 77/77 Debug and 77/77 TSan
  • direct shared-realm delete/probe/fill witness: 1/1 Debug and TSan, no race report
  • full unit suite: 2,262 pass, 1 platform skip, 0 fail, 0 leak across 2,263 tests
  • threadfuzz: 400 programs, 0 failures
  • exact-parent Test262: Array 3,081 plus array expressions 52; 3,133 pass and 0 fail on both revisions, byte-identical logs
  • required-bytecode parity: 3,133 agree, 0 diverge
  • public C API: 117/117 complete; Home private ABI: 447 implemented, 0 pending; 392/392 runtime shims passed

Sparse dense-hole membership now uses one Shape-derived exact-integer context in the existing cold sidecar. The sidecar is published only after its first insertion succeeds, and the hot Object layout is unchanged.

Sign in to comment on this issue.