Skip to content

Commit 5c29074

Browse files
youknowoneyouknowone
authored
Replace GC tracking HashSet with intrusive linked list (#7328)
* Replace GC tracking HashSet with intrusive linked list 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.
1 parent 745efbd commit 5c29074

File tree

4 files changed

+315
-298
lines changed

4 files changed

+315
-298
lines changed

‎crates/common/src/linked_list.rs‎

Lines changed: 33 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -157,6 +157,15 @@ impl<L: Link> LinkedList<L, L::Target> {
157157
let ptr = L::as_raw(&val);
158158
assert_ne!(self.head, Some(ptr));
159159
unsafe {
160+
// Verify the node is not already in a list (pointers must be clean)
161+
debug_assert!(
162+
L::pointers(ptr).as_ref().get_prev().is_none(),
163+
"push_front: node already has prev pointer (double-insert?)"
164+
);
165+
debug_assert!(
166+
L::pointers(ptr).as_ref().get_next().is_none(),
167+
"push_front: node already has next pointer (double-insert?)"
168+
);
160169
L::pointers(ptr).as_mut().set_next(self.head);
161170
L::pointers(ptr).as_mut().set_prev(None);
162171

@@ -192,6 +201,20 @@ impl<L: Link> LinkedList<L, L::Target> {
192201
// }
193202
// }
194203

204+
/// Removes the first element from the list and returns it, or None if empty.
205+
pub fn pop_front(&mut self) -> Option<L::Handle> {
206+
let head = self.head?;
207+
unsafe {
208+
self.head = L::pointers(head).as_ref().get_next();
209+
if let Some(new_head) = self.head {
210+
L::pointers(new_head).as_mut().set_prev(None);
211+
}
212+
L::pointers(head).as_mut().set_next(None);
213+
L::pointers(head).as_mut().set_prev(None);
214+
Some(L::from_raw(head))
215+
}
216+
}
217+
195218
/// Returns whether the linked list does not contain any node
196219
pub const fn is_empty(&self) -> bool {
197220
self.head.is_none()
@@ -212,7 +235,11 @@ impl<L: Link> LinkedList<L, L::Target> {
212235
pub unsafe fn remove(&mut self, node: NonNull<L::Target>) -> Option<L::Handle> {
213236
unsafe {
214237
if let Some(prev) = L::pointers(node).as_ref().get_prev() {
215-
debug_assert_eq!(L::pointers(prev).as_ref().get_next(), Some(node));
238+
debug_assert_eq!(
239+
L::pointers(prev).as_ref().get_next(),
240+
Some(node),
241+
"linked list corruption: prev->next != node (prev={prev:p}, node={node:p})"
242+
);
216243
L::pointers(prev)
217244
.as_mut()
218245
.set_next(L::pointers(node).as_ref().get_next());
@@ -225,7 +252,11 @@ impl<L: Link> LinkedList<L, L::Target> {
225252
}
226253

227254
if let Some(next) = L::pointers(node).as_ref().get_next() {
228-
debug_assert_eq!(L::pointers(next).as_ref().get_prev(), Some(node));
255+
debug_assert_eq!(
256+
L::pointers(next).as_ref().get_prev(),
257+
Some(node),
258+
"linked list corruption: next->prev != node (next={next:p}, node={node:p})"
259+
);
229260
L::pointers(next)
230261
.as_mut()
231262
.set_prev(L::pointers(node).as_ref().get_prev());

0 commit comments

Comments
 (0)