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

1、關(guān)于malloc相關(guān)的幾個(gè)函數(shù)

關(guān)于malloc我們進(jìn)入Linux man一下就會(huì)得到如下結(jié)果：

也可以這樣認(rèn)為（window下）原型：

extern void *malloc(unsigned int num_bytes);

頭文件：

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

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

不然返回指針NULL

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

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

malloc:

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

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

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

2、malloc和new

new返回指定類型的指針，并且可以自動(dòng)計(jì)算所需要的大小。

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

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

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

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

簡(jiǎn)單的說：

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

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

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

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

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

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

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

頁與地址構(gòu)成

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

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

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

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

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

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

2.2.1內(nèi)存排布

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

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

具體分布如圖所示：

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

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

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

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

Heap內(nèi)存模型：

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

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

brk與sbrk

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

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

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

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

其中rlimt是一個(gè)結(jié)構(gòu)體

struct rlimit
{
  rlimt_t rlim_cur;
  rlim_t rlim_max;
};

每種資源有硬限制和軟限制，并且可以通過setrlimit對(duì)rlimit進(jìn)行有條件限制作為軟限制的上限，非特權(quán)進(jìn)程只能設(shè)置軟限制，且不能超過硬限制

實(shí)現(xiàn)malloc

(1)數(shù)據(jù)結(jié)構(gòu)

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

可以使用如下結(jié)構(gòu)體定義一個(gè)block

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

（2）尋找合適的block

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

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

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

最新評(píng)論