c語言 malloc函數詳解

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

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是配對的，如果申請后不釋放就是內存泄露，如果無故釋放那就是什么也沒做，釋放只能釋放一次，如果一塊空間釋放兩次或者兩次以上會出現錯誤（但是釋放空指針例外，釋放空指針也等于什么也沒做，所以釋放多少次都是可以的。）

2、malloc和new

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

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

而malloc需要我們自己計算字節數，并且返回的時候要強轉成指定類型的指針。

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分配的內存空間在邏輯上是連續的，而在物理上可以不連續。我們作為程序員，關注的是邏輯上的連續，其他的操作系統會幫著我們處理。

下面就來看看malloc具體是怎么實現的。

首先要了解操作系統相關的知識：

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

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

這種虛擬地址空間的作用主要是簡化程序的編寫及方便操作系統對進程間內存的隔離管理，真實中的進程不太可能如此大的空間，實際能用到的空間大小取決于物理內存的大小。

由于在機器語言層面都是采用虛擬地址，當實際的機器碼程序涉及到內存操作時，需要根據當前進程運行的實際上下文將虛擬地址轉化為物理內存地址，才能實現對內存數據的操作。這個轉換一般由一個叫MMU的硬件完成。

頁與地址構成

在現代操作系統中，不論是虛擬內存還是物理內存，都不是以字節為單位進行管理的，而是以頁為單位。一個內存頁是一段固定大小的連續的連續內存地址的總稱，具體到Linux中，典型的內存頁大小為4096 Byte

所以內存地址可以分為頁號和頁內偏移量。下面以64位機器，4G物理內存，4K頁大小為例，虛擬內存地址和物理內存地址的組成如下：

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

內存頁與磁盤頁

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

Linux進程級內存管理

2.2.1內存排布

明白了虛擬內存和物理內存的關系及相關的映射機制，下面看一下具體在一個進程內是如何排布內存的。

以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往上，是未映射的地址空間，如果訪問這段空間則程序會報錯

brk與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進行有條件限制作為軟限制的上限，非特權進程只能設置軟限制，且不能超過硬限制

實現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;
}

以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持億速云。