v37.01 鴻蒙核心原始碼分析(TLFS演算法篇) | 圖表解讀TLFS原理 | 百篇部落格分析OpenHarmony原始碼

語言: CN / TW / HK

本篇關鍵詞:TLFS 、記憶體池 、malloc、free

記憶體管理相關篇為:

動態分配

本篇開始說一個耳朵聽起老繭的概念 動態分配,將分成上下兩篇,本篇為上篇,看完能快速理解下篇鴻蒙核心原始碼對動態記憶體的具體實現。

  • 鴻蒙核心原始碼分析(TLFS演算法) 結合圖表從理論視角說清楚 TLFS 演算法
  • 鴻蒙核心原始碼分析(記憶體池管理) 結合原始碼說清楚鴻蒙核心動態記憶體池實現過程,個人認為這部分程式碼很精彩,簡潔高效,尤其對空閒節點和已使用節點的實現令人稱奇。

TLFS 原理

TLSF(Two-Level Segregate Fit) 是一種用於實時作業系統的記憶體分配演算法,用兩級結構對空閒塊按大小進行劃分,採用兩級連結串列/索引的方式來加快查詢。詳細可檢視 >> TLSF 論文

把上圖看懂基本能明白 TLFS 的原理,請嘗試自己先理解一遍再看本篇。

解讀

  • 為方便理解 ,將上圖做成(表一),中間過程請檢視圖表變化

    步驟 操作 一級點陣圖 (FL_bitmap) 二級點陣圖 (SL_bitmaps[]) 空閒連結串列(大小-虛擬地址)
    第一步 初始階段 0011 00000000<br>00000000<br>00100000<br>00000010 109b(0x5625) --> 104b(0x6838) <br> 38b(0x3457) --> 36b(0xed31)
  • 右邊為第一級連結串列 First List (簡稱fl)。將空閒記憶體塊的大小根據2的冪進行分類,如(32、64、128、...), 這跟夥伴演算法很類似,夥伴演算法是實體記憶體的分配演算法,這樣做的好處是防止外部碎片化,是否空閒用點陣圖標識 FL_bitmap | 一維陣列0011代表 [32-64]、[64-128]這個區間有記憶體可以申請,例如: malloc(37) 時,查到在區間[32-64]中,為 1代表本次可能可以申請到記憶體,但具體行不行得進入第二級檢視。

  • 中間為第二級連結串列 Second List (簡稱sl)。第二層連結串列在第一層的基礎上,按照一定的間隔,線性分段,圖中將其分成 8等份,對於[32-64]來說 1/84,對於[64 - 128]來說 1/88,可以確定的是等份也是2的倍數,同樣是否空閒用點陣圖標識SL_bitmaps[] | 二維陣列 ,每個bit代表是否空閒,圖中代表 [36 - 39]有記憶體可供分配,再檢視其空閒連結串列發現真正可供分配的空間有兩塊,38 和 36,自然將 38malloc(37) 返回,此時空閒連結串列中還剩36節點 ,所以 一二級點陣圖資料不會有任何的變化。

  • 左邊為空閒連結串列塊,上面掛flsl都為1時的空閒記憶體塊,塊大小為區間範圍值,圖中有兩個空閒塊 38b --> 36b109b --> 104b,在實際執行過程往往出現同樣大小的記憶體塊例如38b --> 36b--> 36b

申請過程

用二次申請說明詳細過程

  • malloc(37) ,發現值在區間[32-64]並對應fl的點陣圖為1,說明sl中肯定會有一個1,但並不能保證能申請到。得細看第二步sl發現區間[36 - 39]的點陣圖為1,說明空閒連結串列中肯定會有一塊記憶體,,但也不能保證大小適合37。再看最後一步,發現有兩塊記憶體38b --> 36b,只有38b符合,於是**malloc(37)**的結果是獲得了一塊大小38b的記憶體塊,相差的一個 1b稱為內部碎片,這種碎片無法避免。將(表一)更新為(表二)

    步驟 操作 一級點陣圖 (FL_bitmap) 二級點陣圖 (SL_bitmaps[]) 空閒連結串列(大小-虛擬地址)
    第一步 初始階段 0011 00000000<br>00000000<br>00100000<br>00000010 109b(0x5625) --> 104b(0x6838) <br> 38b(0x3457) --> 36b(0xed31)
    第二步 malloc(37)<br>返回地址0x3457 0011 00000000<br>00000000<br>00100000<br>00000010 109b(0x5625) --> 104b(0x6838) <br> 36b(0xed31)
  • malloc(50),同樣落在[32-64]檢視fl的點陣圖為1,檢視第二步sl只有[36 - 39]的點陣圖為1,而 50 > 39,不能滿足所以沒必要看第三步,得返回第一步往上走發現[64-128]fl的點陣圖為150 < 64 說明 malloc(50) 這次肯定能申請到記憶體了,檢視[64-128]對應的sl發現[104-111]的點陣圖為1,到第三步發現有109b --> 104b兩塊,選擇其中更小104b的塊切割成5054兩小塊,此時要對54處理掛入空閒連結串列,54處於fl = [32-64]sl = [52-55]區間,地址為: 0x6838+50=0x686A 。所以將[52-55]區間點陣圖置為1,並掛入空閒連結串列。將(表二)更新為(表三)

    步驟 操作 一級點陣圖 (FL_bitmap) 二級點陣圖 (SL_bitmaps[]) 空閒連結串列(大小-虛擬地址)
    第一步 初始階段 0011 00000000<br>00000000<br>00100000<br>00000010 109b(0x5625) --> 104b(0x6838) <br> 38b(0x3457) --> 36b(0xed31)
    第二步 malloc(37)<br>返回地址0x3457 0011 00000000<br>00000000<br>00100000<br>00000010 109b(0x5625) --> 104b(0x6838) <br> 36b(0xed31)
    第三步 malloc(50)<br>返回地址0x6838 0011 00000000<br>00000000<br>00100000<br>00100010 109b(0x5625) <br> 54b(0x686A) <br> 36b(0xed31)

    注意此時[32-64]的二級點陣圖變成了 00100010 有兩個1

釋放過程

同樣用二次釋放說明詳細過程

  • free(0x3457) 從地址可知正是上面的 malloc(37)的記憶體,與分配切割相對應的是釋放有合併的步驟,但malloc(37)雖然申請是37,但其實核心記錄的記憶體塊大小是38,所以會找尋地址為 0x3457 + 38 = 0x348F 的地址是否也處於空閒,如果是則合併,由表三可知 並沒有 0x348F的空閒塊將,而38位於fl = [32-64]sl = [36-39]區間,所以掛回該空閒連結串列等待後續再分配使用,由此(表三)更新為(表四)

    步驟 操作 一級點陣圖 (FL_bitmap) 二級點陣圖 (SL_bitmaps[]) 空閒連結串列(大小-虛擬地址)
    第一步 初始階段 0011 00000000<br>00000000<br>00100000<br>00000010 109b(0x5625) --> 104b(0x6838) <br> 38b(0x3457) --> 36b(0xed31)
    第二步 malloc(37)<br>返回地址0x3457 0011 00000000<br>00000000<br>00100000<br>00000010 109b(0x5625) --> 104b(0x6838) <br> 36b(0xed31)
    第三步 malloc(50)<br>返回地址0x6838 0011 00000000<br>00000000<br>00100000<br>00100010 109b(0x5625) <br> 54b(0x686A) <br> 36b(0xed31)
    第四步 free(0x3457) 0011 00000000<br>00000000<br>00100000<br>00100010 109b(0x5625)<br> 54b(0x686A) <br> 38b(0x3457) --> 36b(0xed31)
  • free(0x5610) 這裡假設核心記錄該記憶體塊大小為 0x15,歸還的同時會找尋0x5610 + 0x15 = 0x5625 是否有空閒塊,發現sl = [104-111]有一塊109b空閒塊,兩塊合成一塊大小為 109 + 0x15 = 109 + 21 = 130,位於fl = [128-255]sl = [128-143]區間,由此(表四)再更新為(表五)

    步驟 操作 一級點陣圖 (FL_bitmap) 二級點陣圖 (SL_bitmaps[]) 空閒連結串列(大小-虛擬地址)
    第一步 初始階段 0011 00000000<br>00000000<br>00100000<br>00000010 109b(0x5625) --> 104b(0x6838) <br> 38b(0x3457) --> 36b(0xed31)
    第二步 malloc(37)<br>返回地址0x3457 0011 00000000<br>00000000<br>00100000<br>00000010 109b(0x5625) --> 104b(0x6838) <br> 36b(0xed31)
    第三步 malloc(50)<br>返回地址0x6838 0011 00000000<br>00000000<br>00100000<br>00100010 109b(0x5625) <br> 54b(0x686A) <br> 36b(0xed31)
    第四步 free(0x3457) 0011 00000000<br>00000000<br>00100000<br>00100010 109b(0x5625)<br> 54b(0x686A) <br> 38b(0x3457) --> 36b(0xed31)
    第五步 free(0x5610) 0101 00000000<br>00000001<br>00000000<br>00100010 130b(0x5610) <br> 54b(0x686A) <br> 38b(0x3457) --> 36b(0xed31)

總結

TLSF(Two-Level Segregate Fit) 有兩大優點:

  • 實時性,執行速度快,只需查詢點陣圖就能知道結果,最多查詢兩次一級點陣圖,時間複雜度為O(1)。
  • 碎片少,浪費少,利用率高,因採用2次冪的方式,切割和合並非常的方便,很少出現外部碎片。

真正的鴻蒙記憶體動態分配實現過程比這些要複雜些,但有了本文演算法基礎做鋪墊看原始碼實現會容易很多。

百文說核心 | 抓住主脈絡

  • 百文相當於摸出核心的肌肉和器官系統,讓人開始豐滿有立體感,因是直接從註釋原始碼起步,在加註釋過程中,每每有心得處就整理,慢慢形成了以下文章。內容立足原始碼,常以生活場景打比方儘可能多的將核心知識點置入某種場景,具有畫面感,容易理解記憶。說別人能聽得懂的話很重要! 百篇部落格絕不是百度教條式的在說一堆詰屈聱牙的概念,那沒什麼意思。更希望讓核心變得栩栩如生,倍感親切。
  • 與程式碼需不斷debug一樣,文章內容會存在不少錯漏之處,請多包涵,但會反覆修正,持續更新,v**.xx 代表文章序號和修改的次數,精雕細琢,言簡意賅,力求打造精品內容。
  • 百文在 < 鴻蒙研究站 | 開源中國 | 部落格園 | 51cto | csdn | 知乎 | 掘金 > 站點發布,鴻蒙研究站 | weharmonyos 中回覆 百文 可方便閱讀。

按功能模組:

百萬注原始碼 | 處處扣細節

  • 百萬漢字註解核心目的是要看清楚其毛細血管,細胞結構,等於在拿放大鏡看核心。核心並不神祕,帶著問題去原始碼中找答案是很容易上癮的,你會發現很多文章對一些問題的解讀是錯誤的,或者說不深刻難以自圓其說,你會慢慢形成自己新的解讀,而新的解讀又會碰到新的問題,如此層層遞進,滾滾向前,拿著放大鏡根本不願意放手。

  • < gitee | github | coding | gitcode > 四大碼倉推送 | 同步官方原始碼,鴻蒙研究站 | weharmonyos 中回覆 百萬 可方便閱讀。

據說喜歡點贊分享的,後來都成了大神。:)

「其他文章」