Chenhao Zuo

Model DICE key equality behavior Summary: ## Motivation DICE previously represented value equality only through `Key::equality(old, new)`. Paging therefore could not determine whether an old paged-out value might be reusable without first hydrating it. Some keys always install the recomputed value, so that hydration cannot affect the update decision. ## Equality behavior Replace the equality hooks on `Key`, `ProjectionKey`, and `InjectedKey` with: ```rust enum EqualityBehavior<T> { Compare(fn(&T, &T) -> bool), AlwaysUnequal, } ``` `Compare` carries the comparator used by DICE. `AlwaysUnequal` expresses that no comparison can reuse the old value. Keeping the policy and comparator in one enum prevents separate declarations from diverging. ## Implementation - Migrate existing equality implementations to `EqualityBehavior::Compare`. - Mark keys with unconditionally false equality as `EqualityBehavior::AlwaysUnequal`. - Forward the behavior through injected keys and erased key and projection values. This diff only exposes the equality policy; it does not change page-in behavior. The dependent diff uses the policy to skip hydration whose result cannot affect DICE value selection. Reviewed By: JakobDegen Differential Revision: D115785700 fbshipit-source-id: ff96564d46310f27dc545687a48d7478d9a10ecf

Reuse resident heaps during page-in Summary: This completes the shared-heap paging fix started by the previous diff. In the X/Y example, after X is paged out and evicted, Y may still keep heap A alive. When X is paged back in, reconstructing a second allocation of A would give both allocations the same `HeapRefId`. A subsequent page-out can register the chunks of one allocation and then hit the pointer-not-found panic when it serializes a value from the other. Track each registered heap as a weak `HeapRefId` to `FrozenFrozenHeap` association. Page-in reuses A when Y still keeps it alive and resolves the serialized `value_index` for X through the existing chunk index for A, while still consuming the serialized heap body to keep the deserializer cursor aligned. If A is no longer resident, the existing lazy heap reconstruction path remains unchanged. Pointer-identity-checked cleanup prevents an older allocation from unregistering a newer resident entry with the same ID. Reviewed By: christolliday Differential Revision: D113883882 fbshipit-source-id: 4b4345dbbe733ae68e7addc8bd1d5dba991db45a

Page matched values in only on demand Summary: ## Motivation A lookup that finds a key valid at the requested version returns `Match`. When that key's value is paged out, the worker read it back from disk before completing — every time, whether or not anyone wanted the payload. The dominant caller does not: `check_dependency` reads only `versions()` and `invalidation_paths()`, both of which travel beside the value. So an incremental build that revalidates a paged-out graph pays a page-in per key it merely proves unchanged. The blocker is not the lookup, which can already describe a paged-out value; it is that a key has exactly one task per version, whose result slot is a write-once `OnceLock`. A task that completes without a payload leaves a later caller nowhere to put one. ## The page-in lane Give a key a second task table. `SharedCache` gains `page_in_storage` beside `storage`, and `TaskLane` picks between them: ``` VersionEpochState::bring_up_to_date(key) // TaskLane::UpToDate: leaves a paged-out value on disk VersionEpochState::page_in(key, ..) // TaskLane::PageIn: reads it back ``` A task's `TaskGoal` says which it is. `UpToDate` is the old flow minus the `Match` hydration. `PageIn` reads exactly the `DataKey` its caller observed rather than re-deriving it from the graph: re-deriving could land on `Compute` and recompute a key whose task for this version has already finished, which would break DICE's one-computation-per-key-version guarantee. Only a *read failure* falls through to the normal path, so a page-in that cannot be read still recovers by recomputing, exactly as before. A page-in task reports no activation, so that recovery cannot push the key into the critical-path graph twice. Being a real task is what gives the read what it needs: it is deduplicated across callers, it is cancelled with its transaction, and it can recompute on failure. The new table is wired into `is_cancelled`, `cancel_pending_tasks` (both the insert barrier and the cancel-and-collect loop, which is what `Dice::is_idle` reads) and `iter_tasks`. ## Demanding the payload Two places consume a key's payload, and both now ask for it explicitly: `ComputeCtx::compute_opaque`, and the projection arm of `TransactionData::evaluate`, which computes a projection *from* its base's value and so cannot make do with version metadata. `VersionEpochState::compute_opaque` is renamed `bring_up_to_date` to say what it does and what it does not do. It is the only entry point whose result may lack a payload, and `check_dependency` is the only caller that legitimately stops there. ## Telemetry `PageInPhase::Match` becomes `PageInPhase::Demanded`: a page-in on this path is no longer "the key happened to be an exact match" but "a caller asked for the payload". The buck2 critical-path topology is unchanged — such a page-in still has no activation of its own, so it emits `key -> PageIn(key)` immediately rather than pairing with one. ## Future size `compute_opaque` grows by one word (`words_of_async_fn_future!` assertions in `api/computations.rs` and `buck2_build_api`): the branch is inline, but the page-in future behind it is boxed and out of line, so only the branch is paid for on the resident path. Reviewed By: christolliday Differential Revision: D116412953 fbshipit-source-id: b7a608df21dfe0ec260359f603c6d02188f004f1

Improve SQLite page-out size errors Summary: ## Motivation SQLite reports oversized page-out rows as only `string or blob too big`. This does not identify the affected serialized value or show the connection limit, making the failure difficult to diagnose. ## Implementation Group the immutable writer insertion settings in `SqliteInsertConfig`. When SQLite returns `ErrorCode::TooBig`, preserve the original error and attach the failed batch size, largest `DataKey`, its IEC and exact byte sizes, and the active `SQLITE_LIMIT_LENGTH`. Other SQLite errors retain their existing behavior. Use the existing `bytesize` crate for IEC formatting and cover the diagnostic with a real SQLite connection configured with a small length limit. Reviewed By: christolliday Differential Revision: D117563634 fbshipit-source-id: d58ae74fb5bcb3aaa10bb8120f78d3eee7de7192

Cross-process pagable ser/de for BcInstrs Summary: `BcInstrs` is a packed `Box<[u64]>` of `BcInstrRepr` records with embedded `FrozenValue`s; copying the raw words is unsound across processes because the pointers don't relocate. Give `BcInstrs` a manual `StarlarkSerialize`/`StarlarkDeserialize` that walks the instruction stream and routes each instruction's `I::Arg` through its own ser/de, so embedded `FrozenValue`s relocate via the normal mechanism. Wire format: a u8 tag followed by a `(u32 opcode, arg)` stream terminated by `End`. `'static`-backed args re-resolve on read instead of being serialized (`BcNativeFunction` from its frozen value, `KnownMethod` by name); `BcOpcode` serializes as a u32 (there are >256 opcodes). This unblocks paging any `FrozenDef`. Reviewed By: christolliday Differential Revision: D108842732 fbshipit-source-id: acc9b5836a003e287ffe2341b58a2b73a19679f2

Share heap state across page-out calls Summary: This is the first half of the fix for a paging lifecycle that can leave two live `FrozenFrozenHeap` allocations with the same `HeapRefId`. Suppose DICE values X and Y both own values in heap A. Paging out X registers A in a temporary page-out context; X can then be evicted while Y keeps A alive. Paging X back in uses the storage context, which cannot see that registration and may reconstruct a second allocation of A. A later page-out can encounter both allocations; registration is deduplicated by `HeapRefId`, so the chunk index describes only one allocation and serializing a pointer from the other panics because it cannot be found. Make DICE page-out use the `PagableStorage` session context also used by page-in, including for recursively serialized arcs, so heap registration survives across paging operations. Because this state is now long-lived, weakly associate each registered heap with the shared `StarlarkSerState` and unregister its exact chunk bases when it drops. This provides the persistent, lifetime-safe resident-heap registry used by the next diff to prevent a duplicate allocation from being reconstructed. Reviewed By: christolliday Differential Revision: D113883883 fbshipit-source-id: 15242648365159dc876c6cdb7c693854be1b94a9

Attribute demanded page-ins to their waiters Summary: ## Motivation Dependency validation can now reuse a key while leaving its payload paged out. If another key later demands that payload, the paged-in key may already be present in the critical-path graph, so pushing it again creates a duplicate `NodeKey` and loses the identity of the evaluation that actually waited for the read. Page-in tasks are also deduplicated across callers. Storing one `demanded_by` value on the shared worker attributes the read only to the caller that created the task and misses any callers that join it while it is pending. ## Attribute the physical read to every waiter Separate the two facts that deduplication previously collapsed: - `key_paged_in` reports the successful physical hydration once and supplies its duration. - `key_page_in_waited` reports each evaluation whose PageIn lookup returned `Pending` or `NeedsRestart`. A finished lookup and a top-level demand report no waiter. Build signals represent a shared read as: ``` P --\ PageIn(K) -> K Q --/ ``` The receiver indexes waited-on keys by waiter and successful PageIn nodes by paged-in key. When a waiter's evaluation arrives, only the dependencies that waiter actually awaited are routed through the canonical `PageIn(K)` node. Other dependents retain their direct edges, and a failed hydration cannot create an edge to a nonexistent PageIn node. Dependency validation no longer performs a page-in, so remove `PageInPhase::AfterDependencyValidation` and its obsolete critical-path topology. The remaining phases are `Demanded` and `AfterRecompute`. ## Performance The ordinary `UpToDate` path passes a monomorphized empty callback, with no allocation or dynamic dispatch. Each actual waiter adds one signal and expected O(1) set insertion. A physical read creates one canonical `PageIn` node shared by all waiters, and dependency splicing remains linear in the evaluated waiter's dependency count. ## Review Guide 1. `ActivationTracker` separates per-waiter notification from physical page-in completion. 2. `VersionEpochState::run` invokes the waiter callback only for `Pending` and `NeedsRestart`; `DiceTaskWorker` keeps only the physical PageIn input. 3. `BuildSignalReceiver` joins waiter relationships with successful completions and rewrites each waiter's dependency edge. 4. Unit and concurrent paging tests cover multiple page-ins per waiter, multiple waiters per read, failed hydration, and one physical completion. Reviewed By: christolliday Differential Revision: D116412957 fbshipit-source-id: 4d002f3d309c46843161cd86e9e91d0322e96ce8

Reuse DataKeys during concurrent page-out Summary: ## Motivation `page_out_item` checked an Arc's `data_key` before serialization. Another page-out could associate the same `PartialPagableArc` with a stored representation after that check, causing the first page-out to attempt an unsafe reserialization and fail even though the canonical data was already available. It solve the errors like this https://fburl.com/scuba/buck2_page_outs/kulu292c ## Serialization Outcome `ArcSerializeOutcome` distinguishes a newly `Serialized` payload from `ReuseDataKey`. `PartialPagableArc::serialize_inner` returns the existing key instead of serializing a potentially partial value, while ordinary Arc implementations report that they wrote their payload. Page-out treats the reused key as success, while genuine serialization errors still propagate. The inline `TestingSerializer` rejects `ReuseDataKey` because its format cannot encode external storage references. The in-memory paging backend reuses the key directly. ## Implementation - Thread the typed outcome through `ArcErase` and `ArcEraseDyn`. - Teach storage callers to consume `ReuseDataKey`. - Add a deterministic regression test that pauses after an initial missing-key observation, lets another page-out store the same Arc, then verifies both operations resolve to the same `DataKey`. Reviewed By: christolliday Differential Revision: D117590400 fbshipit-source-id: fe320ef0156f45034850a71ce9798c6ee1a7df79

wait for in-progress slots to fix concurrent/cyclic sentinel access Summary: Partial deserialization (110) allocates each value's header with a sentinel vtable and fills it in lazily. When a slot is mid-deserialization, `ensure_initialized` handed back that not-yet-materialized value; using it then panics with "accessing a frozen value that has not been deserialized yet" (the sentinel vtable in `values/traits.rs`). This shows up during concurrent DICE page-in, where one `buck2-rt` worker hashes a value (e.g. as a SmallMap key) while another worker is still deserializing it. The `ClaimResult::InProgress` path now blocks on the claimer (`wait_for_slot` / `wait_for_init` on a per-slot condvar) and reads the materialized value, instead of returning the sentinel pointer. To avoid deadlocking on a genuine cycle — a same-thread re-entry or a cross-thread cycle — a `WaitForGraph` (the `claimers` / `waiters` edges walked by `has_cycle`) detects when blocking would deadlock and returns the sentinel only in that unavoidable case. The per-claim and per-wait edges are tracked with RAII guards so every exit path unwinds them exactly once. Adds `test_cross_thread_cycle_does_not_deadlock`, which concurrently deserializes a cross-referencing cycle (`a = [b]; b = [a]`) on two threads and asserts the round-trip neither deadlocks nor panics. Also adds `test_concurrent_page_in_does_not_hash_sentinel_key`, a regression for the sentinel-hash above — one thread hashes a key while another is still deserializing it (setup explained in the test's comment). Reviewed By: christolliday Differential Revision: D107338958 fbshipit-source-id: 14f7307a26b13fca48f130bf33f69cdbd77b4e3a

Unify paged-out lookup results Summary: ## Motivation Graph lookup encoded two independent dimensions as a cross product: `Match` versus `CheckDeps`, and resident versus paged-out payloads. The resulting four variants duplicated version and invalidation metadata, forced `DiceComputedValue` to require its payload to be paged in, and made the worker reunify the same logical result before it could act on it. ## Representation Introduce `MaybeResident<V>` and make payload residency part of `DiceComputedValue` and `VersionedGraphResultMismatch`. `VersionedGraphResult` now describes only the logical lookup outcome, while the payload independently records either the resident value or its `DataKey`. The worker still pages values in at the same points as before, including after successful dependency validation. Full-value consumers explicitly state that task results are resident, and the core graph-update boundary remains resident-only in this commit, so runtime behavior does not change. ## Implementation - Collapse `MatchPagedOut` into `Match` and `CheckDepsPagedOut` into `CheckDeps`. - Let `OccupiedGraphNode::computed_val` report either resident or paged-out payload state. - Replace unconditional `DiceComputedValue::value()` access with residency-aware accessors. - Remove the worker's parallel `CheckDepsCandidate` representation while preserving its existing page-in policy. Reviewed By: christolliday Differential Revision: D116412955 fbshipit-source-id: 89621a4fc6d6b1c34f320a9f1f2b366aaec4a115