Linux malloc内存分配实现原理

一、内存管理框架

malloc是内存管理框架中的一环，提供给用户进程分配虚拟内存。

2、内存空间布局

2.1 虚拟内存空间布局

以Linux 64位系统为例。理论上，64bit内存地址可寻址空间为0x0000000000000000 ~ 0xFFFFFFFFFFFFFFFF，这是个相当庞大的地址空间，Linux实际上只用了其中一小部分（256T）。Linux64位操作系统仅使用低47位，高17位做扩展（全0或全1）。因此，实际用到的地址为空间为0x0000000000000000 ~ 0x00007FFFFFFFFFFF和0xFFFF800000000000 ~ 0xFFFFFFFFFFFFFFFF，其中前者为用户空间（User Space），后者为内核空间（Kernel Space）。

同理，32位的系统，0x00000000 ~ 0xBFFFFFFF为用户空间地址(3G)，0xC0000000 ~ 0xFFFFFFFF为内核空间地址(1G)。

64位和32位的内存布局，如下：

用户空间的内存空间通常包括以下几个部分，每个部分用于存放不同类型的数据：

• Text（代码段）

存放程序的机器指令（即编译后的代码）。这部分内存是只读的，包含程序的执行代码。

• Data（数据段）

存放已初始化的全局变量和静态变量。这些变量在程序启动时就已经有了初始值。

• BSS（Block Started by Symbol）段

存放未初始化的全局变量和静态变量。这些变量在程序启动时默认初始化为零或空。

• Heap（堆）

用于动态内存分配，如通过 malloc、calloc、realloc等函数分配的内存。堆的大小可以通过 brk或 sbrk系统调用进行调整。

• Stack（栈）

用于存放局部变量、函数调用的参数和返回地址。栈是后进先出（LIFO）的数据结构，用于管理函数调用和返回。

mmap（内存映射区域）：

用于内存映射文件、共享库、匿名映射等。通过 mmap系统调用，可以将文件或其他对象映射到进程的地址空间。

• 保留区

保留区是一些未明确分配用途的虚拟地址空间，这些区域可能用于未来的扩展或其他特殊用途。

由上图可以看出，进程的虚拟地址空间，由多个虚拟内存区域构成。虚拟内存区域是进程的虚拟地址空间中的一个同质区间，即具有同样特性的连续地址范围。上图中所示的text数据段、Data段、Bss数据段、堆、栈、mmap区域，都是一个独立的虚拟内存区域。linux 内核使用的vm_area_struct 结构来表示一个独立的虚拟内存区域，由于每个不同质的虚拟内存区域功能和内部机制不同；因此同一个进程使用多个vm_area_struct 结构来分别表示不同类型的虚拟内存区域。各个vm_area_struct 结构使用链表或者树形结构链接，方便进程快速访问。如下图所示：

2.2 物理内存布局

• ZONE_DMA

用途：这个区域包含适合进行直接内存访问（DMA）操作的内存页。DMA操作通常需要物理连续的内存，并且这些内存不能太远离某些特定的地址范围。

特点：通常这个区域的内存位于物理地址空间的较低部分，大小有限。

• ZONE_NOEMAL

用途：这个区域包含可以直接映射到内核线性地址空间的内存页。在32位系统中，这部分内存通常位于1GB以下的物理地址空间。

特点：内核可以直接访问这个区域的内存，无需复杂的地址转换。

• ZONE_HIGHMEM

用途：这个区域包含不能直接映射到内核线性地址空间的内存页。在32位系统中，由于内核线性地址空间有限（通常是1GB），超过这个范围的物理内存需要通过特殊的方式（如页表映射）才能被内核访问。

特点：在64位系统中，由于地址空间非常充裕，通常不存在zone_highmem。

• ZONE_MOVABEL

用途：这个区域是为了减少内存碎片而引入的。它包含可以被迁移的内存页，主要用于用户空间的内存分配。通过将可迁移的内存页集中在这个区域，可以减少因内存碎片导致的内存分配失败。

特点：这个区域的内存页可以通过内存热插拔（hotplug）和内存迁移（migration）机制进行管理。

3、malloc工作原理

了解了内存管理框架、虚拟内存与物理内存的结构布局后，可以更加深入的理解malloc工作原理。

3.1 malloc实现流程

malloc 实现通常会使用 brk 或 mmap 系统调用来向内核请求内存。

对于小块内存(<= 128kB)分配，malloc 通常使用 brk 系统调用扩展数据段。

对于大块内存(> 128kB)分配，malloc 通常使用 mmap 系统调用创建新的匿名映射。

最终通过伙伴系统分配物理内存。

3.1.1 brk方式申请内存

如果用户分配的内存小于或等于 128 KB，通过 brk() 申请内存。brk()的实现方式很简单，就是通过 brk() 函数将堆顶指针向高地址移动，获得新的内存空间。使用brk()分配了一段新的虚拟内存区域，但这并不会立即分配物理内存。实际的物理内存分配通常是在访问新分配的虚拟内存区域时，如果发生了缺页异常（Page Fault），操作系统才会开始分配并映射相应的物理内存页面。如下所示：

malloc 通过 brk() 方式申请的内存，free 释放内存的时候，并不一定会把内存归还给操作系统，而是缓存在 malloc 的内存池中，待下次使用，这样就可以重复使用。

brk()系统调用的优点：

可以减少缺页异常的发生，提高内存访问效率。

brk()系统调用的缺点：

由于申请的内存没有归还系统，在内存工作繁忙时，频繁的内存分配和释放会造成内存碎片。brk()方式之所以会产生内存碎片，是由于brk通过移动堆顶的位置来分配内存，并且使用完不会立即归还系统，重复使用，如果高地址的内存不释放，低地址的内存是得不到释放的。

正是由于使用brk()会出现内存碎片，所以在申请大块内存的时候才会使用mmap()方式，mmap()是以页为单位进行内存分配和管理的，释放后就直接归还系统了，所以不会出现这种小碎片的情况。

3.1.2 mmap方式分配内存

mmap是在进程的虚拟地址空间中的文件映射区域找一块空闲的虚拟内存，内存分配器通常使用这个系统调用来创建私有匿名映射，以分配内存，但不会立即分配物理内存。

实现这样的映射关系后，进程就可以采用指针的方式读写操作这一段内存，而系统会自动回写脏页面到对应的文件磁盘上，即完成了对文件的操作而不必调用read,write等系统调用函数。相反，内核空间的这段区域的修改也直接反映用户空间，从而可以实现不同进程的文件共享。如下：

3.2 核心代码

• brk

用户程序通过malloc进行内存分配会系统调用brk

SYSCALL_DEFINE1(brk, unsigned long, brk)
{
    unsigned long newbrk, oldbrk, origbrk;
    struct mm_struct *mm = current->mm;
    struct vm_area_struct *brkvma, *next = NULL;
    unsigned long min_brk;
    bool populate;
    bool downgraded = false;
    LIST_HEAD(uf);
    MA_STATE(mas, &mm->mm_mt, 0, 0);

    if (mmap_write_lock_killable(mm))
        return -EINTR;

    origbrk = mm->brk;

#ifdef CONFIG_COMPAT_BRK
    /*
     * CONFIG_COMPAT_BRK can still be overridden by setting
     * randomize_va_space to 2, which will still cause mm->start_brk
     * to be arbitrarily shifted
     */
    if (current->brk_randomized)
        min_brk = mm->start_brk;
    else
        min_brk = mm->end_data;
#else
    min_brk = mm->start_brk;
#endif
    if (brk < min_brk)
        goto out;

    /*
     * Check against rlimit here. If this check is done later after the test
     * of oldbrk with newbrk then it can escape the test and let the data
     * segment grow beyond its set limit the in case where the limit is
     * not page aligned -Ram Gupta
     */
    if (check_data_rlimit(rlimit(RLIMIT_DATA), brk, mm->start_brk,
                  mm->end_data, mm->start_data))
        goto out;

    newbrk = PAGE_ALIGN(brk);
    oldbrk = PAGE_ALIGN(mm->brk);
    if (oldbrk == newbrk) {
        mm->brk = brk;
        goto success;
    }

    /*
     * Always allow shrinking brk.
     * do_brk_munmap() may downgrade mmap_lock to read.
     */
    if (brk <= mm->brk) {
        int ret;

        /* Search one past newbrk */
        mas_set(&mas, newbrk);
        brkvma = mas_find(&mas, oldbrk);
        if (!brkvma || brkvma->vm_start >= oldbrk)
            goto out; /* mapping intersects with an existing non-brk vma. */
        /*
         * mm->brk must be protected by write mmap_lock.
         * do_brk_munmap() may downgrade the lock,  so update it
         * before calling do_brk_munmap().
         */
        mm->brk = brk;
        ret = do_brk_munmap(&mas, brkvma, newbrk, oldbrk, &uf);
        if (ret == 1)  {
            downgraded = true;
            goto success;
        } else if (!ret)
            goto success;

        mm->brk = origbrk;
        goto out;
    }

    if (check_brk_limits(oldbrk, newbrk - oldbrk))
        goto out;

    /*
     * Only check if the next VMA is within the stack_guard_gap of the
     * expansion area
     */
    mas_set(&mas, oldbrk);
    next = mas_find(&mas, newbrk - 1 + PAGE_SIZE + stack_guard_gap);
    if (next) {
        vma_start_write(next);
        if (newbrk + PAGE_SIZE > vm_start_gap(next))
            goto out;
    }

    brkvma = mas_prev(&mas, mm->start_brk);
    /* Ok, looks good - let it rip. */
    if (do_brk_flags(&mas, brkvma, oldbrk, newbrk - oldbrk, 0) < 0)
        goto out;

    mm->brk = brk;

success:
    // 如果标记有VM_LOCKED的flag，立刻进行物理内存分配
    populate = newbrk > oldbrk && (mm->def_flags & VM_LOCKED) != 0;
    if (downgraded)
        mmap_read_unlock(mm);
    else
        mmap_write_unlock(mm);
    userfaultfd_unmap_complete(mm, &uf);
    if (populate)
        mm_populate(oldbrk, newbrk - oldbrk);
    return brk;

out:
    mmap_write_unlock(mm);
    return origbrk;
}

进程的堆边界：指进程虚拟地址空间中堆区域的结束地址，可动态调整。

内存动态分配：应用程序调用 malloc等函数请求内存时，如果当前堆空间不足，操作系统会通过调整堆边界来分配更多的内存。相反，当调用 free函数释放内存时，堆边界通常不会立即调整，而是由内存管理器在后续的内存分配请求中决定是否收缩堆。

• do_brk_flags

根据给定的地址和长度，扩展或创建一个新的虚拟内存区域（VMA），并将其添加到当前进程的内存管理结构中。

static int do_brk_flags(struct ma_state *mas, struct vm_area_struct *vma,
        unsigned long addr, unsigned long len, unsigned long flags)
{
    struct mm_struct *mm = current->mm;

    validate_mm_mt(mm);
    /*
     * Check against address space limits by the changed size
     * Note: This happens *after* clearing old mappings in some code paths.
     */
    flags |= VM_DATA_DEFAULT_FLAGS | VM_ACCOUNT | mm->def_flags;
    if (!may_expand_vm(mm, flags, len >> PAGE_SHIFT))
        return -ENOMEM;

    if (mm->map_count > sysctl_max_map_count)
        return -ENOMEM;

    if (security_vm_enough_memory_mm(mm, len >> PAGE_SHIFT))
        return -ENOMEM;

    if (vma)
        vma_start_write(vma);
    /*
     * Expand the existing vma if possible; Note that singular lists do not
     * occur after forking, so the expand will only happen on new VMAs.
     */
    if (vma && vma->vm_end == addr && !vma_policy(vma) &&
        can_vma_merge_after(vma, flags, NULL, NULL,
                addr >> PAGE_SHIFT, NULL_VM_UFFD_CTX, NULL)) {
        mas_set_range(mas, vma->vm_start, addr + len - 1);
        if (mas_preallocate(mas, vma, GFP_KERNEL))
            return -ENOMEM;

        /* Set flags first to implicitly lock the VMA before updates */
        vm_flags_set(vma, VM_SOFTDIRTY);
        vma_adjust_trans_huge(vma, vma->vm_start, addr + len, 0);
        if (vma->anon_vma) {
            anon_vma_lock_write(vma->anon_vma);
            anon_vma_interval_tree_pre_update_vma(vma);
        }
        vma->vm_end = addr + len;
        mas_store_prealloc(mas, vma);

        if (vma->anon_vma) {
            anon_vma_interval_tree_post_update_vma(vma);
            anon_vma_unlock_write(vma->anon_vma);
        }
        khugepaged_enter_vma(vma, flags);
        goto out;
    }

    /* create a vma struct for an anonymous mapping */
    // 创建一个新的VMA
    vma = vm_area_alloc(mm);
    if (!vma)
        goto vma_alloc_fail;

    vma_set_anonymous(vma);
    vma->vm_start = addr;
    vma->vm_end = addr + len;
    vma->vm_pgoff = addr >> PAGE_SHIFT;
    vm_flags_init(vma, flags);
    vma->vm_page_prot = vm_get_page_prot(flags);
    vma_start_write(vma);
    mas_set_range(mas, vma->vm_start, addr + len - 1);
    // 新的VMA（虚拟内存区域）添加到当前进程的内存管理结构
    if (mas_store_gfp(mas, vma, GFP_KERNEL))
        goto mas_store_fail;

    mm->map_count++;
out:
    perf_event_mmap(vma);
    mm->total_vm += len >> PAGE_SHIFT;
    mm->data_vm += len >> PAGE_SHIFT;
    if (flags & VM_LOCKED)
        mm->locked_vm += (len >> PAGE_SHIFT);
    vm_flags_set(vma, VM_SOFTDIRTY);
    validate_mm(mm);
    return 0;

mas_store_fail:
    vm_area_free(vma);
vma_alloc_fail:
    vm_unacct_memory(len >> PAGE_SHIFT);
    return -ENOMEM;
}

• mm_populate

为VMA分配物理内存。

int __mm_populate(unsigned long start, unsigned long len, int ignore_errors)
{
    ...
    // 查询VMA
    vma = find_vma_intersection(mm, nstart, end);
    ...
    ret = populate_vma_page_range(vma, nstart, nend, &locked);
   ...
        return ret; 
}

long populate_vma_page_range(struct vm_area_struct *vma,
                unsigned long start, unsigned long end, int *locked)
{
        struct mm_struct *mm = vma->vm_mm;
        unsigned long nr_pages = (end - start) / PAGE_SIZE;
        int gup_flags;
        long ret;
        ...
        
        ret = __get_user_pages(mm, start, nr_pages, gup_flags,
                                NULL, NULL, locked);
        lru_add_drain();
        return ret;
}

static long __get_user_pages(struct mm_struct *mm,
                unsigned long start, unsigned long nr_pages,
                unsigned int gup_flags, struct page **pages,
                struct vm_area_struct **vmas, int *locked)
{
        long ret = 0, i = 0;
        struct vm_area_struct *vma = NULL;
        struct follow_page_context ctx = { NULL };
        ...
     
        page = follow_page_mask(vma, start, foll_flags, &ctx);
        if (!page || PTR_ERR(page) == -EMLINK) {
                // 缺页异常处理
                ret = faultin_page(vma, start, &foll_flags,
                                   PTR_ERR(page) == -EMLINK, locked);
                ...
         }             
        return i ? i : ret;
}

这块代码量较大，有兴趣可以自己跟读后续的代码。

3.3 malloc分配物理内存的时机

触发缺页异常，会去分配物理内存。

3.4 malloc分配的实际内存大小

如果malloc通过mmap系统调用，最终通过linux伙伴系统（以页为单位）分配器进行物理内存分配，申请的内存4KB，一律分配4KB.

四、虚拟内存与物理内存

4.1 如何建立映射

虚拟内存和物理内存建立映射的关键步骤：

1） 页表的创建

当一个进程被创建时，操作系统会为该进程分配一个页表。页表的初始状态通常是空的，因为此时进程的虚拟地址空间还没有与物理内存建立任何映射。

2）页表条目的填充

随着进程的运行，操作系统会根据需要将虚拟页映射到物理页框。这通常发生在以下几种情况：

• 进程首次访问某个虚拟地址时，如果对应的虚拟页还没有映射到物理内存，会发生缺页异常，操作系统会处理这个异常，将所需的页从磁盘加载到物理内存，并更新页表。

• 操作系统主动为进程分配内存时，例如通过 malloc 或 mmap 等系统调用，操作系统会在物理内存中找到可用的页框，并更新页表，建立虚拟页到物理页框的映射。

3）页表的维护

操作系统需要持续地维护页表，确保虚拟地址空间和物理内存之间的映射是正确的。这包括在内存不足时进行页面置换（将不常用的页写回磁盘，释放物理页框），以及在进程结束时清理页表，释放相关的物理内存。

4）页表的更新

当物理内存中的页框发生变化时（例如，由于页面置换或内存回收），操作系统需要更新相关的页表条目，以反映最新的映射关系。

总结来说，虚拟内存和物理内存之间的映射是通过页表的创建、填充、维护和更新来建立和管理的。

两个进程分别malloc 20个字节的内存，即使虚拟地址空间一致，但由于映射方式不一样，对应的物理内存地址页不一致。如下：

4.2 分配物理内存

分配物理内存的基本步骤：

1）虚拟内存分配

当应用程序调用 malloc 或其他内存分配函数时，操作系统会在进程的虚拟地址空间中分配一块内存。

2）缺页异常

当进程首次尝试访问新分配的虚拟内存时，由于这块内存尚未映射到物理内存，会发生缺页异常。

3）物理内存分配

内核在处理缺页异常时，会检查是否有可用的物理内存页。如果有可用页，内核会通过伙伴系统或其他内存分配机制分配一个物理内存页。

4）建立映射

内核随后会将这个新分配的物理内存页映射到发生缺页异常的虚拟地址，并更新页表以反映这种映射关系。

一旦映射建立完成，进程就可以访问刚刚分配的内存。

4.3 物理内存访问

一旦虚拟内存与物理内存之间的映射建立完成，进程访问这块物理内存的过程是通过CPU的内存管理单元（MMU）和页表自动完成的。以下是进程访问物理内存的具体步骤：

1）虚拟地址生成

当进程中的指令需要访问内存时，它会生成一个虚拟地址。这个虚拟地址是进程在其虚拟地址空间中看到的地址。

2）虚拟地址到物理地址的转换

CPU中的MMU负责将虚拟地址转换为物理地址。MMU使用进程的页表来进行这种转换。页表中包含了虚拟页号到物理页帧号的映射信息。

3）物理地址计算

MMU首先查找虚拟地址的页表条目。如果页表条目中的present bit（存在位）被设置，表示该虚拟页已经映射到了物理内存中。如果在页表查找过程中发现present bit没有被设置，这意味着对应的虚拟页当前不在物理内存中，MMU会产生一个缺页异常。内核会处理这个异常，可能会从磁盘上的交换空间加载缺失的页，并更新页表和TLB。

MMU使用页表条目中的物理页帧号和虚拟地址中的页内偏移量来计算出最终的物理地址。

为了加速虚拟地址到物理地址的转换，CPU通常有一个TLB（Translation Lookaside Buffer），它是一个小型的硬件缓存，存储了最近使用的虚拟页到物理页的映射。如果TLB中有所需的映射，MMU可以直接从TLB中获取物理地址，而不需要访问页表，这样可以显著提高内存访问速度。

4）内存访问

计算出物理地址，CPU就可以直接访问物理内存中的数据。这个访问可以是读取操作，也可以是写入操作，具体取决于进程的指令。

整个过程对进程来说是透明的，进程只需要使用虚拟地址，而不需要知道物理内存的具体位置。内核和MMU共同确保了进程能够正确地访问其请求的内存。

五、new和malloc区别与联系

new分配内存：

int *p;
p = new int; //返回类型为int *类型，分配的大小为sizeof(int)
p = new int[100]; //返回类型为int *类型，分配的大小为sizeof(int) * 100

malloc分配内存：

int *p;
p = (int *)malloc(sizeof(int));

主要区别有3点：

1）new返回指定类型的指针，并且可以自动计算所需要的大小；而malloc则必须由我们计算字节数，并且在返回的是void*，需强转成实际指定类型的指针

2）malloc的实参是sizeof(int),用于指明一个整形数据需要的大小，如果我们写成p = （int *）malloc(1), 只是申请了一个字节的空间，如果向里面存放了一个整数的话，将会占用额外的3个字节，可能会改变原有内存空间中的数据

3）malloc只管分配内存，并不能对其进行初始化，所以得到的一片新内存中，其值将是随机的，可以用memset将其初始化为0