传说的伙伴系统

memblock作为系统启动初期的内存管理系统,在系统启动后就显得不是那么灵活了。在这个时候,内核就提出了页分配器来管理物理内存。而我们在Node->Zone->Page这篇中看到的这个层次结构,就是为了页分配器做的准备。

页从哪来

一路走来,我们回顾一下内存信息是怎么收集上来的

    BIOS -> e820 -> memblock

那现在就要看系统是怎么从memblock的信息中,组合成page的信息的。

众所周知,在内核中我们使用page结构体来表示物理页。在SPARSEMEM这篇中我们也对page结构体的存储位置做了探索。那在最开始的时候,这个结构体是空的。那什么时候系统把物理实际存在的页面和这个page结构体对应上呢?系统是什么时候确认系统到底是有那些page可以使用的呢?如何把page结构体保存到相应的Zone结构体中的呢?

这个过程就在memblock_free_all()函数中。

start_kernel()
    mm_core_init()
        mem_init()
            memblock_free_all()
                free_unused_memmap()                // 释放内存空洞对应的page struct
                reset_all_zones_managed_pages()     // 清除临时的managed_pages
                free_low_memory_core_early()
                    memblock_clear_hotplug(0, -1)
                    memmap_init_reserved_pages()    // set PageReserved
                    __free_memory_core()
                        __free_pages_memory(start_pfn, end_pfn)
                            memblock_free_pages()

在这个过程中你可以看到熟悉的for_each_free_mem_range()。对了,这就是遍历memory_block的内存信息,来填充page结构体的过程了。

PS: 当有了defer_init后,大部分的page struct初始化由单独的线程调用deferred_init_memmap()延迟初始化

释放

通常我们都是先讲分配,再讲释放的。但是这次要到过来。为什么呢,因为在free_all_bootmem()中就是调用了内存释放的方法来初始化page结构的。所以还是先来看看释放吧。

我们通常使用的函数是free_pages()。但是最后都调用到了函数__free_one_page()。这个函数其实比较简单,就是算的东西稍微有点绕。我们都知道页分配器中使用的是伙伴系统,也就是相邻的两个页是一对儿。所以在释放的时候,会去判断自己的伙伴是不是也是空闲的。如果是的话,那就做合并。且继续判断。

关于伙伴查找的算法,后面详细讲。有兴趣的可以仔细看。

那最后释放到哪里了呢?

对了,就是zone->free_area[order].free_list上了。

释放流程

整个流程比较长,分开看。下面这部分到拿到zone的锁。

__free_pages_core(page, order)
    __ClearPageReserved(p)
    set_page_count(p, 0)
    __free_pages_ok(page, order, FPI_TO_TAIL)
        free_pages_prepare(page, order)
        migratetype = get_pfnblock_migratetype(page, pfn)
        free_one_page(zone, page, pfn, order, migratetype, fpi_flags)
            spin_lock_irqsave(&zone->lock, flags)                 // free_list的锁在zone这里
            __free_one_page(page, pfn, zone, order, migratetype, fpi_flags)
            spin_unlock_irqrestore(&zone->lock, flags)

这部分是已经拿到锁之后,判断是否要和相邻的buddy合并。

__free_one_page(page, pfn, zone, order, migratetype, fpi_flags)
    __mod_zone_freepage_state(zone, 1 << order, migratetype)      // 增加NR_FREE_PAGES计数

    buddy = find_buddy_page_pfn(page, pfn, order, &buddy_pfn)
        __buddy_pfn = __find_buddy_pfn(pfn, order)
            return page_pfn ^ (1 << order)
        buddy = page + (__buddy_pfn - pfn)
        page_is_buddy(page, buddy, order)
    del_page_from_free_list(buddy, zone, order)                   // 如果buddy刚好空闲,先把他从free_list上摘下来
    combined_pfn = buddy_pfn & pfn
    page = page + (combined_pfn - pfn)
    pfn = combined_pfn
    order++

done_merging:
    set_buddy_order(page, order)
        set_page_private(page, order)
        __SetPageBuddy(page)

    add_to_free_list[_tail](page, zone, order, migratetype)       // 添加到free_list上

分配

页分配的核心函数是__alloc_pages_nodemask()。正如函数的注释上写的"This is the 'heart' of the zoned buddy allocator."。

Node->Zone->Page中我们已经看到了,内存被分为了node,zone来管理。这么管理的目的也就是为了在分配的时候,能能够找到合适的内存。所以在分配的时候,就是按照优先级搜索node和zone,如果找到匹配的zone则在该zone的free_area链表中取下一个。

和释放内存对称,分配的时候也可能会分配到高阶的page。如果发生这种情况,则会将高阶部分放回到对应的free_area中。

MAX_ORDER不是MAX_ORDER

这个标题有点绕吧。不过你看完了就知道确实就是这个意思。

我们知道zone->free_area[MAX_ORDER]上排列着指定大小的空闲页。一般情况下MAX_ORDER定义为11。但是你知道吗,这个MAX_ORDER的值并不表示内核管理空闲页最大单位是2^MAX_ORDER。

一个数组的个数和数组的下标之间相差为1,所以free_area表示的是2^0到2^10单位的空闲页。

记住了哈,页分配器中管理的最大空闲页是2^(MAX_ORDER -1)的大小。

伙伴系统

你不是一个人

内核中的buddy system可谓是久仰大名,如雷贯耳。这年头找对象不容易,看看人内核里面是怎么找的,咱也好好学学,取取经~

敬个礼,握握手,你是我的好朋友

好了,说正经的,人是怎么找的呢?


__free_one_page()
...
	while (order < max_order - 1) {
		buddy_idx = __find_buddy_index(page_idx, order);
		buddy = page + (buddy_idx - page_idx);
		if (!page_is_buddy(page, buddy, order))
			goto done_merging;
		/*
		 * Our buddy is free or it is CONFIG_DEBUG_PAGEALLOC guard page,
		 * merge with it and move up one order.
		 */
		if (page_is_guard(buddy)) {
			clear_page_guard(zone, buddy, order, migratetype);
		} else {
			list_del(&buddy->lru);
			zone->free_area[order].nr_free--;
			rmv_page_order(buddy);
		}
		combined_idx = buddy_idx & page_idx;
		page = page + (combined_idx - page_idx);
		page_idx = combined_idx;
		order++;
	}
...

其中重要的就是__find_buddy_index()。

/*
 * Locate the struct page for both the matching buddy in our
 * pair (buddy1) and the combined O(n+1) page they form (page).
 *
 * 1) Any buddy B1 will have an order O twin B2 which satisfies
 * the following equation:
 *     B2 = B1 ^ (1 << O)
 * For example, if the starting buddy (buddy2) is #8 its order
 * 1 buddy is #10:
 *     B2 = 8 ^ (1 << 1) = 8 ^ 2 = 10
 *
 * 2) Any buddy B will have an order O+1 parent P which
 * satisfies the following equation:
 *     P = B & ~(1 << O)
 *
 * Assumption: *_mem_map is contiguous at least up to MAX_ORDER
 */
static inline unsigned long
__find_buddy_index(unsigned long page_idx, unsigned int order)
{
	return page_idx ^ (1 << order);
}

人注释写得真好,还有个例子给你看。我这个人有个毛病,一旦看懂了代码就老兴奋了。忍不住多说两句,估计人真正的大牛对这种代码了如指掌,根本没兴趣了。

我个人看完这个代码有两点体会:

  • 使用某个位置上的数做异或就像是一个开关,原来有的就清,没的就置位

  • 两个小伙伴的上一级伙伴,是这个位为零的那个

举个栗子

 +--------+--------+--------+--------+
 |8       |9       |10      |11      |
 +--------+--------+--------+--------+

 [======  2  =====] [=====  2  ======]

 [###############  4  ###############]

举个栗子, 从上面这个图看出,O为1的时候,(8,9)为一组,(10,11)为一组。

         8   ^ 2 =  0b 1000 ^ 0b 0010 = 0b 1010 = 10
         10 ^ 2 =  0b 1010 ^ 0b 0010 = 0b 1000 = 8

可以看到,异或的结果就是order 2的那一位去反。很有意思。恩,是不是可以理解为男生找女生,女生找男生呢? (如果你硬要找一样的,我就没办法了)

那我们再来看如何找上一级的伙伴。从图上直观来看, (8,9) (9,10)的上一级就是数量为4的组。那他的首页面index就是8。

好了看看代码实现的效果

         8   & ~2 =  0b 1000 & 0b 1101 = 0b 1000 = 8
         10 & ~2 =  0b 1010 & 0b 1101 = 0b 1000 = 8

直观的效果就是大家都将order 2的那一位清除。哇哦,so easy.

大家注意一下实际代码中的一句

		combined_idx = buddy_idx & page_idx;
		page_idx = combined_idx;

在循环中,page_idx将作为下一次循环要去寻找伙伴的索引。那你想到了啥? 对了,正是因为自己的上一级伙伴是把order 2的那一位清空,所以自己和自己小伙伴做与运算就得到了上一级~

好了,我想你知道内核页分配中伙伴是怎么找的了~

到这里,就到这里,休息休息~

Compound Page

真实的页分配远比上述的描述要复杂的多,复杂点不在于内存大小的分配,而是对页的分类、统计和管理。

在这里我们先看一个概念 compound page。也就是对一个跨越多个页的“组合页”。内核对超过一个页面大小的页提供了一个方法PageCompound()来判断一个page是不是组合页的一部分。

简单得用一个图来描述这么一个概念。

page                  page                  page                  page
+----------------+    +----------------+    +----------------+    +----------------+
|PG_HEAD         |    |                |    |                |    |                |
|compound_order  |    |                |    |                |    |                |
|compound_dtor   |    |                |    |                |    |                |
|                |    |                |    |                |    |                |
|                |    |compound_head + |    |compound_head + |    |compound_head + |
+----------------+    +--------------|-+    +--------------|-+    +--------------|-+
^                                    |                     |                     |
|                                    |                     |                     |
+------------------------------------+---------------------+---------------------+

设置组合页和清除组合页的方法为

  • prep_compound_page

  • free_tail_pages_check

但是出乎我意料的是,只有在分配页面时使用__GFP_COMP时才会设置compound_head。那么这么说有些“组合页”也不能用PageCompound检测出来了。

在“组合页”的第一个页中有两个字段

  • compound_order

  • compound_dtor

第一个保存了页面的大小,第二个用来区分“组合页”的类型。

从定义上看有下面这么几个类型

NULL_COMPOUND_DTOR
COMPOUND_PAGE_DTOR
HUGETLB_PAGE_DTOR
TRANSHUGE_PAGE_DTOR

引用计数

随着伙伴系统越来越复杂,就会需要一些辅助信息来帮助管理。比如记录当前页面有多少使用者。在页结构体中有两个重要的引用计数:

  • _refcount

  • _mapcount

前者用来记录该页面当前的使用者个数,而后者标示当前页面映射到页表的次数。

而且在内核中如果前者的数目大于后者,则称这个页面“pin”住了。

page->_refcount

这个值用来表示有多少人在使用这个page,当page在buddy分配器中_refcount为0。

memmap_init()
    memmap_init_zone()
        init_page_count()
            set_page_count(page, 1)    <--- set to 1

mem_init()
    memblock_free_all()
        free_low_memory_core_early()
            __free_memory_core()
                ...
                __free_pages_core()
                    set_page_refcounted()   <--- set to 1 again
                    __free_pages()

之后有新的使用者,一般会用get_page来表示,防止错误释放页面。

同样在put_page中,就会检查_refcount是不是为零。如果减到零,就会把页面归还给buddy分配器。

值得注意的是如果是compound page那么这个引用计数会加在head page上。

page->_mapcount

用来表示映射到用户空间的次数。从-1开始。所以在分配页面时需要确认这点。

check_new_page()
  if (unlikely(atomic_read(&page->_mapcount) != -1))
    return false;

不过要获得一个页面被映射到进程的次数,就稍微复杂了点。这里涉及到了两个函数:

  • page_mapcount

  • total_mapcount

其中page_mapcount是针对一个PTE page来看的。 而total_mapcount则是针对一个THP来看的。

里面的原因在THP和mapcount之间的恩恩怨怨一文中做了详细的阐述。

Last updated