turbo-tasks-gc: Defer most aggregation graph management until after GC has settled by lukesandberg · Pull Request #98591 · vercel/next.js

lukesandberg · 2026-09-11T23:52:54Z

Fix AggregationGraph updates during GC.

During GC we aremoving a lot of edges so this can trigger a lot of aggregation graph churn. Because of the highly parallel nature of GC this can end up with multiple queues fighting over updates which can exceed various retry limits and lead to things like trying to turn nodes into followers that are actively being deleted.

Instead we just don't rebalance the aggregation graph during GC, instead we buffer every rebalance request and set the optimize budget to zero. Then after GC settles we process all the rebalances at once, taking care to filter out any tasks that have been since deleted.

Because GC is only removing edges it can lead to inefficient graphs (too many interior nodes) but not violate graph invariants.

Alternatives considered:

The initial idea was to ensure GC had finished with all 'children' of the node before processing rebalance requests, but this was only a partial solution (and complex!), since it didn't handle the case of an aggregating node having multiple children become collectible in the initial scan, this could still trigger 'optimization contention' and turning dead nodes into followers.

github-actions · 2026-09-11T23:53:13Z

Failing test suites

Commit: 31c5333 | About building and testing Next.js

pnpm test-dev-turbo test/development/app-hmr/hmr.test.ts (turbopack) (job)

app-dir-hmr > filesystem changes > can navigate cleanly to a page that requires a change in the Webpack runtime (DD)

Expand output

● app-dir-hmr › filesystem changes › can navigate cleanly to a page that requires a change in the Webpack runtime

expect(received).toEqual(expected) // deep equality

Expected: ArrayContaining [{"message": StringContaining "[Fast Refresh] done in", "source": "log"}]
Received: [{"message": "%cDownload the React DevTools for a better development experience: https://react.dev/link/react-devtools font-weight:bold", "source": "info"}, {"message": "[HMR] connected", "source": "log"}, {"message": "Next.js page already hydrated", "source": "log"}]

  192 |       const logs = await browser.log()
  193 |       // TODO: Should assert on all logs but these are cluttered with logs from our test utils (e.g. playwright tracing or webdriver)
> 194 |       expect(logs).toEqual(
      |                    ^
  195 |         expect.arrayContaining([
  196 |           {
  197 |             message: expect.stringContaining('[Fast Refresh] done in'),

  at Object.toEqual (development/app-hmr/hmr.test.ts:194:20)

vercel

Additional Suggestion:

GC-collected (soft-deleted) transient tasks are never physically removed from the resident map because the eviction retain loop's is_transient() early-return runs before the flags.deleted() removal branch, leaking tombstoned transient entries for the life of the session.

Enabling GC on CI surfaced ~14.5k panics from the aggregation graph. Three related fixes: - `followers` is no longer a collectibility pin. A follower is an *outgoing* edge, so it says nothing about whether anything still reaches this task; only `upper` (incoming) does. Treating it as a pin made any task that had grown a follower during aggregation-graph reorganization permanently uncollectible. - Defer rebalance work until the parallel collect phase is quiescent. Running `balance_edge` while other workers were still collecting could add aggregation edges to a task that had just been soft-deleted. The deferred state is now the balance edges themselves rather than whole queues, and the queues GC collects with refuse optimizations outright: optimizing only raises an aggregation number to shrink fan-out, which is regenerable via `optimization_pending`, unlike `balance_edge`, which restores an invariant. - Guard the aggregation-edge add sites against deleted tasks, so a sibling cascade cannot resurrect edges on a tombstone. Also deepens the GC test fixture: the previous graph was too shallow to build interior aggregation nodes, which is why none of this was caught by existing coverage. The fixture now recurses to a configurable branching factor with a retained top layer, so collection happens under a live root -- the common case. Drops `GC_UNOWNED_ENTRY_REF`. Now that `ConnectChildOperation::run` pins every parentless child, the bit distinguished nothing that a plain refcount does not. Includes a rename of `GcStats` to `GcPassOutcome` and a revert of incidental formatting churn in the napi bindings. Co-Authored-By: Claude Opus 5 (1M context) <noreply@anthropic.com>

lukesandberg · 2026-09-13T19:18:24Z

+// TREE shape: a `BRANCHING`-ary tree of `subtree` nodes over `width` leaves. Bumping the
+// generation disconnects the whole previous tree.
+//
+// The depth matters. A node's `distance` is `children.ilog2() * 2` and, while a parent is still a
+// leaf, its children start at `parent_effective + 3` — so `effective` climbs down the levels and
+// crosses `LEAF_NUMBER` (16), which is the transition that turns a node's children into
+// `followers`. The previous flat root -> intermediate -> leaf shape never crossed it and so
+// produced *no follower edges at all*, leaving the aggregation-rebalance half of a collect
+// completely unmeasured.
+


simplify comment

lukesandberg · 2026-09-13T19:21:39Z

+/// generation bump and re-executes with new children. This reproduces the common real shape —
+/// a live parent whose children are collected out from under it — where sibling children go
+/// garbage together, are found independently by the shard scan, and are collected concurrently
+/// while both mutate this parent's aggregation state.


simplfiy comment

lukesandberg · 2026-09-13T19:22:35Z

+    /// Refuse every optimization, so `optimize_queue` stays empty and each request is recorded on
+    /// its task's `optimization_pending` flag instead.
+    ///
+    /// GC sets this on the queues it collects with. Optimizing raises a task's aggregation number
+    /// to shrink its fan-out, which is a shape improvement rather than something the graph's
+    /// correctness depends on -- unlike `balance_edge`, which restores the upper/follower
+    /// invariant after a number changes. Collection only removes nodes, so an optimization it
+    /// triggers is regenerable work that the next operation to touch the task can do, and
+    /// dropping it keeps the deferred state to balance edges alone.
+    no_optimizations: bool,


setting optimizations_executed to max does introduce an overflow risk but we have good coverage in CI and it is intuitive behavior

we can simply set it to the Max value which is far less than usize max mitigating all concerns

lukesandberg · 2026-09-13T20:30:57Z

+    /// `balance_queue`, then `optimize_queue` — so once the first two are empty everything that
+    /// remains rebalances the graph rather than tearing edges out of it. GC uses this to stop at
+    /// that boundary and defer the rest until the parallel collect is quiescent.
+    pub fn only_rebalance_remains(&self) -> bool {


needs to be pub?

also the comment can be much simpler, the fact that the queue drains in a particular order is an implementation detail not something the caller should care about

maybe this function shouldn't exist?

lukesandberg · 2026-09-13T20:32:03Z

+            if ctx.task(upper_id, TaskDataCategory::Meta).deleted()
+                || ctx.task(task_id, TaskDataCategory::Meta).deleted()
+            {
+                continue;


if only one is deleted should we consider enqueueing an optimize task?

lukesandberg · 2026-09-13T20:32:25Z

+    /// GC variant: tears down `outdated` and drains only the edge-removal work, returning the
+    /// queue with its rebalance (`balance_edge` / `optimize`) jobs still pending.
+    ///
+    /// GC accumulates this remainder across the whole parallel phase and drains it once collection
+    /// is quiescent: collection only removes nodes, and every removal path is correct on its own,
+    /// but `balance_edge` *adds* edges, which is unsafe while other workers are still deleting
+    /// tasks. See `TurboTasksBackend::gc_collect`.
+    pub fn run_edges_only(


run_edge_deletions_only

lukesandberg · 2026-09-13T20:32:49Z

+                                let parent_is_transient = task_id.is_transient();
+                                let mut removed_durable = SmallVec::<[TaskId; 4]>::new();
+                                let mut removed_transient = SmallVec::<[TaskId; 4]>::new();
                                for child_id in children.iter() {
-                                    if task.remove_children(child_id) && !child_id.is_transient() {
-                                        removed_persistent_children.push(*child_id);
+                                    if task.remove_children(child_id) {
+                                        if parent_is_transient || child_id.is_transient() {
+                                            removed_transient.push(*child_id);
+                                        } else {
+                                            removed_durable.push(*child_id);
+                                        }
                                    }
                                }
-                                // Each removed persistent child loses a parent.
-                                if !removed_persistent_children.is_empty() {
-                                    let job = if task_id.is_transient() {
-                                        AggregationUpdateJob::AdjustTransientRefCount {
-                                            task_ids: removed_persistent_children,
-                                            delta: -1,
-                                        }
-                                    } else {
-                                        AggregationUpdateJob::AdjustParentCount {
-                                            task_ids: removed_persistent_children,
-                                            delta: -1,
-                                        }
-                                    };
-                                    queue.push(job);
+                                if !removed_durable.is_empty() {
+                                    queue.push(AggregationUpdateJob::AdjustParentCount {
+                                        task_ids: removed_durable,
+                                        delta: -1,
+                                    });
+                                }
+                                if !removed_transient.is_empty() {
+                                    queue.push(AggregationUpdateJob::AdjustTransientRefCount {
+                                        task_ids: removed_transient,
+                                        delta: -1,
+                                    });


is this in the right PR? does it belong in gc-10-predicates?

lukesandberg · 2026-09-13T20:33:36Z

+            // parentless child (resurrecting a soft-deleted task, forcing the root aggregation
+            // number, scheduling it if it has no output).
+            let mut child_task = ctx.task(child_task_id, TaskDataCategory::Meta);
+            child_task.add_entry_ref();


wrong PR? should this be in the gc-10-predicates since it is about fixing transient collection?

lukesandberg · 2026-09-13T20:34:10Z

+                // including a transient child, whose incoming edges can never outlive the
+                // session no matter what kind of parent holds them.
+                if parent_is_transient || child.id().is_transient() {
+                    child.update_and_get_transient_ref_count(1);


lukesandberg · 2026-09-13T20:35:28Z

+    /// `(upper, task)` edges needing a `balance_edge`, held back from the parallel collect and
+    /// run once it is quiescent. See [`TurboTasksBackend::gc_collect`].
+    ///
+    /// A set, so the repeated rebalances of a shared edge collapse. Deferred optimizations are not
+    /// carried here: they are flushed to their task's `optimization_pending` flag instead, which
+    /// keeps this to plain data with no queue budget to reconcile. Not a statistic — this is the
+    /// pass's deferred work list, like `deleted_roots`.


simplify comment

Suggested change

/// `(upper, task)` edges needing a `balance_edge`, held back from the parallel collect and

/// run once it is quiescent. See [`TurboTasksBackend::gc_collect`].

///

/// A set, so the repeated rebalances of a shared edge collapse. Deferred optimizations are not

/// carried here: they are flushed to their task's `optimization_pending` flag instead, which

/// keeps this to plain data with no queue budget to reconcile. Not a statistic — this is the

/// pass's deferred work list, like `deleted_roots`.

/// Aggregation rebalance requests that were deferred from the main GC loop.

lukesandberg · 2026-09-13T20:35:47Z

        }
+        // merge into the larger set and keep that one
+        if other.deferred_balance_edges.len() > self.deferred_balance_edges.len() {
+            std::mem::swap(


should we do this same swap for the deleted_roots?

lukesandberg · 2026-09-13T20:37:05Z

+                // Tear the edges down now and hold the rebalance back. Collection only *removes*
+                // nodes and edges, and every removal path (dropping an upper edge, un-applying
+                // aggregated data, cascading into a follower's followers) is correct on its own.
+                // Rebalancing is the one part that *adds* edges — `balance_edge` converts follower
+                // edges to upper edges and adopts a task's followers — which is a shape
+                // optimization for later queries, not something deletion requires. Running it
+                // concurrently with collection is what produced edges pointing at tasks another
+                // worker had already deleted, so it is accumulated here and drained once the
+                // parallel phase is quiescent.


Suggested change

// Tear the edges down now and hold the rebalance back. Collection only *removes*

// nodes and edges, and every removal path (dropping an upper edge, un-applying

// aggregated data, cascading into a follower's followers) is correct on its own.

// Rebalancing is the one part that *adds* edges — `balance_edge` converts follower

// edges to upper edges and adopts a task's followers — which is a shape

// optimization for later queries, not something deletion requires. Running it

// concurrently with collection is what produced edges pointing at tasks another

// worker had already deleted, so it is accumulated here and drained once the

// parallel phase is quiescent.

// Delete outgoing edges but don't update the aggregation graph yet.

// To avoid accidentally rebalancing on deleted tasks due to racing deletions,

// we defer all rebalancing to the end

lukesandberg · 2026-09-13T20:38:20Z

+        // The parallel phase is done, so the graph is quiescent and rebalancing it is safe.
+        // Folding the per-worker accumulators into one queue collapses the repeated rebalances of
+        // shared edges (`balance_queue`/`optimize_queue` are ring *sets*) and keeps a single
+        // optimization budget.
+        //
+        // This runs before `gc_scan_roots` on purpose: rebalancing moves `upper` edges, and
+        // `gc_is_root` reads them, so classifying roots first would read a stale shape.
+        //
+        // NOTE: this drain is single-threaded and scales with the amount of garbage, so it is a
+        // latency risk on a large collection. Left unbounded for now; the existing
+        // `optimization_pending` mechanism is how a bound would defer the remainder.
+        let deferred = std::mem::take(&mut stats.deferred_balance_edges);
+        if !deferred.is_empty() {


Suggested change

// The parallel phase is done, so the graph is quiescent and rebalancing it is safe.

// Folding the per-worker accumulators into one queue collapses the repeated rebalances of

// shared edges (`balance_queue`/`optimize_queue` are ring *sets*) and keeps a single

// optimization budget.

//

// This runs before `gc_scan_roots` on purpose: rebalancing moves `upper` edges, and

// `gc_is_root` reads them, so classifying roots first would read a stale shape.

//

// NOTE: this drain is single-threaded and scales with the amount of garbage, so it is a

// latency risk on a large collection. Left unbounded for now; the existing

// `optimization_pending` mechanism is how a bound would defer the remainder.

let deferred = std::mem::take(&mut stats.deferred_balance_edges);

if !deferred.is_empty() {

// Process the rebalance requests now that deletion work is done

// Do this before computing roots so all uppers are settled

let deferred = std::mem::take(&mut stats.deferred_balance_edges);

if !deferred.is_empty() {

lukesandberg · 2026-09-13T20:39:46Z

@@ -878,46 +890,108 @@ impl TaskStorage {
            && self.gc_transient_ref_count() == 0
            && self.get_activeness().is_none()
            && self.get_in_progress().is_none()
-            // It is rare for upper/followers to be present when the ref counts are 0 but it can happen transiently during a concurrent GC pass as uppers are moved around during the cascade.
+            // `upper` is an *incoming* edge: some aggregating node above references this task,
+            // so it must block collection. It is rare for one to be present when the ref counts
+            // are 0, but it can happen transiently during a concurrent GC pass as uppers are
+            // moved around during the cascade.
            && self.upper().is_empty()
-            && self.followers().is_none_or(|f| f.is_empty())
+            // NOTE: `followers` is deliberately *not* checked here. Unlike `upper`, a follower is
+            // an *outgoing* edge — a node this task points at — so it says nothing about whether
+            // anything still references *this* task, exactly like `children`. Treating it as a
+            // pin made every parent-less aggregating node look like a GC root, which is
+            // unreachable garbage by the `children`-reachability model. The follower edges
+            // themselves are torn down by the `InnerOfUpperLostFollowers` cascade that
+            // `CleanupOldEdgesOperation` drives off this task's `children`.
            // `collectibles_dependents` is Meta, so it is always checkable here.
            && self
                .collectibles_dependents()


are some of these diffs in the wrong PR, the followers removal should be here but output_dependent and cell_dependent belong in the predicated pr?

lukesandberg · 2026-09-13T20:40:01Z

+/// Children per interior node in [`wide_root`]'s tree.
+///
+/// Chosen so the tree actually promotes nodes into *aggregating* nodes, which is what makes the
+/// fixture exercise `followers` at all. Two effects compound in `prepare_new_children`:
+///
+/// - A node's own `distance` is `children_count.ilog2() * 2`, so 8 children gives distance 6.
+/// - While a parent is still a leaf its children start at `parent_effective + 3`, so `base`
+///   accumulates down each level.
+///
+/// Together they carry `effective` past `LEAF_NUMBER` (16) a few levels down, and *that* is the
+/// transition where a node's children convert into `followers`. A flat one-level tree never gets
+/// there no matter how wide it is, which is why the previous fixture produced zero follower edges
+/// and left the whole rebalance path untested.
+pub const BRANCHING: u32 = 4;
+


simplify comments

lukesandberg added this pull request to stack #98592 September 11, 2026 23:52

lukesandberg force-pushed the gc-08-gc-fixes branch 2 times, most recently from c40516c to 2ef1efe Compare September 12, 2026 17:29

vercel Bot reviewed Sep 13, 2026

View reviewed changes

lukesandberg force-pushed the gc-08-gc-fixes branch from c96a1ef to 4053847 Compare September 13, 2026 17:20

lukesandberg changed the title ~~gc 08 gc fixes~~ turbopack-gc: Defer most aggregation graph management until after GC has settled Sep 13, 2026

lukesandberg changed the title ~~turbopack-gc: Defer most aggregation graph management until after GC has settled~~ turbo-tasks-gc: Defer most aggregation graph management until after GC has settled Sep 13, 2026

lukesandberg force-pushed the gc-08-gc-fixes branch from 4053847 to c59bf08 Compare September 13, 2026 18:49

lukesandberg force-pushed the gc-08-gc-fixes branch from c59bf08 to 31c5333 Compare September 13, 2026 19:14

lukesandberg commented Sep 13, 2026

View reviewed changes

Uh oh!

Conversation

lukesandberg commented Sep 11, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

github-actions Bot commented Sep 11, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Failing test suites

Uh oh!

vercel Bot left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

1 participant

lukesandberg commented Sep 11, 2026 •

edited

Loading

github-actions Bot commented Sep 11, 2026 •

edited

Loading