2023-06-11
原文作者:奇小葩 原文地址:https://blog.csdn.net/u012489236/category_9614673.html

学习完了用户进程地址空间,那么从本章开始学习下用户空间的内存分配。对于我们来说,对是进程中用于动态分配变量和数据的内存区域,堆的管理对应用程序员来说是不可见的。因为它依赖于标准库提供的各种辅助函数(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命令跟踪)

  1. 即分配一块小型内存(小于或等于128kb),malloc()会调用brk()调高断点(brk是将数据段(.data)的最高地址指针_edata往高地址推),分配的内存在堆区域。
  2. 当分配一块大型内存(大于128kb),malloc()会调用mmap2()分配一块内存(mmap是在进程的虚拟地址空间中(一般是堆和栈中间)找一块空闲的空间。

202306111243365291.png

小于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,于是内存紧缩,如下图所示。

202306111243386732.png

事实是:_edata+30K只是完成虚拟地址的分配,A这块内存现在还是没有物理页与之对应的,等到进程第一次读写A这块内存的时候,发生缺页中断,这个时候,内核才分配A这块内存对应的物理页。也就是说,如果用malloc分配了A这块内容,然后从来不访问它,那么,A对应的物理页是不会被分配的。
  同时brk 分配的内存需要等到高地址内存释放以后才能释放(例如,在 C 释放之前,A 是不可能释放的,这就是内存碎片产生的原因),而 mmap 分配的内存可以单独释放。

1.2 mmap

使用mmap分配内存。在堆和栈之间找一块空闲内存分配(对应独立内存,而且初始化为0)

  1. 进程调用B=malloc(200K)以后,内存空间如图4 ,默认情况下,malloc函数分配内存,如果请求内存大于128K(可由M_MMAP_THRESHOLD选项调节),那就不是去推_edata指针了,而是利用mmap系统调用,从堆和栈的中间分配一块虚拟内存。

  2. 进程调用free(B)以后,B对应的虚拟内存和物理内存一起释放

    202306111243396813.png  默认情况下,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段组成。如下图所示

202306111243413124.png

  • 用户进程的用户栈从3GB的虚拟空间的顶部开始,由顶向下延伸

  • brk分配的空间是从数据段的顶部end_data到用户栈的地步,所以动态分配空间是从用户栈的地步。

    下面我们看看内核关于brk的代码实现,详细见(mm/mmap.c),其主要的实现流程图如下图所示,最终是调用了do_brk来实现内存的分配

    202306111243428135.png

由于这个函数既可以用来分配空间,即把动态分配区地步的边界往上推;也可以用来释放,即归还空间。因此,它的代码也大致可以分为两部分。首先是第一部分:收缩数据区,伸长操作。我们分为两种情况来分析。对于第一部分,内存映射一起学习,这部分主要是第二部分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函数使为用户空间分配进程地址空间,其实现流程如下:

202306111243453106.png

至此上面过程,malloc返回了一个线性地址,如果此时用户地址访问这个线性地址,那么就会发生缺页异常,内核才会真正的为虚拟地址分配实际的物理内存。所以实际在用户空间,如果我们通过malloc(4096),申请4k的地址空间,当我们不去使用的时候,是不会申请到实际的物理地址。其分配流程如下图

202306111243467537.png

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

阅读全文