02.21 如何實現一個malloc函數

一、概述

1、malloc簡介

函數所在頭文件：<stdlib.h>

函數原型是：void *malloc (size_t n)

函數功能：在內存的動態存儲區中分配一個長度為size的連續空間。其參數是一個無符號整形數，返回值是一個指向所分配的連續存儲域的起始地址的指針。

2、malloc函數使用注意事項

• 申請了內存空間後，必須檢查是否分配成功。
• 當不需要再使用申請的內存時，記得釋放；釋放後應該把指向這塊內存的指針指向NULL，防止程序後面不小心使用了它。
• malloc和free函數應該配對使用。如果申請後不釋放，就是內存洩露；如果無故釋放那就是什麼也沒有做。釋放只能一次，如果釋放兩次及兩次以上會出現錯誤。
• 越界使用動態分配的存儲塊，尤其是越界賦值，可能引起非常嚴重的後果，通常會破壞程序的運行系統，可能造成本程序或者整個計算機系統垮臺。

3、本文的目的

一直很想親手實現一個malloc函數，不僅僅是鍛鍊自己的編程能力，對指針的駕馭能力，而且也是為了解除自己對malloc函數的疑惑--為什麼使用malloc函數有上述的注意事項？要想知道原因，只有自己查閱源碼，或者自己編寫功能類似的源碼，而筆者選用了後者。

二、本程序實現機制

1、塊控制頭部

塊控制頭部結構體定義如下所示：

typedef struct{
unsigned char is_available; /* whether blcok is avaiable */
unsigned int prior_blocksize; /* size of prior block */
unsigned int current_blocksize; /* block size */
}mem_control_block;
 

每申請一個內存空間，無論大小（char、short、long）都將其命名為"Block"。在分配一個Block的時候，在堆區（heap）首先存放的是Block的控制塊，然後才是有效的數據區。可以想象，假設我們申請一個char型大小的空間，實際上在堆區佔據了“sizeof(char)+sizeof(mem_control_block)”。就是通過Block的頭部控制塊將堆區連成一個鏈表，通過這個鏈表可以遍歷整個堆區的每一個塊。

is_avilable標記內存塊是否被分配，是否可用。prior_blocksize保存了前一個塊的大小，current_blocksize保存了當前塊的實際有效數據空間大小。有了current_blocksize，我們可以從前向後遍歷整個堆區；而有了prior_blocksize，我們可以從後向前遍歷整個堆區。也就是說，這個控制塊頭部使我們為堆區建立了一個雙向鏈表，以便於管理。

2、malloc

調用malloc函數時，它沿連接表從前向後，尋找一個沒有被佔用的，而且大到足以滿足用戶請求所需要的內存塊。在尋找過程中，分三種情況。

第一種情況，倘若可用而且大小剛好合適，那麼直接將此塊返回就完成了分配。

第二種情況，倘若可用而且超過了所需要的內存塊並且還能容納一個新塊的控制頭部，這個時候就將此塊一分為二。將分配給用戶的那塊內存的is_available置0（不再可用），然後將此塊的有效數據區首地址作為函數值返回。而新塊的控制頭部要進行賦值（只有含有頭部的塊才能稱的上一個塊），沒有控制頭部的塊不能進行管理。

第三種情況，倘若可用內存塊的空間小於需要的空間，或者雖然超過了但是不能騰出一個控制頭部，最終的處理都是跳過改塊，移動到鏈表的下一塊進行新一輪的比較。

3、free

free函數用於內存塊的回收，當不用的內存塊調用此函數釋放空間的時候，將is_available置1（可以重新分配）。接下來要做的就是整合內存碎片。由於可能多次malloc函數，產生了很多的內存碎片，在釋放一個塊的時候，不僅要標記此塊為“可用”。另外，還需要試著將此塊前後的塊進行合併，這樣才能為將來申請更大的空間做好準備。

4、malloc_init

初始化函數，主要是確定堆區的起始位置、大小和結束地址，也就是確定堆區的邊界。我們申請的內存塊必須在堆區內，不得超出邊界，否則會修改其他的數據。

另外，還需要對堆區進行初始化，建立第一個內存塊（初始化頭部控制結構體）。顯然，這個塊是一個完整的塊，也是一次能分配最大內存空間的塊。之所以進行初始化，原因還是沒有頭部控制結構體的塊無法進行管理。

三、代碼及解釋

1、malloc_init

 1 /**
 2 * @brief Initializes malloc's gloabl varialbe and head of heap memory 
 3 * @param None 
 4 * @retval None
 5 */
 6 void malloc_init(void)
 7 {
 8 mem_control_block * mcb = NULL;
 9 
10 /* confirm heap's start address */
11 managed_memory_start = (unsigned int)malloc_addr; 

12 /* confirm heap's size */
13 managed_memory_size = malloc_size;
14 /*confirm heap's end address */
15 managed_memory_end = managed_memory_start + managed_memory_size;
16 
17 /* make mcb point to heap's start address */ 
18 mcb = (mem_control_block *)managed_memory_start;
19 /*the first blcok is avaialbe */
20 mcb->is_available = 1;
21 /*there is no block before the first block */
22 mcb->prior_blocksize = 0;
23 /*the first block's block size is difference of between heap's size and control block */ 
24 mcb->current_blocksize = managed_memory_size - sizeof(mem_control_block);
25 /* Initialize done */
26 has_initialized = 1;
27 }

2、malloc

 1 /**
 2 * @brief Dynamic distribute memory function
 3 * @param numbytes: what size you need 
 4 * @retval a void pointer to the distribute first address
 5 */ 
 6 void * malloc(unsigned int numbytes)
 7 {
 8 unsigned int current_location,otherbck_location;
 9 /* This is the same as current_location, but cast to a memory_control_block */
10 mem_control_block * current_location_mcb = NULL,* other_location_mcb = NULL;
11 /* varialbe for saving return value and be set to 0 until we find something suitable */
12 void * memory_location = NULL;
13 /* current dividing block size */
14 unsigned int process_blocksize;
15 
16 /* Initialize if we haven't already done so */
17 if(! has_initialized) {
18 malloc_init();
19 }
20 
21 /* Begin searching at the start of managed memory */
22 current_location = managed_memory_start;
23 /* Keep going until we have searched all allocated space */
24 while(current_location != managed_memory_end){
25 /* current_location and current_location_mcb point to the same address. However, 
26 * current_location_mcb is of the correct type, so we can use it as a struct. current_location 
27 * is a void pointer so we can use it to calculate addresses.
28 */ 

29 current_location_mcb = (mem_control_block *)current_location;
30 /* judge whether current block is avaiable */
31 if(current_location_mcb->is_available){
32 /* judge whether current block size exactly fit for the need */
33 if((current_location_mcb->current_blocksize == numbytes)){
34 /* It is no longer available */ 
35 current_location_mcb->is_available = 0; 
36 /* We own it */
37 memory_location = (void *)(current_location + sizeof(mem_control_block));
38 /* Leave the loop */
39 break;
40 /* judge whether current block size is enough for dividing a new block */
41 }else if(current_location_mcb->current_blocksize >= numbytes + sizeof(mem_control_block)){
42 /* It is no longer available */ 
43 current_location_mcb->is_available = 0;
44 /* because we will divide current blcok,before we changed current block size,we should
45 * save the integral size.
46 */
47 process_blocksize = current_location_mcb->current_blocksize;
48 /* Now blcok size could be changed */
49 current_location_mcb->current_blocksize = numbytes;
50 
51 /* find the memory_control_block's head of remaining block and set parameter,block of no
52 * parameter can't be managed. 
53 */
54 other_location_mcb = (mem_control_block *)(current_location + numbytes \\
55 + sizeof(mem_control_block));
56 /* the remaining block is still avaiable */
57 other_location_mcb->is_available = 1;
58 /* of course,its prior block size is numbytes */
59 other_location_mcb->prior_blocksize = numbytes;
60 /* its size should get small */
61 other_location_mcb->current_blocksize = process_blocksize - numbytes \\
62 - sizeof(mem_control_block);
63 
64 /* find the memory_control_block's head of block after current block and \\
65 * set parameter--prior_blocksize. 
66 */
67 otherbck_location = current_location + process_blocksize \\
68 + sizeof(mem_control_block); 
69 /* We need check wehter this block is on the edge of managed memeory! */
70 if(otherbck_location != managed_memory_end){
71 other_location_mcb = (mem_control_block *)(otherbck_location);
72 /* its prior block size has changed! */
73 other_location_mcb->prior_blocksize = process_blocksize\\
74 - numbytes - sizeof(mem_control_block);
75 }
76 /*We own the occupied block ,not remaining block */ 
77 memory_location = (void *)(current_location + sizeof(mem_control_block));
78 /* Leave the loop */ 

79 break;
80 } 
81 }
82 /* current block is unavaiable or block size is too small and move to next block*/
83 current_location += current_location_mcb->current_blocksize \\
84 + sizeof(mem_control_block);
85 }
86 /* if we still don't have a valid location,we'll have to return NULL */
87 if(memory_location == NULL) {
88 return NULL;
89 }
90 /* return the pointer */
91 return memory_location; 
92 }

此函數流程圖

3、free

 1 /**
 2 * @brief free your unused block 
 3 * @param firstbyte: a pointer to first address of your unused block
 4 * @retval None
 5 */ 
 6 void free(void *firstbyte) 
 7 {
 8 unsigned int current_location,otherbck_location;
 9 mem_control_block * current_mcb = NULL,* next_mcb = NULL,* prior_mcb \\
10 = NULL,* other_mcb = NULL;
11 /* Backup from the given pointer to find the current block */
12 current_location = (unsigned int)firstbyte - sizeof(mem_control_block);
13 current_mcb = (mem_control_block *)current_location;
14 /* Mark the block as being avaiable */
15 current_mcb->is_available = 1;
16 
17 /* find next block location */
18 otherbck_location = current_location + sizeof(mem_control_block) \\
19 + current_mcb->current_blocksize;
20 /* We need check wehter this block is on the edge of managed memeory! */
21 if(otherbck_location != managed_memory_end){
22 /* point to next block */
23 next_mcb = (mem_control_block *)otherbck_location;
24 /* We need check whether its next block is avaiable */ 
25 if(next_mcb->is_available){
26 /* Because its next block is also avaiable,we should merge blocks */
27 current_mcb->current_blocksize = current_mcb->current_blocksize \\
28 + sizeof(mem_control_block) + next_mcb->current_blocksize;
29 
30 /* We have merge two blocks,so we need change prior_blocksize of
31 * block after the two blocks,just find next block location. 
32 */
33 otherbck_location = current_location + sizeof(mem_control_block) \\
34 + current_mcb->current_blocksize;
35 /* We need check wehter this block is on the edge of managed memeory! */
36 if(otherbck_location != managed_memory_end){
37 other_mcb = (mem_control_block *)otherbck_location;
38 /* its prior block size has changed! */
39 other_mcb->prior_blocksize = current_mcb->current_blocksize;
40 }
41 }
42 }
43 
44 /* We need check wehter this block is on the edge of managed memeory! */ 

45 if(current_location != managed_memory_start){
46 /* point to prior block */
47 prior_mcb = (mem_control_block *)(current_location - sizeof(mem_control_block)\\
48 - current_mcb->prior_blocksize);
49 /* We need check whether its prior block is avaiable */ 
50 if(prior_mcb->is_available){
51 /* Because its prior block is also avaiable,we should merge blocks */
52 prior_mcb->current_blocksize = prior_mcb->current_blocksize \\
53 + sizeof(mem_control_block) + current_mcb->current_blocksize;
54 
55 /* We have merge two blocks,so we need change prior_blocksize of
56 * block after the two blocks,just find next block location. 
57 */
58 otherbck_location = current_location + sizeof(mem_control_block) \\
59 + current_mcb->current_blocksize;
60 /* We need check wehter this block is on the edge of managed memeory! */
61 if(otherbck_location != managed_memory_end){
62 other_mcb = (mem_control_block *)otherbck_location;
63 /* its prior block size has changed! */
64 other_mcb->prior_blocksize = prior_mcb->current_blocksize;
65 }
66 }
67 }
68 }

知乎：

釋放一個已分配的數據塊，只是對此數據塊以及其前後數據塊的控制塊頭部進行調整，並沒有對實際有效數據區域（用戶可見的區域）進行初始化操作，也就是說數據區域中的數據保持不變。

四、實現過程中易出現的Bug

我們管理堆，靠的就是頭部控制塊。不管是分配還是釋放，都是通過修改頭部控制塊的信息來實現堆鏈表的改變，從而達到從堆區中分配一塊內存空間給用戶，或者將一個內存塊釋放為重新可用。分配過程中的將大塊一分為二，其實就是增加一個控制塊頭部；釋放過程中的將兩個連續可用塊合併到一起，實際上就是減少一個控制塊頭部。

堆棧的分配和釋放，在我們改變堆棧控制頭部的信息之前，一定要檢查塊是否是已經位於堆區之外（如果你確定這個塊一定在堆內，可以省去檢查代碼）。倘若不去核查，而直接更改堆內存數據，有可能會更改堆區之外的數據，這是非常危險的。

五、測試結果

1、初始化建立第一個塊成功

2、支持在第一個塊上分割出一個用戶塊

3、用戶塊釋放之後，可以和前後的可用塊合併

4、釋放後的塊可以重新用於分配

5、支持在一個大的可用塊中分出一個較小的用戶塊，伴隨著一個新的較小塊的產生

6、找不到合適的塊分配給用戶了，返回空地址

六、目前本程序的應用以及展望

1、目前本程序的應用

操作系統的動態分配內存函數malloc的實現方法與本文差別還是很大的。目前本程序不支持操作系統的動態內存分配，但是可以在單片機的動態內存管理上使用。

使用方法就是一開始為單片機定義一個固定位置、固定大小的堆區，然後將堆區的起始地址和大小作為宏參數傳遞給Rewrite_malloc_init函數中，並進行初始化。接下來，就可以調用malloc和free對內存進行動態分配和管理。

2、展望

本程序的malloc函數，在沒有足夠的堆空間分配給用戶時，就直接以NULL返回給用戶。如果可能的話，在操作系統中，可以繼續從操作系統中申請堆空間（sbrk函數），然後再進行分配。　

七、探秘malloc函數使用注意事項

1、使用malloc函數，注意對不用的空間進行釋放

顯然，每申請一個用戶空間都會引起可用堆區的減少。如果只申請不釋放，就會導致可用堆區不斷減少，到最後有可能就沒有空間分配給新的用戶需要。

2、釋放只能一次，重複釋放有可能產生錯誤

多次釋放同一用戶空間，有可能不會出現錯誤；但是，也有可能會出現錯誤。也就是說，多次釋放產生的結果是難以預測的。下面展示一個錯誤的釋放例程。

/**
 * @brief Test malloc function 
 * @param None 
 * @retval int
 */
int main(void)
{
 int * p1,* p2,* p3;

 memset((void *)heap,0,HEAPSIZE);
 malloc_init();

 p1 = (int *)malloc(sizeof(int)); 
 p2 = (int *)malloc(sizeof(int)); 
 p3 = (int *)malloc(sizeof(int)); 

 free((void *)p2);
 free((void *)p1);
 free((void *)p2);

 while(1); 

 return 0;
}

解釋：

可以肯定的是，p1、p2、p3這三個塊對應的塊大小都是相同的。一個塊的大小，包含一個頭部（sizeof(mem_control_block) = 12Byts）和有效數據區（4 Bytes），所以總共16個bytes。

當第一次釋放p2的時候，p2控制塊的is_avaialbe變為1（重新可用）。當釋放p1的時候，會將p1和p2整合到一起，這個時候p2對應的塊就被註銷了（注意塊頭部的信息還在內存中，只不過p1的塊大小變大，將來沿著鏈表遍歷時，會將這個塊跳過）。當再次釋放p2的時候，由於控制頭部信息還在，所以還會再進行一次p1和p2塊的整合，結果將p1塊的大小設置成更大的，而超出了p1塊實際擁有的空間。

因此重複釋放可能導致“塊頭部控制結構體”的錯誤修改，而導致塊管理信息錯誤，喪失堆區管理功能。