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

// mm/memory.c
/*
 * Do a quick page-table lookup for a single page. 
 */
// 这个函数是 mm 中待遍历的页表。address 与 struct page 和 write 有关，它表明该页
// 是否将被写。
static struct page * follow_page(struct mm_struct *mm, unsigned long address, int write) 
{
  pgd_t *pgd;
  pmd_t *pmd;
  pte_t *ptep, pte;

  // 获取 address 处的 PGD 并保证它存在且有效。
  pgd = pgd_offset(mm, address);
  if (pgd_none(*pgd) || pgd_bad(*pgd))
    goto out;
  
  // 获取address处的PMD并保证它存在且有效。
  pmd = pmd_offset(pgd, address);
  if (pmd_none(*pmd) || pmd_bad(*pmd))
    goto out;

  // 获取address处的PTE并保证它存在且有效。
  ptep = pte_offset(pmd, address);
  if (!ptep)
    goto out;

  pte = *ptep;
  // 如果PTE当前存在，则可以返回一些东西。
  if (pte_present(pte)) {
  // 如果调用者指定了将发生写操作,则检查以保证PTE有写权限。如果是这样, 将PTE设为脏。
    if (!write ||
        (pte_write(pte) && pte_dirty(pte)))
  // 如果PTE存在并有权限，则返回由PTE映射的struct page        
      return pte_page(pte);
  }

out:
  // 返回0表明该address没有相应的struct page
  return 0;
}

// include/asm-i386/pgalloc.h
#define pgd_alloc(mm)   get_pgd_fast()

// include/asm-i386/pgalloc.h
static inline pgd_t *get_pgd_fast(void)
{
  unsigned long *ret;

  if ((ret = pgd_quicklist) != NULL) {
    pgd_quicklist = (unsigned long *)(*ret);
    ret[0] = 0;
    pgtable_cache_size--;
  } else
    ret = (unsigned long *)get_pgd_slow();
  return (pgd_t *)ret;
}

// include/asm-i386/pgalloc.h
static inline pgd_t *get_pgd_slow(void)
{
  pgd_t *pgd = (pgd_t *)__get_free_page(GFP_KERNEL);

  if (pgd) {
    memset(pgd, 0, USER_PTRS_PER_PGD * sizeof(pgd_t));
    memcpy(pgd + USER_PTRS_PER_PGD,
      swapper_pg_dir + USER_PTRS_PER_PGD,
      (PTRS_PER_PGD - USER_PTRS_PER_PGD) * sizeof(pgd_t));
  }
  return pgd;
}

// include/asm-i386/pgalloc.h
#define pgd_free(pgd)   free_pgd_slow(pgd)

// include/asm-i386/pgalloc.h
static inline void free_pgd_slow(pgd_t *pgd)
{
#if defined(CONFIG_X86_PAE)
  int i;

  for (i = 0; i < USER_PTRS_PER_PGD; i++)
    free_page((unsigned long)__va(pgd_val(pgd[i])-1));
  kmem_cache_free(pae_pgd_cachep, pgd);
#else
  free_page((unsigned long)pgd);
#endif
}

// include/linux/mm.h
/*
 * On a two-level page table, this ends up being trivial. Thus the
 * inlining and the symmetry break with pte_alloc() that does all
 * of this out-of-line.
 */
 // x86 两级页表，pmd 即为 pgd ?
static inline pmd_t *pmd_alloc(struct mm_struct *mm, pgd_t *pgd, unsigned long address)
{
  if (pgd_none(*pgd))
    return __pmd_alloc(mm, pgd, address);
  return pmd_offset(pgd, address);
}

// include/asm-i386/pgtable-2level.h
static inline int pgd_none(pgd_t pgd)   { return 0; }

static inline pmd_t * pmd_offset(pgd_t * dir, unsigned long address)
{
  return (pmd_t *) dir;
}

// mm/memory.c
/*
 * Allocate page middle directory.
 *
 * We've already handled the fast-path in-line, and we own the
 * page table lock.
 *
 * On a two-level page table, this ends up actually being entirely
 * optimized away.
 */
pmd_t *__pmd_alloc(struct mm_struct *mm, pgd_t *pgd, unsigned long address)
{
  pmd_t *new;

  /* "fast" allocation can happen without dropping the lock.. */
  new = pmd_alloc_one_fast(mm, address);
  if (!new) {
    spin_unlock(&mm->page_table_lock);
    new = pmd_alloc_one(mm, address);
    spin_lock(&mm->page_table_lock);
    if (!new)
      return NULL;

    /*
     * Because we dropped the lock, we should re-check the
     * entry, as somebody else could have populated it..
     */
    if (!pgd_none(*pgd)) {
      pmd_free(new);
      goto out;
    }
  }
  pgd_populate(mm, pgd, new);
out:
  return pmd_offset(pgd, address);
}

// include/asm-i386/pgalloc.h
/*
 * allocating and freeing a pmd is trivial: the 1-entry pmd is
 * inside the pgd, so has no extra memory associated with it.
 * (In the PAE case we free the pmds as part of the pgd.)
 */

#define pmd_alloc_one_fast(mm, addr)  ({ BUG(); ((pmd_t *)1); })
#define pmd_alloc_one(mm, addr)   ({ BUG(); ((pmd_t *)2); })
#define pmd_free_slow(x)    do { } while (0)
#define pmd_free_fast(x)    do { } while (0)
#define pmd_free(x)     do { } while (0)
#define pgd_populate(mm, pmd, pte)  BUG()

// include/asm-x86_64/pgalloc.h
static inline pmd_t *pmd_alloc_one (struct mm_struct *mm, unsigned long addr)
{
  return (pmd_t *)get_zeroed_page(GFP_KERNEL); 
}

// mm/page_alloc.c
unsigned long get_zeroed_page(unsigned int gfp_mask)
{
  struct page * page;

  page = alloc_pages(gfp_mask, 0);
  if (page) {
    void *address = page_address(page);
    clear_page(address);
    return (unsigned long) address;
  }
  return 0;
}

// mm/memory.c
/*
 * Allocate the page table directory.
 *
 * We've already handled the fast-path in-line, and we own the
 * page table lock.
 */
pte_t *pte_alloc(struct mm_struct *mm, pmd_t *pmd, unsigned long address)
{
  if (pmd_none(*pmd)) {
    pte_t *new;

    /* "fast" allocation can happen without dropping the lock.. */
    new = pte_alloc_one_fast(mm, address);
    if (!new) {
      spin_unlock(&mm->page_table_lock);
      new = pte_alloc_one(mm, address);
      spin_lock(&mm->page_table_lock);
      if (!new)
        return NULL;

      /*
       * Because we dropped the lock, we should re-check the
       * entry, as somebody else could have populated it..
       */
      if (!pmd_none(*pmd)) {
        pte_free(new);
        goto out;
      }
    }
    pmd_populate(mm, pmd, new);
  }
out:
  return pte_offset(pmd, address);
}

// include/asm-i386/pgalloc.h
static inline pte_t *pte_alloc_one(struct mm_struct *mm, unsigned long address)
{
  pte_t *pte;

  pte = (pte_t *) __get_free_page(GFP_KERNEL);
  if (pte)
    clear_page(pte);
  return pte;
}

// arch/i386/kernel/setup.c
static unsigned long __init setup_memory(void) {
  unsigned long bootmap_size, start_pfn, max_low_pfn;
  // 将物理地址向上取整到下一页面，返回页帧号。由于_end 是已载入内核
  // 镜像的底端地址，所以 start_pfn 现在是可能被用到的第一块物理页面帧的偏移。
  start_pfn = PFN_UP(__pa(&_end));
  // 遍历 e820 图，查找最高的可用 PFN。
  find_max_pfn();
  // 在 ZONE_NORMAL 中找到可寻址的最高页面帧。
  max_low_pfn = find_max_low_pfn();
  
#ifdef CONFIG_HIGHMEM
  // 如果高端内存可用，则从高端内存区域的 0 位置开始。如果内存在 max_low_pfn 后，
  // 则把高端内存区的起始位置（highstart_pfn）定在那里，而其结束位置定在 max_pfn，
  // 然后打印可用高端内存的提示消息。
  highstart_pfn = highend_pfn = max_pfn;
  if (max_pfn > max_low_pfn) {
    highstart_pfn = max_low_pfn;
  }
  printk(KERN_NOTICE "%ldMB HIGHMEM available.\n",
    pages_to_mb(highend_pfn - highstart_pfn));
#endif

  // 为 config_page_data 节点初始化 bootmem_data 结构。
  // 它设置节点的物理内存起始点（页帧号 start_pfn）和终点（页帧号 max_low_pfn ），
  // 分配一张位图来表示这些页面,并将所有的页面设置为初始时保留。
  bootmap_size = init_bootmem(start_pfn, max_low_pfn);
  // 读入 e820 图，然后为运行时系统中的所有可用页面
  // 调用 free_bootmem() 这将标记页面在初始化时为空闲（即可分配页面）。
  register_bootmem_low_pages(max_low_pfn);
  
  // 保留页面，即相应的位图的位设置为 1
  reserve_bootmem(HIGH_MEMORY, (PFN_PHYS(start_pfn) +
       bootmap_size + PAGE_SIZE-1) - (HIGH_MEMORY));

  // 保留 0 号页面，因为 0 号页面是 BIOS 用到的一个特殊页面。      
  reserve_bootmem(0, PAGE_SIZE);
#ifdef CONFIG_SMP
  // 保留额外的页面为跳板代码用。跳板代码处理用户空间如何进入内核空间。
  reserve_bootmem(PAGE_SIZE, PAGE_SIZE);
#endif
#ifdef CONFIG_ACPI_SLEEP
  // 如果加入了睡眠机制，就需要为它保留内存。这仅为那些有挂起功能的手提
  // 电脑所用到。它已经超过本书的范围。
  acpi_reserve_bootmem();
#endif
  // ...  
  return max_low_pfn;      
}

// arch/i386/kernel/setup.c
// 读入 e820 图，然后为运行时系统中的所有可用页面
// 调用 free_bootmem() 这将标记页面在初始化时为空闲（即可分配页面）。
static void __init register_bootmem_low_pages(unsigned long max_low_pfn)
{
  int i;

  for (i = 0; i < e820.nr_map; i++) {
    unsigned long curr_pfn, last_pfn, size;
    // ...  
    size = last_pfn - curr_pfn;
    free_bootmem(PFN_PHYS(curr_pfn), PFN_PHYS(size));
  }
}

// arch/i386/mm/init.c
static void __init zone_sizes_init(void)
{
  // 初始化大小为 0。
  unsigned long zones_size[MAX_NR_ZONES] = {0, 0, 0};
  unsigned int max_dma, high, low;
  
  // 计算最大可能 DMA 寻址的 PFN。
  // #define MAX_DMA_ADDRESS      (PAGE_OFFSET+0x1000000) 16M
  max_dma = virt_to_phys((char *)MAX_DMA_ADDRESS) >> PAGE_SHIFT;
  // max_low_pfn 是 ZONE_NORMAL 可用的最高 PFN。
  low = max_low_pfn;
  // highest_pfn 是 ZONE_HIGHMEM 可用的最高 PFN。
  high = highend_pfn;

  // 如果在 ZONE_NORMAL 中的最高 PFN 低于 MAX_DMA_ADDRESS，则仅
  // 把 ZONE_DMA 的大小赋值给它,其他管理区仍然为 0。
  if (low < max_dma)
    zones_size[ZONE_DMA] = low;
  else {
  // 设置 ZONE_DMA 中的页面数。
    zones_size[ZONE_DMA] = max_dma;
  // ZONE_NORMAL 的大小等于 max_low_pfn 减去 ZONE_DMA 中的页面数。   
    zones_size[ZONE_NORMAL] = low - max_dma;
#ifdef CONFIG_HIGHMEM
  // ZONE_HIGHMEM 的大小是可能的最高 PFN 减去 ZONE_NORMAL 中可能的最
  // 高 PFN(max_low_pfn)。
    zones_size[ZONE_HIGHMEM] = high - low;
#endif
  }
  free_area_init(zones_size);
}

// mm/page_alloc.c
void __init free_area_init(unsigned long *zones_size)
{
  free_area_init_core(0, &contig_page_data, &mem_map, zones_size, 0, 0, 0);
}

/*
 * Helper functions to size the waitqueue hash table.
 * Essentially these want to choose hash table sizes sufficiently
 * large so that collisions trying to wait on pages are rare.
 * But in fact, the number of active page waitqueues on typical
 * systems is ridiculously low, less than 200. So this is even
 * conservative, even though it seems large.
 *
 * The constant PAGES_PER_WAITQUEUE specifies the ratio of pages to
 * waitqueues, i.e. the size of the waitq table given the number of pages.
 */
#define PAGES_PER_WAITQUEUE 256

// 这一块初始化管理区的等待队列。等待该管理区中页面的进程将会使用这个哈希表选择
// 一个队列等待。这意味着在页面解锁时并不需要唤醒所有的等待进程，仅需要唤醒其中的一
// 个子集。
// wait_table_size() 计算所用哈希表的大小。它基于管理区的页面数和队列数与页面
// 数之间的特定比率完成计算。该哈希表不会大于 4 KB。
// 每 PAGES_PER_WAITQUEUE（256）个使用同一个值
static inline unsigned long wait_table_size(unsigned long pages)
{
  unsigned long size = 1;

  pages /= PAGES_PER_WAITQUEUE;

  while (size < pages)
    size <<= 1;

  /*
   * Once we have dozens or even hundreds of threads sleeping
   * on IO we've got bigger problems than wait queue collision.
   * Limit the size of the wait table to a reasonable size.
   */
  size = min(size, 4096UL);

  return size;
}

// mm/page_alloc.c
/*
 * This is an integer logarithm so that shifts can be used later
 * to extract the more random high bits from the multiplicative
 * hash function before the remainder is taken.
 */
static inline unsigned long wait_table_bits(unsigned long size)
{
  return ffz(~size);
}

// include/linux/wait.h
struct __wait_queue_head {
  wq_lock_t lock;
  struct list_head task_list;
#if WAITQUEUE_DEBUG
  long __magic;
  long __creator;
#endif
};
typedef struct __wait_queue_head wait_queue_head_t;

static inline void init_waitqueue_head(wait_queue_head_t *q)
{
#if WAITQUEUE_DEBUG
  if (!q)
    WQ_BUG();
#endif
  q->lock = WAITQUEUE_RW_LOCK_UNLOCKED;
  INIT_LIST_HEAD(&q->task_list);
#if WAITQUEUE_DEBUG
  q->__magic = (long)&q->__magic;
  q->__creator = (long)current_text_addr();
#endif
}

// include/linux/mm.h
/*
 * The zone field is never updated after free_area_init_core()
 * sets it, so none of the operations on it need to be atomic.
 */
#define NODE_SHIFT 4
#define ZONE_SHIFT (BITS_PER_LONG - 8)

struct zone_struct;
extern struct zone_struct *zone_table[];

static inline zone_t *page_zone(struct page *page)
{
  return zone_table[page->flags >> ZONE_SHIFT];
}

static inline void set_page_zone(struct page *page, unsigned long zone_num)
{
  page->flags &= ~(~0UL << ZONE_SHIFT);
  page->flags |= zone_num << ZONE_SHIFT;
}

#define set_page_count(p,v)   atomic_set(&(p)->count, v)

#define SetPageReserved(page)   set_bit(PG_reserved, &(page)->flags)

/*
 * In order to avoid #ifdefs within C code itself, we define
 * set_page_address to a noop for non-highmem machines, where
 * the field isn't useful.
 * The same is true for page_address() in arch-dependent code.
 */
#if defined(CONFIG_HIGHMEM) || defined(WANT_PAGE_VIRTUAL)

#define set_page_address(page, address)     \
  do {            \
    (page)->virtual = (address);    \
  } while(0)

#else /* CONFIG_HIGHMEM || WANT_PAGE_VIRTUAL */
#define set_page_address(page, address)  do { } while(0)
#endif /* CONFIG_HIGHMEM || WANT_PAGE_VIRTUAL */

/*
 * Builds allocation fallback zone lists.
 */
static inline void build_zonelists(pg_data_t *pgdat)
{
  int i, j, k;

// 遍历最大可能数量的管理区。GFP_ZONEMASK（15）
  for (i = 0; i <= GFP_ZONEMASK; i++) {
    zonelist_t *zonelist;
    zone_t *zone;

// 获取管理区的 zonelist 并归 0。
    zonelist = pgdat->node_zonelists + i;
    memset(zonelist, 0, sizeof(*zonelist));

// 与 ZONE_DMA 对应，j 从 0 开始。
    j = 0;
// 设置 k 为当前检查过的管理区类型。
    k = ZONE_NORMAL;
    if (i & __GFP_HIGHMEM)
      k = ZONE_HIGHMEM;
    if (i & __GFP_DMA)
      k = ZONE_DMA;

    switch (k) {
      default:
        BUG();
      /*
       * fallthrough:
       */
      case ZONE_HIGHMEM:
// 获取 ZONE_HIGHMEM。
        zone = pgdat->node_zones + ZONE_HIGHMEM;
// 如果管理区有内存，ZONE_HIGHMEM 就是从高端内存分配的相应管理区。
// 如果 ZONE_HIGHMEM 没有内存，ZONE_NORMAL 将在下一次变成相应的管理区，这是
// 因为 j 并没有在空管理区时加 1。
        if (zone->size) {
#ifndef CONFIG_HIGHMEM
          BUG();
#endif
          zonelist->zones[j++] = zone;
        }
// 设置下一个相应的管理区中分配的为 ZONE_NORMAL，同样，如果管理区没
// 有内存就不使用它。
      case ZONE_NORMAL:
        zone = pgdat->node_zones + ZONE_NORMAL;
        if (zone->size)
          zonelist->zones[j++] = zone;
      case ZONE_DMA:
// 设置最后的回退管理区为 ZONE_DMA。这个检查也对拥有内存的 ZONE_DMA 
// 进行。在 NUMA 体系结构中，不是所有的节点都有 ZONE_DMA。
        zone = pgdat->node_zones + ZONE_DMA;
        if (zone->size)
          zonelist->zones[j++] = zone;
    }
    zonelist->zones[j++] = NULL;
  } 
}

// include/linux/mmzone.h
#define ZONE_DMA    0
#define ZONE_NORMAL   1
#define ZONE_HIGHMEM    2
#define MAX_NR_ZONES    3

/*
 * One allocation request operates on a zonelist. A zonelist
 * is a list of zones, the first one is the 'goal' of the
 * allocation, the other zones are fallback zones, in decreasing
 * priority.
 *
 * Right now a zonelist takes up less than a cacheline. We never
 * modify it apart from boot-up, and only a few indices are used,
 * so despite the zonelist table being relatively big, the cache
 * footprint of this construct is very small.
 */
typedef struct zonelist_struct {
  zone_t * zones [MAX_NR_ZONES+1]; // NULL delimited
} zonelist_t;

#define GFP_ZONEMASK  0x0f