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

// include/linux/mm.h
// gfp_mask (Get Free Pages) 标志表明分配器如何操作。如，如果没有设置 GFP_WAIT，
// 分配器将不会阻塞，而是在内存紧张时返回 NULL，b是分配页面数的 2 的幂。
static inline struct page * alloc_pages(unsigned int gfp_mask, unsigned int order)
{
  /*
   * Gets optimized away by the compiler.
   */
  // 在编译时的调试检查。  
  if (order >= MAX_ORDER)
    return NULL;
  return _alloc_pages(gfp_mask, order);
}

// include/linux/mm.h
/*
 * GFP bitmasks..
 */
/* Zone modifiers in GFP_ZONEMASK (see linux/mmzone.h - low four bits) */
#define __GFP_DMA 0x01
#define __GFP_HIGHMEM 0x02

// mm/page_alloc.c
/*
 * This is the 'heart' of the zoned buddy allocator:
 */
struct page * __alloc_pages(unsigned int gfp_mask, unsigned int order, 
              zonelist_t *zonelist)
{
  unsigned long min;
  zone_t **zone, * classzone;
  struct page * page;
  int freed;

  // 设置该管理区为要从中分配的合适管理区。
  zone = zonelist->zones;
  // 合适的管理区标记为 classzone。如果在后面达到一个页面的极值，则 classzone 标记
  // 为需要平衡。
  classzone = *zone;
  // 不需要的有效性检查。build_zonelists()需要被严重地打散。
  if (classzone == NULL)
    return NULL;

// 这一块的风格似乎在这个函数中出现多次。它读作 "遍历在该回退链表中的所
// 有管理区，看是否有一个分配器可以在不超过极值的情况下满足条件" 。每个回退管理区的
// pages_low 加到一起。这里特意减少使用一个回退管理区的概率。   
  min = 1UL << order;
  for (;;) {
  // z 是当前检查的管理区。 zone 变量移到下一个回退管理区。
    zone_t *z = *(zone++);
  // 如果这是回退链表的最后一个管理区，则退出循环。    
    if (!z)
      break;

  // 为方便比较，将该极值分配器的页面数加 1，这一步在每个回退管理区的每个区域中
  // 都进行。虽然这看起来像是一个 bug，但它实际上是想减少使用回退管理区的概率。
    min += z->pages_low;
  // 如果页面块分配可以不超过 pages_min 极值，就分配一块页面块。rmqueue() 
  // 负责从管理区中重新移动该页面块。   
    if (z->free_pages > min) {
      page = rmqueue(z, order);
  // 如果可以分配该页，则这里返回一个指向它们的指针。     
      if (page)
        return page;
    }
  }

  // 标记合适的管理区为需要平衡。这个标志位将在后面由 kswapd 读取。
  classzone->need_balance = 1;
  // 这是一个内存界限。它保证所有的 CPU 都可以看到在这行代码之前的所有变化。
  // 这很重要，因为 kswapd 除了在内存分配器上运行外还可以在不同的处理器上运行。
  mb();
  // 如果 kswapd 处于睡眠状态，则唤醒它。
  if (waitqueue_active(&kswapd_wait))
    wake_up_interruptible(&kswapd_wait);

  // 以第一个合适的管理区和 min 值再次开始。
  zone = zonelist->zones;
  min = 1UL << order;
// 遍历所有的管理区。这一次，如果不超过 page_min 的极限值则分配一页。 
  for (;;) {
    unsigned long local_min;
    zone_t *z = *(zone++);
    if (!z)
      break;

  // local_min 表明该管理区可以拥有的空闲页数量。
    local_min = z->pages_min;
  // 如果该进程不能等待或者重调度 (__GFP_WAIT 清空) ，在这里允许管理区进
  // 一步增加比普通极值还要大的内存压力。   
    if (!(gfp_mask & __GFP_WAIT))
      local_min >>= 2;
    min += local_min;
    if (z->free_pages > min) {
      page = rmqueue(z, order);
      if (page)
        return page;
    }
  }

  /* here we're in the low on memory slow path */
// 在试着同步空闲页面后返回这个标号。从这一行起，就达到了内存路径的低端，在这
// 种情形下，进程很可能会睡眠。
rebalance:
  // OOM 管理程序只会设置两个标志。由于进程试着完整地杀死它自身，在可能
  // 的情况下，将分配页面，因为知道马上就可以释放这些页面。
  if (current->flags & (PF_MEMALLOC | PF_MEMDIE)) {
    zone = zonelist->zones;
    for (;;) {
      zone_t *z = *(zone++);
      if (!z)
        break;

      page = rmqueue(z, order);
      if (page)
        return page;
    }
    return NULL;
  }

  /* Atomic allocations - we can't balance anything */
  // 如果调用进程无法睡眠，这里返回 NULL，因为分配页面的惟一途径是调用睡眠。
  if (!(gfp_mask & __GFP_WAIT))
    return NULL;

  // balance_classzone() 同步进行 kswapd 的工作。主要的区别在于，它
  // 不是将内存释放到一个全局的池中，而是保证进程始终使用 curren→local_pages 链表。
  page = balance_classzone(classzone, gfp_mask, order, &freed);
  // 如果已经按顺序释放了一个页块，这里就返回该页块。由于高次页面可能被释
  // 放，所以这里 NULL 并不意味着分配失败。
  if (page)
    return page;

  zone = zonelist->zones;
  min = 1UL << order;

// 这里与前面块相似。如果可以不超过 pages_min 极值则可以分配一页块。 
  for (;;) {
    zone_t *z = *(zone++);
    if (!z)
      break;

    min += z->pages_min;
    if (z->free_pages > min) {
      page = rmqueue(z, order);
      if (page)
        return page;
    }
  }

  /* Don't let big-order allocations loop */
  // 要满足一次分配一块如 2^4 那样数量的页面比较困难。如果现在还没有满足，那
  // 么最好直接返回 NULL。
  if (order > 3)
    return NULL;

  /* Yield for kswapd, and try again */
  // 阻塞进程，以给 kswapd 工作的机会。
  yield();
  // 试着再次平衡和分配管理区。
  goto rebalance;
}

// include/linux/wait.h
static inline int waitqueue_active(wait_queue_head_t *q)
{
#if WAITQUEUE_DEBUG
  if (!q)
    WQ_BUG();
  CHECK_MAGIC_WQHEAD(q);
#endif

  return !list_empty(&q->task_list);
}

// include/linux/sched.h
// 只会唤醒那些执行可中断休眠的进程
#define wake_up_interruptible(x)  __wake_up((x),TASK_INTERRUPTIBLE, 1)

// kernel/sched.c
void __wake_up(wait_queue_head_t *q, unsigned int mode, int nr)
{
  if (q) {
    unsigned long flags;
    wq_read_lock_irqsave(&q->lock, flags);
    __wake_up_common(q, mode, nr, 0);
    wq_read_unlock_irqrestore(&q->lock, flags);
  }
}

// kernel/sched.c
/**
 * yield - yield the current processor to other threads.
 *
 * this is a shortcut for kernel-space yielding - it marks the
 * thread runnable and calls sys_sched_yield().
 */
void yield(void)
{
  set_current_state(TASK_RUNNING);
  sys_sched_yield();
  schedule();
}

// mm/page_alloc.c
static FASTCALL(struct page * rmqueue(zone_t *zone, unsigned int order));
// 参数是要从中分配的区域和页面所需的幂次。
static struct page * rmqueue(zone_t *zone, unsigned int order)
{
  // 由于 free_area 是顺序链表的一个数组，幂次可以用作数组中的下标。
  free_area_t * area = zone->free_area + order;
  unsigned int curr_order = order;
  struct list_head *head, *curr;
  unsigned long flags;
  struct page *page;

  //  获取一个管理区锁。
  spin_lock_irqsave(&zone->lock, flags);
// 这个 while 块负责找到我们需要分配的页面次。如果空闲块处于我们感兴趣
// 的次中，这里就检查更高的块直到找到更加适合的块。 
  do {
    // head 是该次空闲页块的链表。
    head = &area->free_list;
    // curr 是页面的第一块。
    curr = head->next;

// 如果空闲页块处于这一次，这里就开始分配。
    if (curr != head) {
      unsigned int index;
  // 该页设置为指向空闲块的第一个页面的指针。
      page = list_entry(curr, struct page, list);
  // 有效性检查保证该页属于这个管理区以及处于 zone_mem_map 中。现在还不
  // 清楚是否可能发生在分配器自身将块放到错误的管理区中而不是严重 bug 的情况。      
      if (BAD_RANGE(zone,page))
        BUG();
  // 由于该块将被分配，这里就从空闲链表中移除。        
      list_del(curr);
  // index 将 zone_mem_map 看做一个由页面组成的数组，下标就是该数组中的偏移。     
      index = page - zone->zone_mem_map;
  // 表示伙伴对的位置位。MARX_USED() 是一个计算置位的宏。     
      if (curr_order != MAX_ORDER-1)
        MARK_USED(index, curr_order, area);
  // 更新该管理区统计。1UL << order 是要分配的页面数。        
      zone->free_pages -= 1UL << order;
  // expand() 是负责分割高次页面块的函数。
      page = expand(zone, page, index, order, curr_order, area);
  // 不再需要进一步更新管理区，所以这里释放锁。      
      spin_unlock_irqrestore(&zone->lock, flags);
  // 表明页面正在使用中。
      set_page_count(page, 1);
  // 进行有效性检查。     
      if (BAD_RANGE(zone,page))
        BUG();
      if (PageLRU(page))
        BUG();
      if (PageActive(page))
        BUG();
  // 由于已经成功分配页面块，所以返回它。       
      return page;  
    }
  // 如果没有释放正确次的页面块，这里就将转移到高次页面块，看在那里可以找到什么。   
    curr_order++;
    area++;
  } while (curr_order < MAX_ORDER);
  // 不再需要进一步更新管理区，所以这里释放锁。
  spin_unlock_irqrestore(&zone->lock, flags);
  // 没有所请求页面块或者更高次页面块可用，所以这里返回失败。
  return NULL;
}

// mm/page_alloc.c
#define MARK_USED(index, order, area) \
  __change_bit((index) >> (1+(order)), (area)->map)

//  mm/page_alloc.c
// zone 是从中分配的地方。
// page 是要待分割块的一个页面。
// index 是在 mem_map 中的页面索引。
// low 是需要分配的页面次。
// high 是分配时要分割的页面次。
// area 是代表高次页面块的 free_area_t。
static inline struct page * expand (zone_t *zone, struct page *page,
   unsigned long index, int low, int high, free_area_t * area)
{
  // size 是待分割的页面数量。
  unsigned long size = 1 << high;

// 不断分割，直到找到了所需页面次的一块。
  while (high > low) {
  // 有效性检查保证该页面属于该管理区，且在 zone_mem_map 中。
    if (BAD_RANGE(zone,page))
      BUG();
  // area 是现在表示低次页面块的下一个 free_area_t。     
    area--;
  // high 是待分割页面块的下一次。    
    high--;
  // 分割块的大小是原来大小的一半。    
    size >>= 1;
  // 在伙伴对中，mem_map 中较低的那一个加入到低次的空闲包表中。    
    list_add(&(page)->list, &(area)->free_list);
  // 表示伙伴对的位置位。   
    MARK_USED(index, high, area);
  // index 是现在新创建伙伴对的第 2 个伙伴索引。 
    index += size;
  // page 现在指向新创建伙伴对的第 2 个伙伴。   
    page += size;
  }
  // 有效性检查。
  if (BAD_RANGE(zone,page))
    BUG();
  // 已经成功分割一块。所以返回页面。   
  return page;
}

// mm/page_alloc.c
static struct page * FASTCALL(
          balance_classzone(zone_t *, unsigned int, unsigned int, int *));
static struct page * balance_classzone(zone_t * classzone, unsigned int gfp_mask, 
                    unsigned int order, int * freed)
{
  struct page * page = NULL;
  int __freed = 0;

  // 如果调用者不允许睡眠，这里转到 out 退出该函数。如果发生睡眠，这个函数
  // 将必须直接调用，或者 __alloc_pages() 需要被故意中断。
  if (!(gfp_mask & __GFP_WAIT))
    goto out;
  // 这个函数可能不会被突然使用。另外，发生这种条件必须引入故意的损坏。
  if (in_interrupt())
    BUG();

  // 记录在 current->allocation_order 的分配大小。虽然它可能用于将特定次的页面加
  // 入到 local_pages 链表中，但实际上这没有用。链表中页面的次存放在 page→index 中。
  current->allocation_order = order;
  // 设置释放函数的标志以将页面加入 local_list。
  current->flags |= PF_MEMALLOC | PF_FREE_PAGES;

  // 利用 try_to_free_pages_zone() 直接从特定管理区中释放页面。这也
  // 是 kswapd 与直接回收路径交互的地方。
  __freed = try_to_free_pages_zone(classzone, gfp_mask);
  // 再一次清除标志位，这样释放函数不会继续将页面加入到 local_pages 链表中。
  current->flags &= ~(PF_MEMALLOC | PF_FREE_PAGES);

// 假设页面在 local_pages 链表中，这个函数将遍历链表查找属于特定管理区和次的页面块。
  // 如果页面存放在局部链表中则仅进入这一块。
  if (current->nr_local_pages) {
    struct list_head * entry, * local_pages;
    struct page * tmp;
    int nr_pages;
    
  // 从链表头开始。
    local_pages = &current->local_pages;

  // 如果利用 try_to_free_pages_zone() 释放了页面，则 ......
    if (likely(__freed)) {
      /* pick from the last inserted so we're lifo */
  // 插入的最后一页选择为第 1 页，因为这可能是一次高速缓存命中，而且一般都使用最
  // 近引用过的页面。     
      entry = local_pages->next;
// 遍历链表中所有页面，直到我们找到合适的管理区和次。      
      do {
  // 从链表项中获取页面。     
        tmp = list_entry(entry, struct page, list);
  // 页面块的次存放在 page→index 中，所以这里检查该次是否与请求的次相符以及它是
  // 否属于正确的管理区。虽然链表中的页面还不太可能来自于其他管理区，但是如果调用
  // swap_out() 将页面直接从进程页表中释放，这种情况还是有可能发生的。       
        if (tmp->index == order && memclass(page_zone(tmp), classzone)) {
  // 这是一个处于正确次和管理区的页面，所以从链表中移除它。        
          list_del(entry);
  // 将链表的页面块数量减 1。          
          current->nr_local_pages--;
  // 设置页面计数为 1，因为它将被释放。         
          set_page_count(tmp, 1);
  // 设置 page 因为它可能返回。需要 tmp 在下一块中释放局部链表中的剩余页。         
          page = tmp;
  // 进行在 __free_pages_ok() 中相同的检查以确保释放该页的安全。
          if (page->buffers)
            BUG();
          if (page->mapping)
            BUG();
          if (!VALID_PAGE(page))
            BUG();
          if (PageLocked(page))
            BUG();
          if (PageLRU(page))
            BUG();
          if (PageActive(page))
            BUG();
          if (PageDirty(page))
            BUG();

          break;
        }
  // 如果当前页面不在特定的次和管理区中则移到链表中的下一页。       
      } while ((entry = entry->next) != local_pages);
    }

// 这一块释放链表中的剩余页面。
  // 获取那些待释放的页面块数量。
    nr_pages = current->nr_local_pages;
    /* free in reverse order so that the global order will be lifo */
  // 循环直到 local_pages 链表变为空。    
    while ((entry = local_pages->prev) != local_pages) {
  // 从链表中移除该页面块。    
      list_del(entry);
  // 获取 struct page 对应的表项。      
      tmp = list_entry(entry, struct page, list);
  // 利用 __free_pages_ok() 释放页面。     
      __free_pages_ok(tmp, tmp->index);
  // 如果页面块的引用计数达到 0，而页面还在链表中，则意味着计数在某个地方被
  // 严重地打乱，或者某个人手动将页面加入到 local_pages 链表中，所以这里调用 BUG()。      
      if (!nr_pages--)
        BUG();
    }
  // 设置页面块数量为 0，因为它们都将被释放。    
    current->nr_local_pages = 0;
  }
 out:
  // 更新 freed 参数告知调用者总共释放了多少页面。
  *freed = __freed;
  // 返回请求次和管理区的页面块。如果释放失败，这里将返回 NULL。
  return page;
}

// include/linux/mmzone.h
#define memclass(pgzone, classzone) (((pgzone)->zone_pgdat == (classzone)->zone_pgdat) \
      && ((pgzone) <= (classzone)))

// include/linux/mm.h
#define alloc_page(gfp_mask) alloc_pages(gfp_mask, 0)

// include/linux/mm.h
#define __get_free_page(gfp_mask) \
    __get_free_pages((gfp_mask),0)

// mm/page_alloc.c
/*
 * Common helper functions.
 */
unsigned long __get_free_pages(unsigned int gfp_mask, unsigned int order)
{
  struct page * page;

  page = alloc_pages(gfp_mask, order);
  if (!page)
    return 0;
  // 返回页面虚拟地址   
  return (unsigned long) page_address(page);
}

// include/linux/mm.h
/*
 * Permanent address of a page. Obviously must never be
 * called on a highmem page.
 */
#if defined(CONFIG_HIGHMEM) || defined(WANT_PAGE_VIRTUAL)

#define page_address(page) ((page)->virtual)

#else /* CONFIG_HIGHMEM || WANT_PAGE_VIRTUAL */

#define page_address(page)            \
  __va( (((page) - page_zone(page)->zone_mem_map) << PAGE_SHIFT)  \
      + page_zone(page)->zone_start_paddr)

#endif /* CONFIG_HIGHMEM || WANT_PAGE_VIRTUAL */

// include/linux/mm.h
#define __get_dma_pages(gfp_mask, order) \
    __get_free_pages((gfp_mask) | GFP_DMA,(order))
  // gfp_mask 与 GFP_DMA 进行或操作, 告知分配器从 ZONE_DMA 中分配。   

// mm/page_alloc.c
// gfp_mask 是影响分配器行为的标志位。
unsigned long get_zeroed_page(unsigned int gfp_mask)
{
  struct page * page;
  // alloc_pages() 完成分配器页面块的工作
  page = alloc_pages(gfp_mask, 0);
  if (page) {
  // page_address() 返回页面的虚拟地址。
    void *address = page_address(page);
  // clear_page()将页面内容清零。   
    clear_page(address);
  // 返回清零后的页面。    
    return (unsigned long) address;
  }
  return 0;
}

// include/asm-i386/page.h
#ifdef CONFIG_X86_USE_3DNOW

#include <asm/mmx.h>

#define clear_page(page)  mmx_clear_page((void *)(page))
#define copy_page(to,from)  mmx_copy_page(to,from)

#else

/*
 *  On older X86 processors its not a win to use MMX here it seems.
 *  Maybe the K6-III ?
 */
 
#define clear_page(page)  memset((void *)(page), 0, PAGE_SIZE)
#define copy_page(to,from)  memcpy((void *)(to), (void *)(from), PAGE_SIZE)

#endif