c malloc/free 初探

我雖然完成了 simple os kernel, 也支援不少特性, 不過卻沒有實作記憶體管理的部份, 該是補上它了, 沒有記憶體管理也能寫 os kernel 哦? 也許你會有這樣的疑惑, 是的, 對於一個學習用的 os kernel, 是可以的。

operating systems design and implementation 4.2.2 提到: 記憶體管理可以用 bit map 或是 linked list 實作, bit map 在 bare metal programming for stm32f4 - discovery: using c++ std::vector 提過了, 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 指向的地方。

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 那塊記憶體位址。

fig 2: char *p1 = malloc(2);

fig3, fig4 則展示了繼續再要 4 bytes, 6 bytes 之後的變化。

fig 3: char *p2 = malloc(4);

fig 4: char *p3 = malloc(6);

到這邊沒什麼特別的變化, 如果在這時候 free (p1) 會怎麼樣?


free(p1);

free(p1); 之後, p1 這塊就空出來了, 所以之前的 free area 就和這塊串起來了。freep 指向的位址也改變了。

如果 free(p1) 再接著 free(p3) 會怎麼樣呢? p3 會和前面那塊 free area 合起來。


free(p1); free(p3);

如果 free(p1) 再接著 free(p2) 會怎麼樣呢? p2 會和後面那塊 p1 合起來。

free(p1); free(p2);

由於 malloc/free 組合起來的情形幾乎是無窮無盡, 我無法列舉所有情形, 這邊討論的幾個情境應當可以幫助理解程式碼。

這位同學也有類似的筆記:
https://embedded2015.hackpad.com/Lab-42-Mini-ARM-OS-uUoMN3XWZdb

最後我得告訴你, 這個不能用來當作管理 os 記憶體的 code, 因為 linked list 需要記住的是被要去的記憶體而不僅僅只是 free 的記憶體, 這樣在這個 process 結束之後, 才能歸還這些記憶體。你辛苦的理解並沒有白費, 弄懂它還是有很大的參考價值。

ref:

有關 malloc 是不是 thread safe 的討論:

總結一下: malloc 是不是 thread safe 要看實作, 大部分系統都會有 thread safe 的版本, 但還是要看手冊的說明。

list 1 是 linux/glibc 的實作, 看起來是 thread safe。

list 1 man malloc
To avoid corruption in multithreaded applications, mutexes are used internally to protect the memory-man‐
agement data structures employed by these functions. In a multithreaded application in which threads
simultaneously allocate and free memory, there could be contention for these mutexes. To scalably handle
memory allocation in multithreaded applications, glibc creates additional memory allocation arenas if mutex
contention is detected. Each arena is a large region of memory that is internally allocated by the system
(using brk(2) or mmap(2)), and managed with its own mutexes.

u-boot/common/malloc_simple.c
common/dlmalloc.c , Void_t* mALLOc(bytes) size_t bytes;
各實作一個 malloc() 有需要也可以參考。

人體汽肛 - 風馳電掣, 人車一體

blog 文章

2015年6月5日星期五