一個基于內(nèi)存池的buddy系統(tǒng)實現(xiàn) 的算法分析

liu090

   提到buddy 就會想起linux 下的物理內(nèi)存的管理 ,這里的memory pool 上實現(xiàn)的 buddy 系統(tǒng)
和linux 上按page 實現(xiàn)的buddy系統(tǒng)有所不同的是,他是按照字節(jié)的2的n次方來做block的size

實現(xiàn)的機制中主要的結(jié)構(gòu)如下:

整個buddy 系統(tǒng)的結(jié)構(gòu):

1. struct mem_pool_table
   
2. {
   
3. #define MEM_POOL_TABLE_INIT_COOKIE (0x62756479)
   
4.   uint32 initialized_cookie; /* Cookie 指示內(nèi)存已經(jīng)被初始化后的魔數(shù),
   
5.                                      如果已經(jīng)初始化設置為0x62756479*/
   
6.   uint8 *mem_pool_ptr; /* 指向內(nèi)存池的地址 */
   
7.     
   
8.   uint32 mem_pool_size; /* 整個pool 的size,下面是整個max block size
   
9.                                     的大小 */
   
10.     
    
11.   uint32 max_block_size; /* 必須是2的n次方,表示池中最大塊的大小 */
    
12.     
    
13.   boolean assert_on_empty; /* 如果該值被設置成TRUE,內(nèi)存分配請求沒有完成,
    
14.                                    就返回 并輸出出錯信息 */
    
15. 
    
16.   uint32 mem_remaining; /* 當前內(nèi)存池中剩余內(nèi)存字節(jié)數(shù)*/
    
17.                                                 
    
18.   uint32 max_free_list_index; /* 最大freelist 的下標,*/
    
19. 
    
20.   struct mem_free_hdr_type     *free_lists[MAX_LEVELS];
    
21.                                  /* 這個就是伙伴系統(tǒng)的level數(shù)組*/
    
22. 
    
23. #ifdef FEATURE_MEM_CHECK
    
24.   uint32 max_block_requested;
    
25.   uint32 min_free_mem; /* 放mem_remaining */
    
26. #endif /* FEATURE_ONCRPC_MEM_CHECK */
    
27. };

這個結(jié)構(gòu)是包含在free node 或alloc node 中的結(jié)構(gòu):

1. typedef struct mem_node_hdr_type
   
2. {
   
3.   mem_pool_type pool; /*回指向內(nèi)存池*/
   
4.   uint16 check;
   
5.   uint8 state; /* bits 0-3 放該node 屬于那1級
   
6.                             bit 7 如果置1,表示已經(jīng)分配(not free)
   
7.   uint8 fill;
   
8. } mem_node_hdr_type;

其中check 和 fill 都被設置為某個pattern
用來檢查該node 的合法性
#define MEM_HDR_CHECK_PATTERN ((uint16)0x3CA4)
#define MEM_HDR_FILL_PATTERN ((uint8)0x5C)

這個結(jié)構(gòu)就是包含node 類型結(jié)構(gòu)的 free header 的結(jié)構(gòu):

1. typedef struct mem_free_hdr_type
2. {
3. mem_node_hdr_type hdr;
4. struct mem_free_hdr_type *next; /* next,prev,用于連接
5. free header的雙向 list*/
6. struct mem_free_hdr_type *prev;
7. } mem_free_hdr_type;

這個結(jié)構(gòu)就是包含node 類型結(jié)構(gòu)的 alloc header 的結(jié)構(gòu):
已分配的mem 的node 在內(nèi)存中就是這樣表示的

1. typedef struct mem_alloc_hdr_type
   
2. {
   
3.    mem_node_hdr_type hdr;
   
4. 
   
5. #ifdef FEATURE_MEM_CHECK_OVERWRITE
   
6.    uint32     in_use_size;
   
7. #endif
   
8. 
   
9. } mem_alloc_hdr_type;

其中用in_use_size 來表示如果請求分配的size 所屬的level上實際用了多少
比如申請size=2000bytes, 按size to level 應該是2048,實際in_use_size
為2000,剩下48byte 全部填充為某一數(shù)值,然后在以后free 是可以check
是否有overwite 到著48byte 中的數(shù)值,一般為了速度,只 檢查8到16byte

另外為什么不把這剩下的48byte 放到freelist 中其他level 中呢,這個可能
因為本來buddy 系統(tǒng)的缺點就是容易產(chǎn)生碎片,這樣的話就更碎了

關于free or alloc node 的示意圖:

假設

最小塊為2^4=16,著是由mem_alloc_hdr_type (12byte)決定的, 實際可分配4byte

如果假定最大max_block_size =1024,

如果pool 有mem_free_hdr_type[0]上掛了兩個1024的block node

上圖是free node, 下圖紫色為alloc node

接下來主要是buddy 系統(tǒng)的操作主要包括pool init , mem alloc ,mem free

pool init :
 1. 將實際pool 的大小去掉mem_pool_table 結(jié)構(gòu)大小后的size 放到
     mem_pool_size, 并且修改實際mem_pool_ptr指向前進mem_pool_table
     結(jié)構(gòu)大小的地址
 2.  接下來主要將mem_pool_size 大小的內(nèi)存,按最大塊掛到free_lists 上
    level 為0的list 上,然后小于該level block size 部分,繼續(xù)掛大下一
    級,循環(huán)到全部處理完成  (感覺實際用于pool的size ,應該為減去
    mem_pool_table 的大小,然后和最大塊的size 對齊,這樣比較好,
    但沒有實際測試過)
   
   
mem alloc:
    這部分相當簡單,先根據(jù)請求mem的size ,實際分配時需要加上mem_alloc_hdr_type
這12byte ,然后根據(jù)調(diào)整后的size,計算實際應該在那個 level上分配,如果有相應級
很簡單,直接返回,如果沒有,一級一級循環(huán)查找,找到后,把省下的部分,在往下一級
一級插入到對應級的freelist 上

mem free:
     其中free 的地址,減去12 就可以獲得mem_alloc_hdr_type 結(jié)構(gòu)
     然后確定buddy 在該被free block 前,還是后面, 然后合并buddy,
     循環(huán)尋找上一級的buddy ,有就再合并,只到最大block size 那級



關于這個算法,在<<The Art  of Computer Programming>> vol 1,的
動態(tài)存儲分配中有描述,對于那些只有OSAL 的小系統(tǒng),該算法相當有用