本篇文章講述了如何基於C實現一個簡單的內存分配器。

這是一篇入門級別的文章，不會涉及過深的內存分配演算法

及其相關實現。我們的目的是實現一個可以正常工作的內存分配器，但是它的性能和內存的利用率都不是最優的。我們將會實現 malloc(),calloc(),realoc(),free() 四個函數。

翻譯自：Memory Allocators 101 - Write a simple memory allocator

1. 什麼是內存管理器

  • 進程是如何向內核申請內存的？
  • 已申請的內存是由誰來管理的，內核？庫函數？還是應用程序？
  • 在heap上到底存在什麼？
  • 堆內存可以擴展嗎？

除了我們即將討論的內存分配器，還有如下幾種的存在：

  • dlmalloc – General purpose allocator
  • ptmalloc2 – glibc
  • jemalloc – FreeBSD and Firefox
  • tcmalloc – Google
  • libumem – Solaris

每個內存分配器都說自己可以快速分配內存、可擴展而且高效。但並不是所有的分配器都適用於我們的應用程序。像那些對內存異常渴求的應用程序來說，它的性能很大程度上依賴於內存分配器的性能。

2. 進程地址空間由什麼構成

在實現內存分配器之前，需要先了解一下Linux的進程地址空間：

每個Linux都有一個地址空間，邏輯上由以下五部分組成：

  • text：包含了形成程序可執行代碼的機器指令。它是由編譯器和彙編器把C、C++或者其他程序的源碼轉化為機器碼產生的。通常，代碼段是只讀的
  • data：包含了所有（已初始化的）的程序變數、字元串、數字和其他數據的存儲
  • bss：包含了所有未初始化的靜態數據，這些數據將被初始化為0
  • heap：包含了進程動態申請的內存
  • stack：包含了局部變數，函數參數，指針拷貝

正如我們圖中所看到的，heap是向上增長的，stack是向下增長的。在有些時候，我們把data, bss 和 heap 統稱為數據段。heap的頂部，被一個brk(break) 指針標示，在heap申請內存的時候，需要請求操作系統增加brk。同樣，在heap上釋放內存的時候需要請求操作系統減小brk。

在Linux /Unix操作系統中，有一個sbrk的系統調用可以讓我們實現修改brk指針

  • 調用sbrk(0)可以返回當前brk指針的地址
  • 調用sbrk(x),brk指針增加x位元組，內存被申請
  • 調用sbrk(-x),brk指針減小x位元組，內存被釋放

3.malloc()

malloc(size)函數申請 size位元組的內存並且返回已申請內存的地址。

void *malloc(size_t size)
{
void *block;
block = sbrk(size);
if (block == (void*) -1)
return NULL;
return block;
}

上述代碼調用了sbrk() ，成功的話，新申請的內存將位於heap的頂部。

問題的關鍵在於：該如何釋放這部分內存？

free(ptr) 函數可以釋放ptr指針所指向的內存，該ptr指針由malloc()，calloc()，realloc() 等調用成功返回。

但是想要釋放一塊內存的的話，我們需要知道這塊內存的地址(指針) 以及這塊內存的大小(size)。在當前的情況下，我們必須要把已申請內存塊的地址以及大小保存下來。

在解決這個問題之前，需要先明確 freeing memory 和 releasing memory的區別：

  • Freeing a block of memory does not necessarily mean we release memory back to OS. It just means that we keep the block marked as free. This block marked as free may be reused on a later malloc() call. Since memory not at the end of heap cant be released.

目前為止，對於每塊申請的內存，我們需要知道：

  • 該內存塊的size
  • 該內存塊是否是free的

要實現上述要求，需要給每一塊申請的內存添加一個header_t的數據結構：

struct header_t {
size_t size;
unsigned is_free;
};

另外，我們還無法保證我們使用malloc() 申請的內存是連續的。假設進程調用了其他的sbrk() , 或者在我們申請的內存塊之間有一段mmap() 映射的內存。我們需要一種方式來遍歷我們所申請的內存，對於每塊使用malloc()申請的內存，我們把它放在一個鏈表中。header_t 的數據結構和內存塊的鏈表示意圖如下所示：

struct header_t {
size_t size;
unsigned is_free;
struct header_t *next;
};

保存鏈表的head和tail來對鏈表進行追蹤：

struct header_t *head, *tail；

使用一個簡單的線程鎖來保證我們的內存分配器是線程安全的。

pthread_mutex_t global_malloc_lock;

基於以上討論，新的malloc()函數實現如下：

void *malloc(size_t size)
{
size_t total_size;
void *block;
struct header_t *header;
if (!size)
return NULL;
pthread_mutex_lock(&global_malloc_lock);
header = get_free_block(size);
if (header) {
header->is_free = 0;
pthread_mutex_unlock(&global_malloc_lock);
return (void*)(header + 1);
}
total_size = sizeof(struct header_t) + size;
block = sbrk(total_size);
if (block == (void*) -1) {
pthread_mutex_unlock(&global_malloc_lock);
return NULL;
}
header = block;
header->size = size;
header->is_free = 0;
header->next = NULL;
if (!head)
head = header;
if (tail)
tail->next = header;
tail = header;
pthread_mutex_unlock(&global_malloc_lock);
return (void*)(header + 1);
}

struct header_t *get_free_block(size_t size)
{
struct header_t *curr = head;
while(curr) {
if (curr->is_free && curr->size >= size)
return curr;
curr = curr->next;
}
return NULL;
}

我們分析以下上述代碼：

如果所申請內存的size為0，返回NULL

Acquire Lock，遍歷內存塊組成的鏈表，查找是否有滿足size並且標記為free的內存塊。如果找到了，將該內存塊標記為non-free，Release Lock，返回該內存快的地址。如果沒有找到符合條件的內存塊，那麼我們從heap的頂部重新申請新的內存塊，內存的大小: total_size = sizeof(struct header_t) + size，然後調用sbrk(total_size)修改brk指針。

4.free()

free() 首先要確定當前要釋放的內存塊是否位於heap的頂部（鏈表的尾部）。如果是的話，release it to the OS. 如果不是的話，標記為free，便於以後重用。

void free(void *block)
{
struct header_t *header, *tmp;
void *programbreak;

if (!block)
return;
pthread_mutex_lock(&global_malloc_lock);
header = (struct header_t*)block - 1;

programbreak = sbrk(0);
if ((char*)block + header->size == programbreak) {
if (head == tail) {
head = tail = NULL;
} else {
tmp = head;
while (tmp) {
if(tmp->next == tail) {
tmp->next = NULL;
tail = tmp;
}
tmp = tmp->next;
}
}
sbrk(0 - sizeof(struct header_t) - header->size);
pthread_mutex_unlock(&global_malloc_lock);
return;
}
header->is_free = 1;
pthread_mutex_unlock(&global_malloc_lock);
}

5. calloc()

calloc(num, nsize) 函數為一個長度為num，元素大小為nsize的數組申請內存，數組所有內存初始化為0，返回該數組的地址。

void *calloc(size_t num, size_t nsize)
{
size_t size;
void *block;
if (!num || !nsize)
return NULL;
size = num * nsize;
/* check mul overflow */
if (nsize != size / num)
return NULL;
block = malloc(size);
if (!block)
return NULL;
memset(block, 0, size);
return block;
}

6. realloc()

realloc() 將當前申請的內存塊的大小修改為指定的size。

void *realloc(void *block, size_t size)
{
struct header_t *header;
void *ret;
if (!block || !size)
return malloc(size);
header = (struct header_t*)block - 1;
if (header->size >= size)
return block;
ret = malloc(size);
if (ret) {

memcpy(ret, block, header->size);
free(block);
}
return ret;
}

參考鏈接：

https://arjunsreedharan.org/post/148675821737/memory-allocators-101-write-a-simple-memory?

arjunsreedharan.org

arjun024/memalloc?

github.com圖標
推薦閱讀：
相关文章