glibc的malloc--更多的改進

前面說過glibc實作了malloc，它實作linux系統的堆管理，在linux中沒有專有的所謂的API，所有的調用幾乎都以c庫為根本，是以glibc顯得尤為重要，glibc的實作抛開自己的獨特政策不說它和windows的實作是一樣的，都是維護一個全局的連結清單，然後每一個連結清單元素由固定大小記憶體塊或者不固定大小的記憶體塊組成，和windows不同的是，glibc維護了不止一個不定長的記憶體塊連結清單，而是好幾個，每一個這種連結清單負責一個大小範圍，這種做法有效減少了配置設定大記憶體時的周遊開銷，類似于哈希的方式，将很大的範圍的資料散列到有限的幾個小的範圍内而不是所有資料都放在一起，雖然最終還是要在小的範圍内查找，但是最起碼省去了很多的開銷，如果隻有一個不定長連結清單那麼就要全部周遊，如果分成3個，就省去了2/3的開銷，總之這個政策十分類似于散列。glibc另外的政策就是不止維護一類空閑連結清單，而是另外再維護一個緩沖連結清單和一個高速緩沖連結清單，在配置設定的時候首先在高速緩存中查找，失敗之後再在空閑連結清單查找，如果找到的記憶體塊比較大，那麼将切割之後的剩餘記憶體塊插入到緩存連結清單，如果空閑連結清單查找失敗那麼就往緩存連結清單中查找，這麼查找有什麼依據嗎？實際上是有的，正是這個方式讓glibc有了自己的政策。

這種依據在free的時候展現。如果能合并在堆頂，也就是能和堆頂的空閑元素合并，那麼就合并，因為堆的縮減僅僅在堆頂的空閑元素達到一定量的時候才會進行，是以為了盡快将記憶體歸還作業系統，盡量優先考慮堆頂的釋放，但是如果不能合并，比如它和堆頂根本就沒有相鄰，那麼如果該釋放的塊大小小于80位元組，那麼就直接将之挂在高速緩存中，為了防止别的塊和它合并是以并不更改使用位，這裡可以看到，glibc實際上為小于80位元組的小記憶體塊維護了一個高速的記憶體池，如果有小塊記憶體需求，直接從此池中拿走一個即可，隻需要從高速緩存摘除之并不需要修改使用位，因為高速緩存中的元素的使用位均為1，這個高速緩存在有大記憶體塊配置設定需求并且幾個配置設定政策都失敗的時候會被回收，回收進空閑連結清單的過程涉及到相鄰塊的合并，合并之後就有可能滿足稍微大一些的記憶體配置設定需求，這裡為何将界限定位為80個位元組呢？實際上是一個經驗值，那麼介于80位元組和128k位元組之間的記憶體塊在釋放的時候要将使用位設定為0，然後試圖和相鄰塊合并，然後挂入緩存連結清單。

下面的這段話摘自于一篇文章，比較詳細的闡述了glibc的記憶體配置設定和釋放的過程，前提是配置設定大小小于128k：

1.堆是通過brk的方式來增長或壓縮的，如果在現有的堆中不能找到合适的chunk，會通過增長堆的方式來滿足配置設定，如果堆頂的空閑塊超過一定的閥值會收縮堆，是以隻要堆頂的空間沒釋放，堆是一直不會收縮的。

2.堆中的配置設定資訊是通過兩個方式來記錄。第一．是通過chunk的頭，chunk中的頭一個字是記錄前一個chunk的大小，第二個字是記錄目前chunk的大小和一些标志位，從第三個字開始是要使用的記憶體。是以通過記憶體位址可以找到chunk，通過chunk也可以找到記憶體位址。還可以找到相鄰的下一個chunk，和相鄰的前一個chunk。一個堆完全是由n個chunk組成。第二．是由3種隊列記錄，隻用空閑chunk才會出現在隊列中，使用的chunk不會出現在隊列中。如果記憶體塊是空閑的它會挂到其中一個隊列中，它是通過記憶體複用的方式，使用空閑chunk的第3個字和第4個字當作它的前鍊和後鍊（變長塊是第5個字和第6個字），省的再配置設定空間給它。第一種隊列是bins，bins有128個隊列，前64個隊列是定長的，每隔8個位元組大小的塊配置設定在一個隊列，後面的64個隊列是不定長的，就是在一個範圍長度的都配置設定在一個隊列中。所有長度小于512位元組（大約）的都配置設定在定長的隊列中。後面的64個隊列是變長的隊列，每個隊列中的chunk都是從小到大排列的。第二種隊列是unsort隊列（隻有一個隊列），（是一個緩沖）所有free下來的如果要進入bins隊列中都要經過unsort隊列。第三種隊列是fastbins，大約有10個定長隊列，（是一個高速緩沖）所有free下來的并且長度是小于80的chunk就會進入這種隊列中。進入此隊列的chunk在free的時候并不修改使用位，目的是為了避免被相鄰的塊合并掉。

3.malloc的步驟

-->先在fastbins中找，如果能找到，從隊列中取下後（不需要再置使用位為1了）立刻傳回。

-->判斷需求的塊是否在小箱子（bins的前64個bin）範圍，如果在小箱子的範圍，并且剛好有需求的塊，則直接傳回記憶體位址；如果範圍在大箱子（bins的後64個bin）裡，則觸發consolidate。（因為在大箱子找一般都要切割，是以要優先合并，避免過多碎片）

-->然後在unsort中取出一個chunk，如果能找到剛好和想要的chunk相同大小的chunk，立刻傳回，如果不是想要chunk大小的chunk，就把他插入到bins對應的隊列中去。轉3，直到清空，或者一次循環了10000次。

-->然後才在bins中找，找到一個最小的能符合需求的chunk從隊列中取下，如果剩下的大小還能建一個chunk，就把chunk分成兩個部分，把剩下的chunk插入到unsort隊列中去，把chunk的記憶體位址傳回。

-->在topchunk（是堆頂的一個chunk，不會放到任何一個隊列裡的）找，如果能切出符合要求的，把剩下的一部分當作topchunk，然後傳回記憶體位址。

-->如果fastbins不為空，觸發consolidate即把所有的fanbins清空（是把fanbins的使用位置0，把相鄰的塊合并起來，然後挂到unsort隊列中去），然後繼續第3步。

-->還找不到話就調用sysalloc，其實就是增長堆了。然後傳回記憶體位址。

4.free的步驟

-->如果和topchunk相鄰，直接和topchunk合并，不會放到其他的空閑隊列中去。

-->如果釋放的大小小于80位元組，就把它挂到fastbins中去，使用位仍然為1，當然更不會去合并相鄰塊。

-->如果釋放塊大小介于80-128k，把chunk的使用位置成0，然後試圖合并相鄰塊，挂到unsort隊列中去，如果合并後的大小大于64k，也會觸發consolidate，（可能是周圍比較多小塊了吧），然後才試圖去收縮堆。（收縮堆的條件是目前free的塊大小加上前後能合并chunk的大小大于64k，并且要堆頂的大小要達到閥值，才有可能收縮堆）

以上的闡述還是很明确的，glibc配置設定的關鍵就是在于采用了一些政策，比如多個變長連結清單的散列政策，比如高速緩存政策以及一般緩存政策，考慮到的原因就是一般小記憶體的使用率比大記憶體要大，是以有必要為小記憶體維護一個高速的池，另外小記憶體的釋放頻率也高，一般都是用于存放一些臨時資料的，是以為小記憶體維護一個池不會對其它需求不公平，緩存的優勢在于它容量一般比較小，周遊查找很快，并且裡面的資料幾乎都是熱的，，在這裡，所謂的資料要過熱的意義不是指記憶體塊的記憶體，而是記憶體塊的大小，一個記憶體塊比較熱的意思是說該大小的記憶體塊被頻繁使用，另一句話說就是隻有頻繁使用的資料才會進入緩存，并且這些資料的量不會太多，如果太多的話緩存就失去了它的查找優勢，如果資料不熱的話，查找就會頻繁失敗，最終還是要進入一般的配置設定模式，是以設計一個緩存系統要考慮的問題很多，絕不僅僅是理論上那麼簡單。還有一個政策就是堆頂的特殊處理，堆頂不放在任何一個連結清單中，對它進行照顧就是因為為了更有效的将記憶體退還作業系統，因為堆的壓縮隻能從堆頂開始，作業系統隻知道給了一個程序虛拟記憶體連續的一大塊叫做堆的記憶體，别的什麼也不知道，應用程式歸還的時候同樣需要連續的從堆頂歸還而不能僅僅歸還空洞，歸根結底要對堆頂進行特殊的處理

 本文轉自 dog250 51CTO部落格，原文連結:http://blog.51cto.com/dog250/1274091