接着上一篇博文：的知识来讲一下自己动手写malloc函数的实现细节。

如果你看了前文应该知道了进程的内存管理和malloc函数的实现原理。实际上malloc函数所分配得到的空间都是利用sbrk函数来得到的，只不过这个函数不应该每次用户调用malloc的时候都调用一次，这样开销太大，也没有必要。所以这里就需要在malloc中加入内存的分配、释放、合并等等操作。

首先需要说明的是，每次通过sbrk函数申请到的空间都是连续的，所以malloc函数需要管理的内存空间也是连续的。只不过随着用户多次的释放和申请，这些空间有的是用户使用状态，有些是用户释放状态：

元数据设计

就如图中所示，在每一段空间中，除了用户申请的空间之外，还需要一部分meta-data来管理该空间。在我的程序中，我把这部分的大小设置为了8个字节。而这8个字节不仅需要存储该段空间的大小，还需要标示下一段空间的起始位置。而我的设计就是前四个字节用来标示该段空间的长度，其中这个长度不仅包括数据段的长度还包括的meta-data的8个字节；而后4个字节用来标示改段空间是正在被用户使用还是空闲状态。

另外还有一个需要注意的地方就是对齐，因为分配对齐的空间开销更小，而且也便于之后的管理。在本程序设计中，我采用的是8字节对齐。比如用户如果申请一个99字节的空间，那么实际分配给他的空间应该是大于99的最小的8的倍数，即104，另外还需要加上8个字节的meta-data，所以总共申请的空间是112个字节。

再说一句题外话，在计算实际分配给用户的空间大小的时候不要使用除法，更有效率的方法是使用移位操作。比如用户需要申请size个字节长度的空间，那么计算实际分配的空间大小可以使用：(((size - 1)>>3)<<3) + 8 + 8得到。

另外还规定一次使用sbrk最少开辟8192字节。

13 #define SPACE_IN_USE 0//用户使用状态 14 #define SPACE_AVAILABLE 1//空闲状态 15 #define MINIMUM_SBRK_SPACE  8192 16  17 #define align8(size)\ 18     size = (((size - 1)>>3)<<3) + 8 25 void* free_list_head; //静态变量，标示动态空间的起始地址

空间链表维护

malloc的另外一个作用就是维护通过sbrk开辟的空间，通过前文描述的元数据，不难发现，这个内存空间其实就是一个链表，这个链表中记录了每一块空间，包括用户正在使用的和没有使用的。为了维护这个这个链表，需要有两个功能函数：

void* free_list_begin();//返回第一个空闲空间的起始地址,没有则返回NULLvoid* free_list_next(void *node);//返回node的后一个空间空间，没有则返回NULLvoid* free_list_begin

() 11 { 12 //if the head is null 13 if(!free_list_head) 14 { 15 return NULL; 16 } 17 else 18 { 19 void* tmp = free_list_head; 20 while(tmp != (void*)sbrk(0)) 21 { 22 int* size = (int*)tmp; 23 int* flag = (int*)(tmp+4);//the flag to indicate whether this space is in use 24 if(*flag == SPACE_AVAILABLE) 25 { 26 return tmp; 27 } 28 else 29 { 30 tmp += *size; 31 } 32 } 33 return NULL; 34 } 35 } 37 void* free_list_next(void *node) 38 { 39 if(!free_list_head || !node) 40 { 41 return NULL; 42 } 43 44 if(node < free_list_head || node > sbrk(0)) 45 { 46 printf("illeagal address\n"); 47 return NULL; 48 } 49 int flag = 0; 50 void *tmp = free_list_head; 51 while(tmp < sbrk(0)) 52 { 53 int* size = (int*)tmp; 54 if(tmp == node) 55 { 56 tmp += *size; 57 break; 58 } 59 tmp += *size; 60 61 } 62 if(tmp == sbrk(0)) 63 { 64 return NULL; 65 } 66 while(tmp < sbrk(0)) 67 { 68 int* size = (int*)tmp; 69 int* flag = (int*)(tmp+4); 70 if((*flag) == SPACE_AVAILABLE) 71 { 72 return tmp; 73 } 74 tmp += (*size); 75 } 76 return NULL; 77 }

my_malloc和my_free函数

79 void*  my_malloc_new(size_t size) 80 { 81     size_t new_size = size; 82     align8(new_size);//对齐 83     new_size += 8;//添加meta_data的空间 84     if(new_size >=  MINIMUM_SBRK_SPACE) 85     { 86         void* res = sbrk(new_size); 87         if((void*)-1 == res) 88         { 89             printf("error occured when allocation space\n"); 90             return NULL; 91         } 92         *((int*)res) = new_size;//前4位设置为长度位 93         *((int*)(res + 4)) = SPACE_IN_USE;//后4位设置为标识位 94         return res; 95     } 96     else 97     { 98         size_t gap = MINIMUM_SBRK_SPACE - new_size; 99         align8(gap);100         gap+=8;101         void* res = sbrk(gap + new_size);102         if((void*)-1 == res)103         {104             printf("error occured when allocating space\n");105             return NULL;106         }107         *((int*)res) = new_size;108         *((int*)(res + 4)) = SPACE_IN_USE;109 110         res += new_size;111         *((int*)res) = gap;112         *((int*)(res + 4)) = SPACE_AVAILABLE;113         res -= new_size;114         return res;115     }116 117 118 }120 void* my_malloc(size_t size)121 {122     //create a new node123     if(NULL == free_list_begin())//如果没有空闲空间124     {125         void* res = my_malloc_new(size);126         free_list_head = res;127         return res + 8;128     }129     else130     {131         void* tmp = free_list_begin();//从free_list中遍历空闲空间132 133         size_t new_size = size;134         align8(new_size);135         new_size += 8;136 137 138         while(tmp != NULL)139         {140             int cur_size = *((int*)tmp);141             if(cur_size >= new_size)142             {143                 if(cur_size >= new_size + 12)//如果当前空闲空间的尺寸比所需分配的空间大12个字节以上，则将这个空间划分成两个空间144                 {                           145                     *((int*)tmp) = new_size;//一个部分分配给申请用户146                     *((int*)(tmp + 4)) = SPACE_IN_USE;147 148                     void* new_tmp = tmp + new_size; //另一部分重新成为一个空闲空间149                     *((int*)(new_tmp)) = cur_size - new_size;150                     *((int*)(new_tmp + 4)) = SPACE_AVAILABLE;151                 }152                 else153                 {154                     *((int*)(tmp + 4)) = SPACE_IN_USE;155                 }156                 157                 return tmp + 8;158             }159             tmp = free_list_next(tmp);160         }161         162         void* res = my_malloc_new(size);163         return res + 8;164     }165 }167 void my_free(void *ptr)168 {169     if(ptr < free_list_head || sbrk(0) < ptr)170     {171         printf("illegal pointer\n");172         return;173     }174     printf("free ptr:%p\n", ptr);175     int* flag = (int*)(ptr - 4);176     *flag = SPACE_AVAILABLE;177     return;178 }

my_free函数很简单，就是将meta-data中的符号位置为SPACE_AVAILABLE。而my_malloc的逻辑就是通过free_list_begin()和free_list_next()来遍历整个空闲空间，如果有足够的空间则分配，如果没有则利用sbrk重新分配。

coalesce_free_list

还有一个问题需要注意的就是，当用户多次使用my_malloc和my_free之后，会出现碎片问题，即存在多块连续的，空闲的空间，coalesce_free_list函数就是将这些连续的空闲空间重新合并成一个空间

180 void coalesce_free_list()181 {182     void *first, *second, *tail;183     first = free_list_begin();184     int tmp_size = *((int*)first);185     int size = tmp_size;186     second = first + tmp_size;187     tail = sbrk(0);188 189     while(second < tail && first < tail)190     {191         while(second < tail && *((int*)(second + 4)) == SPACE_AVAILABLE )192         {193             tmp_size = *((int*)second);194             size += tmp_size;195             second += tmp_size;196         }197         *((int*)first) = size;198         first = second;199         while(first < tail && *((int*)(first + 4)) == SPACE_IN_USE )200         {201             first += *((int*)first);202         }203         if(first == tail)204         {205             return;206         }207         else208         {209             size = *((int*)first);210             second = first + size;211         }212     }213     return;214 }

好了，整个代码就讲完了。我已经把代码放在了csdn上，大家可以下载：