首先介绍几个重要的数据结构。
1、page
typedef struct page {struct list_head list;struct address_space *mapping;unsigned long index;struct page *next_hash;atomic_t count;unsigned long flags;/* atomic flags, some possibly updated asynchronously */struct list_head lru;unsigned long age;wait_queue_head_t wait;struct page **pprev_hash;struct buffer_head * buffers;void *virtual; /* non-NULL if kmapped */struct zone_struct *zone;} mem_map_t; 其中virtual指向实际的页面内存地址。
2、zone_struct
typedef struct zone_struct {/* * Commonly accessed fields: */spinlock_tlock;unsigned longoffset;unsigned longfree_pages;unsigned longinactive_clean_pages;unsigned longinactive_dirty_pages;unsigned longpages_min, pages_low, pages_high;/* * free areas of different sizes */struct list_headinactive_clean_list;free_area_tfree_area[MAX_ORDER];/* * rarely used fields: */char*name;unsigned longsize;/* * Discontig memory support fields. */struct pglist_data*zone_pgdat;unsigned longzone_start_paddr;unsigned longzone_start_mapnr;struct page*zone_mem_map;} zone_t;#define ZONE_DMA0#define ZONE_NORMAL1#define ZONE_HIGHMEM2#define MAX_NR_ZONES3
3、free_area_t
typedef struct free_area_struct {struct list_headfree_list;unsigned int*map;} free_area_t;
系统中的每一个物理页面都有一个page结构(或者mem_map_t)。系统在初始化时根据物理内存的大小建立起一个page结构数组mem_map，作为物理页面的“仓库”，里面的每个page数据结构都代表着系统中的一个物理页面。每个物理页面的page结构在这个数组里的下标就是该物理页面的序号。
“仓库”里的物理页面划分为ZONE_DMA和ZONE_NORMAL两个管理区。每个管理区都有一个数据结构，即zone_struct数据结构。在zone_struct数据结构中有一组“空闲区间”(free_area_t)队列。为什么是“一组”队列，而不是"一个"队列呢？这也是因为常常需要成“块”地分配在物理空间内连续的多个页面，所以要按块的大小分别加以管理。因此，在管理区数据结构中既要有一个队列来保持一些离散(连续长度为1)的物理页面，还要有一个队列来保持一个连续长度为2的页面块，以及连续长度为4、8、16 … 直到2 ^ MAX_ORDER的页面块。常数MAX_ORDER定义为10，也就是说最大的连续页面块可以达到2 ^ 10=1024个页面，即4M字节。
管理区结构中的offset表示该分区在mem_map中的起始页面号。一旦建立起管理区，每个物理页面便永久地属于某一个管理区，具体取决于页面的起始地址，就好像一幢建筑物属于哪一个派出所管辖取决于其地址一样。
空闲区free_area_struct结构中用来维持双向链队列的结构list_head是一个通用的数据结构。回到上面的page结构，其中的第一个成分就是一个list_head结构，物理页面的page结构正是通过它进入free_area_struct结构中的双向链队列的。
alloc_pages分配内存，如下：
static inline struct page * alloc_pages(int gfp_mask, unsigned long order){/* * Gets optimized away by the compiler. */if (order >= MAX_ORDER)return NULL;return __alloc_pages(contig_page_data.node_zonelists+(gfp_mask), order);}
其中contig_page_data.node_zonelists如下：
typedef struct zonelist_struct {zone_t * zones [MAX_NR_ZONES+1]; // NULL delimitedint gfp_mask;} zonelist_t; __alloc_pages函数如下：/* * This is the ‘heart’ of the zoned buddy allocator: */struct page * __alloc_pages(zonelist_t *zonelist, unsigned long order){zone_t **zone;int direct_reclaim = 0;unsigned int gfp_mask = zonelist->gfp_mask;struct page * page;……memory_pressure++;……if (order == 0 && (gfp_mask & __GFP_WAIT) &&!(current->flags & PF_MEMALLOC))direct_reclaim = 1;//如果要求分配的只是单个页面，并且要等待分配完成，又不是用于管理目的，则把一个局部量direct_reclaim设成1，表示可以从相应页面管理区的"不活跃干净页面"缓冲队列中回收……if (inactive_shortage() > inactive_target / 2 && free_shortage())wakeup_kswapd(0);//唤醒kswapd内核线程……else if (free_shortage() && nr_inactive_dirty_pages > free_shortage()&& nr_inactive_dirty_pages >= freepages.high)wakeup_bdflush(0);//唤醒bdflush内核线程try_again:……zone = zonelist->zones;for (;;) {zone_t *z = *(zone++);if (!z)break;if (!z->size)BUG();if (z->free_pages >= z->pages_low) {page = rmqueue(z, order);//试图从该管理区中分配if (page)return page;} else if (z->free_pages < z->pages_min &&waitqueue_active(&kreclaimd_wait)) {wake_up_interruptible(&kreclaimd_wait);//唤醒kreclaimd}}……page = __alloc_pages_limit(zonelist, order, PAGES_HIGH, direct_reclaim);//不断降低水位if (page)return page;……page = __alloc_pages_limit(zonelist, order, PAGES_LOW, direct_reclaim);//不断降低水位if (page)return page;……wakeup_kswapd(0);//唤醒内核线程kswapdif (gfp_mask & __GFP_WAIT) { //如果当前分配策略表明对于要求分配的页面时志在必得，分配不到时宁愿等待，就让系统来一次调度。__set_current_state(TASK_RUNNING);current->policy |= SCHED_YIELD;schedule();//让系统来一次调度，这样一来让kswapd有可能立即被调度运行，二来其它进程也有可能会释放出一些页面。}……page = __alloc_pages_limit(zonelist, order, PAGES_MIN, direct_reclaim);//当再次被调度时，或者分配策略表明不允许等待时，就以参数PAGES_MIN再调用一次_alloc_pages_limit()if (page)return page;//如果再失败，这时候就要看是谁在要求分配内存页面了。如果要求分配页面的进程是kswapd或者kreclaimd，本身就是"内存分配工作者"，要求分配内存页面的目的是执行公务，是要更好地分配内存页面，这当前比一般进程重要了，这些进程的task_struct结构中flags字段的PF_MEMALLOC标志位为1。if (!(current->flags & PF_MEMALLOC)) {//对于非kswapd或者kreclaimd的进程……if (order > 0 && (gfp_mask & __GFP_WAIT)) {//分配页面数大于1，且如果分配不到页面，宁愿等待zone = zonelist->zones;/* First, clean some dirty pages. */current->flags |= PF_MEMALLOC;page_launder(gfp_mask, 1);//把不活跃脏的页面变成不活跃干净的页面current->flags &= ~PF_MEMALLOC;for (;;) {zone_t *z = *(zone++);if (!z)break;if (!z->size)continue;while (z->inactive_clean_pages) {struct page * page;/* Move one page to the free list. */page = reclaim_page(z);//把不活跃干净的页面，所有的链表关系都清除，但使用计数仍然为1if (!page)break;__free_page(page);//使用计数减为0，回收这个页面到free_area[MAX_ORDER]，，下次alloc_page就能分配到了/* Try if the allocation succeeds. */page = rmqueue(z, order);if (page)return page;}}}……if ((gfp_mask & (__GFP_WAIT|__GFP_IO)) == (__GFP_WAIT|__GFP_IO)) {wakeup_kswapd(1);memory_pressure++;if (!order)//如果分配的页面数为1，则try_againgoto try_again;……} else if (gfp_mask & __GFP_WAIT) {try_to_free_pages(gfp_mask);memory_pressure++;if (!order)//如果分配的页面数为1，则try_againgoto try_again;}}//如果是"执行公务"，或者虽然不是执行公务，但已想尽了一切方法，采取了一切措施，只不过因为要求分配的是成块的页面才没有转回前面的标号try_again处zone = zonelist->zones;for (;;) {zone_t *z = *(zone++);struct page * page = NULL;if (!z)break;if (!z->size)BUG();……if (direct_reclaim) {//如果要求分配的是一个页面page = reclaim_page(z);if (page)return page;}/* XXX: is pages_min/4 a good amount to reserve for this? */if (z->free_pages < z->pages_min / 4 &&!(current->flags & PF_MEMALLOC))continue;page = rmqueue(z, order);//这次是不惜血本了，只要高于z->pages_min / 4，就试图从管理区分配if (page)return page;}/* No luck.. */printk(KERN_ERR "__alloc_pages: %lu-order allocation failed.\n", order);return NULL;} 调用时有两个参数。第一个参数gfp_mask是一个整数，表示采用哪一种分配策略；第二个参数order表示所需的物理块大小，可以是1、2、4 …、直到2 ^ MAX_ORDER个页面。
你曾经说，最大的愿望，
