malloc和free簡介及實現(xiàn)方式說明

malloc / free 簡介

malloc 分配指定大小的內(nèi)存空間，返回一個指向該空間的指針。大小以字節(jié)為單位。返回 void* 指針，需要強制類型轉(zhuǎn)換后才能引用其中的值。 free 釋放一個由 malloc 所分配的內(nèi)存空間。ptr 指向一個要釋放內(nèi)存的內(nèi)存塊，該指針應(yīng)當(dāng)是之前調(diào)用的 malloc 的返回值。

使用示例：

int* ptr; 
ptr = (int*)malloc(10 * sizeof(int)); /* 進行強制類型轉(zhuǎn)換 */ 
free(ptr);、

動態(tài)內(nèi)存分配的系統(tǒng)調(diào)用：brk / sbrk

動態(tài)分配的內(nèi)存都在堆中，堆從低地址向高地址增長：

Linux 提供了兩個系統(tǒng)調(diào)用 brk 和 sbrk：

int brk(void *addr);
void *sbrk(intptr_t increment);

brk 用于返回堆的頂部地址；sbrk用于擴展堆，通過參數(shù)increment 指定要增加的大小，如果擴展成功，返回 brk 的舊值。如果 increment 為零，返回brk的當(dāng)前值。

我們不會直接通過 brk 或 sbrk 來分配堆內(nèi)存，而是先通過sbrk 擴展堆，將這部分空閑內(nèi)存空間作為緩沖池，然后通過 malloc / free 管理緩沖池中的內(nèi)存。這是一種程序化思想，能夠避免頻繁的系統(tǒng)調(diào)用，提高程序性能。

malloc / free 實現(xiàn)思路

malloc 使用空閑鏈表組織堆中的空閑區(qū)塊，空閑鏈表有時也用雙向鏈表實現(xiàn)。每個空閑區(qū)塊都有一個相同的首部，稱為“內(nèi)存控制塊” mem_control_block，其中記錄了空閑區(qū)塊的信息，比如指向下一個分配塊的指針、當(dāng)前分配塊的長度、或者當(dāng)前區(qū)塊是否已經(jīng)被分配出去。這個首部對于程序是不可見的，malloc 返回的是緊跟在首部后面的地址，即可用空間的起始地址。

malloc 分配時會搜索空閑鏈表，根據(jù)匹配原則，找到一個大于等于所需空間的空閑區(qū)塊，然后將其分配出去，返回這部分空間的指針。如果沒有這樣的內(nèi)存塊，則向操作系統(tǒng)申請擴展堆內(nèi)存。注意，返回的指針是從可用空間開始的，而不是從首部開始的：

malloc 所使用的內(nèi)存匹配算法有很多，執(zhí)行時間和內(nèi)存消耗也各有不同。到底使用哪個匹配算法，取決于實現(xiàn)。常見的內(nèi)存匹配算法有：

• 最佳適應(yīng)法
• 最差適應(yīng)法
• 首次適應(yīng)法
• 下一個適應(yīng)法

free 會將區(qū)塊重新插入到空閑鏈表中。free 只接受一個指針，卻可以釋放恰當(dāng)大小的內(nèi)存，這是因為在分配的區(qū)域的首部保存了該區(qū)域的大小。

【文章福利】小編推薦自己的Linux內(nèi)核技術(shù)交流群:【865977150】整理了一些個人覺得比較好的學(xué)習(xí)書籍、視頻資料共享在群文件里面，有需要的可以自行添加哦??！

內(nèi)核學(xué)習(xí)網(wǎng)站：

Linux內(nèi)核源碼/內(nèi)存調(diào)優(yōu)/文件系統(tǒng)/進程管理/設(shè)備驅(qū)動/網(wǎng)絡(luò)協(xié)議棧-學(xué)習(xí)視頻教程-騰訊課堂?ke.qq.com/course/4032547?flowToken=1040236

malloc 的實現(xiàn)方式一：顯式空閑鏈表 + 整塊分配

malloc 的實現(xiàn)方式有很多種。最簡單的方法是使用一個鏈表來管理所有已分配和未分配的內(nèi)存塊，在每個內(nèi)存塊的首部記錄當(dāng)前塊的大小、當(dāng)前區(qū)塊是否已經(jīng)被分配出去。首部對應(yīng)這樣的結(jié)構(gòu)體：

struct mem_control_block {
  int is_available; // 是否可用（如果還沒被分配出去，就是 1）
  int size;         // 實際空間的大小
};

使用首次適應(yīng)法進行分配：遍歷整個鏈表，找到第一個未被分配、大小合適的內(nèi)存塊；如果沒有這樣的內(nèi)存塊，則向操作系統(tǒng)申請擴展堆內(nèi)存。

下面是這種實現(xiàn)方式的代碼：

int has_initialized = 0;     // 初始化標(biāo)志
void *managed_memory_start;  // 指向堆底（內(nèi)存塊起始位置）
void *last_valid_address;    // 指向堆頂

void malloc_init() {
  // 這里不向操作系統(tǒng)申請堆空間，只是為了獲取堆的起始地址
  last_valid_address = sbrk(0);
  managed_memory_start = last_valid_address;
  has_initialized = 1;
}

void *malloc(long numbytes) {
  void *current_location;  // 當(dāng)前訪問的內(nèi)存位置
  struct mem_control_block *current_location_mcb;  // 只是作了一個強制類型轉(zhuǎn)換
  void *memory_location;  // 這是要返回的內(nèi)存位置。初始時設(shè)為
                          // 0，表示沒有找到合適的位置
  if (!has_initialized) {
    malloc_init();
  }
  // 要查找的內(nèi)存必須包含內(nèi)存控制塊，所以需要調(diào)整 numbytes 的大小
  numbytes = numbytes + sizeof(struct mem_control_block);
  // 初始時設(shè)為 0，表示沒有找到合適的位置
  memory_location = 0;
  /* Begin searching at the start of managed memory */
  // 從被管理內(nèi)存的起始位置開始搜索
  // managed_memory_start 是在 malloc_init 中通過 sbrk() 函數(shù)設(shè)置的
  current_location = managed_memory_start;
  while (current_location != last_valid_address) {
    // current_location 是一個 void 指針，用來計算地址；
    // current_location_mcb 是一個具體的結(jié)構(gòu)體類型
    // 這兩個實際上是一個含義
    current_location_mcb = (struct mem_control_block *)current_location;
    if (current_location_mcb->is_available) {
      if (current_location_mcb->size >= numbytes) {
        // 找到一個可用、大小適合的內(nèi)存塊
        current_location_mcb->is_available = 0;  // 設(shè)為不可用
        memory_location = current_location;      // 設(shè)置內(nèi)存地址
        break;
      }
    }
    // 否則，當(dāng)前內(nèi)存塊不可用或過小，移動到下一個內(nèi)存塊
    current_location = current_location + current_location_mcb->size;
  }
  // 循環(huán)結(jié)束，沒有找到合適的位置，需要向操作系統(tǒng)申請更多內(nèi)存
  if (!memory_location) {
    // 擴展堆
    sbrk(numbytes);
    // 新的內(nèi)存的起始位置就是 last_valid_address 的舊值
    memory_location = last_valid_address;
    // 將 last_valid_address 后移 numbytes，移動到整個內(nèi)存的最右邊界
    last_valid_address = last_valid_address + numbytes;
    // 初始化內(nèi)存控制塊 mem_control_block
    current_location_mcb = memory_location;
    current_location_mcb->is_available = 0;
    current_location_mcb->size = numbytes;
  }
  // 最終，memory_location 保存了大小為 numbyte的內(nèi)存空間，
  // 并且在空間的開始處包含了一個內(nèi)存控制塊，記錄了元信息
  // 內(nèi)存控制塊對于用戶而言應(yīng)該是透明的，因此返回指針前，跳過內(nèi)存分配塊
  memory_location = memory_location + sizeof(struct mem_control_block);
  // 返回內(nèi)存塊的指針
  return memory_location;
}

對應(yīng)的free實現(xiàn)：

void free(void *ptr) {  // ptr 是要回收的空間
  struct mem_control_block *free;
  free = ptr - sizeof(struct mem_control_block); // 找到該內(nèi)存塊的控制信息的地址
  free->is_available = 1;  // 該空間置為可用
  return;
}

這種方法的缺點是：

1、已分配和未分配的內(nèi)存塊位于同一個鏈表中，每次分配都需要從頭到尾遍歷
2、采用首次適應(yīng)法，內(nèi)存塊會被整體分配，容易產(chǎn)生較多內(nèi)部碎片

malloc 的實現(xiàn)方式二：顯式空閑鏈表 + 按需分配

這種實現(xiàn)方式維護一個空閑塊鏈表，只包含未分配的內(nèi)存塊。malloc 分配時會搜索空閑鏈表，找到第一個大于等于所需空間的空閑區(qū)塊，然后從該區(qū)塊的尾部取出所需要的空間，剩余空間還是存在空閑鏈表中；如果該區(qū)塊的剩余部分不足以放下首部信息，則直接將其從空閑鏈表摘除。最后返回這部分空間的指針。 下面是這種實現(xiàn)方式的幾個示例：

通過 free 釋放內(nèi)存時，會將內(nèi)存塊加入到空閑鏈表中，并將前后相鄰的空閑內(nèi)存合并，這時使用雙向鏈表管理空閑鏈表就很有用了。

和第一種方式相比，這種方式的優(yōu)點主要是：

• 空閑鏈表中只包含未被分配的內(nèi)存塊，節(jié)省遍歷開銷
• 只分配必須大小的空間，避免內(nèi)存浪費

這種方式的缺點是：多次調(diào)用 malloc 后，空閑內(nèi)存被切成很多的小內(nèi)存片段，產(chǎn)生較多外部碎片，會導(dǎo)致用戶在申請內(nèi)存使用時，找不到足夠大的內(nèi)存空間。這時需要進行內(nèi)存整理，將連續(xù)的空閑內(nèi)存合并，但是這會降低函數(shù)性能。

注意：內(nèi)存緊湊在這里一般是不可用的，因為這會改變之前 malloc 返回的空間的地址。

malloc 的實現(xiàn)方式三：分離的空閑鏈表

上面的兩種分配方法，分配時間都和空閑塊的數(shù)量成線性關(guān)系。

另一種實現(xiàn)方式是分離存儲，即維護多個空閑鏈表，其中每個鏈表中的塊有大致相等或者相同的大小。一般常見的是根據(jù) 2 的冪來劃分塊大小。分配時，可以直接在某個空閑鏈表里搜索合適的塊。如果沒有找到合適的塊與之匹配，就搜索下一個鏈表，以此類推。

簡單分離存儲

每個大小類的空閑鏈表包含大小相等的塊。分配時，從某個空閑鏈表取下一塊，或者向操作系統(tǒng)請求內(nèi)存片并分割成大小相等的塊，形成新的鏈表。釋放時，只需要簡單的將塊插入到相應(yīng)空閑鏈表的前面。

優(yōu)點一是分配和釋放只需要在鏈表頭進行操作，都是常數(shù)時間，二是因為每個塊大小都是固定的，所以只需要一個 next 指針，不需要額外的控制信息，節(jié)省空間。缺點是容易造成內(nèi)部碎片和外部碎片。內(nèi)部碎片顯而易見，因為每個塊都是整體分配的，不會被分割。外部碎片在這樣的模式下很容易產(chǎn)生：應(yīng)用頻繁地申請和釋放較小大小的內(nèi)存塊，由于這些內(nèi)存塊不會合并，所以系統(tǒng)維護了大量小內(nèi)存塊形成的空閑鏈表，而沒有多余空間來分配大內(nèi)存塊，導(dǎo)致產(chǎn)生外部碎片。

分離適配

這種方法同樣維護了多個空閑鏈表，只不過每個鏈表中的塊是大致相等的大小，比如每個鏈表中的塊大小范圍可能是：

• 1
• 2
• 3~4
• 5~8
• …
• 1025~2048
• 2049~4096
• 4097~∞

在分配的時候，需要先根據(jù)申請內(nèi)存的大小選擇適當(dāng)?shù)目臻e鏈表，然后遍歷該鏈表，根據(jù)匹配算法（如首次適應(yīng)）尋找合適的塊。如果找到一個塊，將其分割（可選），并將剩余部分插入到適當(dāng)?shù)目臻e鏈表中。如果找不到合適的塊，則查找下一個更大的大小類的空閑鏈表，以此類推，直到找到或者向操作系統(tǒng)申請額外的堆內(nèi)存。在釋放一個塊時，合并前后相鄰的空閑塊，并將結(jié)果放到相應(yīng)的空閑鏈表中。

分離適配方法是一種常見的選擇，C 標(biāo)準(zhǔn)庫中提供的 GNU malloc 包就是采用的這種方法。這種方法既快速，對內(nèi)存的使用也很有效率。由于搜索被限制在堆的某個部分而不是整個堆，所以搜索時間減少了。內(nèi)存利用率也得到了改善，避免大量內(nèi)部碎片和外部碎片。

伙伴系統(tǒng)

伙伴系統(tǒng)是分離適配的一種特例。它的每個大小類的空閑鏈表包含大小相等的塊，并且大小都是 2 的冪。最開始時，全局只有一個大小為 2m2m 字的空閑塊，2m2m 是堆的大小。

假設(shè)分配的塊的大小都是 2 的冪，為了分配一個大小為 2k2k 的塊，需要找到大小恰好是 2k2k 的空閑塊。如果找到，則整體分配。如果沒有找到，則將剛好比它大的塊分割成兩塊，每個剩下的半塊（也叫做伙伴）被放置在相應(yīng)的空閑鏈表中，以此類推，直到得到大小恰好是 2k2k 的空閑塊。釋放一個大小為 2k2k 的塊時，將其與空閑的伙伴合并，得到新的更大的塊，以此類推，直到伙伴已分配時停止合并。

伙伴系統(tǒng)分配器的主要優(yōu)點是它的快速搜索和快速合并。主要缺點是要求塊大小為 2 的冪可能導(dǎo)致顯著的內(nèi)部碎片。因此，伙伴系統(tǒng)分配器不適合通用目的的工作負(fù)載。然而，對于某些特定應(yīng)用的工作負(fù)載，其中塊大小預(yù)先知道是 2 的冪，伙伴系統(tǒng)分配器就很有吸引力了。

tcmalloc

tcmalloc 是 Google 開發(fā)的內(nèi)存分配器，全稱 Thread-Caching Malloc，即線程緩存的 malloc，實現(xiàn)了高效的多線程內(nèi)存管理。

tcmalloc 主要利用了池化思想來管理內(nèi)存分配。對于每個線程，都有自己的私有緩存池，內(nèi)部包含若干個不同大小的內(nèi)存塊。對于一些小容量的內(nèi)存申請，可以使用線程的私有緩存；私有緩存不足或大容量內(nèi)存申請時再從全局緩存中進行申請。在線程內(nèi)分配時不需要加鎖，因此在多線程的情況下可以大大提高分配效率。

總結(jié)

malloc 使用鏈表管理內(nèi)存塊。malloc 有多種實現(xiàn)方式，在不同場景下可能會使用不同的匹配算法。

malloc 分配的空間中包含一個首部來記錄控制信息，因此它分配的空間要比實際需要的空間大一些。這個首部對用戶而言是透明的，malloc 返回的是緊跟在首部后面的地址，即可用空間的起始地址。

malloc 分配的函數(shù)應(yīng)該是字對齊的。在 32 位模式中，malloc 返回的塊總是 8 的倍數(shù)。在 64 位模式中，該地址總是 16 的倍數(shù)。最簡單的方式是先讓堆的起始位置字對齊，然后始終分配字大小倍數(shù)的內(nèi)存。

malloc 只分配幾種固定大小的內(nèi)存塊，可以減少外部碎片，簡化對齊實現(xiàn)，降低管理成本。

free 只需要傳遞一個指針就可以釋放內(nèi)存，空間大小可以從首部讀取。

審核編輯：湯梓紅