Linux 内存管理

1 页的概念

linux 内核中把物理页作为内存分配的最小单位，32位CPU 页的大小通常为4K，64位的CPU通常支持8K的也。内存管理单元MMU 同样以页为大小分配内存。

2 内核虚拟地址分区和物理内存分区

在32位内核中，内核虚拟地址空间为0-4G，其中用户态为1-3G空间，内核态为3G-4G，内核空间根据物理地址的特性大概可以分为三个区：

下面的图描述了内核地址空间和物理内存的映射关系：

32位 内核内存分区

Linux 内核启动后的mm 的初始化过程：

/*
 * Set up kernel memory allocators
 */
static void __init mm_init(void)
{
    /*
     * page_ext requires contiguous pages,
     * bigger than MAX_ORDER unless SPARSEMEM.
     */
    page_ext_init_flatmem();
    mem_init();
    kmem_cache_init();
    percpu_init_late();
    pgtable_init();
    vmalloc_init();
    ioremap_huge_init();
}

3伙伴系统算法

3.1 简介

在实际应用中，经常需要分配一组连续的页，而频繁地申请和释放不同大小的连续页，必然导致在已分配页框的内存块中分散了许多小块的空闲页框。这样，即使这些页框是空闲的，其他需要分配连续页框的应用也很难得到满足。为了避免出现这种情况，Linux内核中引入了伙伴系统算法(buddy system)。把所有的空闲页框分组为11个块链表，每个块链表分别包含大小为1，2，4，8，16，32，64，128，256，512和1024个连续页框的页框块。最大可以申请1024个连续页框，对应4MB大小的连续内存。每个页框块的第一个页框的物理地址是该块大小的整数倍。

假设要申请一个256个页框的块，先从256个页框的链表中查找空闲块，如果没有，就去512个页框的链表中找，找到了则将页框块分为2个256个页框的块，一个分配给应用，另外一个移到256个页框的链表中。如果512个页框的链表中仍没有空闲块，继续向1024个页框的链表查找，如果仍然没有，则返回错误。页框块在释放时，会主动将两个连续的页框块合并为一个较大的页框块。

mem_init() 函数中会把内核启动后的空闲内存用buddy 系统管理。

参考：mem_init bootmem 迁移至伙伴系统

3.2 伙伴系统算法分配函数

mem_init 初始化完伙伴系统后通过 alloc_page(s) 函数分配伙伴系统内存池的内存。

3.3 get_free_page(s)与alloc_page(s)的差异

alloc_page alloc_pages 分配后还不能直接使用， 需要得到该页对应的虚拟地址

• void *page_address(struct page *page);
• 低端内存的映射方式：__va((unsigned long)(page - mem_map) << 12)
• 高端内存到映射方式：struct page_address_map分配一个动态结构来管理高端内存。(内核是访问不到vma的3G以下的虚拟地址的) 具体映射由kmap / kmap_atomic执行。

get_free_page(s)与alloc_page(s)系列最大的区别是无法申请高端内存，因为它返回到是一个逻辑地址，而高端内存是需要额外映射才可以

Android x86 的buffyinfo.
以Normal区域进行分析，第二列值为459，表示当前系统中normal区域，可用的连续两页的内存大小为459*2^1*PAGE_SIZE；第三列值为52，表示当前系统中normal区域，可用的连续四页的内存大小为52*2^2*PAGE_SIZE

generic_x86:/ # cat /proc/buddyinfo
Node 0, zone      DMA      4      1      2      2      3      2      3      1      2      0      1
Node 0, zone   Normal   1186    459    220    142     25     13      2      0      1      2    138
Node 0, zone  HighMem     87     74     12      9      0      1      1      0      0      0      0

4 Slab 内存分配算法

Slab 内存分配算法 和Java中的对象池是一个概念。采用buddy算法，解决了外碎片问题，这种方法适合大块内存请求，不适合小内存区请求

4.1 Slab 内存分配算法

slab分配器源于 Solaris 2.4 的分配算法，工作于物理内存页框分配器之上，管理特定大小对象的缓存，进行快速而高效的内存分配。slab分配器为每种使用的内核对象建立单独的缓冲区。Linux 内核已经采用了伙伴系统管理物理内存页框，因此 slab分配器直接工作于伙伴系统之上。每种缓冲区由多个 slab 组成，每个 slab就是一组连续的物理内存页框，被划分成了固定数目的对象。根据对象大小的不同，缺省情况下一个 slab 最多可以由 1024个页框构成。出于对齐等其它方面的要求，slab 中分配给对象的内存可能大于用户要求的对象实际大小，这会造成一定的内存浪费。

Linux 所使用的 slab 分配器的基础是 Jeff Bonwick 为SunOS 操作系统首次引入的一种算法。Jeff的分配器是围绕对象缓存进行的。在内核中，会为有限的对象集（例如文件描述符和其他常见结构）分配大量内存。Jeff发现对内核中普通对象进行初始化所需的时间超过了对其进行分配和释放所需的时间。因此他的结论是不应该将内存释放回一个全局的内存池，而是将内存保持为针对特定目而初始化的状态。例如，如果内存被分配给了一个互斥锁，那么只需在为互斥锁首次分配内存时执行一次互斥锁初始化函数（mutex_init）即可。后续的内存分配不需要执行这个初始化函数，因为从上次释放和调用析构之后，它已经处于所需的状态中了。

4.2 Slab 内存结构

kmem_cache_alloc 分配的所有的内存块在内核中以链表的形式组织。
kmem_cache_alloc 从buddy系统分配到内存后，在内部被分为 slab 单元，这是一段连续的内存块（通常都是页面）。所有的对象都分配在这些slab 单元上，这些slab 单元被组织为三个链表：

1. slabs_full 完全分配的 slab
2. slabs_partial 部分分配的 slab
3. slabs_free 可以回收的 slab

4.3 slab 着色区和slab 结构

每个Slab的首部都有一个小小的区域是不用的，称为“着色区（coloring area）”。着色区的大小使Slab中的每个对象的起始地址都按高速缓存中的”缓存行（cache line）”大小进行对齐（80386的一级高速缓存行大小为16字节，Pentium为32字节）。因为Slab是由1个页面或多个页面（最多为32）组成，因此，每个Slab都是从一个页面边界开始的，它自然按高速缓存的缓冲行对齐。但是，Slab中的对象大小不确定，设置着色区的目的就是将Slab中第一个对象的起始地址往后推到与缓冲行对齐的位置。每个Slab上最后一个对象以后也有个小小的区是不用的，这是对着色区大小的补偿，其大小取决于着色区的大小，以及Slab与其每个对象的相对大小。

slab 内存分配

4.4 Slab 内存函数

mm_init --> kmem_cache_init(); kernel 初始化

• kmem_cache_t* xx_cache; // 链表头
• 创建： xx_cache = kmem_cache_create("name", sizeof(struct xx), SLAB_HWCACHE_ALIGN, NULL, NULL);
• 分配： kmem_cache_alloc(xx_cache, GFP_KERNEL);
• 释放： kmem_cache_free(xx_cache, addr);
  slab 内存用结构体 kmem_cache_t 表示：

4.5 slabinfo对象

从 /proc/slabinfo 中看一看出，内核为大结构体使用了slab 缓存。如ext4_inode_cache vm_area_struct task_struct等。

generic_x86:/ # 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>
...
ext4_inode_cache    2025   2025    632   25    4 : tunables    0    0    0 : slabdata     81     81      0
ext4_allocation_context    156    156    104   39    1 : tunables    0    0    0 : slabdata      4      4      0
ext4_prealloc_space    224    224     72   56    1 : tunables    0    0    0 : slabdata      4      4      0
ext4_io_end          408    408     40  102    1 : tunables    0    0    0 : slabdata      4      4      0
ext4_extent_status   2048   2048     32  128    1 : tunables    0    0    0 : slabdata     16     16      0
...
vm_area_struct     20791  22402     88   46    1 : tunables    0    0    0 : slabdata    487    487      0
mm_struct             85     85    480   17    2 : tunables    0    0    0 : slabdata      5      5      0

...
task_struct          621    621   1184   27    8 : tunables    0    0    0 : slabdata     23     23      0
...
kmalloc-8192          28     28   8192    4    8 : tunables    0    0    0 : slabdata      7      7      0
kmalloc-4096          96    104   4096    8    8 : tunables    0    0    0 : slabdata     13     13      0
kmalloc-2048         128    128   2048   16    8 : tunables    0    0    0 : slabdata      8      8      0
kmalloc-1024         336    336   1024   16    4 : tunables    0    0    0 : slabdata     21     21      0
kmalloc-512          752    752    512   16    2 : tunables    0    0    0 : slabdata     47     47      0
kmalloc-256          698    752    256   16    1 : tunables    0    0    0 : slabdata     47     47      0
kmalloc-192          903    903    192   21    1 : tunables    0    0    0 : slabdata     43     43      0
kmalloc-128         1760   1760    128   32    1 : tunables    0    0    0 : slabdata     55     55      0
kmalloc-96          2100   2100     96   42    1 : tunables    0    0    0 : slabdata     50     50      0
kmalloc-64         14272  14272     64   64    1 : tunables    0    0    0 : slabdata    223    223      0
kmalloc-32         26182  28416     32  128    1 : tunables    0    0    0 : slabdata    222    222      0
kmalloc-16         15360  15360     16  256    1 : tunables    0    0    0 : slabdata     60     60      0
kmalloc-8           6656   6656      8  512    1 : tunables    0    0    0 : slabdata     13     13      0
kmem_cache_node      128    128     32  128    1 : tunables    0    0    0 : slabdata      1      1      0
kmem_cache           128    128    128   32    1 : tunables    0    0    0 : slabdata      4      4      0

5 kmalloc 和 vmalloc

5.1 kmalloc

从 4.5 节 /proc/slabinfo 对象也可以看出，kmalloc 的分配建立在 slab 内存对象池上。
在mm/slab_common.c 中 kmalloc 的分配定义如下：

// mm/slab_common.c
static struct {
    const char *name;
    unsigned long size;
} const kmalloc_info[] __initconst = {
    {NULL,                      0},     {"kmalloc-96",             96},
    {"kmalloc-192",           192},     {"kmalloc-8",               8},
    {"kmalloc-16",             16},     {"kmalloc-32",             32},
    {"kmalloc-64",             64},     {"kmalloc-128",           128},
    {"kmalloc-256",           256},     {"kmalloc-512",           512},
    {"kmalloc-1024",         1024},     {"kmalloc-2048",         2048},
    {"kmalloc-4096",         4096},     {"kmalloc-8192",         8192},
    {"kmalloc-16384",       16384},     {"kmalloc-32768",       32768},
    {"kmalloc-65536",       65536},     {"kmalloc-131072",     131072},
    {"kmalloc-262144",     262144},     {"kmalloc-524288",     524288},
    {"kmalloc-1048576",   1048576},     {"kmalloc-2097152",   2097152},
    {"kmalloc-4194304",   4194304},     {"kmalloc-8388608",   8388608},
    {"kmalloc-16777216", 16777216},     {"kmalloc-33554432", 33554432},
    {"kmalloc-67108864", 67108864}
};

kmalloc 获取的是以字节为单位的连续物理内存空间

5.2 gfp_t 结构体

// include/linux/slab.h 
void *kmalloc(size_t size, gfp_t flags)

在 alloc_page(s) get_free_page(s) kmalloc 函数的定义中 第二个参数类型为 gfp_t 类型；
gfp_t 标志有3类：(所有的 GFP 标志都在 <linux/gfp.h> 中定义)

1. 行为标志 ：控制分配内存时，分配器的一些行为
2. 区标志 ：控制内存分配在那个区(ZONE_DMA, ZONE_NORMAL, ZONE_HIGHMEM 之类)
3. 类型标志 ：由上面2种标志组合而成的一些常用的场景

区标志主要以下3种：

__GFP_HIGHMEM 优先从 ZONE_HIGHMEM 分配，如果 ZONE_HIGHMEM 没有多余的页则从 ZONE_NORMAL 分配

5.3 vmalloc

vmalloc 分配的内存和kmalloc 不同，vmalloc 在逻辑地址上是连续的，但是在物理地质上不一定连续。

/**
 *  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_flags(size, NUMA_NO_NODE,
                    GFP_KERNEL | __GFP_HIGHMEM);
}


static inline void *__vmalloc_node_flags(unsigned long size,
                    int node, gfp_t flags)
{
    return __vmalloc_node(size, 1, flags, PAGE_KERNEL,
                    node, __builtin_return_address(0));
}


void *__vmalloc_node_range(unsigned long size, unsigned long align,
            unsigned long start, unsigned long end, gfp_t gfp_mask,
            pgprot_t prot, unsigned long vm_flags, int node,
            const void *caller)
{
    struct vm_struct *area;
    void *addr;
    unsigned long real_size = size;

    size = PAGE_ALIGN(size);
    if (!size || (size >> PAGE_SHIFT) > totalram_pages)
        goto fail;

    area = __get_vm_area_node(size, align, VM_ALLOC | VM_UNINITIALIZED |
                vm_flags, start, end, node, gfp_mask, caller);
    if (!area)
        goto fail;

    addr = __vmalloc_area_node(area, gfp_mask, prot, node);
    if (!addr)
        return NULL;

    ......
}

static void *__vmalloc_area_node(struct vm_struct *area, gfp_t gfp_mask,
                 pgprot_t prot, int node)
{
    struct page **pages;
    unsigned int nr_pages, array_size, i;
    const gfp_t nested_gfp = (gfp_mask & GFP_RECLAIM_MASK) | __GFP_ZERO;
    const gfp_t alloc_mask = gfp_mask | __GFP_NOWARN;

    nr_pages = get_vm_area_size(area) >> PAGE_SHIFT;
    array_size = (nr_pages * sizeof(struct page *));

    area->nr_pages = nr_pages;
    /* Please note that the recursion is strictly bounded. */
    if (array_size > PAGE_SIZE) {
        pages = __vmalloc_node(array_size, 1, nested_gfp|__GFP_HIGHMEM,
                PAGE_KERNEL, node, area->caller);
    } else {
        pages = kmalloc_node(array_size, nested_gfp, node);
    }
    
    area->pages = pages;
    if (!area->pages) {
        remove_vm_area(area->addr);
        kfree(area);
        return NULL;
    }

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

        if (node == NUMA_NO_NODE)
            page = alloc_page(alloc_mask);
        else
            page = alloc_pages_node(node, alloc_mask, 0);

        if (unlikely(!page)) {
            /* Successfully allocated i pages, free them in __vunmap() */
            area->nr_pages = i;
            goto fail;
        }
        area->pages[i] = page;
        if (gfpflags_allow_blocking(gfp_mask))
            cond_resched();
    }
    ......

从vmalloc 函数的实现看 最终调用了alloc_page 系列函数实现 从伙伴分配系统中分配内存。所以所vmalloc 适用了大块非物理连续的内存分配。 __vmalloc_node_flags(size, NUMA_NO_NODE, GFP_KERNEL | __GFP_HIGHMEM) 函数中vmalloc 指定了从高端内存分配。

linux 内存分配结构

6 malloc

6.1 程序在内存中的地址

二进制程序通常分为text， Data， Bss， 区， 堆和栈。加载到内存后的内存镜像如图所示：

程序在内存中的地址

==图片来源于网络==

6.2 sbrk 系统调用 和 “program break" (程序间断点)

程序间断点在最开始指向堆区的起始位置，同时也是数据段的结尾。 malloc 分配内存后，指向分配的内存开始的位置。

linux 系统上malloc 的实现基于sbrk 系统调用。

p1 = sbrk(0);               //sbrk(0)返回当前的程序间断点
p = sbrk(1)                 //将堆区的大小加1，但是返回的是p1的位置

参考
如何实现一个malloc

内存的页映射

malloc 调用后，只是分配了内存的逻辑地址，在内核的mm_struct 链表中插入vm_area_struct结构体，没有分配实际的内存。当分配的区域写入数据是，引发页中断，建立物理页和逻辑地址的映射。下图表示了这个过程。

物理页的分配过程

在Android 上通过procrank 查看 Vss 和 Rss， Rss 总是小于Vss 就是这个原因。

generic_x86_64:/ # procrank
 PID       Vss      Rss      Pss      Uss  cmdline
1509  1077592K  117132K   66232K   57296K  system_server
1237   901952K   66596K   56300K   52884K  zygote
1623  1061168K   98892K   50847K   44164K  com.android.systemui
1236   916248K   78992K   29529K   20532K  zygote64
1780  1020240K   63484K   20138K   15684K  com.android.phone
2004  1014992K   66748K   20112K   14748K  com.android.launcher3

一般来说内存占用大小有如下规律：VSS >= RSS >= PSS >= USS
参考：
How the Kernel Manages Your Memory

部分内容来源于网络，没有一一注明