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

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

在 CPython 中

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

Micropython GC

官方 wiki 介紹

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

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

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

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

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

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

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

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

其中 ATB 標(biāo)記每個(gè)塊的狀態(tài)，包括 free， head（多個(gè)連續(xù)分配的塊的開(kāi)始（頭））， tail（多個(gè)連續(xù)分配的塊的除了頭部塊以外的塊）， mark（標(biāo)記了的頭部，在回收時(shí)（collect）中才會(huì)標(biāo)記） 幾種狀態(tài)，每?jī)晌槐硎疽粋€(gè)block狀態(tài)，即每個(gè)字節(jié)可以表示4個(gè)block的狀態(tài)

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

名詞

• block： 塊，分配的最小單位，比如設(shè)置為16或者32字節(jié)。
• finaliser：這里可理解成析構(gòu)，調(diào)用 類(lèi)的__del__方法，（mpy目前(2019.5)還沒(méi)有實(shí)現(xiàn)調(diào)用用戶(hù)類(lèi)的__del__方法）
• ATB: alloc table，標(biāo)記每個(gè)block的狀態(tài)，包括 free， head（多個(gè)連續(xù)分配的塊的開(kāi)始（頭））， tail（多個(gè)連續(xù)分配的塊的除了頭部塊以外的塊）， mark（標(biāo)記了的頭部） 幾種狀態(tài)，每?jī)晌槐硎疽粋€(gè)block狀態(tài)，即每個(gè)字節(jié)可以表示4個(gè)block的狀態(tài)
• FTB: finaliser table標(biāo)記是否使用 finaliser，每位表示一個(gè)block是否使用finaliser，即每個(gè)字節(jié)表示8個(gè)block是否使用finaliser
• pool: 實(shí)際分配給用戶(hù)使用的空間（alloc 返回的地址），也就是數(shù)據(jù)實(shí)際儲(chǔ)存的位置，最小單位是塊
• (block) chain: （塊）鏈，分配內(nèi)存的最小單位是塊，比如一個(gè)塊32字節(jié)，如果用戶(hù)程序需要分配36個(gè)字節(jié)，則直接分配2個(gè)塊即64字節(jié)，這兩個(gè)塊稱(chēng)為一個(gè)塊鏈（chain），我們標(biāo)記第一個(gè)塊為頭，后面的所有塊為尾(注意不是最后一個(gè)，是除了頭的所有塊）
• reachable object： 可達(dá)的對(duì)象，即可以通過(guò)變量引用引用得到的對(duì)象
• root object： 根節(jié)點(diǎn)對(duì)象，主要是指 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ū)域用來(lái)內(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)存對(duì)齊

從GC分配空間

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

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

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

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

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

data_t* p = m_new(data_t, 1);

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

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來(lái)創(chuàng)建對(duì)象，但是結(jié)構(gòu)體里面第一個(gè)成員又不是base，則最后在調(diào)用finaliser時(shí)就會(huì)出現(xiàn)致命的問(wèn)題，可能會(huì)導(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ù)中，即用戶(hù)通過(guò)i2c = machine.I2C()來(lái)創(chuàng)建對(duì)象的時(shí)候調(diào)用的函數(shù)中，會(huì)創(chuàng)建一個(gè)machine_hard_i2c_obj_t的對(duì)象，如果不使用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);

這樣在對(duì)象銷(xiāo)毀時(shí)不會(huì)調(diào)用__del__方法，如果需要自動(dòng)調(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)存，多個(gè)塊，從左到右依次查找，直到找到符合大小的一塊連續(xù)區(qū)域。
會(huì)有一個(gè)指針指向最左邊的空閑的塊，每次從這個(gè)指針查找的地方往右開(kāi)始找，一旦最左邊的空閑塊位置發(fā)生了變動(dòng)（更左邊的已經(jīng)分配的塊得到了釋放或者最左邊的空閑塊被分配），這個(gè)指針的值也要及時(shí)更新。

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

內(nèi)存釋放

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

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

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

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

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

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

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

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

注意到這里使用了遍歷這個(gè)詞，雖然實(shí)現(xiàn)起來(lái)簡(jiǎn)單有效，但是注定效率不算高，所以寫(xiě)對(duì)時(shí)間要求高的micropython程序需要注意回收的時(shí)機(jī)，能手動(dòng)定期回收也不錯(cuò)。(實(shí)際測(cè)試在 MaixPy 運(yùn)行在400MHz的k210上collect()一次需要花費(fèi)600us+

使用 GC 注意的地方

C層面使用 GC 注意

底層使用的變量被自動(dòng)回收了（變量沒(méi)有鏈接到root objects，gc無(wú)法知道變量仍然有用），再使用時(shí)出錯(cuò)

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

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

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

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

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

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

注意觸發(fā)回收的時(shí)機(jī)

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

參考文章

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