这是源码剖析专栏的第二篇文章

主要分成四大模块来剖析：内存管理、设备管理、系统启动和其他部分

其中内存管理分为Bootmem、Buddy System和Slab三部分来阐述，本文主要阐述的是Buddy System启动流程

目录

• • buddy system
  • • free_unused_memmap_node
    • free_all_bootmem_node
    • • register_page_bootmem_info_node
      • free_all_bootmem_core
      • • __free_pages_bootmem
        • __free_page
        • free_hot_page
        • __free_pages_ok
    • free_area

buddy system

系统初始阶段使用bootmem内存分配器，Linux中由于slab分配器执行bootmem的功能，但是slab分配器是在伙伴系统buddy system中实现的，因此，原来由bootmem管理的内存必须由buddy system伙伴系统管理

在主函数中，即

asmlinkage void __init start_kernel(void)
{// ...mem_init();

zone结构体的成员遍历free_area[]数组正是构建伙伴系统的核心数据结构

void __init mem_init(void)
{unsigned int codesize, datasize, initsize;int i, node;

如果有时间希望可以去看看在Bootmem到Buddy System中间做的一些事情，从构造上来说，主要做了以下几件事

• 初始化per_cpu数据
  注册SMP上的启动进程
  进程调度启动程序
  初始化pglist_data的node_zonelists[]成员（备份列表和zone列表）

free_unused_memmap_node

将物理上不存在的页hole(空洞)组织页管理位图中全部记录为不使用

	/* this will put all unused low memory onto the freelists */for_each_online_node(node) {pg_data_t *pgdat = NODE_DATA(node); // 节点描述符free_unused_memmap_node(node, &meminfo);

函数体为

static void __init free_unused_memmap_node(int node, struct meminfo *mi)
{unsigned long bank_start, prev_bank_end = 0;unsigned int i;for_each_nodebank(i, mi, node) {struct membank *bank = &mi->bank[i];bank_start = bank_pfn_start(bank); // 获得bank起始页帧if (bank_start < prev_bank_end) {printk(KERN_ERR "MEM: unordered memory banks.  ""Not freeing memmap.\n");break;}// 此时prev_bank_end是前一个bank的末尾if (prev_bank_end && prev_bank_end != bank_start)  // 检查一致性,如果不一致，说明存在空洞free_memmap(node, prev_bank_end, bank_start);prev_bank_end = bank_pfn_end(bank); // 本bank的末尾}
}

检查一致性,如果不一致，说明存在空洞，调用free_memmap

static inline void
free_memmap(int node, unsigned long start_pfn, unsigned long end_pfn)
{struct page *start_pg, *end_pg;unsigned long pg, pgend;// 变为页指针的虚拟地址start_pg = pfn_to_page(start_pfn);end_pg = pfn_to_page(end_pfn);// 以页为单位排列pg = PAGE_ALIGN(__pa(start_pg));pgend = __pa(end_pg) & PAGE_MASK;if (pg < pgend)free_bootmem_node(NODE_DATA(node), pg, pgend - pg);
}

找到了相应的页帧为空洞，并且在页管理位图中设为了0，因此下面要释放对应的page结构体

free_all_bootmem_node

在页管理位图中记录为“不使用”之后，在本函数进行释放，使其能在伙伴系统中管理空白页

		if (pgdat->node_spanned_pages != 0) // 页不为空totalram_pages += free_all_bootmem_node(pgdat);}

函数体为

unsigned long __init free_all_bootmem_node(pg_data_t *pgdat)
{register_page_bootmem_info_node(pgdat); // return free_all_bootmem_core(pgdat->bdata); // 将bootmem设置中的所有数据迁移到伙伴系统
}

register_page_bootmem_info_node

对具有元信息(附加信息)的各页指定属性，表示该页具有元信息。

如在具有节点描述符结构体的页中，指定该页包含节点信息

void register_page_bootmem_info_node(struct pglist_data *pgdat)
{unsigned long i, pfn, end_pfn, nr_pages;int node = pgdat->node_id;struct page *page;struct zone *zone;nr_pages = PAGE_ALIGN(sizeof(struct pglist_data)) >> PAGE_SHIFT;page = virt_to_page(pgdat);for (i = 0; i < nr_pages; i++, page++) // 求出pglist_data的大小所需页数，对相应页标记NODE_INFOget_page_bootmem(node, page, NODE_INFO);zone = &pgdat->node_zones[0];for (; zone < pgdat->node_zones + MAX_NR_ZONES - 1; zone++) {if (zone->wait_table) { // 如果zone中有wait_table，则保存相应列表的所有页nr_pages = zone->wait_table_hash_nr_entries* sizeof(wait_queue_head_t);nr_pages = PAGE_ALIGN(nr_pages) >> PAGE_SHIFT;page = virt_to_page(zone->wait_table);for (i = 0; i < nr_pages; i++, page++)get_page_bootmem(node, page, NODE_INFO);}}pfn = pgdat->node_start_pfn; // 页起始end_pfn = pfn + pgdat->node_spanned_pages;/* register_section info */for (; pfn < end_pfn; pfn += PAGES_PER_SECTION)register_page_bootmem_info_section(pfn); // 保存节区信息SECTION_INFO和MIX_SECTION_INFO}

这个函数其实也没做什么，就是加了标志位而已

get_page_bootmem求出pglist_data的大小所需页数，对相应页标记NODE_INFO

/** Types for free bootmem.* The normal smallest mapcount is -1. Here is smaller value than it.*/
#define SECTION_INFO		(-1 - 1)
#define MIX_SECTION_INFO	(-1 - 2)
#define NODE_INFO		    (-1 - 3)

static void get_page_bootmem(unsigned long info,  struct page *page, int type)
{atomic_set(&page->_mapcount, type);SetPagePrivate(page); set_page_private(page, info); // 引用计数加1atomic_inc(&page->_count);
}

free_all_bootmem_core

将bootmem设置中的所有数据迁移到伙伴系统，也是在此函数中将bootmem进行销毁的

哪些物理页会被释放给buddy？

• bootmem allocator中所有标识为“未分配”的页首先会被释放被buddy allocator
• bootmem map所占用的内存被释放给buddy allocator

由于bootmem分配的页里面的数据基本都是用于内存基本结构(如内核、初始页表、pkmap页表、struct page实例、ramdisk、percpu变量、entry_hashtable、inode_hash_table……)，在系统运行期间会一直被用到，所以不会被释放。

不够像__init这种类型的数据段只在系统开机的时候被用到，所以系统初始化完成之后就空页释放掉了。

另外bootmem释放给buddy的时候，调用的是buddy的释放接口，所以在buddy初始化之前不能调用free_bootmem_core函数

系统是通过函数free_all_bootmem()来停止的bootmem allocator使用

	return free_all_bootmem_core(pgdat->bdata);

函数体为

static unsigned long __init free_all_bootmem_core(bootmem_data_t *bdata)
{int aligned;struct page *page;unsigned long start, end, pages, count = 0;

求出起始页帧和结束页帧

	start = bdata->node_min_pfn; // 起始页帧end = bdata->node_low_pfn;  // 结束页帧// 如果按及其位宽对齐，那么bootmem就可以按bulk的方式将批量的物理内存转移给buddy，反之只能将	// 没有对齐的部分按单独的物理页帧转移给buddy分配器aligned = !(start & (BITS_PER_LONG - 1)); // 是否以词单位进行排列

其中

	while (start < end) {unsigned long *map, idx, vec;map = bdata->node_bootmem_map; // 页管理位图idx = start - bdata->node_min_pfn; // 起始地址在bitmap中的索引// 将idx处开始的BITS_PER_LONG个bit值全部取反vec = ~map[idx / BITS_PER_LONG];// 释放页时是否一次释放多页if (aligned && vec == ~0UL && start + BITS_PER_LONG < end) {int order = ilog2(BITS_PER_LONG); // 获得对应的阶数__free_pages_bootmem(pfn_to_page(start), order);count += BITS_PER_LONG;} else { // 每次释放一页unsigned long off = 0;while (vec && off < BITS_PER_LONG) { // 查看vec是否为1if (vec & 1) { // 如果为1则是可以转移给buddy分配器的page = pfn_to_page(start + off); // 获得页__free_pages_bootmem(page, 0); // 将对应的物理页帧转移给buddy分配器count++;}vec >>= 1;off++;}}start += BITS_PER_LONG;}

查找用于页管理的页数

	pages = bdata->node_low_pfn - bdata->node_min_pfn;

最后

	page = virt_to_page(bdata->node_bootmem_map); // 获得物理内存区域bitmap对应的struct pagepages = bdata->node_low_pfn - bdata->node_min_pfn; // 计算当前物理内存区域对应的bitmap占用的物理内存页的数量pages = bootmem_bootmap_pages(pages);count += pages; // 更新到count中while (pages--) // 将bitmap占用的物理页转移到buddy分配器中__free_pages_bootmem(page++, 0);bdebug("nid=%td released=%lx\n", bdata - bootmem_node_data, count);return count; // 返回释放物理页的数量
}

来看看几个转移内存的函数

__free_pages_bootmem

以顺序单位释放页

/** permit the bootmem allocator to evade page validation on high-order frees*/
// page 指向物理页
// order 包含物理页的数量
void __meminit __free_pages_bootmem(struct page *page, unsigned int order)
{if (order == 0) { // 以1页单位释放页__ClearPageReserved(page); // 将struct page 从reversed状态转换到可用状态set_page_count(page, 0); // 使用计数为0set_page_refcounted(page); // 引用技术为1__free_page(page); // 将物理页加入到buddy分配器中} else {int loop;prefetchw(page);for (loop = 0; loop < BITS_PER_LONG; loop++) {struct page *p = &page[loop];if (loop + 1 < BITS_PER_LONG)prefetchw(p + 1);__ClearPageReserved(p);set_page_count(p, 0);}set_page_refcounted(page);__free_pages(page, order);}
}

可见__free_page的作用是将物理页加入到Buddy System中

释放1页的时候，每一页的count=1，而释放多页的时候，每个多页的第一页count=1，使得页作为相应顺序的起始页处于使用状态，并避免在内存中被清除

__free_page

#define __free_page(page) __free_pages((page), 0) // 转移多个页使用的就是这个

extern void __free_pages(struct page *page, unsigned int order);void __free_pages(struct page *page, unsigned int order)
{if (put_page_testzero(page)) { // 检查将页次数减1之后是否为0，仅在count=1时释放页if (order == 0) // 则放回每CPU高速缓存中free_hot_page(page); // 释放到PCP中else // 此时表示以顺序为单位释放，放到伙伴系统__free_pages_ok(page, order); // 将页以顺序单位释放}
}

free_hot_page

从函数体中可以看出，其释放的页主要放在了pcp，因此页的分配方式又加了pcp一种，即per cpu page

void free_hot_page(struct page *page)
{free_hot_cold_page(page, 0);
}static void free_hot_cold_page(struct page *page, int cold)
{struct zone *zone = page_zone(page); // zone结构体struct per_cpu_pages *pcp;unsigned long flags;if (PageAnon(page))page->mapping = NULL;if (free_pages_check(page))return;if (!PageHighMem(page)) {debug_check_no_locks_freed(page_address(page), PAGE_SIZE);debug_check_no_obj_freed(page_address(page), PAGE_SIZE);}arch_free_page(page, 0);kernel_map_pages(page, 1, 0);// 获得对应于get_cpu()的CPU的页列表zone->pageste->pcp// 这是不同cpu具有的1页列表，这些页不会直接返回伙伴系统，而是持有不同cpu的页以快速执行分配pcp = &zone_pcp(zone, get_cpu())->pcp; // local_irq_save(flags);__count_vm_event(PGFREE);if (cold)  // 放到尾部list_add_tail(&page->lru, &pcp->list);else // 放到首部list_add(&page->lru, &pcp->list);set_page_private(page, get_pageblock_migratetype(page));pcp->count++;if (pcp->count >= pcp->high) {free_pages_bulk(zone, pcp->batch, &pcp->list, 0);pcp->count -= pcp->batch;}local_irq_restore(flags);put_cpu();
}

__free_pages_ok

针对伙伴系统的内存分配，主要还是由该函数进行释放

static void __free_pages_ok(struct page *page, unsigned int order)
{// ...free_one_page(page_zone(page), page, order);local_irq_restore(flags);
}static void free_one_page(struct zone *zone, struct page *page, int order)
{// ...__free_one_page(page, zone, order);spin_unlock(&zone->lock);
}static inline void __free_one_page(struct page *page,struct zone *zone, unsigned int order)
{unsigned long page_idx;int order_size = 1 << order;int migratetype = get_pageblock_migratetype(page); // 获得页的迁移类型，即移动类型

free_area[]分为三个链表，由三种不同属性的页组成，因此此处的migratetype 便是决定将该页放置在哪个链表

freee_list[]数组按迁移类型管理页

    // .../*将页面转化为全局页面数组的下标*/ page_idx = page_to_pfn(page) & ((1 << MAX_ORDER) - 1); // 对应于2^{MAX_ORDER}个页中第几页的索引

整个释放过程的核心函数使__free_one_page，依据申请的算法，那么释放就涉及到对页面能够进行合并的。相关的内存区被添加到伙伴系统中适当的free_area列表中，在释放时，该函数将其合并为一个连续的内存区，放置到高一阶的free_are列表中。如果还能合并一个进一步的伙伴对，那么也进行合并，转移到更高阶的列表中。该过程会一致重复下去，直至所有可能的伙伴对都已经合并，并将改变尽可能向上传播

	// 如果被释放的页不是所释放阶的第一个页，则说明参数有误VM_BUG_ON(page_idx & (order_size - 1));VM_BUG_ON(bad_range(zone, page));

释放页以后，当前页面可能与前后的空闲页组成更大的空闲页面，直到放到最大阶的伙伴系统中

	while (order < MAX_ORDER-1) {unsigned long combined_idx;struct page *buddy;// 找到与当前页属于同一阶的伙伴系统页面的地址buddy = __page_find_buddy(page, page_idx, order);// //检查buddy是否描述了大小为order的空闲页框块的第一个页if (!page_is_buddy(page, buddy, order))break;/* Our buddy is free, merge with it and move up one order. */// 如果能够合并，则将伙伴页从伙伴系统中摘除list_del(&buddy->lru);// 同时减少当前阶中的空闲页计数zone->free_area[order].nr_free--;// 清除伙伴页的伙伴标志，因为该页会被合并rmv_page_order(buddy);// 将当前页与伙伴页合并后，新的页面起始地址combined_idx = __find_combined_index(page_idx, order);page = page + (combined_idx - page_idx);page_idx = combined_idx;order++;}

	set_page_order(page, order);// 更高阶的页面已经分配出去，那么将当前页面放到链表前面list_add(&page->lru,&zone->free_area[order].free_list[migratetype]);zone->free_area[order].nr_free++;

但内核如何知道一个伙伴对的两个部分都位于空闲页的列表中呢？为将内存块放回伙伴系统，内核必须计算潜在的伙伴地址，以及在有可能合并的情况下合并后内存块的索引。内核提供辅助函数用于计算

static inline unsigned long
__find_buddy_index(unsigned long page_idx, unsigned int order)
{return page_idx ^ (1 << order);
}

对于__free_one_page试图释放一个order的一个内存块，有可能不只是当前内存块与能够与其合并的伙伴直接合并，而且高阶的伙伴也可以合并，因此内核需要找到可能的最大分配阶。

假设释放一个0阶内存块，即一页，该页的索引值为10，假设页10是合并两个3阶伙伴最后形成一个4阶的内存块，计算如下图所示

伙伴系统释放和合并的过程

释放过程

• 把释放的快放入空闲块数组
• 合并满足合并条件的空闲块

合并条件

• 大小相同
• 地址相邻
• 低地址空闲块起始地址为2^(i+1)的倍数

我个人认为伙伴系统应该叫做伙伴算法更加合适

free_area

移交到高端内存空白页伙伴系统

#ifdef CONFIG_HIGHMEM/* set highmem page free */for_each_online_node(node) { // 遍历每个nodefor_each_nodebank (i, &meminfo, node) { // 遍历每个bankunsigned long start = bank_pfn_start(&meminfo.bank[i]); // 开始页帧unsigned long end = bank_pfn_end(&meminfo.bank[i]); // 结束页帧if (start >= max_low_pfn + PHYS_PFN_OFFSET)totalhigh_pages += free_area(start, end, NULL);}}totalram_pages += totalhigh_pages;
#endif

free_area函数在内部调用__free_page()函数，将空白页和一般内存区域共同释放到伙伴系统

此处可注意一下max_low_pfn这个变量，易知max_pfn是当前最大物理页帧号，但是max_low_pfn是低端内存区(直接映射空间区)的内存的最大可用页帧号。

内核空间分为直接内存映射区(低端、线性)和高端内存映射区

static inline int free_area(unsigned long pfn, unsigned long end, char *s)
{unsigned int pages = 0, size = (end - pfn) << (PAGE_SHIFT - 10);for (; pfn < end; pfn++) { //struct page *page = pfn_to_page(pfn); // 获得pageClearPageReserved(page);init_page_count(page);__free_page(page);  // 释放页pages++;}if (size && s)printk(KERN_INFO "Freeing %s memory: %dK\n", s, size);return pages;
}

至于为什么要把高端内存区地址进行映射，应该是和系统的分配内存的方式有关
即伙伴算法和slab高速缓存都在物理内存映射区分配物理内存，而vmalloc机制则在高端内存映射区分配物理内存