Skip to content

GH-126491: GC: Mark objects reachable from roots before doing cycle collection #127110

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
markshannon merged 18 commits into from
Dec 2, 2024
Merged

GH-126491: GC: Mark objects reachable from roots before doing cycle collection #127110

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
18 commits
Select commit Hold shift + click to select a range
2b0a2c5
Change the young generation to 'not visited'. WIP
markshannon Nov 19, 2024
754bb68
Tidy up visited tracking and add consistency asserts
markshannon Nov 20, 2024
ac3ad26
Partially apply mark-first-gc patch
markshannon Nov 21, 2024
5c3a5ef
Rename get_heap_size
markshannon Nov 21, 2024
0ac1c07
Set visited on entry frame
markshannon Nov 21, 2024
bb51b19
Apply more diff, but comment out marking step
markshannon Nov 21, 2024
be636c9
Refactor work to do calculation
markshannon Nov 21, 2024
287f381
Turn on marking. Explain issue with tuple untracking
markshannon Nov 21, 2024
7e920d6
Add news
markshannon Nov 21, 2024
0b46494
Add stats for marking
markshannon Nov 21, 2024
698abb3
Do not touch permanent generation
markshannon Nov 21, 2024
6d8a0d4
Move informative failure message in test
markshannon Nov 22, 2024
d9632c6
Increase threshold a bit
markshannon Nov 22, 2024
0702959
Increase number of iterations
markshannon Nov 22, 2024
6063dc8
Return number of iterations to 20k
markshannon Nov 22, 2024
67b1e05
Fix compiler warning
markshannon Nov 22, 2024
eaea41e
Turn off extra debugging
markshannon Nov 22, 2024
79ab26c
Add missing macro
markshannon Nov 22, 2024
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Next Next commit
Change the young generation to 'not visited'. WIP
  • Loading branch information
@markshannon
markshannon committed Nov 21, 2024
commit 2b0a2c5beffaee60023b17dc9c94109aa8a5741c
4 changes: 2 additions & 2 deletions Include/internal/pycore_object.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -470,8 +470,8 @@ static inline void _PyObject_GC_TRACK(
PyGC_Head *last = (PyGC_Head*)(generation0->_gc_prev);
_PyGCHead_SET_NEXT(last, gc);
_PyGCHead_SET_PREV(gc, last);
/* Young objects will be moved into the visited space during GC, so set the bit here */
gc->_gc_next = ((uintptr_t)generation0) | (uintptr_t)interp->gc.visited_space;
uintptr_t not_visited = 1 ^ interp->gc.visited_space;
gc->_gc_next = ((uintptr_t)generation0) | not_visited;
generation0->_gc_prev = (uintptr_t)gc;
#endif
}
Expand Down
25 changes: 14 additions & 11 deletions Python/gc.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -24,7 +24,7 @@ typedef struct _gc_runtime_state GCState;
#endif

// Define this when debugging the GC
// #define GC_EXTRA_DEBUG
#define GC_EXTRA_DEBUG


#define GC_NEXT _PyGCHead_NEXT
Expand Down Expand Up @@ -1308,6 +1308,7 @@ gc_collect_young(PyThreadState *tstate,

PyGC_Head survivors;
gc_list_init(&survivors);
gc_list_set_space(young, gcstate->visited_space);
gc_collect_region(tstate, young, &survivors, stats);
Py_ssize_t survivor_count = 0;
if (gcstate->visited_space) {
Expand Down Expand Up @@ -1385,6 +1386,7 @@ expand_region_transitively_reachable(PyGC_Head *container, PyGC_Head *gc, GCStat
* have been marked as visited */
assert(IS_IN_VISITED(gc, gcstate->visited_space));
PyObject *op = FROM_GC(gc);
assert(_PyObject_GC_IS_TRACKED(op));
if (_Py_IsImmortal(op)) {
PyGC_Head *next = GC_NEXT(gc);
gc_list_move(gc, &get_gc_state()->permanent_generation.head);
Expand All @@ -1404,17 +1406,16 @@ expand_region_transitively_reachable(PyGC_Head *container, PyGC_Head *gc, GCStat
static void
completed_cycle(GCState *gcstate)
{
#ifdef Py_DEBUG
PyGC_Head *not_visited = &gcstate->old[gcstate->visited_space^1].head;
assert(gc_list_is_empty(not_visited));
#endif
int not_visited = flip_old_space(gcstate->visited_space);
assert(gc_list_is_empty(&gcstate->old[not_visited].head));
gcstate->visited_space = not_visited;
gcstate->visited_space = flip_old_space(gcstate->visited_space);
/* Make sure all young objects have old space bit set correctly */
PyGC_Head *young = &gcstate->young.head;
PyGC_Head *gc = GC_NEXT(young);
while (gc != young) {
PyGC_Head *next = GC_NEXT(gc);
gc_set_old_space(gc, gcstate->visited_space);
gc_set_old_space(gc, not_visited);
gc = next;
}
gcstate->work_to_do = 0;
Expand All @@ -1433,6 +1434,7 @@ gc_collect_increment(PyThreadState *tstate, struct gc_collection_stats *stats)
if (scale_factor < 1) {
scale_factor = 1;
}
gc_list_set_space(&gcstate->young.head, gcstate->visited_space);
gc_list_merge(&gcstate->young.head, &increment);
gcstate->young.count = 0;
gc_list_validate_space(&increment, gcstate->visited_space);
Expand All @@ -1444,6 +1446,7 @@ gc_collect_increment(PyThreadState *tstate, struct gc_collection_stats *stats)
PyGC_Head *gc = _PyGCHead_NEXT(not_visited);
gc_list_move(gc, &increment);
increment_size++;
assert(!_Py_IsImmortal(FROM_GC(gc)));
gc_set_old_space(gc, gcstate->visited_space);
increment_size += expand_region_transitively_reachable(&increment, gc, gcstate);
}
Expand All @@ -1465,7 +1468,6 @@ gc_collect_increment(PyThreadState *tstate, struct gc_collection_stats *stats)
}
}


static void
gc_collect_full(PyThreadState *tstate,
struct gc_collection_stats *stats)
Expand All @@ -1477,9 +1479,9 @@ gc_collect_full(PyThreadState *tstate,
PyGC_Head *pending = &gcstate->old[gcstate->visited_space^1].head;
PyGC_Head *visited = &gcstate->old[gcstate->visited_space].head;
/* merge all generations into visited */
gc_list_validate_space(young, gcstate->visited_space);
gc_list_set_space(pending, gcstate->visited_space);
gc_list_merge(young, pending);
gc_list_validate_space(pending, 1-gcstate->visited_space);
gc_list_set_space(pending, gcstate->visited_space);
gcstate->young.count = 0;
gc_list_merge(pending, visited);

Expand All @@ -1488,7 +1490,7 @@ gc_collect_full(PyThreadState *tstate,
gcstate->young.count = 0;
gcstate->old[0].count = 0;
gcstate->old[1].count = 0;

completed_cycle(gcstate);
gcstate->work_to_do = - gcstate->young.threshold * 2;
_PyGC_ClearAllFreeLists(tstate->interp);
validate_old(gcstate);
Expand Down Expand Up @@ -1734,9 +1736,10 @@ _PyGC_Freeze(PyInterpreterState *interp)
{
GCState *gcstate = &interp->gc;
/* The permanent_generation has its old space bit set to zero */
if (gcstate->visited_space) {
if (gcstate->visited_space == 0) {
gc_list_set_space(&gcstate->young.head, 0);
}
gc_list_validate_space(&gcstate->young.head, 0);
gc_list_merge(&gcstate->young.head, &gcstate->permanent_generation.head);
gcstate->young.count = 0;
PyGC_Head*old0 = &gcstate->old[0].head;
Expand Down