伙伴系统buddy allocator (1)——初始化

Posted on Edited on
之前有学习过bootmem和memblock两种内存分配方式，分别在笔记 memblock工作原理和 bootmem工作原理中有所记录。这是两种在启动阶段使用的内存分配方式。至于为什么开始的时候要用bootmem这种简单的分配方式，而不直接上伙伴系统呢，Gorman在其书中这样指出：
It is impractical to statically initialize all the core kernel memory structures at compile time because there are simply far too many permutations of hardware con-figurations. To set up even the basic structures, though, requires memory because even the physical page allocator, discussed in the next chapter, needs to allocate memory to initialize itself. 
                                                                      -- 《Understanding the Linux®Virtual Memory Manager》
         
           简而言之，就是不管是buddy allocator还是slab allocator，都太复杂，牵涉到各种对抗碎片的机制，其本身的初始化就要牵涉到内存分配的事情，所以Linux kernel先用bootmem等简单机制顶一阵，之后再把所有内存都分配给伙伴系统，交给他管理。

          本篇先说伙伴系统的初始化。关于伙伴系统就不做介绍了，具体可以参考Linux伙伴系统(一)--伙伴系统的概述 - vanbreaker的专栏 - 博客频道 - CSDN.NET。下面简单列一下涉及到的几个数据结构。

struct zone {
     ……
     struct per_cpu_pageset __percpu *pageset;
     ……
     struct free_area     free_area[MAX_ORDER];
     ……
}

struct free_area {
     struct list_head     free_list[MIGRATE_TYPES];
     unsigned long          nr_free;
};

不一一作解释了，只说一下和伙伴系统相关的部分。所有的伙伴系统的概念，其实都是在zone->free_area[MAX_ORDER]中，借用Gorman的一幅图
每一个order的free_area都有自己的一组按migrate type分类的list，nr_free表示这个order共有多少个空闲块。而list中的节点就是page->lru。

下面开始真正的初始化：
如果不考虑高端内存的话，核心函数就在free_all_bootmem。free_all_bootmem就是在遍历bootmem，并释放bdata_list上的每一块bootmem。下面以释放一块的代码为例。
          while (start < end) {
unsigned long *map, idx, vec;

          map = bdata->node_bootmem_map;
          idx = start - bdata->node_min_pfn;
          vec = ~map[idx / BITS_PER_LONG]; // vec是map取反，则vec中0表示已分配，1表示未分配

                    /* aligned的含义是，start有没有和LONG边界对齐，
           * 没有的话，多出来的部分，也要按order 0来释放
           */
          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) {
                    if (vec & 1) {
                         page = pfn_to_page(start + off);
                         __free_pages_bootmem(page, 0);
                         count++;
                    }
                    vec >>= 1;
                    off++;
               }
          }
          start += BITS_PER_LONG;
          }
这个函数看起来其实很简单，他的核心内容都在释放bootmem上，不管是整片释放还是按页释放，最后都会落到函数__free_pages_bootmem里。其处理流程是
     1）__ClearPageReserved
     2）所有page count设为0，set_page_count(page, 0)
     3）page block首页count设为1，set_page_refcounted(page);
     4）__free_pages(page, order);
所以最后归根结底就到了__free_pages。这是一个很重要的函数，也包含了很多知识点。其定义在mm/page_alloc.c中。

所有的释放被分成两种情况：1）单页释放 2）按order释放。

1.单页释放
如果是单页的话，则将之释放到zone->pageset中，冷页加入头部，热页加入尾部。关于冷热页可以参考笔记认识Linux物理内存管理系统--Buddy System。简单来说，zone->pageset是个per-CPU变量，每个pageset有个struct per_cpu_pages pcp成员，这个成员就代表着一组page。所有的page就在下面的lists这组列表中。那么这组内存从何而来，从初始化的进程看来，就是在释放bootmem时候的这些单个页，就被释放到per-CPU内存中。之所以要有这个per-CPU的内存，是为了减少在分配1页这种小内存时，还要获取zone->lock来锁住整个区域，这样很不划算。
struct per_cpu_pageset {
     struct per_cpu_pages pcp; 
     ……
};
          
struct per_cpu_pages {
     int count;          /* number of pages in the list */
     int high;          /* high watermark, emptying needed */
     int batch;          /* chunk size for buddy add/remove */

     /* Lists of pages, one per migrate type stored on the pcp-lists */
     struct list_head lists[MIGRATE_PCPTYPES];
};
          所谓的冷和热，就是指是否在CPU高速缓存中，一般是在L2 Cache。zone->pageset->pcp[n]这张表上的项，也就是页面按照一定的规则被换入换出，头部最有可能是在热区，那么尾部就最有可能在冷区。所以假如分配单独页面时，尽量分配该list的头部页面。
          pcp->high, batch，是维护这些list的指标，当所有lists中页面总数超过high的时候，就要释放batch个页面到buddy system。也就是free_pcppages_bulk，其过程跟后面的__free_pages_ok是一样的。high, batch的初始化是在setup_per_cpu_pageset->setup_zone_pageset(zone)->setup_pageset(pcp, zone_batchsize(zone)) -> zone_batchsize(zone)。其选择是有一定讲究的，有兴趣的可以参考mm\page_alloc.c。

2.按order释放
          按order来释放，反而过程简单清晰一些，只是通过几个小技巧找到本order块的buddy，以及合成后的combined index，之后只要不断的向上合并到不能合并为之，再set order，就大功告成。加入没有buddy的话，就直接set order，同时会用__SetPageBuddy来设置page结构的flags的第19位PG_buddy位，表示本page已释放，并在buddy list上。最后一点要注意的就是，合成好后的block如果小于MAX_ORDER的，还要放在zone->free_area[order].list的尾部，以便尽量不被分配出去，最好能继续被合并成大块。
          这里值得欣赏的是，怎么找到buddy和combined index。
          找到buddy，其实就是一个表达式
                    page_idx ^ (1<<order)
          仔细算算吧，他就是page_idx +/- (2^order)，若page_idx的order位为1，相当于减，order位为0相当于加。这个式子太优美了。还有怎么找到parent index呢？同样很简洁 
                    combined_idx = page_idx & (1<<order)
          值得好好学习学习。