深入理解Linux虚拟内存管理（四）（上）

// init/main.c
asmlinkage void __init start_kernel(void)
{
  // ...
  setup_arch(&command_line);
  // ...
  mem_init();
  kmem_cache_sizes_init();
  pgtable_cache_init();
  // ...
}

// arch/i386/kernel/setup.c
void __init setup_arch(char **cmdline_p) {
  // ...
  max_low_pfn = setup_memory();
  paging_init();
  // ...  
}

// mm/bootmem.c
// 这是容易混淆的地方。参数 pages 实际上是该节点可寻址内存的 PFN 末端，而不是
// 按名字的意思：页面数。
unsigned long __init init_bootmem (unsigned long start, unsigned long pages) {
  // 如果没有依赖于体系结构的代码，则设置该节点的可寻址最大 PFN。
  max_low_pfn = pages;
  // 如果没有依赖于体系结构的代码，则设置该节点的可寻址最小 PFN。
  min_low_pfn = start;
  // 调用 init_bootmem_core()(见 E.1.3 小节)，在那里完成初始化 bootmem_data 的实
  // 际工作。
  return(init_bootmem_core(&contig_page_data, start, 0, pages));
}

// mm/bootmem.c
// 这个函数由 NUMA 体系结构调用，用于初始化特定节点的引导内存分配器数据。
unsigned long __init init_bootmem_node (pg_data_t *pgdat, unsigned long freepfn, 
                    unsigned long startpfn, unsigned long endpfn)
{
  //  仅直接调用 init_bootmem_core()
  return(init_bootmem_core(pgdat, freepfn, startpfn, endpfn));
}

// mm/bootmem.c
static unsigned long __init init_bootmem_core (pg_data_t *pgdat,
  unsigned long mapstart, unsigned long start, unsigned long end)
{
  bootmem_data_t *bdata = pgdat->bdata;
  unsigned long mapsize = ((end - start)+7)/8;

  pgdat->node_next = pgdat_list;
  pgdat_list = pgdat;

  mapsize = (mapsize + (sizeof(long) - 1UL)) & ~(sizeof(long) - 1UL);
  // 内存最低内存分配给 node_bootmem_map , 大小为 mapsize 个页面（struct page）
  bdata->node_bootmem_map = phys_to_virt(mapstart << PAGE_SHIFT);
  bdata->node_boot_start = (start << PAGE_SHIFT);
  bdata->node_low_pfn = end;

  /*
   * Initially all pages are reserved - setup_arch() has to
   * register free RAM areas explicitly.
   */
  // 把所有位图初始化为 1， 即所有内存设置为保留（被占用）
  memset(bdata->node_bootmem_map, 0xff, mapsize);

  return mapsize;
}

// mm/bootmem.c
void __init reserve_bootmem (unsigned long addr, unsigned long size)
{
  reserve_bootmem_core(contig_page_data.bdata, addr, size);
}

// mm/bootmem.c
/*
 * Marks a particular physical memory range as unallocatable. Usable RAM
 * might be used for boot-time allocations - or it might get added
 * to the free page pool later on.
 */
static void __init reserve_bootmem_core(bootmem_data_t *bdata, unsigned long addr, unsigned long size)
{
  unsigned long i;
  /*
   * round up, partially reserved pages are considered
   * fully reserved.
   */
  // sidx 是服务页的起始索引。它的值是从请求地址中减去起始地址并除以页大小得到的。   
  unsigned long sidx = (addr - bdata->node_boot_start)/PAGE_SIZE;
  // 末尾索引 eidx 的计算与 sidx 类似，但它的分配是向上取整到最近的页面。这意味着
  // 对保留一页中部分请求将导致整个页都被保留。
  unsigned long eidx = (addr + size - bdata->node_boot_start + 
              PAGE_SIZE-1)/PAGE_SIZE;
  // end 是受本次保留影响的最后 PFN。             
  unsigned long end = (addr + size + PAGE_SIZE-1)/PAGE_SIZE;
  // 检查是否给定了一个非零值。
  if (!size) BUG();
  // 检查起始索引不在节点起点之前。
  if (sidx < 0)
    BUG();
  // 检查末尾索引不在节点末端之后。    
  if (eidx < 0)
    BUG();
  // 检查起始索引不在末尾索引之后。    
  if (sidx >= eidx)
    BUG();
  // 检查起始地址没有超出该启动内存节点所表示的内存范围。   
  if ((addr >> PAGE_SHIFT) >= bdata->node_low_pfn)
    BUG();
  // 检查末尾地址没有超出该启动内存节点所表示的内存范围。   
  if (end > bdata->node_low_pfn)
    BUG();
  // 从 sidx 开始，到 eidx 结束，这里测试和设置启动内存分配图中表示页面已经分
  // 配的位。如果该位已经设置为 1，则打印一条消息：该位被设置了两次。    
  for (i = sidx; i < eidx; i++)
    if (test_and_set_bit(i, bdata->node_bootmem_map))
      printk("hm, page %08lx reserved twice.\n", i*PAGE_SIZE);
}

// include/linux/bootmem.h
// 将 L1 硬件高速缓存页对齐，并在 DMA 中可用的最大地址后开始查找一页。 SMP_CACHE_BYTES 为 64?
#define alloc_bootmem(x) \
  __alloc_bootmem((x), SMP_CACHE_BYTES, __pa(MAX_DMA_ADDRESS))
// 将 L1 硬件高速缓存页对齐，并从 0 开始查找。  
#define alloc_bootmem_low(x) \
  __alloc_bootmem((x), SMP_CACHE_BYTES, 0)
  
// 将已分配位对齐到一页大小，这样满页将从 DMA 可用的最大地址开始分配。
#define alloc_bootmem_pages(x) \
  __alloc_bootmem((x), PAGE_SIZE, __pa(MAX_DMA_ADDRESS))
// 将已分配位对齐到一页大小，这样满页将从物理地址 0 开始分配。  
#define alloc_bootmem_low_pages(x) \
  __alloc_bootmem((x), PAGE_SIZE, 0)

// mm/page_alloc.c
pg_data_t *pgdat_list;

// include/linux/mmzone.h
#define for_each_pgdat(pgdat) \
  for (pgdat = pgdat_list; pgdat; pgdat = pgdat->node_next)

// include/linux/bootmem.h
// 将从请求节点处开始分配，对齐 L1 硬件高速缓存，并从
// ZONE_NORMAL 处开始找到一页 (如，在 ZONE_DMA 末端，其为 MAX_DMA_ADDRESS)。
#define alloc_bootmem_node(pgdat, x) \
  __alloc_bootmem_node((pgdat), (x), SMP_CACHE_BYTES, __pa(MAX_DMA_ADDRESS))

// 将从请求节点处开始分配，分配页对齐到一页大小，所以全部页面将从 ZONE_NORMAL 中开始分配。
#define alloc_bootmem_pages_node(pgdat, x) \
  __alloc_bootmem_node((pgdat), (x), PAGE_SIZE, __pa(MAX_DMA_ADDRESS))
  
// 将从请求节点处开始分配，分配页对齐到一页大小，所以全部页面将从物理地址 0 处开始分配，
// 这里将使用 ZONE_DMA。  
#define alloc_bootmem_low_pages_node(pgdat, x) \
  __alloc_bootmem_node((pgdat), (x), PAGE_SIZE, 0)

// mm/bootmem.c
// 它所要分配的节点是特定的。
void * __init __alloc_bootmem_node (pg_data_t *pgdat, unsigned long size, unsigned long align, unsigned long goal)
{
  void *ptr;
  // 调用核心函数 __alloc_bootmem_core 来完成分配。
  ptr = __alloc_bootmem_core(pgdat->bdata, size, align, goal);
  // 如果成功则返回一个指针。
  if (ptr)
    return (ptr);

  /*
   * Whoops, we cannot satisfy the allocation request.
   */
  // 否则，若在这里都没有分配内存，系统将不能启动，所以打印一条消息，表示系统瘫痪。   
  printk(KERN_ALERT "bootmem alloc of %lu bytes failed!\n", size);
  panic("Out of memory");
  return NULL;
}

/*
 * We 'merge' subsequent allocations to save space. We might 'lose'
 * some fraction of a page if allocations cannot be satisfied due to
 * size constraints on boxes where there is physical RAM space
 * fragmentation - in these cases * (mostly large memory boxes) this
 * is not a problem.
 *
 * On low memory boxes we get it right in 100% of the cases.
 */

/*
 * alignment has to be a power of 2 value.
 */
// 这是函数的前面部分，它保证参数有效。
// 
// bdata 是要分配结构体的启动内存。
// size 是请求分配的大小。
// align 是分配的对齐方式，它必须是 2 的幂。
// goal 是上面要分配的最可能的合适大小？ 以 goal 参数为基础计算开始扫描的起始地址。
static void * __init __alloc_bootmem_core (bootmem_data_t *bdata, 
  unsigned long size, unsigned long align, unsigned long goal)
{
  unsigned long i, start = 0;
  void *ret;
  unsigned long offset, remaining_size;
  unsigned long areasize, preferred, incr;
  // 计算末尾位索引 eidx，它返回可能用于分配的最高页面索引。
  unsigned long eidx = bdata->node_low_pfn - (bdata->node_boot_start >>
              PAGE_SHIFT);
              
  //  如果指定了 0 则调用 BUG()。
  if (!size) BUG();
  //  如果对齐不是 2 的幂，则调用 BUG()。
  if (align & (align-1))
    BUG();
  // 对齐的缺省偏移是 0。
  offset = 0;
  // 如果指定了对齐方式则・・・・
  // 请求的对齐方式与开始节点的对齐方式相同，这里计算偏移。
  if (align &&
      (bdata->node_boot_start & (align - 1UL)) != 0)
  // 要使用的偏移与起始地址低位标记的请求对齐。实际上，这里的 offset 与 align 的一
  // 般值 align 相似。     
    offset = (align - (bdata->node_boot_start & (align - 1UL)));
  offset >>= PAGE_SHIFT;

  /*
   * We try to allocate bootmem pages above 'goal'
   * first, then we try to allocate lower pages.
   */
  // 这一块计算开始的 PFN 从 goal 参数为基础的地址处开始扫描。
  //
  // 如果指定了 goal，且 goal 在该节点的开始地址之后，goal 小于该节点可寻址 PFN，则 ...  
  // 开始的适当偏移是 goal 减去该节点可寻址的内存起点。    
  if (goal && (goal >= bdata->node_boot_start) && 
      ((goal >> PAGE_SHIFT) < bdata->node_low_pfn)) {
    preferred = goal - bdata->node_boot_start;
  } else
  // 如果不是这样，则适当偏移为 0。
    preferred = 0;
    
  // 考虑偏移，调整适当偏移的大小，这样该地址将可以正确对齐。
  preferred = ((preferred + align - 1) & ~(align - 1)) >> PAGE_SHIFT;
  preferred += offset;
  // 本次分配影响到的页面数存放在 areasize 中。
  areasize = (size+PAGE_SIZE-1)/PAGE_SIZE;
  // incr 是要跳过的页面数，如果多于一页，则它们满足对齐请求。
  incr = align >> PAGE_SHIFT ? : 1;

  // 这一块扫描内存，寻找一块足够大的块来满足请求。
  //
  // 如果本次分配不能满足从 goal 开始，则跳到这里的标志，这样将重新扫描该映射图。
restart_scan:
  // 从 preferred 开始，这里线性扫描一块足够大的块来满足请求。这里以 incr 为
  // 步长来遍历整个地址空间以满足大于一页的对齐。如果对齐小于一页，incr 为 1。
  for (i = preferred; i < eidx; i += incr) {
    unsigned long j;
    if (test_bit(i, bdata->node_bootmem_map))
      continue;
  // 扫描下一个 areasize 大小的页面来确定它是否也可以被释放。如果到达可寻
  // 址空间的末端 (eidx) 或者其中的一页已经在使用，则失败。      
    for (j = i + 1; j < i + areasize; ++j) {
      if (j >= eidx)
        goto fail_block;
      if (test_bit (j, bdata->node_bootmem_map))
        goto fail_block;
    }
  // 找到一个空闲块，所以这里记录 start，并跳转到找到的块。   
    start = i;
    goto found;
  fail_block:;
  }
  // 分配失败，所以从开始处重新开始。
  if (preferred) {
    preferred = offset;
    goto restart_scan;
  }
  // 如果再次失败，则返回 NULL，这将导致系统瘫疾。
  return NULL;

  // 这一块测试以确定本次分配可以与前一次分配合并。
found:
  // 检查分配的起点不会在可寻址内存之后。刚才已经检查过，所以这里是多余的。
  if (start >= eidx)
    BUG();

  /*
   * Is the next page of the previous allocation-end the start
   * of this allocation's buffer? If yes then we can 'merge'
   * the previous partial page with this allocation.
   */
  // 如果对齐小于 PAGE_SIZE，前面的页面在其中有空间(last_offset != 0)，而且
  // 前面使用的页与本次分配的页相邻，则试着与前一次分配合并。  
  if (align <= PAGE_SIZE
      && bdata->last_offset && bdata->last_pos+1 == start) {
  // 更新用于对 align 请求正确分页的偏移。     
    offset = (bdata->last_offset+align-1) & ~(align-1);
  // 如果偏移现在超过了页面边界，则调用 BUG()。这个条件需要使用一次非常
  // 槽糕的对齐选择。由于一般使用的对齐仅是一个 PAGE_SIZE 的因子，所以不可能在平常
  // 使用。    
    if (offset > PAGE_SIZE)
      BUG();
  // remaining_size 是以前用过的页面中处于空闲的空间。     
    remaining_size = PAGE_SIZE-offset;
// 如果在旧的页面中有足够的空间剩余，这里使用旧的页面，然后更新 bootmem_data 
//
  // 结构来反映这一点。    
    if (size < remaining_size) {
  // 这次分配中用到的页面数现在为 0。    
      areasize = 0;
      // last_pos unchanged
  // 更新 last_offset 为本次分配的末端。     
      bdata->last_offset = offset+size;
  // 计算返回成功分配的虚拟地址。     
      ret = phys_to_virt(bdata->last_pos*PAGE_SIZE + offset +
            bdata->node_boot_start);
    } else {
// 如果不是这样，则这里计算除了这一页外还需要多少页面，并更新 bootmem_data。  
//
  //  remaining_size 是上一次用来满足分配的页面空间。 
      remaining_size = size - remaining_size;
  // 计算还需要多少页面来满足分配请求。      
      areasize = (remaining_size+PAGE_SIZE-1)/PAGE_SIZE;
  // 计算分配开始的地址。     
      ret = phys_to_virt(bdata->last_pos*PAGE_SIZE + offset +
            bdata->node_boot_start);
  // 使用到的最后一页是 start 页面加上满足这次分配的额外页面数量 areasize。            
      bdata->last_pos = start+areasize-1;
  // 已经计算过本次分配的末端。          
      bdata->last_offset = remaining_size;
    }
  // 如果偏移在页尾，则标记为 0。    
    bdata->last_offset &= ~PAGE_MASK;
  } else {
// 如果没有，这里记录本次分配用到的页面和偏移，以便于下次分配时的合并。
//
  // 不发生合并，所以这里记录用到的满足本次分配的最后一页。
    bdata->last_pos = start + areasize - 1;
  // 记录用到的最后一页。   
    bdata->last_offset = size & ~PAGE_MASK;
  // 记录分配的起始虚拟地址。   
    ret = phys_to_virt(start * PAGE_SIZE + bdata->node_boot_start);
  }
  /*
   * Reserve the area now:
   */
// 这一块在位图中标记分配页为 1，并将其内容清 0。
//
  // 遍历本次分配用到的所有页面，在位图中设置 1。如果它们中已经有 1，则发生
  // 了一次重复分配，所以调用 BUG()。   
  for (i = start; i < start+areasize; i++)
    if (test_and_set_bit(i, bdata->node_bootmem_map))
      BUG();
  // 将页面用 0 填充。     
  memset(ret, 0, size);
  // 返回分配的地址。
  return ret;
}