malloc / free 簡(jiǎn)介

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

使用示例：

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

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

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

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

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

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

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

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

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

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

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

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

free 會(huì)將區(qū)塊重新插入到空閑鏈表中。free 只接受一個(gè)指針，卻可以釋放恰當(dāng)大小的內(nèi)存，這是因?yàn)樵诜峙涞膮^(qū)域的首部保存了該區(qū)域的大小。

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

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

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

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

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

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

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

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

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

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

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

對(duì)應(yīng)的free實(shí)現(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;
}

這種方法的缺點(diǎn)是：

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

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

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

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

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

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

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

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

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

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

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

簡(jiǎn)單分離存儲(chǔ)

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

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

分離適配

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

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

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

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

伙伴系統(tǒng)

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

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

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

tcmalloc

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

tcmalloc 主要利用了池化思想來(lái)管理內(nèi)存分配。對(duì)于每個(gè)線程，都有自己的私有緩存池，內(nèi)部包含若干個(gè)不同大小的內(nèi)存塊。對(duì)于一些小容量的內(nèi)存申請(qǐng)，可以使用線程的私有緩存；私有緩存不足或大容量?jī)?nèi)存申請(qǐng)時(shí)再?gòu)娜志彺嬷羞M(jìn)行申請(qǐng)。在線程內(nèi)分配時(shí)不需要加鎖，因此在多線程的情況下可以大大提高分配效率。

總結(jié)

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

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

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

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

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

審核編輯：湯梓紅