一个基于内存池的buddy系统实现 的算法分析

liu090

   提到buddy 就会想起linux 下的物理内存的管理 ,这里的memory pool 上实现的 buddy 系统
和linux 上按page 实现的buddy系统有所不同的是,他是按照字节的2的n次方来做block的size

实现的机制中主要的结构如下:

整个buddy 系统的结构:

1. struct mem_pool_table
   
2. {
   
3. #define MEM_POOL_TABLE_INIT_COOKIE (0x62756479)
   
4.   uint32 initialized_cookie; /* Cookie 指示内存已经被初始化后的魔数,
   
5.                                      如果已经初始化设置为0x62756479*/
   
6.   uint8 *mem_pool_ptr; /* 指向内存池的地址 */
   
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,内存分配请求没有完成,
    
14.                                    就返回 并输出出错信息 */
    
15. 
    
16.   uint32 mem_remaining; /* 当前内存池中剩余内存字节数*/
    
17.                                                 
    
18.   uint32 max_free_list_index; /* 最大freelist 的下标,*/
    
19. 
    
20.   struct mem_free_hdr_type     *free_lists[MAX_LEVELS];
    
21.                                  /* 这个就是伙伴系统的level数组*/
    
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. };

这个结构是包含在free node 或alloc node 中的结构:

1. typedef struct mem_node_hdr_type
   
2. {
   
3.   mem_pool_type pool; /*回指向内存池*/
   
4.   uint16 check;
   
5.   uint8 state; /* bits 0-3 放该node 属于那1级
   
6.                             bit 7 如果置1,表示已经分配(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)

这个结构就是包含node 类型结构的 free header 的结构:

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;

这个结构就是包含node 类型结构的 alloc header 的结构:
已分配的mem 的node 在内存中就是这样表示的

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 全部填充为某一数值,然后在以后free 是可以check
是否有overwite 到着48byte 中的数值,一般为了速度,只 检查8到16byte

另外为什么不把这剩下的48byte 放到freelist 中其他level 中呢,这个可能
因为本来buddy 系统的缺点就是容易产生碎片,这样的话就更碎了

关于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 系统的操作主要包括pool init , mem alloc ,mem free

pool init :
 1. 将实际pool 的大小去掉mem_pool_table 结构大小后的size 放到
     mem_pool_size, 并且修改实际mem_pool_ptr指向前进mem_pool_table
     结构大小的地址
 2.  接下来主要将mem_pool_size 大小的内存,按最大块挂到free_lists 上
    level 为0的list 上,然后小于该level block size 部分,继续挂大下一
    级,循环到全部处理完成  (感觉实际用于pool的size ,应该为减去
    mem_pool_table 的大小,然后和最大块的size 对齐,这样比较好,
    但没有实际测试过)
   
   
mem alloc:
    这部分相当简单,先根据请求mem的size ,实际分配时需要加上mem_alloc_hdr_type
这12byte ,然后根据调整后的size,计算实际应该在那个 level上分配,如果有相应级
很简单,直接返回,如果没有,一级一级循环查找,找到后,把省下的部分,在往下一级
一级插入到对应级的freelist 上

mem free:
     其中free 的地址,减去12 就可以获得mem_alloc_hdr_type 结构
     然后确定buddy 在该被free block 前,还是后面, 然后合并buddy,
     循环寻找上一级的buddy ,有就再合并,只到最大block size 那级



关于这个算法,在<<The Art  of Computer Programming>> vol 1,的
动态存储分配中有描述,对于那些只有OSAL 的小系统,该算法相当有用