---
disqus: 8thedition
---
[主頁](https://hackmd.io/@8thEdition) > [深入Python記憶體回收機制(Garbage Collection)](https://hackmd.io/@8thEdition/garbage_collection) > 標記清除演算法(Mark and Sweep)與分代機制
###### tags: `Python`, `CPython`, `Garbage Collection`, `Mark and Sweep`, `Generation`
# 標記與清除演算法(Mark and Sweep)與分代機制
## 引用計數的問題
[上一篇](https://hackmd.io/@8thEdition/cpython_garbage_collection_reference_counting)已經介紹了CPython最主要的記憶體回收機制，大多數用不到的物件都可以藉由引用技術機制回收，但為什麼說是大部分而不是全部呢？那是因為一旦遇到循環引用(reference cycles)的情況，就會導致物件引用數量永不為0，造成引用計數無法進行垃圾回收，簡單舉個例子吧：
---
```python=
import gc
a = []
a.append(a)
del a
```
---
像上述的例子，由於指派給a的這個list物件循環引用了自己，使得此物件引用數量為2，然而del a之後，只會讓這個list物件的引用數量降為1，而我們沒有任何方法使這個物件的引用數量降回0，因此引用計數在這種情況是毫無作用的。
為了解決這個問題，CPython採用了標記-清除的輔助垃圾回收機制，這是個什麼樣子的機制呢？
## 標記-清除垃圾回收機制
此機制大致分為兩步驟:
1. 標記：遍歷可能產生循環引用的物件列表(Garbage Collect物件列表，簡稱為GC物件列表)，將物件分為可達(reachable)與不可達(unreachable)。所謂可達表示該物件有變量的引用，或是有可達物件的引用。
```python=
# []物件有a變量引用，因此為可達
a = []
# {}物件有a這個可達物件引用，因此為可達
a.append({})
# 刪除a變量，[]與{}皆為不可達
del a
```
2. 清除：回收不可達的物件
接著我們來說說這個回收機制是怎麼運作的吧！不過為了避免冗長的名詞，此篇我們若提到垃圾回收，就是指CPython在回收記憶體時的輔助機制-**標記-清除垃圾回收**喔！
## 分代機制
我們可以先想想，當我們有了GC物件列表，該多久去掃一次這個GC列表呢？最簡單的想法，我們可以每過一段時間就去掃一次這個列表，並將不可達的物件做回收，沒錯！其實就這麼簡單！
不過再想想，每次都掃過整個GC物件列表，聽起來就效率很差啊！這可怎麼辦？我們可以先來思考一下我們創造出來的物件都有什麼特性？通常，我們常常在一個方法(function)中創造出許多暫時的物件，做了許多運算後，才回傳最終需要的物件，也就是說，我們創造出的物件中，多數都是生存期比較短的，而生存期長的物件，常常就是我們需要長時間使用的物件，若我們每次都去檢查他是不是需要回收，就很浪費時間了！那我們該怎麼基於這麼想法做優化呢？
這就是CPython垃圾回收分代機制！簡單講解一下這個分代機制是怎麼做的吧！首先，CPython將GC物件列表分為三代：
1. 第0代：物件被創造時，若該物件可能產生循環引用，就加入第0代
2. 第1代：第0代的可達物件，也就是對第0代的GC物件列表做了垃圾回收後，還存活下來的物件。
3. 第2代：第1代的可達物件，也就是對第1代的GC物件列表做了垃圾回收後，還存活下來的物件。
> 註：對GC物件列表做了標記後，原先為不可達的物件，若在Python中定義了__del__()方法後，並因為執行了__del__()而轉為可達物件，當下是不會被移致下一代的
那下一個問題就是，我們什麼時候會去回收這三代的物件呢？
## 執行時機
我們先來看個示意圖，讓我們對於CPython是怎麼儲存這三代物件大概有個概念:
上圖可以看到，對於每一代GC物件列表，我們另外儲存了三個變量，分別為GC_Head head, threshold, count，head的部分我們等等會有詳細的解釋，現在我們先將這個generation[n].head視為指向GC物件列表的指標，而當generation[i].count超過generation[n].threshold之時，就會觸發**第i代**的**標記-清除垃圾回收機制**了，但generation[n].count是什麼呢？count在不同代可是有著不同的意思：
1. generation[0].count: 第0代所指向的GC物件列表數量
2. generation[1].count: 第0代垃圾回收執行次數
3. generation[2].count: 第1代垃圾回收執行次數
> [註] 當觸發了第n代的垃圾回收機制**時，實際上會回收第0~n代的GC物件列表中不可達的物件，因此最2代(最老代)也稱為完全回收，而第0代與第1代也稱為非完全回收
接著我們再來分析一下，每一代執行垃圾回收時最多需要遍歷多少物件呢？
1. 第0代：generation[0].threshold
2. 第1代：generation[0].threshold * generation[1].threshold
> 發生在每次第0代的GC物件列表做了垃圾回收後，所有物件皆存活下來，即皆為可達物件(不可回收)
3. 第2代：無上限
由於在最老代中的可達物件(不可回收)無法再被移至下一代，因此最多需要遍歷的物件數量是沒有上限的，若物件一直都無法回收，又一直產生無法回收的物件，執行一次垃圾回收就會有非常大的開銷，因此這邊做了一點優化，當等待第一次完全回收的物件數量與上次完全回收存活下來的物件數量)超過1/4時，才會執行一次最老代的垃圾回收喔！
現在知道了什麼時候會觸發各代的垃圾回收機制了，那怎麼知道實際上真的是這樣運作的呢？老樣子！用實際的CPython程式碼來證明吧！
首先，在我們創建一個物件時，以Python的角度來看，是呼叫了__new__這個函式，也就是我們說的建構函式，而這個函式實際上就是對應到CPython的tp_new函式，讓我們以list物件作為例子，list物件的tp_new函式在哪邊呢？就定義在listobject.c的PyList_Type當中：
---
```c=
PyTypeObject PyList_Type = {
...
PyType_GenericNew, /* tp_new */
...
};
```
> [CPython原始碼](https://github.com/python/cpython/blob/v3.10.0/Objects/listobject.c#L3081)
---
我們接著進去看看PyType_GenericNew做了什麼：
---
```c=
PyObject *
PyType_GenericNew(PyTypeObject *type, PyObject *args, PyObject *kwds)
{
return type->tp_alloc(type, 0);
}
```
> [CPython原始碼](https://github.com/python/cpython/blob/v3.10.0/Objects/typeobject.c#L1175)
---
看來PyType_GenericNew做的事情只是再去呼叫tp_alloc函式而已，那list物件的tp_alloc函式是什麼呢？我們同樣去PyList_Type找一找：
---
```c=
PyTypeObject PyList_Type = {
...
PyType_GenericAlloc, /* tp_alloc */
...
};
```
> [CPython原始碼](https://github.com/python/cpython/blob/v3.10.0/Objects/listobject.c#L3080)
---
原來是PyType_GenericAlloc，這裡面又在做什麼呢？
---
```c=
...
PyObject *
PyType_GenericAlloc(PyTypeObject *type, Py_ssize_t nitems)
{
...
//當物件用標記-清除演算法來幫忙回收
if (_PyType_IS_GC(type)) {
obj = _PyObject_GC_Malloc(size);
}
else {
...
}
}
...
```
> [CPython原始碼](https://github.com/python/cpython/blob/v3.10.0/Objects/typeobject.c#L1142)
---
從上述程式碼，我們可以先這樣解讀，當物件是可能需要垃圾回收機制來幫忙回收的話，會呼叫_PyObject_GC_Malloc這個方法，我們會在之後的 [如何維護GC物件列表](##如何維護GC物件列表)有更詳細的解析，現在繼續看看當物件創造時，到底做了什麼事呢？也就是_PyObject_GC_Malloc做了什麼？
---
```c=
...
PyObject *
_PyObject_GC_Malloc(size_t basicsize)
{
return _PyObject_GC_Alloc(0, basicsize);
}
...
```
> [CPython原始碼](https://github.com/python/cpython/blob/v3.10.0/Modules/gcmodule.c#L2275)
---
```c=
...
static PyObject *
_PyObject_GC_Alloc(int use_calloc, size_t basicsize)
{
...
gcstate->generations[0].count++; /* number of allocated GC objects */
if (gcstate->generations[0].count > gcstate->generations[0].threshold &&
gcstate->enabled &&
gcstate->generations[0].threshold &&
!gcstate->collecting &&
!_PyErr_Occurred(tstate))
{
gcstate->collecting = 1;
gc_collect_generations(tstate);
gcstate->collecting = 0;
}
...
}
...
```
> [CPython原始碼](https://github.com/python/cpython/blob/v3.10.0/Modules/gcmodule.c#L2236)
---
看起來找到我們要的東西了，看到了嗎？，generations[0].count增加了，且若generations[0].count超過了generations[0].threshold，就會執行gc_collect_generations(...)：
---
```c=
...
static Py_ssize_t
gc_collect_generations(PyThreadState *tstate)
{
GCState *gcstate = &tstate->interp->gc;
Py_ssize_t n = 0;
for (int i = NUM_GENERATIONS-1; i >= 0; i--) {
if (gcstate->generations[i].count > gcstate->generations[i].threshold) {
if (i == NUM_GENERATIONS - 1
&& gcstate->long_lived_pending < gcstate->long_lived_total / 4)
continue;
n = gc_collect_with_callback(tstate, i);
break;
}
}
return n;
}
...
```
> [CPython原始碼](https://github.com/python/cpython/blob/v3.10.0/Modules/gcmodule.c#L2081)
---
```c=
...
static Py_ssize_t
gc_collect_with_callback(PyThreadState *tstate, int generation)
{
...
result = gc_collect_main(tstate, generation, &collected, &uncollectable, 0);
...
}
...
```
> [CPython原始碼](https://github.com/python/cpython/blob/v3.10.0/Modules/gcmodule.c#L1408)
---
當我們攤開gc_collect_generations這個方法的程式碼後，我們看到了generation[i].count > generation[i].threshold這個我們之前提到的垃圾回收機制觸發條件。接著會以**第2代 -> 第1代 -> 第0代**這個順序來優先決定要執行哪一代的垃圾回收。
> [註] 還記得我們先前提過的最老代垃圾回收優化技巧嗎？從程式碼就可以證明最老代除了用count&threshold來判斷要不要執行，還會以等待第一次完全回收的物件數量(gcstate->long_lived_pending)與上次執行第老代垃圾回收存活下來的物件數量(gcstate->long_lived_total)比例，來決定要不要執行喔！
而gc_collect_with_callback方法中呼叫的gc_collect_main方法，就是**標記-清除垃圾回收機制**的實際運作邏輯了。
另外，我們也可以手動來觸發垃圾回收機制，也就是直接執行import gc;gc.collect()，呼叫了此方法後，會執行CPython以下的程式碼：
---
```c=
...
/* Public API to invoke gc.collect() from C */
Py_ssize_t
PyGC_Collect(void)
{
...
if (gcstate->collecting) {
...
}
else {
...
n = gc_collect_with_callback(...);
...
}
return n;
}
...
```
> [CPython原始碼](https://github.com/python/cpython/blob/v3.10.0/Modules/gcmodule.c#L2081)
---
```c=
...
static Py_ssize_t
gc_collect_with_callback(PyThreadState *tstate, int generation)
{
...
result = gc_collect_main(tstate, generation, &collected, &uncollectable, 0);
...
}
...
```
> [CPython原始碼](https://github.com/python/cpython/blob/v3.10.0/Modules/gcmodule.c#L1408)
---
從上面發現，此方法最終也會呼叫到gc_collect_main這個方法，但在我們深入去看這個方法前，我們需要先談談GC物件列表究竟是怎麼維護的，畢竟我們一直提到這個GC物件列表，代表這個GC列表對於這個演算法是至關重要的！
## 如何維護GC物件列表
首先，我們來看看物件被創造時，CPython中會呼叫的PyType_GenericAlloc這個函式吧！
---
```c=
...
PyObject *
PyType_GenericAlloc(PyTypeObject *type, Py_ssize_t nitems)
{
...
if (_PyType_IS_GC(type)) {
obj = _PyObject_GC_Malloc(size);
}
else {
...
}
...
if (_PyType_IS_GC(type)) {
_PyObject_GC_TRACK(obj);
}
return obj;
}
...
```
> [CPython原始碼](https://github.com/python/cpython/blob/v3.10.0/Objects/typeobject.c#L1142)
---
先前我們說過，當物件被創造時，一旦是可能造成循環引用的物件(例如list, dict...等)，也就是可能需要垃圾回收機制來幫忙回收的物件，就會馬上被加入GC物件列表當中，而如何判斷要不要被加進列表中，就是由_PyType_IS_GC(...)這個方法來做判斷的：
---
```c=
...
// Fast inlined version of PyType_IS_GC()
#define _PyType_IS_GC(t) _PyType_HasFeature((t), Py_TPFLAGS_HAVE_GC)
...
```
> [CPython原始碼](https://github.com/python/cpython/blob/v3.10.0/Include/internal/pycore_object.h#L169)
---
```c=
// Fast inlined version of PyType_HasFeature()
static inline int
_PyType_HasFeature(PyTypeObject *type, unsigned long feature) {
return ((type->tp_flags & feature) != 0);
}
```
> [CPython原始碼](https://github.com/python/cpython/blob/v3.10.0/Include/internal/pycore_object.h#L26)
---
判斷方法其實非常簡單，我們看到_PyType_IS_GC就只是去判斷這個物件有沒有開gc collect這個功能，而有沒有開gc這個功能，實際上就是直接定義在tp_flags中，看到tp_開頭，馬上我們就到PyList_Type去查一查：
---
```c=
PyTypeObject PyList_Type = {
...
Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
Py_TPFLAGS_BASETYPE | Py_TPFLAGS_LIST_SUBCLASS |
_Py_TPFLAGS_MATCH_SELF | Py_TPFLAGS_SEQUENCE, /* tp_flags */
...
};
```
> [CPython原始碼](https://github.com/python/cpython/blob/v3.10.0/Objects/listobject.c#L3061)
---
果不其然！我們找到了tp_flags定義的地方，也在這邊我們找到了Py_TPFLAGS_HAVE_GC這個flag的確有被打開，因此物件到底需不需要做gc collect就是在這邊定義的啦！
現在我們終於可以繼續看看當物件創造時，到底做了什麼事呢？也就是_PyObject_GC_Malloc做了什麼？
---
```c=
...
PyObject *
_PyObject_GC_Malloc(size_t basicsize)
{
return _PyObject_GC_Alloc(0, basicsize);
}
...
```
> [CPython原始碼](https://github.com/python/cpython/blob/v3.10.0/Modules/gcmodule.c#L2275)
---
```c=
...
static PyObject *
_PyObject_GC_Alloc(int use_calloc, size_t basicsize)
{
...
size_t size = sizeof(PyGC_Head) + basicsize;
PyGC_Head *g;
if (use_calloc) {
g = (PyGC_Head *)PyObject_Calloc(1, size);
}
else {
g = (PyGC_Head *)PyObject_Malloc(size);
}
if (g == NULL) {
return _PyErr_NoMemory(tstate);
}
assert(((uintptr_t)g & 3) == 0); // g must be aligned 4bytes boundary
g->_gc_next = 0;
g->_gc_prev = 0;
...
PyObject *op = FROM_GC(g);
return op;
}
...
```
> [CPython原始碼](https://github.com/python/cpython/blob/v3.10.0/Modules/gcmodule.c#L2236)
---
這種可能需要垃圾回收機制幫忙回收的物件，CPython會在此物件上，多加一個叫做PyGC_Head的資訊，因此我們會看到CPyhton在要記憶體時，不只包含物件本身需要的記憶體大小(basicsize)，還包含sizeof(PyGC_Head)喔！
那PyGC_Head裡面有什麼呢？它包含了兩個指標，分別是prev以及next，這兩個欄位又是拿來做什麼的呢？其實就是來維護我們一直提到的GC物件列表，從這裡我們也可以猜到這個GC物件列表應該就是一個linked list，CPython就是透過prev以及next來維護這個列表的：
---
```c=
...
/* GC information is stored BEFORE the object structure. */
typedef struct {
// Pointer to next object in the list.
// 0 means the object is not tracked
uintptr_t _gc_next;
// Pointer to previous object in the list.
// Lowest two bits are used for flags documented later.
uintptr_t _gc_prev;
} PyGC_Head;
...
```
> [CPython原始碼](https://github.com/python/cpython/blob/v3.10.0/Include/internal/pycore_gc.h#L12)
---
而當CPython為物件要到記憶體空間時，也就是PyGC_Head \*g，我們可以透過改變指標位置(FROM_GC)，來獲得我們所創建的物件本身(PyObject)，因此在_PyObject_GC_Alloc最後一行，就可以把物件本身(PyObject)傳回去啦！
---
```c=
...
/* Get the object given the GC head */
#define FROM_GC(g) ((PyObject *)(((PyGC_Head *)g)+1))
...
```
> [CPython原始碼](https://github.com/python/cpython/blob/v3.10.0/Modules/gcmodule.c#L75)
---
同理，未來我們也可以再透過改變指標位置(AS_GC)，來獲得PyGC_Head的資訊:
---
```c=
...
#define AS_GC(o) ((PyGC_Head *)(o)-1)
...
```
> [CPython原始碼](https://github.com/python/cpython/blob/v3.10.0/Modules/gcmodule.c#L72)
---
現在再讓我們回憶一下先前提過物件要被創造時，會呼叫PyType_GenericAlloc：
---
```c=
...
PyObject *
PyType_GenericAlloc(PyTypeObject *type, Py_ssize_t nitems)
{
...
if (_PyType_IS_GC(type)) {
obj = _PyObject_GC_Malloc(size);
}
else {
...
}
...
if (_PyType_IS_GC(type)) {
_PyObject_GC_TRACK(obj);
}
return obj;
}
...
```
> [CPython原始碼](https://github.com/python/cpython/blob/v3.10.0/Objects/typeobject.c#L1142)
---
我們剛剛已經看完了_PyObject_GC_Malloc是怎麼做的，也有了GC_Head的概念，現在我們就來看看物件是怎麼被加進GC物件列表中的，也就是_PyObject_GC_TRACK到底做了什麼呢？
---
```c=
...
static inline void _PyObject_GC_TRACK(
// The preprocessor removes _PyObject_ASSERT_FROM() calls if NDEBUG is defined
#ifndef NDEBUG
const char *filename, int lineno,
#endif
PyObject *op)
{
_PyObject_ASSERT_FROM(op, !_PyObject_GC_IS_TRACKED(op),
"object already tracked by the garbage collector",
filename, lineno, __func__);
PyGC_Head *gc = _Py_AS_GC(op);
_PyObject_ASSERT_FROM(op,
(gc->_gc_prev & _PyGC_PREV_MASK_COLLECTING) == 0,
"object is in generation which is garbage collected",
filename, lineno, __func__);
PyInterpreterState *interp = _PyInterpreterState_GET();
PyGC_Head *generation0 = interp->gc.generation0;
PyGC_Head *last = (PyGC_Head*)(generation0->_gc_prev);
_PyGCHead_SET_NEXT(last, gc);
_PyGCHead_SET_PREV(gc, last);
_PyGCHead_SET_NEXT(gc, generation0);
generation0->_gc_prev = (uintptr_t)gc;
}
...
```
> [CPython原始碼](https://github.com/python/cpython/blob/v3.10.0/Include/internal/pycore_object.h#L71)
---
PyGC_Head \*generation0就是第0代GC物件列表的起始點，其prev會指向最後一個物件，next則指向第一個物件，而在一開始，prev以及next兩個指標就都是指向generation0自己囉！(至於為什麼叫做generation是什麼意思我們到了分代機制會再說明)
而初始程式碼如下所示：
---
```c=
...
#define GEN_HEAD(gcstate, n) (&(gcstate)->generations[n].head)
...
void
_PyGC_InitState(GCState *gcstate)
{
gcstate->enabled = 1; /* automatic collection enabled? */
#define _GEN_HEAD(n) GEN_HEAD(gcstate, n)
struct gc_generation generations[NUM_GENERATIONS] = {
/* PyGC_Head, threshold, count */
{{(uintptr_t)_GEN_HEAD(0), (uintptr_t)_GEN_HEAD(0)}, 700, 0},
{{(uintptr_t)_GEN_HEAD(1), (uintptr_t)_GEN_HEAD(1)}, 10, 0},
{{(uintptr_t)_GEN_HEAD(2), (uintptr_t)_GEN_HEAD(2)}, 10, 0},
};
for (int i = 0; i < NUM_GENERATIONS; i++) {
gcstate->generations[i] = generations[i];
};
gcstate->generation0 = GEN_HEAD(gcstate, 0);
struct gc_generation permanent_generation = {
{(uintptr_t)&gcstate->permanent_generation.head,
(uintptr_t)&gcstate->permanent_generation.head}, 0, 0
};
gcstate->permanent_generation = permanent_generation;
}
...
```
> [CPython原始碼](https://github.com/python/cpython/blob/v3.10.0/Modules/gcmodule.c#L128)
---
而當一個新的物件要被加進GC物件列表後，會有以下四個步驟
1. _PyGCHead_SET_NEXT(last, gc);
2. _PyGCHead_SET_PREV(gc, last);
3. _PyGCHead_SET_NEXT(gc, generation0);
4. generation0->_gc_prev = (uintptr_t)gc;
以圖來看就會向下列這個樣子：
若是再加一個新物件就會再變成以下這個樣子
而相反的，幫我們決定要銷毀這個物件時，銷毀前也需要把物件從這個GC物件列表移除，以list物件為例子，我們可以在list物件的list_dealloc函式中CPython透過PyObject_GC_UnTrack這個函式來移除GC物件列表中的物件：
---
```c=
...
static void
list_dealloc(PyListObject *op)
{
Py_ssize_t i;
PyObject_GC_UnTrack(op);
...
}
...
```
> [CPython原始碼](https://github.com/python/cpython/blob/v3.10.0/Objects/listobject.c#L331)
---
```c=
...
void
PyObject_GC_UnTrack(void *op_raw)
{
PyObject *op = _PyObject_CAST(op_raw);
/* Obscure: the Py_TRASHCAN mechanism requires that we be able to
* call PyObject_GC_UnTrack twice on an object.
*/
if (_PyObject_GC_IS_TRACKED(op)) {
_PyObject_GC_UNTRACK(op);
}
}
...
```
> [CPython原始碼](https://github.com/python/cpython/blob/v3.10.0/Modules/gcmodule.c#L2218)
---
```c=
...
static inline void _PyObject_GC_UNTRACK(
// The preprocessor removes _PyObject_ASSERT_FROM() calls if NDEBUG is defined
#ifndef NDEBUG
const char *filename, int lineno,
#endif
PyObject *op)
{
_PyObject_ASSERT_FROM(op, _PyObject_GC_IS_TRACKED(op),
"object not tracked by the garbage collector",
filename, lineno, __func__);
PyGC_Head *gc = _Py_AS_GC(op);
PyGC_Head *prev = _PyGCHead_PREV(gc);
PyGC_Head *next = _PyGCHead_NEXT(gc);
_PyGCHead_SET_NEXT(prev, next);
_PyGCHead_SET_PREV(next, prev);
gc->_gc_next = 0;
gc->_gc_prev &= _PyGC_PREV_MASK_FINALIZED;
}...
```
> [CPython原始碼](https://github.com/python/cpython/blob/v3.10.0/Include/internal/pycore_object.h#L107)
---
從GC物件列表移除物件的方式由上述程式碼來看，主要就是這兩步驟：
1. _PyGCHead_SET_NEXT(prev, next);
2. _PyGCHead_SET_PREV(next, prev);
以圖表示就是下列這個樣子：
說到這，我們就知道CPython是怎麼維護GC物件列表的了，接下來，我們就來看看CPython是怎麼透過這個GC物件列表來解決循環引用的問題囉！
## 實際運作流程
從[執行時機](##執行時機)的分析中，我們已經知道CPython在執行第i代的**標記-清除垃圾回收機制**的進入點在於gc_collect_main這個函式中，而當中主要可以分為以下9個步驟：
1. 更新第n代標記-清除垃圾回收機制的執行次數
2. 重置generation[0].count～generation[n].count值
3. 合併第0代～第n代的GC物件列表
4. 在合併的物件列表中，標記可回收(不可達)與不可回收(可達)的物件
5. 更新**等待第一次完全回收的物件數量**及**最老代執行垃圾回收後存活下來的物件數量**並將不可回收之物件移至老一代的物件列表中
6. 處理指向可回收物件的弱引用
7. 若可回收物件有定義tp_finalize函式(也就是python中的def \_\_del\_\_)，則執行tp_finalize函式
8. 再次標記真正可回收及不可回收的物件，並將不可回收的物件移至老一代GC列表中
9. 刪除可回收的物件
而這9個步驟可以對應到以下的程式碼：
---
```c=
...
/* This is the main function. Read this to understand how the
* collection process works. */
static Py_ssize_t
gc_collect_main(PyThreadState *tstate, int generation,
Py_ssize_t *n_collected, Py_ssize_t *n_uncollectable,
int nofail)
{
int i;
PyGC_Head *young; /* the generation we are examining */
PyGC_Head *old; /* next older generation */
PyGC_Head unreachable; /* non-problematic unreachable trash */
PyGC_Head *gc;
...
/* 1. 更新第n代標記-清除垃圾回收機制的執行次數 */
if (generation+1 < NUM_GENERATIONS)
gcstate->generations[generation+1].count += 1;
/* 2. 重置generation[0].count～generation[n].count值 */
for (i = 0; i <= generation; i++)
gcstate->generations[i].count = 0;
/* 3. 合併第0代～第n代的GC物件列表 */
for (i = 0; i < generation; i++) {
gc_list_merge(GEN_HEAD(gcstate, i), GEN_HEAD(gcstate, generation));
}
...
/* 4. 在合併的物件列表中，標記可回收(不可達)與不可回收(可達)的物件 */
deduce_unreachable(young, &unreachable);
...
/* 5. 更新**等待第一次完全回收的物件數量**及**最老代執行垃圾回收後存活下來的物件數量**並將不可回收之物件移至老一代的物件列表中 */
if (young != old) {
if (generation == NUM_GENERATIONS - 2) {
gcstate->long_lived_pending += gc_list_size(young);
}
gc_list_merge(young, old);
}
else {
/* We only un-track dicts in full collections, to avoid quadratic
dict build-up. See issue #14775. */
untrack_dicts(young);
gcstate->long_lived_pending = 0;
gcstate->long_lived_total = gc_list_size(young);
}
...
/* 6. 處理指向可回收物件的弱引用 */
m += handle_weakrefs(&unreachable, old);
...
/* 7. 若可回收物件有定義tp_finalize函式(也就是python中的def __del__)，則執行tp_finalize函式 */
finalize_garbage(tstate, &unreachable);
/* 8. 再次標記真正可回收及不可回收的物件，並將不可回收的物件移至老一代GC列表中 */
PyGC_Head final_unreachable;
handle_resurrected_objects(&unreachable, &final_unreachable, old);
...
/* 9. 刪除可回收的物件 */
delete_garbage(tstate, gcstate, &final_unreachable, old);
...
}...
```
> [CPython原始碼](https://github.com/python/cpython/blob/3.10/Modules/gcmodule.c#L1183)
---
### 1. 更新第n代垃圾回收的執行次數
首先，當第n代垃圾回收機制的觸發時，gc_collect_main會先去更新第n代垃圾回收的執行次數，也就是[執行時機](##執行時機)中所提到的generation[n+1].count：
```c=
...
/* This is the main function. Read this to understand how the
* collection process works. */
static Py_ssize_t
gc_collect_main(PyThreadState *tstate, int generation,
Py_ssize_t *n_collected, Py_ssize_t *n_uncollectable,
int nofail)
{
int i;
PyGC_Head *young; /* the generation we are examining */
PyGC_Head *old; /* next older generation */
PyGC_Head unreachable; /* non-problematic unreachable trash */
PyGC_Head *gc;
...
/* 1. 更新第n代標記-清除垃圾回收機制的執行次數 */
if (generation+1 < NUM_GENERATIONS)
gcstate->generations[generation+1].count += 1;
...
}...
```
> [CPython原始碼](https://github.com/python/cpython/blob/3.10/Modules/gcmodule.c#L1221)
---
### 2. 重置generation[0].count～generation[n].count值
由於觸發了第n代的垃圾回收機制時，實際上會遍歷第0~n代的GC物件列表中並一起進行垃圾回收，因此第0代～第n代的count值會一起重置：
```c=
...
/* This is the main function. Read this to understand how the
* collection process works. */
static Py_ssize_t
gc_collect_main(PyThreadState *tstate, int generation,
Py_ssize_t *n_collected, Py_ssize_t *n_uncollectable,
int nofail)
{
int i;
PyGC_Head *young; /* the generation we are examining */
PyGC_Head *old; /* next older generation */
PyGC_Head unreachable; /* non-problematic unreachable trash */
PyGC_Head *gc;
...
/* 2. 重置generation[0].count～generation[n].count值 */
for (i = 0; i <= generation; i++)
gcstate->generations[i].count = 0;
...
}...
```
> [CPython原始碼](https://github.com/python/cpython/blob/3.10/Modules/gcmodule.c#L1223)
---
### 3. 合併第0代～第n代的GC物件列表
由於要遍歷第0~n代的GC物件列表中並一起進行垃圾回收，因此會將第0代～第(n-1)代的物件列表串接至第n代的GC物件列表後，而第0代～第(n-1)代的GC物件列表將會被清空。
以示意圖來說，若目前第0代～第2代GC物件列表如下圖所示：
若觸發了第2代垃圾回收機制，則合併了第0代～第1代GC物件列表至第2代的GC物件列表後，會轉為下圖所示：
若示意圖了解了，程式碼的部分應該就很容易懂了：
```c=
...
/* This is the main function. Read this to understand how the
* collection process works. */
static Py_ssize_t
gc_collect_main(PyThreadState *tstate, int generation,
Py_ssize_t *n_collected, Py_ssize_t *n_uncollectable,
int nofail)
{
int i;
PyGC_Head *young; /* the generation we are examining */
PyGC_Head *old; /* next older generation */
PyGC_Head unreachable; /* non-problematic unreachable trash */
PyGC_Head *gc;
...
/* 3. 合併第0代～第n代的GC物件列表 */
for (i = 0; i < generation; i++) {
gc_list_merge(GEN_HEAD(gcstate, i), GEN_HEAD(gcstate, generation));
}
...
}...
```
> [CPython原始碼](https://github.com/python/cpython/blob/3.10/Modules/gcmodule.c#L1227)
```c=
...
/* This is the main function. Read this to understand how the
* collection process works. */
/* append list `from` onto list `to`; `from` becomes an empty list */
static void
gc_list_merge(PyGC_Head *from, PyGC_Head *to)
{
assert(from != to);
if (!gc_list_is_empty(from)) {
PyGC_Head *to_tail = GC_PREV(to);
PyGC_Head *from_head = GC_NEXT(from);
PyGC_Head *from_tail = GC_PREV(from);
assert(from_head != from);
assert(from_tail != from);
_PyGCHead_SET_NEXT(to_tail, from_head);
_PyGCHead_SET_PREV(from_head, to_tail);
_PyGCHead_SET_NEXT(from_tail, to);
_PyGCHead_SET_PREV(to, from_tail);
}
gc_list_init(from);
}
...
```
> [CPython原始碼](https://github.com/python/cpython/blob/3.10/Modules/gcmodule.c#L302)
```c=
...
static inline void
gc_list_init(PyGC_Head *list)
{
// List header must not have flags.
// We can assign pointer by simple cast.
list->_gc_prev = (uintptr_t)list;
list->_gc_next = (uintptr_t)list;
}
...
```
> [CPython原始碼](https://github.com/python/cpython/blob/3.10/Modules/gcmodule.c#L236)
---
### 4. 標記可回收(不可達)與不可回收(可達)的物件
我們前面說了這麼多可回收與不可回收的物件，到底我們要怎麼知道哪些物件是可回收，哪些物件又是不可回收的呢？這一步就是要帶大家來看看CPython是怎麼判斷的啦！
```c=
...
/* This is the main function. Read this to understand how the
* collection process works. */
static Py_ssize_t
gc_collect_main(PyThreadState *tstate, int generation,
Py_ssize_t *n_collected, Py_ssize_t *n_uncollectable,
int nofail)
{
int i;
PyGC_Head *young; /* the generation we are examining */
PyGC_Head *old; /* next older generation */
PyGC_Head unreachable; /* non-problematic unreachable trash */
PyGC_Head *gc;
...
/* handy references */
young = GEN_HEAD(gcstate, generation);
if (generation < NUM_GENERATIONS-1)
old = GEN_HEAD(gcstate, generation+1);
else
old = young;
validate_list(old, collecting_clear_unreachable_clear);
/* 4. 在合併的物件列表中，標記可回收(不可達)與不可回收(可達)的物件 */
deduce_unreachable(young, &unreachable);
...
}...
```
> [CPython原始碼](https://github.com/python/cpython/blob/3.10/Modules/gcmodule.c#L1239)
上述程式碼中，young就是我們這次要遍歷的GC物件列表，也就是第n代的物件列表，我們將要透過deduce_unreachable這個函式將可回收的物件放至unreachable列表中。
而這個函式需要做到以下兩件事情：
1. 遍歷GC列表中的物件(young)，若物件有包含除GC列表中物件的引用，則視為不可回收物件(可達物件)
2. 將不可回收物件有引用之物件，也標為不可回收物件
看起來最重要的問題是，我們要怎麼找出那些包含外部引用的物件(物件的引用次數，包含除GC列表中物件的引用)呢？我們可以透過物件的引用次數來判斷，當遍歷至GC物件列表中的物件A時，我們將接著遍歷A所引用的物件1\~n，並將物件1\~n的引用次數分別減1，最後引用次數大於0的物件，即代表此為包含外部引用之物件。
接著讓我們來看看原始碼吧！
```c=
...
static inline void
deduce_unreachable(PyGC_Head *base, PyGC_Head *unreachable) {
...
// 1. 初始化物件引用次數
update_refs(base); // gc_prev is used for gc_refs
// 2. 將物件引用次數扣除所有內部引用次數
subtract_refs(base);
...
//3. 將物件引用次數不為0的物件視為不可回收物件，而不可回收物件有引用之物件，也視為不可回收物件，並將所有可回收物件移至unreachable列表中
move_unreachable(base, unreachable); // gc_prev is pointer again
...
}
...
```
> [CPython原始碼](https://github.com/python/cpython/blob/3.10/Modules/gcmodule.c#L1097)
原始碼中又可以分為三大步驟：
1. 初始化物件引用次數
> [註] 為什麼我們需要找另外一個地方紀錄物件引用次數呢？物件引用次數不是已經記錄在[引用計數機制](https://hackmd.io/@8thEdition/cpython_garbage_collection_reference_counting)所提到的PyObject中的ob_refcnt了嗎？我們先前有提到，我們會對物件的引用次數作減法，而這只是為了判斷物件是否有包含外部引用而已，可不能把真正的物件的引用次數改掉啦！
2. 將物件引用次數扣除所有內部引用次數(此內部引用次數為GC物件列表之物件造成的引用次數)
3. 將物件引用次數不為0的物件視為不可回收物件，而不可回收物件有引用之物件，也視為不可回收物件，並將所有可回收物件移至unreachable列表中
#### 4.1 初始化物件引用次數
我們先看到update_refs這個函式，其主要做的事情，是要另外找個地方紀錄各物件的引用次數：
```c=
...
static void
update_refs(PyGC_Head *containers)
{
PyGC_Head *gc = GC_NEXT(containers);
for (; gc != containers; gc = GC_NEXT(gc)) {
gc_reset_refs(gc, Py_REFCNT(FROM_GC(gc)));
...
}
}
...
```
> [CPython原始碼](https://github.com/python/cpython/blob/3.10/Modules/gcmodule.c#L423)
```c=
...
static inline void
gc_reset_refs(PyGC_Head *g, Py_ssize_t refs)
{
g->_gc_prev = (g->_gc_prev & _PyGC_PREV_MASK_FINALIZED)
| PREV_MASK_COLLECTING
| ((uintptr_t)(refs) << _PyGC_PREV_SHIFT);
}
...
```
> [CPython原始碼](https://github.com/python/cpython/blob/3.10/Modules/gcmodule.c#L102)
我們可以從上面的程式碼中，發現PyGC_Head.\_gc_prev除了最後兩個位元，皆被用來儲存了GC物件的引用次數，而最後兩個位元則被拿來存放以下兩個flags：
1. \_PyGC_PREV_MASK_FINALIZED：用來表示此物件是法已經執行過tp_finalize，也就是Python中的__del__函式。
> 原本判定為可回收的物件，有可能在執行finalize_garbage([實際運作流程:步驟7](#實際運作流程))這個函式之後，復活為不可回收的物件，並被丟進老一代中，為了避免再次執行tp_finalize，因此需要對物件打上這個flag，讓我們可以在finalize_garbage這個函式中，判斷要不要呼叫tp_finalize喔
2. PREV_MASK_COLLECTING：用來表示此物件為這次分代垃圾回收所需要處理的物件
> PREV_MASK_COLLECTING是用來做什麼的，我們會在解析subtract_refs及move_unreachable這兩個函式的時候說明
但這裡又有兩個問題：
1. PyGC_Head.\_gc_prev不是用來指向上一個物件的指標嗎？為什麼後面兩個位元可以用來儲存flag呢？其實是因為在32位元電腦架構中，物件的記憶體位址是4的倍數(4-byte aligned)，因此最後兩個位元永遠都是00，而為了省記憶體，CPython就直接利用最後兩個位元來紀錄\_PyGC_PREV_MASK_FINALIZED及PREV_MASK_COLLECTING這兩個flag囉！
> 若是64位元的電腦架構，物件記體體位置則皆是8的倍數，最後三個位元就都會是000了
因此當我們透過GC_PREV這個函式拿取上一個物件時，實際上是這樣做的：
```c=
...
#define GC_PREV _PyGCHead_PREV
...
```
> [CPython原始碼](https://github.com/python/cpython/blob/3.10/Modules/gcmodule.c#L48)
```c=
...
#define _PyGC_PREV_SHIFT (2)
#define _PyGC_PREV_MASK (((uintptr_t) -1) << _PyGC_PREV_SHIFT)
...
#define _PyGCHead_PREV(g) ((PyGC_Head*)((g)->_gc_prev & _PyGC_PREV_MASK))
...
```
> [CPython原始碼](https://github.com/python/cpython/blob/3.10/Include/internal/pycore_gc.h#L40)
2. PyGC_Head.\_gc_prev中除了最後兩個位元，其他位元也被拿來紀錄物件引用次數，這樣不就找不到前一個物件了嗎？這邊就不用擔心囉，因為在之後要說明的move_unreachable中，會再把PyGC_Head.\_gc_prev重置為指向上一個物件的指標。
#### 4.2 將物件引用次數扣除所有內部引用次數
接著我們再來看看subtract_refs這個函式：
```c=
...
static void
subtract_refs(PyGC_Head *containers)
{
traverseproc traverse;
PyGC_Head *gc = GC_NEXT(containers);
for (; gc != containers; gc = GC_NEXT(gc)) {
PyObject *op = FROM_GC(gc);
traverse = Py_TYPE(op)->tp_traverse;
(void) traverse(FROM_GC(gc),
(visitproc)visit_decref,
op);
}
}
...
```
> [CPython原始碼](https://github.com/python/cpython/blob/3.10/Modules/gcmodule.c#L474)
```c=
...
static int
visit_decref(PyObject *op, void *parent)
{
...
if (_PyObject_IS_GC(op)) {
PyGC_Head *gc = AS_GC(op);
...
if (gc_is_collecting(gc)) {
gc_decref(gc);
}
}
return 0;
}
...
```
> [CPython原始碼](https://github.com/python/cpython/blob/3.10/Modules/gcmodule.c#L452)
從程式碼中，我們可以看到在subtract_refs函式中，會去遍歷GC物件列表的物件，並透過物件定義的的tp_traverse函式，再去遍歷該物件所引用的物件，接著再呼叫visit_decref這個函式將該物件的引用次數減去1。
以示意圖來看的話，若現在觸發了第0代垃圾回收，而第0代的GC物件列表如下：
當遍歷到list A這個物件時，會透過A.tp_traverse去拿到list A所引用的list A以及list B兩個物件，並將這兩個物件的引用次數減去1，則GC物件列表轉為：
接著會遍歷到list B這個物件，並透過B.tp_traverse拿到list B這個物件，再將其引用次數減去1：
如果我們接著遍歷list C這個物件會發生什麼事呢？首先透過C.tp_traverse會拿到list C，而我們將其引用次數減去1，示意圖如下：
但list C所引用特物件D卻沒有出現在GC物件列表中，這是為什麼呢？這是由於有下面兩個可能：
1. 物件D不需要垃圾回收機制幫忙回收(例如數字，字串等等)
2. 物件D在其他代的GC物件列表中
若是第一種情況的話，就會因為visit_decref這個函式中的"if (\_PyObject_IS_GC(op))"這個判斷式跳過；若是第二種情況，則就會因為"if (gc_is_collecting(gc))"這個判斷式跳過喔！看看gc_is_collecting的原始碼吧！
```c=
...
static inline int
gc_is_collecting(PyGC_Head *g)
{
return (g->_gc_prev & PREV_MASK_COLLECTING) != 0;
}
...
```
> [CPython原始碼](https://github.com/python/cpython/blob/3.10/Modules/gcmodule.c#L452)
還記得在我們透過PyGC_Head.\_gc_prev來紀錄的 PREV_MASK_COLLECTING這個flag嗎？這就是它其中一個用途喔！
最後當我們遍歷完所有GC物件列表的物件後，引用次數大於0的物件，就代表是有外部引用的囉！也就是在一開始就被視為不可回收(可達)物件。
#### 4.3 將物件引用次數不為0的物件視為不可回收物件，而不可回收物件有引用之物件，也視為不可回收物件，並將所有可回收物件移至unreachable列表中
而deduce_unreachable函式的最後一步，將透過move_unreachable這個函式，將可回收物件，以及其引用的物件皆移至unreachable的列表中，而原先的GC物件列表就可以被視為不可回收的物件列表了：
```c=
...
static void
move_unreachable(PyGC_Head *young, PyGC_Head *unreachable)
{
PyGC_Head *prev = young;
PyGC_Head *gc = GC_NEXT(young);
while (gc != young) {
if (gc_get_refs(gc)) {
traverseproc traverse = Py_TYPE(op)->tp_traverse;
(void) traverse(op,
(visitproc)visit_reachable,
(void *)young);
_PyGCHead_SET_PREV(gc, prev);
gc_clear_collecting(gc);
prev = gc;
}
else {
prev->_gc_next = gc->_gc_next;
PyGC_Head *last = GC_PREV(unreachable);
last->_gc_next = (NEXT_MASK_UNREACHABLE | (uintptr_t)gc);
_PyGCHead_SET_PREV(gc, last);
gc->_gc_next = (NEXT_MASK_UNREACHABLE | (uintptr_t)unreachable);
unreachable->_gc_prev = (uintptr_t)gc;
}
gc = (PyGC_Head*)prev->_gc_next;
}
young->_gc_prev = (uintptr_t)prev;
unreachable->_gc_next &= ~NEXT_MASK_UNREACHABLE;
}
...
```
> [CPython原始碼](https://github.com/python/cpython/blob/3.10/Modules/gcmodule.c#L562)
```c=
...
static int
visit_reachable(PyObject *op, PyGC_Head *reachable)
{
if (!_PyObject_IS_GC(op)) {
return 0;
}
PyGC_Head *gc = AS_GC(op);
const Py_ssize_t gc_refs = gc_get_refs(gc);
if (! gc_is_collecting(gc)) {
return 0;
}
if (gc->_gc_next & NEXT_MASK_UNREACHABLE) {
PyGC_Head *prev = GC_PREV(gc);
PyGC_Head *next = (PyGC_Head*)(gc->_gc_next & ~NEXT_MASK_UNREACHABLE);
...
prev->_gc_next = gc->_gc_next; // copy NEXT_MASK_UNREACHABLE
_PyGCHead_SET_PREV(next, prev);
gc_list_append(gc, reachable);
gc_set_refs(gc, 1);
}
else if (gc_refs == 0) {
gc_set_refs(gc, 1);
}
else {
...
}
return 0;
}
...
```
> [CPython原始碼](https://github.com/python/cpython/blob/3.10/Modules/gcmodule.c#L490)
由於這邊判斷式比較多，我們就搭配示意圖來講解流程吧！另外建議開另一分頁搭配著程式碼看喔！
假設第0代的垃圾回收機制被觸發了，而第0代的GC物件列表及unreachable列表如下：
一開始，move_unreachable函式中，會先遍歷GC物件列表，而一開始拿到了list A，而在經過subtract_refs這個函式過後，list A的引用次數為0，表示list A並沒有外部引用，因此會進入到"if (gc_get_refs(gc))"的else陳述式中，將list A"暫時"移至unreachable的列表中，並透過list A的PyGC_Head.\_gc_next最後一位元NEXT_MASK_UNREACHABLE，表示list A已在unreachable的列表中。
> 為什麼是"暫時"移至unreachable的列表中呢？是因為之後有可能會有不可回收的物件引用list A，這時就需要將list A從unreachable移回GC物件列表囉！
接著，我們繼續遍歷GC物件列表，拿到了list B，而list B的引用次數大於0(代表有外部引用，因此list B是不可以回收的！)，因此在move_unreachable函式中，則進入到"if (gc_get_refs(gc))"的陳述式中，接著，會透過list B所定義的tp_traverse函式，遍歷list B所引用的物件，將所引用的物件，也標記為不可回收物件！但怎麼標記呢？很簡單！我們前面提過判斷可不可以回收的物件就是看引用次數是不是大於0，而實際上是多少並不重要，因此標記方法就是將引用次數直接標記成1就可以啦！
現在我們來遍歷list B所引用的物件，一開始我們遍歷到了list A，我們將透過visit_reachable這個函式將list A移回GC物件列表中。
```c=
...
static int
visit_reachable(PyObject *op, PyGC_Head *reachable)
{
...
PyGC_Head *gc = AS_GC(op);
const Py_ssize_t gc_refs = gc_get_refs(gc);
...
if (gc->_gc_next & NEXT_MASK_UNREACHABLE) {
PyGC_Head *prev = GC_PREV(gc);
PyGC_Head *next = (PyGC_Head*)(gc->_gc_next & ~NEXT_MASK_UNREACHABLE);
...
prev->_gc_next = gc->_gc_next; // copy NEXT_MASK_UNREACHABLE
_PyGCHead_SET_PREV(next, prev);
gc_list_append(gc, reachable);
gc_set_refs(gc, 1);
}
else if (gc_refs == 0) {
...
}
else {
...
}
return 0;
}
...
```
> [CPython原始碼](https://github.com/python/cpython/blob/3.10/Modules/gcmodule.c#L490)
透過list A的PyGC_Head.\_gc_next的最後一位元，我們得知NEXT_MASK_UNREACHABLE為1，表示list A在unreachable列表中，因此需要：
1. 將list A從unreachable列表中移除
2. 透過gc_list_append(gc, reachable)將list A重新加入GC物件列表中
3. 透過gc_set_refs(gc, 1)將list A的引用次數設置為1，以標記list A是不可回收之物件
做完了以上3步之後，物件列表及unreachable列表如下：
遍歷完list B所引用的list A後，我們繼續遍歷list B所引用的list B，由於list B的引用次數本來就大於0，因此不會有什麼特別的改變。
接著我們遍歷到的list B所引用的list C，由於list C的引用次數為0，表示沒有任何外部引用，然後list B這個不可回收物件引用了list C，因此我們需要將list C也標為不可回收物件。
```c=
...
static int
visit_reachable(PyObject *op, PyGC_Head *reachable)
{
...
PyGC_Head *gc = AS_GC(op);
const Py_ssize_t gc_refs = gc_get_refs(gc);
...
if (gc->_gc_next & NEXT_MASK_UNREACHABLE) {
...
}
else if (gc_refs == 0) {
gc_set_refs(gc, 1);
}
else {
...
}
return 0;
}
...
```
> [CPython原始碼](https://github.com/python/cpython/blob/3.10/Modules/gcmodule.c#L490)
這邊就很簡單啦！由於list C的引用次數為0，因此進入了上述的"else if (gc_refs == 0)"陳述式中，接著直接利用gc_set_refs(gc, 1)將list C的引用次數設定為1就可以啦！
現在我們遍歷完GC物件列表的list B了，值得注意的是，當move_unreachable在遍歷到物件時，若發現物件為不可回收物件時，並執行完tp_traverse之後，就會將物件的PyGC_Head.\_gc_prev透過_PyGCHead_SET_PREV(gc, prev);還原為指向上一個物件的指標喔！
```c=
...
static void
move_unreachable(PyGC_Head *young, PyGC_Head *unreachable)
{
PyGC_Head *prev = young;
PyGC_Head *gc = GC_NEXT(young);
while (gc != young) {
if (gc_get_refs(gc)) {
...
_PyGCHead_SET_PREV(gc, prev);
...
prev = gc;
}
else {
...
}
gc = (PyGC_Head*)prev->_gc_next;
}
...
}
...
```
> [CPython原始碼](https://github.com/python/cpython/blob/3.10/Modules/gcmodule.c#L562)
現在我們已經處理完GC物件列表的list B了，接著我們繼續遍歷GC物件列表，並拿到了list C，由於list C的引用次數已經由之前的步驟更新大於0的值，且list C只引用了list C自己而已，經由tp_traverse遍歷過所引用的物件後，除了list C的PyGC_Head.\_gc_prev還原為指向上一個物件的指標，並沒有其他的改變：
接著我們繼續往下遍歷到list D，與先前遍歷到list A是相同的情況，list D會被移至unreachable的列表中：
而繼續遍歷下一個物件，會發現我們又遍歷到了list A，這是由於list A一開始暫時被視為可回收物件，也因此沒有將list A所引用的物件標記為不可回收物件，而後由於不可回收物件list B有引用list A，使得list A被移回GC物件列表中，我們需要再次遍歷list A所引用的物件，並將所引用的list D標記為不可回收物件，GC物件列表會轉為下列狀態：
我們最後遍歷剛被加回GC物件列表的list D，結束了整個move_unreachable的函式，最終的GC物件列表如下：
以上就是move_unreachable函式的流程啦！也就是標記可回收物件與不可回收物件的步驟！
---
### 5. 更新**等待第一次完全回收的物件數量**及**最老代執行垃圾回收後存活下來的物件數量**並將不可回收之物件移至老一代的物件列表
經由上一步，我們將不可回收的物件留在了GC物件列表(PyGC_Head \*young)中，而可回收物件皆放到了unreachable列表中，現在我們就可以把不可回收的物件移到下一代(PyGC_Head \*old)啦！
另外還記得我們在[執行時機](##執行時機)中，有提到最老代的觸發時機的優化，當等待第一次完全回收的物件數量(gcstate->long_lived_pending)與上次完全回收存活下來的物件數量(gcstate->long_lived_total)超過1/4時，才會執行一次最老代的垃圾回收，在這一步驟中，也會去設定long_lived_pending與long_lived_total喔！
```c=
...
static Py_ssize_t
gc_collect_main(PyThreadState *tstate, int generation,
Py_ssize_t *n_collected, Py_ssize_t *n_uncollectable,
int nofail)
{
...
PyGC_Head *young; /* the generation we are examining */
PyGC_Head *old; /* next older generation */
PyGC_Head unreachable; /* non-problematic unreachable trash */
...
young = GEN_HEAD(gcstate, generation);
if (generation < NUM_GENERATIONS-1)
old = GEN_HEAD(gcstate, generation+1);
else
old = young;
...
if (young != old) {
if (generation == NUM_GENERATIONS - 2) {
gcstate->long_lived_pending += gc_list_size(young);
}
gc_list_merge(young, old);
}
else {
/* We only un-track dicts in full collections, to avoid quadratic
dict build-up. See issue #14775. */
untrack_dicts(young);
gcstate->long_lived_pending = 0;
gcstate->long_lived_total = gc_list_size(young);
}
...
}
...
```
> [CPython原始碼](https://github.com/python/cpython/blob/3.10/Modules/gcmodule.c#L562)
---
### 6. 處理指向可回收物件的弱引用
現在我們知道了哪些物件為可回收物件(unreachable列表)，我們應該可以開始回收這些物件了吧？先等等！有些物件可能會有弱引用，且可能會需要呼叫callback函式，這就是handle_weakrefs在處理的事情囉，不過由於這並不是垃圾回收的重點，有興趣的人就自己追看看這個函式囉！
```c=
...
/* This is the main function. Read this to understand how the
* collection process works. */
static Py_ssize_t
gc_collect_main(PyThreadState *tstate, int generation,
Py_ssize_t *n_collected, Py_ssize_t *n_uncollectable,
int nofail)
{
int i;
PyGC_Head *young; /* the generation we are examining */
PyGC_Head *old; /* next older generation */
PyGC_Head unreachable; /* non-problematic unreachable trash */
PyGC_Head *gc;
...
/* 6. 處理指向可回收物件的弱引用 */
m += handle_weakrefs(&unreachable, old);
...
}...
```
> [CPython原始碼](https://github.com/python/cpython/blob/3.10/Modules/gcmodule.c#L1183)
---
### 7. 若可回收物件有定義tp_finalize函式(也就是python中的def \_\_del\_\_)，則執行tp_finalize函式
現在離真正回收物件只差一點了！在回收物件之前，可別忘了使用者會在Python中定義__del__這個方法，這就代表在物件被刪除之前，要執行的程式碼喔！而Python定義的__del__就是對應到CPython中的
tp_finalize函式，因此在回收物件之前，我們要先執行所有可回收物件的tp_finalize函式：
```c=
...
/* This is the main function. Read this to understand how the
* collection process works. */
static Py_ssize_t
gc_collect_main(PyThreadState *tstate, int generation,
Py_ssize_t *n_collected, Py_ssize_t *n_uncollectable,
int nofail)
{
int i;
PyGC_Head *young; /* the generation we are examining */
PyGC_Head *old; /* next older generation */
PyGC_Head unreachable; /* non-problematic unreachable trash */
PyGC_Head *gc;
...
/* 7. 若可回收物件有定義tp_finalize函式，則執行tp_finalize函式 */
finalize_garbage(tstate, &unreachable);
...
}...
```
> [CPython原始碼](https://github.com/python/cpython/blob/3.10/Modules/gcmodule.c#L1183)
```c=
...
static void
finalize_garbage(PyThreadState *tstate, PyGC_Head *collectable)
{
destructor finalize;
PyGC_Head seen;
/* While we're going through the loop, `finalize(op)` may cause op, or
* other objects, to be reclaimed via refcounts falling to zero. So
* there's little we can rely on about the structure of the input
* `collectable` list across iterations. For safety, we always take the
* first object in that list and move it to a temporary `seen` list.
* If objects vanish from the `collectable` and `seen` lists we don't
* care.
*/
gc_list_init(&seen);
while (!gc_list_is_empty(collectable)) {
PyGC_Head *gc = GC_NEXT(collectable);
PyObject *op = FROM_GC(gc);
gc_list_move(gc, &seen);
if (!_PyGCHead_FINALIZED(gc) &&
(finalize = Py_TYPE(op)->tp_finalize) != NULL) {
_PyGCHead_SET_FINALIZED(gc);
Py_INCREF(op);
finalize(op);
assert(!_PyErr_Occurred(tstate));
Py_DECREF(op);
}
}
gc_list_merge(&seen, collectable);
}
...
```
> [CPython原始碼](https://github.com/python/cpython/blob/3.10/Modules/gcmodule.c#L959)
---
### 8. 再次標記真正可回收及不可回收的物件，並將不可回收的物件移至老一代GC列表中
而由於我們在上一步執行了所有可回收物件的tp_finalize函式，有可能造成可回收物件又轉為不可回收物件了，因此我們需要再重新針對unreachable列表中的物件，再次標記最終可回收物件，這要怎麼做呢？就是再透過我們先前提到的deduce_unreachable函式囉！且我們會再將轉為不可回收的物件，再移至老一代的GC物件列表中：
```c=
...
/* This is the main function. Read this to understand how the
* collection process works. */
static Py_ssize_t
gc_collect_main(PyThreadState *tstate, int generation,
Py_ssize_t *n_collected, Py_ssize_t *n_uncollectable,
int nofail)
{
int i;
PyGC_Head *young; /* the generation we are examining */
PyGC_Head *old; /* next older generation */
PyGC_Head unreachable; /* non-problematic unreachable trash */
PyGC_Head *gc;
...
/* 8. 再次標記真正可回收及不可回收的物件，並將不可回收的物件移至老一代GC列表中 */
PyGC_Head final_unreachable;
handle_resurrected_objects(&unreachable, &final_unreachable, old);
...
}...
```
> [CPython原始碼](https://github.com/python/cpython/blob/3.10/Modules/gcmodule.c#L1183)
```c=
```c=
...
static inline void
handle_resurrected_objects(PyGC_Head *unreachable, PyGC_Head* still_unreachable,
PyGC_Head *old_generation)
{
// Remove the PREV_MASK_COLLECTING from unreachable
// to prepare it for a new call to 'deduce_unreachable'
gc_list_clear_collecting(unreachable);
// After the call to deduce_unreachable, the 'still_unreachable' set will
// have the PREV_MARK_COLLECTING set, but the objects are going to be
// removed so we can skip the expense of clearing the flag.
PyGC_Head* resurrected = unreachable;
deduce_unreachable(resurrected, still_unreachable);
clear_unreachable_mask(still_unreachable);
// Move the resurrected objects to the old generation for future collection.
gc_list_merge(resurrected, old_generation);
}
...
```
> [CPython原始碼](https://github.com/python/cpython/blob/3.10/Modules/gcmodule.c#L1162)
---
### 9. 刪除可回收的物件
最後，我們拿到了最終可回收物件列表(final_unreachable)，我們終於可以進行回收啦！而進行回收的方式，就是透過物件所定義的tp_clear函式來回收囉！
```c=
...
/* This is the main function. Read this to understand how the
* collection process works. */
static Py_ssize_t
gc_collect_main(PyThreadState *tstate, int generation,
Py_ssize_t *n_collected, Py_ssize_t *n_uncollectable,
int nofail)
{
int i;
PyGC_Head *young; /* the generation we are examining */
PyGC_Head *old; /* next older generation */
PyGC_Head unreachable; /* non-problematic unreachable trash */
PyGC_Head *gc;
...
/* 9. 刪除可回收的物件 */
delete_garbage(tstate, gcstate, &final_unreachable, old);
...
}...
```
> [CPython原始碼](https://github.com/python/cpython/blob/3.10/Modules/gcmodule.c#L1183)
```c=
...
static void
delete_garbage(PyThreadState *tstate, GCState *gcstate,
PyGC_Head *collectable, PyGC_Head *old)
{
assert(!_PyErr_Occurred(tstate));
while (!gc_list_is_empty(collectable)) {
PyGC_Head *gc = GC_NEXT(collectable);
PyObject *op = FROM_GC(gc);
...
if (gcstate->debug & DEBUG_SAVEALL) {
...
}
else {
inquiry clear;
if ((clear = Py_TYPE(op)->tp_clear) != NULL) {
Py_INCREF(op);
(void) clear(op);
if (_PyErr_Occurred(tstate)) {
_PyErr_WriteUnraisableMsg("in tp_clear of",
(PyObject*)Py_TYPE(op));
}
Py_DECREF(op);
}
}
if (GC_NEXT(collectable) == gc) {
/* object is still alive, move it, it may die later */
gc_clear_collecting(gc);
gc_list_move(gc, old);
}
}
}
...
```
> [CPython原始碼](https://github.com/python/cpython/blob/3.10/Modules/gcmodule.c#L995)
以上，我們就瞭解了CPython記憶體回收的機制囉！不過當然，實際上CPython還是做了許多優化的，這邊我們只是講解了一下CPython記憶體回收的大致的運作方式喔！
Sign in with Wallet
Connect another wallet