Linux之glibc記憶體管理malloc和free 轉載：http://blog.csdn.net/phenics/article/details/777053 1 前言 2 x86平台Linux程式的記憶體分布 3 Allocator 4 chuck的組織 5 空閑 chunk 容器 6 sbrk & mmap

轉載：http://blog.csdn.net/phenics/article/details/777053

1  前言

C語言提供了動态記憶體管理功能, 在C語言中, 程式員可以使用 malloc() 和 free() 函數顯式的配置設定和釋放記憶體. 關于 malloc() 和free() 函數, C語言标準隻是規定了它們需要實作的功能, 而沒有對實作方式有什麼限制, 這多少讓那些追根究底的人感到有些許迷茫, 比如對于 free() 函數, 它規定一旦一個記憶體區域被釋放掉, 那麼就不應該再對其進行任何引用, 任何對釋放區域的引用都會導緻不可預知的後果 (unperdictable effects). 那麼, 到底是什麼樣的不可預知後果呢? 這完全取決于記憶體配置設定器(memory allocator)使用的算法. 這篇文章試圖對 Linux glibc 提供的 allocator 的工作方式進行一些描述, 并希望可以解答上述類似的問題. 雖然這裡的描述局限于特定的平台, 但一般的事實是, 相同功能的軟體基本上都會采用相似的技術. 這裡所描述的原理也許在别的環境下會仍然有效. 另外還要強調的一點是, 本文隻是側重于一般原理的描述, 而不會過分糾纏于細節, 如果需要特定的細節知識, 請參考特定 allocator 的源代碼. 最後, 本文描述的硬體平台是 Intel 80x86, 其中涉及的有些原理和資料可能是平台相關的.

因為隻是草草看了 ptmalloc 的源代碼, 并做了一些實驗, 而沒有仔細分析代碼. 是以文章中的一些内容難免不實, 甚至為虛妄. 實在是因為水準有限, 并非存心妄自揣測, 來愚人耳目. 如果讀者發現其中有任何錯誤, 請來信告之, 并歡迎來信讨論. 另外, 文章中涉及一些阙值, 比如記憶體配置設定的位置, 以及 max_fast 大小等等, 會因具體的實作而異, 若與所述有出入, 請自己判斷原因.

2  x86平台Linux程式的記憶體分布

Linux 程式載入記憶體後, loader 會把可執行檔案中的各個段依次載入到從某一位址開始的空間中(載入位址取決于 link editor(ld), 在我的機器上是0x8048000, 即128M處). 如圖1所 示, 首先被載入的是 “.text” 段, 然後是 “.data” 段, 最後是 “.bss” 段. 這可以看作是程式的開始空間. 程式所能通路的最後的位址是0xbfffffff, 也就是到3G位址處, 3G以上的1G空間是核心使用的, 應用程式不可以直接通路. 應用程式的堆棧從最高位址處開始向下生長, “.bss”段與堆棧之間的空間是空閑的. 這個區域可以供使用者自由使用, 但是它在剛開始的時候并沒有映射到記憶體空間内, 是不可通路的. 在向核心請求配置設定該空間之前, 對這個空間的通路會導緻一個 “segmentation fault”. 使用者程式可以直接使用系統調用來管理這塊空間, 但更多的時候都是程式都是使用C語言提供的 malloc() 和 free() 函數來動态的申請和釋放記憶體.

圖 1:  Linux程式記憶體分布示意圖

3  Allocator

GNU Libc 的記憶體配置設定器( allocator ) — ptmalloc 起源于 Doug Lea 的 malloc (請參看[1]). ptmalloc 實作了 malloc() , free() 以及一組其它的函數. 以提供動态記憶體管理的支援. allocator 處在使用者程式和核心之間, 它響應使用者的配置設定請求, 向作業系統申請記憶體, 然後将其傳回給使用者程式, 為了保持高效的配置設定, allocator 一般都會預先配置設定一塊大于使用者請求的記憶體, 并通過某種算法管理這塊記憶體. 來滿足使用者的記憶體配置設定要求, 使用者 free 掉的記憶體也并不是立即就傳回給作業系統, 相反, allocator 會管理這些被 free 掉的空閑空間, 以應對使用者以後的記憶體配置設定要求. 也就是說, allocator 不但要管理已配置設定的記憶體塊, 還需要管理空閑的記憶體塊, 當響應使用者配置設定要求時, allocator 會首先在空閑空間中尋找一塊合适的記憶體給使用者, 在空閑空間中找不到的情況下才配置設定一塊新的記憶體. 為實作一個高效的 allocator, 需要考慮很多的因素. 比如, allocator 本身管理記憶體塊所占用的記憶體空間必須很小, 配置設定算法必須要足夠的快. Jonathan Bartlett 給出了一個簡單的 allocator 實作[2], 事先看看或許會對了解本文有所幫助. 另外插一句, Jonathan Bartlett 的書“Programming from Ground Up” 對想要了解 linux 彙編和工作方式的入門者是個不錯的選擇.

4  chuck的組織

不管記憶體是在哪裡被配置設定的, 用什麼方法配置設定, 使用者請求配置設定的空間在 ptmalloc 中都使用一個 chunk 來表示. 使用者調用 free() 函數釋放掉的記憶體也并不是立即就歸還給作業系統, 相反, 它們也會被表示為一個 chunk, ptmalloc 使用特定的資料結構來管理這些空閑的 chuck.

4.1  chuck

ptmalloc 在給使用者配置設定的空間的前後加上了一些控制資訊, 用這樣的方法來記錄配置設定的資訊, 以便完成配置設定和釋放工作. 一個使用中的chuck( 使用中, 就是指還沒有被free掉 ) 在記憶體中的樣子如圖2所示.

圖 2:   使用中的chuck

在圖中, chunk 指針指向一個 chunk 的開始, 一個chunk 中包含了使用者請求的記憶體區域和相關的控制資訊. 圖中的 mem 指針才是真正傳回給使用者的記憶體指針. chunk 的第二個域的最低一位為p, 它表示前一個塊是否在使用中, p為0則表示前一個 chunk 為空閑, 這時 chunk 的第一個域 prev_size 才有效, prev_size 表示前一個 chunk 的 size, 程式可以使用這個值來找到前一個 chunk 的開始. 當p為1時, 表示前一個 chunk 正在使用中, prev_size 無效, 程式也就不可以得到前一個 chunk 的大小. 而不能對前一個 chunk 進行任何操作. ptmalloc 配置設定的第一個塊總是将p設為1, 以防止程式引用到不存在的區域.

空閑 chunk 在記憶體中的結構如圖3所示,

圖 3:  空閑的thunk

當 chunk 空閑時, 原本是使用者資料區的地方存儲了兩個指針, 指針 fd 指向後一個空閑的 chunk, 而 bk 指向前一個空閑的 chunk, ptmalloc 通過這兩個指針将大小相近的 chunk 連成一個雙向連結清單. 而不同的 chunk 連結清單又是通過 bins 或者 fastbins 來組織的(bins 在第5.1節介紹, fastbins 在第5.2節介紹).

4.2  chunk中的空間複用

為了使得 chunk 所占用的空間最小, ptmalloc 使用了空間複用, 一個 chunk 或者正在被使用, 或者已經被 free 掉, 是以 chunk 的中的一些域可以在使用狀态和空閑狀态表示不同的意義, 來達到空間複用的效果. 空閑時, 一個 chunk 中至少要4個 

size_t

 大小的空間, 用來存儲 prev_size, size , fd 和 bk (見圖3所 示). 也就是16 bytes. chuck 的大小要 align 到8 bytes. 當一個 chunk 處于使用狀态時, 它的下一個 chunk 的 prev_size 域肯定是無效的. 是以實際上, 這個空間也可以被目前 chunk 使用. 這聽起來有點不可思議, 但确實是合理空間複用的例子. 故而實際上, 一個使用中的 chunk 的大小的計算公式應該是:

[xleftmargin=1cm] in_use_size = ( 使用者請求大小 + 8 - 4 ) align to 8 bytes 這裡加8是因為需要存儲 prev_size 和 size, 但又因為向下一個 chunk “借”了4個bytes, 是以要減去4. 最後, 因為空閑的 chunk 和使用中的 chunk 使用的是同一塊空間. 是以肯定要取其中最大者作為實際的配置設定空間. 即最終的配置設定空間 

chunk_size = max(in_use_size, 16)

. 這就是當使用者請求記憶體配置設定時, ptmalloc 實際需要配置設定的記憶體大小, 在後面的介紹中. 如果不是特别指明的地方, 指的都是這個經過轉換的實際需要配置設定的記憶體大小, 而不是使用者請求的記憶體配置設定大小.

5  空閑 chunk 容器

5.1  Bins

使用者 free 掉的記憶體并不是都會馬上歸還給系統, 相反, ptmalloc 會統一管理 heap 中的空閑的 chunk (關于heap, 請參照第6節中圖5), 當使用者進行下一次配置設定請求時, ptmalloc 會首先試圖在 heap 中空閑的 chunk 中挑選一塊給使用者, 這樣就避免了頻繁的系統調用, 降低了記憶體配置設定的開銷. ptmalloc 将 heap 中相似大小的 chunk 用雙向連結清單連結起來, 這樣的一個連結清單被稱為一個bin. ptmalloc 共維護了128個bin, 并使用一個數組來存儲這些 bin(如圖4).

圖 4:  bins 結構示意圖

數組中的前64個 bin 稱為 “exact bins”, “exact bins” 中的 chunk 具有相同的大小. 兩個相鄰的 bin 中的 chunk 大小相差8 bytes. “exact bins”中的 chunk 按照最近使用順序進行排列, 最後釋放的 chunk 被連結到連結清單的頭部, 而 allocation 是從尾部開始, 這樣, 每一個 chunk 都有相同的機會被 ptmalloc 選中. 後面的 bin 被稱作 “ordered bins”. “ordered bins” 中的每一個 bin 分别包含了一個給定範圍内的 chunk, 其中的 chunk 按大小序排列. 相同大小的 chunk 同樣按照最近使用順序排列. ptmalloc 使用 “smallest-first, best-fit” 原則在空閑 “ordered bins” 中查找合适的 chunk.

當空閑的 chunk 被連結到bin中的時候, ptmalloc 會把表示該 chunk 是否處于使用中的标志 p 設為0(注意, 這個标志實際上處在下一個 chunk 中), 同時 ptmalloc 還會檢查它前後的 chunk 是否也是空閑的, 如果是的話, ptmalloc 會首先把它們合并為一個大的 chunk, 然後将合并後的 chunk 放到 bin 中. 要注意的是, 并不是所有的 chunk 被釋放後就立即被放到bin中. ptmalloc 為了提高配置設定的速度, 會把一些小的的 chunk 先放到一個叫做 fastbin的容器内.

5.2  Fastbins

一般的情況是, 程式在運作時會經常需要配置設定和釋放一些較小的記憶體空間. 當 allocator 合并了相鄰的幾個小的 chunk 之後, 也許馬上就會有另一個小塊記憶體的請求, 這樣 allocator 又需要從大的空閑記憶體中分出一塊出來, 這樣無疑是比較低效的, 故而, ptmalloc 中在配置設定過程中引入了 fastbins, 不大于 

max_fast

 (72 bytes) 的 chunk 被 free 後, 首先會被放到 fastbins 中, fastbins 中的 chunk 并不改變它的使用标志p. 這樣也就無法将它們合并, 當需要給使用者配置設定的 chunk 小于或等于 

max_fast

 時, ptmalloc 首先會在 fastbins 中查找相應的空閑塊(具體的配置設定算法請參考第7節), 然後才會去查找 bins 中的空間 chunk. 在某個特定的時候, ptmalloc 會周遊 fastbins 中的 chunk, 将相鄰的空閑 chunk 進行合并, 并将合并後的 chunk 放到 bins 中去.

5.3  Unsorted Bins

如果被使用者釋放的 chunk 大于 max_fast, 則按上面的叙述它應該會被放到 bins中. 但實際上, ptmalloc 還引入了一個稱為 “unsorted bins”的隊列. 這些大于 max_fast 的chunk 首先會被放到 “unsorted bins” 隊列中, 在進行 malloc 操作的時候, 如果在 fastbins 中沒有找到合适的 chunk, 則 ptmalloc 會先在 “unsorted bins”中查找合适的空閑 chunk, 然後才查找 bins. 如果 “unsorted bins” 不能滿足配置設定要求. malloc 便會将 “unsorted bins” 中的 chunk 放到 bins 中, 然後再在 bins 中繼續進行查找和配置設定過程. 從這個過程可以看出來, “unsorted bins”可以看做是 bins 的一個緩沖區, 增加它隻是為了加快配置設定的速度, 忽略它對我們了解 ptmalloc 沒有太大的影響, 在本文中, 這個過程就不被考慮了.

5.4  例外的 chunk

并不是所有的 chunk 都按照上面的方式來組織, 實際上, 有兩種例外情況.

top chunk

在前面一直提到, ptmalloc 會預先配置設定一塊較大的空閑記憶體(也就是所為的 heap), 而通過管理這塊記憶體來響應使用者的需求, 因為記憶體是按位址從低向高進行配置設定的, 在空閑記憶體的最高處, 必然存在着一塊空閑 chunk, 叫做 “top chunk”. 當 bins 和 fastbins 都不能滿足配置設定需要的時候, ptmalloc 會設法在 “top chunk” 中分出一塊記憶體給使用者, 如果 “top chunk” 本身不夠大, 則 ptmalloc 會适當的增加它的大小(也就增加了 heap 的大小). 以滿足配置設定的需要, 實際上, “top chunk” 在配置設定時總是在 ‘fastbins 和 bins 之後被考慮, 是以, 不論 “top chunk” 有多大, 它都不會被放到 fastbins 或者是 bins 中.

mmaped chunk

當需要配置設定的 chunk 足夠大, 而且 fastbins 和 bins 都不能滿足要求, 甚至 “top chunk” 本身也不能滿足配置設定需求時, ptmalloc 會使用 mmap 來直接使用記憶體映射來将頁映射到程序空間(具體的情況, 請參考第 6節). 這樣配置設定的 chunk 在被 free 時将直接解除映射, 于是就将記憶體歸還給了系統, 再次對這樣的記憶體區的引用将導緻一個 “segmentation fault” 錯誤. 這樣的 chunk 也不會包含在任何 bin 中.

6  sbrk & mmap

ptmalloc 使用兩種方法向記憶體索取記憶體空間: sbrk 和 mmap. 它們用于不同的場合.

6.1  sbrk

如圖5所示,

圖 5:  使用 sbrk 和 mmap 配置設定記憶體示意圖

.bss 段之上的這塊配置設定給使用者程式的空間被稱為 heap (堆). start_brk 指向 heap 的開始, 而 brk 指向 heap 的頂部. 可以使用系統調用 brk 和 sbrk 來增加辨別 heap 頂部的 brk 值, 進而線性的增加配置設定給使用者的 heap 空間. 在使用malloc之前, brk 的值等于start_brk, 也就是說 heap 大小為0. ptmalloc 在開始時, 若請求的空間小于

DEFAULT_MMAP_THRESHOLD

 (128K bytes)時, ptmalloc 會調用sbrk增加一塊大小為 

( 128 KB + chunk_size ) align 4K 

的空間作為heap. 這就是前面所說的 ptmalloc 所維護的配置設定空間, 當使用者請求記憶體配置設定時, 首先會在這個區域内找一塊合适的 chunk 給使用者. 當使用者釋放了 heap 中的 chunk 時, ptmalloc 又會使用 fastbins 和 bins 來組織空閑 chunk. 以備使用者的下一次配置設定(具體的配置設定過程見第7節). 若需要配置設定的 chunk 大小小于 

DEFAULT_MMAP_THRESHOLD

, 而 heap 空間又不夠, 則此時 ptmalloc 會通過 sbrk 調用來增加 heap 值, 也就是增加 “top chunk”的大小, 每次 heap 增加的值都會 align 到4k bytes.

6.2  mmap

當使用者的請求超過 

DEFAULT_MMAP_THRESHOLD

 , 并且使用 sbrk 配置設定失敗的時候, ptmalloc 會嘗試使用 mmap 直接映射一塊記憶體到程序記憶體空間(我機器上是在0x40159000位址處). 使用 mmap 直接映射的 chunk 在釋放時直接解除映射, 而不再屬于程序的記憶體空間. 任何對該記憶體的通路都會産生段錯誤. 而在 heap 中配置設定的空間則可能會留在程序記憶體空間内, 還可以再次引用(當然是很危險的).

7  malloc()

ptmalloc 的響應使用者記憶體配置設定要求的具體步驟為:

1. 擷取配置設定區的鎖, ptmalloc 對 Doug Lea malloc 的主要擴充便是增加了線程支援. 為了防止多個線程同時通路同一個配置設定區, 在進行配置設定之前需要取得配置設定區域的鎖, 如果主配置設定區域的鎖不能得到, 那麼會 ptmalloc 會建立一個新的配置設定區域供目前線程使用.
2. 将使用者的請求大小轉換為實際需要配置設定的空間大小(見第4.2節的相關介紹).
3. 判斷所需配置設定 chunk 的大小是否滿足 

   chunk_size <= max_fast 

   (max_fast 預設為 72 bytes) , 如果是的話, 則轉下一步, 否則跳到第5步.
4. 首先嘗試在 fastbins 中摘取一個所需大小的 chunk 配置設定給使用者. 如果可以找到, 則配置設定結束. 否則轉到下一步.
5. 判斷所需大小是否處在 “exact bins” 中, 即判斷 

   chunk_size

   512 bytes 

   是否成立(見圖4). 如果 chunk 大小處在 “exact bins”中, 則轉下一步, 否則轉到第6步.
6. 根據所需配置設定的 chunk 的大小, 找到具體所在的 “exact bins”, 并從該 bin 的尾部摘取一塊恰好滿足大小的 chunk. 若成功, 則配置設定結束, 否則, 轉到下一步.
7. 到了這一步, 說明需要配置設定的是一塊大的記憶體, 或者, “exact bins” 中找不到合适的 chunk. 于是, ptmalloc 首先會周遊 fastbins 中的 chunk , 将相鄰的 chunk 進行合并, 并連結到 bins 中, 然後從 “sorted bins” 中按照 “smallest-first, best-fit” 原則, 找一塊合适的 chunk, 從中劃分一塊所需大小的chunk, 并将剩下的部分連結回到 bins 中. 若操作成功, 則配置設定結束, 否則轉到下一步.
8. 如果搜尋 fastbins 和 bins 都沒有找到合适的 chunk, 那麼就需要操作 top chunk 來進行配置設定了. 判斷 top chunk 大小是否滿足所需 chunk 的大小, 如果是, 則從 top chunk 中分出一塊來. 否則轉到下一步.
9. 到了這一步, 說明 top chunk 也不能滿足配置設定要求, 是以, 于是就有了兩個選擇: 調用 sbrk, 增加 top chunk 大小; 或者使用 mmap 來直接配置設定. 在這裡, 需要依靠 chunk 的大小來決定到底使用哪種方法. 判斷所需配置設定的 chunk 大小是否大于等于 

   DEFAULT_MMAP_THRESHOLD

    (128KB), 如果是的話, 則轉下一步, 調用 mmap 配置設定, 否則跳到第11步, 使用 sbrk 來增加 top chunk 的大小.
10. 使用 mmap 系統調用在大約 0x40159000 (大約為1G) 位址處為程式的記憶體空間映射一塊 

    chunk_size align 4kB

     大小的空間. 然後将記憶體指針傳回給使用者.
11. 判斷是否為第一次調用 malloc, 若是, 則需要進行一次初始化工作, 配置設定一塊大小為 

    (chunk_size + 128K) align 4KB

     大小的空間作為初始的 heap. 若已經初始化過了, 則調用 sbrk 增加 heap 空間, 使之滿足配置設定需求, 并将記憶體指針傳回給使用者.

總結一下: 根據使用者請求配置設定的記憶體的大小, ptmalloc 有可能會在兩個地方為使用者配置設定記憶體空間. 在第一次配置設定記憶體時, brk 值等于 start_brk, 是以實際上 heap 大小為0, top chunk 大小也是0. 這時, 如果不增加 heap 大小, 就不能滿足任何配置設定要求. 是以, 若使用者的請求小于 

DEFAULT_MMAP_THRESHOLD

, 則 ptmalloc 會初始化heap. 然後在 heap 中配置設定空間給使用者, 以後的配置設定就基于這個 heap 進行. 若第一次使用者的請求就大于

DEFAULT_MMAP_THRESHOLD

, 則 ptmalloc 直接使用 mmap 配置設定一塊給使用者, 而 heap 也就沒有被初始化, 直到使用者第一次請求小于 

DEFAULT_MMAP_THRESHOLD

的記憶體配置設定. 第一次以後的配置設定就比較複雜了, 簡單說來, ptmalloc 首先會查找 fastbins, 如果不能找到比對的 chunk, 則查找 “exact bins”. 若還是不行, 則查找 “sorted bins”. 在 fastbins 和 “exact bins” 中的查找都需要精确比對, 而在sorted bins 中查找時, 則遵循 “smallest-first, best-fit” 的原則, 不需要精确比對. 若以上方法都失敗了, 則 ptmalloc 會考慮使用 top chunk. 若top chunk 也不能滿足配置設定要求. 而且所需 chunk 大小大于 

DEFAULT_MMAP_THRESHOLD

 , 則使用 mmap 進行配置設定. 否則增加 heap. 增大 top chunk. 以滿足配置設定要求.

8  free()

free() 函數接受一個指向配置設定區域的指針作為參數, 釋放該指針所指向的 chunk. 而具體的釋放方法則看該 chunk 所處的位置和該 chunk 的大小. free()函數的工作步驟如下:

1. free() 函數同樣首先需要擷取配置設定區的鎖, 來保證線程安全.
2. 判斷傳入的指針是否為0, 如果為0, 則什麼都不做, 直接return. 否則轉下一步:
3. 判斷所需釋放的 chunk 是否為 mmaped chunk, 如果是, 則直接釋放 mmaped chunk, 解除記憶體空間映射. 該空間不再有效. 釋放完成. 否則跳到下一步.
4. 判斷 chunk 的大小和所處的位置, 若 

   chunk_size <= max_fast 

   , 并且 chunk 并不位于 heap 的頂部, 也就是說并不與 top chunk 相鄰, 則轉到下一步, 否則跳到第6步. (因為與 top chunk 相鄰的小 chunk 也和 top chunk 進行合并, 是以這裡不僅需要判斷大小, 還需要判斷相鄰情況.)
5. 将 chunk 放到 fastbins 中, chunk 放入到 fastbins 中時, 并不設定該 chunk 使用位. 也不與相鄰的 chunk 進行合并. 隻是放進去, 如此而已. 做實驗的結果還發現ptmalloc 放入 fastbins 中的 chunk 中的使用者資料去全置為 0. 但是在源代碼中找不到相關的代碼. 這一步做完之後釋放便結束了, 程式從 free() 函數中傳回..
6. 判斷前一個 chunk 是否處在使用中, 如果前一個塊也是空閑塊, 則合并. 并轉下一步.
7. 判斷目前釋放 chunk 的下一個塊是否為 top chunk, 如果是, 則轉第9步, 否則轉下一步.
8. 判斷下一個 chunk 是否處在使用中, 如果下一個 chunk 也是空閑的. 則合并, 并将合并後的 chunk 放到 bins 中. 注意, 這裡在合并的過程中, 要更新 chunk 的大小, 以反映合并後的 chunk 的大小. 并轉到第10步.
9. 如果執行到這一步, 說明釋放了一個與 top chunk 相鄰的chunk. 則無論它有多大, 都将它與 top chunk 合并, 并更新 top chunk 的大小等資訊. 轉下一步.
10. 判斷合并後的 chunk 的大小是否大于 

    FASTBIN_CONSOLIDATION_THRESHOLD

    , 如果是的話, 則會觸發進行 fastbins 的合并操作, fastbins 中的 chunk 将被周遊, 并于相鄰的空閑 chunk 進行合并, 合并後的 chunk 會被放到 bins 中. fastbins 将變為空, 操作完成之後轉下一步.
11. 判斷 top chunk 的大小是否大于 

    DEFAULT_TRIM_THERESHOLD

    . 如果是的話, 則會試圖歸還 top chunk 中的一部分給作業系統. 但是最先配置設定的128KB的空間是不會歸還. ptmalloc 會一直控制這部分記憶體. 用于響應使用者的配置設定請求. 做完這一步之後, 釋放結束, 從 free 函數退出.

參考文獻：http://gee.cs.oswego.edu/dl/html/malloc.html.