RSS Feed

Posts Tagged ‘mm’

  1. 内核的物理页分配器

    January 17, 2013 by xudifsd

    注意,本文主要内容来自《Understanding the Linux Virtual Memory Manager》,基于2.4内核,和最新内核有所不同。并且本人是内核新手,请轻拍。

    伙伴系统的结构和水位

    linux内核使用伙伴系统来分配内存页,分配内存的API是alloc_pages(),但是主函数是__alloc_pages(),这个函数分为三个部分:

    1. 看是否能在不达到zone->pages_low水位的情况下满足分配要求,如能则直接分配。
    2. 否则zone需要balance,唤醒kswapd,并看能否在不达到zone->pages_min水位的情况下满足分配要求,如能则分配。
    3. 否则进入slow path,先看自己是否是即将被OOM killer杀掉的进程,如是则不管水位直接分配,否则自己同步地做kswapd该做的事。

    每个zone都有三个水位线:pages_min,pages_low,pages_high,这三个水位线用于描述系统的内存压力大小的,当zone内空闲页的数目达到pages_low时__alloc_pages()会唤醒kswapd进程,当到了pages_min时__alloc_pages()也会自己干kswapd该干的活,也就是同步的kswapd,直到空闲页数目达到pages_high。

    不过,物理页分配器最难理解的就是伙伴系统的结构和操作过程了。伙伴系统使用下面的结构体的数组描述空闲页:

    typedef struct free_area_struct {
            struct list_head free_list;
            unsigned long *map;
    } free_area_t;

    由于伙伴系统的最基本单位是页,而且只能分配2order页数的连续内存块,所以order就作为结构体数组的索引,结构体中的free_list链接的是连续内存块中的第一个struct page,而map则是表示页是否分配的位图。

    需要注意的是内核用一种比较特殊的方式操作位图:只用1位了表示两个伙伴的状态,即每分配或释放一个伙伴就会对相应的位取反。所以0表示两个伙伴都可用或都不可用,1表示有一个可用。内核使用下面宏来操作位图:

    #define MARK_USED(index, order, area) \
    		__change_bit((index) >> (1 + (order)), (area)->map)

    注意其中的1,就是因为内核使用1位表示两个伙伴的状态,才会有中间的1。其中index是struct page在全局mem_map中的索引,area即是struct free_area_struct。

    分配内存

    考虑一个有16页的系统,如果一开始都是空闲那么free_area数组应该如下图,其中我用page表示结构体中的free_list,page的值就是相应struct page在全局mem_map中的偏移:

    free_area初始状态

    free_area初始状态

    其中order为4的page有个0表示mem_map的0偏移开始的24页都是空闲,其他page为NULL表示没有对应order大小的空闲页,而由于总共才16(24)页,所以order 4没有伙伴,而内核用位图的1位来描述伙伴,所以order为4的map为NULL,而3有一位,以此类推。

    假设现在需要分配order为2的连续内存块,先在free_area[2]中找,由于order为2的page为NULL,即表示没有order 2的连续空间,这样就要往order更高的地方找,3中也没有,只有4中有,这样就要进行分裂,将分裂出来的前一个伙伴放在order为3的page中,而后一个伙伴继续分裂一直到得到想要的order,本例中就是2,所以分配完这次order 2和3都会有一个空闲的块,如下图:

    分配内存块后的free_area状态

    分配内存块后的free_area状态

    现在的物理页应该有最后4页被占用,前面12页仍然空闲,上面的结构页表示正确(order为2的page有8表示从第8~11页为空闲,而12~15页已经被分配)。

    释放内存

    再看看释放的过程,内存块使用者必须记得所使用内存块的order,因为在释放时需要用到,这也是伙伴系统不方便的地方,分配的API是alloc_pages()而释放的API是__free_pages(),它的主要函数是__free_pages_ok(),由其做主要的释放工作:检查刚释放的内存块是否能与相应伙伴合并,这只要通过查看相应的位图是否为1即可完成,如果能合并,那么合并后会往更高的order里添加空闲页,并继续查看是否能此合并,直到MAX_ORDER,这个常数常常是10。本例合并后又变成原来的状态了。

    碎片

    碎片分为两种:

    • 外部碎片是无法满足大的分配要求,因为只存在小的内存块。
    • 内部碎片是对于小的请求也只能分配大的内存块。

    Linux的外部碎片问题并不严重,因为大的请求可以通过vmalloc()分配一个物理地址上不连续但是虚拟地址上连续的内存块。只是伙伴系统的内部碎片问题非常严重,因为伙伴系统的最小单位是页,这个单位对于直接分配结构体太大,所以内核还使用了slab分配器来解决这个问题。