bootmem工作原理

            if (test_bit(i, bdata->node_bootmem_map)) { // 如果连续空间不足，则返回重新搜索未分配区

                sidx = align_idx(bdata, i, step);

                if (sidx == i)

                    sidx += step;

                goto find_block;

            }

        if (bdata->last_end_off & (PAGE_SIZE - 1) && // 上一次分配的空间末地址在页边界

                PFN_DOWN(bdata->last_end_off) + 1 == sidx)  

            start_off = align_off(bdata, bdata->last_end_off, align); // align = 64，将start_off提升到last_end_off附近，要按align向下对齐

        else

1.初始化

1)arm_bootmem_init

     有一点，先理清楚，Linux支持NUMA架构的内存管理，但NUMA一般应用于中大型系统，来灵活处理本地内存与远端内存，以提高平均内存读写速度，即优先使用本地内存或者访问速度较快的内存。但嵌入式设备或者我们的D7800并没有使用Linux的NUMA架构来管理内存。换句话说，就是我们的系统只有node 0，即其上只有本地内存。

     上图中bdata_list在NUMA架构中包含了所有node的内存地址，但在我们的系统中，该list上只有node 0的：min~max_low低端内存地址空间。再看memblock，具体参考memblock工作原理，其中memblock.memory表格中，包含了meminfo中所有bank的物理地址区间。对应到一张图上，就如上图左半部分的示意图所示，bdata_list上node 0的min~max_low区段上，有着nrbanks个region_start~region_end内存区间。

     于是，对应到代码里就很好理解了。在函数mark_bootmem中，遍历bdata_list列表，判断区段是否符合的条件如下。

     if (pos < bdata->node_min_pfn || 

            pos >= bdata->node_low_pfn) { // 表示超过了此node对应的区段，

            BUG_ON(pos != start);

            continue;

     }

          ……

          if (max == end) // end会不会超过max_low，即end是高端地址？我的理解，end可以超过low mem的限制，不过在bootmem中我们只考虑low mem的部分

            return 0;

     pos = bdata->node_low_pfn; // 运行到这里，表示start~end的region已经处理过了，只是max!=end，之后会空跑完剩下的循环

     总体来说所谓的bootmem，即是为meminfo中所有nrbanks内存的min~maxlow，来分配一张bitmap，每一位代表一个page是否分配。他和memblock两套不同的机制。bootmem的bitmap被memblock管理，memblock变量，以及memblock的两张表格memblock_memory_init_regions和memblock_reserved_init_regions，都是存在.init.data section中，即在kernel image里。

2)arm_bootmem_free

其中本node内存指标示意图如下：

alloc_node_mem_map在后面的章节讨论。

还有一点需要补充一下，pgdat一般指向NODE_DATA(i)，即node_data[i]成员。对于我们的系统，只考虑node 0，所以pgdat可以简单的看成是指向node 0的数据。在init_bootmem_node中，我们对该node的bootmem部分加以初始化。其他部分在其他部分初始化。

3)free_area_init_core

     a) 每个zone的page按照page block组织，每个page block包含MAX_ORDER-1 = 10，即1024页

     b) 代码中几个指标备注如下：

               size: 第j个zone的total_size，单位page

               memmap_pages: 本zone的memmap数组需要的page数

               realsize: totalsize - zhole_size[j] - memmap_pages - dma_reserve(如果是zone[0])

               nr_kernel_pages += realsize; // 如果是HIGHMEM zone，更新nr_kernel_pages

               nr_all_pages += realsize;

     c) init_currently_empty_zone, memmap_init在后面章节讨论

4) memmap_init

memmap数组在arm_bootmem_free->free_area_init_node中通过alloc_node_mem_map-> alloc_bootmem_node来分配一段bootmem内存，并赋给pgdat->node_mem_map。memmap_init函数负责初始化这块区域（数组）中的每个成员。

     a)关于SetPageReserved，在这里不知何用。

          内核中申请到页面之后，要调用一下SetPageReserved，相当于告诉系统，这个页面我已经占了。对于每一个申请到的页面，应该都要这样做。

     b)为每个页面设置miagrate type是为了防止外部碎片，其中的机制也略有些复杂

     c)lru list是为了回收机制设计的，全称是Least Recently Used

     d)关于struct page，具体可以参考Mel Gorman的《Understanding the Linux® Virtual Memory Manager》的P41：Pages一节。

5) alloc_bootmem_node

     alloc_bootmem_node -> __alloc_bootmem_node -> ___alloc_bootmem_node -> alloc_arch_preferred_bootmem / alloc_bootmem_core / ___alloc_bootmem

     最后落实到三个函数alloc_arch_preferred_bootmem / alloc_bootmem_core / ___alloc_bootmem。

     alloc_arch_preferred_bootmem 和___alloc_bootmem在未定义CONFIG_NO_BOOTMEM时，最终调用的都是alloc_bootmem_core 。所以alloc_bootmem_core 是核心函数。

     那么来看alloc_bootmem_core。

     

     这其中有很多个指标，大体总结如下：

     sidx / midx: start - bdata->node_min_pfn / max - bdata->node_min_pfn // 这两个变量也会有一些处理，但大体上可以认为是本node低端内存的首末地址页索引。

     eidx: sidx + PFN_UP(size) // 需要分配空间末地址按页向下（增长方向）对齐后的页索引

     start_off / end_off: 分配空间始末地址的物理地址

     merge: PFN_DOWN(start_off) < sidx // 此时start_off是经过处理的，因为前次分配的末地址（last_end_off）所在页还有空闲，则将start_off向上提升到该页，并与last_end_off隔开一定的距离

     bdata->last_end_off: 记录上一次分配末地址的物理地址，并不按页对齐，此变量只在alloc_bootmem_core中更新

     bdata->hint_idx: 在alloc_bootmem_core中= PFN_UP(end_off)，在__free的时候= sidx，记录的是可分配地址的最小值的页索引

     了解这些指标之后，对code就比较容易理解了。摘录如下

     static void * __init alloc_bootmem_core (……) {

                ……

     find_block:

                sidx = find_next_zero_bit(bdata->node_bootmem_map, midx, sidx); // find_next_zero_bit参考另一篇笔记find_next_zero_bit

        sidx = align_idx(bdata, sidx, step);

        eidx = sidx + PFN_UP(size);

        if (sidx >= midx || eidx > midx) // sidx > midx和eidx > midx比较好理解

                break; // sidx = midx的情况指的是find_next_zero_bit返回的是midx，根据find_next_zero_bit这篇笔记可知，这种情况是find_next_zero_bit失败，没有找到未分配页

     

                for (i = sidx; i < eidx; i++)

            start_off = PFN_PHYS(sidx);

                merge = PFN_DOWN(start_off) < sidx; // 表示本次分配与上次分配有交叠，参看图1

                ……

        /*

         * Reserve the area now:

         */

        if (__reserve(bdata, PFN_DOWN(start_off) + merge, // merge =0: 没有交叠，正常分配，merge =1：和上次有交叠，但有交叠的页已经reserve过了，所以从下一页开始reserve

                PFN_UP(end_off), BOOTMEM_EXCLUSIVE))

                ……     

     }

          

     alloc_bootmem_core中还有个fall_back机制，具体如下：

     static void * __init alloc_bootmem_core (……) {

                ……

          if (bdata->hint_idx > sidx) { // hint_idx是可分配空间的最小值，这个条件表示搜索起始点可以向前提升

        /*

         * Handle the valid case of sidx being zero and still

         * catch the fallback below.

         */

        fallback = sidx + 1; // 记录fall_back值

        sidx = align_idx(bdata, bdata->hint_idx, step); // 将sidx提升到hint_idx附近

          }

     while(1) {

find_block:

          ……

     }

          if (fallback) { // 如果搜索失败，则将sidx还原再重新搜索

        sidx = align_idx(bdata, fallback - 1, step);

        fallback = 0;

        goto find_block;

          }

     return NULL;

     }

6) init_currently_empty_zone

本函数主要是为了初始化zone结构，更明确的就是：（1）wait queue table初始化，（2）free_area初始化

调用顺序如下

zone_wait_table_init -> zone_init_free_lists(zone)

     a) zone_wait_table_init 

     此函数初始化了zone->wait_table，这是一张哈希表，有zone->wait_table_hash_nr_entries个表项（最少4，最多4096）。wait_table相关内容可参考可以参考Mel Gorman的《Understanding the Linux® Virtual Memory Manager》P40：Zone Wait Queue Table一节。内存页的wait-wake机制请参考笔记内存页的wait-wake机制。

     本函数调用流程为：

wait_table_hash_nr_entries(zone_size_pages) -> wait_table_bits(zone->wait_table_hash_nr_entries) -> alloc_bootmem_node(pgdat, alloc_size) -> 遍历所有哈希项，并初始化init_waitqueue_head(zone->wait_table + i)

     b）zone_init_free_lists

     牵涉到migrate type，尚不清楚其中的机制，会用新篇来作介绍