malloc

本文梳理了一下malloc跟free的源碼。malloc()函數在源代碼中使用宏定義為public_mALLOc()。public_mALLOc()函數只是簡單的封裝_int_malloc()函數，_int_malloc()函數才是內存分配的核心實現。

public_mALLOc()

首先檢查是否存在__malloc_hook。如果存在，則調用hook函數。注意hook函數的傳參為請求分配的內存大小。

獲取分配區指針，如果獲取分配區失敗，返回退出，否則，調用_int_malloc()函數分配內存。

如果_int_malloc()函數分配內存失敗，并且使用的分配區不是主分配區，這種情況可能是mmap區域的內存被用光了。如果目前主分配區還可以從堆中分配內存，則需要再嘗試從主分配區中分配內存。首先釋放所使用分配區的鎖，然后獲得主分配區的鎖，并調用_int_malloc()函數分配內存，最后釋放主分配區的鎖。

如果_int_malloc()函數分配內存失敗，并且使用的分配區是主分配區，查看是否有非主分配區，如果有，調用arena_get2()獲取分配區，然后對主分配區解鎖，如果arena_get2()返回一個非分配區，嘗試調用_int_malloc()函數從該非主分配區分配內存，最后釋放該非主分配區的鎖。

如果_int_malloc()函數分配內存成功，釋放所使用的分配區的鎖。返回分配的chunk。

_int_malloc

_int_malloc函數是內存分配的核心，根據分配的內存塊的大小，該函數中實現了了四種分配內存的路徑。先給出_int_malloc()函數的定義及臨時變量的定義：

checked_request2size()函數將需要分配的內存大小bytes轉換為需要分配的chunk大小nb，Ptmalloc內部分配都是以chunk為單位，根據chunk的大小，決定如何獲得滿足條件的chunk。

分配fast bin chunk

如果所需的chunk大小小于等于fast bins中的最大chunk大小，首先嘗試從fast bin中分配chunk。1.根據所需的chunk大小獲得該chunk所屬的fast bin的index，根據該index獲得所屬fast bin的空閑chunk鏈表頭指針。如果沒有開啟ATOMIC_FASTBINS優化，則按以下步驟：2.將頭指針的下一個chunk作為空閑chunk鏈表的頭部。3.取出第一個chunk，并調用chunk2mem()函數返回用戶所需的內存塊。如果開啟了ATOMIC_FASTBINS優化，則步驟與上述類似，只是在刪除fastbin頭節點的時候使用了lock-free技術，加快了分配速度。

check

fastbin分配對size做了檢查，如果分配chunk的size不等于分配時的idx，就會報錯。使用chunksize()和fastbin_index函數計算chunk的size大小，所以我們無需管size的后三位(size_sz=8的情況下無需管后四位)，只需保證前幾位與idx相同即可。

分配small bin chunk

如果所需的chunk大小屬于small bin，則會執行如下步驟：1.查找chunk對應small bins數組的index，根據index獲得某個small bin的空閑chunk雙向循環鏈表表頭。2.將最后一個chunk賦值給victim，如果victim與表頭相同，表示該鏈表為空，不能從small bin的空閑chunk鏈表中分配，這里不做處理，等后面的步驟來處理。3.victim與表頭不同有兩種情況。

• victim為0
  1.表示small bin還沒有初始化為雙向循環鏈表，調用malloc_consolidete()函數將fast bins中的chunk合并。
• victim不為0
  1.設置victim chunk的inuse標志，該標志處于vimctim chunk的下一個相鄰chunk的size字段的第一個bit。2.做與unlink類似的操作將chunk從small bin中脫鏈。

4.判斷當前分配區是否屬于非主分配區，如果是，將victim chunk的size字段中的標志非主分配區的標志bit清零。5.調用chunk2mem()函數獲得chunk的實際可用的內存指針，將該內存指針返回給應用層。

check

申請的chunk需滿足chunk->bk->fd = chunk

分配large bin chunk

所需chunk不屬于small bins，那么就在large bins的范圍內，則

1.根據chunk的大小獲得對應large bin的index

2.判斷當前分配區的fast bins中是否包含chunk，如果存在，調用malloc_consolidate()函數合并fast bins中的chunk，并將這些空閑chunk加入unsorted bin中。

下面的源代碼實現從last remainder chunk，large bins和top chunk中分配所需的chunk，這里包含了多個多層循環，在這些循環中，主要工作是分配前兩步都未分配成功的small bin chunk、large bin chunk和large chunk。最外層的循環用于重新嘗試分配small bin chunk，因為如果在前一步分配smallbin chunk不成功，并沒有調用malloc_consolidate()函數合并fast bins中的chunk，將空閑chunk加入unsorted bin中，如果第一嘗試從last remainder chunk、top chunk中分配small bin chunk都失敗以后，如果fast bins中存在空閑chunk，會調用malloc_consolidate()函數，那么在usorted bin中就可能存在合適的small bin chunk供分配，所以需要再次嘗試。

反向遍歷unsorted bin的雙向鏈表，遍歷結束的條件是循環鏈表中只剩一個頭節點。

1.檢查當前遍歷的chunk是否合法，chunk的大小不能小于等于2*SIZE_SZ，也不能超過該分配區總的內存分配量。

2.獲取chunk的大小并賦值給size。

如果需要分配一個small bin chunk，并且unsorted bin中只有一個chunk，并且這個chunk為last remainder chunk，并且這個chunk的大小大于所需chunk的大小加上MINSIZE，在滿足這些條件的情況下，可以使用這個chunk切分出需要的small bin chunk。這是唯一的從unsorted bin中分配small bin chunk的情況。

1.從chunk中切分出所需大小的chunk。

2.計算切分后剩下chunk的大小，將剩下的chunk加入unsorted bin的鏈表中，并將剩下的chunk作為分配區的last remainder chunk。

3.如果剩下的chunk屬于large bin chunk，將該chunk的fd_nextsize和bk_nextsize設置為NULL，因為這個chunk僅僅存在于unsorted bin中，并且unsorted bin中有且僅有這一個chunk。

設置分配出的chunk和last remainder chunk的相關信息。，調用chunk2mem()獲得chunk中可用的內存指針，返回給應用層，退出。

將雙向循環鏈表中的最后一個chunk移除。

如果當前chunk與所需的chunk大小一致 1.設置當前chunk處于inuse狀態 2.設置分配區標志位 3.調用chunk2mem()獲得chunk中的可用內存指針，返回給應用層。

如果當前chunk屬于small bins，獲得當前chunk所屬small bin的index，并將該small bin的鏈表表頭復制給bck，第一個chunk賦值給fwd，也就是當前的chunk會插入到bck和fwd之間，作為small bin比鏈表的第一個chunk。

如果當前chunk屬于large bins，獲得當前chunk所屬large bin的index，并將該large bin的鏈表表頭賦值給bck，第一個chunk賦值給fwd，也就是當前的chunk會插入到bck和fwd之間，作為large bin鏈表的第一個chunk。

如果fwd不等于bck，意味著large bin中有空閑chunk存在，由于large bin中的空閑chunk是按照大小排序的，需要將當前從unsorted bin中取出的chunk插入到large bin中合適的位置。將當前的chunk的size的inuse標志bit置位，相當于加1，便于加快chunk大小的比較，找到合適的地方插入當前chunk。

如果當前的chunk比large bin的最后一個chunk的大小還小，那么當前chunk1就插入到large bin的鏈表的最后，作為最后一個chunk。可以看出large bin中的chunk是按照從大到小的順序排序的，同時一個chunk存在于兩個雙向循環鏈表中，一個鏈表包含了large bin中所有的chunk，另一個鏈表為chunk size鏈表，該鏈表從每個相同大小的chunk中取除第一個chunk按照大小順序鏈接在一起，便于一次跨域多個相同大小的chunk遍歷下一個不同大小的chunk，這樣可以加快在large bin鏈表中的遍歷速度。

正向遍歷chunk size鏈表，直到找到第一個chunk大小小于等于當前chunk大小的chunk退出循環。

如果從large bin鏈表中找到了與當前chunk大小相同的chunk，則統一大小的chunk已經存在，那么chunk size一定包含了fwd指向的chunk，為了不久改chunk size鏈表，當前chunk只能插入fwd之后。

如果chunk size鏈表中還沒有包含當前chunk大小的chunk，也就是說當前chunk的大小大于fwd的大小，則將當前chunk作為該chunk size的代表加入chunk size鏈表，chunk size鏈表也是按照由大到小的順序排序。

如果large bin鏈表中沒有chunk，直接將當前chunk加入chunk size鏈表。

將當前chunk插入到對應的空閑的chunk鏈表中，并將large bin所對應binmap的相應bit置位。

如果unsorted bin中的chunk超過了10000個，最多遍歷一萬個就退出，避免長時間處理unsorted bin影響內存分配的效率。當unsorted bin中的空閑chunk加入到相應的small bins和large bins后，將使用最佳匹配法分配large bin chunk。

如果所需分配的chunk為large bin chunk，查詢對應的large bin鏈表，如果large bin鏈表為空，或者鏈表中最大的chunk也不能滿足要求，則不能從large bin中分配。否則，遍歷large bin鏈表，找到合適的chunk。

反向遍歷chunk size鏈表，直到找到第一個大于等于所需chunk大小的chunk退出循環。

如果large bin鏈表中選取的chunk civtim不是鏈表中的最后一個chunk，并且與victim大小相同的chunk不止一個，那么意味著victim為chunk size鏈表中的節點，為了不調整chunk size鏈表，需要避免將chunk size鏈表中取出，所以取victim->fd節點對應的chunk作為候選chunk。由于large bin鏈表中的chunk也是按照大小排序，同一大小的chunk有多個時，這些chunk必定排在一起，所以victim->fd節點對應的chunk的大小必定與victim的大小一樣。

計算將victim切分后剩余大小，并調用unlink()宏函數將victim從large bin鏈表中取出。

如果將victim切分后剩余大小小于MINSIZE，則將整個victim分配給應用層，設置victim的inuse標志，inuse標志位于下一個相鄰的chunk的size字段中。如果當前分配區不是主分配區，將victim的size字段中的非主分配區標志置位。

從victim中切分出所需的chunk，剩余部分作為一個新的chunk加入到unsorted bin中。如果剩余部分chunk屬于large bins，將剩余部分chunk的chunk size鏈表指針設置為NULL，因為unsorted bin中的chunk是不排序的，這兩個指針無用，必須清零。

設置victim和remainder的狀態，由于remainder為空閑chunk，所以需要設置該chunk的foot。

從large bin中使用最佳匹配法找到了合適的chunk，調用chunk2mem()獲得chunk中可用的內存指針，返回給應用層，退出。如果通過上面的方式從最合適的small bin或large bin中都沒有分配到需要的chunk，則查看比當前bin的index大的small bin或large bin是否有空閑chunk可利用來分配所需的chunk。源代碼實現如下：

獲取下一個相鄰bin的空閑chunk鏈表，并獲取該bin對于binmap中的bit位的值。Binmap中的標識了相應的bin中是否有空閑 chunk 存在。Binmap按block管理，每個block為一個int，共32個bit，可以表示32個bin中是否有空閑chunk存在。使用binmap可以加快查找bin是否包含空閑chunk。這里只查詢比所需chunk大的bin中是否有空閑chunk 可用。

Idx2bit()宏將idx指定的位設置為1，其它位清零，map表示一個block值，如果bit大于map，意味著map為0，該block所對應的所有bins中都沒有空閑chunk，于是遍歷binmap的下一個block，直到找到一個不為0的block或者遍歷完所有的 block。退出循環遍歷后，設置 bin 指向 block 的第一個 bit 對應的 bin，并將 bit 置為 1，表示該 block 中 bit 1 對應的 bin，這個 bin 中如果有空閑 chunk，該 chunk 的大小一定滿足要求。

在一個block遍歷對應的bin，直到找到一個bit不為0退出遍歷，則該bit對于的bin中有空閑chunk存在。將bin鏈表中的最后一個chunk賦值為victim。

如果victim與bin鏈表頭指針相同，表示該bin中沒有空閑chunk，binmap中的相應位設置不準確，將binmap的相應bit位清零，獲取當前bin下一個bin，將bit移到下一個bit位，即乘以2。

當前bin中的最后一個chunk滿足要求，獲取該chunk的大小，計算切分出所需chunk后剩余部分的大小，然后將victim從bin的鏈表中取出。

如果剩余部分的大小小于MINSIZE，將整個chunk分配給應用層(代碼在后面)，設置victim的狀態為inuse，如果當前分配區為非分配區，設置victim的非主分配區標志位。

從victim中切分出所需的chunk，剩余部分作為一個新的chunk加入到unsorted bin中。如果剩余部分chunk屬于large bins，將剩余部分chunk的chunk size鏈表指針設置為NULL，因為unsorted bin中的chunk是不排序的，這兩個指針無用，必須清零。

設置victim和remainder的狀態，由于remainder為空閑chunk，所以需要設置該chunk的foot。

調用chunk2mem()獲得chunk中可用的內存指針，返回給應用層，退出。如果從所有的bins中都沒有獲得所需的chunk，可能的情況為bins中沒有空閑chunk，或者所需的chunk大小很大，下一步將嘗試從top chunk中分配所需chunk。源代碼實現如下：

將當前分配區的top chunk賦值給victim，并獲得victim的大小。

由于top chunk切分出所需chunk后，還需要MINSIZE的空間來作為fencepost，所需必須滿足top chunk的大小大于所需chunk的大小加上MINSIZE這個條件，才能從top chunk中分配所需chunk。從top chunk切分出所需chunk的處理過程跟前面的chunk切分類似，不同的是，原top chunk切分后的剩余部分將作為新的top chunk，原top chunk的fencepost仍然作為新的top chunk的fencepost，所以切分之后剩余的chunk不用set_foot。

如果top chunk也不能滿足要求，查看fast bins中是否有空閑chunk存在，由于開啟了ATOMIC_FASTBINS優化情況下，free屬于fast bins的chunk時不需要獲得分配區的鎖，所以在調用_int_malloc()函數時，有可能有其它線程已經向fast bins中加入了新的空閑chunk，也有可能是所需的chunk屬于small bins，但通過前面的步驟都沒有分配到所需的chunk，由于分配small bin chunk時在前面的步驟都不會調用malloc_consolidate()函數將fast bins中的 chunk合并加入到unsorted bin中。所在這里如果fast bin中有chunk存在，調用malloc_consolidate()函數，并重新設置當前bin的index。并轉到最外層的循環，嘗試重新分配small bin chunk或是large bin chunk。如果開啟了ATOMIC_FASTBINS優化，有可能在由其它線程加入到fast bins中的chunk被合并后加入unsorted bin中，從unsorted bin中就可以分配出所需的large bin chunk了，所以對沒有成功分配的large bin chunk也需要重試。

如果top chunk也不能滿足要求，查看fast bins中是否有空閑chunk存在，如果fast bins中有空閑chunk存在，在沒有開啟ATOMIC_FASTBINS優化的情況下，只有一種可能，那就是所需的chunk屬于small bins，但通過前面的步驟都沒有分配到所需的small bin chunk，由于分配small bin chunk時在前面的步驟都不會調用malloc_consolidate()函數將fast bins中的空閑chunk合并加入到unsorted bin中。所在這里如果fast bins中有空閑chunk存在，調用 malloc_consolidate()函數，并重新設置當前bin的index。并轉到最外層的循環，嘗試重新分配small bin chunk。

山窮水盡了，只能想系統申請內存了。sYSMALLOc()函數可能分配的chun 包括small bin chunk，large bin chunk 和large chunk。

check

1.fastbin頭部的chunk的idx與fastbin的idx要一致。2.unsorted bin中的chunk1大小不能小于等于2*SIZE_SZ，也不能超過該分配區總的內存分配量。3.將chunk從unsorted bin取出放入small bin和large bin時用到了unlink()宏，注意繞過unlink()宏中的檢測。4.切出的remainder在重新放入unsorted bin時需要滿足 unsorted_chunks(av)->fd->bk = unsorted_chunks(av)。

總結

malloc分配步驟大致如下：1.檢查有沒有_malloc_hook，有則調用hook函數。2.獲得分配區的鎖，調用函數_int_malloc()分配內存。3.如果申請大小在fast bin范圍內，則從fast bin分配chunk，成功則返回用戶指針，否則進行下一步。(當對應的bin為空時，就會跳過第5步操作) 4.如果申請大小在small bin范圍內，則從small bin中分配chunk，成功則返回用戶指針，否則進行下一步。5.調用malloc_consolidate()函數合并fast bin，并鏈接進unsorted bin中。6.如果申請大小在small bin范圍內，且此時unsorted bin只有一個chunk，并且這個chunk為last remainder chunk且大小夠大，則從這個chunk中切分出需要的大小，成功則返回用戶指針，否則進行下一步。7.反向遍歷unsorted bin，如果當前chunk與所需chunk大小一致，則分配，成功則返回用戶指針，否則將當前chunk放入small bin或者large bin中合適的位置。8.使用最佳匹配算法在large bin中找到合適的chunk進行分配，成功則返回用戶指針，否則進行下一步。9.到了這一步，說明沒有大小正好合適的chunk，則看看比當前bin的index大的small bin或者large bin中有沒有空閑chunk可用來分配。成功則返回用戶指針，否則進行下一步。10.嘗試從top chunk中分配，成功則返回用戶指針，否則進行下一步。11.如果fast bin中還有chunk，調用malloc_consolidate()回到第6步(因為第3步對應bin為空時會跳過第五步，而fast bin合并之后有可能出現能夠分配的small bin)。12.到了這步還不行，則調用sYSMALLOc()函數向系統申請內存。