接着上一篇博文：Linux下进程内存管理之malloc和sbrk 的知识来讲一下自己动手写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();//返回第一个空闲空间的起始地址,没有则返回NULL
void* free_list_next(void *node);//返回node的后一个空间空间，没有则返回NULL<pre name="code" class="cpp">void* <pre name="code" class="cpp">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 node
123 if(NULL == free_list_begin())//如果没有空闲空间
124 {
125 void* res = my_malloc_new(size);
126 free_list_head = res;
127 return res + 8;
128 }
129 else
130 {
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 else
153 {
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 else
208 {
209 size = *((int*)first);
210 second = first + size;
211 }
212 }
213 return;
214 }
好了，整个代码就讲完了。我已经把代码放在了csdn上，大家可以下载：
点击打开链接
相关资源：自己编写的malloc源码
