6.3.2 物理页面的分配和释放

       当一个进程请求分配连续的物理页面时，可以通过调用alloc_pages()来完成。Linux2.4版本中有两个alloc_pages() ，一个在mm/numa.c中，另一个在mm/page_alloc,c中       ，编译时根据所定义的条件选项CONFIG_DISCONTIGMEM来进行取舍。

1．非一致存储结构（NUMA）中页面的分配。

CONFIG_DISCONTIGMEM条件编译的含义是“不连续的存储空间”，Linux把不连续的存储空间也归类为非一致存储结构（NUMA）。这是因为，不连续的存储空间本质上是一种广义的NUMA，因为那说明在最低物理地址和最高物理地址之间存在着空洞，而有空洞的空间当然是“不一致”的。所以，在地址不连续的物理空间也要像结构不一样的物理空间那样划分出若干连续且均匀的“节点”。因此，在存储结构不连续的系统中，每个模块都由若干个节点，因而都有个pg_data_t数据结构队列。  我们先来看mm/numa.c中的alloc_page()函数：

 

/*

  * This can be refined. Currently, tries to do round robin, instead

  * should do concentratic circle search, starting from current node.

  */

struct page * _alloc_pages(unsigned int gfp_mask, unsigned int order)

{

         struct page *ret = 0;

         pg_data_t *start, *temp;

#ifndef CONFIG_NUMA

         unsigned long flags;

         static pg_data_t *next = 0;

#endif

 

         if (order >= MAX_ORDER)

                 return NULL;

#ifdef CONFIG_NUMA

         temp = NODE_DATA(numa_node_id());

#else

         spin_lock_irqsave(&node_lock, flags);

         if (!next)  next = pgdat_list;

         temp = next;

         next = next->node_next;

         spin_unlock_irqrestore(&node_lock, flags);

#endif

         start = temp;

         while (temp) {

                 if ((ret = alloc_pages_pgdat(temp, gfp_mask, order)))

                         return(ret);

                 temp = temp->node_next;

         }

         temp = pgdat_list;

         while (temp != start) {

                 if ((ret = alloc_pages_pgdat(temp, gfp_mask, order)))

                         return(ret);

                 temp = temp->node_next;

         }

         return(0);

  }

对该函数的说明如下：

·     该函数有两个参数。gfp_mask表示采用哪种分配策略。参数order表示所需物理块的大小，可以是1、2、3直到2MAX_ORDER-1。

·     如果定义了CONFIG_NUMA，也就是在NUMA结构的系统中，可以通过NUMA_DATA（）宏找到CPU所在节点的pg_data_t数据结构队列，并存放在临时变量temp中。

·     如果在不连续的UMA结构中，则有个pg_data_t数据结构的队列pgdat_list，pgdat_list就是该队列的首部。因为队列一般都是临界资源，因此，在对该队列进行两个以上的操作时要加锁。

·     分配时轮流从各个节点开始，以求各节点负荷的平衡。函数中有两个循环，其形式基本相同，也就是，对节点队列基本进行两遍扫描，直至在某个节点内分配成功，则跳出循环，否则，则彻底失败，从而返回0。对于每个节点，调用alloc_pages_pgdat（）函数试图分配所需的页面。

2. 一致存储结构(UMA)中页面的分配

   连续空间UMA结构的alloc_page()是在include/linux/mm.h中定义的：

   #ifndef CONFIG_DISCONTIGMEM

     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,

                 contig_page_data.node_zonelists+(gfp_mask & GFP_ZONEMASK));

    }

    #endif

 

从这个函数的定义可以看出，alloc_page()是_alloc_pages（）的封装函数，而_alloc_pages（）才是伙伴算法的核心。这个函数定义于mm/page_alloc.c中，我们先对此函数给予概要描述。

_alloc_pages（）在管理区链表zonelist中依次查找每个区，从中找到满足要求的区，然后用伙伴算法从这个区中分配给定大小（2 order个）的页面块。如果所有的区都没有足够的空闲页面，则调用swapper或 bdflush内核线程，把脏页写到磁盘以释放一些页面。

在__alloc_pages()和虚拟内存（简称VM）的代码之间有一些复杂的接口（后面会详细描述）。每个区都要对刚刚被映射到某个进程VM的页面进行跟踪，被映射的页面也许仅仅做了标记，而并没有真正地分配出去。因为根据虚拟存储的分配原理，对物理页面的分配要尽量推迟到不能再推迟为止，也就是说，当进程的代码或数据必须装入到内存时，才给它真正分配物理页面。

   搞清楚页面分配的基本原则后，我们对其代码具体分析如下：

/*

     * 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 = *zone;

                min = 1UL << order;

              for (;;) {

                     zone_t *z = *(zone++);

                     if (!z)

                              break;

 

                 min += z->pages_low;

                 if (z->free_pages > min) {

                         page = rmqueue(z, order);

                         if (page)

                                 return page;

                 }

        }

 

这是对一个分配策略中所规定的所有页面管理区的循环。循环中依次考察各个区中空闲页面的总量，如果总量尚大于“最低水位线”与所请求页面数之和，就调用rmqueue（）试图从该区中进行分配。如果分配成功，则返回一个page结构指针，指向页面块中第一个页面的起始地址。

 

         classzone->need_balance = 1;

         mb();

         if (waitqueue_active(&kswapd_wait))

                 wake_up_interruptible(&kswapd_wait);

 

如果发现管理区中的空闲页面总量已经降到最低点，则把zone_t结构中需要重新平衡的标志（need_balance）置1，而且如果内核线程kswapd在一个等待队列中睡眠，就唤醒它，让它收回一些页面以备使用（可以看出，need_balance是和kswapd配合使用的）。

 

         zone = zonelist->zones;

         min = 1UL << order;

         for (;;) {

                 unsigned long local_min;

                 zone_t *z = *(zone++);

                 if (!z)

                         break;

 

                 local_min = z->pages_min;

                 if (!(gfp_mask & __GFP_WAIT))

                         local_min >>= 2;

                 min += local_min;

                 if (z->free_pages > min) {

                         page = rmqueue(z, order);

                         if (page)

                                 return page;

                 }

         }

 

 如果给定分配策略中所有的页面管理区都分配失败，那只好把原来的“最低水位”再向下调（除 以4），然后看是否满足要求（z->free_pages > min），如果能满足要求，则调用rmqueue（）进行分配。

 

         /* here we're in the low on memory slow path */

 

rebalance:

         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;

           }

   

 如果分配还不成功，这时候就要看是哪类进程在请求分配内存页面。其中PF_MEMALLOC和PF_MEMDIE是进程的task_struct结构中flags域的值，对于正在分配页面的进程（如kswapd内核线程），则其PF_MEMALLOC的值为1（一般进程的这个标志为0），而对于使内存溢出而被杀死的进程，则其PF_MEMDIE为1。不管哪种情况，都说明必须给该进程分配页面（想想为什么）。因此，继续进行分配。

 

         /* Atomic allocations - we can't balance anything */

         if (!(gfp_mask & __GFP_WAIT))

                 return NULL;

 

如果请求分配页面的进程不能等待，也不能被重新调度，只好在没有分配到页面的情况下“空手”返回。

 

         page = balance_classzone(classzone, gfp_mask, order, &freed);

         if (page)

                 return page;

 

如果经过几番努力，必须得到页面的进程（如kswapd）还没有分配到页面，就要调用balance_classzone（）函数把当前进程所占有的局部页面释放出来。如果释放成功，则返回一个page结构指针，指向页面块中第一个页面的起始地址。

 

         zone = zonelist->zones;

         min = 1UL << order;

        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 *

         if (order > 3)

                return NULL;

 

        /* Yield for kswapd, and try again */

         current->policy |= SCHED_YIELD;

         __set_current_state(TASK_RUNNING);

        schedule();

         goto rebalance;

       }

   在这个函数中，频繁调用了rmqueue（）函数，下面我们具体来看一下这个函数内容：

 （1）rmqueue（）函数

该函数试图从一个页面管理区分配若干连续的内存页面。这是最基本的分配操作，其具体代码如下：

static struct page * rmqueue(zone_t *zone, unsigned int order)

{

         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);

         do {

                 head = &area->free_list;

                 curr = memlist_next(head);

 

                 if (curr != head) {

                         unsigned int index;

 

                         page = memlist_entry(curr, struct page, list);

                         if (BAD_RANGE(zone,page))

                                 BUG();

                         memlist_del(curr);

                         index = page - zone->zone_mem_map;

                         if (curr_order != MAX_ORDER-1)

                                 MARK_USED(index, curr_order, area);

                         zone->free_pages -= 1UL << order;

 

                         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;

 }

对该函数的解释如下：

·     参数zone指向要分配页面的管理区，order表示要求分配的页面数为2 order。

·     do循环从free_area数组的第order个元素开始，扫描每个元素中由page结构组成的双向循环空闲队列。如果找到合适的页块，就把它从队列中删除，删除的过程是不允许其他进程、其他处理器来打扰的。所以要用spin_lock_irqsave（）将这个循环加上锁。

·     首先在恰好满足大小要求的队列里进行分配。其中memlist_entry(curr, struct page, list)获得空闲块的第一个页面的地址，如果这个地址是个无效的地址，就陷入BUG()。如果有效，memlist_del(curr)从队列中摘除分配出去的页面块。如果某个页面块被分配出去，就要在frea_area的位图中进行标记，这是通过调用MARK_USED（）宏来完成的。

·     如果分配出去后还有剩余块，就通过expand（）获得所分配的页块,而把剩余块链入适当的空闲队列中。

·     如果当前空闲队列没有空闲块，就从更大的空闲块队列中找。

 （2）expand（）函数

     该函数源代码如下：

     static inline struct page * expand (zone_t *zone, struct page *page,

          unsigned long index, int low, int high, free_area_t * area)

  {

         unsigned long size = 1 << high;

 

         while (high > low) {

                 if (BAD_RANGE(zone,page))

                         BUG();

                 area--;

                 high--;

                 size >>= 1;

                 memlist_add_head(&(page)->list, &(area)->free_list);

                 MARK_USED(index, high, area);

                 index += size;

                 page += size;

         }

         if (BAD_RANGE(zone,page))

                 BUG();

         return page;

  }

   对该函数解释如下：

·      参数zone指向已分配页块所在的管理区；page指向已分配的页块；index是已分配的页面在mem_map中的下标； low表示所需页面块大小为2 low，而high表示从空闲队列中实际进行分配的页面块大小为2 high；area是free_area_struct结构，指向实际要分配的页块。

·      通过上面介绍可以知道，返回给请求者的块大小为2low个页面，并把剩余的页面放入合适的空闲队列，且对伙伴系统的位图进行相应的修改。例如，假定我们需要一个2页面的块，但是，我们不得不从order为3（8个页面）的空闲队列中进行分配，又假定我们碰巧选择物理页面800作为该页面块的底部。在我们这个例子中，这几个参数值为：

page == mem_map+800

index == 800

   low == 1

   high == 3

      area == zone->free_area+high ( 也就是frea_area数组中下标为3的元素)

·      首先把size初始化为分配块的页面数(例如，size = 1<<3 == 8)

·      while循环进行循环查找。每次循环都把size减半。如果我们从空闲队列中分配的一个块与所要求的大小匹配，那么low = high，就彻底从循环中跳出，返回所分配的页块。

·      如果分配到的物理块所在的空闲块大于所需块的大小（即2 high>2low），那就将该空闲块分为两半（即area--;high--; size >>= 1）,然后调用memlist_add_head（）把刚分配出去的页面块又加入到低一档（物理块减半）的空闲队列中，准备从剩下的一半空闲块中重新进行分配，并调用MARK_USED（）设置位图。

·      在上面的例子中，第1次循环，我们从页面800开始，把页面大小为4（即2high--）的块其首地址插入到frea_area[2]中的空闲队列；因为low<high，又开始第2次循环，这次从页面804开始，把页面大小为2的块插入到frea_area[1]中的空闲队列，此时，page＝806，high=low＝1，退出循环，我们给调用者返回从806页面开始的一个2页面块。

·      从这个例子可以看出，这是一种巧妙的分配算法。

3． 释放页面

   从上面的介绍可以看出,页面块的分配必然导致内存的碎片化，而页面块的释放则可以将页面块重新组合成大的页面块。页面的释放函数为__free_pages(page struct *page, unsigned long order) ，该函数从给定的页面开始，释放的页面块大小为2order。原函数为:

 

void __free_pages(page struct *page, unsigned long order)

{

          if (!PageReserved(page) && put_page_testzero(page))

           __free_pages_ok(page, order);

}

       

其中比较巧妙的部分就是调用put_page_testzero()宏,该函数把页面的引用计数减1,如果减1后引用计数为0，则该函数返回1。因此，如果调用者不是该页面的最后一个用户，那么，这个页面实际上就不会被释放。另外要说明的是不可释放保留页PageReserved，这是通过PageReserved（）宏进行检查的。

如果调用者是该页面的最后一个用户，则__free_pages() 再调用 __free_pages_ok()。__free_pages_ok（）才是对页面块进行释放的实际函数，该函数把释放的页面块链入空闲链表，并对伙伴系统的位图进行管理，必要时合并伙伴块。这实际上是expand()函数的反操作，我们对此不再进行详细的讨论。