错别字，关系 -> 管理。
想观察伙伴系统的效果，可以跳过libc/用户态，写个简单的kernel module验证。
本帖最后由 nswcfd 于 2016-03-02 12:04 编辑
把楼主的例子修改一下
$ cat brk.c#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
void *p0, *p, *lastp;
void *b0, *b, *lastb;
lastb = b0 = sbrk(0);
lastp = p0 = NULL;
#define do_alloc(x) do { \
p = malloc(x); \
if (!p0) lastp = p0 = p; \
b = sbrk(0);\
printf("p=%p, p-lastp=%08x, p-p0=%08x, b=%p, b-lastb=%08x, b-b0=%08x\n", \
p, p-lastp, p-p0, b, b-lastb, b-b0); \
lastp = p; \
lastb = b;\
} while (0)
printf("sbrk(0) is %p\n", b0);
#define K *1024
do_alloc(1 K);
do_alloc(2 K);
do_alloc(4 K);
do_alloc(8 K);
do_alloc(16 K);
do_alloc(32 K);
do_alloc(64 K);
do_alloc(128 K);
return 0;
}$ ./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) = ?
可见，整个过程中，只发生了一次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。
可能我的理解有误，所以我想先明确以下几点：
第一，os解决碎片或者空洞问题，是解决虚存地址空间的碎片，还是解决物理地址空间的碎片？我一直认为是为了解决虚存地址的碎片。因为用户一般是申请虚存上连续的地址，物理地址不连续没关系，换句话说物理地址碎片再多也没关系。
第二，mmap 或brk只是分配虚存地址空间，而并没有映射真正的物理空间是吗？
第三，我的理解slab只是缓存固定大小的内核结构，一般的的brk的大小都是用户随意指定的，slab中怎么可能有刚好符合大小的块？
看来需要学习的太多太多了。
回复 10# nswcfd
2. linux尽可能的lazy，把page的分配推迟到缺页中断
3. 如果跳过libc直接使用brk，所有的地址和大小都是page对齐的，可以认为跟slab没有关系
1. 这个话题有点大，有一些是用来解决（或降低）物理碎片的问题，例如XXX_MOVEABLE （http://blog.csdn.net/dog250/article/details/6108028）
本帖最后由 Buddy_Zhang1 于 2016-03-04 14:28 编辑
如果您想研究伙伴系统如何分配物理页,我可以给您一个测试代码来了解.
#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;
for(current_order = order ; current_order < MAX_ORDER ; current_order++) {
int size = 1 << current_order;
if(list_empty(&area->free_list))
continue;
page = list_entry(area->free_list.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.lru,&area->free_list);
set_page_order(&page,current_order);
area->nr_free++;
}
break;
}
/* Get page */
if(!PageBuddy(page))
printk(KERN_INFO "Get page from buddy System\n");
}
最近工作比较忙，没上来看。非常感谢你的耐心解答，我刚好在看相关的书。对你讲的大概明白了一些。等我看完书再来仔细研读的的回答。
其实，我一直有误解：
1. 之前一直认为伙伴系统是为了解决虚存碎片的，现在才发现它其实是解决物理碎片的。所以我的例子打印出来的是虚存地址，本身和伙伴没有直接关系。但我还是有疑问，书中提到，一般情况下，分配的空间在物理地址上也是连续的，为啥在物理地址也要连续，因为有页表映射，我觉得物理地址不连续也没关系啊，只要虚拟地址连续即可，难道一些特定场合必须要求物理地址也连续？DMA是要求连续物理地址的，这个我知道。不知道理解的对不对。
2. 看到struct page结构，里面的list成员以及lru成员。我具体怎么知道这个list是什么list，因为同样是list却可以连入任何list里面，lru是什么lru，是clean list还是dirty list，书上说通过flag来区分，还有比如zone->pageset->pcp->list,这其实就是page list，这时的page里的list就是zone->pageset->pcp的链表吗？这时page里的lru又是什么，会是null？
回复 17# 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->pcp->list,这其实就是page list，这时的page里的list就是zone->pageset->pcp的链表吗？这时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.free_list); /* 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);
else
list_add(&page->lru,&pcp->lists);
pcp->count++;
3. 如果这个 struct page 属于 SLUB 分配器,那么 struct page 的 lru 就会被加入到 struct kmem_cache->node.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.partial);
{:yxh45:}
膜拜，你怎么可以研究这么细，学习的路还很长。以后要多请教。加个好友先。回复 19# Buddy_Zhang1