linux学习四 内存分配

linux对物理内存的管理是分3个层次，节点，管理区，页面。分配流程如下：

1.首先获得节点列表的头，循环搜索可以分配给用户要求大小的内存。分配成功则跳出循环，不成功则返回0。

2.找到分配节点，根据分配策略和大小找到合适的管理区分配内存。

3.从管理区空闲页面链表内划分合适的内存，分配给用户。

便于理解，对linux分配策略具体实现和部分内存数据结构做下补充：

1.分配策略具体实现：在节点数据结构中

typedef struct pglist_data {
    zone_t    node_zones[MAX_NR_ZONES];   //该节点最多的3个页面管理区，MAX_NR_ZONE值是3，在linux中分为3个管理区，也可能是2个ZONE_DMA,ZONE_NORMAL,ZONE_HIGHMEM
    zonelist_t    node_zonelist[NR_GFPINDEX];   //具体说明见下面的数据结构
    struct page * node_mem_map;   //用于指向属于该存储节点的page数组
    unsigned long * valid_addr_bitmap;
    struct bootmem_data    * bdata;
    unsigned long node_start_paddr;
    unsigned long node_start_mapnr;
    unsigned long node_size;
    int    node_id;
    struct pglistdata * node_next;   //用于形成一个单链队列
}    pg_data_t;

内存分配策略实现由zonelist_t    node_zonelist[NR_GFPINDEX]完成。

typedef struct zonelist_struct {
    zone_t * zones [MAX_NR_ZONES+1]; //指针数组，指向每个具体的页面管理区
    int gfp_mask; //表示分配策略
}    zonelist_t;

比如要实现最小分配（寻找可以分配给用户最小的合适的内存，定义可以查操作系统内存分配策略），把属于该节点的所有管理区按照空闲页面从小到大排列，顺讯遍历这个链表，找到的第一个合适的元素分配，就实现了最小分配。这个数据结构是个指针数组，各种不同的分配策略就形成了各种数组，用户请求内存时候要指定采取的分配策略。

2.管理区空闲队列：

typedef struct free_area_struct {
    struct list_head free_list;   //linux 中通用的双向链队列
    unsigned int * map;
} free_area_t;

typedef struct zone_struct{

    spinlock_t        lock;

    unsigned long offset;  //表示该管理区在mem-map数组中，起始的页号

    unsigned long free pages;
    unsigned long inactive_clean_pages;
    unsigned long inactive_dirty_pages;
    unsigned pages_min, pages_low, pages_high;
   
    struct list_head inactive_clean_list;   //用于页面交换的队列，基于linux页面交换的机制。这里存贮的是不活动“干净”页面
    free_area_t free_area[MAX_ORDER]; 

    char * name;
    unsigned long size;
   
    struct pglist_data * zone_pgdat;   //用于指向它所属的存贮节点，及下面的数据结构
    unsigned  long  zone_start_paddr;
    unsigned  long    zone_start_mapnr;
    struct page * zone_mem_map;

} zone_t;

free_area_t free_area[MAX_ORDER]表示的意义：这个数组0号，表示2的0次方的空闲页面内存。所有空闲页面大小为1，就被双向链表链接，将它们放到free_area[0]。依次类推，free_area[1]表示所有空闲大小是2的1次方的内存，被双向链表链接放在free_area[1]中。

内存分配大致过程，首先找到合适的节点，根据分配策略找到节点中合适分配策略队列，从队列中找到合适的页面管理区，从区里面分配页面
内存分配的起始点mm/numa.c中的

//第一个函数就是逐个去搜索节点，找到节点后进入下一个函数
struct page * _alloc_pages(unsigned int gfp_mask, unsigned int order) //gfp_mask表示分配策略,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) //首先要分配的内存大小不能大于最大分配数，大于的话，直接返回NULL;
        return NULL;
#ifdef CONFIG_NUMA    //表示配置了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); //非numa结构中获取节点链表
#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);
}
//整体看来，就是找到节点链表，找到起始位置，从起始位置向下找，如果分配出内存就退出，没分配就继续。如果起始位置以下都没有，就从链表的起始找，一直找到上次起始处，如果还没找到就return(0);

调用alloc_page_pgdat()来分配内存，这个定义在mm/numa.c中
//根据传递过来的分配策略，进入节点中指定的分配策略数组
static struct page * alloc_pages_pgdat(pg_data_t *pgdat, unsigned int gfp_mask,
    unsigned int order)    //pgdat代表节点(从该节点内分配内存)，gfp_mask表示分配策略,order表示要分配的内存大小，结合上面的调用就可以对上
{
    return __alloc_pages(gfp_mask, order, pgdat->node_zonelists + (gfp_mask & GFP_ZONEMASK)); //调用__alloc_pages分配内存
    //第3个参数，结合上面的数据结构pgdat->node_zonelists + (gfp_mask & GFP_ZONEMASK),指向了gfp_mask指向的分配策略
}

__alloc_pages定义于mm/page_alloc.c中
//进入具体的分配策略数组，去找合适的管理区，来分配内存
struct page * fastcall __alloc_pages(unsigned int gfp_mask, unsigned int order, zonelist_t *zonelist) //各个参数，分配策略，分配策略队列
{
    zone_t **zone, * classzone;
    struct page * page;
    int freed, class_idx;

    zone = zonelist->zones;    //获取该分配策略队列的管理区数据结构指针数组
    classzone = *zone;
    class_idx = zone_idx(classzone);

    for (;;) { //如果rmqueue分配失败就通过该循环降低要求，去寻找该管理区的下一个管理区，如果从该循环出来，表示全部失败
        zone_t *z = *(zone++);
        if (!z)
            break;

        if (zone_free_pages(z, order) > z->watermarks[class_idx].low) { //表示该管理区空闲页面数量大于要求维持的最低页面数量
            page = rmqueue(z, order);    //分配内存
            if (page) //表示分配成功
                return page;    //这里，当分配失败时候没任何动作，而是继续循环去寻找下一个管理区。当我们找到第一个合适的管理区，表示这个管理区是按照指定策略适合的管理区，此时若分配失败，则应该退出。但没有退出这个循环，目的是分配失败时候，放宽要求。继续去寻找下一个管理区，看是否适合。
        }
    }

    classzone->need_balance = 1;
    mb();
    if (waitqueue_active(&kswapd_wait))
        wake_up_interruptible(&kswapd_wait);    //唤醒守护进程kswapd来腾出一些页面，为再次内存分配做准备。下面的代码都是在分配内存失败时候所采取的一些策略来分配给用户内存，其中包括：将干净页面回收，洗干净“脏”页面，回收。合并空闲页面。绝大部分页面分配是不用这么麻烦，他们绝大部分在第一次分配时候就会成功，做这么多工作是保证系统的健壮性

    zone = zonelist->zones;
    for (;;) {  //再腾出一些页面后，再次分配内存。
        unsigned long min;
        zone_t *z = *(zone++);
        if (!z)
            break;

        min = z->watermarks[class_idx].min;
        if (!(gfp_mask & __GFP_WAIT))
            min >>= 2;
        if (zone_free_pages(z, order) > min) {
            page = rmqueue(z, order);
            if (page)
                return page;
        }
    }

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

    if ((current->flags & PF_MEMALLOC) &&
            (!in_interrupt() || (current->flags & 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 */
    if (!(gfp_mask & __GFP_WAIT))
        goto out;

 rebalance:
    page = balance_classzone(classzone, gfp_mask, order, &freed);
    if (page)
        return page;

    zone = zonelist->zones;
    if (likely(freed)) {
        for (;;) {
            zone_t *z = *(zone++);
            if (!z)
                break;

            if (zone_free_pages(z, order) > z->watermarks[class_idx].min) {
                page = rmqueue(z, order);
                if (page)
                    return page;
            }
        }
        goto rebalance;
    } else {
        /*
         * Check that no other task is been killed meanwhile,
         * in such a case we can succeed the allocation.
         */
        for (;;) {
            zone_t *z = *(zone++);
            if (!z)
                break;

            if (zone_free_pages(z, order) > z->watermarks[class_idx].high) {
                page = rmqueue(z, order);
                if (page)
                    return page;
            }
        }
    }

 out:
    printk(KERN_NOTICE "__alloc_pages: %u-order allocation failed (gfp=0x%x/%i)\n",
           order, gfp_mask, !!(current->flags & PF_MEMALLOC));
    if (unlikely(vm_gfp_debug))
        dump_stack();
    return NULL;
}

rmqueue定义于mm/page_alloc.c中
//进入正确的管理区，开始分配内存
static struct page * fastcall 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 = head->next;

        if (curr != head) { //这里补充下关于zone->free_area意义，它是一个数组，数组的每个元素是个双向链表，其中第一个元素是所有2的0次方区间页面链接成的链表。1号表示所有2的1次方区间页面链接成的链表，依次类推。当表头的下一个指针指向自身，则表明该数组中这个元素的双向链表中的内存全部分出去了
            unsigned int index;

            page = list_entry(curr, struct page, list); //从list里面获取page，curr指的是要分配大小
            if (BAD_RANGE(zone,page))
                BUG();
            list_del(curr); //从这个队列里面摘去这个page
            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;
}

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;
        list_add(&(page)->list, &(area)->free_list);
        MARK_USED(index, high, area);
        index += size;
        page += size;
    }
    if (BAD_RANGE(zone,page))
        BUG();
    return page;
}