内存分配的小例子请教

nswcfd

错别字，关系 -> 管理。

nswcfd

想观察伙伴系统的效果，可以跳过libc/用户态，写个简单的kernel module验证。

nswcfd

把楼主的例子修改一下

$ cat brk.c

1. #include <unistd.h>
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. 
   
5. int main(void)
   
6. {
   
7.         void *p0, *p, *lastp;
   
8.         void *b0, *b, *lastb;
   
9. 
   
10.         lastb = b0 = sbrk(0);
    
11.         lastp = p0 = NULL;
    
12. 
    
13. #define do_alloc(x) do { \
    
14.         p = malloc(x); \
    
15.         if (!p0) lastp = p0 = p; \
    
16.         b = sbrk(0);\
    
17.         printf("p=%p, p-lastp=%08x, p-p0=%08x, b=%p, b-lastb=%08x, b-b0=%08x\n", \
    
18.                 p, p-lastp, p-p0, b, b-lastb, b-b0); \
    
19.         lastp = p; \
    
20.         lastb = b;\
    
21. } while (0)
    
22. 
    
23.         printf("sbrk(0) is %p\n", b0);
    
24. 
    
25. #define K *1024
    
26.         do_alloc(1 K);
    
27.         do_alloc(2 K);
    
28.         do_alloc(4 K);
    
29.         do_alloc(8 K);
    
30.         do_alloc(16 K);
    
31.         do_alloc(32 K);
    
32.         do_alloc(64 K);
    
33.         do_alloc(128 K);
    
34. 
    
35.         return 0;
    
36. }

复制代码

$ ./brk
sbrk(0) is 0x1262000
p=0x1262010, p-lastp=00000000, p-p0=00000000, b=0x1283000, b-lastb=00021000, b-b0=00021000
p=0x1262420, p-lastp=00000410, p-p0=00000410, b=0x1283000, b-lastb=00000000, b-b0=00021000
p=0x1262c30, p-lastp=00000810, p-p0=00000c20, b=0x1283000, b-lastb=00000000, b-b0=00021000
p=0x1263c40, p-lastp=00001010, p-p0=00001c30, b=0x1283000, b-lastb=00000000, b-b0=00021000
p=0x1265c50, p-lastp=00002010, p-p0=00003c40, b=0x1283000, b-lastb=00000000, b-b0=00021000
p=0x1269c60, p-lastp=00004010, p-p0=00007c50, b=0x1283000, b-lastb=00000000, b-b0=00021000
p=0x1271c70, p-lastp=00008010, p-p0=0000fc60, b=0x1283000, b-lastb=00000000, b-b0=00021000
p=0x7f8c2a495010, p-lastp=292233a0, p-p0=29233000, b=0x1283000, b-lastb=00000000, b-b0=00021000

$ strace ./brk
execve("./brk", ["./brk"], [/* 28 vars */]) = 0
brk(0)                                  = 0xa7e000
mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f977ffe1000
access("/etc/ld.so.preload", R_OK)      = -1 ENOENT (No such file or directory)
open("/etc/ld.so.cache", O_RDONLY)      = 3
fstat(3, {st_mode=S_IFREG|0644, st_size=91750, ...}) = 0
mmap(NULL, 91750, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7f977ffca000
close(3)                                = 0
open("/lib64/libc.so.6", O_RDONLY)      = 3
read(3, "\177ELF\2\1\1\3\0\0\0\0\0\0\0\0\3\0>\0\1\0\0\0\360\355\241\245:\0\0\0"..., 832) = 832
fstat(3, {st_mode=S_IFREG|0755, st_size=1922152, ...}) = 0
mmap(0x3aa5a00000, 3745960, PROT_READ|PROT_EXEC, MAP_PRIVATE|MAP_DENYWRITE, 3, 0) = 0x3aa5a00000
mprotect(0x3aa5b8a000, 2093056, PROT_NONE) = 0
mmap(0x3aa5d89000, 20480, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x189000) = 0x3aa5d89000
mmap(0x3aa5d8e000, 18600, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0x3aa5d8e000
close(3)                                = 0
mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f977ffc9000
mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f977ffc8000
mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f977ffc7000
arch_prctl(ARCH_SET_FS, 0x7f977ffc8700) = 0
mprotect(0x3aa5d89000, 16384, PROT_READ) = 0
mprotect(0x3aa541f000, 4096, PROT_READ) = 0
munmap(0x7f977ffca000, 91750)           = 0
brk(0)                                  = 0xa7e000
fstat(1, {st_mode=S_IFCHR|0620, st_rdev=makedev(136, 4), ...}) = 0
mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f977ffe0000
write(1, "sbrk(0) is 0xa7e000\n", 20sbrk(0) is 0xa7e000
)   = 20
brk(0xa9f000)                           = 0xa9f000
write(1, "p=0xa7e010, p-lastp=00000000, p-"..., 89p=0xa7e010, p-lastp=00000000, p-p0=00000000, b=0xa9f000, b-lastb=00021000, b-b0=00021000
) = 89
write(1, "p=0xa7e420, p-lastp=00000410, p-"..., 89p=0xa7e420, p-lastp=00000410, p-p0=00000410, b=0xa9f000, b-lastb=00000000, b-b0=00021000
) = 89
write(1, "p=0xa7ec30, p-lastp=00000810, p-"..., 89p=0xa7ec30, p-lastp=00000810, p-p0=00000c20, b=0xa9f000, b-lastb=00000000, b-b0=00021000
) = 89
write(1, "p=0xa7fc40, p-lastp=00001010, p-"..., 89p=0xa7fc40, p-lastp=00001010, p-p0=00001c30, b=0xa9f000, b-lastb=00000000, b-b0=00021000
) = 89
write(1, "p=0xa81c50, p-lastp=00002010, p-"..., 89p=0xa81c50, p-lastp=00002010, p-p0=00003c40, b=0xa9f000, b-lastb=00000000, b-b0=00021000
) = 89
write(1, "p=0xa85c60, p-lastp=00004010, p-"..., 89p=0xa85c60, p-lastp=00004010, p-p0=00007c50, b=0xa9f000, b-lastb=00000000, b-b0=00021000
) = 89
write(1, "p=0xa8dc70, p-lastp=00008010, p-"..., 89p=0xa8dc70, p-lastp=00008010, p-p0=0000fc60, b=0xa9f000, b-lastb=00000000, b-b0=00021000
) = 89
mmap(NULL, 135168, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f977ffa6000
write(1, "p=0x7f977ffa6010, p-lastp=7f5183"..., 95p=0x7f977ffa6010, p-lastp=7f5183a0, p-p0=7f528000, b=0xa9f000, b-lastb=00000000, b-b0=00021000
) = 95
exit_group(0)                           = ?

nswcfd

可见，整个过程中，只发生了一次brk调用和一次mmap调用。

这次brk（strace版本），heap空间从0xa7e00提升到0xa9f00，增加了0x21000，即132K，足以容纳后续1K ~ 64K的分配。

至于每次分配都多出0x10字节，那应该是libc用于维护各个buffer的管理开销（比如把已分配空间link起来），或者是出于检查越界等操作增加的额外保护空间（red zone）。

最后一次分配128K的时候，现有的brk空间不够了，libc有两种选择，继续brk扩大heap空间（这样的话返回地址跟之前是连续的），或者通过mmap在线性空间里找一段未用的（注意mmap的size同样是132K），这里选择的后者，所以p7一下子跳了很远。

貌似libc有个可配的参数，size小于某个值采取brk策略，大于采取mmap策略。

使用mmap，释放之后可以很容易归还给os；使用brk，如果heap上有漏洞，则空间无法及时归还os。例如p7没有释放，则p1~p6都free的情况下，libc也无法通过brk把p1~p6的空间归还给os。

allkillers

可能我的理解有误，所以我想先明确以下几点：
第一，os解决碎片或者空洞问题，是解决虚存地址空间的碎片，还是解决物理地址空间的碎片？我一直认为是为了解决虚存地址的碎片。因为用户一般是申请虚存上连续的地址，物理地址不连续没关系，换句话说物理地址碎片再多也没关系。
第二，mmap 或brk只是分配虚存地址空间，而并没有映射真正的物理空间是吗？
第三，我的理解slab只是缓存固定大小的内核结构，一般的的brk的大小都是用户随意指定的，slab中怎么可能有刚好符合大小的块？

看来需要学习的太多太多了。
回复 10# nswcfd


   

nswcfd

2. linux尽可能的lazy，把page的分配推迟到缺页中断
3. 如果跳过libc直接使用brk，所有的地址和大小都是page对齐的，可以认为跟slab没有关系
1. 这个话题有点大，有一些是用来解决（或降低）物理碎片的问题，例如XXX_MOVEABLE （http://blog.csdn.net/dog250/article/details/6108028）

Buddy_Zhang1

如果您想研究伙伴系统如何分配物理页,我可以给您一个测试代码来了解.

#include <linux/kernel.h>
#include <linux/mmzone.h>
#include <linux/mm.h>

void TestCase_Get_Buddy_Page(void)
{
    struct pglist_data *pgdat;
    struct zonelist *zonelist;
    struct zone *zone;
    struct free_area *area;
    struct page *page;
    int migratetype;
    int order,current_order;

    pgdat = NODE_DATA(0);
    zonelist = pgdat->node_zonelists;
    migratetype = MIGRATE_MOVABLE;
    order = 4; // alloc 64 page.

    first_zones_zonelist(zonelist,0,NULL,&zone);
    area = &zone->free_area[order];
   
    for(current_order = order ; current_order < MAX_ORDER ; current_order++) {
          int size = 1 << current_order;
         
          if(list_empty(&area->free_list[migratetype]))
                continue;
     
         page = list_entry(area->free_list[migratetype].next,
                                          struct page,lru);
         list_del(&page->lru);
         rmv_page_order(page);
         area->nr_free--;

         while(order < current_order) {
                 area--;
                 current_order--;
                 size >>= 1;
                 list_add(&page[size].lru,&area->free_list[migratetype]);
                 set_page_order(&page[size],current_order);
                 area->nr_free++;
         }
         break;
    }
    /* Get page */
    if(!PageBuddy(page))
       printk(KERN_INFO "Get page from buddy System\n");  
}

allkillers

最近工作比较忙，没上来看。非常感谢你的耐心解答，我刚好在看相关的书。对你讲的大概明白了一些。等我看完书再来仔细研读的的回答。
其实，我一直有误解：
1. 之前一直认为伙伴系统是为了解决虚存碎片的，现在才发现它其实是解决物理碎片的。所以我的例子打印出来的是虚存地址，本身和伙伴没有直接关系。但我还是有疑问，书中提到，一般情况下，分配的空间在物理地址上也是连续的，为啥在物理地址也要连续，因为有页表映射，我觉得物理地址不连续也没关系啊，只要虚拟地址连续即可，难道一些特定场合必须要求物理地址也连续？DMA是要求连续物理地址的，这个我知道。不知道理解的对不对。

2. 看到struct page结构，里面的list成员以及lru成员。我具体怎么知道这个list是什么list，因为同样是list却可以连入任何list里面，lru是什么lru，是clean list还是dirty list，书上说通过flag来区分，还有比如zone->pageset[1]->pcp[0]->list,这其实就是page list，这时的page里的list就是zone->pageset[1]->pcp[0]的链表吗？这时page里的lru又是什么，会是null？

回复 17# Buddy_Zhang1


   

Buddy_Zhang1

回复 18# allkillers


    1. 之前一直认为伙伴系统是为了解决虚存碎片的，现在才发现它其实是解决物理碎片的。所以我的例子打印出来的是虚存地址，本身和伙伴没有直接关系。但我还是有疑问，书中提到，一般情况下，分配的空间在物理地址上也是连续的，为啥在物理地址也要连续，因为有页表映射，我觉得物理地址不连续也没关系啊，只要虚拟地址连续即可，难道一些特定场合必须要求物理地址也连续？DMA是要求连续物理地址的，这个我知道。不知道理解的对不对。

      内核使用 "物理连续或者不连续" 都是根据相应的策略要求使用的,但虚拟地址一定是连续的.
      对于内核空间,只要 ZONE_NOMAL 物理内存充足,一般都使用物理地址和虚拟地址都连续的方式.如果 ZONE_NOMAL 的物理内存吃紧,内核就将 ZONE_HIGHMEM 的物理内存通过不同的方式
      映射到内核空间 3G ~ 4G 虚拟地址其中的某一段上,但这段区域绝对不是 ZONE_NOMAL 对应的虚拟区.
      内核可以使用 vmalloc 去获得虚拟地址连续但物理地址不连续的区域,这些区域的物理地址都属于 ZONE_HIGHMEM.

2. 看到struct page结构，里面的list成员以及lru成员。我具体怎么知道这个list是什么list，因为同样是list却可以连入任何list里面，lru是什么lru，是clean list还是dirty list，书上说通过flag来区分，还有比如zone->pageset[1]->pcp[0]->list,这其实就是page list，这时的page里的list就是zone->pageset[1]->pcp[0]的链表吗？这时page里的lru又是什么，会是null？

     简单的说 struct page 的 lru 成员就是负责被各个内存分配器管理.
     1. 假如这个 struct page 属于 Buddy System,那么内核通过将该 struct page 的 lru 加入到对应的 free_area 链表上,可以参照下面代码;
            struct page *page;  /* Page 已知 */
            struct zone *zone;
            int migratetype;
            int order;

            zone = page_zone(page);
            migratetype = get_pageblock_migratetype(page);
            order = page_order(page);

            list_add(&page->lru,
                    &zone->free_area[order].free_list[migratetype]);   /* page 所属的 free_list */
      2. 加入这个 struct page 属于 PCP(per_cpu_pages) 分配器,也就是 hot 或 cold 页.那么这个 struct page 的 lru 就会加入到 PCP 的 冷热页链表中.可参照下面代码.
           struct page *page; /* 已知 */
           struct zone *zone;
           struct per_cpu_pages *pcp;
           int migratetype;
           int cold = 0; /* 如果这个页属于 hot 页 cold 为0,如果这个页属于 cold 页那么 cold 为 1*/

           zone = page_zone(page);
           migratetype = get_pageblock_migratetype(page);
           pcp = &zone->pageset->pcp;

           if(cold)
                list_add_tail(&page->lru,&pcp->lists[migratetype]);
           else
                list_add(&page->lru,&pcp->lists[migratetype]);
           pcp->count++;

       3. 如果这个 struct page 属于 SLUB 分配器,那么 struct page 的 lru 就会被加入到 struct kmem_cache->node[0].partial 链表里面.可以参照如下代码:
            struct page *page = alloc_page(page);
            struct kmem_cache *cache;

             cache = kmem_cache_create("Buddy",8,8,0,NULL);

             list_add(&page->lru,&cache->node[0].partial);


            
        

allkillers

膜拜，你怎么可以研究这么细，学习的路还很长。以后要多请教。加个好友先。回复 19# Buddy_Zhang1