Chinaunix
標(biāo)題: 一個(gè)基于內(nèi)存池的buddy系統(tǒng)實(shí)現(xiàn) 的算法分析 [打印本頁(yè)]
作者: liu090 時(shí)間: 2011-12-22 08:51
標(biāo)題: 一個(gè)基于內(nèi)存池的buddy系統(tǒng)實(shí)現(xiàn) 的算法分析
提到buddy 就會(huì)想起linux 下的物理內(nèi)存的管理 ,這里的memory pool 上實(shí)現(xiàn)的 buddy 系統(tǒng)
和linux 上按page 實(shí)現(xiàn)的buddy系統(tǒng)有所不同的是,他是按照字節(jié)的2的n次方來做block的size
實(shí)現(xiàn)的機(jī)制中主要的結(jié)構(gòu)如下:
整個(gè)buddy 系統(tǒng)的結(jié)構(gòu):
- struct mem_pool_table
- {
- #define MEM_POOL_TABLE_INIT_COOKIE (0x62756479)
- uint32 initialized_cookie; /* Cookie 指示內(nèi)存已經(jīng)被初始化后的魔數(shù),
- 如果已經(jīng)初始化設(shè)置為0x62756479*/
- uint8 *mem_pool_ptr; /* 指向內(nèi)存池的地址 */
-
- uint32 mem_pool_size; /* 整個(gè)pool 的size,下面是整個(gè)max block size
- 的大小 */
-
- uint32 max_block_size; /* 必須是2的n次方,表示池中最大塊的大小 */
-
- boolean assert_on_empty; /* 如果該值被設(shè)置成TRUE,內(nèi)存分配請(qǐng)求沒有完成,
- 就返回 并輸出出錯(cuò)信息 */
- uint32 mem_remaining; /* 當(dāng)前內(nèi)存池中剩余內(nèi)存字節(jié)數(shù)*/
-
- uint32 max_free_list_index; /* 最大freelist 的下標(biāo),*/
- struct mem_free_hdr_type *free_lists[MAX_LEVELS];
- /* 這個(gè)就是伙伴系統(tǒng)的level數(shù)組*/
- #ifdef FEATURE_MEM_CHECK
- uint32 max_block_requested;
- uint32 min_free_mem; /* 放mem_remaining */
- #endif /* FEATURE_ONCRPC_MEM_CHECK */
- };
這個(gè)結(jié)構(gòu)是包含在free node 或alloc node 中的結(jié)構(gòu):
- typedef struct mem_node_hdr_type
- {
- mem_pool_type pool; /*回指向內(nèi)存池*/
- uint16 check;
- uint8 state; /* bits 0-3 放該node 屬于那1級(jí)
- bit 7 如果置1,表示已經(jīng)分配(not free)
- uint8 fill;
- } mem_node_hdr_type;
其中check 和 fill 都被設(shè)置為某個(gè)pattern
用來檢查該node 的合法性
#define MEM_HDR_CHECK_PATTERN ((uint16)0x3CA4)
#define MEM_HDR_FILL_PATTERN ((uint8)0x5C)
這個(gè)結(jié)構(gòu)就是包含node 類型結(jié)構(gòu)的 free header 的結(jié)構(gòu):
- typedef struct mem_free_hdr_type
- {
- mem_node_hdr_type hdr;
- struct mem_free_hdr_type *next; /* next,prev,用于連接
- free header的雙向 list*/
- struct mem_free_hdr_type *prev;
- } mem_free_hdr_type;
這個(gè)結(jié)構(gòu)就是包含node 類型結(jié)構(gòu)的 alloc header 的結(jié)構(gòu):
已分配的mem 的node 在內(nèi)存中就是這樣表示的
- typedef struct mem_alloc_hdr_type
- {
- mem_node_hdr_type hdr;
- #ifdef FEATURE_MEM_CHECK_OVERWRITE
- uint32 in_use_size;
- #endif
- } mem_alloc_hdr_type;
其中用in_use_size 來表示如果請(qǐng)求分配的size 所屬的level上實(shí)際用了多少
比如申請(qǐng)size=2000bytes, 按size to level 應(yīng)該是2048,實(shí)際in_use_size
為2000,剩下48byte 全部填充為某一數(shù)值,然后在以后free 是可以check
是否有overwite 到著48byte 中的數(shù)值,一般為了速度,只 檢查8到16byte
另外為什么不把這剩下的48byte 放到freelist 中其他level 中呢,這個(gè)可能
因?yàn)楸緛韇uddy 系統(tǒng)的缺點(diǎn)就是容易產(chǎn)生碎片,這樣的話就更碎了
關(guān)于free or alloc node 的示意圖:
假設(shè)
最小塊為2^4=16,著是由mem_alloc_hdr_type (12byte)決定的, 實(shí)際可分配4byte
如果假定最大max_block_size =1024,
如果pool 有mem_free_hdr_type[0]上掛了兩個(gè)1024的block node
上圖是free node, 下圖紫色為alloc node
接下來主要是buddy 系統(tǒng)的操作主要包括pool init , mem alloc ,mem free
pool init :
1. 將實(shí)際pool 的大小去掉mem_pool_table 結(jié)構(gòu)大小后的size 放到
mem_pool_size, 并且修改實(shí)際mem_pool_ptr指向前進(jìn)mem_pool_table
結(jié)構(gòu)大小的地址
2. 接下來主要將mem_pool_size 大小的內(nèi)存,按最大塊掛到free_lists 上
level 為0的list 上,然后小于該level block size 部分,繼續(xù)掛大下一
級(jí),循環(huán)到全部處理完成 (感覺實(shí)際用于pool的size ,應(yīng)該為減去
mem_pool_table 的大小,然后和最大塊的size 對(duì)齊,這樣比較好,
但沒有實(shí)際測(cè)試過)
mem alloc:
這部分相當(dāng)簡(jiǎn)單,先根據(jù)請(qǐng)求mem的size ,實(shí)際分配時(shí)需要加上mem_alloc_hdr_type
這12byte ,然后根據(jù)調(diào)整后的size,計(jì)算實(shí)際應(yīng)該在那個(gè) level上分配,如果有相應(yīng)級(jí)
很簡(jiǎn)單,直接返回,如果沒有,一級(jí)一級(jí)循環(huán)查找,找到后,把省下的部分,在往下一級(jí)
一級(jí)插入到對(duì)應(yīng)級(jí)的freelist 上
mem free:
其中free 的地址,減去12 就可以獲得mem_alloc_hdr_type 結(jié)構(gòu)
然后確定buddy 在該被free block 前,還是后面, 然后合并buddy,
循環(huán)尋找上一級(jí)的buddy ,有就再合并,只到最大block size 那級(jí)
關(guān)于這個(gè)算法,在<<The Art of Computer Programming>> vol 1,的
動(dòng)態(tài)存儲(chǔ)分配中有描述,對(duì)于那些只有OSAL 的小系統(tǒng),該算法相當(dāng)有用
| 歡迎光臨 Chinaunix (http://www.72891.cn/) |
Powered by Discuz! X3.2 |