malloc和free簡介及實現方式說明

malloc / free 簡介

malloc 分配指定大小的內存空間，返回一個指向該空間的指針。大小以字節為單位。返回 void* 指針，需要強制類型轉換后才能引用其中的值。 free 釋放一個由 malloc 所分配的內存空間。ptr 指向一個要釋放內存的內存塊，該指針應當是之前調用的 malloc 的返回值。

使用示例：

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

動態內存分配的系統調用：brk / sbrk

動態分配的內存都在堆中，堆從低地址向高地址增長：

Linux 提供了兩個系統調用 brk 和 sbrk：

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

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

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

malloc / free 實現思路

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

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

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

• 最佳適應法
• 最差適應法
• 首次適應法
• 下一個適應法

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

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

內核學習網站：

Linux內核源碼/內存調優/文件系統/進程管理/設備驅動/網絡協議棧-學習視頻教程-騰訊課堂?ke.qq.com/course/4032547?flowToken=1040236

malloc 的實現方式一：顯式空閑鏈表 + 整塊分配

malloc 的實現方式有很多種。最簡單的方法是使用一個鏈表來管理所有已分配和未分配的內存塊，在每個內存塊的首部記錄當前塊的大小、當前區塊是否已經被分配出去。首部對應這樣的結構體：

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

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

下面是這種實現方式的代碼：

int has_initialized = 0;     // 初始化標志
void *managed_memory_start;  // 指向堆底（內存塊起始位置）
void *last_valid_address;    // 指向堆頂

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

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

對應的free實現：

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

這種方法的缺點是：

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

malloc 的實現方式二：顯式空閑鏈表 + 按需分配

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

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

和第一種方式相比，這種方式的優點主要是：

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

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

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

malloc 的實現方式三：分離的空閑鏈表

上面的兩種分配方法，分配時間都和空閑塊的數量成線性關系。

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

簡單分離存儲

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

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

分離適配

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

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

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

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

伙伴系統

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

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

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

tcmalloc

tcmalloc 是 Google 開發的內存分配器，全稱 Thread-Caching Malloc，即線程緩存的 malloc，實現了高效的多線程內存管理。

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

總結

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

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

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

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

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

審核編輯：湯梓紅