Linux内存管理之伙伴系统（建立）

内核使用伙伴系统来解决内存分配引起的外部碎片问题。

一、数据结构描述

结构zone中的free_area数组描述伙伴系统该数组为free_area结构

1. struct zone {  


2. ……  


3.     struct free_area    free_area[MAX_ORDER];  


4. ……  


5. }；  

1. struct free_area {/*链表类型为5类，对于分类为新加入的*/  


2.     struct list_head    free_list[MIGRATE_TYPES];  


3.     unsigned long       nr_free;  


4. };  

下图为伙伴系统在管理区中的表示。

二、伙伴系统的初始化

在初始化物理管理区的时候初始化伙伴系统的，具体实现在下面的函数中：

Start_kernel()->setup_arch()->paging_init()->zone_sizes_init()->free_area_init_nodes()->free_area_init_node()->free_area_init_core()->init_currently_empty_zone()->zone_init_free_lists()

1. /*初始化对应zone中所有order和所有类型的链表*/  


2. static void __meminit zone_init_free_lists(struct zone *zone)  


3. {  


4.     int order, t;  


5.     for_each_migratetype_order(order, t) {  


6.         INIT_LIST_HEAD(&zone->free_area[order].free_list[t]);  


7.         zone->free_area[order].nr_free = 0;  


8.     }  


9. }  

三、伙伴系统中数据初始化

将bootmem分配器中的数据回收到伙伴系统中

start_kernel()->mm_init()->mem_init()

1. void __init mem_init(void)  


2. {  


3.     int codesize, reservedpages, datasize, initsize;  


4.     int tmp;  


5. /*和具体硬件相关*/  


6.     pci_iommu_alloc();  


7.   


8. #ifdef CONFIG_FLATMEM   


9.     BUG_ON(!mem_map);  


10. #endif   


11.     /* this will put all low memory onto the freelists */  


12.     /*释放bootmem中的内存到伙伴系统中，包括bootmem占有的位图 


13.      返回总共释放的页面数**/  


14.     totalram_pages += free_all_bootmem();  


15.   


16.     reservedpages = 0;  


17.     for (tmp = 0; tmp < max_low_pfn; tmp++)  


18.         /* 


19.          * Only count reserved RAM pages: 


20.          */  


21.         if (page_is_ram(tmp) && PageReserved(pfn_to_page(tmp)))  


22.             reservedpages++;  


23.     /*初始化高端内存区，将高端内存区放入伙伴系统中*/  


24.     set_highmem_pages_init();  


25.     /*内核代码段、数据段、初始化端长度*/  


26.     codesize =  (unsigned long) &_etext – (unsigned long) &_text;  


27.     datasize =  (unsigned long) &_edata – (unsigned long) &_etext;  


28.     initsize =  (unsigned long) &__init_end – (unsigned long) &__init_begin;  


29.     /*打印输出各种内存初始化后的信息*/  


30.     printk(KERN_INFO “Memory: %luk/%luk available (%dk kernel code, “  


31.             “%dk reserved, %dk data, %dk init, %ldk highmem)\n”,  


32.         nr_free_pages() << (PAGE_SHIFT-10),  


33.         num_physpages << (PAGE_SHIFT-10),  


34.         codesize >> 10,  


35.         reservedpages << (PAGE_SHIFT-10),  


36.         datasize >> 10,  


37.         initsize >> 10,  


38.         (unsigned long) (totalhigh_pages << (PAGE_SHIFT-10))  


39.            );  


40.   


41.     printk(KERN_INFO “virtual kernel memory layout:\n”  


42.         ”    fixmap  : 0x%08lx – 0x%08lx   (%4ld kB)\n”  


43. #ifdef CONFIG_HIGHMEM   


44.         ”    pkmap   : 0x%08lx – 0x%08lx   (%4ld kB)\n”  


45. #endif   


46.         ”    vmalloc : 0x%08lx – 0x%08lx   (%4ld MB)\n”  


47.         ”    lowmem  : 0x%08lx – 0x%08lx   (%4ld MB)\n”  


48.         ”      .init : 0x%08lx – 0x%08lx   (%4ld kB)\n”  


49.         ”      .data : 0x%08lx – 0x%08lx   (%4ld kB)\n”  


50.         ”      .text : 0x%08lx – 0x%08lx   (%4ld kB)\n”,  


51.         FIXADDR_START, FIXADDR_TOP,  


52.         (FIXADDR_TOP – FIXADDR_START) >> 10,  


53.   


54. #ifdef CONFIG_HIGHMEM   


55.         PKMAP_BASE, PKMAP_BASE+LAST_PKMAP*PAGE_SIZE,  


56.         (LAST_PKMAP*PAGE_SIZE) >> 10,  


57. #endif   


58.   


59.         VMALLOC_START, VMALLOC_END,  


60.         (VMALLOC_END – VMALLOC_START) >> 20,  


61.   


62.         (unsigned long)__va(0), (unsigned long)high_memory,  


63.         ((unsigned long)high_memory – (unsigned long)__va(0)) >> 20,  


64.   


65.         (unsigned long)&__init_begin, (unsigned long)&__init_end,  


66.         ((unsigned long)&__init_end –  


67.          (unsigned long)&__init_begin) >> 10,  


68.   


69.         (unsigned long)&_etext, (unsigned long)&_edata,  


70.         ((unsigned long)&_edata – (unsigned long)&_etext) >> 10,  


71.   


72.         (unsigned long)&_text, (unsigned long)&_etext,  


73.         ((unsigned long)&_etext – (unsigned long)&_text) >> 10);  


74.   


75.     /* 


76.      * Check boundaries twice: Some fundamental inconsistencies can 


77.      * be detected at build time already. 


78.      */  


79. #define __FIXADDR_TOP (-PAGE_SIZE)   


80. #ifdef CONFIG_HIGHMEM   


81.     BUILD_BUG_ON(PKMAP_BASE + LAST_PKMAP*PAGE_SIZE  > FIXADDR_START);  


82.     BUILD_BUG_ON(VMALLOC_END            > PKMAP_BASE);  


83. #endif   


84. #define high_memory (-128UL << 20)   


85.     BUILD_BUG_ON(VMALLOC_START          >= VMALLOC_END);  


86. #undef high_memory   


87. #undef __FIXADDR_TOP   


88.   


89. #ifdef CONFIG_HIGHMEM   


90.     BUG_ON(PKMAP_BASE + LAST_PKMAP*PAGE_SIZE    > FIXADDR_START);  


91.     BUG_ON(VMALLOC_END              > PKMAP_BASE);  


92. #endif   


93.     BUG_ON(VMALLOC_START                >= VMALLOC_END);  


94.     BUG_ON((unsigned long)high_memory       > VMALLOC_START);  


95.   


96.     if (boot_cpu_data.wp_works_ok < 0)  


97.         test_wp_bit();  


98.   


99.     save_pg_dir();  


100.     /*调用zap_low_mappings函数清low_memory的映射，内核线程只访问内核空间是不能访问用户空间的 


101.     ，其实low_memory的映射被设置的部分也就是当初为 


102.      8MB建立的恒等映射填充了临时内核页全局目录的第0项，第1项 


103.      这里将用户空间的页目录项<3G的PGD清0；*/  


104.     zap_low_mappings(true);  


105. }  

1. /** 


2.  * free_all_bootmem – release free pages to the buddy allocator 


3.  * 


4.  * Returns the number of pages actually released. 


5.  */  


6. unsigned long __init free_all_bootmem(void)  


7. {  


8.     return free_all_bootmem_core(NODE_DATA(0)->bdata);  


9. }  

1. static unsigned long __init free_all_bootmem_core(bootmem_data_t *bdata)  


2. {  


3.     int aligned;  


4.     struct page *page;  


5.     unsigned long start, end, pages, count = 0;  


6.   


7.     if (!bdata->node_bootmem_map)  


8.         return 0;  


9.     /*节点内存开始和结束处*/  


10.     start = bdata->node_min_pfn;  


11.     end = bdata->node_low_pfn;  


12.   


13.     /* 


14.      * If the start is aligned to the machines wordsize, we might 


15.      * be able to free pages in bulks of that order. 


16.      */  


17.     aligned = !(start & (BITS_PER_LONG – 1));  


18.   


19.     bdebug(“nid=%td start=%lx end=%lx aligned=%d\n”,  


20.         bdata – bootmem_node_data, start, end, aligned);  


21.     /*用于释放整个bootmem所涉及的内存*/  


22.     while (start < end) {  


23.         unsigned long *map, idx, vec;  


24.   


25.         map = bdata->node_bootmem_map;  


26.         idx = start – bdata->node_min_pfn;/*相对于开始处的偏移*/  


27.         vec = ~map[idx / BITS_PER_LONG];/*vec值为页面分配情况*/  


28.         /*如果开始地址以32位对其、连续的32个页面都没有被分配(空闲),并且 


29.         释放起点以上的32个页面都是合法的(不超过end值)，则释放连续的32个 


30.         页面，即1<<5个页面*/  


31.         if (aligned && vec == ~0UL && start + BITS_PER_LONG < end) {  


32.             int order = ilog2(BITS_PER_LONG);/*32位下为5*/  


33.             /*释放到伙伴系统中*/  


34.             __free_pages_bootmem(pfn_to_page(start), order);  


35.             count += BITS_PER_LONG;/*释放的总页面数更新*/  


36.         } else {  


37.             unsigned long off = 0;  


38.             /*vec!=0表示这个区间存在页面空闲，off为这个区间的下标，从0开始*/   


39.             while (vec && off < BITS_PER_LONG) {  


40.                 if (vec & 1) {/*如果页面空闲*/  


41.                     /*偏移转化为具体的页面*/  


42.                     page = pfn_to_page(start + off);  


43.                     /*一个页面一个页面的释放*/  


44.                     __free_pages_bootmem(page, 0);/*释放单个页面*/  


45.                     count++;/*更新释放页面总数*/  


46.                 }  


47.                 vec >>= 1;/*vec向右移动一位，表示访问下一个页面*/  


48.                 off++;/*偏移加一*/  


49.             }  


50.         }  


51.         start += BITS_PER_LONG;/*偏移向后移动*/  


52.     }  


53.     /*虚拟地址转化为page 


54.     用于释放bdata中的位图所占有的内存*/  


55.     page = virt_to_page(bdata->node_bootmem_map);  


56.     pages = bdata->node_low_pfn – bdata->node_min_pfn;  


57.       


58.     /*计算bootmem分配器中所使用的页面数,即位图使用的页面数*/  


59.     pages = bootmem_bootmap_pages(pages);  


60.     count += pages;/*释放的总页面数加*/  


61.     while (pages–)/*每次释放一个页面，释放 


62.         总共的pages个页面*/  


63.         __free_pages_bootmem(page++, 0);  


64.   


65.     bdebug(“nid=%td released=%lx\n”, bdata – bootmem_node_data, count);  


66.   


67.     return count;/*返回释放的总页面数*/  


68. }  

1. /* 


2.  * permit the bootmem allocator to evade page validation on high-order frees 


3.  */  


4. void __meminit __free_pages_bootmem(struct page *page, unsigned int order)  


5. {  


6.     if (order == 0) {  


7.         __ClearPageReserved(page);  


8.         set_page_count(page, 0);/*设置页面的引用位为0*/  


9.         set_page_refcounted(page);/*设置页面的引用位为1*/  


10.         __free_page(page);/*释放单个页面到伙伴系统中*/  


11.     } else {  


12.         int loop;  


13.           


14.         /*这个不是很明白，可能和特定的体系相关???*/  


15.         prefetchw(page);  


16.         for (loop = 0; loop < BITS_PER_LONG; loop++) {  


17.             struct page *p = &page[loop];  


18.   


19.             if (loop + 1 < BITS_PER_LONG)  


20.                 prefetchw(p + 1);  


21.             __ClearPageReserved(p);  


22.             set_page_count(p, 0);  


23.         }  


24.   


25.         set_page_refcounted(page);/*设置页面的引用计数为1*/  


26.         /*这里具体释放到那个类型里面， 


27.         要看page的里面具体的东西，也就是 


28.         可以用相关函数来获取他所属的类型*/  


29.         __free_pages(page, order);/*释放order个页面*/  


30.     }  


31. }  

1. void __init set_highmem_pages_init(void)  


2. {  


3.     struct zone *zone;  


4.     int nid;  


5.   


6.     for_each_zone(zone) {  


7.         unsigned long zone_start_pfn, zone_end_pfn;  


8.   


9.         if (!is_highmem(zone))/*验证是否属于高端内存区域中*/  


10.         /*如果不属于，将不执行下面的操作*/  


11.             continue;  


12.   


13.         zone_start_pfn = zone->zone_start_pfn;  


14.         zone_end_pfn = zone_start_pfn + zone->spanned_pages;  


15.         /*返回zone中的node的id*/  


16.         nid = zone_to_nid(zone);  


17.         printk(KERN_INFO “Initializing %s for node %d (%08lx:%08lx)\n”,  


18.                 zone->name, nid, zone_start_pfn, zone_end_pfn);  


19.         /*将区间中的内存放到伙伴系统中*/  


20.         add_highpages_with_active_regions(nid, zone_start_pfn,  


21.                  zone_end_pfn);  


22.     }  


23.     totalram_pages += totalhigh_pages;  


24. ｝  

1. void __init add_highpages_with_active_regions(int nid, unsigned long start_pfn,  


2.                           unsigned long end_pfn)  


3. {  


4.     struct add_highpages_data data;  


5.   


6.     data.start_pfn = start_pfn;  


7.     data.end_pfn = end_pfn;  


8.     /*对节点中的每个区域进行页面的回收到伙伴系统中*/  


9.     work_with_active_regions(nid, add_highpages_work_fn, &data);  


10. }  

1. /*用指定函数来操作活动区，在高端内存初始化时用了*/  


2. void __init work_with_active_regions(int nid, work_fn_t work_fn, void *data)  


3. {  


4.     int i;  


5.     int ret;  


6.   


7.     for_each_active_range_index_in_nid(i, nid) {  


8.         ret = work_fn(early_node_map[i].start_pfn,  


9.                   early_node_map[i].end_pfn, data);  


10.         if (ret)  


11.             break;  


12.     }  


13. }  

1. static int __init add_highpages_work_fn(unsigned long start_pfn,  


2.                      unsigned long end_pfn, void *datax)  


3. {  


4.     int node_pfn;  


5.     struct page *page;  


6.     unsigned long final_start_pfn, final_end_pfn;  


7.     struct add_highpages_data *data;  


8.   


9.     data = (struct add_highpages_data *)datax;  


10.     /*活动内存区间与指定考虑区间交集*/  


11.     final_start_pfn = max(start_pfn, data->start_pfn);  


12.     final_end_pfn = min(end_pfn, data->end_pfn);  


13.     if (final_start_pfn >= final_end_pfn)  


14.         return 0;  


15.   


16.     for (node_pfn = final_start_pfn; node_pfn < final_end_pfn;  


17.          node_pfn++) {  


18.         if (!pfn_valid(node_pfn))/*验证页面是否有效*/  


19.             continue;  


20.         page = pfn_to_page(node_pfn);/*将下标转换为具体的页面*/  


21.         /*初始化页面的count值，将页面释放到伙伴系统中*/  


22.         add_one_highpage_init(page, node_pfn);  


23.     }  


24.   


25.     return 0;  


26.   


27. }  

1. static void __init add_one_highpage_init(struct page *page, int pfn)  


2. {  


3.     /*ClearPageReserved清除了该页面flag中的reserved标志，表示该页面属于动态内存*/  


4.     ClearPageReserved(page);  


5.     init_page_count(page);/*设置page的count值为1*/  


6.     __free_page(page);  /*释放页面到伙伴系统*/  


7.     totalhigh_pages++;/*更新高端页面总数*/  


8. }  

1. void zap_low_mappings(bool early)  


2. {  


3.     int i;  


4.   


5.     /* 


6.      * Zap initial low-memory mappings. 


7.      * 


8.      * Note that “pgd_clear()” doesn’t do it for 


9.      * us, because pgd_clear() is a no-op on i386. 


10.      */  


11.     /*这个函数很简单，就是把前面我们在arch/x86/kernel/head_32.S中设置的页全局目录的前若干项清零 


12.     。这若干项到底是多少 


13.      不错，0xc0000000>>22 & 1023= 768，这些也全局目录项代表虚拟地址前3G的页面，也就是所谓的用户区 


14.      ，我们在这里把它全清零了。*/  


15.     for (i = 0; i < KERNEL_PGD_BOUNDARY; i++) {  


16. #ifdef CONFIG_X86_PAE   


17.         set_pgd(swapper_pg_dir+i, __pgd(1 + __pa(empty_zero_page)));  


18. #else   


19.         set_pgd(swapper_pg_dir+i, __pgd(0));  


20. #endif   


21.     }  


22.   


23.     if (early)  


24.         __flush_tlb();  


25.     else  


26.         flush_tlb_all();  


27. }  

到此，伙伴系统已经建立并且里面存放了应有的内存数据。要从伙伴系统中分配内存，必须要有分配和释放机制。后面总结具体的分配和释放工作。