内存管理、内存分配与释放、地址映射、malloc/free的实现

一、内存管理概述

（一）、虚拟内存实现结构

（1）内存映射模块(mmap)：负责把磁盘文件的逻辑地址映射到虚拟地址，以及把虚拟地址映射到物理地址。

（2）交换模块（swap）：负责控制内存内容的换入和换出，它通过交换机制，使得在物理内存的页面（RAM 页）中保留有效的页 ，即从主存中淘汰最近没被访问的页，保存近来访问过的页。

（3）核心内存管理模块（core）：负责核心内存管理功能，即对页的分配、回收、释放及请页处理等，这些功能将被别的内核子系统（如文件系统）使用。

（4）结构特定的模块：负责给各种硬件平台提供通用接口，这个模块通过执行命令来改变硬件MMU 的虚拟地址映射，并在发生页错误时，提供了公用的方法来通知别的内核子系统。这个模块是实现虚拟内存的物理基础。

（二）、内核空间和用户空间

Linux 简化了分段机制，使得虚拟地址与线性地址总是一致，因此，Linux 的虚拟地址空间也为0～4G 字节。Linux 内核将这4G 字节的空间分为两部分。将最高的1G 字节（从虚拟地址0xC0000000 到0xFFFFFFFF），供内核使用，称为“内核空间”。而将较低的3G 字节（从虚拟地址0x00000000 到0xBFFFFFFF），供各个进程使用，称为“用户空间”。因为每个进程可以通过系统调用进入内核，因此，Linux 内核由系统内的所有进程共享。于是，从具体进程的角度来看，每个进程可以拥有4G 字节的虚拟空间。图 6.3 给出了进程虚拟空间示意图。

Linux 使用两级保护机制：0 级供内核使用，3 级供用户程序使用。从图6.3 中可以看出，每个进程有各自的私有用户空间（0～3G），这个空间对系统中的其他进程是不可见的。最高的1G 字节虚拟内核空间则为所有进程以及内核所共享。

（三）、虚拟内存实现机制间的关系

首先内存管理程序通过映射机制把用户程序的逻辑地址映射到物理地址，在用户程序运行时如果发现程序中要用的虚地址没有对应的物理内存时，就发出了请页要求①；如果有空闲的内存可供分配，就请求分配内存②（于是用到了内存的分配和回收），并把正在使用的物理页记录在页缓存中③（使用了缓存机制）。如果没有足够的内存可供分配，那么就调用交换机制，腾出一部分内存④⑤。另外在地址映射中要通过TLB（翻译后援存储器）来寻找物理页⑧；交换机制中也要用到交换缓存⑥，并且把物理页内容交换到交换文件中后也要修改页表来映射文件地址⑦。

二、内存分配与释放

在Linux 中，CPU 不能按物理地址来访问存储空间，而必须使用虚拟地址；因此，对于内存页面的管理，通常是先在虚存空间中分配一个虚存区间，然后才根据需要为此区间分配相应的物理页面并建立起映射，也就是说，虚存区间的分配在前，而物理页面的分配在后。

（一）、伙伴算法(Buddy)

Linux 的伙伴算法把所有的空闲页面分为10 个块组，每组中块的大小是2 的幂次方个页面，例如，第0 组中块的大小都为2^0（1 个页面），第1 组中块的大小都为2^1（2 个页面），第9 组中块的大小都为2^9（512 个页面）。也就是说，每一组中块的大小是相同的，且这同样大小的块形成一个链表。

我们通过一个简单的例子来说明该算法的工作原理。

假设要求分配的块的大小为128 个页面（由多个页面组成的块我们就叫做页面块）。该算法先在块大小为128 个页面的链表中查找，看是否有这样一个空闲块。如果有，就直接分配；如果没有，该算法会查找下一个更大的块，具体地说，就是在块大小256 个页面的链表中查找一个空闲块。如果存在这样的空闲块，内核就把这256 个页面分为两等份，一份分配出去，另一份插入到块大小为128 个页面的链表中。如果在块大小为256 个页面的链表中也没有找到空闲页块，就继续找更大的块，即512 个页面的块。如果存在这样的块，内核就从512 个页面的块中分出128 个页面满足请求，然后从384 个页面中取出256 个页面插入到块大小为256 个页面的链表中。然后把剩余的128 个页面插入到块大小为128 个页面的链表中。如果512 个页面的链表中还没有空闲块，该算法就放弃分配，并发出出错信号。

以上过程的逆过程就是块的释放过程，这也是该算法名字的来由。满足以下条件的两个块称为伙伴：

（1）两个块的大小相同；

（2）两个块的物理地址连续。

伙伴算法把满足以上条件的两个块合并为一个块，该算法是迭代算法，如果合并后的块还可以跟相邻的块进行合并，那么该算法就继续合并。

(二）、Slab 分配机制

可以根据对内存区的使用频率来对它分类。对于预期频繁使用的内存区，可以创建一组特定大小的专用缓冲区进行处理，以避免内碎片的产生。对于较少使用的内存区，可以创建一组通用缓冲区（如Linux 2.0 中所使用的2 的幂次方）来处理，即使这种处理模式产生碎

片，也对整个系统的性能影响不大。

硬件高速缓存的使用，又为尽量减少对伙伴算法的调用提供了另一个理由，因为对伙伴算法的每次调用都会“弄脏”硬件高速缓存，因此，这就增加了对内存的平均访问次数。

Slab 分配模式把对象分组放进缓冲区（尽管英文中使用了Cache 这个词，但实际上指的是内存中的区域，而不是指硬件高速缓存）。因为缓冲区的组织和管理与硬件高速缓存的命中率密切相关，因此，Slab 缓冲区并非由各个对象直接构成，而是由一连串的“大块（Slab）”构成，而每个大块中则包含了若干个同种类型的对象，这些对象或已被分配，或空闲，如图6.10 所示。一般而言，对象分两种，一种是大对象，一种是小对象。所谓小对象，是指在一个页面中可以容纳下好几个对象的那种。例如，一个inode 结构大约占300 多个字节，因此，一个页面中可以容纳8 个以上的inode 结构，因此，inode 结构就为小对象。Linux 内核中把小于512 字节的对象叫做小对象。

实际上，缓冲区就是主存中的一片区域，把这片区域划分为多个块，每块就是一个Slab，每个Slab 由一个或多个页面组成，每个Slab 中存放的就是对象。

三、地址映射机制

在进程的task_struct 结构中包含一个指向 mm_struct 结构的指针，mm_strcut 用来描述一个进程的虚拟地址空间。进程的 mm_struct 则包含装入的可执行映像信息以及进程的页目录指针pgd。该结构还包含有指向 vm_area_struct 结构的几个指针，每个 vm_area_struct 代表进程的一个虚拟地址区间。vm_area_struct 结构含有指向vm_operations_struct 结构的一个指针，vm_operations_struct 描述了在这个区间的操作。vm_operations 结构中包含的是函数指针；其中，open、close 分别用于虚拟区间的打开、关闭，而nopage 用于当虚存页面不在物理内存而引起的“缺页异常”时所应该调用的函数，当 Linux 处理这一缺页异常时（请页机制），就可以为新的虚拟内存区分配实际的物理内存。图6.15 给出了虚拟区间的操作集。

 C++ Code 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

struct mm_struct {     struct vm_area_struct *mmap;            /* list of VMAs */     struct rb_root mm_rb;     struct vm_area_struct *mmap_cache;      /* last find_vma result */     ...     unsigned long start_code, end_code, start_data, end_data;     unsigned long start_brk, brk, start_stack;     ... }; struct vm_area_struct {     struct mm_struct *vm_mm;        /* The address space we belong to. */     unsigned long vm_start;         /* Our start address within vm_mm. */     unsigned long vm_end;           /* The first byte after our end address                                            within vm_mm. */     ....     /* linked list of VM areas per task, sorted by address */     struct vm_area_struct *vm_next;     ....     /* describe the permissable operation */     unsigned long vm_flags;     /* operations on this area */     struct vm_operations_struct * vm_ops;          struct file * vm_file; /* File we map to （can be NULL）. */ } ; /* * These are the virtual MM functions - opening of an area, closing and * unmapping it （needed to keep files on disk up-to-date etc）, pointer * to the functions called when a no-page or a wp-page exception occurs. */ struct vm_operations_struct {     void (*open)(struct vm_area_struct *area);     void (*close)(struct vm_area_struct *area);     struct page * （*nopage）（struct vm_area_struct * area, unsigned long address, int unused）; };

四、malloc 和 free 的实现

 C++ Code 

1 2 3 4 5 6 7 8 9 10

Normally,  malloc()  allocates  memory  from  the heap, and adjusts the size of the heap as required, using sbrk(2).  When allocating blocks of memory larger than MMAP_THRESHOLD bytes, the glibc malloc() implementation allocates the memory as  a private  anonymous mapping using mmap(2).  MMAP_THRESHOLD is 128 kB by default, but is adjustable using mallopt(3).  Allo‐ cations performed using mmap(2) are unaffected by the RLIMIT_DATA resource limit (see getrlimit(2)). MAP_ANONYMOUS     The  mapping  is  not  backed  by  any file; its contents are initialized to zero.  The fd and offset arguments are ignored;     however, some implementations require fd to be - 1 if MAP_ANONYMOUS ( or MAP_ANON) is specified, and  portable applications      should ensure this. The use of MAP_ANONYMOUS in conjunction with MAP_SHARED is only supported on Linux since kernel 2.4.

（一）、使用brk()/ sbrk() 实现

图中白色背景的框表示 malloc管理的空闲内存块，深色背景的框不归 malloc管，可能是已经分配给用户的内存块，也可能不属于当前进程， Break之上的地址不属于当前进程，需要通过 brk系统调用向内核申请。每个内存块开头都有一个头节点，里面有一个指针字段和一个长度字段，指针字段把所有空闲块的头节点串在一起，组成一个环形链表，长度字段记录着头节点和后面的内存块加起来一共有多长，以 8字节为单位（也就是以头节点的长度为单位）。

1. 一开始堆空间由一个空闲块组成，长度为 7×8=56字节，除头节点之外的长度为 48字节。

2. 调用 malloc分配 8个字节，要在这个空闲块的末尾截出 16个字节，其中新的头节点占了 8个字节，另外 8个字节返回给用户使用，注意返回的指针 p1指向头节点后面的内存块。

3. 又调用 malloc分配 16个字节，又在空闲块的末尾截出 24个字节，步骤和上一步类似。

4. 调用 free释放 p1所指向的内存块，内存块（包括头节点在内）归还给了 malloc，现在 malloc管理着两块不连续的内存，用环形链表串起来。注意这时 p1成了野指针，指向不属于用户的内存， p1所指向的内存地址在 Break之下，是属于当前进程的，所以访问 p1时不会出现段错误，但在访问 p1时这段内存可能已经被 malloc再次分配出去了，可能会读到意外改写数据。另外注意，此时如果通过 p2向右写越界，有可能覆盖右边的头节点，从而破坏 malloc管理的环形链表， malloc就无法从一个空闲块的指针字段找到下一个空闲块了，找到哪去都不一定，全乱套了。

5. 调用 malloc分配 16个字节，现在虽然有两个空闲块，各有 8个字节可分配，但是这两块不连续， malloc只好通过 brk系统调用抬高 Break，获得新的内存空间。在 [K&R]的实现中，每次调用 sbrk函数时申请 1024×8=8192个字节，在 Linux系统上 sbrk函数也是通过 brk实现的，这里为了画图方便，我们假设每次调用 sbrk申请 32个字节，建立一个新的空闲块。

6. 新申请的空闲块和前一个空闲块连续，因此可以合并成一个。在能合并时要尽量合并，以免空闲块越割越小，无法满足大的分配请求。

7. 在合并后的这个空闲块末尾截出 24个字节，新的头节点占 8个字节，另外 16个字节返回给用户。

8. 调用 free(p3)释放这个内存块，由于它和前一个空闲块连续，又重新合并成一个空闲块。注意， Break只能抬高而不能降低，从内核申请到的内存以后都归 malloc管了，即使调用 free也不会还给内核。

（二）、使用mmap() / munmap() 实现

在Linux下面，kernel 使用4096 byte来划分页面，而malloc的颗粒度更细，使用8 byte对齐，因此，分配出来的内存不一定是页对齐的。而mmap 分配出来的内存地址是页对齐的，所以munmap处理的内存地址必须页对齐（Page Aligned）。