Python的垃圾回收機制以引?計數器為主、分代碼回收和標記清除為輔

1.refchai鏈表

在Python的C源碼中有?個名為refchain的環狀雙向鏈表，在Python程序中每創建1個對象，就會將其加入此鏈表。

city = '四川'  內部會創建一個結構體，包含【上一個對象、下一個對象、類型、引用計數、值、其他特有屬性】
num= 123

static PyObject refchain = {&refchain, &refchain}

1.1兩個重要的結構體

#define PyObject_HEAD PyObject ob_base;
#define PyObject_VAR_HEAD PyVarObject ob_base;

// 宏定義，包含 上?個、下?個，?于構造雙向鏈表?。(將對象放到refchain鏈表中時，需要?到)
#define _PyObject_HEAD_EXTRA \
    struct _object *_ob_next; \
    struct _object *_ob_prev;

typedef struct _object {
    _PyObject_HEAD_EXTRA // ?于構造雙向鏈表
    Py_ssize_t ob_refcnt; // 引?計數器
    struct _typeobject *ob_type; // 數據類型
} PyObject;

typedef struct {
    PyObject ob_base; // PyObject對象
    Py_ssize_t ob_size; /* Number of items in variable part，即：元素個數 */
} PyVarObjec;

這兩個結構體PyObject和PyVarObject是基本結構，他們是各數據類型公共部分。PyVarObject主要在多元素對象創建時使用，它在PyObject基礎上添加了一個ob_size用于記錄元素個數。

例：單元素的對象在創建時大多使用PyObject，會包含其4部分基礎數據；list/tuple/set等由多個元素組成對象創建時使用的PyVarObject，會包含其5部分基礎數據

1.2常?類型結構體

• int類型

struct _longobject {
    PyObject_VAR_HEAD
    digit ob_digit[1];
};
/* Long (arbitrary precision) integer object interface */
typedef struct _longobject PyLongObject; /* Revealed in longintrepr.h *

• float類型

typedef struct {
    PyObject_HEAD
    double ob_fval;
} PyFloatObjec;

• str類型

typedef struct {
    PyObject_HEAD
    Py_ssize_t length; /* Number of code points in the string*/
    Py_hash_t hash; /* Hash value; -1 if not set */
    struct {
        unsigned int interned:2;
        /* Character size:
        - PyUnicode_WCHAR_KIND (0):
        * character type = wchar_t (16 or 32 bits, depending on the
        platform)
        - PyUnicode_1BYTE_KIND (1):
        * character type = Py_UCS1 (8 bits, unsigned)
        * all characters are in the range U+0000-U+00FF (latin1)
        * if ascii is set, all characters are in the range U+0000-U+007F
        (ASCII), otherwise at least one character is in the rangeU+0080-U+00FF
        - PyUnicode_2BYTE_KIND (2):
        * character type = Py_UCS2 (16 bits, unsigned)
        * all characters are in the range U+0000-U+FFFF (BMP)
        * at least one character is in the range U+0100-U+FFFF
        - PyUnicode_4BYTE_KIND (4):
        * character type = Py_UCS4 (32 bits, unsigned)
        * all characters are in the range U+0000-U+10FFFF
        * at least one character is in the range U+10000-U+10FFFF
        */
        unsigned int kind:3;
        unsigned int compact:1;
        unsigned int ascii:1;
        unsigned int ready:1;
    	unsigned int :24;
    } state;
    wchar_t *wstr; /* wchar_t representation (null-terminated) */
} PyASCIIObject;
typedef struct {
    PyASCIIObject _base;
    Py_ssize_t utf8_length; /* Number of bytes in utf8, excluding the
    * terminating \0. */
    char *utf8; /* UTF-8 representation (null-terminated) */
    Py_ssize_t wstr_length; /* Number of code points in wstr, possible
    * surrogates count as two code points.
    */
} PyCompactUnicodeObject;
typedef struct {
	PyCompactUnicodeObject _base;
	union {
        void *any;
        Py_UCS1 *latin1;
        Py_UCS2 *ucs2;
        Py_UCS4 *ucs4;
	} data; /* Canonical, smallest-form Unicode buffer */
} PyUnicodeObjec;

str類型?較繁瑣，因為python字符串在處理時需要考慮到編碼問題，在python內部規定（?源碼結構體）：
字符串只包含ascii，則每個字符?1個字節表示，即：latin1
字符串包含中?等，則每個字符?2個字節表示，即：ucs2
字符串包含emoji等，則每個字符?4個字節表示，即：ucs4

• list類型

typedef struct {
    PyObject_VAR_HEAD
    PyObject **ob_item;
    Py_ssize_t allocated;
} PyListObjec;

• tuple類型

typedef struct {
    PyObject_VAR_HEAD
    PyObject *ob_item[1];
} PyTupleObjec;

• dict類型

typedef struct {
    PyObject_HEAD
    Py_ssize_t ma_used;
    PyDictKeysObject *ma_keys;
    PyObject **ma_values;
} PyDictObjec;

1.3 Float類型創建

val = 3.14

val = 3.14 
內部會創建： 
    _ob_next = refchain中的上一個對象 
    _ob_prev = refchain中的下一個對象 
    ob_refcnt = 1 //引用計數
    ob_type = float //類型
    ob_fval = 3.14 //值

下面是創建到銷毀的部分源碼，有的可以暫時不關注

創建對象3.14

// Objects/floatobject.c
// ?于緩存float對象的鏈表
static PyFloatObject *free_list = NULL;
static int numfree = 0;
PyObject *
PyFloat_FromDouble(double fval)
{
    // 如果free_list中有可?對象，則從free_list鏈表拿出來?個；否則為對象重新開辟內存。
    PyFloatObject *op = free_list;
    if (op != NULL) {
        free_list = (PyFloatObject *) Py_TYPE(op);
        numfree--;
    } else {
        // 根據float類型的??，為float對象新開辟內存。
        op = (PyFloatObject*) PyObject_MALLOC(sizeof(PyFloatObject));
        if (!op)
        return PyErr_NoMemory();
    }
    // 對float對象進?初始化，例如：引?計數器初始化為1、添加到refchain鏈表等。
    /* Inline PyObject_New */
    (void)PyObject_INIT(op, &PyFloat_Type);
    // 對float對象賦值。即：op->ob_fval = 3.14
    op->ob_fval = fval;
    return (PyObject *) op;
}

加入refchain鏈表

// Include/objimpl.h
#define PyObject_INIT(op, typeobj) \( Py_TYPE(op) = (typeobj), _Py_NewReference((PyObject *)(op)), (op) 
// Objects/object.c
// 維護了所有對象的?個環狀雙向鏈表
static PyObject refchain = {&refchain, &refchain};
void
_Py_AddToAllObjects(PyObject *op, int force)
{
    if (force || op->_ob_prev == NULL) {
        op->_ob_next = refchain._ob_next;
        op->_ob_prev = &refchain;
        refchain._ob_next->_ob_prev = op;
        refchain._ob_next = op;
    }
}
void
_Py_NewReference(PyObject *op)
{
    _Py_INC_REFTOTAL;
    // 引?計數器初始化為1。
    op->ob_refcnt = 1;
    // 對象添加到雙向鏈表refchain中。
    _Py_AddToAllObjects(op, 1);
    _Py_INC_TPALLOCS(op);
}

添加引用計數

// Include/object.h
static inline void _Py_INCREF(PyObject *op)
{
    _Py_INC_REFTOTAL;
    // 對象的引?計數器 + 1
    op->ob_refcnt++;
}
#define Py_INCREF(op) _Py_INCREF(_PyObject_CAST(op))

銷毀

val = 3.14
del va

在項?中如果出現這種刪除的語句，則內部會將引?計數器-1，如果引?計數器減為0，則進?緩存或垃圾回收。

// Include/object.h
static inline void _Py_DECREF(const char *filename, int lineno, PyObject *op)
{
    (void)filename; /* may be unused, shut up -Wunused-parameter */
    (void)lineno; /* may be unused, shut up -Wunused-parameter */
    _Py_DEC_REFTOTAL;
    // 引?計數器-1，如果引?計數器為0，則執? _Py_Dealloc去緩存或垃圾回收。
    if (--op->ob_refcnt != 0) {
#ifdef Py_REF_DEBUG
        if (op->ob_refcnt < 0) {
            _Py_NegativeRefcount(filename, lineno, op);
        }
#endif
	}
    else {
    	_Py_Dealloc(op);
	}
}
#define Py_DECREF(op) _Py_DECREF(__FILE__, __LINE__, _PyObject_CAST(op)

// Objects/object.c
void
_Py_Dealloc(PyObject *op)
{
    // 找到float類型的 tp_dealloc 函數
    destructor dealloc = Py_TYPE(op)->tp_dealloc;
    // 在refchain雙向鏈表中摘除此對象。
    _Py_ForgetReference(op);
    // 執?float類型的 tp_dealloc 函數，去進?緩存或垃圾回收。
    (*dealloc)(op);
}
void
_Py_ForgetReference(PyObject *op)
{
    ...
    // 在refchain鏈表中移除此對象
    op->_ob_next->_ob_prev = op->_ob_prev;
    op->_ob_prev->_ob_next = op->_ob_next;
    op->_ob_next = op->_ob_prev = NULL;
    _Py_INC_TPFREES(op);
}

// Objects/floatobject.c
#define PyFloat_MAXFREELIST 100
static int numfree = 0;
static PyFloatObject *free_list = NULL;
// float類型中函數的對應關系
PyTypeObject PyFloat_Type = {
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    "float",
    sizeof(PyFloatObject),
    0,
    // tp_dealloc表示執?float_dealloc?法
    (destructor)float_dealloc, /* tp_dealloc */
    0, /* tp_print */
    ...
};
static void
float_dealloc(PyFloatObject *op)
{
    // 檢測是否是float類型
    if (PyFloat_CheckExact(op)) {
        // 檢測free_list中緩存的個數是否已滿，如果已滿，則直接將對象銷毀。
    	if (numfree >= PyFloat_MAXFREELIST) {
            // 銷毀
            PyObject_FREE(op);
    		return;
		}
		// 將對象加?到free_list鏈表中
        numfree++;
		Py_TYPE(op) = (struct _typeobject *)free_list;
		free_list = op;
	}
	else
		Py_TYPE(op)->tp_free((PyObject *)op);
}

2.引用計數器

val = 3.14 
內部會創建： 
    _ob_next = refchain中的上一個對象 
    _ob_prev = refchain中的下一個對象 
    ob_refcnt = 1 //引用計數
    ob_type = float //類型
    ob_fval = 3.14 //值

如上，在python中，創建一個數據對象后，結構體中會有一個ob_refcnt參數，默認值是1

• 當有其他變量引用該對象時，該參數會+1
• 引用該對象的變量被刪除時，該參數會-1

這就是對象的引用計數器

eg:
val = 3.14  //ob_refcnt = 1
vv = val    //ob_refcnt = 2
del vv      //ob_refcnt = 1

源碼：

// Include/object.h
static inline void _Py_INCREF(PyObject *op)
{
    _Py_INC_REFTOTAL;
    // 對象的引?計數器 + 1
    op->ob_refcnt++;
}
#define Py_INCREF(op) _Py_INCREF(_PyObject_CAST(op))

當引用計數器為0時，表示該對象沒有被任何人使用，此時該對象就是垃圾，需要垃圾回收。

垃圾回收有兩種情況：

• 對象從refchain鏈移除后，將對象直接銷毀，回收內存空間
• 對象從refchain鏈移除后，將對象加入free_list（緩存鏈表中），等待之后再創建對象時直接提取（不需要重新開辟內存），初始化后使用，以提高效率

源碼：參考1.3銷毀部分

3.標記清除和分代回收

如果只使用引用計數器進行垃圾回收，在出現循環引用時，會導致對象無法回收，從而內存泄漏。

例如：

v1 = [11,22,33] # refchain中創建?個列表對象，由于v1=對象，所以列表引對象?計數器為1. ob_refcnt = 1
v2 = [44,55,66] # refchain中再創建?個列表對象，因v2=對象，所以列表對象引?計數器為1. ob_refcnt = 1
v1.append(v2) # 把v2追加到v1中，則v2對應的[44,55,66]對象的引?計數器加1，最終為2. ob_refcnt = 2
v2.append(v1) # 把v1追加到v1中，則v1對應的[11,22,33]對象的引?計數器加1，最終為2. ob_refcnt = 2
del v1 # 引?計數器-1 ob_refcnt = 1
del v2 # 引?計數器-1 ob_refcnt = 1

如上，現在外部已經沒人在使用者兩個對象了，但是由于存在循環引用，所以引用計數器仍然不為0。針對這種情況，python引入了標記清除機制。

標記清除：在python底層，創建特殊鏈表專??于保存可能存在循環應?的類型（列表、元組、字典、集合、?定義類等對象），之后再去檢查這個鏈表中的對象是否存在循環引?，如果存在則讓雙?的引?計數器均 - 1 。

在標記清除中，如果每次都全量掃描所有對象，那么效率會很低，為了優化這一問題，python引入了分代回收機制。

分代回收：對標記清除中的鏈表進?優化，將那些可能存在循引?的對象拆分到3個鏈表，鏈表分為：0/1/2三代，每代都可以存儲對象，有自己特定的閾值，當達到閾值時，就會對相應的鏈表中的每個對象做?次掃描，將循環引?對象的計數各?減1，并且銷毀引?計數器為0的對象。

gcmodule.c


  struct gc_generation {
      PyGC_Head head;
      int threshold; /* collection threshold */  // 閾值
      int count; /* count of allocations or collections of younger
                    generations */    // 實時個數
  };

#define NUM_GENERATIONS 3
struct gc_generation generations[NUM_GENERATIONS] = {
    /* PyGC_Head,                                        threshold, count */
    {{(uintptr_t)_GEN_HEAD(0), (uintptr_t)_GEN_HEAD(0)}, 700,       0},
    // 0代
    {{(uintptr_t)_GEN_HEAD(1), (uintptr_t)_GEN_HEAD(1)}, 10,        0},
    // 1代
    {{(uintptr_t)_GEN_HEAD(2), (uintptr_t)_GEN_HEAD(2)}, 10,        0},
    // 2代
};

特別注意：0代和1、2代的threshold和count表示的意義不同。
0代：count表示0代鏈表中對象的數量，threshold表示0代鏈表對象個數閾值，超過則執??次0代掃描檢查。
1代：count表示0代鏈表掃描的次數，threshold表示0代鏈表掃描的次數閾值，超過則執??次1代掃描查。
2代：count表示1代鏈表掃描的次數，threshold表示1代鏈表掃描的次數閾值，超過則執??2代掃描檢查。

源碼：

Modules/gcmodule.c

/* GC information is stored BEFORE the object structure. */
typedef union _gc_head {
    struct {
        // 建立鏈表需要的前后指針
        union _gc_head *gc_next;
        union _gc_head *gc_prev;
        // 在初始化時會被初始化為 GC_UNTRACED
        Py_ssize_t gc_refs;
    } gc;
    long double dummy;  /* force worst-case alignment */
} PyGC_Head;

創建對象的過程: 對象 = pyGC_Head | PyObject_HEAD | Container Object

PyObject *
_PyObject_GC_New(PyTypeObject *tp)
{
    PyObject *op = _PyObject_GC_Malloc(_PyObject_SIZE(tp));
    if (op != NULL)
        op = PyObject_INIT(op, tp);
    return op;
}

=> _PyObject_GC_Malloc

#define _PyGC_REFS_UNTRACKED                    (-2)
#define GC_UNTRACKED                    _PyGC_REFS_UNTRACKED

PyObject *
_PyObject_GC_Malloc(size_t basicsize)
{
    PyObject *op;
    PyGC_Head *g;
    if (basicsize > PY_SSIZE_T_MAX - sizeof(PyGC_Head))
        return PyErr_NoMemory();

    // 為 對象本身+PyGC_Head申請內存, 注意分配的size
    g = (PyGC_Head *)PyObject_MALLOC(
        sizeof(PyGC_Head) + basicsize);
    if (g == NULL)
        return PyErr_NoMemory();

    // 初始化 GC_UNTRACED
    g->gc.gc_refs = GC_UNTRACKED;
    generations[0].count++; /* number of allocated GC objects */

    // 如果大于閾值, 執行分代回收
    if (generations[0].count > generations[0].threshold &&
        enabled &&
        generations[0].threshold &&
        !collecting &&
        !PyErr_Occurred()) {

        collecting = 1;
        collect_generations();
        collecting = 0;
    }
    op = FROM_GC(g);
    return op;
}

注意, FROM_GC和AS_GC用于 PyObject_HEAD <=> PyGC_HEAD地址相互轉換

// => Modules/gcmodule.c

/* Get an object's GC head */
#define AS_GC(o) ((PyGC_Head *)(o)-1)

/* Get the object given the GC head */
#define FROM_GC(g) ((PyObject *)(((PyGC_Head *)g)+1))

// => objimpl.h

#define _Py_AS_GC(o) ((PyGC_Head *)(o)-1)

將list對象放到這個對象鏈表中

// => listobject.c

PyObject *
PyList_New(Py_ssize_t size)
{
    PyListObject *op;
    op = PyObject_GC_New(PyListObject, &PyList_Type);
    _PyObject_GC_TRACK(op);
    return (PyObject *) op;
}

// =>  _PyObject_GC_TRACK

// objimpl.h
// 加入到可收集對象鏈表中

#define _PyObject_GC_TRACK(o) do { \
    PyGC_Head *g = _Py_AS_GC(o); \
    if (g->gc.gc_refs != _PyGC_REFS_UNTRACKED) \
        Py_FatalError("GC object already tracked"); \
    g->gc.gc_refs = _PyGC_REFS_REACHABLE; \
    g->gc.gc_next = _PyGC_generation0; \
    g->gc.gc_prev = _PyGC_generation0->gc.gc_prev; \
    g->gc.gc_prev->gc.gc_next = g; \
    _PyGC_generation0->gc.gc_prev = g; \
    } while (0);

將對象鏈表中摘除

// Objects/listobject.c

static void
list_dealloc(PyListObject *op)
{
    Py_ssize_t i;
    PyObject_GC_UnTrack(op);
    .....
}

// => PyObject_GC_UnTrack => _PyObject_GC_UNTRACK

// 對象銷毀的時候
#define _PyObject_GC_UNTRACK(o) do { \
    PyGC_Head *g = _Py_AS_GC(o); \
    assert(g->gc.gc_refs != _PyGC_REFS_UNTRACKED); \
    g->gc.gc_refs = _PyGC_REFS_UNTRACKED; \
    g->gc.gc_prev->gc.gc_next = g->gc.gc_next; \
    g->gc.gc_next->gc.gc_prev = g->gc.gc_prev; \
    g->gc.gc_next = NULL; \
    } while (0);

垃圾回 例：

第?步：創建對象age=22，并將對象添加到refchain鏈表中。

第?步：創建對象num_list = [11,22]，并將列表對象添加到 refchain和generations 0代中。

第三步：新創建對象使generations 0鏈表上的對象數量?于閾值700，對鏈表上的對象進?掃描檢查。
當0代?于閾值后，底層不是直接掃描0代，?是先判斷2、1代是否也超過了閾值。

• 如果2、1代未達到閾值，則掃描0代，并讓1代的 count + 1 。
• 如果2代已達到閾值，則將2、1、0三個鏈表拼接起來進?全掃描，并將2、1、0代的count重置為0。
• 如果1代已達到閾值，則講1、0兩個鏈表拼接起來進?掃描，并將所有1、0代的count重置為0。

 PyObject *
  _PyObject_GC_Malloc(size_t basicsize)
  {
      // 執行分配
      ....
      generations[0].count++; /* number of allocated GC objects */  //增加一個
      if (generations[0].count > generations[0].threshold && // 發現大于預支了
          enabled &&
          generations[0].threshold &&
          !collecting &&
          !PyErr_Occurred())
          {
              collecting = 1;
              collect_generations();  //  執行收集
              collecting = 0;
          }
      op = FROM_GC(g);
      return op;
  }

=> collect_generations

  static Py_ssize_t
  collect_generations(void)
  {
      int i;
      Py_ssize_t n = 0;

      /* Find the oldest generation (highest numbered) where the count
       * exceeds the threshold.  Objects in the that generation and
       * generations younger than it will be collected. */

      // 從最老的一代, 開始回收
      for (i = NUM_GENERATIONS-1; i >= 0; i--) {  // 遍歷所有generation
          if (generations[i].count > generations[i].threshold) {  // 如果超過了閾值
              /* Avoid quadratic performance degradation in number
                 of tracked objects. See comments at the beginning
                 of this file, and issue #4074.
              */
              if (i == NUM_GENERATIONS - 1
                  && long_lived_pending < long_lived_total / 4)
                  continue;
              n = collect(i); // 執行收集
              break;  // notice: break了
          }
      }
      return n;
  }

gcmodule.c

  /* This is the main function.  Read this to understand how the
   * collection process works. */
  static Py_ssize_t
  collect(int generation)
  {
    // 第1步: 將所有比 當前代 年輕的代中的對象 都放到 當前代 的對象鏈表中
    /* merge younger generations with one we are currently collecting */
    for (i = 0; i < generation; i++) {
        gc_list_merge(GEN_HEAD(i), GEN_HEAD(generation));
    }


    // 第2步
    update_refs(young);
    // 第3步
    subtract_refs(young);

    // 第4步
    gc_list_init(&unreachable);
    move_unreachable(young, &unreachable);

    // 第5步
      /* Move reachable objects to next generation. */
      if (young != old) {
          if (generation == NUM_GENERATIONS - 2) {
              long_lived_pending += gc_list_size(young);
          }
          gc_list_merge(young, old);
      }
      else {
          /* We only untrack dicts in full collections, to avoid quadratic
             dict build-up. See issue #14775. */
          untrack_dicts(young);
          long_lived_pending = 0;
          long_lived_total = gc_list_size(young);
      }

    // 第6步
      delete_garbage(&unreachable, old);

  }

將所有比 當前代 年輕的代中的對象 都放到 當前代 的對象鏈表中

// => gc_list_merge

// 執行拷貝而已
/* append list `from` onto list `to`; `from` becomes an empty list */
static void
gc_list_merge(PyGC_Head *from, PyGC_Head *to)
{
    PyGC_Head *tail;
    assert(from != to);
    if (!gc_list_is_empty(from)) {
        tail = to->gc.gc_prev;
        tail->gc.gc_next = from->gc.gc_next;
        tail->gc.gc_next->gc.gc_prev = tail;
        to->gc.gc_prev = from->gc.gc_prev;
        to->gc.gc_prev->gc.gc_next = to;
    }
    // 清空
    gc_list_init(from);
}

=>

static void
gc_list_init(PyGC_Head *list)
{
    list->gc.gc_prev = list;
    list->gc.gc_next = list;
}

對拼接起來的鏈表在進?掃描時，主要就是剔除循環引?和銷毀垃圾，詳細過程為：

• 掃描鏈表，把每個對象的引?計數器拷??份并保存到gc_refs中，保護原引?計數器。

//遍歷對象鏈表, 將每個對象的gc.gc_ref值設置為ob_refcnt
// => gcmodule.c

static void
update_refs(PyGC_Head *containers)
{
    PyGC_Head *gc = containers->gc.gc_next;
    for (; gc != containers; gc = gc->gc.gc_next) {
        assert(gc->gc.gc_refs == GC_REACHABLE);
        gc->gc.gc_refs = Py_REFCNT(FROM_GC(gc));
        /* Python's cyclic gc should never see an incoming refcount
         * of 0:  if something decref'ed to 0, it should have been
         * deallocated immediately at that time.
         * Possible cause (if the assert triggers):  a tp_dealloc
         * routine left a gc-aware object tracked during its teardown
         * phase, and did something-- or allowed something to happen --
         * that called back into Python.  gc can trigger then, and may
         * see the still-tracked dying object.  Before this assert
         * was added, such mistakes went on to allow gc to try to
         * delete the object again.  In a debug build, that caused
         * a mysterious segfault, when _Py_ForgetReference tried
         * to remove the object from the doubly-linked list of all
         * objects a second time.  In a release build, an actual
         * double deallocation occurred, which leads to corruption
         * of the allocator's internal bookkeeping pointers.  That's
         * so serious that maybe this should be a release-build
         * check instead of an assert?
         */
        assert(gc->gc.gc_refs != 0);
    }
}

• 再次掃描鏈表中的每個對象，并檢查是否存在循環引?，如果存在則讓各?的gc_refs減 1 。

  /* A traversal callback for subtract_refs. */
  static int
  visit_decref(PyObject *op, void *data)
  {
      assert(op != NULL);
      // 判斷op指向的對象是否是被垃圾收集監控的, 對象的type對象中有Py_TPFLAGS_HAVE_GC符號
      if (PyObject_IS_GC(op)) {
          PyGC_Head *gc = AS_GC(op);
          /* We're only interested in gc_refs for objects in the
           * generation being collected, which can be recognized
           * because only they have positive gc_refs.
           */
          assert(gc->gc.gc_refs != 0); /* else refcount was too small */
          if (gc->gc.gc_refs > 0)
              gc->gc.gc_refs--;  // -1
      }
      return 0;
  }


  /* Subtract internal references from gc_refs.  After this, gc_refs is >= 0
   * for all objects in containers, and is GC_REACHABLE for all tracked gc
   * objects not in containers.  The ones with gc_refs > 0 are directly
   * reachable from outside containers, and so can't be collected.
   */
  static void
  subtract_refs(PyGC_Head *containers)
  {
      traverseproc traverse;
      PyGC_Head *gc = containers->gc.gc_next;
      // 遍歷鏈表
      for (; gc != containers; gc=gc->gc.gc_next) {
          // 與特定的類型相關, 得到類型對應的traverse函數
          traverse = Py_TYPE(FROM_GC(gc))->tp_traverse;
          // 調用
          (void) traverse(FROM_GC(gc),
                         (visitproc)visit_decref, // 回調形式傳入
                         NULL);
      }
  }

  static int
  dict_traverse(PyObject *op, visitproc visit, void *arg)
  {
      Py_ssize_t i = 0;
      PyObject *pk;
      PyObject *pv;

      // 遍歷所有鍵和值
      while (PyDict_Next(op, &i, &pk, &pv)) {
          Py_VISIT(pk);
          Py_VISIT(pv);
      }
      return 0;
  }

遍歷容器對象里面的所有對象, 通過visit_decref將這些對象的引用計數都-1,

• 再次掃描鏈表，將 gc_refs為 0 的對象移動到unreachable鏈表中；不為0的對象升級到下?代鏈表中。

 /* Move the unreachable objects from young to unreachable.  After this,
   * all objects in young have gc_refs = GC_REACHABLE, and all objects in
   * unreachable have gc_refs = GC_TENTATIVELY_UNREACHABLE.  All tracked
   * gc objects not in young or unreachable still have gc_refs = GC_REACHABLE.
   * All objects in young after this are directly or indirectly reachable
   * from outside the original young; and all objects in unreachable are
   * not.
   */
  static void
  move_unreachable(PyGC_Head *young, PyGC_Head *unreachable)
  {
      PyGC_Head *gc = young->gc.gc_next;

      /* Invariants:  all objects "to the left" of us in young have gc_refs
       * = GC_REACHABLE, and are indeed reachable (directly or indirectly)
       * from outside the young list as it was at entry.  All other objects
       * from the original young "to the left" of us are in unreachable now,
       * and have gc_refs = GC_TENTATIVELY_UNREACHABLE.  All objects to the
       * left of us in 'young' now have been scanned, and no objects here
       * or to the right have been scanned yet.
       */

      while (gc != young) {
          PyGC_Head *next;

          // 對于root object,
          if (gc->gc.gc_refs) {
              /* gc is definitely reachable from outside the
               * original 'young'.  Mark it as such, and traverse
               * its pointers to find any other objects that may
               * be directly reachable from it.  Note that the
               * call to tp_traverse may append objects to young,
               * so we have to wait until it returns to determine
               * the next object to visit.
               */
              PyObject *op = FROM_GC(gc);
              traverseproc traverse = Py_TYPE(op)->tp_traverse;
              assert(gc->gc.gc_refs > 0);
              // 設置其gc->gc.gc_refs = GC_REACHABLE
              gc->gc.gc_refs = GC_REACHABLE;

              // 注意這里邏輯, visit_reachable, 意圖是?
              (void) traverse(op,
                              (visitproc)visit_reachable,
                              (void *)young);
              next = gc->gc.gc_next;
              if (PyTuple_CheckExact(op)) {
                  _PyTuple_MaybeUntrack(op);
              }
          }
          // 有效引用計數=0, 非root對象, 移動到unreachable鏈表中
          else {
              /* This *may* be unreachable.  To make progress,
               * assume it is.  gc isn't directly reachable from
               * any object we've already traversed, but may be
               * reachable from an object we haven't gotten to yet.
               * visit_reachable will eventually move gc back into
               * young if that's so, and we'll see it again.
               */
              next = gc->gc.gc_next;
              gc_list_move(gc, unreachable);
              gc->gc.gc_refs = GC_TENTATIVELY_UNREACHABLE;
          }
          gc = next;
      }
  }

將存活對象放入下一代

      /* Move reachable objects to next generation. */
      if (young != old) {
          if (generation == NUM_GENERATIONS - 2) {
              long_lived_pending += gc_list_size(young);
          }
          gc_list_merge(young, old);
      }
      else {
          /* We only untrack dicts in full collections, to avoid quadratic
             dict build-up. See issue #14775. */
          untrack_dicts(young);
          long_lived_pending = 0;
          long_lived_total = gc_list_size(young);
      }

• 處理unreachable鏈表中的對象的 析構函數 和 弱引?，不能被銷毀的對象升級到下?代鏈表，能銷毀的保留在此鏈表。
  析構函數：指的就是那些定義了__del__?法的對象，需要執?后再進?銷毀處理。

  弱引?：不會增加引用計數，當對象沒有強引用時會被回收

• 最后將unreachable中的每個對象回收（銷毀或放入free_list）并在refchain鏈表中移除。

gcmoudle.c

  static int
  gc_list_is_empty(PyGC_Head *list)
  {
      return (list->gc.gc_next == list);
  }


  /* Break reference cycles by clearing the containers involved.  This is
   * tricky business as the lists can be changing and we don't know which
   * objects may be freed.  It is possible I screwed something up here.
   */
  static void
  delete_garbage(PyGC_Head *collectable, PyGC_Head *old)
  {
      inquiry clear;

      // 遍歷
      while (!gc_list_is_empty(collectable)) {
          PyGC_Head *gc = collectable->gc.gc_next;
          // 得到對象
          PyObject *op = FROM_GC(gc);

          assert(IS_TENTATIVELY_UNREACHABLE(op));
          if (debug & DEBUG_SAVEALL) {
              PyList_Append(garbage, op);
          }
          else {
              // 清引用
              if ((clear = Py_TYPE(op)->tp_clear) != NULL) {
                  Py_INCREF(op);
                  // 這個操作會調整container對象中每個引用所有對象的引用計數, 從而完成打破循環的最終目標
                  clear(op);
                  Py_DECREF(op);
              }
          }

          // 重新送回到reachable鏈表.
          // 原因: 在進行clear動作, 如果成功, 會把自己從垃圾收集機制維護的鏈表中摘除, 由于某些原因, 對象可能在clear的時候, 沒有成功完成必要動作, 還不能被銷毀, 所以放回去
          if (collectable->gc.gc_next == gc) {
              /* object is still alive, move it, it may die later */
              gc_list_move(gc, old);
              gc->gc.gc_refs = GC_REACHABLE;
          }
      }
  }

=> 來看下, list的clear

static int
list_clear(PyListObject *a)
{
    Py_ssize_t i;
    PyObject **item = a->ob_item;
    if (item != NULL) {
        /* Because XDECREF can recursively invoke operations on
           this list, we make it empty first. */
        i = Py_SIZE(a);
        Py_SIZE(a) = 0;
        a->ob_item = NULL;
        a->allocated = 0;
        while (--i >= 0) {
            // 減引用
            Py_XDECREF(item[i]);
        }
        PyMem_FREE(item);
    }
    /* Never fails; the return value can be ignored.
       Note that there is no guarantee that the list is actually empty
       at this point, because XDECREF may have populated it again! */
    return 0;
}


// e.g. 處理list3, 調用其list_clear, 減少list4的引用計數, list4.ob_refcnt=0, 引發對象銷毀, 調用list4的list_dealloc


static void
list_dealloc(PyListObject *op)
{
    Py_ssize_t i;
    PyObject_GC_UnTrack(op);  //  從可收集對象鏈表中去除, 會影響到list4所引用所有對象的引用計數, => list3.refcnt=0, list3的銷毀動作也被觸發

    Py_TRASHCAN_SAFE_BEGIN(op)
    if (op->ob_item != NULL) {
        /* Do it backwards, for Christian Tismer.
           There's a simple test case where somehow this reduces
           thrashing when a *very* large list is created and
           immediately deleted. */
        i = Py_SIZE(op);
        while (--i >= 0) {
            Py_XDECREF(op->ob_item[i]);
        }
        PyMem_FREE(op->ob_item);
    }
    if (numfree < PyList_MAXFREELIST && PyList_CheckExact(op))
        free_list[numfree++] = op;
    else
        Py_TYPE(op)->tp_free((PyObject *)op);
    Py_TRASHCAN_SAFE_END(op)
}

4.緩存機制

由于反復的創建和銷毀會使程序的執?效率變低，所以Python中引?了一種緩存機制。即引?計數器為0時，不會真正銷毀對象，?是將他放到名為 free_list 的鏈表中，之后會再創建對象時不再重新開辟內存，?是從free_list中撈出一個對象，重置內部的值來使?。

不同數據類型的free_list是不一樣的：

• float類型，維護的free_list鏈表最多可緩存100個float對象。

v1 = 3.14 # 開辟內存來存儲float對象，并將對象添加到refchain鏈表。
print( id(v1) ) # 內存地址：4436033488
del v1 # 引?計數器-1，如果為0則在rechain鏈表中移除，不銷毀對象，?是將對象添加到float的free_list.
v2 = 9.999 # 優先去free_list中獲取對象，并重置為9.999，如果free_list為空才重新開辟內存。
print( id(v2) ) # 內存地址：4436033488
# 注意：引?計數器為0時，會先判斷free_list中緩存個數是否滿了，未滿則將對象緩存，已滿則直接將對象銷毀。

• list類型，維護的free_list數組最多可緩存80個list對象。

v1 = [111] 
print(id(v1)) # 2780926292480
del v1
v2 = [555] 
print(id(v2))# 2780926292480

• tuple類型，維護?個free_list數組且數組容量20，數組中元素可以是鏈表且每個鏈表最多可以容納2000個元組對象。元組的free_list數組在存儲數據時，是按照元組可以容納的個數為索引找到free_list數組中對應的鏈表，并添加到鏈表中。

v1 = (111, 2222)
print(id(v1))  # 2780926292480
del v1
v2 = ('zzz', 6666)
print(id(v2))  # 2780926292480

• dict類型，維護的free_list數組最多可緩存80個dict對象。

v1 = {'a': 222}
print(id(v1))  # 2780926292480
del v1
v2 = {'aa': 666}
print(id(v2))  # 2780926292480

另外，int和str類型，不是基于free_list，而是在python解釋器啟動時，就創建了一個小數據池。

• int類型，維護?個small_ints鏈表保存常?數據，?數據池范圍：-5 <= value < 257，當使?這個范圍的整數時，不會重新開辟內存。

v1 = 38 # 去?數據池small_ints中獲取38整數對象，將對象添加到refchain并讓引?計數器+1。
print( id(v1)) #內存地址：4514343712
v2 = 38 # 去?數據池small_ints中獲取38整數對象，將refchain中的對象的引?計數器+1。
print( id(v2) ) #內存地址：4514343712
# 注意：在解釋器啟動時候-5~256就已經被加?到small_ints鏈表中且引?計數器初始化為1，代碼中使?的值時直接去small_ints中拿來?并將引?計數器+1即可。另外，small_ints中的數據引?計數器永遠不會為0（初始化時就設置為1了），所以也不會被銷毀

• str類型，維護unicode_latin1[256]鏈表，內部將所有的ascii字符緩存起來，使?時就不再重新創建。

v1 = "A"
print( id(v1) ) # 輸出：4517720496
del v1
v2 = "A"
print( id(v1) ) # 輸出：4517720496
# 除此之外，Python內部還對字符串做了駐留機制，針對只含有字?、數字、下劃線的字符串（?源碼Objects/codeobject.c），如果內存中已存在則不會重新在創建?是使?原來的地址?（不會像free_list那樣?直在內存存活，只有內存中有才能被重復利?）。
v1 = "wupeiqi"
v2 = "wupeiqi"
print(id(v1) == id(v2)) # 輸出：True

注意：python在不同版本和不同環境下，上述代碼執行結果可能出現偏差，原因通常是 Python 內存分配器優化或特定代碼塊優化的結果。

CPython 解釋器中主要的數據駐留規則：

數據類型	駐留條件	說明與示例
整數	-5 到 256	這個范圍內的整數被預先創建并緩存，全局唯一。a = 100; b = 100; a is b 返回 True。
字符串	長度為 0 或 1	所有空字符串和單字符字符串都會被駐留。
	僅含字母、數字、下劃線的標識符	類似于變量名的字符串，如 "hello_world"。
	由乘法運算生成且長度有限制	規則較復雜，Python 版本不同，長度限制可能不同（如 20 或 4096），且字符串只能包含數字、字母、下劃線。
	顯式調用 sys.intern()	可以強制駐留任意字符串，常用于性能優化場景，如處理大量重復的字典鍵。
其他單例對象	None, True, False, Ellipsis (...)	這些對象在解釋器中是全局唯一的。
空不可變容器	空元組 (), 空字符串 ""	會被緩存。注意，空列表 [] 和空字典 {} 等可

1. 代碼塊優化：Python 會對一個代碼塊（如一個模塊、一個函數體、一個類定義或交互式環境中的單行命令）內的不可變對象進行一些優化，主要目的是提高執行效率和減少內存使用。如果在一個代碼塊內多次出現相同的浮點數字，解釋器可能會使其指向同一個對象以節省內存。但這并非強制規定，行為可能因 Python 版本或具體代碼上下文而異。
2. 內存分配器優化（Pymalloc）：Python 對小對象（通常小于等于512字節）有自己的內存分配器。當一個浮點數對象被銷毀后，其釋放的內存可能會被緊接著創建的相同大小的新對象（未必是相同的浮點數值）立即重用。這會導致你觀察到新對象的 ID（內存地址）與剛被銷毀的對象的 ID 相同，但這與基于值的駐留是兩回事。

參考資料：

Python垃圾回收.pdf

https://wklken.me/posts/2015/09/29/python-source-gc.html