CPython — Сборка мусора изнутри, ч.3 / Хабр

В прошлых частях мы поговорили о том, как происходит регистрация объектов в сборщике мусора, о том как происходит планирование и вызов сборки мусора, что такое молодое поколение и как устроена для него сборка мусора. В этой части пришло время поговорить об инкрементальной сборке мусора — главному нововведению версии 3.14 в части сборки мусора. Поговорим, как она устроена, какие даёт преимущества и какие имеет недостатки, а также затронем полную сборку мусора.

Если вам интересно, давайте попробуем разобраться.

Side note

Как и в прошлый раз, я успел сделать доклад на тему сборки мусора на локальной конференции #UFADEVCONF2025. Несмотря на то, что тема называется так же, как на конференции в Нижнем Новгороде, я подготовил полностью другой доклад и почти полностью новые слайды — если вам интересно, то тут можно найти слайды и ссылки на видео.

Инкрементальная сборка мусора

В версию 3.14 была добавлена инкрементальная сборка мусора (Incremental cycle GC). Основная цель этого нововведения — снизить длительность выполнения сборки мусора, так как в некоторых сценариях данные паузы могут быть довольно продолжительными.

С чем это связано? Кто занимался оптимизацией программ на Python, рано или поздно с этим сталкивался, но, думаю, что стоит это проговорить.

До версии 3.14 сборщик мусора содержал три поколения, сборку в которых можно было вызвать вручную через gc.collect(0|1|2). Вызов gc.collect(0) приводит к сборке мусора в молодом поколении, как было описано ранее, и это поведение не изменилось в 3.14. Вызов gc.collect(2) приводит к сборке мусора для старшего поколения или (что то же самое) к полной сборке мусора:

With no arguments, run a full collection. The optional argument generation may be an integer specifying which generation to collect (from 0 to 2). The number of unreachable objects found is returned.
The free lists maintained for a number of built-in types are cleared whenever a full collection or collection of the highest generation (2) is run.

И это поведение также не изменилось в 3.14. Изменения затронули среднее поколение.

Мы знаем, что до версии 3.14 сборщик мусора управлялся тремя граничным значениями, которые устанавливаются через gc.set_threshold.

Первое значение указывает, при каком количестве живых молодых объектов должна запуститься сборка мусора. В случае автоматического запуска сборщика мусора происходит выбор, для какого поколения необходимо выполнить сборку мусора. Этим управляют второе и третье граничные значения. Второе граничное значение определяет через какое количество запусков сборщика мусора для молодого поколения, должна запуститься сборка мусора для второго, среднего поколения. А третье значение, соответственно, относится к количеству запусков сборщика для среднего поколения, чтобы запустить сборку для старшего поколения.

Такая схема могла в некоторых случаях приводить к нелинейной сложности, когда со временем сборка старшего поколения начинала занимать всё больше времени. Чтобы этого избежать, была добавлена проверка на количество объектов, ожидающих полную сборку мусора. Подробнее можно посмотреть в документации — collecting the oldest generation.

С другой стороны, чем больше мы делаем паузы между сборками старшего поколения, тем дольше они будут выполняться, так как в старшем поколении будет скапливаться всё больше объектов.

Инкрементальный сборщик должен решить эти проблемы. Начиная с версии 3.14 CPython отказался от трёх поколений — остались только младшее и старшее поколения.

Но старшее поколение разделено на две части — одна часть, содержит объекты, которые уже были проверены (visited), вторая часть, содержит объекты, которые ожидают проверку (not visited или pending — я могу употреблять оба термина в дальнейшем). Несмотря на то, что «физически» у нас осталось три коллекции объектов, смысл поменялся.

Также поменялся и смысл для вызова gc.collect(1), который теперь запускает инкрементальную сборку мусора, а точнее, сборку мусора только для небольшой части объектов. И если раньше, вызвав gc.collect(1) мы выполняли сборку мусора в среднем поколении и могли быть уверены, что объекты из молодого и среднего поколения, которые пережили сборку, будут перенесены в старшее поколение, то сейчас мы не можем точно определить, какое количество вызовов gc.collect(1) нам необходимо совершить, чтобы обработать все ожидающие объекты.

Небольшая часть объектов, для которой запускается инкрементальный сборщик, состоит из всех объектов молодого поколения, а также некоторой части ожидающих объектов старшего поколения. Эта часть называется increment (я буду называть её инкремент, для краткости):

Calling gc.collect(1) will perform a GC collection on the young generation and an increment of the old generation.

Можно сказать, что размер инкремента зависит от сценария работы программы, и учитывает, сколько объектов было создано, сколько объектов было перемещено в просмотренную часть старшего поколения.

Ещё одно нововведение в сборщике мусора — это наличие нескольких фаз: фаза маркировки (GC_PHASE_MARK) и фаза сборки (GC_PHASE_COLLECT). В первую очередь вызывается фаза маркировки, во время которой рассчитывается начальное количество объектов, которые должны попасть в инкремент и переключается сборка мусора в фазу сборки.

Затем выполняется фаза сборки. Данная фаза вызывается столько раз, сколько необходимо, чтобы обработать все объекты, которые находятся в ожидающей части старшего поколения.

Как только ожидающая часть старшего поколения будет полностью обработана, то есть список будет пуст, то произойдёт переключение частей старшего поколения — просмотренная часть будет считаться ожидающей и наоборот. Также при этом фаза сборки мусора переключится обратно на фазу маркировки.

Таком образом, с помощью вызова gc.collect(1) можно выполнить сборку мусора для какой‑то части объектов. Но нет никаких гарантий или документированных способов определить, сколько таких вызовов понадобится, чтобы собрать весь «мусор». Так что вызывать инкрементальную сборку мусора из пользовательского кода особого смысла нет, только если мы не хотим досрочно (как и в случае сборки для молодого поколения) перенести молодые объекты в старшее поколение.

Детали реализации

Концептуально инкрементальная сборка мусора основывается на простой идее — обрабатывать объекты небольшими частями.

Примечание о версии

Черновик статьи писался ещё до появления 3.14.0, но время идёт, и с тех пор вышли версии 3.14.1 и 3.14.2. После 3.14.0 были найдены некоторые баги (Potentially serious regression in garbage collector performance in Python 3.14, Observed memory leak in ssl library: Python 3.14 GC issue) и для их решения были внесены исправления в инкрементальный сборщик мусора. И, возможно, будут ещё внесены. Поэтому на момент чтения статьи исходный код может немного отличаться от описанного в статье.

Теперь стоит посмотреть, а как эта идея реализована. Как и ранее, оставлю за бортом отладочные вызовы и сбор статистики.

static void
gc_collect_increment(PyThreadState *tstate, struct gc_collection_stats *stats)
{
    GCState *gcstate = &tstate->interp->gc;
    gcstate->work_to_do += assess_work_to_do(gcstate);
    if (gcstate->work_to_do < 0) {
        return;
    }
    untrack_tuples(&gcstate->young.head);
    if (gcstate->phase == GC_PHASE_MARK) {
        Py_ssize_t objects_marked = mark_at_start(tstate);
        gcstate->work_to_do -= objects_marked;
        stats->candidates += objects_marked;
        return;
    }
    PyGC_Head *not_visited = &gcstate->old[gcstate->visited_space^1].head;
    PyGC_Head *visited = &gcstate->old[gcstate->visited_space].head;
    PyGC_Head increment;
    gc_list_init(&increment);

    intptr_t objects_marked = mark_stacks(tstate->interp, visited, gcstate->visited_space, false);
    gcstate->work_to_do -= objects_marked;
    gc_list_set_space(&gcstate->young.head, gcstate->visited_space);
    gc_list_merge(&gcstate->young.head, &increment);
    Py_ssize_t increment_size = gc_list_size(&increment);
    while (increment_size < gcstate->work_to_do) {
        if (gc_list_is_empty(not_visited)) {
            break;
        }
        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);
    }

    PyGC_Head survivors;
    gc_list_init(&survivors);
    gc_collect_region(tstate, &increment, &survivors, stats);
    gc_list_merge(&survivors, visited);
    gcstate->work_to_do -= increment_size;

    if (gc_list_is_empty(not_visited)) {
        completed_scavenge(gcstate);
    }
}

В первую очередь, независимо от фазы сборки мусора, обновляется количество объектов, которые попадут в инкремент gcstate->work_to_do, делается это функцией assess_work_to_do.

Определение размера инкремента

Как сказано выше, gc.set_threshold задаёт три граничных значения для управления сборкой мусора. В версии 3.14 значимыми остались только первые два. Первое значение, как и прежде, задаёт, какое количество живых молодых объектов должно быть создано, чтобы запустилась сборка мусора. А второе значение задаёт какая часть старшего поколения должна быть обработана за один инкремент.

Ранее значения по умолчанию были (2000, 10, 10), что можно понимать следующим образом — через 100 вызовов сборки мусора для молодого и среднего поколений должна запуститься полная сборка мусора. То для версии 3.14 эти значения интерпретируются таким образом, ч��о через 100 инкрементальных сборок выполнилась полная сборка ожидающей части старшего поколения.

Основная функция для расчёта значения gcstate->work_to_do это assess_work_to_do:


/* Divide by 10, so that the default incremental threshold of 10
 * scans objects at 1% of the heap size */
#define SCAN_RATE_DIVISOR 10

static intptr_t
assess_work_to_do(GCState *gcstate)
{
    /* The amount of work we want to do depends on three things.
     * 1. The number of new objects created
     * 2. The growth in heap size since the last collection
     * 3. The heap size (up to the number of new objects, to avoid quadratic effects)
     *
     * For a steady state heap, the amount of work to do is three times the number
     * of new objects added to the heap. This ensures that we stay ahead in the
     * worst case of all new objects being garbage.
     *
     * This could be improved by tracking survival rates, but it is still a
     * large improvement on the non-marking approach.
     */
    intptr_t scale_factor = gcstate->old[0].threshold;
    if (scale_factor < 2) {
        scale_factor = 2;
    }
    intptr_t new_objects = gcstate->young.count;
    intptr_t max_heap_fraction = new_objects*2;
    intptr_t heap_fraction = gcstate->heap_size / SCAN_RATE_DIVISOR / scale_factor;
    if (heap_fraction > max_heap_fraction) {
        heap_fraction = max_heap_fraction;
    }
    gcstate->young.count = 0;
    return new_objects + heap_fraction;
}

Стоит сделать несколько комментариев. Во‑первых, мы обрабатываем случаи, когда граничное значение установлено слишком низким (да, это не документировано). Во‑вторых, расчёт значения max_heap_fraction различается для версий 3.14.0 и 3.14.1. В 3.14.0 формула явно содержит ошибку, которая была исправлена в GH-139951: Fix major GC performance regression.

В‑третьих, gcstate->young.count = 0 не относится к расчёту размера инкремента и в эту функцию, скорей всего, попало по недосмотру. Цель этого выражения — сбросить счётчик живых молодых объектов, чтобы, в случае раннего возврата из gc_collect_increment, следующий вызов инкрементального сборщика мусора выполнился только после создания новой пачки объектов.

Но размер инкремента определяется не только этой функцией. Несколько корректировок делается и в основной функции gc_collect_increment.

Из work_to_do вычитается количество объектов, которые были определены как «живые». А также вычитается размер инкремента. Насколько я могу судить по обсуждениям в трекере на гитхабе, цель этих корректировок — адаптировать частоту вызовов инкрементального сборщика, в зависимости от интенсивности создания объектов. Но, есть предположение, что эти корректировки некорректны и на момент написания статьи существует предложение их отменить (GH-142002: Revert GC changes to «work_to_do» logic.). Могу сказать одно, что это самая неочевидная часть нового инкрементального сборщика мусора.

Если work_to_do имеет отрицательное значение, то осуществляется ранний выход из процедуры. Данная проверка была добавлена в 3.14.1, как одна из оптимизаций при решении проблемы Potentially serious regression in garbage collector performance in Python 3.14, но на данный момент, есть предложение удалить эту проверку, так как она может приводить к увеличению потребления памяти.

Далее идёт дерегистрация кортежей, мы её разбирали в прошлой части — CPython — Сборка мусора изнутри, ч.2

Фаза маркировки

На фазе маркировки выполняется несколько действий — вызывается функция mark_at_start и корректируется размер work_to_do.

Рассмотрим функцию mark_at_start:

static intptr_t
mark_at_start(PyThreadState *tstate)
{
    GCState *gcstate = &tstate->interp->gc;
    PyGC_Head *visited = &gcstate->old[gcstate->visited_space].head;
    Py_ssize_t objects_marked = mark_global_roots(tstate->interp, visited, gcstate->visited_space);
    objects_marked += mark_stacks(tstate->interp, visited, gcstate->visited_space, true);
    gcstate->work_to_do -= objects_marked;
    gcstate->phase = GC_PHASE_COLLECT;
    return objects_marked;
}

Данная функция вызывает mark_global_roots, для определения глобальных корневых объектов и объектов, которые из них транзитивно достижимы. Также вызывается mark_stacks, в которой определяются локальные корневые объекты и также транзитивно достижимые объекты. И корректируется значение work_to_do. Внимательный читатель заметит, что work_to_do дважды корректируется на одно и то же значение во время этой фазы. Это известная ошибка — GH-126491: Lower heap size limit with faster marking, GH-141890: Fix GC double‑counting of marked objects — но комплексного исправления ситуации пока нет.

Обработка глобальных корневых объектов

Обработкой глобальных корневых объектов занимается функция mark_global_roots:

static intptr_t
mark_global_roots(PyInterpreterState *interp, PyGC_Head *visited, int visited_space)
{
    PyGC_Head reachable;
    gc_list_init(&reachable);
    Py_ssize_t objects_marked = 0;
    objects_marked += move_to_reachable(interp->sysdict, &reachable, visited_space);
    objects_marked += move_to_reachable(interp->builtins, &reachable, visited_space);
    objects_marked += move_to_reachable(interp->dict, &reachable, visited_space);
    struct types_state *types = &interp->types;
    for (int i = 0; i < _Py_MAX_MANAGED_STATIC_BUILTIN_TYPES; i++) {
        objects_marked += move_to_reachable(types->builtins.initialized[i].tp_dict, &reachable, visited_space);
        objects_marked += move_to_reachable(types->builtins.initialized[i].tp_subclasses, &reachable, visited_space);
    }
    for (int i = 0; i < _Py_MAX_MANAGED_STATIC_EXT_TYPES; i++) {
        objects_marked += move_to_reachable(types->for_extensions.initialized[i].tp_dict, &reachable, visited_space);
        objects_marked += move_to_reachable(types->for_extensions.initialized[i].tp_subclasses, &reachable, visited_space);
    }
    objects_marked += mark_all_reachable(&reachable, visited, visited_space);
    assert(gc_list_is_empty(&reachable));
    return objects_marked;
}

Интерпретатор особым образом работает с модулями sys и builtins. Это связано с тем, что даже во время финализации интерпретатора может быть вызван произвольный Python‑код, для которого должна быть доступна функциональность этих модулей. Словари для этих модулей хранятся в interp->sysdict и interp->builtins соответственно. Также у самого интерпретатора есть состояние, которое хранится в interp->dict. Объекты в этих словарях «живут» на протяжении всей жизни интерпретатора, поэтому мы их и их зависимости считаем живыми.

Далее, CPython содержит ряд статических типов (ранее, большинство типов было преобразовано в HeapTypes, с целью повышения уровня изоляции между интерпретаторами), которые инициализируются при создании каждого интерпретатора. Типы содержат несколько словарей — первый это словарь для состояния типа — tp_dict, второй — это список подтипов. Очевидно, что объекты в обоих словарях живы на протяжении всей жизни интерпретатора, а значит их и их зависимости тоже можно исключить из обработки сборщиком мусора.

Как можно видеть, эти объекты относятся к состоянию интерпретатора, так как каждый интерпретатор имеет собственный сборщик мусора. И единственными легитимными объектами, которые могут принадлежать нескольким сборщикам мусора, являются бессмертные объекты (CPython — бессмертные Immortal объекты).

Глобальные корневые объекты обрабатываются функцией mark_global_roots, она переносит указанные выше объекты в список reachable, при условии что эти объекты находятся в ожидающей части старшего поколения (gc_old_space(gc) != visited_space).

static intptr_t
move_to_reachable(PyObject *op, PyGC_Head *reachable, int visited_space)
{
    if (op != NULL && !_Py_IsImmortal(op) && _PyObject_IS_GC(op)) {
        PyGC_Head *gc = AS_GC(op);
        if (_PyObject_GC_IS_TRACKED(op) &&
            gc_old_space(gc) != visited_space) {
            gc_flip_old_space(gc);
            gc_list_move(gc, reachable);
            return 1;
        }
    }
    return 0;
}

static int
visit_add_to_container(PyObject *op, void *arg)
{
    struct container_and_flag *cf = (struct container_and_flag *)arg;
    int visited = cf->visited_space;
    assert(visited == get_gc_state()->visited_space);
    if (!_Py_IsImmortal(op) && _PyObject_IS_GC(op)) {
        PyGC_Head *gc = AS_GC(op);
        if (_PyObject_GC_IS_TRACKED(op) &&
            gc_old_space(gc) != visited) {
            gc_flip_old_space(gc);
            gc_list_move(gc, cf->container);
            cf->size++;
        }
    }
    return 0;
}

static intptr_t
mark_all_reachable(PyGC_Head *reachable, PyGC_Head *visited, int visited_space)
{
    // Transitively traverse all objects from reachable, until empty
    struct container_and_flag arg = {
        .container = reachable,
        .visited_space = visited_space,
        .size = 0
    };
    while (!gc_list_is_empty(reachable)) {
        PyGC_Head *gc = _PyGCHead_NEXT(reachable);
        assert(gc_old_space(gc) == visited_space);
        gc_list_move(gc, visited);
        PyObject *op = FROM_GC(gc);
        traverseproc traverse = Py_TYPE(op)->tp_traverse;
        (void) traverse(op,
                        visit_add_to_container,
                        &arg);
    }
    return arg.size;
}

Для переноса используется функция move_to_reachable, которая также проверяет, что объект не является бессмертным, поддерживает сборку мусора _PyObject_IS_GC, находится в сборщике мусора _PyObject_GC_IS_TRACKED. Если объект перемещается в список reachable, то у него также помечается как просмотренный (visited), делается это путём переворачивания соответствующего бита в указателе с помощью функции gc_flip_old_space.

Проверка бессмертных объектов

Стандартным способом иммортализации объектов является вызов функции _Py_SetImmortal. Объекты, которые иммортализуются этой функцией, удаляются из сборщика мусора. И кажется, что проверка бессмертных объектов в функции move_to_reachable лишняя, но бессмертным может стать любой объект в любой момент времени в результате Accidental Immortalization и такие объекты также необходимо из обработки исключать.

После того как сформирован список достижимых объектов, для них определяются транзитивно достижимые объекты. Делается это функцией mark_all_reachable.

Данная функция рекурсивно обрабатывает все достижимые объекты, но без использования явной рекурсии. Выпрямление происходит за счёт того, что все новые найденные объекты добавляются в конец того же списка.

Для каждого объекта в списке вызывается tp_traverse с функцией visit_add_to_container (можно заметить, что visit_add_to_container и move_to_reachable очень похожи), в которой найденные объекты добавляются в список достижимых. Проверенный объект переносится в просмотренную часть старшего поколения, а проверки продолжаются, пока список достижимых объектов не пуст.

Таким образом, глобальные корни и все объекты, которые из них достижимы, переносятся в просмотренную часть старшего поколения и до следующей фазы маркировки исключаются из обработки сборщиком мусора.

Обработка локальных корневых объектов

Помимо глобальных корневых объектов достижимыми являются локальные объекты на стеке. Их обработкой занимается функция mark_stacks.

static intptr_t
mark_stacks(PyInterpreterState *interp, PyGC_Head *visited, int visited_space, bool start)
{
    PyGC_Head reachable;
    gc_list_init(&reachable);
    Py_ssize_t objects_marked = 0;
    _PyRuntimeState *runtime = &_PyRuntime;
    HEAD_LOCK(runtime);
    PyThreadState* ts = PyInterpreterState_ThreadHead(interp);
    HEAD_UNLOCK(runtime);
    while (ts) {
        _PyInterpreterFrame *frame = ts->current_frame;
        while (frame) {
            if (frame->owner >= FRAME_OWNED_BY_INTERPRETER) {
                frame = frame->previous;
                continue;
            }
            _PyStackRef *locals = frame->localsplus;
            _PyStackRef *sp = frame->stackpointer;
            objects_marked += move_to_reachable(frame->f_locals, &reachable, visited_space);
            PyObject *func = PyStackRef_AsPyObjectBorrow(frame->f_funcobj);
            objects_marked += move_to_reachable(func, &reachable, visited_space);
            while (sp > locals) {
                sp--;
                if (PyStackRef_IsNullOrInt(*sp)) {
                    continue;
                }
                PyObject *op = PyStackRef_AsPyObjectBorrow(*sp);
                if (_Py_IsImmortal(op)) {
                    continue;
                }
                if (_PyObject_IS_GC(op)) {
                    PyGC_Head *gc = AS_GC(op);
                    if (_PyObject_GC_IS_TRACKED(op) &&
                        gc_old_space(gc) != visited_space) {
                        gc_flip_old_space(gc);
                        objects_marked++;
                        gc_list_move(gc, &reachable);
                    }
                }
            }
            if (!start && frame->visited) {
                // If this frame has already been visited, then the lower frames
                // will have already been visited and will not have changed
                break;
            }
            frame->visited = 1;
            frame = frame->previous;
        }
        HEAD_LOCK(runtime);
        ts = PyThreadState_Next(ts);
        HEAD_UNLOCK(runtime);
    }
    objects_marked += mark_all_reachable(&reachable, visited, visited_space);
    return objects_marked;
}

Какие локальные объекты являются достижимыми? Это определяется следующим образом.

Для всех потоков текущего интерпретатора (PyInterpreterState_ThreadHead и PyThreadState_Next) анализируется стек вызовов — с каждым вызовом связан собственный объект — Frame Object, а все они связаны в список через frame->previous. Анализ стека производится снизу вверх, из анализа исключаются фреймы, которые связаны с вызовом С‑функций (через проверку условия frame->owner >= FRAME_OWNED_BY_INTERPRETER).

Функция mark_stacks вызывается как в фазе маркировки, так и в фазе сборки. В последнем случае из анализа также исключаются фреймы, которые были ранее проанализированы в фазе маркировки (и отмечены соответствующим образом frame->visited = 1).

Итак, следующие объекты фрейма считаются достижимыми и добавляются в список reachable с помощью функции move_to_reachable:

Список локальных переменных фрейма (frame->f_locals)
Функция, которая выполняется (frame->f_funcobj)
Все локальные переменные на стеке, созданные виртуальной машиной (при выполнении инструкций байткода, виртуальная машина перемещает часть объектов на стек и размещает их в PyStackRef‑объектах), которые зарегистрированы в сборщике мусора (_PyObject_GC_IS_TRACKED) и которые находятся в ожидающей части старшего поколения.
1. За исключением бессмертных объектов.
2. В случае локальных переменных не используется функция move_to_reachable, хотя код практически идентичен. Это делается для того, чтобы избежать повторной проверки условия при подсчёте достижимых объектов.

Для определения локальных переменных на стеке используется условный указатель на начало стека frame->localsplus и указатель на текущее положение на стеке frame->stackpointer.

После того как сформирован список reachable (это отдельный список — mark_global_roots и mark_stacks имеют собственные списки reachable) аналогичным образом вызывается функция mark_all_reachable, которая переносит ожидающие (pending) объекты в просмотренную часть старшего поколения.

Аналогично тому как делается для глобальных корневых объектов, локальные объекты, и достижимые из них объекты считаются достижимыми, то есть живыми и просто переносятся в просмотренную часть старшего поколения, без вызова основной процедуры сборки мусора.

На этом обработка корневых объектов заканчивается, а также заканчивается фаза маркировки.

Фаза сборки

При следующем вызова инкрементальной сборки мусора будет выполнена фаза сборки, и если work_to_do имеет значение выше 0, то запустится процедура mark_stacks, а также скорректируется значение work_to_do.

После этого все оставшиеся объекты молодого поколения будут перемещены в список increment. Тут стоит заметить следующее: в настоящее время сборка мусора устроена так, что она вызывается только при выполнении определённых инструкций виртуальной машины (подробнее смотри в первой части — CPython — сборка мусора изнутри, ч.1). Для нас важно, что при наступлении этих событий интерес с точки зрения сборки мусора будут представлять объекты, которые были удалены из списков локальных и глобальных объектов, но при этом находятся в каких‑либо циклах. В большинстве случаев мы работаем с объектами, которые не входят в циклы, а значит, либо уничтожаются механизмом подсчёта ссылок, либо будут перемещены в просмотренную часть во время вызова mark_stacks.

Т.о. в молодом поколении может оказаться небольшое количество объектов. И следующим выполняется цикл заполнения инкремента.

Определение транзитивно достижимых объектов при построении инкремента

Как было сказано выше, если количество элементов в молодом поколении меньше требуемого (work_to_do), то в инкремент будут добавляться объекты из ожидающей части старшего поколения, а также транзитивно из них достижимые.

Транзитивно достижимые объекты

Мы можем быть уверены, что все живые объекты перемещаются в просмотренную часть старшего поколения. Поэтому при определении транзитивно достижимых объектов мы всегда работаем с объектами из ожидающей части старшего поколения.

Для определения транзитивно достижимых объектов используется функция expand_region_transitively_reachable, которая, так же как и mark_all_reachable, рекурсивно обходит все объекты. Для обхода используется tp_traverse и visit_add_to_container. Так же как и для mark_all_reachable, рекурсия выпрямляется, но несколько другим способом. Если в случае с mark_all_reachable все объекты из списка достижимых переносятся в просмотренную часть старшего поколения и достаточно проверить, что список reachable пуст. То в случае expand_region_transitively_reachable используется тот факт, что все списки, которые используются в сборщике мусора: а) двусвязные, б) кольцевые. Т.е. в каком бы направлении мы ни обходили эти списки, мы всегда придём в начальный элемент. И этот факт используется для остановки обхода.

static intptr_t
expand_region_transitively_reachable(PyGC_Head *container, PyGC_Head *gc, GCState *gcstate)
{
    struct container_and_flag arg = {
        .container = container,
        .visited_space = gcstate->visited_space,
        .size = 0
    };
    assert(GC_NEXT(gc) == container);
    while (gc != container) {
        /* Survivors will be moved to visited space, so they should
         * 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, &gcstate->permanent_generation.head);
            gc = next;
            continue;
        }
        traverseproc traverse = Py_TYPE(op)->tp_traverse;
        (void) traverse(op,
                        visit_add_to_container,
                        &arg);
        gc = GC_NEXT(gc);
    }
    return arg.size;
}

Бессмертные объекты также не добавляются в инкремент.

Бессмертные объекты

На момент написания данной заметки имеется дефект, в результате которого бессмертные объекты перемещаются в постоянное поколение. На мой взгляд, это некорректное поведение, и оно должно быть исправлено, чтобы соответствовать другим местам — бессмертные объекты должны исключаться из сборки мусора.

gh-137110: Untrack immortal objects from expand_region_transitivity_reachable — реквест для исправления дефекта.

Пополнение инкремента осуществляется до тех пор, пока его размер будет меньшее work_to_do.

Главная функция сборки мусора

После формирования инкремента вызывается главная функция сборки мусора — gc_collect_region. Это «сердце» сборщика мусора, которое довольно стабильно, и отвечает за определение достижимых и недостижимых объектов, вызов финализаторов и разрыв циклов.

Я опишу её отдельно, так как описание довольно объёмно. Сейчас для нас важно следующее — все объекты, которые не будут удалены во время выполнения gc_collect_region, попадут в список survivors и затем будут перемещены в просмотренную часть старшего поколения.

Завершение фазы сборки

Если ожидающая часть старшего поколения пуста, то фаза сборки завершается и активная фаза переключается на фазу маркировки. Также при этом сбрасывается размер инкремента. За завершение фазы сборки отвечает функция completed_scavenge.

static void
completed_scavenge(GCState *gcstate)
{
    /* We must observe two invariants:
    * 1. Members of the permanent generation must be marked visited.
    * 2. We cannot touch members of the permanent generation. */
    int visited;
    if (gc_list_is_empty(&gcstate->permanent_generation.head)) {
        /* Permanent generation is empty so we can flip spaces bit */
        int not_visited = gcstate->visited_space;
        visited = other_space(not_visited);
        gcstate->visited_space = visited;
        /* Make sure all objects have visited bit set correctly */
        gc_list_set_space(&gcstate->young.head, not_visited);
    }
    else {
         /* We must move the objects from visited to pending space. */
        visited = gcstate->visited_space;
        int not_visited = other_space(visited);
        assert(gc_list_is_empty(&gcstate->old[not_visited].head));
        gc_list_merge(&gcstate->old[visited].head, &gcstate->old[not_visited].head);
        gc_list_set_space(&gcstate->old[not_visited].head, not_visited);
    }
    assert(gc_list_is_empty(&gcstate->old[visited].head));
    gcstate->work_to_do = 0;
    gcstate->phase = GC_PHASE_MARK;
}

Но не всё так просто. Как было сказано ранее, существует постоянное поколение permanent_generation, в него попадают объекты при заморозке сборки мусора.

Заморозка

Функция gc.freeze/_PyGC_Freeze переносит объекты из молодого и обоих частей старшего поколений в permanent_generation, а также переводит все перенесённые объекты в состояние просмотренный.

Функция gc.unfreeze/_PyGC_Unfreeze выполняет обратную операцию и переносит все объекты из permanent_generation в просмотренную часть старшего поколения.

Если постоянное поколение не пустое, то при завершении фазы сборки не происходит переключение активной части старшего поколения. gcstate->visited_space не меняется, а все объекты из просмотренной части старшего поколения переносятся в ожидающую.

В случае если постоянное поколение пусто, то мы можем просто поменять, какая часть старшего поколения считается активной — просмотренная часть станет ожидающей, ожидающая — просмотренной. Новое значение активной части старшего поколения будет проставлено для всех объектов молодого поколения.

Почему молодое поколение не пустое

Почему молодое поколение не пустое, хотя мы находимся в конце функции сборки мусора?

Удалением неиспользуемых объектов занимается функция gc_collect_region, которая будет рассмотрена в следующей части. Здесь же я дам небольшое пояснение.

При удалении неиспользуемых объектов может быть совершенно произвольное количество вызовов в Python — через tp_finalize, через ��ункции обратного вызова у слабых ссылок, даже из tp_dealloc. Любой вызов в Python может привести к выполнению произвольного кода и создании новых объектов в молодом поколении. Т.к. повторная сборка мусора не может быть запущена, то созданные объекты останутся в молодом поколении, так как в старшее попасть они не могут.

Выполняемый скрипт, может создать достаточное количество объектов, чтобы их количество соответствовало граничным значениям для вызова сборки мусора. Но процедура, которая делает проверки в том числе проверяет, что сборка мусора уже выполняется.

А повторно вызывать gc.collect во время сборки мусора запрещено, так как его поведение не определено:

The effect of calling gc.collect() while the interpreter is already performing a collection is undefined.

Отсюда мы получаем, что в некоторых случая во время завершения фазы сборки молодое поколение может содержать объекты.

На этом заканчивается процедура инкрементальной сборки мусора. И у нас осталась не рассмотренной полная сборка мусора, которая вызывается через gc.collect(2). В текущей версии CPython она состоит из функций и процедур, которые мы рассмотрели в этой и предыдущей части, и имеет смысл разобрать её в этой статье.

Полная сборка мусора

За полную сборку мусора отвечает функция gc_collect_full.

static void
gc_collect_full(PyThreadState *tstate,
                struct gc_collection_stats *stats)
{
    GCState *gcstate = &tstate->interp->gc;
    PyGC_Head *young = &gcstate->young.head;
    PyGC_Head *pending = &gcstate->old[gcstate->visited_space^1].head;
    PyGC_Head *visited = &gcstate->old[gcstate->visited_space].head;
    untrack_tuples(young);
    /* merge all generations into visited */
    gc_list_merge(young, pending);
    gc_list_set_space(pending, gcstate->visited_space);
    gcstate->young.count = 0;
    gc_list_merge(pending, visited);

    gc_collect_region(tstate, visited, visited, stats);
    gcstate->young.count = 0;
    gcstate->old[0].count = 0;
    gcstate->old[1].count = 0;
    completed_scavenge(gcstate);
    _PyGC_ClearAllFreeLists(tstate->interp);
}

Как следует из названия — функция выполняет полную сборку мусора. Для этого все объекты из молодого поколения и ожидающей части старшего поколения переносятся в просмотренную часть старшего поколения. И для объединённого списка запускается основная функция сборки мусора gc_collect_region.

Все объекты, которые переживут сборку, будут снова добавлены в просмотренную часть старшего поколения. После чего будет выполнена процедура завершения сборки completed_scavenge с возможным переключением активных частей старшего поколения. И в целом всё.

Единственное, с чем мы не сталкивались ранее — это очистка свободных списков _PyGC_ClearAllFreeLists. Ранее мы говорили только о сборке мусора на уровне объектов Python и не будем углубляться в вопросы, связанные с выделением и освобождением памяти. Краткая заметка о свободных списках ниже.

Свободные списки

В Python существует оптимизация, связанная с выделением памяти для объектов. Ранее выделенная память при освобождении объекта не возвращается в аллокатор и, соответственно, операционную систему. Такой подход имеет преимущества, если производится выделение большого количества объектов, которые поддерживают free-list. Для некоторых объектов есть ограничения на размер свободных списков, для некоторых — нет.

Free-list устроен в виде стека, когда в стеке есть доступные элементы, то они забираются оттуда и выполняется их переинициализация (in-place initialization), когда приходит время освобождать данный объект, то он возвращается в стек free-list, если размер стека меньше ограничения.

Вызов _PyGC_ClearAllFreeLists приводит в _PyObject_ClearFreeLists, в которой можно увидеть какие списки очищаются. Очистка списков позволяет использовать различные функции для освобождения объектов. На текущий момент используются следующие:

free_object
PyMem_Free
PyMem_RawFree
PyObject_GC_Del

Нас, как было сказано выше, будут интересовать только free_object и PyObject_GC_Del.

В случае free_object для объекта вызывается tp_free и уменьшается количество ссылок на тип объекта Py_DECREF(object_type).

В случае PyObject_GC_Del объект удаляется из сборщика мусора (gc_list_remove — выполняет те же действия, что и PyObject_GC_UnTrack, за исключением обнуления указателя на предыдущий объект в списке), уменьшается количество объектов в молодом поколении, уменьшается общее количество выделенных объектов gcstate->heap_size и очищается объект через вызов PyObject_Free.

После вызова всех функций перед окончанием сборки мусора сбрасываются значения для количества объектов в молодом поколении и количестве произведённых сборок в старшем поколении.

На этом с полной сборкой мусора всё.

Заключение

В этой части мы рассмотрели инкрементальную сборку мусора и полную сборку мусора. Разобрали как определяются глобальные корневые объекты и локальные объекты, которые продляют время жизни зависимым объектам.

В следующей части мы рассмотрим основную функцию сборки мусора — gc_collect_region, разберём алгоритм определения недостижимых объектов и как разрываются циклические ссылки.

Спасибо за внимание.

CPython — Сборка мусора изнутри, ч.3

Оглавление