linux内存管理之伙伴系统分析(一)

 

在内核模块的编写中,我们用alloc_page()/alloc_pages()来分配大内存(超过一个页面,即4K).用free_page()/free_pages()来释放用前者分得的内存.今天我们就来分析一下,在linux内核中大内存分配的实现.

跟以往一样.本文的代码分析是基于linux 2.6.9的

本文档包括：

一：准备知识

二：有关的数据结构

三：alloc_pages()/alloc_page 实现分析

四：free_pages()的相关实现

五：总结

一:准备知识:

    一个操作系统的内存管理方式很大程度上决定了它的效率,时间与空间的对立统一在内存管理上体现得最为明显,首先,分配/释放内存是一个发生频率很高的操作,所以它要求有一定的实时性,另外,内存又是一种非常宝贵的资源.所以要尽量减少内存碎片的产生.

     Linux采用了伙伴系统算法来管理内存,即把内页按2^0,2^1,2^2…2^10大小进行分组.每次分配内存时,从相应大小的池中分配内存,然后再把余下的内存分配给它的下一级缓存池.

如下图所示:

 

     关于分配位图:

         在linux中,每一个大小的缓存池都对应一个位图,然后,位图中的每一位对应一对空闲区的空闲标志.每分配一个分配区,都对相应的位图取反.例如:位图管理A,B两个分配块.初始化的时候,该位图置为0.此时,若把A分配出去,更新位图为1.若再把B分配出去,再取反,变为了0.仔细思考,不难发现有以下规律:

若位图为0:表示两个分配块都空或者都已经分配出去.

若位图为1:表示其中有一个已经分配出去,有一个空闲

特别的,关于分配位图,有几点值得注意的地方:

1:位图的大小只跟总内存有关,跟当前缓存池的空闲内存无关.

例如:总内存为4M的系统.总共有4M/4K = 1024个页

那对应的.

2^0位图有1024/1/2 512项

2^1位图有1024/2/2= 256项

……

2^10位图有1024/2^10/2 1项

(除以2是因为1位表示二个页面)

2:为什么一位要管理一对内存呢?其实这是为了更好的管理伙伴系统而设计的,当然,也有减少位图大小的因素

如下图所示

 

 

 

位图1表示A,B的分配情况,位图2表示C,D的分配情.况.A.D已经分配出去了,B,C处于空闲状态

上图中,虽然B,C处理连续的页,且都空闲,但不可以把B,C合位为一块大内存.

 

二:有关的数据结构.

我们以NUMA配置来分析伙伴系统算法中所涉及的数据结构

系统中,每一个页面对应一个页描述符,它的结构如下:

struct page {

         page_flags_t flags;                 //页面所对应的标志,这跟页表项的标志是不一样的

         atomic_t _count;          //页面引用计数

         atomic_t _mapcount;             //有多少个页表项映射到了此页面

         unsigned long private;            //私有数据区,我们在以后将要看到的交换与磁盘高速缓存中会有关于这个成员的使用

         struct address_space *mapping;     //用于磁盘高速缓存,以后分析

         pgoff_t index;                        //同上

         struct list_head lru;                //LRU链表,链至管理区的相应链表中

         #if defined(WANT_PAGE_VIRTUAL)

         void *virtual;                         /* Kernel virtual address (NULL if

                                                  not kmapped, ie. highmem) */

#endif /* WANT_PAGE_VIRTUAL */

}

在linux中,用一个全局的page结构数组mem_map描述了系统中可管理的物理页面项

在上面的成员分析中有一个管理区的概念,我们来看一下何所谓管理区

由于计算机系统的发展原因,老的ISA设备的DMA只能使用前16M的内存..这就是ZONE_DMA

另外,由于内核空间默认配置是1GB.高于1GB的物理地址要通过特殊的方式才能供内核使用.这就是ZONE_HIGHMEM

余下的就是ZONE_NORMAL了.

具体的看一下管理区的结构

struct zone

{

        

          //互斥锁

         spinlock_t           lock;

         //这个区中现有的空闲页面数

         unsigned long                free_pages;

         //pages_min、pages_low及 pages_high是对这个区最少、此少及最多页面个数的描述

         unsigned long                pages_min, pages_low, pages_high;

         //每个类型的管理区的,所保护的页面数

         unsigned long                protection[MAX_NR_ZONES];

 

         ZONE_PADDING(_pad1_)

 

         spinlock_t           lru_lock;    

         struct list_head   active_list;                    //活跃列表

         struct list_head   inactive_list;                 //不活跃列表     

         //内存回收时,所扫描的活跃列表中的页面数

unsigned long                nr_scan_active;

//内存回收时,所扫描的非活跃列表中的页面数

         unsigned long                nr_scan_inactive;

         //活跃链表中的页面个数

         unsigned long                nr_active;

         //非活跃链表中的页面个数

         unsigned long                nr_inactive;

         int                        all_unreclaimable; /* All pages pinned */

         unsigned long                pages_scanned;      /* since last reclaim */

 

         ZONE_PADDING(_pad2_)

        

         //temp_priority与prev_priority 在内存回收算法中使用

         int temp_priority;

         int prev_priority;

 

          //伙伴分配系统中的位图数组和页面链表

         struct free_area   free_area[MAX_ORDER];

 

        

         wait_queue_head_t      * wait_table;

         unsigned long                wait_table_size;

         unsigned long                wait_table_bits;

 

         ZONE_PADDING(_pad3_)

        

         //pcp 结构.我们在后面对此结构进行分析

         struct per_cpu_pageset         pageset[NR_CPUS];

 

        

          //本管理区所在的存储节点

         struct pglist_data         *zone_pgdat;

         //该管理区的内存映射表

         struct page          *zone_mem_map;

         // 起始页面号

         unsigned long                zone_start_pfn;

//管理区中的名字

         char                     *name;

         unsigned long                spanned_pages;   /* total size, including holes */

         unsigned long                present_pages;    /* amount of memory (excluding holes) */

}

在计算机系统中,并不是每一块内存处理的访问时间对于CPU来说都是一样的,例如,靠近CPU的内存插槽的内存访问速度要较快于另外的插槽.CPU缓存的访问速度要大于内存芯片的访问速度.基于这种情况,内核为每个区域都定义了一个结点,认为CPU访问结点所表示的内存消耗的时间是一样的.看一下结点的数据结构:

typedef struct pglist_data {

         struct zone node_zones[MAX_NR_ZONES];                                               //结点中的管理区数组

         struct zonelist node_zonelists[GFP_ZONETYPES];                  //按分配内存的先后顺序排列的管理区

         int nr_zones;                                                                        //该结点总共有多少个管理区

         struct page *node_mem_map;                                             //结点中的页描述符数组

         struct bootmem_data *bdata;                                                        //只用在初始化阶段(boot_mem)

         unsigned long node_start_pfn;                                             //起始物理页号

         unsigned long node_present_pages; /* total number of physical pages */                //总共的物理页面数目

         unsigned long node_spanned_pages; /* total size of physical page                          //物理页面的总大小

                                                    range, including holes */

         int node_id;                                                                                                                //结点的ID

         struct pglist_data *pgdat_next;                                                                                 //下一个结点

         wait_queue_head_t       kswapd_wait;

         struct task_struct *kswapd;                                       //上面这两个成员跟kswap有关,我们在以后分析

}

借用别人的一个图来表示上述三个结构的关系: