內存分配不再神祕：深入剖析 malloc 函數實現原理與機制

前言：內存是計算機中必不可少的資源，因爲 CPU 只能直接讀取內存中的數據，所以當 CPU 需要讀取外部設備（如硬盤）的數據時，必須先把數據加載到內存中。

內存分配有三種方式：

1. 從靜態存儲區分配，生命週期隨程序的結束而結束，比如全局變量，靜態變量。

2. 從棧空間分配，函數調用結束後自動釋放。

3. 從堆空間分配，即動態內存開闢，如 malloc、calloc、realloc。

一、malloc 函數

談到 malloc 函數相信學過 c 語言的人都很熟悉，但是 malloc 底層到底做了什麼又有多少人知道。

1.1 關於 malloc 相關的幾個函數

關於 malloc 我們進入 Linux man 一下就會得到如下結果：

也可以這樣認爲（window 下）原型：

extern void *malloc(unsigned int num_bytes);

頭文件：

#include<malloc.h>或者#include<alloc.h>兩者的內容是完全一樣的

如果分配成功：則返回指向被分配內存空間的指針，不然返回指針 NULL 。同時，當內存不再使用的時候，應使用 free() 函數將內存塊釋放掉。

關於：void*, 表示未確定類型的指針，c,c++ 規定 void * 可以強轉爲任何其他類型的指針，關於 void 還有一種說法就是其他任何類型都可以直接賦值給它，無需進行強轉，但是反過來不可以 。

malloc:

malloc 分配的內存大小至少爲參數所指定的字節數，malloc 的返回值是一個指針，指向一段可用內存的起始位置，指向一段可用內存的起始地址，多次調用 malloc 所分配的地址不能有重疊部分，除非某次 malloc 所分配的地址被釋放掉 malloc 應該儘快完成內存分配並返回（不能使用 NP-hard 的內存分配算法）實現 malloc 時應同時實現內存大小調整和內存釋放函數（realloc 和 free） malloc 和 free 是配對的，如果申請後不釋放就是內存泄露，如果無故釋放那就是什麼也沒做，釋放只能釋放一次，如果一塊空間釋放兩次或者兩次以上會出現錯誤（但是釋放空指針例外，釋放空指針也等於什麼也沒做，所以釋放多少次都是可以的。）

1.2malloc 和 new

new 返回指定類型的指針，並且可以自動計算所需要的大小。

int *p;
p = new int;//返回類型爲int* ，分配的大小是sizeof(int)
p = new int[100];//返回類型是int*類型，分配的大小爲sizeof(int)*100

int *p;
p = (int *)malloc(sizeof(int));

1. malloc 的返回是 void*, 如果我們寫成了：p=malloc(sizeof(int)); 間接的說明了（將 void 轉化給了 int*，這不合理）

2. malloc 的實參是 sizeof(int)，用於指明一個整型數據需要的大小，如果我們寫成 p=(int*)malloc(1), 那麼可以看出：只是申請了一個一個字節大小的空間。

3. malloc 只管分配內存，並不能對其進行初始化，所以得到的一片新內存中，其值將是隨機的。

一般意義上：我們習慣性的將其初始化爲 NULL，當然也可以使用 memset 函數。

簡單的說：

malloc 函數其實就是在內存中找一片指定大小的空間，然後將這個空間的首地址給一個指針變量，這裏的指針變量可以是一個單獨的指針，也可以是一個數組的首地址，這要看 malloc 函數中參數 size 的具體內容。我們這裏 malloc 分配的內存空間在邏輯上是連續的，而在物理上可以不連續。我們作爲程序員，關注的是邏輯上的連續，其他的操作系統會幫着我們處理。

1.3malloc 實現原理

虛擬內存地址和物理內存地址

爲了簡單，現代操作系統在處理物理內存地址時，普遍採用虛擬內存地址技術。即在彙編程序層面，當涉及內存地址時，都是使用的虛擬內存地址。採用這種技術時，每個進程彷彿自己獨享一片 2N 字節的內存，其中 N 是機器位數。例如在 64 位 CPU 和 64 位操作系統下每個進程的虛擬地址空間爲 264Byte。

這種虛擬地址空間的作用主要是簡化程序的編寫及方便操作系統對進程間內存的隔離管理，真實中的進程不太可能如此大的空間，實際能用到的空間大小取決於物理內存的大小。 由於在機器語言層面都是採用虛擬地址，當實際的機器碼程序涉及到內存操作時，需要根據當前進程運行的實際上下文將虛擬地址轉化爲物理內存地址，才能實現對內存數據的操作。這個轉換一般由一個叫 MMU 的硬件完成。

頁與地址構成

在現代操作系統中，不論是虛擬內存還是物理內存，都不是以字節爲單位進行管理的，而是以頁爲單位。一個內存頁是一段固定大小的連續的連續內存地址的總稱，具體到 Linux 中，典型的內存頁大小爲 4096 Byte。所以內存地址可以分爲頁號和頁內偏移量。下面以 64 位機器，4G 物理內存，4K 頁大小爲例，虛擬內存地址和物理內存地址的組成如下：

上面是虛擬內存地址，下面是物理內存地址。由於頁大小都是 4k，所以頁內偏移都是用低 12 位表示，而剩下的高地址表示頁號 MMU 映射單位並不是字節，而是頁，這個映射通過差一個常駐內存的數據結構頁表來實現。現在計算機具體的內存地址映射比較複雜，爲了加快速度會引入一系列緩存和優化，例如 TLB 等機制，下面給出一個經過簡化的內存地址翻譯示意圖：

內存頁與磁盤頁

我們知道一般將內存看做磁盤的緩存，有時 MMU 在工作時，會發現頁表表名某個內存頁不在物理內存頁不在物理內存中，此時會觸發一個缺頁異常，此時系統會到磁盤中相應的地方將磁盤頁載入到內存中，然後重新執行由於缺頁而失敗的機器指令。關於這部分，因爲可以看做對 malloc 實現是透明的，所以不再詳述 ：

真實地址翻譯流程：

Linux 進程級內存管理

內存排布：明白了虛擬內存和物理內存的關係及相關的映射機制，下面看一下具體在一個進程內是如何排布內存的。 以 Linux 64 位系統爲例。理論上，64bit 內存地址空間爲 0x0000000000000000-0xFFFFFFFFFFFFFFF，這是個相當龐大的空間，Linux 實際上只用了其中一小部分。

具體分佈如圖所示：

對用戶來說主要關心的是 User Space。將 User Space 放大後，可以看到裏面主要分成如下幾段：

• Code：這是整個用戶空間的最低地址部分，存放的是指令（也就是程序所編譯成的可執行機器碼） Data：這裏存放的是初始化過的全局變量

• BSS：這裏存放的是未初始化的全局變量

• Heap：堆，這是我們本文主要關注的地方，堆自底向上由低地址向高地址增長

• Mapping Area：這裏是與 mmap 系統調用相關的區域。大多數實際的 malloc 實現會考慮通過 mmap 分配較大塊的內存空間，本文不考慮這種情況，這個區域由高地址像低地址增長 Stack: 棧區域，自高地址像低地址增長 。

• Heap 內存模型：一般來說，malloc 所申請的內存主要從 Heap 區域分配，來看看 Heap 的結構是怎樣的。

Linux 維護一個 break 指針，這個指針執行堆空間的某個地址，從堆開始到 break 之間的地址空間爲映射好的，可以供進程訪問，而從 break 往上，是未映射的地址空間，如果訪問這段空間則程序會報錯。

1.4brk 與 sbrk

由上文知道，要增加一個進程實際上的可用堆大小，就需要將 break 指針向高地址移動。Linux 通過 brk 和 sbrk 系統調用操作 break 指針。兩個系統調用的原型如下：

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

brk 將 break 指針直接設置爲某個地址，而 sbrk 將 break 從當前位置移動 increment 所指定的增量。brk 在執行成功時返回 0，否則返回 - 1 並設置爲 errno 爲 ENOMEM,sbrk 成功時返回 break 移動之前所指向的地址，否則返回（void*）-1;

資源限制和 rlimirt

系統爲每一個進程所分配的資源不是無限的，包括可映射的空間，因此每個進程有一個 rlimit 表示當前進程可用的資源上限，這個限制可以通過 getrlimit 系統調用得到，下面代碼獲取當前進程虛擬內存空間的 rlimit 其中 rlimt 是一個結構體

struct rlimit
{
    rlimt_t rlim_cur;
    rlim_t rlim_max;
};

每種資源有硬限制和軟限制，並且可以通過 setrlimit 對 rlimit 進行有條件限制作爲軟限制的上限，非特權進程只能設置軟限制，且不能超過硬限制

1.5 實現 malloc

（1) 數據結構

首先我們要確定所採用的數據結構。一個簡單可行方案是將堆內存空間以塊的形式組織起來，每個塊由 meta 區和數據區組成，meta 區記錄數據塊的元信息（數據區大小、空閒標誌位、指針等等），數據區是真實分配的內存區域，並且數據區的第一個字節地址即爲 malloc 返回的地址，可以使用如下結構體定義一個 block

typedef struct s_block *t_block;
struck s_block{
    size_t size;//數據區大小
    t_block next;//指向下個塊的指針
    int free;//是否是空閒塊
    int padding;//填充4字節，保證meta塊長度爲8的倍數
    char data[1];//這是一個虛擬字段，表示數據塊的第一個字節，長度不應計入meta
};

（2）尋找合適的 block

現在考慮如何在 block 鏈中查找合適的 block。一般來說有兩種查找算法： First fit: 從頭開始，使用第一個數據區大小大於要求 size 的塊所謂此次分配的塊 Best fit: 從頭開始，遍歷所有塊，使用數據區大小大於 size 且差值最小的塊作爲此次分配的塊 兩種方式各有千秋，best fit 有較高的內存使用率（payload 較高），而 first fit 具有較高的運行效率。這裏我們採用 first fit 算法

t_block find_block(t_block *last,size_t size){
    t_block b = first_block;
    while(b&&b->size>=size)
    {
        *last = b;
        b = b->next;
    }
    return b;
}

find_block 從 first_block 開始，查找第一個符合要求的 block 並返回 block 起始地址，如果找不到這返回 NULL，這裏在遍歷時會更新一個叫 last 的指針，這個指針始終指向當前遍歷的 block. 這是爲了如果找不到合適的 block 而開闢新 block 使用的。

（3）開闢新的 block

如果現有 block 都不能滿足 size 的要求，則需要在鏈表最後開闢一個新的 block。這裏關鍵是如何只使用 sbrk 創建一個 struct：

#define BLOCK_SIZE 24

t_block extend_heap{
    t_block b;
    b = sbrk(0);
        if(sbrk(BLOCK_SIZE+s)==(void*)-1)
        return NULL;
        b->size = s;
        b->next - NULL;
        if(last)
        last->next = b;
        b->free = 0;
        return b;
};

（4）分裂 block

First fit 有一個比較致命的缺點，就是可能會讓更小的 size 佔據很大的一塊 block，此時，爲了提高 payload, 應該在剩餘數據區足夠大的情況下，將其分裂爲一個新的 block：

void split_block(t_block b,size_t s)
{
    t_block new;
    new = b->data;
    new->size = b->size-s-BLOCK_SIZE;
    new->next = b->next;
    new ->free = 1;
    b->size = s;
    b->next = new;
}

（5）malloc 的實現

有了上面的代碼，我們就可以實現一個簡單的 malloc. 注意首先我們要定義個 block 鏈表的頭 first_block, 初始化爲 NULL；另外，我們需要剩餘空間至少有 BLOCK_SIZE+8 才執行分裂操作 由於我們需要 malloc 分配的數據區是按 8 字節對齊，所以 size 不爲 8 的倍數時，我們需要將 size 調整爲大於 size 的最小的 8 的倍數：

size_t align8(size_t s)
{
    if(s&0x7 == 0)
    return s;
    return ((s>>3)+1)<<3;
}
#define BLOCK_SIZE 24
void *first_block=NULL;
void *mallloc(size_t size)
{
    t_block b,last;
    size_t s;
    //對齊地址
    s = align8(size);
    if(first_block)
    //查找適合block
    last = first_block;
    b = find_block(&last,s);
    if(b)
    {
    //如果可以則分裂
    if((b->size-s)>=(BLOCK_SIZE + 8))
    split_block(b,s);
    b->free = 0;
    }
    else
    {
        //沒有合適的block，開闢一個新的
        b=extend_heap(last,s);
        if(!b)
        {
            return NULL;
        }
        else
        {
            b=extend_heap(NULL,s);
            if(!b)
            {
                return NULL;
            }
            first_block = b;
        }
    }
    return b->data;
}

二、calloc 函數

calloc 函數也是與 free() 函數配套使用的，使用方式與 malloc 幾乎相同, 也是在堆區申請動態內存空間。頭文件：stdlib.h, 返回類型爲空指針，size_t num 爲元素個數，size_t size 爲每個元素的字節大小。

calloc 函數的原型：

void* calloc(size_t num ,size_t size)

2.1calloc 函數的使用

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<errno.h>
int main()
{
	//calloc與malloc的區別
	//1.參數的使用方式不同
	//2.calloc會在返回起始地址之前，把在堆區申請的動態內存空間的每個字節都初始化爲0
	int* p=(int*)calloc(10, sizeof(int));
	if (p == NULL)
	{
		printf("%s\n", strerror(errno));
	}
	else
	{
		int i;
		for (i = 0; i < 10; i++)
		{
			printf("%d ", *(p + i));//0 0 0 0 0 0 0 0 0 0
		}
	}
	//注意要釋放calloc申請的那塊空間
	//還給操作系統，並把指針置爲空
	free(p);
	p = NULL;
	return 0;
}

2.2calloc 與 malloc 的區別

1. 參數的使用方式不同

malloc(單位：字節)：malloc(10 * sizeof(int));或malloc(40)
calloc:calloc(10 , sizeof(int))

2.malloc 的使用效率較高，因爲 calloc 在返回在堆區申請的那塊動態內存的起始地址之前，會將每個字節都初始化爲 0

三、realloc 函數

3.1 什麼是 realloc（）

realloc（）是 C 庫的功能，用於爲已分配的內存塊增加更多的內存大小。C 語言中重新分配的目的是擴展當前的存儲塊，同時保留原始內容。realloc（）函數有助於通過 malloc 或 calloc 函數減少先前分配的內存大小。realloc 代表內存的重新分配。

在 C 中 realloc 的語法：

ptr = realloc (ptr,newsize);

上面的語句在變量 newsize 中分配具有指定大小的新內存空間。執行完函數後，指針將返回到存儲塊的第一個字節。新的大小可以大於或小於以前的內存。我們不能確定新分配的塊是否將指向與先前存儲塊相同的位置。

C 語言中的 realloc 函數將在新區域中複製所有先前的數據。它確保數據將保持安全。

例如：

#includeint main () {
   char *ptr;
   ptr = (char *) malloc(10);
   strcpy(ptr, "Programming");
   printf(" %s,  Address = %un", ptr, ptr);

   ptr = (char *) realloc(ptr, 20); //ptr is reallocated with new size
   strcat(ptr, " In 'C'");
   printf(" %s,  Address = %un", ptr, ptr);
   free(ptr);
   return 0;
}

3.2 如何使用 realloc（）

下面的 C 語言程序演示瞭如何在 C 語言中使用 realloc 來重新分配內存。

#include <stdio.h>
#include <stdlib.h>
    int main() {
        int i, * ptr, sum = 0;
        ptr = malloc(100);
        if (ptr == NULL) {
            printf("Error! memory not allocated.");
            exit(0);
        }
        
        ptr = realloc(ptr,500);
    if(ptr != NULL)
           printf("Memory created successfullyn");
           
    return 0;

    }

C 示例中的 realloc 結果：

Memory created successfully

每當重新分配導致操作失敗時，它都會返回空指針，並且先前的數據也將被釋放。

• 1、函數原型：void *realloc(void *ptr,size_f size);ptr 是指向需要修改的內存塊的指針，size 是請求修改的大小

• 2、realloc 用來修改已分配的內存塊的大小

• 3、如果調整成功，返回值是調整大小後內存的起始位置；如果失敗，則返回 NULL，所以要對返回值進行判空。

• 4、在擴大內存空間時會出現的兩種情況：

（1）ptr 所指向的內存後有足夠的內存空間用來擴展

（2）ptr 所指向的內存後沒有足夠的內存空間用來擴展

則在堆上重新找一個大小合適的連續空間來使用，這樣函數返回的是一個新的內存地址。如果新的內存空間申請成功，則會將 ptr 所指向的內存中的內容拷貝到新的內存空間中，ptr 所指向的內存會被釋放，返回新的內存地址；如果不成功，ptr 所指向的內存不會被釋放，函數返回 NULL。

• 5、p = realloc(ptr,size)函數返回值不爲空時，釋放內存不需要寫 free(ptr), 只需要寫free(p)

• 6、申請的內存空間不會進行初始化

四、free 函數

• 1、用來釋放動態開闢的內存

• 2、函數原型：void free(void *ptr); 指針參數是指向 malloc 等函數動態申請的內存地址，這塊內存釋放後會返還給堆，雖然指針指向這塊區域，但可以重新分配這塊數據

• 3、一般來說，free 釋放的是最新開闢的一個內存空間如果程序中 malloc 了，但是沒有 free，則會造成內存泄漏（即在程序運行過程中，系統會一直被申請內存，造成可用內存不斷減少）

• 4、在 free 之後，需要將 ptr 再次置空，即 ptr = NULL;，如果不置空，後面程序如果通過 ptr 會再次訪問到已經釋放 / 無效的 / 已經被回收再利用的內存。

• 5、free 不能同時釋放一塊內存。

在使用以上函數時，需要加頭文件 #include <stdlib.h>

將 free 與 malloc 函數的聯用情況：

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <string.h>
int main()
{
  int* p = (int*)malloc(40);
  int* ptr = p;
  if (ptr == NULL)
  {
  printf("%s\n", strerror(errno));
  return 1;
  }
  //使用
    //自行添加使用的代碼！！
  //釋放
  free(p);  
  p = NULL;
}

在這個代碼中，就是將 malloc 函數與 free 函數初步聯用！！所以才能更合理的分配內存！！

但是在 malloc 函數與 free 函數聯用的情況，由於代碼的不規範，也會出現或多或少的錯誤！！

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <string.h>
int test ()
{
  int* p= (int*)malloc(40);
  if (p == NULL)
  {
  printf("%s\n", strerror(errno));
  return 1;
  }
 
  //使用
  if (1)
  {
  //某個成立的條件！
  return 2;
  }
  //釋放
  free(p);
  p = NULL;
}//該段代碼，存在內存泄露的問題！
int main()
{
  test();
  return 0;

其實，在該段代碼中，可能出現內存泄漏的問題！！

原因在於：在該段代碼中：

//使用
  if (1)
  {
  //某個成立的條件！
  return 2;
  }

如果條件成立，直接返回該值，但並不會繼續執行代碼，導致，後續的釋放（// 釋放 free(p); p = NULL;）出現問題！

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/3vuYNUytfIPWUPMNS3VvCQ