Skip to content

Replace GC tracking HashSet with intrusive linked list#7328

Merged
youknowone merged 5 commits intoRustPython:mainfrom
youknowone:gc-intrusive-linked-list
Mar 4, 2026
Merged

Replace GC tracking HashSet with intrusive linked list#7328
youknowone merged 5 commits intoRustPython:mainfrom
youknowone:gc-intrusive-linked-list

Conversation

@youknowone
Copy link
Member

@youknowone youknowone commented Mar 3, 2026

Replace per-generation HashSet with intrusive doubly-linked lists for GC object tracking. Each PyInner now carries gc_pointers (prev/next) and gc_generation fields, enabling O(1) track/untrack without hashing.

  • Add gc_pointers (Pointers) and gc_generation (u8) to PyInner
  • Implement GcLink trait for intrusive list integration
  • Replace generation_objects/permanent_objects/tracked_objects/finalized_objects HashSets with generation_lists/permanent_list LinkedLists
  • Use GcBits::FINALIZED flag instead of finalized_objects HashSet
  • Change default_dealloc to untrack directly before memory free
  • Hold both src/dst list locks in promote_survivors to prevent race conditions with concurrent untrack_object calls
  • Add pop_front to LinkedList for freeze/unfreeze operations

Summary by CodeRabbit

  • Refactor

    • GC reworked to use intrusive linked lists for per-generation and permanent storage, and object layout now includes GC metadata to track generation and pointers; freeze/unfreeze and promotion flows reorganized for simpler, faster movement.
  • Bug Fixes

    • Synchronous untracking before deallocation and tightened collection/promotion/finalization flows reduce missed or incorrectly retained objects and improve GC reliability and determinism.

@coderabbitai
Copy link
Contributor

coderabbitai bot commented Mar 3, 2026

Note

Reviews paused

It looks like this branch is under active development. To avoid overwhelming you with review comments due to an influx of new commits, CodeRabbit has automatically paused this review. You can configure this behavior by changing the reviews.auto_review.auto_pause_after_reviewed_commits setting.

Use the following commands to manage reviews:

  • @coderabbitai resume to resume automatic reviews.
  • @coderabbitai review to trigger a single review.

Use the checkboxes below for quick actions:

  • ▶️ Resume reviews
  • 🔍 Trigger review
📝 Walkthrough

Walkthrough

Replaces HashSet-based GC tracking with intrusive per-generation LinkedLists, adds pop_front to the linked-list API, and extends PyInner/PyObject with GC fields and GcLink; updates GcState (track/untrack/collect/promote/freeze/unfreeze) to operate on intrusive lists and GcPtr wrappers.

Changes

Cohort / File(s) Summary
Intrusive LinkedList
crates/common/src/linked_list.rs
Adds pub fn pop_front(&mut self) -> Option<L::Handle> to remove and return the head, adjust links, and clear pointers on the removed node.
GC state: tracking & collection
crates/vm/src/gc_state.rs
Replaces per-generation HashSet storage with [PyRwLock<LinkedList<GcLink, PyObject>>; 3] and a permanent_list; introduces private GcPtr wrapper; rewrites track_object/untrack_object, collect/collect_force, maybe_collect, promote_survivors, freeze/unfreeze, and helper list traversal to use intrusive lists.
PyObject core & visibility
crates/vm/src/object/core.rs, crates/vm/src/object/mod.rs
Adds GC_UNTRACKED, GC_PERMANENT, GcLink (implements Link), per-object fields gc_generation and gc_pointers on PyInner; adjusts set_gc_finalized visibility; adds gc_generation getter/setter; re-exports crate-private GC symbols.

Sequence Diagram(s)

sequenceDiagram
  participant Alloc as Allocator
  participant GcState as GcState
  participant GenList as LinkedList<GcLink, PyObject>
  participant PyObj as PyObject
  participant Collector as Collector

  Alloc->>GcState: track_object(PyObject)
  GcState->>GenList: push_front(PyObject) rgba(70,130,180,0.5)
  note right of GenList: object inserted into gen0 list

  Collector->>GcState: collect(generation)
  GcState->>GenList: iterate -> build GcPtr set rgba(34,139,34,0.5)
  Collector->>PyObj: reachability marking
  Collector->>GcState: promote_survivors(from_gen, survivors)
  GcState->>GenList: remove nodes from old list, push_front into higher-gen list rgba(255,165,0,0.5)
Loading

Estimated code review effort

🎯 4 (Complex) | ⏱️ ~45 minutes

Possibly related PRs

Suggested reviewers

  • ShaharNaveh
  • fanninpm

Poem

🐰
I hopped from hashes into lists so spry,
Popped the front node with a twinkle in my eye,
Generations march in tidy, ordered queues,
Pointers snug, the collector finds its cues,
A tiny hop for code, a carrot for you! 🥕

🚥 Pre-merge checks | ✅ 3
✅ Passed checks (3 passed)
Check name Status Explanation
Description Check ✅ Passed Check skipped - CodeRabbit’s high-level summary is enabled.
Title check ✅ Passed The title accurately summarizes the main change: replacing GC tracking HashSet with intrusive linked lists, which is the core architectural change across all modified files.
Docstring Coverage ✅ Passed Docstring coverage is 100.00% which is sufficient. The required threshold is 80.00%.

✏️ Tip: You can configure your own custom pre-merge checks in the settings.

✨ Finishing Touches
🧪 Generate unit tests (beta)
  • Create PR with unit tests
  • Post copyable unit tests in a comment

Thanks for using CodeRabbit! It's free for OSS, and your support helps us grow. If you like it, consider giving us a shout-out.

❤️ Share

Comment @coderabbitai help to get the list of available commands and usage tips.

@github-actions
Copy link
Contributor

github-actions bot commented Mar 3, 2026

Code has been automatically formatted

The code in this PR has been formatted using:

  • cargo fmt --all
    Please pull the latest changes before pushing again:
git pull origin gc-intrusive-linked-list

@youknowone youknowone force-pushed the gc-intrusive-linked-list branch 2 times, most recently from 35ee888 to adf9282 Compare March 3, 2026 13:20
@youknowone youknowone marked this pull request as ready for review March 3, 2026 13:28
Copy link
Contributor

@coderabbitai coderabbitai bot left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Actionable comments posted: 2

🤖 Prompt for all review comments with AI agents
Verify each finding against the current code and only fix it if needed.

Inline comments:
In `@crates/vm/src/gc_state.rs`:
- Around line 703-708: freeze/unfreeze hold locks in opposite orders and set
GC_PERMANENT before insertion, causing deadlocks and transient inconsistent
state; fix both methods (freeze and unfreeze) to acquire locks in a consistent
order (always lock generation_lists entries first, then permanent_list) and
avoid marking objects permanent until they are inserted into permanent_list —
e.g. drain each generation into a temporary Vec while holding the
generation_list write lock, then acquire permanent_list write lock and
push_front each ptr and call ptr.as_ref().set_gc_generation(GC_PERMANENT) while
holding the permanent_list lock; apply the same consistent lock-ordering pattern
for the unfreeze path and the other affected block (lines ~721–727) referencing
generation_lists, permanent_list, set_gc_generation, GC_PERMANENT, and the
freeze/unfreeze functions.
- Around line 275-283: In untrack_object the GC_PERMANENT branch returns early
when list.remove(obj) is None, which can miss concurrent moves; change the logic
in untrack_object so that if unsafe { list.remove(obj) } returns None you do not
return immediately but instead re-check the object's generation and continue to
the appropriate handling (or loop/retry) so the object will still be untracked
if it moved between lists. Update the block that touches permanent_list,
permanent.count.fetch_sub, obj_ref.clear_gc_tracked, and
obj_ref.set_gc_generation(GC_UNTRACKED) to only perform those when a remove
actually succeeded; otherwise recompute obj_ref.get_gc_generation() (or retry)
and handle the object in the correct branch (GC_YOUNG/GC_OLD) instead of
returning.

ℹ️ Review info

Configuration used: Path: .coderabbit.yml

Review profile: CHILL

Plan: Pro

📥 Commits

Reviewing files that changed from the base of the PR and between 3cbd08f and adf9282.

📒 Files selected for processing (4)
  • crates/common/src/linked_list.rs
  • crates/vm/src/gc_state.rs
  • crates/vm/src/object/core.rs
  • crates/vm/src/object/mod.rs

@youknowone youknowone force-pushed the gc-intrusive-linked-list branch from adf9282 to c9f0692 Compare March 3, 2026 14:40
Copy link
Contributor

@coderabbitai coderabbitai bot left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

♻️ Duplicate comments (1)
crates/vm/src/gc_state.rs (1)

711-735: ⚠️ Potential issue | 🔴 Critical

Resolve lock-order inversion between freeze and unfreeze (deadlock risk).

Line 712 locks permanent_list first, while Lines 733-734 lock generation_lists[2] then permanent_list. That opposing order can deadlock under concurrent calls.

🔧 Suggested lock-order fix for freeze
 pub fn freeze(&self) {
     let mut count = 0usize;
-    let mut perm = self.permanent_list.write();

     for (gen_idx, gen_list) in self.generation_lists.iter().enumerate() {
         let mut list = gen_list.write();
+        let mut perm = self.permanent_list.write();
         while let Some(ptr) = list.pop_front() {
             perm.push_front(ptr);
             unsafe { ptr.as_ref().set_gc_generation(GC_PERMANENT) };
             count += 1;
         }
         self.generations[gen_idx].count.store(0, Ordering::SeqCst);
     }

     self.permanent.count.fetch_add(count, Ordering::SeqCst);
 }
🤖 Prompt for AI Agents
Verify each finding against the current code and only fix it if needed.

In `@crates/vm/src/gc_state.rs` around lines 711 - 735, The freeze function
currently acquires self.permanent_list.write() before taking per-generation
locks, which inverts the lock order used by unfreeze (which takes
generation_lists[2].write() then permanent_list.write()) and can deadlock; fix
by reordering locks in freeze to always acquire generation_lists (e.g., iterate
and take each gen_list.write() or at least acquire generation_lists[2].write()
before permanent_list.write()) so the lock ordering matches unfreeze
(generation_lists -> permanent_list), and update the logic in freeze (and any
helper blocks) to move nodes into permanent_list after holding the generation
lock(s) but only take permanent_list.write() after those generation locks are
held to maintain consistent lock order between freeze and unfreeze.
🧹 Nitpick comments (1)
crates/vm/src/gc_state.rs (1)

260-287: Extract shared untrack logic instead of duplicating generation/permanent branches.

The two branches repeat the same re-check/remove/clear flow; only target list/counter selection differs. Consolidating this reduces maintenance risk.

As per coding guidelines: "When branches differ only in a value but share common logic, extract the differing value first, then call the common logic once to avoid duplicate code".

🤖 Prompt for AI Agents
Verify each finding against the current code and only fix it if needed.

In `@crates/vm/src/gc_state.rs` around lines 260 - 287, Extract the duplicated
re-check/remove/clear sequence into a single helper and call it for both
generation and permanent cases: compute the target list and counter first (for
gen <= 2 set list = self.generation_lists[obj_gen as usize].write() and counter
= &self.generations[obj_gen as usize].count; for GC_PERMANENT set list =
self.permanent_list.write() and counter = &self.permanent.count), then perform
the re-check using obj_ref.gc_generation(), call unsafe { list.remove(obj) } and
if Some decrement counter.fetch_sub(1, Ordering::SeqCst), call
obj_ref.clear_gc_tracked() and obj_ref.set_gc_generation(GC_UNTRACKED), and
return; keep the outer loop/continue logic unchanged so the helper is retried
when the generation changed.
🤖 Prompt for all review comments with AI agents
Verify each finding against the current code and only fix it if needed.

Duplicate comments:
In `@crates/vm/src/gc_state.rs`:
- Around line 711-735: The freeze function currently acquires
self.permanent_list.write() before taking per-generation locks, which inverts
the lock order used by unfreeze (which takes generation_lists[2].write() then
permanent_list.write()) and can deadlock; fix by reordering locks in freeze to
always acquire generation_lists (e.g., iterate and take each gen_list.write() or
at least acquire generation_lists[2].write() before permanent_list.write()) so
the lock ordering matches unfreeze (generation_lists -> permanent_list), and
update the logic in freeze (and any helper blocks) to move nodes into
permanent_list after holding the generation lock(s) but only take
permanent_list.write() after those generation locks are held to maintain
consistent lock order between freeze and unfreeze.

---

Nitpick comments:
In `@crates/vm/src/gc_state.rs`:
- Around line 260-287: Extract the duplicated re-check/remove/clear sequence
into a single helper and call it for both generation and permanent cases:
compute the target list and counter first (for gen <= 2 set list =
self.generation_lists[obj_gen as usize].write() and counter =
&self.generations[obj_gen as usize].count; for GC_PERMANENT set list =
self.permanent_list.write() and counter = &self.permanent.count), then perform
the re-check using obj_ref.gc_generation(), call unsafe { list.remove(obj) } and
if Some decrement counter.fetch_sub(1, Ordering::SeqCst), call
obj_ref.clear_gc_tracked() and obj_ref.set_gc_generation(GC_UNTRACKED), and
return; keep the outer loop/continue logic unchanged so the helper is retried
when the generation changed.

ℹ️ Review info

Configuration used: Path: .coderabbit.yml

Review profile: CHILL

Plan: Pro

📥 Commits

Reviewing files that changed from the base of the PR and between adf9282 and c9f0692.

📒 Files selected for processing (4)
  • crates/common/src/linked_list.rs
  • crates/vm/src/gc_state.rs
  • crates/vm/src/object/core.rs
  • crates/vm/src/object/mod.rs
🚧 Files skipped from review as they are similar to previous changes (1)
  • crates/common/src/linked_list.rs

@youknowone youknowone force-pushed the gc-intrusive-linked-list branch from c9f0692 to c0054a4 Compare March 3, 2026 15:43
Copy link
Contributor

@coderabbitai coderabbitai bot left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Actionable comments posted: 2

🤖 Prompt for all review comments with AI agents
Verify each finding against the current code and only fix it if needed.

Inline comments:
In `@crates/vm/src/gc_state.rs`:
- Around line 107-108: Remove the unconditional unsafe impls for Send and Sync
on the GcPtr type: delete the lines "unsafe impl Send for GcPtr {}" and "unsafe
impl Sync for GcPtr {}". GcPtr is only used within the GC collection algorithm
(the GC-related functions in this module) and must not be advertised as
thread-safe; if any compilation error occurs after removal, narrow the required
bounds where a type must be Send/Sync (rather than making GcPtr global
Send/Sync) or add a targeted wrapper that implements Send/Sync with a safe
justification; run cargo check/tests to confirm no other code relies on those
impls.
- Around line 286-297: The methods is_finalized and mark_finalized currently
dereference NonNull<PyObject> in safe public functions; change their signatures
to unsafe fn is_finalized(&self, obj: NonNull<PyObject>) -> bool and unsafe fn
mark_finalized(&self, obj: NonNull<PyObject>) so callers must guarantee the
pointer is valid before dereferencing, and update all call sites to wrap calls
in unsafe blocks (or otherwise ensure safety invariants); keep the internal
logic (unsafe { obj.as_ref() } / obj_ref.set_gc_finalized()) as-is but only
reachable from the new unsafe functions.

ℹ️ Review info

Configuration used: Path: .coderabbit.yml

Review profile: CHILL

Plan: Pro

📥 Commits

Reviewing files that changed from the base of the PR and between c9f0692 and c0054a4.

📒 Files selected for processing (4)
  • crates/common/src/linked_list.rs
  • crates/vm/src/gc_state.rs
  • crates/vm/src/object/core.rs
  • crates/vm/src/object/mod.rs
🚧 Files skipped from review as they are similar to previous changes (1)
  • crates/vm/src/object/mod.rs

@youknowone youknowone force-pushed the gc-intrusive-linked-list branch from c38f9d2 to 40fc922 Compare March 3, 2026 19:49
Copy link
Contributor

@coderabbitai coderabbitai bot left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

♻️ Duplicate comments (1)
crates/vm/src/gc_state.rs (1)

289-299: ⚠️ Potential issue | 🔴 Critical

Make raw-pointer finalization helpers unsafe (or take &PyObject).

is_finalized and mark_finalized are safe pub fns but dereference raw pointers internally (Line 290, Line 297). That makes UB reachable from safe callers passing an invalid NonNull<PyObject>.

🔧 Proposed fix
-    pub fn is_finalized(&self, obj: NonNull<PyObject>) -> bool {
+    /// # Safety
+    /// `obj` must point to a valid live `PyObject`.
+    pub unsafe fn is_finalized(&self, obj: NonNull<PyObject>) -> bool {
         let obj_ref = unsafe { obj.as_ref() };
         obj_ref.gc_finalized()
     }

-    pub fn mark_finalized(&self, obj: NonNull<PyObject>) {
+    /// # Safety
+    /// `obj` must point to a valid live `PyObject`.
+    pub unsafe fn mark_finalized(&self, obj: NonNull<PyObject>) {
         let obj_ref = unsafe { obj.as_ref() };
         obj_ref.set_gc_finalized();
     }

Run this to verify definition/call-site updates after the signature change:

#!/bin/bash
set -euo pipefail

# Confirm helper signatures
rg -nP --type=rust 'pub\s+(unsafe\s+)?fn\s+(is_finalized|mark_finalized)\s*\(' crates/vm/src/gc_state.rs -C2

# Find all call sites that must satisfy unsafe contract (or be ref-based after refactor)
rg -nP --type=rust '\.(is_finalized|mark_finalized)\s*\(' crates/vm/src -C2
🤖 Prompt for AI Agents
Verify each finding against the current code and only fix it if needed.

In `@crates/vm/src/gc_state.rs` around lines 289 - 299, The methods is_finalized
and mark_finalized currently dereference a raw NonNull<PyObject> inside safe
functions which is UB; change their signatures to either pub unsafe fn
is_finalized(&self, obj: NonNull<PyObject>) -> bool and pub unsafe fn
mark_finalized(&self, obj: NonNull<PyObject>) or accept a safe reference pub fn
is_finalized(&self, obj: &PyObject) / pub fn mark_finalized(&self, obj:
&PyObject), update all call sites accordingly to either call them within an
unsafe block or pass &PyObject, and run the ripgrep checks suggested to locate
and fix all call sites that must be adjusted.
🤖 Prompt for all review comments with AI agents
Verify each finding against the current code and only fix it if needed.

Duplicate comments:
In `@crates/vm/src/gc_state.rs`:
- Around line 289-299: The methods is_finalized and mark_finalized currently
dereference a raw NonNull<PyObject> inside safe functions which is UB; change
their signatures to either pub unsafe fn is_finalized(&self, obj:
NonNull<PyObject>) -> bool and pub unsafe fn mark_finalized(&self, obj:
NonNull<PyObject>) or accept a safe reference pub fn is_finalized(&self, obj:
&PyObject) / pub fn mark_finalized(&self, obj: &PyObject), update all call sites
accordingly to either call them within an unsafe block or pass &PyObject, and
run the ripgrep checks suggested to locate and fix all call sites that must be
adjusted.

ℹ️ Review info

Configuration used: Path: .coderabbit.yml

Review profile: CHILL

Plan: Pro

📥 Commits

Reviewing files that changed from the base of the PR and between c38f9d2 and e86c8b2.

📒 Files selected for processing (4)
  • crates/common/src/linked_list.rs
  • crates/vm/src/gc_state.rs
  • crates/vm/src/object/core.rs
  • crates/vm/src/object/mod.rs

@youknowone youknowone force-pushed the gc-intrusive-linked-list branch 2 times, most recently from 7b739f8 to 19e1ab3 Compare March 4, 2026 11:09
youknowone and others added 3 commits March 4, 2026 23:29
Replace per-generation HashSet<GcObjectPtr> with intrusive doubly-linked
lists for GC object tracking. Each PyInner now carries gc_pointers
(prev/next) and gc_generation fields, enabling O(1) track/untrack
without hashing.

- Add gc_pointers (Pointers<PyObject>) and gc_generation (u8) to PyInner
- Implement GcLink trait for intrusive list integration
- Replace generation_objects/permanent_objects/tracked_objects/finalized_objects
  HashSets with generation_lists/permanent_list LinkedLists
- Use GcBits::FINALIZED flag instead of finalized_objects HashSet
- Change default_dealloc to untrack directly before memory free
- Hold both src/dst list locks in promote_survivors to prevent race
  conditions with concurrent untrack_object calls
- Add pop_front to LinkedList for freeze/unfreeze operations
Move unreachable_refs creation before drop(gen_locks) so that raw
pointer dereferences and refcount increments happen while generation
list read locks are held. Previously, after dropping read locks, other
threads could untrack and free objects, causing use-after-free when
creating strong references from the raw GcPtr pointers.

Also add linked list integrity assertions and diagnostic warnings
for debugging GC list corruption.
@youknowone youknowone force-pushed the gc-intrusive-linked-list branch from 19e1ab3 to b279716 Compare March 4, 2026 14:31
- Remove unused is_finalized/mark_finalized methods from GcState
- Remove unnecessary Send/Sync impls on GcPtr (only used locally
  within collect_inner, never shared across threads)
@youknowone youknowone merged commit 5c29074 into RustPython:main Mar 4, 2026
12 of 13 checks passed
@youknowone youknowone deleted the gc-intrusive-linked-list branch March 4, 2026 15:42
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

1 participant