Как то раз я попал на вечеринку опенсорсеров и там обсуждали очередной баг связанный со сборщиком мусора в CPython. И так получилось, что я попробовал баг исправить, нашел причину проблемы и сделал два реквеста. И если первый реквест был просто не правильный, то второй не прошел проверку качества со стороны владельцев кода. И после этого решил основательно разобраться с тем, как устроена сборка мусора в современном CPython.
Если вам интересно, давайте попробуем сделать это вместе.
В сети есть довольно много ресурсов, на которых работа сборщика мусора в Python объясняется с разной степенью погружения. Наиболее близкие статьи на данную тему это CPython Reference Counting and Garbage Collection Internals и CPython's Garbage Collector and its Impact on Application Performance. Мне в этих статьях не хватило деталей реализации и пришлось копнуть чуть глубже. И на основе конспектов родилась эта серия статей.
Т.к. я планирую разобраться, как устроен механизм автоматической сборки мусора в CPython, какие он имеет эффекты и как связан с рантаймом, то буду много говорить о деталях реализации. Я не уверен, что это сильно поможет писать программы на Python лучше, но должно быть полезно если вы хотите узнать, как работает CPython изнутри. Далее я буду употреблять Python, подразумевая реализацию CPython.
С другой стороны, в рабочих чатиках иногда появляются вопросы, связанные с временем жизни объектов в Python, а правильных ответов почти не дают.
Итак, пора начинать!
Оглавление
Как работает сборщик мусора в CPython с включенными GIL
Рассматривать будем работу сборщика мусора в версии Python, в которой включен GIL. В настоящее время free-threading или no-gil версия больше не является экспериментальной и сборка мусора в ней довольно сильно отличается от обычной версии и требует отдельного подхода.
Когда мы говорим сборщик мусора в Python, что мы подразумеваем? Первое что приходит на ум, это модуль gc, который позволяет управлять сборкой мусора. Если мы выключим сборщик мусора посредством вызова gc.disable() то перестанут ли удаляться объекты в Python?
Нет, не перестанут.
И главная причина в том, что основной механизм автоматического управления временем жизни объектов в Python — это подсчет ссылок. Согласно The Garbage Collection Handbook он является одной из стратегий автоматической сборки мусора:
All garbage collection schemes are based on one of four fundamental approaches: mark sweep collection, copying collection, mark‑compact collection, reference counting or some combination of these.
И включить или отключить этот механизм нельзя.
Чем же тогда управляет модуль gc? Зачастую, когда мы в Python говорим gc мы имеем в виду циклический сборщик мусора — cyclic garbage collector. Его основная задача находить и обрабатывать циклы, и удалять объекты, которые в эти циклы входят. Во времена версии 3.4 эта проблема была формализована и был принят PEP-442, в котором были даны следующие формулировки:
Reference cycle
A cyclic subgraph of directional links between objects, which keeps those objects from being collected in a pure reference-counting scheme.Cyclic garbage collector (GC)
A device able to detect cyclic isolates and turn them into cyclic trash. Objects in cyclic trash are eventually disposed of by the natural effect of the references being cleared and their reference counts dropping to zero.Cyclic isolate (CI)
A standalone subgraph of objects in which no object is referenced from the outside, containing one or several reference cycles, and whose objects are still in a usable, non-broken state: they can access each other from their respective finalizers.Cyclic trash (CT)
A former cyclic isolate whose objects have started being cleared by the GC. Objects in cyclic trash are potential zombies; if they are accessed by Python code, the symptoms can vary from weirdAttributeErrorsto crashes.
Мы разберем, как работает подсчет ссылок и как устроен циклический сборщик мусора.
Объекты, которые поддерживают сборку мусора
Механизм подсчета ссылок является базовым для CPython. Все объекты содержат счетчик ссылок и их использование приводит к изменению его значения (за исключением бессмертных объектов).
object -----> +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ /
| ob_refcnt | \
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | PyObject_HEAD
| *ob_type | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ /
| ... |Самые простые примеры использования объектов это передача их в функцию или сохранение на них ссылок в каких-либо других объектах. Объекты, которые содержат ссылки на другие объекты называются контейнерами. Описание модели данных дает следующее определение для контейнеров:
Some objects contain references to other objects; these are called containers. Examples of containers are tuples, lists and dictionaries.
Под это определение подходят не только привычные нам типы коллекций, но и пользовательские типы (наш опыт является иллюстраций этого - зачастую в объектах пользовательских типов мы храним ссылки на составные части этих объектов).
Эта необходимость хранить ссылки на другие объекты, иногда приводит к появлению циклических ссылок, когда один объект ссылается на другой объект, другой на третий и т.д. пока последний не ссылается снова на первый. Иногда это является ошибкой реализации в пользовательской программе, иногда необходимостью. Ранее, для разрешение циклических зависимостей, часто использовались слабые ссылки, которые не содержат сильную ссылку на исходный объект, но позволяют получить к нему доступ. Определение сильной ссылки давно в глоссарии Python:
In Python’s C API, a strong reference is a reference to an object which is owned by the code holding the reference. The strong reference is taken by calling
Py_INCREF()when the reference is created and released withPy_DECREF()when the reference is deleted.The
Py_NewRef()function can be used to create a strong reference to an object. Usually, thePy_DECREF()function must be called on the strong reference before exiting the scope of the strong reference, to avoid leaking one reference.
В нашем случае важно, что сильная ссылка увеличивает значение счетчика ссылок у объекта, а слабая нет.
Циклические ссылки препятствуют автоматическому управлению памятью. Если два объекта ссылаются друг на друга, и на них отсутствуют ссылки извне - то у них все равно значения счетчика ссылок больше 0, что не позволяет им быть удаленными.
Забавный факт
Любая программа на языке Python имеет циклические ссылки. Любой тип, который содержит MRO держит сильную ссылку на самого себя.
В CPython используется циклический сборщик мусора, или для простоты - сборщик мусора, для разрешения циклических ссылок.
Не все объекты поддерживают сборщик мусора (или сборку мусора, также для простоты изложения). Во-первых, так исторически сложилось. Сборщик мусора был добавлен в CPython не сразу. Во-вторых, не для всех объектов имеет смысл поддерживать сборщик мусора. Помимо контейнеров, существуют объекты, которые не могут и не содержат ссылок на другие объекты, например NoneType, int, float и другие примитивные типы. А раз так, то они никогда не могут стать частью цикла, и поэтому не имеет смысла делать у них поддержку сборщика мусора.
Это имеет положительные эффекты. Первый эффект - чем меньше объектов попадает в сборщик мусора, тем меньше требуется времени на их обработку. Второй эффект - каждый объект, поддерживающий сборку мусора, имеет дополнительный заголовок, который называется PyGC_Head:
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ \
| *_gc_next | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | PyGC_Head
| *_gc_prev | |
object -----> +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ /
| ob_refcnt | \
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | PyObject_HEAD
| *ob_type | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ /
| ... |Таким образом, если PyGC_Head у объекта отсутствует, то объект занимает меньше места в памяти.
Итак, какие объекты поддерживают сборку мусора, а какие нет? Это определяется типом объекта, а конкретнее флагами типа. Если у типа в флагах определен бит Py_TPFLAGS_HAVE_GC, то такой тип сборку мусора поддерживает.
В программах на языке Python мы напрямую этим битом не управляем. При создании пользовательских классов происходит следующая цепочка вызовов (где LOAD_BUILD_CLASS операция виртуальной машины):
LOAD_BUILD_CLASS -> ... -> builtin___build_class__ -> ...
-> type_call -> type_new -> type_new_impl -> type_new_init -> type_new_allocКоторая приводит к функции type_new_alloc, в которой есть следующий код:
// Initialize tp_flags.
// All heap types need GC, since we can create a reference cycle by storing
// an instance on one of its parents.
type_set_flags(type, Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HEAPTYPE |
Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_GC);Как мы видим, для всех пользовательских типов явно устанавливается флаг поддержки сборки мусора.
Но это не единственный способ создать пользовательский класс. CPython позволяет разрабатывать модули расширений на языке С, где доступны два способа описания типов:
PyType_Spec, для динамических типов илиheap-typesPyTypeObject, для статических типов
Обе структуры имеют поле flags, предназначенное для указания необходимых флагов. В этом случае корректность заполнения флагов лежит на пользователе. Если у пользовательского типа не указана поддержка сборщика мусора, а тип является контейнерным, то циклические ссылки с объектами такого типа сборщиком мусора обрабатываться не будут и могут возникнуть утечки памяти.
Итак, если объект поддерживает сборку мусора, то что происходит при его создании?
Создание объектов, поддерживающих сборку мусора
Если тип поддерживает сборку мусора, то конструктор должен использовать функции PyObject_GC_New или PyObject_GC_NewVar для выделения памяти для объектов, и PyObject_GC_Track для регистрации объектов в сборщике мусора. Аналогично, деструктор должен использовать PyObject_GC_UnTrack для дерегистрации объектов из сборщика мусора и очищать память с помощью PyObject_GC_Del (подробнее в документации).
В функциях PyObject_GC_New и PyObject_GC_NewVar нас будет интересовать вызов _PyObject_GC_Link:
Вопреки своему названию функция _PyObject_GC_Link делает не то, о чем можно подумать. Она выполняет три задачи:
Инициализирует поля в
PyGC_Head, связанные с регистрацией объекта в сборщике мусора.Обновляет информацию в
gcstateо количестве созданных объектов.Планирует сборку мусора.
Обратная функция PyObject_GC_Del выполняет, если необходимо, дерегистрацию объекта из сборщика мусора и обновляет информация в gcstate о количестве созданных объектов.
Рассмотрим как происходит регистрация и дерегистрация объектов с сборщике мусора.
Регистрация и дерегистрация объектов в сборщике мусора
Если коротко, то регистрация объектов в сборщике мусора, это добавление объектов в список молодого поколения (о поколениях мы будем говорить отдельно). Дерегистрация, соответственно, это удаление объекта из списка, в котором объект находится в данный момент - это может быть список любого поколения, или промежуточный список, используемый во время сборки мусора.
Регистрация объектов в сборщике мусора
Как было сказано выше, каждый объект, который поддерживает сборку мусора имеет дополнительный заголовок PyGC_Head:
/* GC information is stored BEFORE the object structure. */
typedef struct {
// Tagged pointer to next object in the list.
// 0 means the object is not tracked
_Py_ALIGNED_DEF(_PyObject_MIN_ALIGNMENT, uintptr_t) _gc_next;
// Tagged pointer to previous object in the list.
// Lowest two bits are used for flags documented later.
// Those bits are made available by the struct's minimum alignment.
uintptr_t _gc_prev;
} PyGC_Head;Как видно, данная структура представляет собой узел двусвязного списка и имеет указатели на следующий и предыдущий объекты. Структура хранит маркированные указатели (tagged pointers). Использование маркированных указателей доступно благодаря требованию о выравнивании, которое приводит к тому, что несколько младших бит не содержат значимые для указателей значения.
Маркированные указатели
Хороший материал о маркированных указателях я видел здесь - Theory and implementation of tagged pointers. С краткой информацией можно ознакомиться здесь - Tagged pointers and object headers - Writing Interpreters in Rust: a Guide
Каждый из указателей (_gc_prev и _gc_next) содержит разную дополнительную информацию:
_gc_prev - 0x00000000 00000000 00000000 00000000
^^
||- _PyGC_PREV_MASK_FINALIZED
|-- _PyGC_PREV_MASK_COLLECTING
_gc_next - 0x00000000 00000000 00000000 00000000
^
|-- _PyGC_NEXT_MASK_OLD_SPACE_1
/* Bit flags for _gc_prev */
/* Bit 0 is set when tp_finalize is called */
#define _PyGC_PREV_MASK_FINALIZED ((uintptr_t)1)
/* Bit 1 is set when the object is in generation which is GCed currently. */
#define _PyGC_PREV_MASK_COLLECTING ((uintptr_t)2)
/* Bit 0 in _gc_next is the old space bit.
* It is set as follows:
* Young: gcstate->visited_space
* old[0]: 0
* old[1]: 1
* permanent: 0
*
* During a collection all objects handled should have the bit set to
* gcstate->visited_space, as objects are moved from the young gen
* and the increment into old[gcstate->visited_space].
* When object are moved from the pending space, old[gcstate->visited_space^1]
* into the increment, the old space bit is flipped.
*/
#define _PyGC_NEXT_MASK_OLD_SPACE_1 1Задача _PyObject_GC_Linkобнулить указатели _gc_prev и _gc_next. А значит, показать, что объект не зарегистрирован в сборщике мусора.
Что происходит при регистрации объекта?
Каждый интерпретатор (сейчас уже можно говорить что версия 3.14 официально поддерживает работу с несколькими интерпретаторами, подробнее смотри, например, PEP-734: Субинтерпретаторы в Python 3.14) имеет собственный независимый сборщик мусора, а значит и собственную структуру _gc_runtime_state:
struct _gc_runtime_state {
/* List of objects that still need to be cleaned up, singly linked
* via their gc headers' gc_prev pointers. */
PyObject *trash_delete_later;
/* Current call-stack depth of tp_dealloc calls. */
int trash_delete_nesting;
/* Is automatic collection enabled? */
int enabled;
int debug;
/* linked lists of container objects */
struct gc_generation young;
struct gc_generation old[2];
/* a permanent generation which won't be collected */
struct gc_generation permanent_generation;
struct gc_generation_stats generation_stats[NUM_GENERATIONS];
/* true if we are currently running the collector */
int collecting;
/* list of uncollectable objects */
PyObject *garbage;
/* a list of callbacks to be invoked when collection is performed */
PyObject *callbacks;
Py_ssize_t heap_size;
Py_ssize_t work_to_do;
/* Which of the old spaces is the visited space */
int visited_space;
int phase;
};Нас в данном случае будут интересовать поля young, old, permanent_generation. Каждое поле является следующей структурой:
struct gc_generation {
PyGC_Head head;
int threshold; /* collection threshold */
int count; /* count of allocations or collections of younger
generations */
};Нас в этой структуре будет интересовать head - это заголовок списка. Во время инициализации интерпретатора, указатели _gc_prev и _gc_next заголовка устанавливаются таким образом, чтобы указывать на заголовок (см. функцию _PyGC_InitState). Начальное состояние поколения можно изобразить в виде бинарного дерева (на мой взгляд, представление в виде бинарного дерева более наглядное, т.к. позволяет отобразить дополнительную информацию, которая содержится в маркированных указателях):
При добавлении нового объекта в список, в отладочной версии, проверяется, что объект находится в незарегистрированном состоянии.
Т.к. _gc_prev и _gc_next являются маркированными указателями, нельзя просто взять и связать новый объект со списком. Для установки указателей используются функции _PyGCHead_SET_NEXT и _PyGCHead_SET_PREV.
#define _PyGC_PREV_SHIFT 2
#define _PyGC_PREV_MASK (((uintptr_t) -1) << _PyGC_PREV_SHIFT)
static inline void _PyGCHead_SET_NEXT(PyGC_Head *gc, PyGC_Head *next) {
uintptr_t unext = (uintptr_t)next;
assert((unext & ~_PyGC_PREV_MASK) == 0);
gc->_gc_next = (gc->_gc_next & ~_PyGC_PREV_MASK) | unext;
}
static inline void _PyGCHead_SET_PREV(PyGC_Head *gc, PyGC_Head *prev) {
uintptr_t uprev = (uintptr_t)prev;
assert((uprev & ~_PyGC_PREV_MASK) == 0);
gc->_gc_prev = ((gc->_gc_prev & ~_PyGC_PREV_MASK) | uprev);
}Разбор битовой арифметики
_PyGC_PREV_SHIFTимеет значение 2, потому что мы используем младшие два бита у указателя_gc_prev.
_PyGC_PREV_MASKимеет значение, у которого младшие два бита нулевые, а остальные единицы.
~_PyGC_PREV_MASKимеет значение равное трем, т.к. у него младшие биты установлены в 1, а остальные нулевые.
Обе функции выполняют одинаковые битовые операции со значениями переданных указателей - взять младшие два бита от одного указателя и подмешать их к другому указателю.
Таким образом, _PyGCHead_SET_NEXTсвязывает указатель на предыдущий объект у головы списка с новым объектом, условно young.head._gc_prev._gc_next = gc, а _PyGCHead_SET_PREVнаоборот gc._gc_prev = young.head._gc_prev.
Далее у нового объекта указатель на следующий элемент связывается с головой списка молодого поколения, с установленным номером старшего поколения: gc._gc_next = young.head | not_visited_space (про номер старшего поколения поговорим тоже отдельно, здесь достаточно отметить, что указатель маркируется).
Указатель на предыдущий объект у головы списка просто связывается с новым объектом. В коде это выглядит следующим образом:
PyGC_Head *last = (PyGC_Head*)(young.head->_gc_prev);
_PyGCHead_SET_NEXT(last, gc);
_PyGCHead_SET_PREV(gc, last);
uintptr_t not_visited = 1 ^ interp->gc.visited_space;
gc->_gc_next = ((uintptr_t)young.head) | not_visited;
young.head->_gc_prev = (uintptr_t)gc;Схематично добавление нового объекта в список можно показать следующим образом:
Если добавить еще один объект, то структура списка будет следующая:
На схемах видно, что если двигаться только по правым ветвям _gc_next, то мы обойдем список в направлении, в котором объекты добавлялись в список. Если пойти только по левым ветвям _gc_prev, то обойдем список в обратном направлении. Также стоит заметить, что списки закольцованы - при обходе списка всегда возвращаешься в его голову. Эта возможность часто используется в алгоритмах сборщика мусора.
Дерегистрация объектов из сборщика мусора
Т.к. все списки в сборщике мусора двусвязные, то для дерегистрации объекта достаточно этот объект вырезать из списка - т.е. указатели предыдущего и следующего объектов связать между собой.
При этом у самого объекта нужно сохранить информацию в маркированных указателях - один из битов указателя на предыдущий объект содержит информацию о том, был ли объект финализирован. Это препятствует повторной финализации объекта, если он был каким-либо образом воскрешен в ходе сборки мусора.
Чтобы получить чистые указатели из _gc_prev и _gc_next используются функции _PyGCHead_PREV и _PyGCHead_NEXT:
// Lowest two bits of _gc_prev is used for _PyGC_PREV_MASK_* flags.
static inline PyGC_Head* _PyGCHead_PREV(PyGC_Head *gc) {
uintptr_t prev = (gc->_gc_prev & _PyGC_PREV_MASK);
return (PyGC_Head*)prev;
}
// Lowest bit of _gc_next is used for flags only in GC.
// But it is always 0 for normal code.
static inline PyGC_Head* _PyGCHead_NEXT(PyGC_Head *gc) {
uintptr_t next = gc->_gc_next & _PyGC_PREV_MASK;
return (PyGC_Head*)next;
}Как мы видели ранее у _PyGC_PREV_MASK младшие два бита равны нулю и таким образом обе функции возвращают указатели, у которых младшие два бита сброшены.
Сама функция _PyObjectGC_UNTRACK выполняет следующее:
PyGC_Head *gc = _Py_AS_GC(op);
PyGC_Head *prev = _PyGCHead_PREV(gc); // gc->_gc_prev
PyGC_Head *next = _PyGCHead_NEXT(gc); // gc->_gc_next
_PyGCHead_SET_NEXT(prev, next); // gc->_gc_prev->_gc_next = gc->_gc_next
_PyGCHead_SET_PREV(next, prev); // gc->_gc_next->_gc_prev = gc->_gc_prev
gc->_gc_next = 0;
gc->_gc_prev &= _PyGC_PREV_MASK_FINALIZED;Обнуление указателя на следующий элемент сигнализирует о том, что объект был дерегистрирован из сборщика мусора, проверяется в _PyObject_GC_IS_TRACKED.
Код gc->_gc_prev &= _PyGC_PREV_MASK_FINALIZED сохраняет только младший бит у указателя на предыдущий объект, и таким образом сохраняется информация о том, были ли объект финализирован.
Объект может быть повторно добавлен в сборщик мусора (в некоторых случаях используется такой трюк), но функции _PyGCHead_NEXTи _PyGCHead_PREVсохраняют этот бит.
Схематично дерегистрация может быть представлена следующим образом (дерегистрируется объект А, пунктиром обозначаются объекты и связи которые были удалены):
Планирование сборки мусора
Как было сказано выше _PyObject_GC_Link планирует сборку мусора, а это означает что планирование происходит только при создании новых объектов. Планирует означает, что если определенные условия выполняются, то во внутренней структуре интерпретатора выставляется флаг, указывающий на необходимость сборки мусора.
Какие условия должны выполниться?
Во-первых, проверяется количество объектов в молодом поколении young.count. Функции _PyObject_GC_Linkи PyObject_GC_Del изменяют его значение. Также это значение сбрасывается после любого вызова gc.collect или _PyGC_Collect. Если количество объектов в молодом поколении больше, чем граничное значение, заданной с помощью gc.set_threshold, то одно из условий считается выполненным.
Во-вторых, проверяется что сборщик мусора включен. Сборщик мусора можно отключить двумя способами. Первый способ - совершить вызов gc.disable. Второй способ задать граничное значение для молодого поколения равным 0 - т.е. сделать вызов gc.set_threshold(0). Если сборщик мусора включен, то второе условие считается выполненным.
Следующим проверятся, не выполняется ли сборка мусора в данный момент. Если сборка мусора выполняется, то третье условие считается не выполненным и сборка мусора запланирована не будет.
И последним проверяется, чтобы все предыдущие вызовы произошли без ошибок.
Если все условия выполняются, то планируется запуск сборщика мусора. Для этого вызывается функция _Py_ScheduleGC.
Функция _Py_ScheduleGC проверяет, не запланирована ли уже сборка мусора. И если не запланирована устанавливает соответствующий бит в eval_breaker.
Eval breaker
Ранее за планирование GC отвечал отдельный флаг в состоянии интерпретатора interp->ceval->gc_scheduled . Но осенью 2023 года этот флаг и некоторые другие были объединены вместе с eval_breaker для ускорения доступа к ним (GH-109369: Merge all eval-breaker flags and monitoring version into one word).
В начале 2024 года eval_breaker был перенесен из состояния интерпретатора в состояние потока (gh-112175: Add eval_breaker to PyThreadState). Сделано это было ради free-threading версии, чтобы была возможность остановить любой исполняемый поток.
Это изменения были сделаны в версии 3.13.
Нас будут интересовать два момента. Во-первых, теперь за планирование GC отвечает бит _PY_GC_SCHEDULED_BIT = 1<<4 и для работы с ним применяются атомарные операции.
Во-вторых, когда проверяется этот бит и осуществляется запланированная сборка мусора?
За вызов запланированной сборки мусора отвечает _Py_RunGC, которая вызывается из _Py_HandlePending.
Очень долгое время проверка eval_breaker выполнялась периодически, но в начале 2020 года ситуация изменилась и проверки перестали иметь периодический характер и были явно прописаны в определенные байткод инструкции (Only check evalbreaker after calls and on backwards egdes). В pycore_opcode_metadata.h можно отыскать опкоды, которые содержат HAS_EVAL_BREAK_FLAG, в них происходят вызовы _Py_HandlePending.
Для нас важно, что _Py_HandlePending(или check_periodics) вызывается после вызова функций, и в циклах, а значит в эти моменты может произойти запланированная сборка мусора.
Заключение
В этой заметки мы рассмотрели, какие механизмы автоматической сборки мусора присутствуют в CPython, почему возникают циклы, как объекты регистрируются в циклическом сборщике мусора и когда происходит сборка мусора.
В следующих частях я планирую рассмотреть сами процедуры сборки мусора - для молодого поколения, инкрементальную и полную сборку мусора, основной цикл сборки мусора и определение недостижимых объектов.
Спасибо за внимание.
sobolevn
Шикарная статья, спасибо!
zzzzzzerg Автор
Спасибо!