ReviewOS

zig-utils/zig-js

Strings: randomize intern-table shard and bucket placement

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

Parents: #473, #493 Related: #495, #531, #763

Problem

strcell.InternTable uses the deterministic StringCell XXH3 content hash to choose one of 16 locks, then stores host/runtime-controlled bytes in a default-seeded string map. The stable content hash is required for compile-time/runtime cell compatibility, but exposing it as the placement function lets an adversary precompute both shard contention and collision-heavy bucket placement for private atomic-string and future shared-interning paths.

Scope

  • Preserve the existing deterministic StringCell content hash, classification bits, exact equality, canonical pointer identity, and compile-time/runtime compatibility.
  • Add a separate lazy per-InternTable unpredictable placement context and use it for both shard selection and native-map bucket placement.
  • Publish the placement context only after the first successful canonical insertion; entropy or allocation failure must leave no seed, map entry, cell, or owned bytes behind and must permit an exact retry.
  • Coordinate concurrent first insertion with an atomic initialization state so every shard observes one context without a data race or process-global fallback.
  • Keep lookup/insertion to one placement-hash computation by retaining that hash with each exact-byte owned key.
  • Preserve empty/count-only laziness and the existing 16-way lock granularity.

No-workaround rules

  • No deterministic fallback seed, process-global intern seed, content-hash semantic change, reduced shard count, input cap/blacklist, hash-only equality, disabled interning, or swallowed OOM.
  • No stack, queue, job, Promise, Worker, or Map/Set iterator implementation changes.

Acceptance

  • Equal bytes converge to one cell across threads while independent tables use independent secure placement contexts.
  • Empty, duplicate, embedded-NUL, non-Latin-1, 4 KiB, caller-mutation, and concurrent-first-insert cases preserve exact behavior.
  • Entropy and every first-insert allocation failure leave the table unseeded/empty and leak-free; retry succeeds.
  • Focused normal and TSan tests pass with zero leaks/races, including collision/shard distribution witnesses.
  • Exact-parent string/C/private ABI fixtures and relevant Test262 subtrees have nonzero accounting and zero regressions.
9 days ago

Implemented and pushed in fix(strings): randomize intern table placement (#764). StringCell content identity remains deterministic, while each InternTable now owns one lazy secure placement context shared by shard and bucket selection. Entropy and all four first-insert allocation failures are transactional and retryable; duplicate hits allocate zero times. Focused normal/TSan strcell tests pass 16/16 with zero leaks/races; exact-parent valuebox 3/3, private egress 1/1, Home 392/392, C/JSC 34/34, and Test262 built-ins/String 1,223/1,223 all pass with 0 flips.

Sign in to comment on this issue.