operating systems design and implementation 4.2.2 提到: 内存管理可以用 bit
map 或是 linked list 实作, bit map 在 bare metal programming for stm32f4 -
discovery: using c++ std::vector ( http://goo.gl/Asx92Q ) 提过了, linked list
的实作可以先来看看 c 的 malloc/free。别担心, 不用直接去看 glibc 里头的大怪物,
the c programming language 8.7 a storage allocator 提供了一个范例:
mem.h
1 #ifndef MEM_H
2 #define MEM_H
3
4 typedef unsigned char u8;
5 typedef unsigned int u32;
6
7 void *mymalloc(u32 size);
8 void myfree(void *ptr);
9 void print_memarea();
10
11 namespace LIST
12 {
13 typedef long Align;
14 union Header
15 {
16 struct
17 {
18 union Header *ptr;
19 u32 size;
20 }s;
21 Align x;
22 };
23
24 }
25
26 #endif
mem.cpp
1 #include "mem.h"
2
3
4 #ifdef STM32
5
6 #include "k_stdio.h"
7 using namespace DS;
8 #define NL "\r\n"
9
10 #else
11 #include <stdio.h>
12 #include <unistd.h> // sbrk
13
14 #define NL "\n"
15
16 #endif
17
18
19 // #define DEBUG_MSG
20 #ifdef DEBUG_MSG
21 #define PF(...) printf(...)
22 #else
23 #define PF(...)
24 #endif
25
195 namespace
196 {
197 LIST::Header base;
198 LIST::Header *freep = 0;
199 }
200
201 namespace LIST
202 {
203 const int NALLOC = 1024; // minimum units to request
204
205 void free(void *ap)
206 {
207 Header *bp, *p;
208
209 bp = (Header *)ap -1;
210
211 for (p=freep ; !(bp > p && bp < p->s.ptr) ; p = p->s.ptr)
212 if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))
213 break;
214
215 if (bp + bp->s.size == p->s.ptr)
216 {
217 bp->s.size += p->s.ptr->s.size;
218 bp->s.ptr = p->s.ptr->s.ptr;
219 }
220 else
221 bp->s.ptr = p->s.ptr;
222
223 if (p + p->s.size == bp)
224 {
225 p->s.size += bp->s.size;
226 p->s.ptr = bp->s.ptr;
227 }
228 else
229 p->s.ptr = bp;
230
231 freep = p;
232 }
233
234 Header *morecore(u32 nu)
235 {
236 char *cp;
237 Header *up;
238
239 if (nu < NALLOC)
240 nu = NALLOC;
241 cp = (char *)sbrk(nu*sizeof(Header));
242 if (cp == (char *)(-1))
243 return 0;
244 up = (Header*)cp;
245 up->s.size = nu;
246 free((void*)(up+1));
247 return freep;
248 }
249
250 void *malloc(u32 nbytes)
251 {
252 Header *p, *prevp;
253 Header *morecore(u32);
254 u32 nunits;
255 nunits = (nbytes + sizeof(Header) - 1)/sizeof(Header) + 1;
256
257 if ((prevp = freep) == 0) // no free list yet
258 {
259 base.s.ptr = freep = prevp = &base;
260 base.s.size = 0;
261 }
262 for (p=prevp->s.ptr ; ; prevp = p, p = p->s.ptr)
263 {
264 if (p->s.size >= nunits)
265 {
266 if (p->s.size == nunits)
267 prevp->s.ptr = p->s.ptr;
268 else
269 {
270 p->s.size -= nunits;
271 p += p->s.size;
272 p->s.size = nunits;
273 }
274 freep = prevp;
275 return (void *)(p+1);
276 }
277 if (p == freep)
278 if ((p = morecore(nunits)) == 0)
279 return 0;
280 }
281
282 }
283
284 }
我改写成 c++ 版本 (我爱 c++ 嘛), 没什么更动, 只是加上 namesapce。
linked list 版本搞得我头昏脑胀, 简单的 7 页, 花了我四天的鲁蛇模式研究, 终于有
了些许概念, 并画了好几张 A4 的图来让自己更明白些, 程式很短, 但要理解他们并没有
表面上看来的那么容易。书上的解释实在太不专业了, 一点都不详细, 我很不满意, 这是
要卖钱的书耶。
这个实作版本用了 linked list 纪录了 free memory, 很奇怪, 竟然不是纪录使用过的
memory, 你就知道大师的厉害了, 能想到普通人想不到的作法。而且在第一次呼叫 char
*p1 = malloc(2); 时, 并没有 free memory, 所以透过 sbrk 去要了一个 free memory
area 回来, 再分配这块 memory 给呼叫 malloc 的程式。
而本来应该要有一个 linked list 资料结构来纪录 free memory, 但这里并没有使用额
外的内存来产生这个 linked list, 而是直接在 sbrk 要来的这块内存上使用
linked list。也就是说, 这块要来的内存不只拿来分配给需要的程式, 还顺便用来维
护这个 linked list, 一兼二顾摸蜊仔兼洗裤, 一举两得, 实在厉害。
所以 sbrk 要来的内存会以 Header (mem.h L11 ~ L24) 大小为分配单位, 默认会先要
1024 个 Header 大小。
Header [0]
Header [1]
Header [2]
Header [3]
Header [4]
Header [5]
.
.
.
Header [1021]
Header [1022]
Header [1023]
假设你要了一个 Header, 实际上会配置 2 个 Header 空间, 程式拿到的是第一个
Header 指到的位址, 第 0 个则是用来纪录被要走多少块 Header, free 时需要用这个
Header 的资讯。
注意 freep 指向的地方。
( https://goo.gl/h1qNBo )
fig 1: 第一次呼叫 malloc 时, base/freep 指向的位置, mem.cpp L257~261
在我的平台上 (debian 64 bit) Header 是 16 byte, 所以 malloc(2) 要 2 bytes 只需
要一个 Header 就够了。
执行 char *p1 = malloc(2); 之后的指标布局, 第一次呼叫时, base 会做一个初始化
(ref: fig 1), 而 sbrk 会传回一块内存, 回传给 p1 后, 整个指标会像 fig 2。
malloc(2) 会保留 1022/1023 这两块 Header, 一块是 free 用, 另外一块就是要回传给
呼叫的程式用的 (也就是 p1 的位址), p1 得到的是 1023 那块内存位址。
( https://goo.gl/ALOnro )
fig 2: char *p1 = malloc(2);
fig3, fig4 则展示了继续再要 4 bytes, 6 bytes 之后的变化。
( https://goo.gl/H9YzvC )
fig 3: char *p2 = malloc(4);
( https://goo.gl/xdjGn6 )
fig 4: char *p3 = malloc(6);
到这边没什么特别的变化, 如果在这时候 free (p1) 会怎么样?
( https://goo.gl/JdoQsp )
free(p1);
free(p1); 之后, p1 这块就空出来了, 所以之前的 free area 就和这块串起来了。
freep 指向的位址也改变了。
如果 free(p1) 再接着 free(p3) 会怎么样呢? p3 会和前面那块 free area 合起来。
( https://goo.gl/FMwyqc )
free(p1); free(p3);
如果 free(p1) 再接着 free(p2) 会怎么样呢? p2 会和后面那块 p1 合起来。
( https://goo.gl/x1ebOn )
free(p1); free(p2);
由于 malloc/free 组合起来的情形几乎是无穷无尽, 我无法列举所有情形, 这边讨论的
几个情境应当可以帮助理解程式码。
这位同学也有类似的笔记:
https://embedded2015.hackpad.com/Lab-42-Mini-ARM-OS-uUoMN3XWZdb (
https://goo.gl/luy3Rh )
最后我得告诉你, 这个不能用来当作管理 os 内存的 code, 因为 linked list 需要记
住的是被要去的内存而不仅仅只是 free 的内存, 这样在这个 process 结束之后,
才能归还这些内存。你辛苦的理解并没有白废, 弄懂它还是有很大的参考价值。
ref:
析malloc（）的几种方式 ( http://goo.gl/uKuZub )
存管理幕 ( http://goo.gl/l9SbyS )
// 本文使用 Blog2BBS 自动将Blog文章转成缩址的BBS纯文字 http://goo.gl/TZ4E17 //
blog 版本
http://descent-incoming.blogspot.tw/2015/06/c-mallocfree.html