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

1、關于malloc相關的幾個函數(shù)

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

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

extern void *malloc(unsigned int num_bytes);

頭文件：

#include<malloc.h>或者#include<alloc.h>兩者的內(nèi)容是完全一樣的

如果分配成功：則返回指向被分配內(nèi)存空間的指針

不然返回指針NULL

同時，當內(nèi)存不再使用的時候，應使用free()函數(shù)將內(nèi)存塊釋放掉。

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

malloc:

malloc分配的內(nèi)存大小至少為參數(shù)所指定的字節(jié)數(shù)

malloc的返回值是一個指針，指向一段可用內(nèi)存的起始位置，指向一段可用內(nèi)存的起始地址，多次調(diào)用malloc所分配的地址不能有重疊部分，除非某次malloc所分配的地址被釋放掉malloc應該盡快完成內(nèi)存分配并返回（不能使用NP-hard的內(nèi)存分配算法）實現(xiàn)malloc時應同時實現(xiàn)內(nèi)存大小調(diào)整和內(nèi)存釋放函數(shù)（realloc和free）

malloc和free是配對的，如果申請后不釋放就是內(nèi)存泄露，如果無故釋放那就是什么也沒做，釋放只能釋放一次，如果一塊空間釋放兩次或者兩次以上會出現(xiàn)錯誤（但是釋放空指針例外，釋放空指針也等于什么也沒做，所以釋放多少次都是可以的。）

2、malloc和new

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

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

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

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

（1）malloc的返回是void*,如果我們寫成了：p=malloc(sizeof(int));間接的說明了（將void轉化給了int*，這不合理）
（2）malloc的實參是sizeof(int)，用于指明一個整型數(shù)據(jù)需要的大小，如果我們寫成p=(int*)malloc(1),那么可以看出：只是申請了一個一個字節(jié)大小的空間。
（3）malloc只管分配內(nèi)存，并不能對其進行初始化，所以得到的一片新內(nèi)存中，其值將是隨機的。一般意義上：我們習慣性的將其初始化為NULL，當然也可以使用memset函數(shù)。

簡單的說：

malloc函數(shù)其實就是在內(nèi)存中找一片指定大小的空間，然后將這個空間的首地址給一個指針變量，這里的指針變量可以是一個單獨的指針，也可以是一個數(shù)組的首地址，這要看malloc函數(shù)中參數(shù)size的具體內(nèi)容。我們這里malloc分配的內(nèi)存空間在邏輯上是連續(xù)的，而在物理上可以不連續(xù)。我們作為程序員，關注的是邏輯上的連續(xù)，其他的操作系統(tǒng)會幫著我們處理。

下面就來看看malloc具體是怎么實現(xiàn)的。

首先要了解操作系統(tǒng)相關的知識：

虛擬內(nèi)存地址和物理內(nèi)存地址

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

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

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

頁與地址構成

在現(xiàn)代操作系統(tǒng)中，不論是虛擬內(nèi)存還是物理內(nèi)存，都不是以字節(jié)為單位進行管理的，而是以頁為單位。一個內(nèi)存頁是一段固定大小的連續(xù)的連續(xù)內(nèi)存地址的總稱，具體到Linux中，典型的內(nèi)存頁大小為4096 Byte

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

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

內(nèi)存頁與磁盤頁

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

Linux進程級內(nèi)存管理

2.2.1內(nèi)存排布

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

以Linux 64位系統(tǒng)為例。理論上，64bit內(nèi)存地址空間為0x0000000000000000-0xFFFFFFFFFFFFFFF，這是個相當龐大的空間，Linux實際上只用了其中一小部分

具體分布如圖所示：

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

• Code：這是整個用戶空間的最低地址部分，存放的是指令（也就是程序所編譯成的可執(zhí)行機器碼）
• Data：這里存放的是初始化過的全局變量
• BSS：這里存放的是未初始化的全局變量
• Heap：堆，這是我們本文主要關注的地方，堆自底向上由低地址向高地址增長

Mapping Area:這里是與mmap系統(tǒng)調(diào)用相關的區(qū)域。大多數(shù)實際的malloc實現(xiàn)會考慮通過mmap分配較大塊的內(nèi)存空間，本文不考慮這種情況，這個區(qū)域由高地址像低地址增長

Stack:棧區(qū)域，自高地址像低地址增長

Heap內(nèi)存模型：

一般來說，malloc所申請的內(nèi)存主要從Heap區(qū)域分配，來看看Heap的結構是怎樣的。

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

brk與sbrk

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

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

brk將break指針直接設置為某個地址，而sbrk將break從當前位置移動increment所指定的增量。brk在執(zhí)行成功時返回0，否則返回-1并設置為errno為ENOMEM,sbrk成功時返回break移動之前所指向的地址，否則返回（void*）-1;
資源限制和rlimirt

系統(tǒng)為每一個進程所分配的資源不是無限的，包括可映射的空間，因此每個進程有一個rlimit表示當前進程可用的資源上限，這個限制可以通過getrlimit系統(tǒng)調(diào)用得到，下面代碼獲取當前進程虛擬內(nèi)存空間的rlimit

其中rlimt是一個結構體

struct rlimit
{
  rlimt_t rlim_cur;
  rlim_t rlim_max;
};

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

實現(xiàn)malloc

(1)數(shù)據(jù)結構

首先我們要確定所采用的數(shù)據(jù)結構。一個簡單可行方案是將堆內(nèi)存空間以塊的形式組織起來，每個塊由meta區(qū)和數(shù)據(jù)區(qū)組成，meta區(qū)記錄數(shù)據(jù)塊的元信息（數(shù)據(jù)區(qū)大小、空閑標志位、指針等等），數(shù)據(jù)區(qū)是真實分配的內(nèi)存區(qū)域，并且數(shù)據(jù)區(qū)的第一個字節(jié)地址即為malloc返回的地址

可以使用如下結構體定義一個block

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

（2）尋找合適的block

現(xiàn)在考慮如何在block鏈中查找合適的block。一般來說有兩種查找算法：
First fit:從頭開始，使用第一個數(shù)據(jù)區(qū)大小大于要求size的塊所謂此次分配的塊
Best fit:從頭開始，遍歷所有塊，使用數(shù)據(jù)區(qū)大小大于size且差值最小的塊作為此次分配的塊
兩種方式各有千秋，best fit有較高的內(nèi)存使用率（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，這里在遍歷時會更新一個叫l(wèi)ast的指針，這個指針始終指向當前遍歷的block.這是為了如果找不到合適的block而開辟新block使用的。

（3）開辟新的block
如果現(xiàn)有block都不能滿足size的要求，則需要在鏈表最后開辟一個新的block。這里關鍵是如何只使用sbrk創(chuàng)建一個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占據(jù)很大的一塊block，此時，為了提高payload,應該在剩余數(shù)據(jù)區(qū)足夠大的情況下，將其分裂為一個新的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的實現(xiàn)
有了上面的代碼，我們就可以實現(xiàn)一個簡單的malloc.注意首先我們要定義個block鏈表的頭first_block,初始化為NULL；另外，我們需要剩余空間至少有BLOCK_SIZE+8才執(zhí)行分裂操作
由于我們需要malloc分配的數(shù)據(jù)區(qū)是按8字節(jié)對齊，所以size不為8的倍數(shù)時，我們需要將size調(diào)整為大于size的最小的8的倍數(shù)

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

以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。

最新評論