原文：https://neucrack.com/p/46

GC: （Garbage Collector， 垃圾回收器）

在 CPython 中

垃圾回收采用了引用計數(shù)+ 標(biāo)記-清除 + 分代回收 的組合回收方法。
即給每個對象設(shè)置引用計數(shù)，當(dāng)引用計數(shù)為0就立即回收內(nèi)存；
但是由于對象之間存在互相引用的問題，單單使用引用計數(shù)是不夠的，于是引入了標(biāo)記-清除算法來回收來遍歷引用到了的對象，將沒有引用到的對象銷毀
標(biāo)記-清除方法需要消耗很多時間，為了提升效率，又引入了分代回收，將多次檢測都有效的對象升級為下一代，代數(shù)越高則檢查的次數(shù)就越少（共3代，每代實際上就是一個鏈表），以此來增加效率

Micropython GC

官方 wiki 介紹

與 CPython不同，Micropython 只使用了 標(biāo)記-清除算法，可以說是教科書般的標(biāo)記-清除算法實現(xiàn)了（官方的說法2333）

這里 GC 不單單包括了垃圾回收，實際上內(nèi)存分配方法也包含在了里面，大致上包含了以下幾個點：

• 系統(tǒng)預(yù)分配一塊內(nèi)存給GC使用，之后所有的操作都在這塊內(nèi)存上進行
• 然后分配和釋放時根據(jù)分配算法進行分配和釋放（后面再詳細(xì)說明）
• 在以下幾個情況執(zhí)行回收（使用標(biāo)記-清除算法(mark-sweep)：
  • 無法分配內(nèi)存
  • 設(shè)置了回收閾值(threshold)，當(dāng)距離上幾次回收后分配的空間（塊）數(shù)量打到了設(shè)置的閾值，則自動進行回收。當(dāng)然為了減少回收次數(shù)（某種意義上的）可以禁用這個功能
  • 手動調(diào)用函數(shù)進行回收

Micropython 中的 GC 詳細(xì)分析

數(shù)據(jù)儲存結(jié)構(gòu)

為了簡化程序，uPy將初始化時獲得的一段連續(xù)內(nèi)存區(qū)域分成3部分:

• 儲存數(shù)據(jù)塊分配信息，標(biāo)記內(nèi)存分配情況，稱為 ATB(alloc table)
• 儲存銷毀對象時是否需要調(diào)用析構(gòu)函數(shù)（finaliser）（__del__)，稱為FTB(finaliser table)
• 實際儲存數(shù)據(jù)的區(qū)域，稱為內(nèi)存池（pool），由多個塊（block）組成

uPy 分配內(nèi)存的最小單位是塊(block)(比如設(shè)置為16或者32字節(jié))，所以ATB FTB中記錄也是以塊為單位記錄的。

其中 ATB 標(biāo)記每個塊的狀態(tài)，包括 free， head（多個連續(xù)分配的塊的開始（頭））， tail（多個連續(xù)分配的塊的除了頭部塊以外的塊）， mark（標(biāo)記了的頭部，在回收時（collect）中才會標(biāo)記） 幾種狀態(tài)，每兩位表示一個block狀態(tài)，即每個字節(jié)可以表示4個block的狀態(tài)

FTB 則標(biāo)記是否使用 finaliser，每位表示一個block是否使用finaliser，即每個字節(jié)表示8個block是否使用finaliser

名詞

• block： 塊，分配的最小單位，比如設(shè)置為16或者32字節(jié)。
• finaliser：這里可理解成析構(gòu)，調(diào)用 類的__del__方法，（mpy目前(2019.5)還沒有實現(xiàn)調(diào)用用戶類的__del__方法）
• ATB: alloc table，標(biāo)記每個block的狀態(tài)，包括 free， head（多個連續(xù)分配的塊的開始（頭））， tail（多個連續(xù)分配的塊的除了頭部塊以外的塊）， mark（標(biāo)記了的頭部） 幾種狀態(tài)，每兩位表示一個block狀態(tài)，即每個字節(jié)可以表示4個block的狀態(tài)
• FTB: finaliser table標(biāo)記是否使用 finaliser，每位表示一個block是否使用finaliser，即每個字節(jié)表示8個block是否使用finaliser
• pool: 實際分配給用戶使用的空間（alloc 返回的地址），也就是數(shù)據(jù)實際儲存的位置，最小單位是塊
• (block) chain: （塊）鏈，分配內(nèi)存的最小單位是塊，比如一個塊32字節(jié)，如果用戶程序需要分配36個字節(jié)，則直接分配2個塊即64字節(jié)，這兩個塊稱為一個塊鏈（chain），我們標(biāo)記第一個塊為頭，后面的所有塊為尾(注意不是最后一個，是除了頭的所有塊）
• reachable object： 可達的對象，即可以通過變量引用引用得到的對象
• root object： 根節(jié)點對象，主要是指 uPy的一些特殊變量，比如局部字典、全局字典等，Micropython 中代碼如下：

    ////////////////////////////////////////////////////////////
    // START ROOT POINTER SECTION
    // Everything that needs GC scanning must start here, and
    // is followed by state in the mp_state_vm_t structure.
    //

    mp_obj_dict_t *dict_locals;
    mp_obj_dict_t *dict_globals;

    nlr_buf_t *nlr_top;
    . 
    .
    .
    //
    // END ROOT POINTER SECTION
    ////////////////////////////////////////////////////////////

初始化

指定一塊內(nèi)存區(qū)域用來內(nèi)存分配使用：

void gc_init(void *start, void *end)

#define BYTES_PER_WORD (sizeof(mp_uint_t))
#define MICROPY_BYTES_PER_GC_BLOCK (4 * BYTES_PER_WORD)
#define BYTES_PER_BLOCK (MICROPY_BYTES_PER_GC_BLOCK)
end = (void*)((uintptr_t)end & (~(BYTES_PER_BLOCK - 1)));  // 內(nèi)存對齊

從GC分配空間

uPy分配內(nèi)存時以一個塊為最小單位進行分配，并且對這些塊進行了標(biāo)記，初始化時所有塊的標(biāo)記都是free

每次分配，都至少分配1個塊，稱這次分配的空間為一個鏈（chain，即分配的連續(xù)內(nèi)存大于一個塊的大小時，比如一個塊32字節(jié)，需要分配124字節(jié)實際分配了128字節(jié)即128/32=4塊，稱這4塊為一個鏈（chain）），開頭第一個塊標(biāo)記為head，后面的塊都標(biāo)記為tail。 在代碼中，使用m_new(type, size)函數(shù)即可分配

另外，Micropython 有一個 finaliser的功能，可以簡單地理解為，如果在釋放對象時會嘗試去調(diào)用它的__del__方法（如果存在的話），在創(chuàng)建對象的時候會在對應(yīng)的 FTB 中設(shè)置標(biāo)記，表示這個block在釋放時需要調(diào)用__del__方法，只需要設(shè)置這一個block,比如一個對象占用了從第50到100共50個block， 申請時會在ATB的第50個block設(shè)置head標(biāo)記，剩下的全部設(shè)置tail，會在FTB的第50個位設(shè)置標(biāo)記（置1），其它位置不置1。

注意，使用finaliser的時候不再使用m_new，而是使用m_new_obj_with_finaliser（）來進行分配，這個函數(shù)里面會自動標(biāo)記。 另外如果使用這個函數(shù)創(chuàng)建的對象必須是一個有效的Micropython對象定義，比如

typedef struct{
    int a;
    int b;
} data_t;

data_t* p = m_new(data_t, 1);

這只是一個普通的結(jié)構(gòu)體；
在每個定義的第一個成員必須是mp_obj_base_t base；，在實例化對象的時候必須指定base.type（type是mp_obj_type_t類型）， 比如

typedef struct{
    mp_obj_base_t base;
    int a;
    int b;
}
data_t* p = m_new(data_t, 1);
p->base.type = NULL;

如果使用了m_new_obj_with_finaliser來創(chuàng)建對象，但是結(jié)構(gòu)體里面第一個成員又不是base，則最后在調(diào)用finaliser時就會出現(xiàn)致命的問題，可能會導(dǎo)致程序崩潰

比如 I2C 模塊中：

typedef struct _machine_hard_i2c_obj_t {
    mp_obj_base_t         base;
    i2c_device_number_t   i2c;
    machine_i2c_mode_t    mode;
    uint32_t              freq;         // Hz
    uint32_t              timeout;      // reserved
    uint16_t              addr;
    uint8_t               addr_size;
    mp_obj_t              on_receive;
    mp_obj_t              on_transmit;
    mp_obj_t              on_event;
    int                   pin_scl;
    int                   pin_sda; 
} machine_hard_i2c_obj_t;

STATIC const mp_rom_map_elem_t machine_i2c_locals_dict_table[] = {
    { MP_ROM_QSTR(MP_QSTR_init), MP_ROM_PTR(&machine_i2c_init_obj) },
    { MP_ROM_QSTR(MP_QSTR___del__), MP_ROM_PTR(&machine_i2c_deinit_obj) },
    。
    。
    。    
};

MP_DEFINE_CONST_DICT(mp_machine_soft_i2c_locals_dict, machine_i2c_locals_dict_table);

const mp_obj_type_t machine_hard_i2c_type = {
    { &mp_type_type },
    .name = MP_QSTR_I2C,
    .print = machine_hard_i2c_print,
    .make_new = machine_hard_i2c_make_new,
    .protocol = &machine_hard_i2c_p,
    .locals_dict = (mp_obj_dict_t*)&mp_machine_soft_i2c_locals_dict,
};

在machine_hard_i2c_make_new函數(shù)中，即用戶通過i2c = machine.I2C()來創(chuàng)建對象的時候調(diào)用的函數(shù)中，會創(chuàng)建一個machine_hard_i2c_obj_t的對象，如果不使用finaliser：

machine_hard_i2c_obj_t *self = m_new_obj(machine_hard_i2c_obj_t);
self->base.type = &machine_hard_i2c_type;
.
.
.
return MP_OBJ_FROM_PTR(self);

這樣在對象銷毀時不會調(diào)用__del__方法，如果需要自動調(diào)用：

machine_hard_i2c_obj_t *self = m_new_obj_with_finaliser(machine_hard_i2c_obj_t);
self->base.type = &machine_hard_i2c_type;

內(nèi)存分配策略

一塊連續(xù)內(nèi)存，多個塊，從左到右依次查找，直到找到符合大小的一塊連續(xù)區(qū)域。
會有一個指針指向最左邊的空閑的塊，每次從這個指針查找的地方往右開始找，一旦最左邊的空閑塊位置發(fā)生了變動（更左邊的已經(jīng)分配的塊得到了釋放或者最左邊的空閑塊被分配），這個指針的值也要及時更新。

當(dāng)然，這種分配算法簡單有效，但是也沒法避免內(nèi)存碎片的問題

內(nèi)存釋放

調(diào)用釋放函數(shù)時直接設(shè)置對應(yīng)塊的標(biāo)識為free即可，
記得更新指向最左邊空閑塊的指針

回收過程（標(biāo)記-清除(mark-sweep)算法）

執(zhí)行回收的時機在文章開頭已經(jīng)介紹，這里闡述回收過程

uPy中實現(xiàn)自動垃圾回收使用了 mark-sweep 算法， 在gc_collect()函數(shù)中實現(xiàn)：

• 遍歷root objects找到所有能夠找到的有效塊（通過查找mp_state_ctx變量中保存的一系列變量，比如局部字典、全局字典、）

• 對這些找到的塊進行標(biāo)記，所有標(biāo)記為 head標(biāo)識的標(biāo)記為mark， 那些已經(jīng)無法找到的塊則仍然為head標(biāo)識

• 遍歷所有塊，對所有的標(biāo)記為mark的塊重新標(biāo)記為head，對標(biāo)記為head的塊則進行銷毀（標(biāo)記為free），這些標(biāo)記為head的塊是在上一步?jīng)]有找到的，也就是說內(nèi)存已經(jīng)是垃圾內(nèi)存了，所以直接銷毀

• 銷毀對象時檢查是否需要調(diào)用finaliser（檢查FTB標(biāo)記），即嘗試調(diào)用對象的__del__方法（如果存在的話），并且清除FTB標(biāo)記

注意到這里使用了遍歷這個詞，雖然實現(xiàn)起來簡單有效，但是注定效率不算高，所以寫對時間要求高的micropython程序需要注意回收的時機，能手動定期回收也不錯。(實際測試在 MaixPy 運行在400MHz的k210上collect()一次需要花費600us+

使用 GC 注意的地方

C層面使用 GC 注意

底層使用的變量被自動回收了（變量沒有鏈接到root objects，gc無法知道變量仍然有用），再使用時出錯

使用gc創(chuàng)建變量不能像平時使用malloc函數(shù)一樣使用， malloc只要創(chuàng)建了不free就會一直存在，但是gc通過alloc創(chuàng)建的變量如果沒有加入到gc遍歷時能遍歷到的變量中，gc就會認(rèn)為是垃圾，會回收，如果我們的c程序邏輯既沒有把它加入到gc，可以遍歷到的變量中，還把它當(dāng)成和普通一樣的malloc的變量使用，就會出現(xiàn)bug

因為 內(nèi)存不夠時會自動回收，那些沒有被引用的資源自然就會被釋放掉了，如果是修改 micropython的源碼時需要注意，比如在c層面創(chuàng)建了一個str（vstr_init），然后添加字符（vstr_add_strn），可能底層某個地方在使用這個變量，并且在某個時候會手動調(diào)用vstr_clear函數(shù)進行清除，但是由于這個變量沒有被python引用，在系統(tǒng)回收垃圾時有可能會將其回收掉，然后在后來的某個時間c在某個地方調(diào)用了vstr_clear去手動刪除字符串，這時會出錯，因為已經(jīng)被free過了

解決方法就是將這個變量被系統(tǒng)的變量引用一下
（比如創(chuàng)建一個變量鏈接到global變量中,或者當(dāng)成python層面的某個返回值，讓python層面有確定的使用范圍（比如img = image.Image()， 在這個方法中，c層面使用了gc分配內(nèi)存，python層面img變量引用了，只要img變量有效它就不會被自動回收），
或者干脆不要使用gc來創(chuàng)建，可以使用靜態(tài)數(shù)組或者其它不屬于gc管理的內(nèi)存。

可以看MaixPy的a21188b23fa1853b211c0ad65b2bfc4bef8343b2（fix str bug(for ide)) 提交

finaliser 使用時需要注意結(jié)構(gòu)體是否是一個合法的對象形式

創(chuàng)建對象如果需要使用finaliser（使用m_new_obj_with_finaliser函數(shù)創(chuàng)建對象），結(jié)構(gòu)體最開始一定要有mp_obj_base_t定義的變量（base），base變量下的type來指定變量的類型，否則會出現(xiàn)嚴(yán)重問題?。?！

注意觸發(fā)回收的時機

前面說了三種時機會觸發(fā)垃圾回收（collect)，所以寫python程序時需要注意自動回收會不會影響到程序的性能和穩(wěn)定性，以及需不需要自己手動調(diào)用collect來主動執(zhí)行回收程序

參考文章

• Micropython官方 wiki 介紹
• Python垃圾回收機制詳解
• python 中的垃圾回收之標(biāo)記清除