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