0. 引言
1. 页表
2. 结构化内存管理
3. 物理内存的管理
4. SLAB分配器
5. 处理器高速缓存和TLB控制
6. 内存管理的概念
7. 内存覆盖与内存交换
8. 内存连续分配管理方式
9. 内存非连续分配管理方式
10. 虚拟内存的概念、特征及其实现
11. 请求分页管理方式实现虚拟内存
12. 页面置换算法
13. 页面分配策略
14. 页面抖动和工作集
15. 缺页异常的处理
16. 堆与内存管理

1. UMA计算机(一致内存访问 uniform memory access)
将可用内存以连续方式组织起来，SMP系统中的每个处理器访问各个内存区都是同样快

2. NUMA计算机(非一致内存访问 non-uniform memory access)
多处理器计算机，系统的各个CPU都有本地内存，可支持高速访问，各个处理器之间通过总线连接起来，以支持对其他CPU的本地内存的访问，但是跨CPU内存访问比本地CPU内存访问要慢
    1) 基于Alpha的WildFire服务器
    2) IMB的NUMA-Q计算机

1. 页表中不同数目的间接层(向上透明的多级页表)
2. NUMA和UMA系统的划分

1. 首先，内存划分为"结点"，每个结点关联到系统中的一个处理器，在内核中表示为pg_data_t的实例，各个内存节点保存在一个单链表中，供内核遍历
2. 各个结点又划分为"内存域"，是内存的进一步划分，各个内存域都关联了一个数组，用来组织属于该内存域的物理内存页(页帧)，对每个页帧，都分配一个struct page实例以及所需的管理数据
    1) CONFIG_ZONE_DMA

    2) ZONE_DMA: 
    ZONE_DMA is used when there are devices that are not able to do DMA to all of addressable memory (ZONE_NORMAL). Then we carve out the portion of memory that is needed for these devices. The range is arch specific.
        2.1) parisc、ia64、sparc: <4G
        2.2) s390: <2G
        2.3) arm: Various
        2.4) alpha: Unlimited or 0-16MB.
        2.5) i386、x86_64、multiple other arches: <16M.
    ZONE_DMA标记适合DMA的内存域，该区域的长度依赖于处理器类型，在IA-32计算机上，一般的限制是16MB，这是古老的ISA设备强加的边界，但更现代的计算机也可能受这个限制的影响

    3) CONFIG_ZONE_DMA32

    4) ZONE_DMA32: 
    x86_64 needs two ZONE_DMAs because it supports devices that are only able to do DMA to the lower 16M but also 32 bit devices that can only do DMA areas below 4G.
    ZONE_DMA32标记了使用32位地址字可寻址、适合DMA的内存域。显然，只有在64位系统上两种DMA内存域上才有差别，在32位计算机上，这个内存域是空的，即长度为0MB，在Alpha和AMD64系统上，该内存域的长度可能从0到4GB

    5) ZONE_NORMAL
    Normal addressable memory is in ZONE_NORMAL. DMA operations can be performed on pages in ZONE_NORMAL if the DMA devices support transfers to all addressable memory.
    ZONE_NORMAL标记了可直接映射到内核段的普通内存域，这是在所有体系结构上保证都会存在的唯一内存域，但无法保证该地址范围对应了实际的物理内存，例如
        1. 如果AMD64系统有2GB内存，那么所有内存都属于ZONE_DMA32，而ZONE_NORMAL则为空

    6) CONFIG_HIGHMEM

    7) ZONE_HIGHMEM
    A memory area that is only addressable by the kernel through mapping portions into its own address space. This is for example used by i386 to allow the kernel to address the memory beyond 900MB.  The kernel will set up special mappings (page table entries on i386) for each page that the kernel needs to access.
    ZONE_HIGHMEM标记了超出内核段的物理内存

    8) ZONE_MOVABLE
    9) __MAX_NR_ZONES
    1) 对可用于(ISA设备的)DMA操作的内存区是有限制的，只有前16MB可用
    2) 通用的"普通"内存区
    3) 高端内存区域无法直接映射

enum zone_type 
{
#ifdef CONFIG_ZONE_DMA
    /*
     * ZONE_DMA is used when there are devices that are not able to do DMA to all of addressable memory (ZONE_NORMAL). Then we carve out the portion of memory that is needed for these devices.
     * The range is arch specific.
     *
     * Some examples
     *
     * Architecture        Limit
     * ---------------------------
     * parisc, ia64, sparc    <4G
     * s390            <2G
     * arm            Various
     * alpha        Unlimited or 0-16MB.
     *
     * i386, x86_64 and multiple other arches <16M.

     ZONE_DMA标记适合DMA的内存域，该区域的长度依赖于处理器类型，在IA-32计算机上，一般的限制是16MB，这是古老的ISA设备强加的边界，但更现代的计算机也可能受这个限制的影响
     */
    ZONE_DMA,
#endif
#ifdef CONFIG_ZONE_DMA32
    /*
     * x86_64 needs two ZONE_DMAs because it supports devices that are only able to do DMA to the lower 16M but also 32 bit devices that can only do DMA areas below 4G.

     ZONE_DMA32标记了使用32位地址字可寻址、适合DMA的内存域。显然，只有在64位系统上两种DMA内存域上才有差别，在32位计算机上，这个内存域是空的，即长度为0MB，在Alpha和AMD64系统上，该内存域的长度可能从0到4GB
     */
    ZONE_DMA32,
#endif
    /*
     * Normal addressable memory is in ZONE_NORMAL. DMA operations can be performed on pages in ZONE_NORMAL if the DMA devices support transfers to all addressable memory.

     ZONE_NORMAL标记了可直接映射到内核段的普通内存域，这是在所有体系结构上保证都会存在的唯一内存域，但无法保证该地址范围对应了实际的物理内存，例如
     1. 如果AMD64系统有2GB内存，那么所有内存都属于ZONE_DMA32，而ZONE_NORMAL则为空
     */
    ZONE_NORMAL,
#ifdef CONFIG_HIGHMEM
    /*
     * A memory area that is only addressable by the kernel through mapping portions into its own address space. 
     * This is for example used by i386 to allow the kernel to address the memory beyond 900MB. 
     * The kernel will set up special mappings (page table entries on i386) for each page that the kernel needs to access.

     ZONE_HIGHMEM标记了超出内核段的物理内存
     */
    ZONE_HIGHMEM,
#endif
    //内核定义了一个伪内存域ZONE_MOVABLE，在防止物理内存碎片的机制中需要使用该内存域
    ZONE_MOVABLE,
    //__MAX_NR_ZONES充当结束标记，在内核想要迭代系统中的所有内存区域时，会用到该常量
    __MAX_NR_ZONES
};

1. 在64位系统中，并不需要高端内存域
2. 如果支持了只能访问4GB以下内存的32位外设外，才需要DMA32内存域

http://www.cnblogs.com/LittleHann/p/3865490.html
//搜索：0x3: struct pg_data_t

/*
 * Bitmasks that are kept for all the nodes.
 */
enum node_states 
{
    /* 
    The node could become online at some point 
    结点在某个时刻可能变为联机
    */
    N_POSSIBLE,        

    /* 
    The node is online 
    结点是联机的
    */
    N_ONLINE,        

    /* 
    The node has regular memory 
    结点有普通内存域
    */
    N_NORMAL_MEMORY,    
#ifdef CONFIG_HIGHMEM
    /* 
    The node has regular or high memory 
    结点有普通、或高端内存域

    如果结点有普通或高端内存则使用N_HIGH_MEMORY，否则使用N_NORMAL_MEMORY
    */
    N_HIGH_MEMORY,        
#else
    N_HIGH_MEMORY = N_NORMAL_MEMORY,
#endif
    /* 
    The node has one or more cpus 
    结点有一个、或多个CPU
    */
    N_CPU,        
    NR_NODE_STATES
};

static inline void node_set_state(int node, enum node_states state)
{
    __node_set(node, &node_states[state]);
}
static inline void node_clear_state(int node, enum node_states state)
{
    __node_clear(node, &node_states[state]);
}

//宏for_each_node_state用来迭代处于特定状态的所有结
#define for_each_node_state(__node, __state) \
    for_each_node_mask((__node), node_states[__state])

http://www.cnblogs.com/LittleHann/p/3865490.html
//搜索：0x4: struct zone

尽管内存域可能属于一个特定的NUMA结点，因而关联到某个特定的CPU，但其他CPU的高速缓存仍然可以包含该内存域中的页。实际上，每个处理器都可以访问系统中所有的页，尽管速度不同。因此，特定于内存域的数据结构不仅要考虑到所属NUMA结点相关的CPU，还必须考虑到系统中其他的CPU

struct zone
{
    ..
    struct per_cpu_pageset    pageset[NR_CPUS];
    ..
}
//NR_CPUS是一个可以在编译时配置的宏常数，在单处理器系统上其值总是1，针对SMP系统编译的内核中，其值可能在2~32/64(在64位系统上是64)之间

struct per_cpu_pageset 
{
    /*
    pcp[0]: 热页
    pcp[1]: 冷夜
    */
    struct per_cpu_pages pcp;
#ifdef CONFIG_NUMA
    s8 expire;
#endif
#ifdef CONFIG_SMP
    s8 stat_threshold;
    s8 vm_stat_diff[NR_VM_ZONE_STAT_ITEMS];
#endif
} ____cacheline_aligned_in_smp;


struct per_cpu_pages 
{
    /* 
    number of pages in the list 
    列表中页数，count记录与该列表相关的页的数目
    */
    int count;        

    /* 
    high watermark, emptying needed 
    页数上限水印，在需要的情况下清空列表，如果count的值超过了high，则表明列表中的页太多了，对容量过低的状态没有显式使用水印，如果列表中没有成员，则重新填充
    */
    int high;    

    /* 
    chunk size for buddy add/remove 
    如果可能，CPU的高速缓存不是用单个页来填充的，而是用多个页组成的块，batch添加/删除多页块的时候，块的大小(即页数)的参考值
    */    
    int batch;        

    /* 
    Lists of pages, one per migrate type stored on the pcp-lists 页的链表
    lists是一个双链表，保存了当前CPU的冷页或热页，可使用内核的标准方法处理
    */
    struct list_head lists[MIGRATE_PCPTYPES];
};

http://www.cnblogs.com/LittleHann/p/3865490.html
//搜索：0x5: struct page

https://www.google.com.hk/url?sa=t&rct=j&q=&esrc=s&source=web&cd=27&ved=0CDwQFjAGOBQ&url=%68%74%74%70%3a%2f%2f%6f%61%2e%70%61%70%65%72%2e%65%64%75%2e%63%6e%2f%66%69%6c%65%2e%6a%73%70%3f%75%72%6c%74%69%74%6c%65%3d%25%45%36%25%39%36%25%38%37%25%45%34%25%42%42%25%42%36%43%61%63%68%65%25%45%38%25%38%37%25%41%41%25%45%39%25%38%30%25%38%32%25%45%35%25%42%41%25%39%34%25%45%37%25%41%44%25%39%36%25%45%37%25%39%35%25%41%35%25%45%37%25%41%30%25%39%34%25%45%37%25%41%39%25%42%36&ei=veo1VN_RJZfj8AWBnoCACQ&usg=AFQjCNHVjRFlRvV-0O1tYyb4Inv33Pop4A&bvm=bv.76943099,d.dGc&cad=rjt
http://www.cnblogs.com/hanyan225/archive/2011/07/28/2119628.html

1. 页表用于建立用户进程的虚拟地址空间和系统物理内存(页帧)之间的关联
2. 页表用于向每个进程提供一致的虚拟地址空间，应用程序看到的地址空间是一个连续的内存区
3. 页表也将虚拟内存页映射到物理内存，因而支持共享内存的实现(同一个物理页同时映射到不同进程的虚拟地址空间)
4. 层次化的页表用于支持对大地址空间的快速、高效的管理
5. 可以在不额外增加物理内存的情况下，将页换出到块设备来增加有效的可用内存空间，即将进程中某些不常用的虚拟内存进行"解关联"，将对应的页表映射删除，从而释放出这部分物理内存，让其他进程可以用于映射

1. 第一部分依赖于体系结构: 所有数据结构和操作数据结构的函数都是定义在特定于体系结构的文件中
2. 第二部分是体系结构无关的
//需要注意的一点是，在Linux内核中，内存管理和体系结构的关联很密切

1. PGD
2. PUD: PGDIR_SHIFT由PUD_SHIFT加上上层页表索引所需的比特位长度，对全局页目录中的一项所能寻址的的部分地址空间长度: 2(PGDIR_SHIFT)次方
3. PMD: PUD_SHIFT由PMD_SHIFT加上中间层页表索引所需的比特位长度
4. PTE: PMD_SHIFT指定了业内偏移量和最后一项页表项所需比特位的总数，该值减去PAGE_SHIFT，可得最后一项页表项索引所需比特位的数目。同时PMD_SHIFT表明了一个中间层页表项管理的部分地址空间的大小: 2(PMD_SHIFT)次方字节
5. Offset: 每个指针末端的几个比特位，用于指定所选页帧内部的位置，比特位的具体数目由PAGE_SHIFT指定(通过位移+掩码的形式来进行分段)

1. PTRS_PER_PGD: 指定了全局页目录中项的数目
2. PTRS_PER_PUD: 对应于上层页目录中项的数目
3. PTRS_PER_PMD: 对应于中间页目录
4. PTRS_PER_PTE: 页表中项的数目
/*
我们知道，Linux的四级页表实现是向下兼容的，即在两级页表的体系结构中，会将PTRS_PER_PMD、PTRS_PER_PTE定义为1，这使得内核的剩余部分感觉该体系结构也提供了四级页表转换结构
*/

/*
These are used to make use of C type-checking..
*/
1. pgd_t: 全局页目录项
typedef struct 
{
    unsigned long pgd;
} pgd_t;

3 pmd_t: 中间页目录项
typedef struct 
{
    unsigned long pmd[16];
} pmd_t;

4. pte_t: 直接页表项
typedef struct
{
    unsigned long pte;
} pte_t;

pgprot_t:
typedef struct 
{
    unsigned long pgprot;
} pgprot_t;
typedef struct page *pgtable_t;

...
#define pgd_val(x)    ((x).pgd)    //将pte_t等类型的变量转换为unsigned long    
#define pmd_val(x)    ((&x)->pmd[0])
#define pte_val(x)    ((x).pte)
#define pgprot_val(x)    ((x).pgprot)

#define __pgd(x)    ((pgd_t) { (x) } )    //pgd_val等函数的逆，将unsigned long整数转换为pgd_t等类型的变量
#define __pmd(x)    ((pmd_t) { (x) } )
#define __pte(x)    ((pte_t) { (x) } )
#define __pgprot(x)    ((pgprot_t) { (x) } )
...

从某种程度上来说，四级页表的索引是体现(基于)对内存地址的分段索引之上的，即将一个内存地址切成几段，每一段分别代表不同层次的索引信息

1. _PAGE_PRESENT
指定了虚拟内存页是否存在于内存中，因为页可能被换出到交换区
    1) 如果页不在内存中，那么页表项的结构通常会有所不同，因为不需要描述页在内存中的位置
    2) 如果页存在于内存中，就需要信息来标识并找到换出的页

2. _PAGE_ACCESSED
CPU每次访问页时，会自动设置_PAGE_ACCESSED，内核会定期检查该比特位，以确认页使用的活跃程序(不经常使用的页，比较适合换出)。在读或写访问之后会设置该比特位

3. _PAGE_DIRTY
表示该页是否是"脏的"，即页的内容是否已经被修改过

4. _PAGE_FILE
数值和_PAGE_DIRTY相同，但用于不同的上下文，即页不在内存中的时候，显然不存在的页不可能是脏的(因为它不可能被进程修改)，因此可以重新解释该比特位
    1) 如果没有设置，则该项指向一个换出页的位置
    2) 如果该项属于非线性文件映射，则需要设置_PAGE_FILE

5. _PAGE_USER
如果设置了_PAGE_USER，则允许用户空间代码访问该页，否则只有内核才能访问(或CPU处于系统状态的时候)

6. _PAGE_READ、_PAGE_WRITE、_PAGE_EXECUTE
指定了普通的用户进程是否允许读取、写入、执行该页中的机器代码
//内核内存中的页必须防止用户进程写入，对于访问权限粒度不是非常细的体系结构而言，如果没有进一步的准则可以区分读写访问权限，则会定义_PAGE_RW常数，用于同时允许或禁止读写访问

7. _PAGE_BIT_NX
IA-32、AMD64提供了_PAGE_BIT_NX，用于将页标记为"不可执行"的(在IA-32系统上，只有启用了"可寻址64GB内存的页面地址扩展(page address extension PAE)"时，才能使用该保护位)。它可以有效防止执行栈页上的代码，否则，恶意代码可能通过缓冲区溢出手段在栈上执行代码，导致程序的安全漏洞

8. __pgprot、pte_modidy()
每个体系结构都必须提供两个东西，使得内存管理子系统能够修改pte_t项中额外的比特位
    1) 保存额外的比特位的__pgprot数据结构
    2) 以及修改这些比特位的pte_modidy()函数

1. pte_present: 检查页表项指向的页是否存在于内存中，该函数可以用于检测一页是否已经换出
2. pte_read: 从用户空间是否可以读取该页
3. pte_write: 检查内核是否可以写入到该页
4. pte_exec: 检查该页中的数据是否可以作为二进制代码执行
5. pte_dirty: 检查与页表项相关的页是否是脏的，即其内容在上次内核检查之后是否以已经修改过，需要注意的是，只有在pte_present确认了该页可用的情况下(即存在于内存中)，才能调用该函数
6. pte_file: 用于非线性映射，通过操作页表提供了文件内容的一种不同视图，该函数检查页表项是否属于这样的一个映射，要注意的是，只有在pte_present返回false时，才能调用pte_file，即与该页表项相关的页不再内存中
7. pte_young: 访问位(通常是_PAGE_ACCESSED)是否设置
8. pte_rdprotect: 清除该页的读权限
9. pte_wrprotect: 清除该页的写权限 
10. pte_exprotect: 清除执行该页中的二进制数据的权限
11. pte_mkread: 设置读权限
12. pte_mkwrite: 设置写权限
13. pte_mkexec: 允许执行页的内容
14. pte_mkdirty: 将页标记为脏
15. pte_mkclean: "清除"页，通常指清除_PAGE_DIRTY位
16. pte_mkyoung: 设置访问位，在大多数体系结构上是_PAGE_ACCESSED
17. pte_mkold: 清除访问位
//这些函数经常分为3组，分别用于设置、删除、查询某个特定的属性

1. mk_pte
#define mk_pte(page, pgprot)   pfn_pte(page_to_pfn(page), (pgprot))
创建一个页表项，必须将page实例和所需的页访问权限(__pgprot)作为参数传递
2. pte_page
#define pte_page(pte)    pfn_to_page(pte_pfn(pte))
获得页表项描述的页对应的page实例地址
3. pte_alloc
4. pte_free
5. set_pte

6. pgd_alloc
\linux-2.6.32.63\arch\x86\mm\pgtable.c
分配并初始化一个可容纳完整页表的内存
7. pgd_free: 释放页表占据的内存
8. set_pgd: 设置页表中某项的值

9. pud_alloc
10. pud_free
11. set_pud

12. pmd_alloc
13. pmd_free
14. set_pmd

linux-2.6.32.63\arch\x86\include\asm\mmzone_64.h
#define NODE_DATA(nid)        (node_data[nid])

\linux-2.6.32.63\arch\m32r\mm\discontig.c
struct pglist_data *node_data[MAX_NUMNODES];
EXPORT_SYMBOL(node_data);

1. setup_arch
特定于体系结构的设置函数，其中一项任务是负责初始化自举分配器

2. setup_per_cpu_areas
    1) 在SMP系统上，setup_per_cpu_areas初始化源代码中定义的静态per-cpu变量，这种变量对系统中的每个CPU都有一个独立的副本(这类变量保存在内核二进制映像的一个独立的段中)，setup_per_cpu_areas的目的是为系统的各个CPU分别创建一份这些数据的副本
    2) 在非SMP系统上，该函数是一个空操作

3. build_all_zonelists
建立"结点"和"内存域"的数据结构

4. mem_init
另一个特定于体系结构的函数，用于停用bootmem分配器并迁移到实际的内存管理函数

5. setup_per_cpu_pageset
为"strcut zone->struct per_cpu_pageset pageset[NR_CPUS]"数组的第一个数组元素分配内存。分配第一个数组元素，即意味着为第一个系统处理器分配，系统的所有内存域都会考虑进来
该函数还负责设置冷热分配器的限制
//SMP系统上对应于其他CPU的pageset数组成员，将会在相应的CPU激活时初始化

#ifdef CONFIG_WORK_HARD
void do_work()
{
    //start
}
#else
void do_work()
{
    //stop
}
#endif

void build_all_zonelists(void)
{
    /*
    在当前处理的结点和系统中其他结点的内存域之间建立一种等级次序，接下来，依据这种次序分配内存
    考虑下面的例子
    内核想要分配高端内存，它首先试图在当前结点的高端内存域找到一个大小适当的空闲段，如果失败，则查看该节点的普通域，如果还失败，则试图在该结点的DMA内存域执行分配
    如果在3个本地内存域都无法找到空闲内存，则查看其他结点，在这种情况下，备选结点应该尽可能靠近主结点，以最小化由于访问非本地内存引起的性能损失

    内核将内存域分为层次结构，首先试图分配"廉价的"内存，如果失败，则根据访问速度和容量，逐渐尝试分配"更昂贵的"内存
    1. 高端内存是最"廉价的"，因为内核没有部分依赖于从该内存域分配的内存，如果高端内存域用尽，对内核没有任何副作用，这也是优先分配高端内存的原因
    2. 普通内存域的情况有所不同，许多内核数据结构必须保存在该内存域，而不能放置到高端内存域。因此如果普通内存完全用尽，那么内核会面临紧急情况，所以只要高端内存域的内存域没有用尽，都不会从普通内存域分配内存
    3. 最昂贵的是DMA内存域，因为它用于外设和系统之间的数据传输，因此从该内存域分配内存是最后一招(一般情况下不会从DMA中分配内存)
    */
    set_zonelist_order();

    if (system_state == SYSTEM_BOOTING) 
    {
        __build_all_zonelists(NULL);
        mminit_verify_zonelist();
        cpuset_init_current_mems_allowed();
    } 
    else 
    {
        /* we have to stop all cpus to guarantee there is no user of zonelist */
        stop_machine(__build_all_zonelists, NULL, NULL);
        /* cpuset refresh routine should be here */
    }
    vm_total_pages = nr_free_pagecache_pages();
    /*
     * Disable grouping by mobility if the number of pages in the
     * system is too low to allow the mechanism to work. It would be
     * more accurate, but expensive to check per-zone. This check is
     * made on memory-hotadd so a system can start with mobility
     * disabled and enable it later
     */
    if (vm_total_pages < (pageblock_nr_pages * MIGRATE_TYPES))
        page_group_by_mobility_disabled = 1;
    else
        page_group_by_mobility_disabled = 0;

    printk("Built %i zonelists in %s order, mobility grouping %s.  "
        "Total pages: %ld\n",
            nr_online_nodes,
            zonelist_order_name[current_zonelist_order],
            page_group_by_mobility_disabled ? "off" : "on",
            vm_total_pages);
#ifdef CONFIG_NUMA
    printk("Policy zone: %s\n", zone_names[policy_zone]);
#endif
}
//将所有工作都委托给__build_all_zonelists

/* non-NUMA variant of zonelist performance cache - just NULL zlcache_ptr */
static void build_zonelist_cache(pg_data_t *pgdat)
{
    pgdat->node_zonelists[0].zlcache_ptr = NULL;
}

#endif    /* CONFIG_NUMA */

/* return values int ....just for stop_machine() */
static int __build_all_zonelists(void *dummy)
{
    int nid;

#ifdef CONFIG_NUMA
    memset(node_load, 0, sizeof(node_load));
#endif
    //对系统中的各个NUMA结点分别调用build_zonelists
    for_each_online_node(nid) 
    {
　　　　　//pg_data_t *pgdat包含了结点内存配置的所有现存信息，且新建的数据机构也会放置在其中
        pg_data_t *pgdat = NODE_DATA(nid);

        build_zonelists(pgdat);
        build_zonelist_cache(pgdat);
    }
    return 0;
}

static void build_zonelists(pg_data_t *pgdat)
{
    int node, local_node;
    enum zone_type j;
    struct zonelist *zonelist;

    local_node = pgdat->node_id;

    zonelist = &pgdat->node_zonelists[0];
    j = build_zonelists_node(pgdat, zonelist, 0, MAX_NR_ZONES - 1);

    /*
     * Now we build the zonelist so that it contains the zones
     * of all the other nodes.
     * We don't want to pressure a particular node, so when
     * building the zones for node N, we make sure that the
     * zones coming right after the local ones are those from
     * node N+1 (modulo N)
     */
    //迭代所有的结点内存域，每个循环在node_zonelist数组中找到第i个zonelist，对第i个内存域计算备用列表
    for (node = local_node + 1; node < MAX_NUMNODES; node++) 
    {
        if (!node_online(node))
            continue;
        //实际工作委托给build_zonelists_node
        j = build_zonelists_node(NODE_DATA(node), zonelist, j, MAX_NR_ZONES - 1);
    }
    for (node = 0; node < local_node; node++) 
    {
        if (!node_online(node))
            continue;
        j = build_zonelists_node(NODE_DATA(node), zonelist, j, MAX_NR_ZONES - 1);
    }

    zonelist->_zonerefs[j].zone = NULL;
    zonelist->_zonerefs[j].zone_idx = 0;
}

/*
 * Builds allocation fallback zone lists.
 *
 * Add all populated zones of a node to the zonelist.
 */
/*
备用列表的各项是根据zone_type参数排序的，该参数指定了最优选择哪个内存域，该参数的初始值是外层循环的控制变量i，我们知道其值可能是
1. ZONE_HIGHMEM
2. ZONE_NORMAL
3. ZONE_DMA / ZONE_DMA32

nr_zones表示从备用列表中的哪个位置开始填充新项，由于列表中尚没有项，因此调用者传递了0
*/
static int build_zonelists_node(pg_data_t *pgdat, struct zonelist *zonelist, int nr_zones, enum zone_type zone_type)
{
    struct zone *zone;

    BUG_ON(zone_type >= MAX_NR_ZONES);
    zone_type++;

    do 
    {
        //在每一步结束时，都将内存域类型减一，即设置为一个更"昂贵"的内存域类型(例如从ZONE_HIGHMEM -> ZONE_NORMAL -> ZONE_DMA)
        zone_type--;
        zone = pgdat->node_zones + zone_type;
        if (populated_zone(zone)) 
        {
            zoneref_set_zone(zone,
                &zonelist->_zonerefs[nr_zones++]);
            check_highest_zone(zone_type);
        }

    } while (zone_type);
    return nr_zones;
}

1. 将处理器从普通模式切换到保护模式
2. 授予CPU访问32位地址空间的权限
3. 兼容16位8086处理器
4. 分页在默认情况下没有启用，必须手动激活，这涉及处理器的CR0寄存器

1. 0 ~ 0x1000(4KB): 第一个页帧，一般会忽略，以为通常保留给BIOS使用
2. 0x1000 ~ 0x9c80(640KB): 原则上是可用的，但也不用于内核加载，原因是该区域之后紧邻的区域由系统保留，用于映射各种ROM(通常是系统BIOS和显卡ROM)，不可能向映射ROM的区域写入数据。但内核总是会装载到一个连续的内存区中，如果要从4KB处作为起始位置来装载内核映像，则要求内核必须小于640KB
3. 0x9c80 ~ 0x100000: 可用内存区域
4. 0x100000 ~ end: 为了解决内核加载的问题，IA-32内核使用0x100000作为起始地址，从此处开始，有足够的连续内存区，可容纳整个内核，内核占据的内存分为几个段，其边界保存在变量中
    1) _text ~ _etext: 内核代码段的起始和结束地址，包含了编译后的内核代码
    2) _etext ~ _edata: 数据段，保存了大部分内核变量
    3) _edata ~ _end: 初始化数据在内核启动过程结束后不再需要(例如，包含初始化为0的所有静态全局变量的BSS段)，保存在最后一段，在内核初始化完成后，其中的大部分数据都可以从内存删除，给应用程序留出更多空间
//准确的数值依内核配置而异，因为每种配置的代码段和数据段长度都不相同，这取决于启动和禁用了内核的哪些部分，只有起始地址(_text)是相同的

1. 全局变量
2. 内核定义的导出函数
3. 例程函数地址
4. 内存分段常数的值
    1) _text
    2) _etext
    3) _edata
    4) _end
// /proc/iomem也提供了有关物理内存划分的各个段的一些信息

1. machine_specific_memory_setup
创建一个列表，包括系统占据的内存区和空闲内存区，BIOS提供的映射给出了在这种情况下使用的各个内存区，在系统启动时，找到的内存区由内核函数print_memory_map显示
dmesg
BIOS-provided physical RAM map:
 BIOS-e820: 0000000000000000 - 000000000009ec00 (usable)
 BIOS-e820: 000000000009ec00 - 00000000000a0000 (reserved)
 BIOS-e820: 00000000000dc000 - 0000000000100000 (reserved)
 BIOS-e820: 0000000000100000 - 000000007fee0000 (usable)
 BIOS-e820: 000000007fee0000 - 000000007feff000 (ACPI data)
 BIOS-e820: 000000007feff000 - 000000007ff00000 (ACPI NVS)
 BIOS-e820: 000000007ff00000 - 0000000080000000 (usable)
 BIOS-e820: 00000000f0000000 - 00000000f8000000 (reserved)
 BIOS-e820: 00000000fec00000 - 00000000fec10000 (reserved)
 BIOS-e820: 00000000fee00000 - 00000000fee01000 (reserved)
 BIOS-e820: 00000000fffe0000 - 0000000100000000 (reserved)

 2. parse_cmdline_early
 分析命令行，从本质上来讲，内核也是一个进程，需要被链接进系统中，载入内核映像的时候也有参数传入，例如
    1) mem=XXX[KkmM]
    2) highmem=XXX[KkmM]
    3) memmap=XXX[KkmM]
如果内核计算的值或BIOS提供的值不正确，管理员可以修改可用内存的数量或手工划定内存区

3. setup_memory
    1) 确定(每个结点)可用的物理内存页的数目
    2) 初始化bootmem分配器
    3) 分配各种内存区，例如运行第一个用户空间过程所需的最初的RAM磁盘

4. paging_init
初始化内核页表并启用内存分页，因为IA-32计算机上默认情况下分页是禁用的，如果内核编译了PAE支持，而且处理器也支持Execute Disabled Protection，则启用该特性
    1) pagetable_init: 该函数确保了直接映射到内核地址空间的物理内存被初始化，低端内存中的所有页帧都直接映射到PAGE_OFFSET之上的虚拟内存区，这使得内核无需处理页表，即可寻址相当一部分可用内存

5. zone_sizes_init
初始化系统中所有结点pgdat_t实例
    1) add_active_range: 对可用的物理内存建立一个相对简单的列表
    2) free_area_init_nodes: 这是体系结构无关的函数，建立完备的内核数据结构

/*
paging_init() sets up the page tables - note that the first 8MB are already mapped by head.S.
This routines also unmaps the page at virtual kernel address 0, so that we can trap those pesky NULL-reference errors in the kernel.
*/
void __init paging_init(void)
{
    //初始化系统的页表
    pagetable_init();

    //在pagetable_init完成页表初始化之后，则将CR3寄存器设置为指向全局页目录(swapper_pg_dir)的指针，此时必须激活新的页表

    //由于TLB缓存项仍然包含了启动时分配的一些内存地址数据，此时也必须刷出，与上下文切换期间相反，设置了_PAGE_GLOBAL位的页也要刷出
    __flush_tlb_all();

    //kmap_init初始化全局变量kmap_pte，在从高端内存内存域将页映射到内核地址空间时，会使用该变量存入相应内存区的页表项，此外，用于高端内存内核映射的第一个固定映射内存区的地址保存在全局变量kmem_vstart中
    kmap_init();

    /*
     * NOTE: at this point the bootmem allocator is fully available.
     */
    sparse_init();
    zone_sizes_init();
}

static void __init pagetable_init(void)
{
    //以swapper_pg_dir为基础初始化系统的页表
    pgd_t *pgd_base = swapper_pg_dir;

    //建立固定映射和持久内核，用适当的值填充页表
    permanent_kmaps_init(pgd_base);
}

static __meminit void zone_pcp_init(struct zone *zone)
{
    int cpu;
    //用zone_batchsize算出批量大小(用于计算最小和最大填充水平的基础)后，代码将遍历系统中的所有CPU
    unsigned long batch = zone_batchsize(zone);

    for (cpu = 0; cpu < NR_CPUS; cpu++) {
#ifdef CONFIG_NUMA
        /* Early boot. Slab allocator not functional yet */
        zone_pcp(zone, cpu) = &boot_pageset[cpu];
        setup_pageset(&boot_pageset[cpu],0);
#else
        //调用setup_pageset填充每个per_cpu_pageset实例的常量，使用了zone_pcp宏来选择与当前CPU相关的内存域的pageset实例
        setup_pageset(zone_pcp(zone,cpu), batch);
#endif
    }
    if (zone->present_pages)
        printk(KERN_DEBUG "  %s zone: %lu pages, LIFO batch:%lu\n",
            zone->name, zone->present_pages, batch);
}

static int zone_batchsize(struct zone *zone)
{
#ifdef CONFIG_MMU
    int batch;

    /*
     * The per-cpu-pages pools are set to around 1000th of the
     * size of the zone.  But no more than 1/2 of a meg.
     *
     * OK, so we don't know how big the cache is.  So guess.
     */
    batch = zone->present_pages / 1024;
    if (batch * PAGE_SIZE > 512 * 1024)
        batch = (512 * 1024) / PAGE_SIZE;
    batch /= 4;        /* We effectively *= 4 below */
    if (batch < 1)
        batch = 1;

    /*
     * Clamp the batch to a 2^n - 1 value. Having a power
     * of 2 value was found to be more likely to have
     * suboptimal cache aliasing properties in some cases.
     *
     * For example if 2 tasks are alternately allocating
     * batches of pages, one task can end up with a lot
     * of pages of one half of the possible page colors
     * and the other with pages of the other colors.
     */
    batch = rounddown_pow_of_two(batch + batch/2) - 1;

    return batch;

#else
    /* The deferral and batching of frees should be suppressed under NOMMU
     * conditions.
     *
     * The problem is that NOMMU needs to be able to allocate large chunks
     * of contiguous memory as there's no hardware page translation to
     * assemble apparent contiguous memory from discontiguous pages.
     *
     * Queueing large contiguous runs of pages for batching, however,
     * causes the pages to actually be freed in smaller chunks.  As there
     * can be a significant delay between the individual batches being
     * recycled, this leads to the once large chunks of space being
     * fragmented and becoming unavailable for high-order allocations.
     */
    return 0;
#endif
}

dmesg | grep LIFO
    DMA zone: 56 pages used for memmap
    DMA zone: 101 pages reserved
    DMA zone: 3825 pages, LIFO batch:0
    DMA32 zone: 7112 pages used for memmap
    DMA32 zone: 513048 pages, LIFO batch:31

1. bootmem使用一个"位图(bitmap)"来管理页，位图比特位的数目与系统中物理内存页的数目相同
    1) 比特位为1: 表示已经使用该页
    2) 比特位为0: 表示空闲页
2. 在需要分配内存时，分配器逐位扫描位图，直至找到一个能够提供足够"连续页"的位置，即所谓的最先最佳(first-best)或最先适配位置
/*
该过程不是很高效(原因在于每次都需要遍历操作)，因为每次分配都必须从头扫描比特链，因此在内核完全初始化之后，不能将该分配器用于内存管理。伙伴系统(连同slab、slub、slob分配器)是一个更好的技术方案
*/

/*
node_bootmem_map is a map pointer - the bits represent all physical  memory pages (including holes) on the node.
*/
typedef struct bootmem_data 
{
    //node_min_pfn保存了系统中第一个页的编号，大多数体系结构下都是零
    unsigned long node_min_pfn;
    
    //node_low_pfn是可以直接管理的物理地址空间中最后一页的编号(即ZONE_NORMAL的结束页)
    unsigned long node_low_pfn;

    //node_bootmem_map是指向存储分配位图的指针，在IA-32系统上，该内存区(位图)紧接在内核映像之后，对应的地址保存在_end变量中，该变量在链接期间自动地插入到内核映像中
    void *node_bootmem_map;

    unsigned long last_end_off;
    unsigned long hint_idx;

    /*
    内存不连续的系统可能需要多个bootmem分配器，一个典型的例子是NUMA计算机，其中每个结点注册了一个bootmem分配器，但如果物理地址空间中散布者空洞，也可以为每个连续内存区注册一个bootmem分配器
    注册新的自举分配器(bootmem)可以使用init_bootmem_core，所有注册的分配器保存在一个链表中，表头是全局变量bdata_list
    */
    struct list_head list;
} bootmem_data_t;

extern bootmem_data_t bootmem_node_data[];

#ifndef CONFIG_DISCONTIGMEM
static unsigned long __init setup_memory(void)
{
    unsigned long start_pfn, max_low_pfn, bootmap_size;

    //setup_memory分析检测到的内存区，以找到低端内存区中最大的页帧号，因为高端内存处理太过麻烦，因此对bootmem分配器无用
    start_pfn = PFN_UP( __pa(_end) );
    
    //全局变量max_low_pfn保存了可映射的最高页的编号，内核会在启动日志中报告找到的内存数量 
    max_low_pfn = PFN_DOWN( __pa(memory_end) );

    /*
     * Initialize the boot-time allocator (with low memory only):
     */
    bootmap_size = init_bootmem_node(NODE_DATA(0), start_pfn, CONFIG_MEMORY_START>>PAGE_SHIFT, max_low_pfn);

    /*
     * Register fully available low RAM pages with the bootmem allocator.
     */
    {
        unsigned long curr_pfn;
        unsigned long last_pfn;
        unsigned long pages;

        /*
         * We are rounding up the start address of usable memory:
         */
        curr_pfn = PFN_UP(__pa(memory_start));

        /*
         * ... and at the end of the usable range downwards:
         */
        last_pfn = PFN_DOWN(__pa(memory_end));

        if (last_pfn > max_low_pfn)
            last_pfn = max_low_pfn;

        pages = last_pfn - curr_pfn;
        free_bootmem(PFN_PHYS(curr_pfn), PFN_PHYS(pages));
    }

    /*
    Reserve the kernel text and Reserve the bootmem bitmap. We do this in two steps 
    first step was init_bootmem()), because this catches the (definitely buggy) case of us accidentally initializing the bootmem allocator with an invalid RAM area.
    
    由于bootmem分配器需要一些内存页用于管理分配位图，必须首先调用reserve_bootmem分配这些内存页
    但还有一些其他的内存区已经在使用中，必须相应地标记出来，因此还需要用reserve_bootmem注册相应的页，需要注册的内存区的准确数目，高度依赖于内核配置，例如
    1. 需要保留0页，因为在许多计算机上该页是一个特殊的BIOS页，有些特定于计算机的功能需要该页才能运作正常
    */
    reserve_bootmem(CONFIG_MEMORY_START + PAGE_SIZE, (PFN_PHYS(start_pfn) + bootmap_size + PAGE_SIZE - 1) - CONFIG_MEMORY_START, BOOTMEM_DEFAULT);

    /*
    reserve physical page 0 - it's a special BIOS page on many boxes, enabling clean reboots, SMP operation, laptop functions.
    */
    reserve_bootmem(CONFIG_MEMORY_START, PAGE_SIZE, BOOTMEM_DEFAULT);

    /*
     * reserve memory hole
     */
#ifdef CONFIG_MEMHOLE
    reserve_bootmem(CONFIG_MEMHOLE_START, CONFIG_MEMHOLE_SIZE,
            BOOTMEM_DEFAULT);
#endif

#ifdef CONFIG_BLK_DEV_INITRD
    if (LOADER_TYPE && INITRD_START) {
        if (INITRD_START + INITRD_SIZE <= (max_low_pfn << PAGE_SHIFT)) {
            reserve_bootmem(INITRD_START, INITRD_SIZE,
                    BOOTMEM_DEFAULT);
            initrd_start = INITRD_START + PAGE_OFFSET;
            initrd_end = initrd_start + INITRD_SIZE;
            printk("initrd:start[%08lx],size[%08lx]\n",
                initrd_start, INITRD_SIZE);
        } else {
            printk("initrd extends beyond end of memory "
                "(0x%08lx > 0x%08lx)\ndisabling initrd\n",
                INITRD_START + INITRD_SIZE,
                max_low_pfn << PAGE_SHIFT);

            initrd_start = 0;
        }
    }
#endif

    return max_low_pfn;
}
#else    /* CONFIG_DISCONTIGMEM */
extern unsigned long setup_memory(void);
#endif    /* CONFIG_DISCONTIGMEM */

内核提供了各种函数，用于在初始化期间分配内存，在UMA系统上有下列函数可用
    1) alloc_bootmem(size)
    2) alloc_bootmem_pages(size)
按指定的大小在ZONE_NORMAL内存域分配内存，数据是对齐的，这使得内存或者从可适用于L1高速缓存的理想位置开始，或者从边界开始
/*
需要注意的是，用alloc_bootmem/alloc_bootmem_pages函数申请指定大小的内存。如果需要在其他地方调用这块内存，可以将alloc_bootmem返回的内存首地址通过EXPORT_SYMBOL导出，然后就可以使用这块内存了，这种内存分配不是不是通过动态分配获得的，而是类似于"内核引导参数"在编译时就预留出来的内核内存
这种内存分配方式的缺点是，申请内存的代码必须在链接到内核中的代码里才能使用，因此必须重新编译内核，而且内存管理系统看不到这部分内存，需要用户自行管理
*/
    3) alloc_bootmem_low
    4) alloc_bootmem_low_pages
alloc_bootmem_low、alloc_bootmem_low_pages和alloc_bootmem、alloc_bootmem_pages类似，区别在于alloc_bootmem_low系列只是从ZONE_DMA内存域分配内存，因此，只有需要DMA内存时，才能使用上述API函数

/*
1. size: 所需内存区的长度
2. align: 数据的对齐方式
3. goal: 开始搜索适当空闲内存区的起始地址
    1) SMP_CACHE_BYTES: 对齐数据，使之在大多数体系结构上能够理想地置于L1高速缓存中
    2) PAGE_SIZE: 将数据对齐到页边界，适用于分配一个或多个整页
*/
static void * __init ___alloc_bootmem(unsigned long size, unsigned long align, unsigned long goal, unsigned long limit)
{
    void *mem = ___alloc_bootmem_nopanic(size, align, goal, limit);

    if (mem)
        return mem;
    /*
     * Whoops, we cannot satisfy the allocation request.
     */
    printk(KERN_ALERT "bootmem alloc of %lu bytes failed!\n", size);
    panic("Out of memory");
    return NULL;
}

static void * __init ___alloc_bootmem_nopanic(unsigned long size, unsigned long align, unsigned long goal, unsigned long limit)
{
    bootmem_data_t *bdata;
    void *region;

restart:
    region = alloc_arch_preferred_bootmem(NULL, size, align, goal, limit);
    if (region)
        return region;

    list_for_each_entry(bdata, &bdata_list, list) 
    {
        if (goal && bdata->node_low_pfn <= PFN_DOWN(goal))
            continue;
        if (limit && bdata->node_min_pfn >= PFN_DOWN(limit))
            break;

        /*
        alloc_bootmem_core韩素的功能相对而言很广泛，在启动期间不需要太高的效率，该函数主要实现了最先适配算法
        1. 从goal开始，扫描位图，查找满足分配请求的空闲内存页
        2. 如果目标页紧接着上一次分配的页，内核会判断所需的内存(包括对齐数据所需的padding空间)是否能够在上一页分配或从上一页开始分配
        3. 新分配的页在位图对应的比特位设置1
        */
        region = alloc_bootmem_core(bdata, size, align, goal, limit);
        if (region)
            return region;
    }

    if (goal) 
    {
        goal = 0;
        goto restart;
    }

    return NULL;
}

/**
 * free_bootmem - mark a page range as usable
 * @addr: starting address of the range
 * @size: size of the range in bytes
 *
 * Partial pages will be considered reserved and left as they are.
 *
 * The range must be contiguous but may span node boundaries.
 */
void __init free_bootmem(unsigned long addr, unsigned long size)
{
    unsigned long start, end;

    kmemleak_free_part(__va(addr), size);

    start = PFN_UP(addr);
    end = PFN_DOWN(addr + size);

    mark_bootmem(start, end, 0, 0);
}

/**
 * free_all_bootmem - release free pages to the buddy allocator
 *
 * Returns the number of pages actually released.
*/
unsigned long __init free_all_bootmem(void)
{
    return free_all_bootmem_core(NODE_DATA(0)->bdata);
}

static unsigned long __init free_all_bootmem_core(bootmem_data_t *bdata)
{
    int aligned;
    struct page *page;
    unsigned long start, end, pages, count = 0;

    if (!bdata->node_bootmem_map)
        return 0;

    start = bdata->node_min_pfn;
    end = bdata->node_low_pfn;

    /*
     * If the start is aligned to the machines wordsize, we might
     * be able to free pages in bulks of that order.
     */
    aligned = !(start & (BITS_PER_LONG - 1));

    bdebug("nid=%td start=%lx end=%lx aligned=%d\n", bdata - bootmem_node_data, start, end, aligned);

    //扫描bootmem分配器的页位图，释放每个未用的页
    while (start < end) 
    {
        unsigned long *map, idx, vec;

        map = bdata->node_bootmem_map;
        idx = start - bdata->node_min_pfn;
        vec = ~map[idx / BITS_PER_LONG];

        if (aligned && vec == ~0UL && start + BITS_PER_LONG < end) 
        {
            int order = ilog2(BITS_PER_LONG);

            //到伙伴系统的接口是__free_pages_bootmem函数，该函数对每个空闲页调用，该函数内部依赖于标准函数__free_page，它使得这些页并入伙伴系统的数据结构，在其中作为空闲页管理，可用于分配
            __free_pages_bootmem(pfn_to_page(start), order);
            count += BITS_PER_LONG;
        } 
        else 
        {
            unsigned long off = 0;

            while (vec && off < BITS_PER_LONG) 
            {
                if (vec & 1) 
                {
                    page = pfn_to_page(start + off);
                    __free_pages_bootmem(page, 0);
                    count++;
                }
                vec >>= 1;
                off++;
            }
        }
        start += BITS_PER_LONG;
    }

    page = virt_to_page(bdata->node_bootmem_map);
    pages = bdata->node_low_pfn - bdata->node_min_pfn;
    pages = bootmem_bootmap_pages(pages);
    count += pages;
    while (pages--)
        __free_pages_bootmem(page++, 0);

    bdebug("nid=%td released=%lx\n", bdata - bootmem_node_data, count);

    return count;
}

1. 对于链接到内核中的驱动程序而言，则不必要在内核内存中保持其数据结构的"初始化例程(init函数)"，在结构建立后，这些例程就不需要了
2. 驱动程序用于检测其设备的硬件数据库，在相关的设备已经识别之后，就不再需要了

int __init hyper_hopper_probe(struc net_device *dev);
static char stilllocking_msg[] _initdata = "found.\n";

/* These are for everybody (although not all archs will actually discard it in modules) */
#define __init        __section(.init.text) __cold notrace
#define __initdata    __section(.init.data)
#define __initconst    __section(.init.rodata)
#define __exitdata    __section(.exit.data)
#define __exit_call    __used __section(.exitcall.exit)

void free_initmem(void)
{
    free_init_pages("unused kernel memory", (unsigned long)(&__init_begin), (unsigned long)(&__init_end));
}

dmesg
...
Freeing unused kernel memory: 1292k freed 
Freeing unused kernel memory: 788k freed
Freeing unused kernel memory: 1568k freed
...

struct zone
{
    ..
    //不同长度的空闲区域
    struct free_area    free_area[MAX_ORDER];
    ..
}

http://www.cnblogs.com/LittleHann/p/3865490.html
//搜索：0x4: struct zone

struct free_area 
{
    //用于连接空闲页的链表，页链表包含大小相同的连续内存区，其中又定义了多个(MIGRATE_TYPES 个)页链表
    struct list_head    free_list[MIGRATE_TYPES];

    /*
    指定了当前内存区中空闲页块的数目
    1. 对0阶内存区逐页计算
    2. 对1阶内存区计算页对的数目
    3. 对2阶内存区计算4页集合的数目
    ..依次类推
    */
    unsigned long        nr_free;
};

/* Free memory management - zoned buddy allocator.  */
#ifndef CONFIG_FORCE_MAX_ZONEORDER
#define MAX_ORDER 11
#else
#define MAX_ORDER CONFIG_FORCE_MAX_ZONEORDER
#endif
#define MAX_ORDER_NR_PAGES (1 << (MAX_ORDER - 1))

1. 第0个链表包含的内存区为单页: 2(0)次方 = 1
2. 第1个链表管理的内存区为两页: 2(1)次方 = 2
3. 第3个链表管理的内存区为4页
..

Node 0, zone      DMA      0      4      3      2      1      1      0      0      1      1      3 
Node 0, zone    DMA32    475    196     63     49     25     28      9      3      5      4    153 
//给出了各个内存域中每个分配阶中空闲项的数目，从左至右，阶依次升高

1. 左侧的地址空间中散布着空闲页，尽管大约25%的物理内存仍然未分配，但最大的连续空闲页只有一页，这对用户空间程序没有问题，因为用户空间的内存是通过页表映射的，无论空闲页在物理内存中的分布如何，应用程序看到的内存都是"连续"的
2. 右图给出的情形中，空闲页和使用页的数目与左图相同，但所有空闲页都位于一个连续内存中

1. 不可移动页
在内存中有固定位置，不能移动到其他地方，核心内核分配的大多数内存属于该类别

2. 可回收页
不能直接移动，但可以删除，其内容可以从某些源重新生成，例如映射自文件的数据属于该类别
kswapd守护进程会根据可回收页访问的频繁程度，周期性释放此类内存，这是一个复杂的过程，属于页面回收的范畴，简单来说内核会在可回收页占据了太多内存时进行回收
另外，在内存短缺(即分配失败)时也可以发起页面回收

3. 可移动页
可以随意移动，属于用户空间应用程序的页属于该类别，它们是通过页表映射的，如果它们复制到新位置，页表项可以相应地更新，应用程序不会注意到任何区别

#define MIGRATE_UNMOVABLE     0        //
#define MIGRATE_RECLAIMABLE   1        //
#define MIGRATE_MOVABLE       2
#define MIGRATE_PCPTYPES      3        /* the number of types on the pcp lists */
#define MIGRATE_RESERVE       3        // 如果向具有特定可移动特性的列表请求分配内存失败，这种紧急情可以从MIGRATE_RESERVE分配内存
#define MIGRATE_ISOLATE       4        /* can't allocate from here MIGRATE_ISOLATE是一个特殊的虚拟区域，用于跨越NUMA结点移动物理内存页 */
#define MIGRATE_TYPES         5        // MIGRATE_TYPES用于表示迁移类型的数目，不代表具体的区域

struct free_area 
{
    //用于连接空闲页的链表，页链表包含大小相同的连续内存区，其中又定义了多个(MIGRATE_TYPES 个)页链表
    struct list_head    free_list[MIGRATE_TYPES];

    /*
    指定了当前内存区中空闲页块的数目
    1. 对0阶内存区逐页计算
    2. 对1阶内存区计算页对的数目
    3. 对2阶内存区计算4页集合的数目
    ..依次类推
    */
    unsigned long        nr_free;
};

/*
 * This array describes the order lists are fallen back to when the free lists for the desirable migrate type are depleted
 */
static int fallbacks[MIGRATE_TYPES][MIGRATE_TYPES-1] = 
{
    [MIGRATE_UNMOVABLE]   = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE,   MIGRATE_RESERVE },
    [MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE,   MIGRATE_RESERVE },
    [MIGRATE_MOVABLE]     = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_RESERVE },
    [MIGRATE_RESERVE]     = { MIGRATE_RESERVE,     MIGRATE_RESERVE,   MIGRATE_RESERVE }, /* Never used */
};

1. pageblock_order: 表示内核认为是"大"的一个分配阶
2. page_nr_pages: 表示该分配阶对应的页数

1. 在IA-32体系结构上，巨型页长度是4MB，因此每个巨型页由1024个普通页组成，而HUGETLB_PAGE_ORDER则定义为10
2. IA-64体系结构允许设置可变的普通和巨型页长度，因此HUGETLB_PAGE_ORDER的值取决于内核配置
3. 如果体系结构不支持巨型页，则将其定义为第二高的分配阶

#ifdef CONFIG_HUGETLB_PAGE
#ifdef CONFIG_HUGETLB_PAGE_SIZE_VARIABLE
    /* Huge page sizes are variable */
    extern int pageblock_order;
#else /* CONFIG_HUGETLB_PAGE_SIZE_VARIABLE */
    /* Huge pages are a constant size */
    #define pageblock_order        HUGETLB_PAGE_ORDER
#endif /* CONFIG_HUGETLB_PAGE_SIZE_VARIABLE */
#else /* CONFIG_HUGETLB_PAGE */
    /* If huge pages are not used, group by MAX_ORDER_NR_PAGES */
    #define pageblock_order        (MAX_ORDER-1)
#endif /* CONFIG_HUGETLB_PAGE */

1. __GFP_MOVALE: 分配的内存是可移动的
2. __GFP_RECLAIMABLE: 分配的内存是可回收的
//如果这些标志都没有设置，则分配的内存假定为不可移动的

Page block order: 9
Pages per block:  512

Free pages count per migrate type at order       0      1      2      3      4      5      6      7      8      9     10 
Node    0, zone      DMA, type    Unmovable      0      4      3      2      1      1      0      0      1      0      0 
Node    0, zone      DMA, type  Reclaimable      0      0      0      0      0      0      0      0      0      0      0 
Node    0, zone      DMA, type      Movable      0      0      0      0      0      0      0      0      0      0      3 
Node    0, zone      DMA, type      Reserve      0      0      0      0      0      0      0      0      0      1      0 
Node    0, zone      DMA, type      Isolate      0      0      0      0      0      0      0      0      0      0      0 
Node    0, zone    DMA32, type    Unmovable    100     92     31     21     14      5      2      0      1      1      0 
Node    0, zone    DMA32, type  Reclaimable      0      1      0      0      1      1      0      1      1      1      0 
Node    0, zone    DMA32, type      Movable      4      4      3      1      4     19      2      3      1      4    152 
Node    0, zone    DMA32, type      Reserve      1      0      1      1      1      1      1      1      1      1      0 
Node    0, zone    DMA32, type      Isolate      0      0      0      0      0      0      0      0      0      0      0 

Number of blocks type     Unmovable  Reclaimable      Movable      Reserve      Isolate 
Node 0, zone      DMA            1            0            6            1            0 
Node 0, zone    DMA32           74           42          898            2            0 

1. 系统中各个内存域的页帧边界，保存在max_zone_pfn数组
2. 各结点页帧的分配情况，保存在全局变量early_node_map中

/**
 * free_area_init_nodes - Initialise all pg_data_t and zone data
 * @max_zone_pfn: an array of max PFNs for each zone
 *
 * This will call free_area_init_node() for each active node in the system.
 * Using the page ranges provided by add_active_range(), the size of each
 * zone in each node and their holes is calculated. If the maximum PFN
 * between two adjacent zones match, it is assumed that the zone is empty.
 * For example, if arch_max_dma_pfn == arch_max_dma32_pfn, it is assumed
 * that arch_max_dma32_pfn has no pages. It is also assumed that a zone
 * starts where the previous one ended. For example, ZONE_DMA32 starts
 * at arch_max_dma_pfn.
 */
void __init free_area_init_nodes(unsigned long *max_zone_pfn)
{
    unsigned long nid;
    int i;

    /* 
    Sort early_node_map as initialisation assumes it is sorted 
    根据结点的第一个页帧start_pfn，对early_node_map中的各项进行排序
    */
    sort_node_map();

    /* 
    Record where the zone boundaries are 
    计算各个内存域可使用的最低和最高的页帧编号
    */
    memset(arch_zone_lowest_possible_pfn, 0, sizeof(arch_zone_lowest_possible_pfn));
    memset(arch_zone_highest_possible_pfn, 0, sizeof(arch_zone_highest_possible_pfn));
    //辅助函数find_min_pfn_with_active_regions用于找到注册的最低内存域中可用的编号最小的页帧，该内存域不一定是ZONE_DMA
    arch_zone_lowest_possible_pfn[0] = find_min_pfn_with_active_regions();
    arch_zone_highest_possible_pfn[0] = max_zone_pfn[0];
    //接下来构建其他内存域的页帧区间，方法很直接，第n个内存域的最小页帧 = 第n-1个内存域的最大页帧
    for (i = 1; i < MAX_NR_ZONES; i++) 
    {
        if (i == ZONE_MOVABLE)
            continue;
        arch_zone_lowest_possible_pfn[i] = arch_zone_highest_possible_pfn[i-1];
        arch_zone_highest_possible_pfn[i] = max(max_zone_pfn[i], arch_zone_lowest_possible_pfn[i]);
    }
    //因为ZONE_MOVABLE是一个虚拟内存域，不与真正的硬件内存域相关联，该内存域的边界总是设置为0
    arch_zone_lowest_possible_pfn[ZONE_MOVABLE] = 0;
    arch_zone_highest_possible_pfn[ZONE_MOVABLE] = 0;

    /* Find the PFNs that ZONE_MOVABLE begins at in each node */
    memset(zone_movable_pfn, 0, sizeof(zone_movable_pfn));
    find_zone_movable_pfns_for_nodes(zone_movable_pfn);

    /* Print out the zone ranges */
    printk("Zone PFN ranges:\n");
    for (i = 0; i < MAX_NR_ZONES; i++) 
    {
        if (i == ZONE_MOVABLE)
            continue;
        printk("  %-8s %0#10lx -> %0#10lx\n", zone_names[i], arch_zone_lowest_possible_pfn[i], arch_zone_highest_possible_pfn[i]);
    }

    /* Print out the PFNs ZONE_MOVABLE begins at in each node */
    printk("Movable zone start PFN for each node\n");
    for (i = 0; i < MAX_NUMNODES; i++) 
    {
        if (zone_movable_pfn[i])
            printk("  Node %d: %lu\n", i, zone_movable_pfn[i]);
    }

    /* Print out the early_node_map[] */
    printk("early_node_map[%d] active PFN ranges\n", nr_nodemap_entries);
    for (i = 0; i < nr_nodemap_entries; i++)
        printk("  %3d: %0#10lx -> %0#10lx\n", early_node_map[i].nid, early_node_map[i].start_pfn, early_node_map[i].end_pfn);

    /* Initialise every node */
    mminit_verify_pageflags_layout();
    setup_nr_node_ids();
    for_each_online_node(nid) 
    {
        pg_data_t *pgdat = NODE_DATA(nid);
        free_area_init_node(nid, NULL, find_min_pfn_for_node(nid), NULL);

        /* Any memory on that node */
        if (pgdat->node_present_pages)
            node_set_state(nid, N_HIGH_MEMORY);
        check_for_regular_memory(pgdat);
    }
}

void __paginginit free_area_init_node(int nid, unsigned long *zones_size, unsigned long node_start_pfn, unsigned long *zholes_size)
{
    pg_data_t *pgdat = NODE_DATA(nid);

    pgdat->node_id = nid;
    pgdat->node_start_pfn = node_start_pfn;
    /*
    累积各个内存域的页数，计算结点中页的生总数，对连续内存模型而言，这可以通过zones_size_init完成，但calculate_node_totalpages还考虑了内存域中的空洞
    在系统启动初始化期间，内核会输出一段简短的消息
    dmesg
    On node 0 totalpages: 524142
    */
    calculate_node_totalpages(pgdat, zones_size, zholes_size);

    /*
    alloc_node_mem_map负责初始化一个简单但非常重要的数据结构，即系统中的各个物理内存页，都对应着一个strcut page实例，该结构的初始化由alloc_node_mem_map执行
    */
    alloc_node_mem_map(pgdat);
#ifdef CONFIG_FLAT_NODE_MEM_MAP
    printk(KERN_DEBUG "free_area_init_node: node %d, pgdat %08lx, node_mem_map %08lx\n",
        nid, (unsigned long)pgdat,
        (unsigned long)pgdat->node_mem_map);
#endif

    //初始化内存域数据结构涉及的繁重工作由free_area_init_core执行，它会依次遍历结点的所有内存域
    free_area_init_core(pgdat, zones_size, zholes_size);
}

1. alloc_pages(mask, order)
分配2(order)次方页并返回一个struct page的实例，表示分配的内存块的起始页

2. get_zeroed_page(mask)
分配一页并返回一个struct page实例，页对应的内存填充0(所有其他函数分配之后页的内容是未定义的)

3. __get_free_pages(mask, order)
返回分配内存块的虚拟地址

4. get_dma_pages(gfp_mask, order)
用来获得适用于DMA的页
/*
在空闲内存无法满足请求以至于分配失败的情况下，所有上述函数都返回空指针(alloc_page)、或者0(get_zeroed_page、__get_free_pages、get_dma_pages)
因此内核在每次分配之后都必须检查返回的结果，这种惯例与设计良好的用户层应用程序类似，但在内核中忽略检查会导致严重得多的故障
*/

1. vmalloc
2. vmalloc_32
//使用页表将不连续的内存映射到内核地址空间中，使之看上去是连续的

3. kmalloc类型的函数
//用于分配小于一整页的内存区

1. free_page(struct page *)
2. free_pages(struct page *, order);
//用于将一个2(order)次方页返回(释放)给内存管理子系统，内存区的起始地址由指向该内存区的第一个page实例的的指针表示

3. __free_page(addr)
4. __free_pages(addr, order);
//语义类似于1、2函数，但在表示需要释放的内存区时，使用了虚拟内存地址而不是page实例

/*
 * GFP bitmasks..
 *
 * Zone modifiers (see linux/mmzone.h - low three bits)
 *
 * Do not put any conditional on these. If necessary modify the definitions without the underscores and use the consistently. The definitions here may be used in bit comparisons.
*/
#define __GFP_DMA    ((__force gfp_t)0x01u)
#define __GFP_HIGHMEM    ((__force gfp_t)0x02u)
#define __GFP_DMA32    ((__force gfp_t)0x04u)
#define GFP_ZONEMASK    (__GFP_DMA|__GFP_HIGHMEM|__GFP_DMA32|__GFP_MOVABLE)

/*
1. 如果__GFP_DMA、__GFP_HIGHMEM都没有设置，则首先扫描ZONE_NORMAL，然后是ZONE_DMA
2. 如果设置了__GFP_HIGHMEM，没有设置__GFP_DMA，则结果是从__GFP_HIGHMEM开始扫描所有3个内存域
3. 如果设置了__GFP_DMA，那么不管__GFP_HIGHMEM设置与否都从__GFP_DMA开始扫描

总之遵循的一个基本原则是: 尽量遵循掩码参数的指示，同时尽量从最廉价的内存域开始分配
*/
static inline enum zone_type gfp_zone(gfp_t flags)
{
    enum zone_type z;
    int bit = flags & GFP_ZONEMASK;

    z = (GFP_ZONE_TABLE >> (bit * ZONES_SHIFT)) & ((1 << ZONES_SHIFT) - 1);

    if (__builtin_constant_p(bit))
        MAYBE_BUILD_BUG_ON((GFP_ZONE_BAD >> bit) & 1);
    else {
#ifdef CONFIG_DEBUG_VM
        BUG_ON((GFP_ZONE_BAD >> bit) & 1);
#endif
    }
    return z;
}

/*
 * Action modifiers - doesn't change the zoning
 */
 /* 
 Can wait and reschedule 可以等待和重调度 
 __GFP_WAIT表示分配内存的请求可以中断，即调度器在该请求期间可以随意选择另一个进程执行，或者该请求可以被另一个更重要的事件中断
 分配器还可以在返回内存之前，在队列上等待一个事件，相关进程会进入睡眠状态
 */
#define __GFP_WAIT    ((__force gfp_t)0x10u)    

/* 
Should access emergency pools 应该访问紧急分配池 
如果请求非常重要，则设置__GFP_HIGH，即内核急切地需要内存时，在分配内存失败可能给内核带来严重后果时(例如威胁到系统稳定性或系统崩溃)，总是会使用该标志
*/
#define __GFP_HIGH    ((__force gfp_t)0x20u)    

/* 
Can start physical IO 可以启动物理IO 
__GFP_IO说明在查找空闲内存期间内核可以进行I/O操作，实际上，这意味着如果内核在内存分配期间换出页，那么仅当设置该标志时，才能将选择的页写入硬盘
*/
#define __GFP_IO    ((__force gfp_t)0x40u)

/* 
Can call down to low-level FS 可以调用底层文件系统 
__GFP_FS允许内核执行VFS操作，在与VFS层有联系的内核子系统中必须禁用，因为这可能引起循环递归调用
*/
#define __GFP_FS    ((__force gfp_t)0x80u)            

#define __GFP_COLD    ((__force gfp_t)0x100u)            /* Cache-cold page required 需要分缓存的冷页(即不在CPU高速缓存中的"冷页") */
#define __GFP_NOWARN    ((__force gfp_t)0x200u)        /* Suppress page allocation failure warning 禁止分配失败告警*/
#define __GFP_REPEAT    ((__force gfp_t)0x400u)        /* Try hard to allocate the memory, but the allocation attempt _might_ fail.  This depends upon the particular VM implementation 重试分配，但在重试若干次后会停止，可能失败 */
#define __GFP_NOFAIL    ((__force gfp_t)0x800u)        /* The VM implementation _must_ retry infinitely: the caller cannot handle allocation failures 一直重试，不会失败*/
#define __GFP_NORETRY    ((__force gfp_t)0x1000u)    /* The VM implementation must not retry indefinitely 不重试，可能失败 */
#define __GFP_COMP    ((__force gfp_t)0x4000u)        /* Add compound page metadata 增加复合页元数据 */
#define __GFP_ZERO    ((__force gfp_t)0x8000u)        /* Return zeroed page on success 成功则返回填充字节0的页 */
#define __GFP_NOMEMALLOC ((__force gfp_t)0x10000u)     /* Don't use emergency reserves 不使用紧急分配链表 */

/* 
Enforce hardwall cpuset memory allocs 只允许在进程允许运行的CPU所关联的结点分配内存
__GFP_HARDWALL只在NUMA系统上有意义，它限制只在分配到当前进程的各个CPU所关联的结点分配内存，如果进程允许在所有CPU上运行(默认情况)，该标志是无意义的，只有进程可以运行的CPU受限时，该标志才有效果
*/
#define __GFP_HARDWALL   ((__force gfp_t)0x20000u)     

/* 
No fallback, no policies 没有备用结点，没有策略
__GFP_THISNODE只有在NUMA系统上才有意义，如果设置该比特位，则内存分配失败的情况下不允许使用其他结点作为备用，需要保证在当前结点或者明确指定的结点上成功分配内存
*/
#define __GFP_THISNODE    ((__force gfp_t)0x40000u)    
#define __GFP_RECLAIMABLE ((__force gfp_t)0x80000u) /* Page is reclaimable 页是可回收的*/
#define __GFP_MOVABLE    ((__force gfp_t)0x08u)      /*  Flag that this page will be movable by the page migration mechanism or reclaimed 页是可移动的 */

#ifdef CONFIG_KMEMCHECK
#define __GFP_NOTRACK    ((__force gfp_t)0x200000u)  /* Don't track with kmemcheck */
#else
#define __GFP_NOTRACK    ((__force gfp_t)0)
#endif

/* This equals 0, but use constants in case they ever change */
#define GFP_NOWAIT    (GFP_ATOMIC & ~__GFP_HIGH)
/* 
GFP_ATOMIC means both !wait (__GFP_WAIT not set) and use emergency pool 
GFP_ATOMIC用于原子分配，在任何情况下都不能中断，可能使用紧急分配链表中的内存
*/
#define GFP_ATOMIC    (__GFP_HIGH)

//GFP_NOIO明确禁止I/O操作，但可能被中断
#define GFP_NOIO    (__GFP_WAIT)
//GFP_NOIO明确禁止I/O操作、以及访问VFS层，但可能被中断
#define GFP_NOFS    (__GFP_WAIT | __GFP_IO)

//GFP_KERNEL是内核的默认配置，它的失败不会立即威胁系统稳定性，这是内核源代码中最常使用的标志
#define GFP_KERNEL    (__GFP_WAIT | __GFP_IO | __GFP_FS)
#define GFP_TEMPORARY    (__GFP_WAIT | __GFP_IO | __GFP_FS | __GFP_RECLAIMABLE)
#define GFP_USER    (__GFP_WAIT | __GFP_IO | __GFP_FS | __GFP_HARDWALL)

/*
GFP_HIGHUSER是GFP_USER的一个扩展，也用于用户空间，它允许分配无法直接映射的高端内存
使用高端内存是没有坏处的，因为用户进程的地址空间总是通过非线性页表组织的
*/
#define GFP_HIGHUSER    (__GFP_WAIT | __GFP_IO | __GFP_FS | __GFP_HARDWALL |  __GFP_HIGHMEM)
#define GFP_HIGHUSER_MOVABLE    (__GFP_WAIT | __GFP_IO | __GFP_FS | __GFP_HARDWALL | __GFP_HIGHMEM | __GFP_MOVABLE)

#ifdef CONFIG_NUMA
#define GFP_THISNODE    (__GFP_THISNODE | __GFP_NOWARN | __GFP_NORETRY)
#else
#define GFP_THISNODE    ((__force gfp_t)0)
#endif

/* This mask makes up all the page movable related flags */
#define GFP_MOVABLE_MASK (__GFP_RECLAIMABLE|__GFP_MOVABLE)

/* Control page allocator reclaim behavior */
#define GFP_RECLAIM_MASK (__GFP_WAIT|__GFP_HIGH|__GFP_IO|__GFP_FS| __GFP_NOWARN|__GFP_REPEAT|__GFP_NOFAIL| __GFP_NORETRY|__GFP_NOMEMALLOC)

/* Control slab gfp mask during early boot */
#define GFP_BOOT_MASK __GFP_BITS_MASK & ~(__GFP_WAIT|__GFP_IO|__GFP_FS)

/* Control allocation constraints */
#define GFP_CONSTRAINT_MASK (__GFP_HARDWALL|__GFP_THISNODE)

/* Do not use these with a slab allocator */
#define GFP_SLAB_BUG_MASK (__GFP_DMA32|__GFP_HIGHMEM|~__GFP_BITS_MASK)

/* Flag - indicates that the buffer will be suitable for DMA.  Ignored on some
   platforms, used as appropriate on others */

#define GFP_DMA        __GFP_DMA

/* 4GB DMA on some platforms */
#define GFP_DMA32    __GFP_DMA32

1. alloc_page
#define alloc_page(gfp_mask) alloc_pages(gfp_mask, 0)
//分配0阶的内存页，即1页

2. alloc_pages
#define alloc_pages(gfp_mask, order) alloc_pages_node(numa_node_id(), gfp_mask, order)

3. __get_free_page
#define __get_free_page(gfp_mask) __get_free_pages((gfp_mask),0)
//分配0阶的内存页，即1页

4. __get_free_pages
//
unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order)
{
    struct page *page;

    /*
     * __get_free_pages() returns a 32-bit address, which cannot represent a highmem page
    */
    VM_BUG_ON((gfp_mask & __GFP_HIGHMEM) != 0);

    page = alloc_pages(gfp_mask, order);
    if (!page)
        return 0;
    return (unsigned long) page_address(page);
}
EXPORT_SYMBOL(__get_free_pages);

5. __get_dma_pages
#define __get_dma_pages(gfp_mask, order) __get_free_pages((gfp_mask) | GFP_DMA,(order))

6. get_zeroed_page
unsigned long get_zeroed_page(gfp_t gfp_mask)
{
    return __get_free_pages(gfp_mask | __GFP_ZERO, 0);
}
EXPORT_SYMBOL(get_zeroed_page);

1. __free_pages
void __free_pages(struct page *page, unsigned int order)
{
    if (put_page_testzero(page)) 
    {
        trace_mm_page_free_direct(page, order);
        if (order == 0)
            free_hot_page(page);
        else
            __free_pages_ok(page, order);
    }
}

2. __free_page
#define __free_page(page) __free_pages((page), 0)

3. free_page
#define free_page(addr) free_pages((addr),0)

4. free_pages
void free_pages(unsigned long addr, unsigned int order)
{
    if (addr != 0) {
        VM_BUG_ON(!virt_addr_valid((void *)addr));
        //virt_to_page将虚拟内存底子好转换为指向page实例的指针
        __free_pages(virt_to_page((void *)addr), order);
    }
}
EXPORT_SYMBOL(free_pages);
//free_pages和__free_pages之间的关系通过函数而不是宏建立，因为首先必须将虚拟地址转换为指向struct page的指针

static inline struct page *alloc_pages_node(int nid, gfp_t gfp_mask, unsigned int order)
{
    /* 
    Unknown node is current node 
    如果指定负的结点ID(不存在)，内核自动地使用当前执行CPU对应的结点ID
    */
    if (nid < 0)
        nid = numa_node_id();

    //node_zonelist用于选择分配内存的内存域
    return __alloc_pages(gfp_mask, order, node_zonelist(nid, gfp_mask));
}

/* The ALLOC_WMARK bits are used as an index to zone->watermark */
#define ALLOC_WMARK_MIN        WMARK_MIN     /* 使用pages_min水印 */
#define ALLOC_WMARK_LOW        WMARK_LOW     /* 使用pages_low水印 */
#define ALLOC_WMARK_HIGH    WMARK_HIGH     /* 使用pages_high水印 */
#define ALLOC_NO_WATERMARKS    0x04         /* don't check watermarks at all 完全不检查水印 */

/* Mask to get the watermark bits */
#define ALLOC_WMARK_MASK    (ALLOC_NO_WATERMARKS-1)

#define ALLOC_HARDER        0x10         /* try to alloc harder 试图更努力地分配，即放宽限制 */
#define ALLOC_HIGH             0x20         /* __GFP_HIGH set 设置了__GFP_HIGH */
#define ALLOC_CPUSET        0x40         /* check for correct cpuset 检查内存结点是否对应着指定的CPU集合 */

/*
 * Return 1 if free pages are above 'mark'. This takes into account the order of the allocation.
*/
int zone_watermark_ok(struct zone *z, int order, unsigned long mark, int classzone_idx, int alloc_flags)
{
    /* free_pages my go negative - that's OK */
    long min = mark;
    long free_pages = zone_nr_free_pages(z) - (1 << order) + 1;
    int o;

    //在解释了ALLOC_HIGH、ALLOC_HARDER标志之后(将最小值标记降低到当前值的一半或四分之一，使得分配过程更加努力，即放宽限制)
    if (alloc_flags & ALLOC_HIGH)
        min -= min / 2;
    if (alloc_flags & ALLOC_HARDER)
        min -= min / 4;

    //检查空闲页的数目是否小于最小值 + lowmem_reserve中指定的紧急分配值之和
    if (free_pages <= min + z->lowmem_reserve[classzone_idx])
        return 0;
    //如果不小于，则遍历所有小于当前阶的分配阶，从free_pages减去当前分配阶的所有空闲页(左移o位是必要的，因为nr_free记载的是当前分配阶的空闲页块数目)
    for (o = 0; o < order; o++) 
    {
        /* 
        At the next order, this order's pages become unavailable 
        在下一阶，当前阶的页是不可用的
        */
        free_pages -= z->free_area[o].nr_free << o;

        /* 
        Require fewer higher order pages to be free 所需高阶空闲页的数目相对较少 
        每升高一阶，所需空闲页的最小值折半
        */
        min >>= 1;

        //如果内核遍历所有的低端内存域之后，发现内存不足，则不进行内存分配
        if (free_pages <= min)
            return 0;
    }
    return 1;
}

/*
 * get_page_from_freelist goes through the zonelist trying to allocate a page.
*/
static struct page *get_page_from_freelist(gfp_t gfp_mask, nodemask_t *nodemask, unsigned int order, struct zonelist *zonelist, int high_zoneidx, int alloc_flags, struct zone *preferred_zone, int migratetype)
{
    struct zoneref *z;
    struct page *page = NULL;
    int classzone_idx;
    struct zone *zone;
    nodemask_t *allowednodes = NULL;/* zonelist_cache approximation */
    int zlc_active = 0;        /* set if using zonelist_cache */
    int did_zlc_setup = 0;        /* just call zlc_setup() one time */

    classzone_idx = zone_idx(preferred_zone);
zonelist_scan:
    /*
     * Scan zonelist, looking for a zone with enough free.
     * See also cpuset_zone_allowed() comment in kernel/cpuset.c.
     */
    for_each_zone_zonelist_nodemask(zone, z, zonelist, high_zoneidx, nodemask)
    {
        if (NUMA_BUILD && zlc_active && !zlc_zone_worth_trying(zonelist, z, allowednodes))
                continue;
        //cpuset_zone_allowed_softwall用于检查给定内存域是否属于该进程允许运行的CPU
        if ((alloc_flags & ALLOC_CPUSET) && !cpuset_zone_allowed_softwall(zone, gfp_mask))
                goto try_next_zone;

        BUILD_BUG_ON(ALLOC_NO_WATERMARKS < NR_WMARK);
        if (!(alloc_flags & ALLOC_NO_WATERMARKS)) 
        {
            unsigned long mark;
            int ret;

            mark = zone->watermark[alloc_flags & ALLOC_WMARK_MASK];
            //zone_watermark_ok接下来检查所遍历到内存域是否有足够的空闲页，并试图分配一个连续的内存块(足够空闲页、连续内存两者必须同时满足才可继续，否则循环进行到备用列表中的写一个内存域)
            if (zone_watermark_ok(zone, order, mark, classzone_idx, alloc_flags))
                goto try_this_zone;

            if (zone_reclaim_mode == 0)
                goto this_zone_full;

            ret = zone_reclaim(zone, gfp_mask, order);
            switch (ret) 
            {
            case ZONE_RECLAIM_NOSCAN:
                /* did not scan */
                goto try_next_zone;
            case ZONE_RECLAIM_FULL:
                /* scanned but unreclaimable */
                goto this_zone_full;
            default:
                /* did we reclaim enough */
                if (!zone_watermark_ok(zone, order, mark, classzone_idx, alloc_flags))
                    goto this_zone_full;
            }
        }

try_this_zone:
        //如果内存域适用于当前的分配请求，则调用buffered_rmqueue试图从中分配所需数目的页
        page = buffered_rmqueue(preferred_zone, zone, order, gfp_mask, migratetype);
        if (page)
            break;
this_zone_full:
        if (NUMA_BUILD)
            zlc_mark_zone_full(zonelist, z);
try_next_zone:
        if (NUMA_BUILD && !did_zlc_setup && nr_online_nodes > 1) {
            /*
             * we do zlc_setup after the first zone is tried but only
             * if there are multiple nodes make it worthwhile
             */
            allowednodes = zlc_setup(zonelist, alloc_flags);
            zlc_active = 1;
            did_zlc_setup = 1;
        }
    }

    if (unlikely(NUMA_BUILD && page == NULL && zlc_active)) {
        /* Disable zlc cache for second zonelist scan */
        zlc_active = 0;
        goto zonelist_scan;
    }
    return page;
}

static inline struct page *__alloc_pages(gfp_t gfp_mask, unsigned int order, struct zonelist *zonelist)
{
    return __alloc_pages_nodemask(gfp_mask, order, zonelist, NULL);
}

/*
 * This is the 'heart' of the zoned buddy allocator.
 */
struct page *__alloc_pages_nodemask(gfp_t gfp_mask, unsigned int order, struct zonelist *zonelist, nodemask_t *nodemask)
{
    enum zone_type high_zoneidx = gfp_zone(gfp_mask);
    struct zone *preferred_zone;
    struct page *page;
    int migratetype = allocflags_to_migratetype(gfp_mask);

    gfp_mask &= gfp_allowed_mask;

    lockdep_trace_alloc(gfp_mask);

    might_sleep_if(gfp_mask & __GFP_WAIT);

    if (should_fail_alloc_page(gfp_mask, order))
        return NULL;

    /*
    Check the zones suitable for the gfp_mask contain at least one valid zone. 
    It's possible to have an empty zonelist as a result of GFP_THISNODE and a memoryless node
    适合于gfp_mask的内存域列表
    */
    if (unlikely(!zonelist->_zonerefs->zone))
        //如果没有在内存的结点上使用GFP_THISNODE，导致zonelist为空，就会发生这种情况
        return NULL;

    /* The preferred zone is used for statistics later */
    first_zones_zonelist(zonelist, high_zoneidx, nodemask, &preferred_zone);
    if (!preferred_zone)
        return NULL;

    /* 
    First allocation attempt 
    在最简单的情形中，分配空闲内存区只涉及调用一次get_page_from_freelist，然后返回所需数目的页
    */
    page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, nodemask, order, zonelist, high_zoneidx, ALLOC_WMARK_LOW|ALLOC_CPUSET, preferred_zone, migratetype);
    if (unlikely(!page))
        //第一次内存分配尝试不会特别积极，如果在某个内存域中无法找到空闲内存，则意味着内存相对较紧张，内核需要更多的工作量才能找到更多内存
        page = __alloc_pages_slowpath(gfp_mask, order, zonelist, high_zoneidx, nodemask, preferred_zone, migratetype);

    trace_mm_page_alloc(page, order, gfp_mask, migratetype);
    return page;
}
EXPORT_SYMBOL(__alloc_pages_nodemask);

static inline struct page *__alloc_pages_slowpath(gfp_t gfp_mask, unsigned int order, struct zonelist *zonelist, enum zone_type high_zoneidx, nodemask_t *nodemask, struct zone *preferred_zone, int migratetype)
{
    const gfp_t wait = gfp_mask & __GFP_WAIT;
    struct page *page = NULL;
    int alloc_flags;
    unsigned long pages_reclaimed = 0;
    unsigned long did_some_progress;
    struct task_struct *p = current;

    /*
     * In the slowpath, we sanity check order to avoid ever trying to
     * reclaim >= MAX_ORDER areas which will never succeed. Callers may
     * be using allocators in order of preference for an area that is
     * too large.
     */
    if (order >= MAX_ORDER) 
    {
        WARN_ON_ONCE(!(gfp_mask & __GFP_NOWARN));
        return NULL;
    }

    /*
     * GFP_THISNODE (meaning __GFP_THISNODE, __GFP_NORETRY and
     * __GFP_NOWARN set) should not cause reclaim since the subsystem
     * (f.e. slab) using GFP_THISNODE may choose to trigger reclaim
     * using a larger set of nodes after it has established that the
     * allowed per node queues are empty and that nodes are
     * over allocated.
     */
    if (NUMA_BUILD && (gfp_mask & GFP_THISNODE) == GFP_THISNODE)
        goto nopage;

restart:
    //唤醒负责换出页的kswapd守护进程，空闲内存可以通过缩减内核缓存和非热点页面回收来获得，即写回或换出很少使用的页，这两种措施都是由该守护进程发起的
    wake_all_kswapd(order, zonelist, high_zoneidx);

    /*
    OK, we're below the kswapd watermark and have kicked background reclaim. Now things get more complex, so set up alloc_flags according to how we want to proceed.
    在交互守护进程唤醒后，内核开始新的尝试，这一次进行的搜索更为积极，对分配标志进行了调整，修改为一些在当前特定情况下更有可能分配成功的标志
    同时，将水印降低到最小值，对实时进程和指定了__GFP_WAIT标志因为不能睡眠的调用，会设置ALLOC_HARDER
    */
    alloc_flags = gfp_to_alloc_flags(gfp_mask);

rebalance:
    /* 
    This is the last chance, in general, before the goto nopage. 
    使用修改后的标志集，再一次调用get_page_from_freelist，试图获得所需的页
    如果再次失败，内核会借助更强有力的措施
    */
    page = get_page_from_freelist(gfp_mask, nodemask, order, zonelist, high_zoneidx, alloc_flags & ~ALLOC_NO_WATERMARKS, preferred_zone, migratetype);
    if (page)
        goto got_pg;

    /* Allocate without watermarks if the context allows */
    if (alloc_flags & ALLOC_NO_WATERMARKS) 
    {
        page = __alloc_pages_high_priority(gfp_mask, order, zonelist, high_zoneidx, nodemask, preferred_zone, migratetype);
        if (page)
            goto got_pg;
    }

    /* Atomic allocations - we can't balance anything */
    if (!wait)
        goto nopage;

    /* Avoid recursion of direct reclaim */
    if (p->flags & PF_MEMALLOC)
        goto nopage;

    /* Avoid allocations with no watermarks from looping endlessly */
    if (test_thread_flag(TIF_MEMDIE) && !(gfp_mask & __GFP_NOFAIL))
        goto nopage;

    /* 
    Try direct reclaim and then allocating 
    尝试回收页面，并继续分配
    */
    page = __alloc_pages_direct_reclaim(gfp_mask, order, zonelist, high_zoneidx, nodemask, alloc_flags, preferred_zone, migratetype, &did_some_progress);
    if (page)
        goto got_pg;

    /*
     * If we failed to make any progress reclaiming, then we are running out of options and have to consider going OOM
     */
    if (!did_some_progress) 
    {
        if ((gfp_mask & __GFP_FS) && !(gfp_mask & __GFP_NORETRY)) 
        {
            if (oom_killer_disabled)
                goto nopage;
            page = __alloc_pages_may_oom(gfp_mask, order, zonelist, high_zoneidx, nodemask, preferred_zone, migratetype);
            if (page)
                goto got_pg;

            /*
            The OOM killer does not trigger for high-order ~__GFP_NOFAIL allocations so if no progress is being made, 
            there are no other options and retrying is unlikely to help.
            */
            if (order > PAGE_ALLOC_COSTLY_ORDER &&
                        !(gfp_mask & __GFP_NOFAIL))
                goto nopage;

            goto restart;
        }
    }

    /* Check if we should retry the allocation */
    pages_reclaimed += did_some_progress;
    if (should_alloc_retry(gfp_mask, order, pages_reclaimed)) 
    {
        /*
        Wait for some write requests to complete then retry 
        等待块设备层队列释放，这样内核就有机会换出页
        */
        congestion_wait(BLK_RW_ASYNC, HZ/50);
        goto rebalance;
    }

nopage:
    //无论如何都无法分配内存了，只能打印OOM事件信息了
    if (!(gfp_mask & __GFP_NOWARN) && printk_ratelimit()) 
    {
        printk(KERN_WARNING "%s: page allocation failure. order:%d, mode:0x%x\n", p->comm, order, gfp_mask);
        dump_stack();
        show_mem();
    }
    return page;
got_pg:
    if (kmemcheck_enabled)
        kmemcheck_pagealloc_alloc(page, order, gfp_mask);
    return page;
}

1. 必须检查这些页是否是"连续"的，因为到目前为止，只知道有许多空闲页
2. 必须按伙伴系统的方式从free_lists移除这些页，这可能需要分解并重排内存区

/*
Really, prep_compound_page() should be called from __rmqueue_bulk(). 
But we cheat by calling it from here, in the order > 0 path.  Saves a branch or two.
*/
static inline struct page *buffered_rmqueue(struct zone *preferred_zone, struct zone *zone, int order, gfp_t gfp_flags, int migratetype)
{
    unsigned long flags;
    struct page *page;
    //如果分配标志设定了__GFP_COLD，那么必须从per-CPU缓存取得冷页
    int cold = !!(gfp_flags & __GFP_COLD);
    int cpu;

again:
    cpu  = get_cpu();
    //如果只分配一页，内核会进行优化，即分配阶为0 = 2(1)次方的情况，该页不是从伙伴系统直接取得，而是取自per-CPU的页缓存
    if (likely(order == 0)) 
    {
        struct per_cpu_pages *pcp;
        struct list_head *list;

        //在只请求一页时，内核试图借助于per-CPU缓存加速请求的处理，如果缓存为空，内核可借机检查缓存的填充水平
        pcp = &zone_pcp(zone, cpu)->pcp;
        list = &pcp->lists[migratetype];
        local_irq_save(flags);
        if (list_empty(list)) 
        {
            //在针对当前处理器选择了适当的per-CPU列表(热页或冷页列表)之后，调用rmqueue_bulk重新填充缓存
            pcp->count += rmqueue_bulk(zone, 0, pcp->batch, list, migratetype, cold);
            if (unlikely(list_empty(list)))
                goto failed;
        }

        if (cold)
            page = list_entry(list->prev, struct page, lru);
        else
            page = list_entry(list->next, struct page, lru);

        list_del(&page->lru);
        pcp->count--;
    } 
    else 
    {
        //需要分配多页
        if (unlikely(gfp_flags & __GFP_NOFAIL)) 
        {
            /*
             * __GFP_NOFAIL is not to be used in new code.
             *
             * All __GFP_NOFAIL callers should be fixed so that they
             * properly detect and handle allocation failures.
             *
             * We most definitely don't want callers attempting to
             * allocate greater than order-1 page units with
             * __GFP_NOFAIL.
             */
            WARN_ON_ONCE(order > 1);
        }
        spin_lock_irqsave(&zone->lock, flags);
        //__rmqueue会从内存域的伙伴列表中选择适当的内存块，如果有必要，该函数会自动分解大块内存，将未用的部分放回列表中
        page = __rmqueue(zone, order, migratetype);
        spin_unlock(&zone->lock);
        //如果内存域中有足够的空闲页满足分配请求，但页不是连续的，这种情况，__rmqueue调用失败并返回NULL指针
        if (!page)
            goto failed;
        __mod_zone_page_state(zone, NR_FREE_PAGES, -(1 << order));
    }

    __count_zone_vm_events(PGALLOC, zone, 1 << order);
    zone_statistics(preferred_zone, zone);
    local_irq_restore(flags);
    put_cpu();

    VM_BUG_ON(bad_range(zone, page));
    /*
    由于所有失败情形都跳转到标号failed处理，这可以确保内核到达当前点之后，page指向一系列有效的页
    在返回指针前，prep_new_page需要做一些准备工作，以便内核能够处理这些页，如果所选择的页出了问题，该函数返回正值，在这种情况下，分配将从头开始
    */
    if (prep_new_page(page, order, gfp_flags))
        goto again;
    return page;

failed:
    local_irq_restore(flags);
    put_cpu();
    return NULL;
}

/*
Do the hard work of removing an element from the buddy allocator. Call me with the zone->lock already held.
*/
static struct page *__rmqueue(struct zone *zone, unsigned int order, int migratetype)
{
    struct page *page;

retry_reserve:
    //根据传递进来的分配阶、用于获取页的内存域、迁移类型，__rmqueue_smallest扫描页的列表，直至找到适当的连续内存块
    page = __rmqueue_smallest(zone, order, migratetype);

    if (unlikely(!page) && migratetype != MIGRATE_RESERVE)
    {
        //如果指定的迁移列表不能满足分配请求，则调用__rmqueue_fallback尝试其他的迁移列表，作为应急措施
        page = __rmqueue_fallback(zone, order, migratetype);

        /*
         * Use MIGRATE_RESERVE rather than fail an allocation. goto
         * is used because __rmqueue_smallest is an inline function
         * and we want just one call site
         */
        if (!page) 
        {
            migratetype = MIGRATE_RESERVE;
            goto retry_reserve;
        }
    }

    trace_mm_page_alloc_zone_locked(page, order, migratetype);
    return page;
}

/*
Go through the free lists for the given migratetype and remove the smallest available page from the freelists
*/
static inline struct page *__rmqueue_smallest(struct zone *zone, unsigned int order, int migratetype)
{
    unsigned int current_order;
    struct free_area * area;
    struct page *page;

    /* 
    Find a page of the appropriate size in the preferred list 在首选的列表中找到适当大小的页
    搜索从指定分配阶对应的项开始，因为要求页必须是连续的，所以最好的情况也是当前对应分配阶中正好能找到一块内存区
    1. 如果检查的列表中有一个元素(非空)，那么它就是可用的，因为其中包含了所需数目的连续页
    2. 否则，内核将选择下一个更高分配阶，进行类似的搜索 
    */
    for (current_order = order; current_order < MAX_ORDER; ++current_order) 
    {
        area = &(zone->free_area[current_order]);
        if (list_empty(&area->free_list[migratetype]))
            continue;

        page = list_entry(area->free_list[migratetype].next, struct page, lru);
        list_del(&page->lru);
        rmv_page_order(page);
        area->nr_free--;
        //如果需要分配的内存块长度小于所选择的连续页范围，即如果因为没有更小的适当的内存块可用，而从较高的分配阶分配了一块内存，那么该内存块必须按照伙伴系统的原理分裂成更小的块，即调用expand
        expand(zone, page, order, current_order, area, migratetype);
        return page;
    }

    return NULL;
}

void __free_pages(struct page *page, unsigned int order)
{
    if (put_page_testzero(page)) 
    {
        trace_mm_page_free_direct(page, order);
        /*
        首先判断所需释放的内存是单页还是较大的内存块
        1. 如果释放单页，则不还给伙伴系统(在申请内存的时候，如果是单页，也不从伙伴系统中申请，而是从per-CPU中申请)，而是置于per-CPU缓存中，对很可能出现在CPU高速缓存的页，则放置到热页的列表中
        free_hot_page简单的进行参数转换，随即调用free_hot_cold_page
        如果free_hot_cold_page判断per-CPU缓存中页的数目超出了pcp->count，则将数量为pcp->batch的一批内存还给伙伴系统，该策略称之为"惰性合并(lazy coalescing)"
        这种策略的原理在于: 如果单页直接返回给伙伴系统，那么会发生合，为了满足后来的分配请求又需要进行拆分，惰性合并策略阻止了大量可能白费的合并和拆分操作
        */
        if (order == 0)
            free_hot_page(page);
        else
            /*
            如果释放多个页，则将工作委托给__free_pages_ok，即将相关的内存区添加到伙伴系统中适当的free_area列表，即合并到为一个连续的内存区，放置到高一阶的free_area列表中
            如果还能合并一个进一步的伙伴对，那么继续进行合并，转移到更高阶的列表，该过程会一直重复下去，直至所有可能的伙伴对都已经合并，并将改变尽可能向上传播
            该策略的核心思想是: 尽量创造出尽可能多的大块连续内存
            */
            __free_pages_ok(page, order);
    }
}

/*
 * Locate the struct page for both the matching buddy in our pair (buddy1) and the combined O(n+1) page they form (page).
 *
 * 1) Any buddy B1 will have an order O twin B2 which satisfies the following equation:
 *     B2 = B1 ^ (1 << O)
 * For example, if the starting buddy (buddy2) is #8 its order 1 buddy is #10:
 *     B2 = 8 ^ (1 << 1) = 8 ^ 2 = 10
 *
 * 2) Any buddy B will have an order O+1 parent P which satisfies the following equation:
 *     P = B & ~(1 << O)
 *
 * Assumption: *_mem_map is contiguous at least up to MAX_ORDER
 */
static inline struct page *__page_find_buddy(struct page *page, unsigned long page_idx, unsigned int order)
{
    unsigned long buddy_idx = page_idx ^ (1 << order);

    return page + (buddy_idx - page_idx);
}

static inline unsigned long __find_combined_index(unsigned long page_idx, unsigned int order)
{
    return (page_idx & ~(1 << order));
}

/*
 * This function checks whether a page is free && is the buddy, we can do coalesce a page and its buddy if
 * (a) the buddy is not in a hole &&
 * (b) the buddy is in the buddy system &&
 * (c) a page and its buddy have the same order &&
 * (d) a page and its buddy are in the same zone.
 *
 * For recording whether a page is in the buddy system, we use PG_buddy. Setting, clearing, and testing PG_buddy is serialized by zone->lock.
 * For recording page's order, we use page_private(page).
 */
static inline int page_is_buddy(struct page *page, struct page *buddy, int order)
{
    /*
    伙伴的第一页如果在伙伴系统中，则对应的struct page实例会设置PG_buddy标志位，但这不足以作为合并两个伙伴的根据
    在释放2(order)次方页的内存块时，内核必须确保第二个伙伴的2(order)次方页也包含在伙伴系统中
    */
    if (!pfn_valid_within(page_to_pfn(buddy)))
        return 0;

    if (page_zone_id(page) != page_zone_id(buddy))
        return 0;

    if (PageBuddy(buddy) && page_order(buddy) == order) {
        VM_BUG_ON(page_count(buddy) != 0);
        return 1;
    }
    return 0;
}

/*
 * Freeing function for a buddy system allocator.
 *
 * The concept of a buddy system is to maintain direct-mapped table(containing bit values) for memory blocks of various "orders".
 * The bottom level table contains the map for the smallest allocatable units of memory (here, pages), and each level above it describes pairs of units from the levels below, hence, "buddies".
 * At a high level, all that happens here is marking the table entry at the bottom level available, and propagating the changes upward as necessary, 
 * plus some accounting needed to play nicely with other parts of the VM system.
 * At each level, we keep a list of pages, which are heads of continuous free pages of length of (1 << order) and marked with PG_buddy.  Page's order is recorded in page_private(page) field.
 * So when we are allocating or freeing one, we can derive the state of the other.  
 * That is, if we allocate a small block, and both were free, the remainder of the region must be split into blocks.   
 * If a block is freed, and its buddy is also free, then this triggers coalescing into a block of larger size.            
*/
static inline void __free_one_page(struct page *page, struct zone *zone, unsigned int order, int migratetype)
{
    unsigned long page_idx;

    if (unlikely(PageCompound(page)))
        if (unlikely(destroy_compound_page(page, order)))
            return;

    VM_BUG_ON(migratetype == -1);

    page_idx = page_to_pfn(page) & ((1 << MAX_ORDER) - 1);

    VM_BUG_ON(page_idx & ((1 << order) - 1));
    VM_BUG_ON(bad_range(zone, page));

    //例程试图释放分配阶为order的一个内存块，因为有可能不只当前内存块能够与其直接伙伴合并，而且高阶的伙伴也可以合并，因此内核需要找到可能的"最大分配阶"
    while (order < MAX_ORDER-1) 
    {
        unsigned long combined_idx;
        struct page *buddy;

        buddy = __page_find_buddy(page, page_idx, order);
        if (!page_is_buddy(page, buddy, order))
            break;

        /* Our buddy is free, merge with it and move up one order. */
        list_del(&buddy->lru);
        zone->free_area[order].nr_free--;
        rmv_page_order(buddy);
        combined_idx = __find_combined_index(page_idx, order);
        page = page + (combined_idx - page_idx);
        page_idx = combined_idx;
        order++;
    }
    set_page_order(page, order);
    list_add(&page->lru, &zone->free_area[order].free_list[migratetype]);
    zone->free_area[order].nr_free++;
}

关于vmalloc函数的相关编程使用方法请参阅另一篇文章
http://www.cnblogs.com/LittleHann/p/4113830.html

struct vm_struct 
{
    //next使得内核可以将vmalloc区域中的所有子区域保存在一个单链表上
    struct vm_struct    *next;

    //addr定义了分配的子区域在虚拟地址空间中的起始地址
    void            *addr;
    //size表示该区域的长度，可以根据该信息得到vmalloc区域的完成分配方案
    unsigned long        size;
    /*
    flags存储了与该内存区关联的标志联合，它只用于指定内存区类型
    1. VM_ALLOC: 指定由vmalloc产生的子区域
    2. VM_MAP: 用于表示将现存pages集合映射到连续的虚拟地址空间汇总
    3. VM_TOREMAP: 表示将几乎随机的物理内存区域映射到vmalloc区域中，这是一个特定于体系结构的操作
    */
    unsigned long        flags;
    //pages是指向page指针数组的指针，每个数组成员都表示一个映射到虚拟地址空间中的物理内存页的page实例
    struct page        **pages;
    //nr_pages指定pages中数组项的数目，即涉及的内存页数目
    unsigned int        nr_pages;
    //phys_addr仅当用ioremap映射到由物理地址描述的物理内存区域时才需要，该信息保存在phys_addr中
    unsigned long        phys_addr;
    void            *caller;
};

/*** Old vmalloc interfaces ***/
DEFINE_RWLOCK(vmlist_lock);
struct vm_struct *vmlist;

/**
 *    get_vm_area  -  reserve a contiguous kernel virtual area
 *    @size:        size of the area
 *    @flags:        %VM_IOREMAP for I/O mappings or VM_ALLOC
 *
 *    Search an area of @size in the kernel virtual mapping area, and reserved it for out purposes.  Returns the area descriptor on success or %NULL on failure.
 */
struct vm_struct *get_vm_area(unsigned long size, unsigned long flags)
{
    return __get_vm_area_node(size, 1, flags, VMALLOC_START, VMALLOC_END, -1, GFP_KERNEL, __builtin_return_address(0));
}

static struct vm_struct *__get_vm_area_node(unsigned long size, unsigned long align, unsigned long flags, unsigned long start, unsigned long end, int node, gfp_t gfp_mask, void *caller)
{
    static struct vmap_area *va;
    struct vm_struct *area;

    BUG_ON(in_interrupt());
    if (flags & VM_IOREMAP) 
    {
        int bit = fls(size);

        if (bit > IOREMAP_MAX_ORDER)
            bit = IOREMAP_MAX_ORDER;
        else if (bit < PAGE_SHIFT)
            bit = PAGE_SHIFT;

        align = 1ul << bit;
    }

    size = PAGE_ALIGN(size);
    if (unlikely(!size))
        return NULL;

    area = kzalloc_node(sizeof(*area), gfp_mask & GFP_RECLAIM_MASK, node);
    if (unlikely(!area))
        return NULL;

    /*
    We always allocate a guard page.
    总是分配一个警戒页，作为安全隙，内核首先适当提高需要分配的内存长度
    */
    size += PAGE_SIZE;

    va = alloc_vmap_area(size, align, start, end, node, gfp_mask);
    if (IS_ERR(va)) 
    {
        kfree(area);
        return NULL;
    }

    /*
     * When this function is called from __vmalloc_node,
     * we do not add vm_struct to vmlist here to avoid
     * accessing uninitialized members of vm_struct such as
     * pages and nr_pages fields. They will be set later.
     * To distinguish it from others, we use a VM_UNLIST flag.
     */
    if (flags & VM_UNLIST)
        setup_vmalloc_vm(area, va, flags, caller);
    else
        insert_vmalloc_vm(area, va, flags, caller);

    return area;
}

/**
 *    remove_vm_area  -  find and remove a continuous kernel virtual area
 *    @addr:        base address
 *
 *    Search for the kernel VM area starting at @addr, and remove it. This function returns the found VM area, but using it is NOT safe on SMP machines, except for its size or flags.
 */
struct vm_struct *remove_vm_area(const void *addr)
{
    struct vmap_area *va;

    //依次扫描vmlist的链表元素，直至找到匹配者
    va = find_vmap_area((unsigned long)addr);
    if (va && va->flags & VM_VM_AREA) 
    {
        struct vm_struct *vm = va->private;

        if (!(vm->flags & VM_UNLIST)) 
        {
            struct vm_struct *tmp, **p;
            /*
             * remove from list and disallow access to
             * this vm_struct before unmap. (address range
             * confliction is maintained by vmap.)
             */
            write_lock(&vmlist_lock);
            for (p = &vmlist; (tmp = *p) != vm; p = &tmp->next)
                ;
            *p = tmp->next;
            write_unlock(&vmlist_lock);
        }

        vmap_debug_free_range(va->va_start, va->va_end);
        free_unmap_vmap_area(va);
        vm->size -= PAGE_SIZE;

        return vm;
    }
    return NULL;
}

/**
 *    vmalloc  -  allocate virtually contiguous memory
 *    @size:        allocation size
 *    Allocate enough pages to cover @size from the page level
 *    allocator and map them into contiguous kernel virtual space.
 *
 *    For tight control over page level allocator and protection flags
 *    use __vmalloc() instead.
 */
void *vmalloc(unsigned long size)
{
    return __vmalloc_node(size, 1, GFP_KERNEL | __GFP_HIGHMEM, PAGE_KERNEL, -1, __builtin_return_address(0));
}
EXPORT_SYMBOL(vmalloc);

void *__vmalloc(unsigned long size, gfp_t gfp_mask, pgprot_t prot)
{
    return __vmalloc_node(size, 1, gfp_mask, prot, -1, __builtin_return_address(0));
}
EXPORT_SYMBOL(__vmalloc);

/**
 *    __vmalloc_node  -  allocate virtually contiguous memory
 *    @size:        allocation size
 *    @align:        desired alignment
 *    @gfp_mask:    flags for the page level allocator
 *    @prot:        protection mask for the allocated pages
 *    @node:        node to use for allocation or -1
 *    @caller:    caller's return address
 *
 *    Allocate enough pages to cover @size from the page level
 *    allocator with @gfp_mask flags.  Map them into contiguous
 *    kernel virtual space, using a pagetable protection of @prot.
 */
static void *__vmalloc_node(unsigned long size, unsigned long align, gfp_t gfp_mask, pgprot_t prot, int node, void *caller)
{
    struct vm_struct *area;
    void *addr;
    unsigned long real_size = size;

    size = PAGE_ALIGN(size);
    if (!size || (size >> PAGE_SHIFT) > totalram_pages)
        return NULL;

    //在vmlloc地址空间中找到一个适当的区域
    area = __get_vm_area_node(size, align, VM_ALLOC | VM_UNLIST, VMALLOC_START, VMALLOC_END, node, gfp_mask, caller);

    if (!area)
        return NULL;

    //从物理内存中分配各个页
    addr = __vmalloc_area_node(area, gfp_mask, prot, node, caller);

    /*
    In this function, newly allocated vm_struct is not added to vmlist at __get_vm_area_node(). so, it is added here.
    将这些页连续地映射到vmalloc区域中
    */
    insert_vmalloc_vmlist(area);

    /*
     * A ref_count = 3 is needed because the vm_struct and vmap_area
     * structures allocated in the __get_vm_area_node() function contain
     * references to the virtual address of the vmalloc'ed block.
     */
    kmemleak_alloc(addr, real_size, 3, gfp_mask);

    return addr;
}

使用vmalloc从伙伴系统分配内存时，是逐页分配的，而不是一次分配一大块连续内存，这是vmalloc的一个关键方面。如果可以确信能够分配连续内存页，那么就没有必要使用vmalloc，毕竟该函数的所有目的就在于: 即使因为内存碎片的缘故，内存块中的页帧可能不是连续的，还是依旧能够分配大的内存块。将分配单位拆分得尽可能小(即以页为单位)，可以确保在物理内存有严重碎片的情况下，vmalloc仍然可以工作

1. vmalloc_32
vmalloc_32的工作方式与vmalloc相同，但会确保所使用的物理内存总是可以用普通32位指针寻址

2. vmap
使用一个page数组作为起点，来创建虚拟连续内存区，与vmalloc相比，该函数所用的物理内存位置不是隐式分配的，而需要先行分配好，作为参数传递

3. ioremap
ioremap是一个特定于处理器的函数，必须在所有体系结构上实现，它可以取自物理地址空间、由系统总线用于I/O操作的一个内存块，映射到内核的地址空间中
//该函数在设备驱动程序中使用很多，可将用于与外设通信的地址区域暴露给内核的其他部分使用

1. vfree用于释放vmalloc和vmalloc_32分配的区域
2. vunmap用于释放由vmap或ioremap创建的映射

/*
1. addr: 表示要释放的区域的起始地址
2. deallocate_pages: 指定了是否将与该区域相关的物理内存页返回给伙伴系统
    1) vfree: 将这个参数设置为1
    2) vunmap: 将这个参数设置为0，即只删除映射，而不将相关的物理内存页返回给伙伴系统
*/
static void __vunmap(const void *addr, int deallocate_pages)
{
    struct vm_struct *area;

    if (!addr)
        return;

    if ((PAGE_SIZE-1) & (unsigned long)addr) 
    {
        WARN(1, KERN_ERR "Trying to vfree() bad address (%p)\n", addr);
        return;
    }

    //不必明确给出需要释放的区域长度，长度可以从vmlist中的信息导出，remove_vm_area扫描该链表，以找到相关项
    area = remove_vm_area(addr);
    if (unlikely(!area)) 
    {
        WARN(1, KERN_ERR "Trying to vfree() nonexistent vm area (%p)\n",
                addr);
        return;
    }

    debug_check_no_locks_freed(addr, area->size);
    debug_check_no_obj_freed(addr, area->size);

    if (deallocate_pages) 
    {
        int i;

        for (i = 0; i < area->nr_pages; i++) 
        {
            struct page *page = area->pages[i];

            BUG_ON(!page);
            __free_page(page);
        }

        //释放用于管理该内存区的内核数据结构
        if (area->flags & VM_VPAGES)
            vfree(area->pages);
        else
            kfree(area->pages);
    }

    kfree(area);
    return;
}

#ifdef CONFIG_HIGHMEM
#include <asm/highmem.h>

/* declarations for linux/mm/highmem.c */
unsigned int nr_free_highpages(void);
extern unsigned long totalhigh_pages;

void kmap_flush_unused(void);

#else /* CONFIG_HIGHMEM */

static inline unsigned int nr_free_highpages(void) { return 0; }

#define totalhigh_pages 0

#ifndef ARCH_HAS_KMAP
static inline void *kmap(struct page *page)
{
    might_sleep();
    return page_address(page);
}

static inline void kunmap(struct page *page)
{
}

static inline void *kmap_atomic(struct page *page, enum km_type idx)
{
    pagefault_disable();
    return page_address(page);
}
#define kmap_atomic_prot(page, idx, prot)    kmap_atomic(page, idx)

#define kunmap_atomic(addr, idx)    do { pagefault_enable(); } while (0)
#define kmap_atomic_pfn(pfn, idx)    kmap_atomic(pfn_to_page(pfn), (idx))
#define kmap_atomic_to_page(ptr)    virt_to_page(ptr)

#define kmap_flush_unused()    do {} while(0)
#endif

#endif /* CONFIG_HIGHMEM */

/*
为了管理与进程关联的文件系统数据，内核必须经常生成strcut fs_struct的新实例，此类型实例占据的内存块同样需要经常回收(在进程结束时)，换句话说，内核趋向于非常有规律地分配并释放大小为sizeof(fs_struct)的内存块。SLAB分配器将释放的内存块保存在一个内部列表里，并不马上返回给伙伴系统，在请求为该类对象分配一个新实例时，会使用最近释放的内存块，这带来2个优点
*/
1. 由于内核不必使用伙伴系统算法，处理时间会变短(伙伴系统的阶次分配和递归的阶次合并相对较消耗时间)
2. 由于该内存块仍让是"新"的，因此其仍然驻留在CPU高速缓存的概率较高
3. 调用伙伴系统的操作对系统的数据和指令高速缓存有相当的影响，内核越浪费这些资源，这些资源对用户空间进程就越不可用，更轻量级的SLAB分配器在可能的情况下减少了对伙伴系统的调用，有助于防止"缓存污染"
4. 如果数据存储在伙伴系统直接提供的页中，那么其地址总是出现在2的幂次的整数倍附近，这对CPU高速缓存的利用有负面影响，由于这种地址分布，使得某些缓存行过度使用，而其他的则几乎为空，多处理器可能会加剧这种不利情况，因为不同的内存地址可能在不同的总线上传输，多处理会导致某些总线拥塞，而其他的总线几乎没有使用

经常使用的内核对象保存在CPU高速缓存中，这是我们想要的结果。着色这个术语是隐喻性的，它与颜色无关，只是表示SLAB中的对象需要移动的特定偏移量，以便使对象放置到不同的缓存行
值得注意的是，之所以称之为SLAB分配器，是因为各个缓存管理的对象，会合并为较大的组，覆盖一个或多个连续页帧，这种组称作SLAB，每个缓存由这几个这种SLAB组成

1. 微小的嵌入式系统: SLAB分配器代码量和复杂性都太高
2. 配备有大量物理内存的大规模并行系统: SLAB分配器所需的大量元数据可能成为一个问题

1. SLOB分配器(simple linked list of block)进行了特别优化，以便减少代码量，它围绕一个简单的内存块链表展开，在分配内存时，使用了同样简单的最先适配算法
SLOB分配器只有大约600行代码，十分的简单

2. SLUB分配器通过将页帧打包为组，并通过struct page中未使用的字段来管理这些组，试图最小化所需的内存开销

1. kmalloc、_kmalloc、kmalloc_node: 用于一般的(用于特定结点)内存分配函数
2. kmem_cache_alloc、kmem_cache_alloc_node: 提供(特定于结点)特定类型的内核缓存

1. kmalloc(size, flags)
分配长度为size字节的一个内存区，并返回指向该内存区起始处的一个void指针，如果没有足够内存，则结果为NULL指针
2. kfree(*ptr)
释放*ptr指向的内存区
3. vmalloc
4. vfree

5. percpu_alloc
6. percpu_free
//用于为各个系统CPU分配和释放所需内存区

cat /proc/slabinfo
slabinfo - version: 2.1
# name            <active_objs> <num_objs> <objsize> <objperslab> <pagesperslab> : tunables <limit> <batchcount> <sharedfactor> : slabdata <active_slabs> <num_slabs> <sharedavail>
ip_conntrack_expect      0      0    136   28    1 : tunables  120   60    8 : slabdata      0      0      0
ip_conntrack          24     26    304   13    1 : tunables   54   27    8 : slabdata      2      2      0
ip_fib_alias          16     59     64   59    1 : tunables  120   60    8 : slabdata      1      1      0
ip_fib_hash           16     59     64   59    1 : tunables  120   60    8 : slabdata      1      1      0
bio_map_info         100    105   1064    7    2 : tunables   24   12    8 : slabdata     15     15      0
dm_mpath               0      0   1064    7    2 : tunables   24   12    8 : slabdata      0      0      0
jbd_4k                 2      2   4096    1    1 : tunables   24   12    8 : slabdata      2      2      0
dm_uevent              0      0   2608    3    2 : tunables   24   12    8 : slabdata      0      0      0
dm_tio                 0      0     24  144    1 : tunables  120   60    8 : slabdata      0      0      0
dm_io                  0      0     48   77    1 : tunables  120   60    8 : slabdata      0      0      0
sgpool-128            32     32   4096    1    1 : tunables   24   12    8 : slabdata     32     32      0
sgpool-64             32     32   2048    2    1 : tunables   24   12    8 : slabdata     16     16      0
sgpool-32             32     32   1024    4    1 : tunables   54   27    8 : slabdata      8      8      0
sgpool-16             32     32    512    8    1 : tunables   54   27    8 : slabdata      4      4      0
sgpool-8              32     45    256   15    1 : tunables  120   60    8 : slabdata      3      3      0
scsi_io_context        0      0    112   34    1 : tunables  120   60    8 : slabdata      0      0      0
ext3_inode_cache   15169  15185    760    5    1 : tunables   54   27    8 : slabdata   3037   3037      0
ext3_xattr             0      0     88   44    1 : tunables  120   60    8 : slabdata      0      0      0
journal_handle        76    144     24  144    1 : tunables  120   60    8 : slabdata      1      1      0
journal_head         112    160     96   40    1 : tunables  120   60    8 : slabdata      4      4      0
revoke_table           2    202     16  202    1 : tunables  120   60    8 : slabdata      1      1      0
revoke_record          0      0     32  112    1 : tunables  120   60    8 : slabdata      0      0      0
uhci_urb_priv          0      0     56   67    1 : tunables  120   60    8 : slabdata      0      0      0
UNIX                  44     44    704   11    2 : tunables   54   27    8 : slabdata      4      4      0
flow_cache             0      0    128   30    1 : tunables  120   60    8 : slabdata      0      0      0
cfq_ioc_pool          43     90    128   30    1 : tunables  120   60    8 : slabdata      3      3      0
cfq_pool              40     90    216   18    1 : tunables  120   60    8 : slabdata      5      5      0
crq_pool              62     96     80   48    1 : tunables  120   60    8 : slabdata      2      2      0
deadline_drq           0      0     80   48    1 : tunables  120   60    8 : slabdata      0      0      0
as_arq                 0      0     96   40    1 : tunables  120   60    8 : slabdata      0      0      0
mqueue_inode_cache      1      4    896    4    1 : tunables   54   27    8 : slabdata      1      1      0
isofs_inode_cache      0      0    608    6    1 : tunables   54   27    8 : slabdata      0      0      0
hugetlbfs_inode_cache      1      7    576    7    1 : tunables   54   27    8 : slabdata      1      1      0
ext2_inode_cache       0      0    720    5    1 : tunables   54   27    8 : slabdata      0      0      0
ext2_xattr             0      0     88   44    1 : tunables  120   60    8 : slabdata      0      0      0
dnotify_cache          0      0     40   92    1 : tunables  120   60    8 : slabdata      0      0      0
dquot                  0      0    256   15    1 : tunables  120   60    8 : slabdata      0      0      0
eventpoll_pwq          3     53     72   53    1 : tunables  120   60    8 : slabdata      1      1      0
eventpoll_epi          2     20    192   20    1 : tunables  120   60    8 : slabdata      1      1      0
inotify_event_cache     63     92     40   92    1 : tunables  120   60    8 : slabdata      1      1      0
inotify_watch_cache     11     53     72   53    1 : tunables  120   60    8 : slabdata      1      1      0
kioctx                 0      0    320   12    1 : tunables   54   27    8 : slabdata      0      0      0
kiocb                  0      0    256   15    1 : tunables  120   60    8 : slabdata      0      0      0
fasync_cache           0      0     24  144    1 : tunables  120   60    8 : slabdata      0      0      0
shmem_inode_cache    224    250    768    5    1 : tunables   54   27    8 : slabdata     50     50      0
posix_timers_cache      0      0    128   30    1 : tunables  120   60    8 : slabdata      0      0      0
uid_cache              2     30    128   30    1 : tunables  120   60    8 : slabdata      1      1      0
ip_mrt_cache           0      0    128   30    1 : tunables  120   60    8 : slabdata      0      0      0
tcp_bind_bucket       21    112     32  112    1 : tunables  120   60    8 : slabdata      1      1      0
inet_peer_cache        2     30    128   30    1 : tunables  120   60    8 : slabdata      1      1      0
secpath_cache          0      0     64   59    1 : tunables  120   60    8 : slabdata      0      0      0
xfrm_dst_cache         0      0    384   10    1 : tunables   54   27    8 : slabdata      0      0      0
ip_dst_cache          47     60    384   10    1 : tunables   54   27    8 : slabdata      6      6      0
arp_cache              3     15    256   15    1 : tunables  120   60    8 : slabdata      1      1      0
RAW                   19     20    768    5    1 : tunables   54   27    8 : slabdata      4      4      0
UDP                    5      5    768    5    1 : tunables   54   27    8 : slabdata      1      1      0
tw_sock_TCP           19     20    192   20    1 : tunables  120   60    8 : slabdata      1      1      0
request_sock_TCP       0      0    128   30    1 : tunables  120   60    8 : slabdata      0      0      0
TCP                   10     10   1600    5    2 : tunables   24   12    8 : slabdata      2      2      0
blkdev_ioc            35    118     64   59    1 : tunables  120   60    8 : slabdata      2      2      0
blkdev_queue          23     25   1576    5    2 : tunables   24   12    8 : slabdata      5      5      0
blkdev_requests       41     70    272   14    1 : tunables   54   27    8 : slabdata      5      5      0
biovec-256             7      7   4096    1    1 : tunables   24   12    8 : slabdata      7      7      0
biovec-128             7      8   2048    2    1 : tunables   24   12    8 : slabdata      4      4      0
biovec-64              7      8   1024    4    1 : tunables   54   27    8 : slabdata      2      2      0
biovec-16              7     15    256   15    1 : tunables  120   60    8 : slabdata      1      1      0
biovec-4               7     59     64   59    1 : tunables  120   60    8 : slabdata      1      1      0
biovec-1              49    202     16  202    1 : tunables  120   60    8 : slabdata      1      1      0
bio                  300    360    128   30    1 : tunables  120   60    8 : slabdata     12     12      0
utrace_engine_cache      0      0     64   59    1 : tunables  120   60    8 : slabdata      0      0      0
utrace_cache           0      0     64   59    1 : tunables  120   60    8 : slabdata      0      0      0
sock_inode_cache      96     96    640    6    1 : tunables   54   27    8 : slabdata     16     16      0
skbuff_fclone_cache     21     21    512    7    1 : tunables   54   27    8 : slabdata      3      3      0
skbuff_head_cache    498    555    256   15    1 : tunables  120   60    8 : slabdata     37     37      0
file_lock_cache        5     22    176   22    1 : tunables  120   60    8 : slabdata      1      1      0
Acpi-Operand        3248   3304     64   59    1 : tunables  120   60    8 : slabdata     56     56      0
Acpi-ParseExt          0      0     64   59    1 : tunables  120   60    8 : slabdata      0      0      0
Acpi-Parse             0      0     40   92    1 : tunables  120   60    8 : slabdata      0      0      0
Acpi-State             0      0     80   48    1 : tunables  120   60    8 : slabdata      0      0      0
Acpi-Namespace      2199   2240     32  112    1 : tunables  120   60    8 : slabdata     20     20      0
delayacct_cache      225    295     64   59    1 : tunables  120   60    8 : slabdata      5      5      0
taskstats_cache       13     53     72   53    1 : tunables  120   60    8 : slabdata      1      1      0
proc_inode_cache    1188   1212    592    6    1 : tunables   54   27    8 : slabdata    202    202      3
sigqueue              96     96    160   24    1 : tunables  120   60    8 : slabdata      4      4      0
radix_tree_node     6432   6433    536    7    1 : tunables   54   27    8 : slabdata    919    919      0
bdev_cache            24     28    832    4    1 : tunables   54   27    8 : slabdata      7      7      0
sysfs_dir_cache     3468   3520     88   44    1 : tunables  120   60    8 : slabdata     80     80      0
mnt_cache             28     30    256   15    1 : tunables  120   60    8 : slabdata      2      2      0
inode_cache         1267   1281    560    7    1 : tunables   54   27    8 : slabdata    183    183      0
dentry_cache       23148  23148    216   18    1 : tunables  120   60    8 : slabdata   1286   1286      0
filp                 600   1185    256   15    1 : tunables  120   60    8 : slabdata     79     79      0
names_cache           25     25   4096    1    1 : tunables   24   12    8 : slabdata     25     25      0
avc_node              34     53     72   53    1 : tunables  120   60    8 : slabdata      1      1      0
selinux_inode_security  17931  18000     80   48    1 : tunables  120   60    8 : slabdata    375    375      0
key_jar                5     20    192   20    1 : tunables  120   60    8 : slabdata      1      1      0
idr_layer_cache      100    105    528    7    1 : tunables   54   27    8 : slabdata     15     15      0
buffer_head        43856  43880     96   40    1 : tunables  120   60    8 : slabdata   1097   1097      0
mm_struct             76     76    896    4    1 : tunables   54   27    8 : slabdata     19     19      0
vm_area_struct      1632   1914    176   22    1 : tunables  120   60    8 : slabdata     87     87    180
fs_cache             177    177     64   59    1 : tunables  120   60    8 : slabdata      3      3     60
files_cache           75     80    768    5    1 : tunables   54   27    8 : slabdata     16     16      0
signal_cache         122    144    832    9    2 : tunables   54   27    8 : slabdata     16     16      0
sighand_cache         87     87   2112    3    2 : tunables   24   12    8 : slabdata     29     29      0
task_struct          136    136   1888    2    1 : tunables   24   12    8 : slabdata     68     68      0
anon_vma             651   1440     24  144    1 : tunables  120   60    8 : slabdata     10     10     15
pid                  242    295     64   59    1 : tunables  120   60    8 : slabdata      5      5      0
shared_policy_node      0      0     48   77    1 : tunables  120   60    8 : slabdata      0      0      0
numa_policy           38    144     24  144    1 : tunables  120   60    8 : slabdata      1      1      0
size-131072(DMA)       0      0 131072    1   32 : tunables    8    4    0 : slabdata      0      0      0
size-131072            0      0 131072    1   32 : tunables    8    4    0 : slabdata      0      0      0
size-65536(DMA)        0      0  65536    1   16 : tunables    8    4    0 : slabdata      0      0      0
size-65536             0      0  65536    1   16 : tunables    8    4    0 : slabdata      0      0      0
size-32768(DMA)        0      0  32768    1    8 : tunables    8    4    0 : slabdata      0      0      0
size-32768             3      3  32768    1    8 : tunables    8    4    0 : slabdata      3      3      0
size-16384(DMA)        0      0  16384    1    4 : tunables    8    4    0 : slabdata      0      0      0
size-16384             5      5  16384    1    4 : tunables    8    4    0 : slabdata      5      5      0
size-8192(DMA)         0      0   8192    1    2 : tunables    8    4    0 : slabdata      0      0      0
size-8192             13     13   8192    1    2 : tunables    8    4    0 : slabdata     13     13      0
size-4096(DMA)         0      0   4096    1    1 : tunables   24   12    8 : slabdata      0      0      0
size-4096            130    130   4096    1    1 : tunables   24   12    8 : slabdata    130    130      0
size-2048(DMA)         0      0   2048    2    1 : tunables   24   12    8 : slabdata      0      0      0
size-2048            237    244   2048    2    1 : tunables   24   12    8 : slabdata    122    122      0
size-1024(DMA)         0      0   1024    4    1 : tunables   54   27    8 : slabdata      0      0      0
size-1024            752    752   1024    4    1 : tunables   54   27    8 : slabdata    188    188     27
size-512(DMA)          0      0    512    8    1 : tunables   54   27    8 : slabdata      0      0      0
size-512             405    416    512    8    1 : tunables   54   27    8 : slabdata     52     52      0
size-256(DMA)          0      0    256   15    1 : tunables  120   60    8 : slabdata      0      0      0
size-256            1080   1080    256   15    1 : tunables  120   60    8 : slabdata     72     72      0
size-128(DMA)          0      0    128   30    1 : tunables  120   60    8 : slabdata      0      0      0
size-64(DMA)           0      0     64   59    1 : tunables  120   60    8 : slabdata      0      0      0
size-64             2011   2183     64   59    1 : tunables  120   60    8 : slabdata     37     37      0
size-32(DMA)           0      0     32  112    1 : tunables  120   60    8 : slabdata      0      0      0
size-128            1316   1380    128   30    1 : tunables  120   60    8 : slabdata     46     46      0
size-32             2155   2352     32  112    1 : tunables  120   60    8 : slabdata     21     21      0
kmem_cache           134    134   2688    1    1 : tunables   24   12    8 : slabdata    134    134      0

1. 用于标识各个缓存的字符串名称(确保不会创建相同的缓存)
2. 缓存中活动对象的数量
3. 缓存中对象的总数(已用、未用)
4. 所管理对象的长度，按字节计算
5. 一个SLAB中对象的数量
6. 每个SLAB中页的数量
7. 活动SLAB的数量
8. 在内核决定向缓存分配更多内存时，所分配对象的数量。每次会分配一个较大的内存块，以减少与伙伴系统的交互，在缩小缓存时，也使用该值作为释放内存块的大小

1. 保存管理性数据的缓存对象
2. 保存被管理对象的各个SLAB

struct kmem_cache 
{
    /* 
    1) per-cpu data, touched during every alloc/free 
    指向一个数组，每次分配/释放期间都会访问，其中包含了与系统CPU数目相同的数组项，每个元素都是一个指针，指向一个数组缓存(array cache)，其中包含了对应于特定系统CPU的管理数据
    struct array_cache 
    {  
        unsigned int avail;  
        unsigned int limit;  
        unsigned int batchcount;  
        unsigned int touched;  
        spinlock_t lock;  
        void *entry[0];  
    };  
    为最好地利用CPU高速缓存(即尽可能地去访问热点数据，CPU高速缓存是一种硬件机制，而内核需要做的是尽可能遵循正确地使用方式操作内存，最大化地利用这个硬件机制)
    这些per-CPU指针是很重要的，在分配和释放对象时，采用后进先出原理(LIFO last in first out)，内核假定刚释放的对象仍然处于CPU高速缓存中，会尽快再次分配它(响应下一个分配请求)
    仅当per-CPU缓存为空时，才会用SLAB中的空闲对象重新填充它们
    */
    struct array_cache *array[NR_CPUS];
    /* 
    2) Cache tunables. Protected by cache_chain_mutex 
    可调整的缓存参数，由cache_chain_mutex保护
    */
    //batchcount指定了在per-CPU列表为空的情况下，从缓存的SLAB中获取对象的数目，它还表示在缓存增长时分配的对象数目
    unsigned int batchcount;
    //limit指定了per-CPU列表中保存的对象的最大数目，如果超出该值，内核会将batchcount个对象返回到SLAB，如果接下来内核缩减缓存，则释放的内存从SLAB返回到伙伴系统
    unsigned int limit;
    unsigned int shared;

    //buffer_size指定了缓存中管理的对象的长度
    unsigned int buffer_size;
    u32 reciprocal_buffer_size;
    /* 3) touched by every alloc & free from the backend */

    unsigned int flags;            /* constant flags  常数标志*/
    unsigned int num;            /* # of objs per slab 每个SLAB中对象的数量 */

    /* 
    4) cache_grow/shrink 
    缓存的增长/缩减
    */
    /* order of pgs per slab (2^n) 每个SLAB中页数，取以2为底的对数*/
    unsigned int gfporder;

    /* force GFP flags, e.g. GFP_DMA 强制的GFP标志 */
    gfp_t gfpflags;

    //colour指定了颜色的最大数目
    size_t colour;                
    /* cache colouring range 缓存着色范围，即基本偏移量乘以颜色值获得的绝对偏移量*/
    unsigned int colour_off;    /* colour offset 着色偏移 */
    struct kmem_cache *slabp_cache;
    unsigned int slab_size;
    /* dynamic flags 动态标志集合，描述SLAB的"动态性质" */
    unsigned int dflags;        

    /* constructor func 构造函数*/
    void (*ctor)(void *obj);

    /* 5) cache creation/removal 缓存创建/删除 */
    //name是一个字符串，包含该缓存的名称
    const char *name;
    //next是一个标准的链表元素，用于将kmem_cache的所有实例保存在全局链表cache_chain上
    struct list_head next;

    /* 6) statistics 统计量 */
#ifdef CONFIG_DEBUG_SLAB
    unsigned long num_active;
    unsigned long num_allocations;
    unsigned long high_mark;
    unsigned long grown;
    unsigned long reaped;
    unsigned long errors;
    unsigned long max_freeable;
    unsigned long node_allocs;
    unsigned long node_frees;
    unsigned long node_overflow;
    atomic_t allochit;
    atomic_t allocmiss;
    atomic_t freehit;
    atomic_t freemiss;

    /*
     * If debugging is enabled, then the allocator can add additional
     * fields and/or padding to every object. buffer_size contains the total
     * object size including these internal fields, the following two
     * variables contain the offset to the user object and its size.
     */
    int obj_offset;
    int obj_size;
#endif /* CONFIG_DEBUG_SLAB */

    /*
    We put nodelists[] at the end of kmem_cache, because we want to size this array to nr_node_ids slots instead of MAX_NUMNODES 
    We still use [MAX_NUMNODES] and not [1] or [0] because cache_cache is statically defined, so we reserve the max number of nodes.
    每个内存结点都对应3个表头，用于组织SLAB的链表
    1. 第一个链表: 包含完全用尽的SLAB
    2. 第二个链表: 包含部分空闲的SLAB
    3. 第三个链表: 空闲的SLAB
    */
    struct kmem_list3 *nodelists[MAX_NUMNODES];
    /*
     * Do not add fields after nodelists[]
     */
};

1. 仍然处于CPU高速缓存中的per-CPU对象
2. 现存SLAB中未使用的对象
3. 刚使用伙伴系统分配的新SLAB中未使用的对象

/*
 * The slab lists for all objects.
 */
struct kmem_list3 
{
    /*
    管理结构位于每个SLAB的起始处，保存了所有的管理数据(和用于连接缓存链表的链表元素)
    /*
    struct list_head slabs_partial;    /* partial list first, better asm code */
    struct list_head slabs_full;
    struct list_head slabs_free;

    //free_objects表示slabs_partial和slabs_free的所有SLAB中空闲对象的总数
    unsigned long free_objects;

    //free_limit指定了所有SLAB上容许未使用对象的最大数目
    unsigned int free_limit;
    unsigned int colour_next;    /* Per-node cache coloring 各结点缓存着色 */
    spinlock_t list_lock;
    struct array_cache *shared;    /* shared per node 结点内共享 */
    struct array_cache **alien;    /* on other nodes 在其他结点上 */

    /* 
    updated without locking 无需锁定即可更新 
    next_reap定义了内核在两次尝试收缩缓存之间，必须经过的时间间隔，其思想是防止由于频繁的缓存收缩和增长操作而降低系统性能
    这种操作可能在某些系统共负荷下发生，该技术只能在NUMA系统上使用
    */
    unsigned long next_reap;    

    /* 
    updated without locking 无需锁定即可更新 
    free_touched表示缓存是否是活动的，在从缓存获取一个对象时，内核将该变量的值设置为1，在缓存收缩时，该值重置为0
    但内核只有在free_touched预先设置为0时，才会收缩缓存，因为1表示内核的另一部分刚从该缓存获取对象，此时收缩是不合适的
    */
    int free_touched;        
};

1. SLAB创建时使用标志SLAB_HWCACHE_ALIGN，SLAB用户可以要求对象按硬件缓存行对齐，那么会按照cache_line_size的返回值进行对齐，该函数返回特定于处理器的L1缓存大小，如果对象小于缓存行长度的一半，那么将多个对象放入一个缓存行
2. 如果不要求按硬件缓存行对齐，那么内核保证对象按BYTES_PER_WORD对齐，该值是表示void指针所需字节的数目
/*
在32位机器上，void指针需要4个字节，因此对有6个字节的对象，则需要8 = 2 * 4个字节，15个字节的对象需要16 = 4 * 4个字节，多余的字节称为填充字节，填充字节可以加速对SLAB中对象的访问，如果使用对齐的地址，那么在几乎所有的体系结构上，内存访问都会更快，这弥补了使用填充字节必然导致需要更多内存的不利情况
*/

1. struct page -> lru.next: 指向页驻留的缓存的管理结构
2. struct page -> lru.prev: 指向保存该页的SLAB的管理结构

//处理缓存信息的设置和读取
1. static inline void page_set_cache(struct page *page, struct kmem_cache *cache)
2. static inline struct kmem_cache *page_get_cache(struct page *page)

//设置或读取SLAB信息
1. static inline void page_set_slab(struct page *page, struct slab *slab)
2. static inline struct slab *page_get_slab(struct page *page)

http://cxw06023273.iteye.com/blog/867312 
http://guojing.me/linux-kernel-architecture/posts/slab-structure/

1. 危险区(red zoning)
在每个对象的开始和结束处增加一个额外的内存区，其中填充已知的字节模式，如果模式被修改，程序员在分析内核内存时就可以注意到，可能是因为某些代码访问了不属于它们的内存区

2. 对象毒化(object poisoning)
在建立和释放SLAB时，将对象用预定义的的模式填充，如果在对象分配时注意到该模式已经改变，程序员知道已经发生了未授权的访问

/* 
internal cache of cache description objs 
该结构在内核中其他地方是不可见的，缓存的用户无须详细了解缓存是如何实现的，将SLAB缓存视为通过一组标准函数来高效地创建和释放特定类型对象的机制，就足够了
*/
static struct kmem_cache cache_cache = 
{
    .batchcount = 1,
    .limit = BOOT_CPUCACHE_ENTRIES,
    .shared = 1,
    .buffer_size = sizeof(struct kmem_cache),
    .name = "kmem_cache",
};

1. kmem_cache_init创建系统中的第一个SLAB缓存，以便为kmem_cache的实例提供内存，为此，内核使用的主要是在编译时创建的静态数据，实际上，一个静态的数据结构(initarray_cache)用作per-CPU数组，该缓存的名称是cache_cache
2. kmem_cache_init接下来初始化一般性的缓存，用作kmalloc内存的来源，为此，针对所需的各个缓存长度，分别调用kmem_cache_create 
3. 在kmem_cache_init最后一步，把到目前为止一直使用的数据结构的所有静态实例化成员，用kmalloc动态分配的版本替代

/*
1. name: 缓存名称，随后会出现在/proc/slabinfo中
2. size: 被管理对象以字节记的长度
3. align: 在对齐数据时使用的偏移量
4. flags: 一组标志
5. ctor: 构造函数
*/
struct kmem_cache *kmem_cache_create (const char *name, size_t size, size_t align, unsigned long flags, void (*ctor)(void *))

struct kmem_cache *kmem_cache_create (const char *name, size_t size, size_t align, unsigned long flags, void (*ctor)(void *))
{
    size_t left_over, slab_size, ralign;
    struct kmem_cache *cachep = NULL, *pc;
    gfp_t gfp;

    /*
    Sanity checks... these are all serious usage bugs.
    参数有效性检查
    */
    if (!name || in_interrupt() || (size < BYTES_PER_WORD) || size > KMALLOC_MAX_SIZE) 
    {
        printk(KERN_ERR "%s: Early error in slab %s\n", __func__, name);
        BUG();
    }

    /*
     * We use cache_chain_mutex to ensure a consistent view of
     * cpu_online_mask as well.  Please see cpuup_callback
     */
    if (slab_is_available()) 
    {
        get_online_cpus();
        mutex_lock(&cache_chain_mutex);
    }

    list_for_each_entry(pc, &cache_chain, next) 
    {
        char tmp;
        int res;

        /*
         * This happens when the module gets unloaded and doesn't
         * destroy its slab cache and no-one else reuses the vmalloc
         * area of the module.  Print a warning.
         */
        res = probe_kernel_address(pc->name, tmp);
        if (res) 
        {
            printk(KERN_ERR "SLAB: cache with size %d has lost its name\n", pc->buffer_size);
            continue;
        }

        if (!strcmp(pc->name, name)) 
        {
            printk(KERN_ERR "kmem_cache_create: duplicate cache %s\n", name);
            dump_stack();
            goto oops;
        }
    }

#if DEBUG
    WARN_ON(strchr(name, ' '));    /* It confuses parsers */
#if FORCED_DEBUG
    /*
     * Enable redzoning and last user accounting, except for caches with
     * large objects, if the increased size would increase the object size
     * above the next power of two: caches with object sizes just above a
     * power of two have a significant amount of internal fragmentation.
     */
    if (size < 4096 || fls(size - 1) == fls(size-1 + REDZONE_ALIGN + 2 * sizeof(unsigned long long)))
        flags |= SLAB_RED_ZONE | SLAB_STORE_USER;
    if (!(flags & SLAB_DESTROY_BY_RCU))
        flags |= SLAB_POISON;
#endif
    if (flags & SLAB_DESTROY_BY_RCU)
        BUG_ON(flags & SLAB_POISON);
#endif
    /*
     * Always checks flags, a caller might be expecting debug support which
     * isn't available.
     */
    BUG_ON(flags & ~CREATE_MASK);

    /*
    Check that size is in terms of words.  This is needed to avoid unaligned accesses for some archs when redzoning is used, 
    and makes sure any on-slab bufctl's are also correctly aligned.
    对象对齐
    */
    if (size & (BYTES_PER_WORD - 1)) 
    {
        size += (BYTES_PER_WORD - 1);
        size &= ~(BYTES_PER_WORD - 1);
    }

    /* calculate the final buffer alignment: */

    /* 
    1) arch recommendation: can be overridden for debug
    对象对齐通常也是基于基于处理器的字长，但如果设置了SLAB_HWCACHE_ALIGN标志，则内核按照特定于体系结构的函数cache_line_size给出的值，来对齐数据
    内核还尝试将尽可能多的对象填充到一个缓存行中，只要对象长度允许，则会一直尝试将对齐值除以2，因此，会有2、4、6..个对象放入一个缓存行，而不是只有一个对象
    */
    if (flags & SLAB_HWCACHE_ALIGN) 
    {
        /*
         * Default alignment: as specified by the arch code.  Except if
         * an object is really small, then squeeze multiple objects into
         * one cacheline.
         */
        ralign = cache_line_size();
        while (size <= ralign / 2)
            ralign /= 2;
    } else {
        ralign = BYTES_PER_WORD;
    }

    /*
     * Redzoning and user store require word alignment or possibly larger.
     * Note this will be overridden by architecture or caller mandated
     * alignment if either is greater than BYTES_PER_WORD.
     */
    if (flags & SLAB_STORE_USER)
        ralign = BYTES_PER_WORD;

    if (flags & SLAB_RED_ZONE) {
        ralign = REDZONE_ALIGN;
        /* If redzoning, ensure that the second redzone is suitably
         * aligned, by adjusting the object size accordingly. */
        size += REDZONE_ALIGN - 1;
        size &= ~(REDZONE_ALIGN - 1);
    }

    /* 
    2) arch mandated alignment 
    内核也考虑以下事实，某些体系结构需要一个最小值作为数据对齐的边界，由ARCH_SLAB_MINALIGN定义，用于所要求的对齐也可以接收
    */
    //体系结构强制的最小对齐值
    if (ralign < ARCH_SLAB_MINALIGN) 
    {
        ralign = ARCH_SLAB_MINALIGN;
    }
    /* 
    3) caller mandated alignment 
    使用者强制的对齐值
    */
    if (ralign < align) 
    {
        ralign = align;
    }
    /* disable debug if necessary */
    if (ralign > __alignof__(unsigned long long))
        flags &= ~(SLAB_RED_ZONE | SLAB_STORE_USER);
    /*
    4) Store it.
    存储最后计算出的对齐值
    */
    align = ralign;

    if (slab_is_available())
        gfp = GFP_KERNEL;
    else
        gfp = GFP_NOWAIT;

    /*
    Get cache's description obj. 
    在数据对齐值计算完毕之后，分配struct kmem_cache的一个新实例
    */
    cachep = kmem_cache_zalloc(&cache_cache, gfp);
    if (!cachep)
        goto oops;

#if DEBUG
    cachep->obj_size = size;

    /*
     * Both debugging options require word-alignment which is calculated
     * into align above.
     */
    if (flags & SLAB_RED_ZONE) {
        /* add space for red zone words */
        cachep->obj_offset += sizeof(unsigned long long);
        size += 2 * sizeof(unsigned long long);
    }
    if (flags & SLAB_STORE_USER) {
        /* user store requires one word storage behind the end of
         * the real object. But if the second red zone needs to be
         * aligned to 64 bits, we must allow that much space.
         */
        if (flags & SLAB_RED_ZONE)
            size += REDZONE_ALIGN;
        else
            size += BYTES_PER_WORD;
    }
#if FORCED_DEBUG && defined(CONFIG_DEBUG_PAGEALLOC)
    if (size >= malloc_sizes[INDEX_L3 + 1].cs_size
        && cachep->obj_size > cache_line_size() && ALIGN(size, align) < PAGE_SIZE) {
        cachep->obj_offset += PAGE_SIZE - ALIGN(size, align);
        size = PAGE_SIZE;
    }
#endif
#endif

    /*
    Determine if the slab management is 'on' or 'off' slab.
    (bootstrapping cannot cope with offslab caches so don't do it too early on.)
    确定是否将SLAB头存储在SLAB之上相对比较简单，如果对象长度大于页帧的1/8，则将头部管理数据存储在SLAB之外，否则存储在SLAB之上
    */
    if ((size >= (PAGE_SIZE >> 3)) && !slab_early_init)
        /*
         * Size is large, assume best to place the slab management obj
         * off-slab (should allow better packing of objs).
         */
        flags |= CFLGS_OFF_SLAB;

    //增加对象的长度size，直至对应到之前计算的对齐值
    size = ALIGN(size, align);

    /*
    尝试找到适当的页数用作SLAB长度，不太小，也不太大。SLAB中对象太少会增加管理开销，降低方法的效率，而过大的SLAB内存区则对伙伴系统不利
    针对特定的页数，来计算对象数目、浪费的空间、着色所需的空间，循环往复，直至内核对结果满意为止
    */
    left_over = calculate_slab_order(cachep, size, align, flags);

    if (!cachep->num) 
    {
        printk(KERN_ERR "kmem_cache_create: couldn't create cache %s.\n", name);
        kmem_cache_free(&cache_cache, cachep);
        cachep = NULL;
        goto oops;
    }
    slab_size = ALIGN(cachep->num * sizeof(kmem_bufctl_t)
              + sizeof(struct slab), align);

    /*
     * If the slab has been placed off-slab, and we have enough space then
     * move it on-slab. This is at the expense of any extra colouring.
     */
    if (flags & CFLGS_OFF_SLAB && left_over >= slab_size) {
        flags &= ~CFLGS_OFF_SLAB;
        left_over -= slab_size;
    }

    if (flags & CFLGS_OFF_SLAB) {
        /* really off slab. No need for manual alignment */
        slab_size =
            cachep->num * sizeof(kmem_bufctl_t) + sizeof(struct slab);

#ifdef CONFIG_PAGE_POISONING
        /* If we're going to use the generic kernel_map_pages()
         * poisoning, then it's going to smash the contents of
         * the redzone and userword anyhow, so switch them off.
         */
        if (size % PAGE_SIZE == 0 && flags & SLAB_POISON)
            flags &= ~(SLAB_RED_ZONE | SLAB_STORE_USER);
#endif
    }

    cachep->colour_off = cache_line_size();
    /* Offset must be a multiple of the alignment. */
    if (cachep->colour_off < align)
        cachep->colour_off = align;
    cachep->colour = left_over / cachep->colour_off;
    cachep->slab_size = slab_size;
    cachep->flags = flags;
    cachep->gfpflags = 0;
    if (CONFIG_ZONE_DMA_FLAG && (flags & SLAB_CACHE_DMA))
        cachep->gfpflags |= GFP_DMA;
    cachep->buffer_size = size;
    cachep->reciprocal_buffer_size = reciprocal_value(size);

    if (flags & CFLGS_OFF_SLAB) {
        cachep->slabp_cache = kmem_find_general_cachep(slab_size, 0u);
        /*
         * This is a possibility for one of the malloc_sizes caches.
         * But since we go off slab only for object size greater than
         * PAGE_SIZE/8, and malloc_sizes gets created in ascending order,
         * this should not happen at all.
         * But leave a BUG_ON for some lucky dude.
         */
        BUG_ON(ZERO_OR_NULL_PTR(cachep->slabp_cache));
    }
    cachep->ctor = ctor;
    cachep->name = name;

    if (setup_cpu_cache(cachep, gfp)) {
        __kmem_cache_destroy(cachep);
        cachep = NULL;
        goto oops;
    }

    /* 
    cache setup completed, link it into the list 
    为完成初始化，将初始化过的kmem_cache实例添加到全局链表，表头为cache_chain

    */
    list_add(&cachep->next, &cache_chain);
oops:
    if (!cachep && (flags & SLAB_PANIC))
        panic("kmem_cache_create(): failed to create slab `%s'\n",
              name);
    if (slab_is_available()) {
        mutex_unlock(&cache_chain_mutex);
        put_online_cpus();
    }
    return cachep;
}
EXPORT_SYMBOL(kmem_cache_create);

/*
1. cachep: 用于获取对象的缓存
2. flags: 精确描述分配特征的标志变量
*/
void *kmem_cache_alloc(struct kmem_cache *cachep, gfp_t flags)

1. 依次扫描slabs_free链表上的slab，首先对每个slab的每个对象调用析构器函数，然后将slab的内存空间返回给伙伴系统
2. 释放用于per-CPU缓存的内存空间
3. 从cache_cache链表移除相关数据

/* Size description struct for general caches. */
struct cache_sizes 
{
    //cs_size指定了该项负责的内存区的长度，每个长度对应于两个SLAB缓存，其中之一提供适合DMA访问的内存
    size_t             cs_size;
    struct kmem_cache    *cs_cachep;
#ifdef CONFIG_ZONE_DMA
    struct kmem_cache    *cs_dmacachep;
#endif
};

/*
 * These are the default caches for kmalloc. Custom caches can have other sizes.
 */
struct cache_sizes malloc_sizes[] = 
{
#define CACHE(x) { .cs_size = (x) },
#include <linux/kmalloc_sizes.h>
    CACHE(ULONG_MAX)
#undef CACHE
};
EXPORT_SYMBOL(malloc_sizes);

/**
 * kfree - free previously allocated memory
 * @objp: pointer returned by kmalloc.
 *
 * If @objp is NULL, no operation is performed.
 *
 * Don't free memory not originally allocated by kmalloc()
 * or you will run into trouble.
 */
void kfree(const void *objp)
{
    struct kmem_cache *c;
    unsigned long flags;

    trace_kfree(_RET_IP_, objp);

    if (unlikely(ZERO_OR_NULL_PTR(objp)))
        return;
    local_irq_save(flags);
    kfree_debugcheck(objp);
    c = virt_to_cache(objp);
    debug_check_no_locks_freed(objp, obj_size(c));
    debug_check_no_obj_freed(objp, obj_size(c));
    __cache_free(c, (void *)objp);
    local_irq_restore(flags);
}
EXPORT_SYMBOL(kfree);

1. TLB的语义抽象是将虚拟地址转换为物理地址的一种机制
2. 内核将高速缓存视为通过虚拟地址快速访问数据的一种机制，该机制无需访问物理内存，数据和指令高速缓存并不总是明确区分，如果高速缓存区分数据和指令，那么特定于体系结构的代码负责对此进行处理

1. flush_tlb_all、flush_cache_all
刷出整个TLB/高速缓存，这只在操纵内核(而非用户空间进程的)页表时需要，因为此类修改不仅影响所有进程，而且影响系统中的所有处理器

2. flush_tlb_mm(struct mm_struct * mm)、flush_cache_mm
刷出所有属于地址空间mm的TLB/高速缓存项

3. flush_tlb_range(struct vm_area_struct * vma, unsigned long start, unsigned long end)、flush_cache_range(vma, start, end)
刷出地址范围vma->vm_mm中虚拟地址start、end之间的所有TLB/高速缓存项

4. flush_tlb_page(struct vm_area_struct * vma, unsigned long page)、flush_cache_page(vma, page)
刷出虚拟地址在[page, page + PAGE_SIZE]范围内所有的TLB/高速缓存项

5. update_mmu_cache(struct vm_area_struct * vma, unsigned long address, pte_t pte)
在处理页失效之后调用，它在处理器的内存管理单元MMU中加入信息，使得虚拟地址address由页表项pte描述。仅当存在外部MMU时，才需要该函数，通常MMU集成在处理器内部，但有例外情况，例如MIPS处理器具有外部MMU

//1. 刷出高速缓存
flush_cache_mm(oldmm);
...
//操作页表(操作内存)
...
//3. 刷出TLB
flush_tlb_mm(oldmm);

1. 如果顺序反过来，那么在TLB刷出之后，正确信息提供之前，多处理器系统中的另一个CPU可能从进程的页表取得错误的信息
2. 在刷出高速缓存时，某些体系结构需要依赖TLB中的"虚拟->物理"转换规则(具有该性质的高速缓存称之为严格的)。flush_tlb_mm必须在flush_cache_mm之后执行，以确保这一点

1. 如果高速缓存包含几个虚拟地址不同的项指向内存中的同一页，可能会发生所谓的alias问题，flush_dcache_page(struct page * page)有助于防止该问题。在内核向页缓存中的一页写入数据，或者从映射在用户空间中的一页读出数据时，总是会调用该函数，这个例程使得存在alias问题的各个体系结构有机会防止问题的发生

2. 在内核向内核内存范围(start、end之间)写入数据，而该数据将在此后作为代码执行，则此时需要调用flush_icache_range(unsigned long start, unsigned long end)。该场景的一个标准示例是向内核载入模块时，二进制数据首先复制到物理内存中，然后执行。
flush_icache_range确保在数据和指令高速缓存分别实现的情况下，二者彼此不发生干扰

3. flush_icache_user_range(*vma, *page, addr, len)是一个特殊的函数，用于ptrace机制
为了将修改传送到被调试进程的地址空间，需要使用该函数

1. 在内核进入正常运作之后，内存管理分为两个层次处理。伙伴系统负责物理页帧的管理，而SLAB分配器则处理小块内存的分配，并提供了用户层malloc函数族的内核等价物
2. 伙伴系统围绕着由多页组成的连续内存块的拆分和再合并而展开，在连续内存区变为空闲时，内核会自动注意到这一点，并在相应的分配请求出现时使用它，由于该机制在系统长时间运行后，无法以令人满意的方式防止物理内存碎片发生，因此2.6之后的内核版本引入了反碎片技术，它一方面允许按页的可移动性将其分组，另一方面增加了一个新的虚拟内存域。二者的实质都在于降低在大块内存中间分配内存的几率(这是导致碎片的根本原因)，以避免碎片出现
3. SLAB分配器在伙伴系统之上实现，它不仅允许分配任意用途的小块内存，还用于对经常使用的数据结构创建特定的缓存

1. 内存空间的分配与回收：
由操作系统完成主存储器空间的分配和管理，使程序员摆脱存储分配的麻烦，提高编程效率

2. 地址转换：
在多道程序环境下，程序中的逻辑地址与内存中的物理地址不可能一致，因此存储管理必须提供地址变换功能，把逻辑地址转换成相应的物理地址

3. 内存空间的扩充：
利用虚拟存储技术或自动覆盖技术，从逻辑上扩充内存

4. 存储保护：
保证各道作业在各自的存储空间内运行，互不干扰

http://see.xidian.edu.cn/cpp/html/2608.html

覆盖的基本思想是：由于程序运行时并非任何时候都要访问程序及数据的各个部分(尤其是大程序)，因此可以把用户空间分成一个固定区和若干个覆盖区。将经常活跃的部分放在固定区，其余部分按调用关系分段。首先将那些即将要访问的
段放入覆盖区，其他段放在外存中，在需要调用前，系统再将其调入覆盖区，替换覆盖区中原有的段。

交换(对换)的基本思想是：
1. 把处于等待状态(或在CPU调度原则下被剥夺运行权利)的程序从内存移到辅存，把内存空间腾出来，这一过程又叫换出
2. 把准备好竞争CPU运行的程序从辅存移到内存，这一过程又称为换入 

1. 交换需要备份存储，通常是快速磁盘。它必须足够大，并且提供对这些内存映像的直接访问。
2. 为了有效使用CPU，需要每个进程的执行时间比交换时间长，而影响交换时间的主要是转移时间。转移时间与所交换的内存空间成正比。
3. 如果换出进程，必须确保该进程是完全处于空闲状态。
4. 交换空间通常作为磁盘的一整块，且独立于文件系统，因此使用就可能很快。
5. 交换通常在有许多进程运行且内存空间吃紧时开始启动，而系统负荷降低就暂停。
6. 普通的交换使用不多，但交换策略的某些变种在许多系统中(如UNIX系统)仍发挥作用。

http://see.xidian.edu.cn/cpp/html/2609.html

http://see.xidian.edu.cn/cpp/html/2610.html

http://see.xidian.edu.cn/cpp/html/2611.html

http://see.xidian.edu.cn/cpp/html/2612.html

http://see.xidian.edu.cn/cpp/html/2613.html

7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

1. 先将7, 0, 1三个页面依次装入内存
2. 进程要访问页面2时，产生缺页中断，根据最佳置换算法，选择第18次访问才需调入的页面7予以淘汰
3. 然后，访问页面0时，因为已在内存中所以不必产生缺页中断
4. 访问页面3时又会根据最佳置换算法将页面1淘汰
5. ……依此类推 

LRU算法的思想是：选择最近最长时间未访问过的页面予以淘汰，它认为过去一段时间内未访问过的页面，在最近的将来可能也不会被访问。

1. 用一个链表、或者具有链表特征的数据结构来保存数据，取数据时只从头部取，插入数据的时候只从尾部插入，这样，每次数据被使用后就会从头部取出，并插入尾部。这种策略隐含的思想就是越尾部的数据就是越最近被使用的，
头部的都是不经常被使用的

2. 为每个页面设置一个访问字段，来记录页面自上次被访问以来所经历的时间，淘汰页面时选择现有页面中值最大的予以淘汰。