学习完了用户进程地址空间，那么从本章开始学习下用户空间的内存分配。对于我们来说，对是进程中用于动态分配变量和数据的内存区域，堆的管理对应用程序员来说是不可见的。因为它依赖于标准库提供的各种辅助函数(malloc)来分配任意长度的内存区。使用malloc，相对于栈空间而言，堆内存面临着更为复杂的情况。那么malloc在堆上分配内存到底是如何实现的呢？主要内容包括如下：
- 堆的内存怎么从内核中申请
- 怎么有效地进行堆内存管理
1. malloc简介
malloc函数使C/C++中常用内存分配库函数，使用malloc时，需包含头文件<stdlib.h>，函数原型如下
void* malloc(size_t size);
- 功能：分配长度为size的内存块，一般为系统堆上的可用内存上找到一块长度大于size的连续内存空间。如果分配成功，则返回指向分配内存的指针，否则返回空指针NULL。
- 返回值：类型为void *，表示未确定类型指针，它可以强制转换为任意其他类型的指针
- 当内存不再使用时，应用free函数将内存块释放。将之前malloc分配的空间还给操作系统，释放传入指针指向的那块内存区域。指针本身的数值没有变，释放后，指向的内容是垃圾内容，所以最好将这块内存的指针再指向NULL，防止后面的程序误用。
而对于进程的堆，并不是直接建立在Linux的内核的内存分配策略上的，而是建立在glibc的堆管理策略上的（也就是glibc的动态内存分配策略上），堆的管理是由glibc进行的。所以我们调用free对malloc得到的内存进行释放的时候，并不是直接释放给操作系统，而是还给了glibc的堆管理实体，而glibc会在把实际的物理内存归还给系统的策略上做一些优化，以便优化用户任务的动态内存分配过程。
malloc的调用规律（该过程可以通过系统调用接口strace命令跟踪)
- 即分配一块小型内存(小于或等于128kb)，malloc()会调用brk()调高断点(brk是将数据段(.data)的最高地址指针_edata往高地址推)，分配的内存在堆区域。
- 当分配一块大型内存(大于128kb),malloc()会调用mmap2()分配一块内存（mmap是在进程的虚拟地址空间中（一般是堆和栈中间）找一块空闲的空间。
小于128K的堆内存分配方式
- stack的内存地址是向下增长的，heap的内存地址是向上增长
- glibc对于heap内存申请大于128k的内存申请，glibc采用mmap的方式向内核申请内存，这不能保证内存地址向上增长；小于128k的则采用brk，对于它来讲是正确的。128k的阀值，可以通过glibc的库函数进行设置
1.1 brk
1，进程启动的时候，其（虚拟）内存空间的初始布局如图所示
2，进程调用A=malloc(30K)以后，，将_edata指针往高地址推30K，就完成虚拟内存分配，内存空间如图：
3，进程调用 free 以后，如下图所示，C对应的虚拟内存和物理内存都没有释放，因为只有一个 _edata 指针，如果往回推，那么 C 这块内存怎么办呢？当然，B 这块内存是可以重用的，如果这个时候再来一个 30K 的请求，那么 malloc 很可能就将 B 这块内存返回的。
4，进程调用 free(A) 以后，如下图所示，C 和 A 连接起来变成一块70K 的空闲内存。当最高地址空间的空闲内存超过128K（可由 M_TRIM_THRESHOLD 选项调节）时，执行内存紧缩操作（trim）。在上一个步骤 free 的时候，发现最高地址空闲内存超过128K，于是内存紧缩，如下图所示。
事实是：_edata+30K只是完成虚拟地址的分配，A这块内存现在还是没有物理页与之对应的，等到进程第一次读写A这块内存的时候，发生缺页中断，这个时候，内核才分配A这块内存对应的物理页。也就是说，如果用malloc分配了A这块内容，然后从来不访问它，那么，A对应的物理页是不会被分配的。
同时brk 分配的内存需要等到高地址内存释放以后才能释放（例如，在 C 释放之前，A 是不可能释放的，这就是内存碎片产生的原因），而 mmap 分配的内存可以单独释放。
1.2 mmap
使用mmap分配内存。在堆和栈之间找一块空闲内存分配（对应独立内存，而且初始化为0）
-
进程调用B=malloc(200K)以后，内存空间如图4 ，默认情况下，malloc函数分配内存，如果请求内存大于128K（可由M_MMAP_THRESHOLD选项调节），那就不是去推_edata指针了，而是利用mmap系统调用，从堆和栈的中间分配一块虚拟内存。
-
进程调用free(B)以后，B对应的虚拟内存和物理内存一起释放
默认情况下，malloc函数分配内存，如果请求内存大于128K（可由M_MMAP_THRESHOLD选项调节），那就不是去推_edata指针了，而是利用mmap系统调用，从堆和栈的中间分配一块虚拟内存
brk分配的内存需要等到高地址内存释放以后才能释放（例如，在B释放之前，A是不可能释放的，因为只有一个_edata 指针，这就是内存碎片产生的原因，什么时候紧缩看下面），而mmap分配的内存可以单独释放。
2 . 源码分析
malloc用于用户空间堆扩展的函数接口。该函数是C库，属于封装了相关系统调用（brk()）的glibc库函数。而不是系统调用（系统可没有sys_malloc()。如果谈及malloc函数涉及的系统内核的那些操作，那么总体可以分为用户空间层面和内核空间层面，本章主要是讲解内核空间。
malloc和free是在用户层工作的，该接口为用户提供一个比较方便管理堆的接口。它的主要工作是维护一个空闲的堆空间缓冲区链表。该缓冲区可以用如下数据结构表述，详细的过程见glibc源码
struct malloc_chunk {
INTERNAL_SIZE_T mchunk_prev_size; /* Size of previous chunk (if free). */
INTERNAL_SIZE_T mchunk_size; /* Size in bytes, including overhead. */
struct malloc_chunk* fd; /* double links -- used only if free. */
struct malloc_chunk* bk;
/* Only used for large blocks: pointer to next larger size. */
struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
struct malloc_chunk* bk_nextsize;
};
每当用户进程调用malloc，首先会在该堆缓冲区寻找足够大小的内存块分配给进程。如果从缓冲区无法找到满足需求的内存块时，那么malloc就会根据相应的内存大小调用系统调用brk或者mmap。我们以sys_brk为例，这个时候，才真正的进入到内核空间。
在32位linux内核中，每个用户进程拥有3GB的虚拟地址空间，那么内核如何为用户空间划分这3GB的虚拟地址空间呢？由上一章讲解，用户进程的可执行文件由text、data、bss段组成。如下图所示
-
用户进程的用户栈从3GB的虚拟空间的顶部开始，由顶向下延伸
-
brk分配的空间是从数据段的顶部end_data到用户栈的地步，所以动态分配空间是从用户栈的地步。
下面我们看看内核关于brk的代码实现，详细见(mm/mmap.c)，其主要的实现流程图如下图所示，最终是调用了do_brk来实现内存的分配
由于这个函数既可以用来分配空间，即把动态分配区地步的边界往上推；也可以用来释放，即归还空间。因此，它的代码也大致可以分为两部分。首先是第一部分：收缩数据区，伸长操作。我们分为两种情况来分析。对于第一部分，内存映射一起学习，这部分主要是第二部分do_brk。
static unsigned long do_brk(unsigned long addr, unsigned long len)
{
struct mm_struct *mm = current->mm;
struct vm_area_struct *vma, *prev;
unsigned long flags;
struct rb_node **rb_link, *rb_parent;
pgoff_t pgoff = addr >> PAGE_SHIFT;
int error;
len = PAGE_ALIGN(len);
if (!len)
return addr;
flags = VM_DATA_DEFAULT_FLAGS | VM_ACCOUNT | mm->def_flags;
error = get_unmapped_area(NULL, addr, len, 0, MAP_FIXED); ----------------------------(1)
if (offset_in_page(error))
return error;
error = mlock_future_check(mm, mm->def_flags, len);
if (error)
return error;
/*
* mm->mmap_sem is required to protect against another thread
* changing the mappings in case we sleep.
*/
verify_mm_writelocked(mm);
/*
* Clear old maps. this also does some error checking for us
*/
while (find_vma_links(mm, addr, addr + len, &prev, &rb_link, ----------------------------(2)
&rb_parent)) {
if (do_munmap(mm, addr, len))
return -ENOMEM;
}
/* Check against address space limits *after* clearing old maps... */
if (!may_expand_vm(mm, 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;
/* Can we just expand an old private anonymous mapping? */
vma = vma_merge(mm, prev, addr, addr + len, flags, ---------------------------(3)
NULL, NULL, pgoff, NULL, NULL_VM_UFFD_CTX);
if (vma)
goto out;
/*
* create a vma struct for an anonymous mapping
*/
vma = kmem_cache_zalloc(vm_area_cachep, GFP_KERNEL); ---------------------------(4)
if (!vma) {
vm_unacct_memory(len >> PAGE_SHIFT);
return -ENOMEM;
}
INIT_LIST_HEAD(&vma->anon_vma_chain);
vma->vm_mm = mm;
vma->vm_start = addr;
vma->vm_end = addr + len;
vma->vm_pgoff = pgoff;
vma->vm_flags = flags;
vma->vm_page_prot = vm_get_page_prot(flags);
vma_link(mm, vma, prev, rb_link, rb_parent);
out:
perf_event_mmap(vma);
mm->total_vm += len >> PAGE_SHIFT;
if (flags & VM_LOCKED)
mm->locked_vm += (len >> PAGE_SHIFT);
vma->vm_flags |= VM_SOFTDIRTY;
return addr;
}
do_brk()有两个参数，addr是要开展的目标区域的开始地址，len是目标区域的长度，其实质也应该是处理vm_erea，目标是在进程空间中有一个匿名vm_erea能映射到[addr, len)这段区域中。下面是代码主要的分析
-
1.**get_unmapped_area()**函数在当前进程的用户空间中查找一个符合len大小的线性地址区域。PAGE_MASK的值为0xFFFFF000，因此，如果 (error & ~PAGE_MASK)为非0，说明addr最低12位非0，addr就不是一个有效的地址，就以这个地址作为返回值；否则，addr就是一个有效的地址（最低12位为0）
-
2.通过**find_vma_links()**在当前进程的所有线性区组成的红黑树中依次遍历每个vma，以确定上一步找到的新区域之前线性区对象位置。如果addr位于某个现存的vma中，则调用do_munmap删去这个线性区。主要是找到合适的VMA的插入点。
-
3.经过2，已经找到了一个合适大小的空闲线性区，接下来通过 vma_merge 去试着将当前的线性区与临近的线性区进行合并，确认这个新节点是否能够与现有树中的节点进行合并，如果地址是连续的，就能够合并，则不用创建新的vm_eara_struct了，直接跳出out，更新统计值即可。
struct vm_area_struct *vma_merge(struct mm_struct *mm,
struct vm_area_struct *prev, unsigned long addr,
unsigned long end, unsigned long vm_flags,
struct anon_vma *anon_vma, struct file *file,
pgoff_t pgoff, struct mempolicy *policy,
struct vm_userfaultfd_ctx vm_userfaultfd_ctx)- mm：描述添加新区域进程的内存空间
- prev：指向当前区域之前的一个内存区
- addr：表示新区域的起始地址
- end：表示新区域的结束地址
- vm_flag：表示该区域的标志，如果该新区域映射了一个磁盘文件，则file结构表示该文件
- pgoff：表示文件映射的偏移量
-
4.如果不能合并，则通过kmem_cache_zalloc创建新的vm_erea_struct，加到anon_vma_chain链表中，也将新创建的VMA加入到mm->mmap链表和红黑树中
到这里malloc就结束了，从以上可看出malloc在完成调用后并没有立马分配物理内存，而是在需要在进程需要访问此虚拟内存块时才会产生缺页中断，才会分配物理内存，并建立虚拟内存到物理内存的映射。以上情况除了当分配flag带有VM_MLOCK时需要立即调用mm_populate来分配物理内存，其实现为mm_populate，其代码实现如下
int __mm_populate(unsigned long start, unsigned long len, int ignore_errors)
{
struct mm_struct *mm = current->mm;
unsigned long end, nstart, nend;
struct vm_area_struct *vma = NULL;
int locked = 0;
long ret = 0;
VM_BUG_ON(start & ~PAGE_MASK);
VM_BUG_ON(len != PAGE_ALIGN(len));
end = start + len;
for (nstart = start; nstart < end; nstart = nend) { ---------------------(1)
/*
* We want to fault in pages for [nstart; end) address range.
* Find first corresponding VMA.
*/
if (!locked) {
locked = 1;
down_read(&mm->mmap_sem);
vma = find_vma(mm, nstart);
} else if (nstart >= vma->vm_end)
vma = vma->vm_next;
if (!vma || vma->vm_start >= end)
break;
/*
* Set [nstart; nend) to intersection of desired address
* range with the first VMA. Also, skip undesirable VMA types.
*/
nend = min(end, vma->vm_end);
if (vma->vm_flags & (VM_IO | VM_PFNMAP))
continue;
if (nstart < vma->vm_start)
nstart = vma->vm_start;
/*
* Now fault in a range of pages. populate_vma_page_range()
* double checks the vma flags, so that it won't mlock pages
* if the vma was already munlocked.
*/
ret = populate_vma_page_range(vma, nstart, nend, &locked); ---------------------(2)
if (ret < 0) {
if (ignore_errors) {
ret = 0;
continue; /* continue at next VMA */
}
break;
}
nend = nstart + ret * PAGE_SIZE;
ret = 0;
}
if (locked)
up_read(&mm->mmap_sem);
return ret; /* 0 or negative error code */
}
- 1.以start为起始地址，先通过find_vma()查找VMA，如果没有找到VMA，则退出循环
- 2.调用populate_vma_page_range为VMA分配物理内存，最终会调用__get_user_pages为进程地址空间分配物理内存并且建立映射关系。
至此，已经为这块进程地址空间VMA分配了物理页面，并建立了映射关系。对于malloc函数使为用户空间分配进程地址空间，其实现流程如下：
至此上面过程，malloc返回了一个线性地址，如果此时用户地址访问这个线性地址，那么就会发生缺页异常，内核才会真正的为虚拟地址分配实际的物理内存。所以实际在用户空间，如果我们通过malloc(4096)，申请4k的地址空间，当我们不去使用的时候，是不会申请到实际的物理地址。其分配流程如下图
3.总结
malloc() 是 C 标准库提供的内存分配函数，对应到系统调用上，有两种实现方式，即 brk() 和 mmap()。
| 分配方式 | 特点 | 优点 | 缺点 |
|---|---|---|---|
| brk/sbrk | 对小块内存（小于128K）,通过移动堆顶的位置来分配内存 | 内存释放后并不会立刻归还系统，而是被缓存起来，这样就可以重复使用,可以减少缺页异常的发生，提高内存访问效率 | 由于这些内存没有归还系统，在内存工作繁忙时，频繁的内存分配和释放会造成内存碎片 |
| mmap | 大块内存（大于128K）,也就是在文件映射段找一块空闲内存分配出去 | 分配的内存，会在释放时直接归还系统,每次mmap都会发生缺页异常 | 在内存工作繁忙时，频繁的内存分配会导致大量的缺页异常，使内核的管理负担增大。这也是malloc只对大块内存使用mmap的原因 |
进程向 OS 申请和释放地址空间的接口 sbrk/mmap/munmap 都是系统调用，频繁调用系统调用都比较消耗系统资源的。并且， mmap 申请的内存被 munmap 后，重新申请会产生更多的缺页中断。例如使用 mmap 分配 1M 空间，第一次调用产生了大量缺页中断 (1M/4K 次 ) ，当munmap 后再次分配 1M 空间，会再次产生大量缺页中断。缺页中断是内核行为，会导致内核态CPU消耗较大。另外，如果使用 mmap 分配小内存，会导致地址空间的分片更多，内核的管理负担更大。
同时堆是一个连续空间，并且堆内碎片由于没有归还 OS ，如果可重用碎片，再次访问该内存很可能不需产生任何系统调用和缺页中断，这将大大降低 CPU 的消耗。 因此， glibc 的 malloc 实现中，充分考虑了 sbrk 和 mmap 行为上的差异及优缺点，默认分配大块内存 (128k) 才使用 mmap 获得地址空间，也可通过 mallopt(M_MMAP_THRESHOLD, ) 来修改这个临界值。
4. 参考文档
奔跑吧linux内核
https://www.jishuchi.com/read/linux-interview/2830
https://www.pianshen.com/article/59731684449/
https://blog.holbertonschool.com/hack-the-virtual-memory-malloc-the-heap-the-program-break/
https://www.jishuchi.com/read/linux-interview/2830
