内存池
从内核中的伙伴系统，页高速缓存系统，slab内存管理系统，常规内存高速缓存系统，到用户线性区管理，用户动态内存分配malloc/free，最终因时制宜选择自定义内存区管理策略，到底有哪些驱动力？
接下来我们来梳理一下
1.伙伴系统
伙伴系统是内核为解决外碎化问题引入的内存管理机制。在32位体系结构中，虚拟内存空间的第四个GB用来线性的映射物理内存开始的DMA和低端内存管理区。而内存管理的基本单位是页，一个页的大小为4kB。所谓的外碎化指的是多次申请多个页的内存并释放后，会导致内存中存在不间隔的无法集中利用的页，其基本单位仍然是页，只是没有办法找到连续的可用来分配的多个页框。为了应对这样的事情，伙伴系统应运而生。伙伴系统首先将内存分为11个不同的2指数个大小的内存对象集合，每个集合用双向链表表示。分配内存时从小到大选择第一个能够满足大小的内存对象（2的order指数个），在这个过程中，如果没有办法找到适配的块，则对于大块的内存需要分割，分割时候将剩下的2k-2order大小的内存区分别放入到k~order大小的内存对象集合中，如果发现伙伴（相邻的）中有空闲的内存块，则进行合并。释放内存块的时候同理。
伙伴系统有效的解决了大块内存的分配问，使得内存管理高效
2.页高速缓存机制
在cpu高速缓存往往是提高整个内存访问的关键所在，所以对于单页管理我们采取单独的机制来运行。其中包括热高速换粗和冷高速缓存，热高速缓存是用来保存经常存取的数据的。将内存中分散的单页缓存到高速缓存中进行管理能够有效的提高内存分配合释放的效率。
slab内存管理系统，slab系统也是一种有效的高速缓存机制，只是这是一种更加细粒度的内碎化避免机制。它将内存管理的粒度降低到实际分配数据类型的规模。同样的，在高速缓存中维护着多个大小不同的slab对象集合，集合使用空闲，使用，部分空闲等三个链表进行管理，使用三个链表能够有效的分配和释放内存。同时每一个cpu高速缓存都维护着自己的常规高速缓存（相当于维护了一个常用内存对象的集合，用于更加高效的内存管理）
总体而言这些都是在内存利用率和和性能之间寻找折中方案的内存管理策略，管理的粒度越小，内存利用率越高，但是相应的内碎化就越严重，进一步又制约了大块内存分配的效率，而管理的粒度越大，带来的内存管理的开销变小了，但是内存的利用率会衰减的很严重。
image.png
用户动态内存的分配
malloc/free是用户动态内存分配的libc接口，传统的堆内存分配机制使用brk（）（底层类似于mmap的机制）系统调用来从操作系统获得内存。往往初始化会分配128k内存区，然后统一管理者128k的内存。到这一步，内存管理的开销就仅仅取决于算法层面的设计了。malloc中将内存分成不同的大小的块（但是得保证对8字节对齐，字），每一次malloc都会按照给定的大小寻找合适的块。这里我们有两种选取策略，第一种是选择第一个满足条件的内存块（first fit），第二种是选择最适配的块（best fit）；这两种大小各有优劣，标准采用的是第一种 ，但是在其之上使用的相应的优化算法，如块的分裂；
Ptmalloc2是glibc malloc的多线程拓展：
因为系统调用的代价很高，用户申请内存不能每次都从内核分配，尤其对小内存。并且因为mmap的区域容易被munmap释放，所以一般大内存采用mmap(),小内存使用brk().
事实上，brk申请内存的方式和mmap申请匿名空间的内存映射的机制差不多，只不过前者维护一个边界指针，只会上下滑动扩展或者收缩内存，无法随机分配或者分配内存。
ptmalloc2拥有一个主分配区和多个非主分配区。非主分配区使用mmap向操作系统批量申请HEAP_MAX_SIZE大小的虚拟内存。
对于多线程的支持：当其中某一个线程调用malloc的时候，会先查看线程的私有变量中是否已经存在一个分配区，如果存在则尝试加锁，如果加锁失败则遍历areana链表（分配区组成的环形链表）试图获取一个没有加锁的arena，如果依然获取不到就创建一个新的非主分配区。
free释放的时候也要获取锁。分配小块内存容易产生碎片，ptmalloc在整理合并的时候要对arena做加锁操作。在线程多的时候，锁的开销就会增大。
用户请求分配的内存在ptmalloc中使用chunk表示，每一个chunk至少需要8个字节额外的开销。用户free掉的内存不会马上归还给操作系统，ptmalloc会同一管理heap哈mmap区域的空闲chunks，避免了频繁的系统调用。
ptmalloc将相似大小的chunk用双向链表链接起来，这样的一个链表被称为一个bin，维护了128个内存对象的bins，用数组存储：
数组中的第一个为 unsorted bin, 数组中从 2 开始编号的前 64 个 bin 称为 small bins, 同一个small bin中的chunk具有相同的大小。small bins后面的bin被称作large bins。
当free一个chunk的时候，ptmalloc还会检查它前后的chunk是否是空闲的，如果是的话，ptmalloc会首先把他们合并成为一个大的chunk，然后将合并后的chunk放到unsortedbin中。另外ptmalloc为了提高分配的速度，会把一些小的（不大于64B）chunk先放到一个fast bin中
在fast bins和bins都不能满足需求之后，ptmalloc会设法在一个叫做top chunk的空间分配内存。对于非主分配区会预先通过mmap分配一块内存作为top chunk，当bins和fast bins都不能满足分配需要的时候，ptmalloc会设法在top chunk迁移到的chunk上，并用单链表链接起来。如果free的chunk恰好与top chunk相邻，那么这两个chunk就会合并成新的top chunk，如果top chunk大小恰好与top chunk迁移到新的chunk上，并用单链表链接起来。如果top chunk的大小大于某个阈值才还给操作系统。主分配区类似，不过通过sbrk（）分配和调整top chunk的大小，只有heap顶部连续内存空间超过阈值的才会回收内存。
ptmalloc存在的问题：
1、后分配的内存先释放，因为ptmalloc收缩内存是从top chunk开始，如果与top chunk相邻的chunk不能释放，top chunk以下的chunk都无法释放。
2、多线程开销太大，需要避免多线程频繁的分配释放
3、内存从thread的arena中分配，内存不能从一个arena移动到另外一个arena。就是说如果多线程使用内存不均衡，容易导致内存的浪费。
4、不定期分配长生存周期的内存容易产生大量的内存碎片，不利于回收。64位操作系统最好分配32位以上的内存，这是使用mmap的阈值。
内存池拓展一：tcmalloc——golang的内存管理机制
简介：提出，tcmalloc是google开源的一个内存管理库，作为glibc malloc的替代品。目前已经在chrome和safari等知名软件中使用。
小对象分配：tcmalloc为每一个线程分配一个线程本地Thread Cache，小内存从ThreadCache中分配，此外还有一个中央堆，ThreadCache不够用的时候，会从CentralCache中获取空间放到threadcache中。
小对象（<=32KB）从threadcache中分配，大对象从centralcache中分配。大对象分配的空间都是4k对齐的多个pages也能分割成多个小对象划分到threadcache中。小对象有将近170个不同的大小分类，每一个class维护一个该大小内存块的的freelist的单链表，分配的时候先找到bestfit的class，然后无锁的获取该链表首个首元素返回。如果链表中悟无空间了，则到centralCache中划分几个页面并分割成该class的大小，放入链表中。
CentralCache分配管理
大对象（32k）先4k对齐后，从centralCache中分配。CentralCache维护的PageHeap，数组中的第256个元素是所有大于255个页面都挂在该链表上。
当best fit的页面链表没有空闲时，则一直往更大的页面空间找，如果256个链表都遍历后依然没有成功分配。则使用sbrk，mmap，、/dev/mem从系统中分配
tcmalloc PageHeap管理的连续的页面叫做span，如果span是pageHeap中的一个链表元素，如果span已经分配，他可能是返回给应用程序的大对象，或者已经被分割成了多个小对象，该小对象的size-class会被记录在span中
在32位系统中，使用一个中央数组映射了页面和span的对应关系，数组索引是页面好，数组元素是页面所在的span。在64位系统中，使用一个三级 radix tree记录了该映射关系。
回收
当一个object free时候，会根据地址对齐计算所在的页面号，然后通过central array找到对应的span
如果是小对象，span会告诉我们他的size class，然后把该对象插入当前进程的threadCache中，如果此时ThreadCache超过一个预算值，则会使用垃圾回收机制把未收用object从threadcCached移动到CentralCache的central free lists中
如果是大对象，span会告诉我们对象锁在页面号范围。假设这个范围是[p,q]， 先查找页面p-1和q+1所在的span，如果这些临近的span也是free的，则合并到[p,q]所在的span， 然后把这个span回收到PageHeap中。
CentralCache的central free lists类似ThreadCache的FreeList，不过它增加了一级结构，先根据size-class关联到spans的集合， 然后是对应span的object链表。如果span的链表中所有object已经free， 则span回收到PageHeap中。
改进：
threadCache会阶段性的回收内存到CentralCache里。解决了ptmalloc2中arena间不能迁移的问题。
Tcmalloc占用更少的额外空间，例如N个8字节对象可能要使用大约8N*1.01字节的空间。即，多用百分之一的空间。Ptmalloc2使用8字节描述一个chunk。
更快。小对象几乎无锁，大于32KB的对象从CentralCache中分配使用自旋锁。并且>32KB对象都是页面对齐分配，多线程的时候应该尽量避免频繁分配，否则造成自旋锁的竞争和页面对齐造成的浪费。
jemalloc
简介：jemalloc是facebook推出的，最早的时候的freebsd的libc malloc实现。目前firefox、Facebook服务器各种组件中大量使用。
jemalloc原理：
与tcmalloc类似，每一个线程同样在<32KB的时候无锁使用线程本地cache。
jemalloc在64bits系统上使用下面的size-class分类：
small：
large：
huge：
references:
https://blog.csdn.net/junlon2006/article/details/77854898
https://blog.csdn.net/junlon2006/article/details/77854898
任何一个用过或学过C的人对malloc都不会陌生。大家都知道malloc可以分配一段连续的内存空间，并且在不再使用时可以通过free释放掉。但是，许多程序员对malloc背后的事情并不熟悉，许多人甚至把malloc当做操作系统所提供的系统调用或C的关键字。实际上，malloc只是C的标准库中提供的一个普通函数，而且实现malloc的基本思想并不复杂，任何一个对C和操作系统有些许了解的程序员都可以很容易理解。
这篇文章通过实现一个简单的malloc来描述malloc背后的机制。当然与现有C的标准库实现（例如glibc）相比，我们实现的malloc并不是特别高效，但是这个实现比目前真实的malloc实现要简单很多，因此易于理解。重要的是，这个实现和真实实现在基本原理上是一致的。
这篇文章将首先介绍一些所需的基本知识，如操作系统对进程的内存管理以及相关的系统调用，然后逐步实现一个简单的malloc。为了简单起见，这篇文章将只考虑x86_64体系结构，操作系统为Linux。
1 什么是malloc
在实现malloc之前，先要相对正式地对malloc做一个定义。
根据标准C库函数的定义，malloc具有如下原型：
C
void* malloc(size_t size);
1
void*malloc(size_tsize);
这个函数要实现的功能是在系统中分配一段连续的可用的内存，具体有如下要求：
malloc分配的内存大小至少为size参数所指定的字节数
malloc的返回值是一个指针，指向一段可用内存的起始地址
多次调用malloc所分配的地址不能有重叠部分，除非某次malloc所分配的地址被释放掉
malloc应该尽快完成内存分配并返回（不能使用NP-hard的内存分配算法）
实现malloc时应同时实现内存大小调整和内存释放函数（即realloc和free）
对于malloc更多的说明可以在命令行中键入以下命令查看：
C
man malloc
1
manmalloc
2 预备知识
在实现malloc之前，需要先解释一些Linux系统内存相关的知识。
2.1 Linux内存管理
2.1.1 虚拟内存地址与物理内存地址
为了简单，现代操作系统在处理内存地址时，普遍采用虚拟内存地址技术。即在汇编程序（或机器语言）层面，当涉及内存地址时，都是使用虚拟内存地址。采用这种技术时，每个进程仿佛自己独享一片2N字节的内存，其中N是机器位数。例如在64位CPU和64位操作系统下，每个进程的虚拟地址空间为264Byte。
这种虚拟地址空间的作用主要是简化程序的编写及方便操作系统对进程间内存的隔离管理，真实中的进程不太可能（也用不到）如此大的内存空间，实际能用到的内存取决于物理内存大小。
由于在机器语言层面都是采用虚拟地址，当实际的机器码程序涉及到内存操作时，需要根据当前进程运行的实际上下文将虚拟地址转换为物理内存地址，才能实现对真实内存数据的操作。这个转换一般由一个叫MMU（Memory Management Unit）的硬件完成。
2.1.2 页与地址构成
在现代操作系统中，不论是虚拟内存还是物理内存，都不是以字节为单位进行管理的，而是以页（Page）为单位。一个内存页是一段固定大小的连续内存地址的总称，具体到Linux中，典型的内存页大小为4096Byte（4K）。
所以内存地址可以分为页号和页内偏移量。下面以64位机器，4G物理内存，4K页大小为例，虚拟内存地址和物理内存地址的组成如下：
上面是虚拟内存地址，下面是物理内存地址。由于页大小都是4K，所以页内便宜都是用低12位表示，而剩下的高地址表示页号。
MMU映射单位并不是字节，而是页，这个映射通过查一个常驻内存的数据结构页表来实现。现在计算机具体的内存地址映射比较复杂，为了加快速度会引入一系列缓存和优化，例如TLB等机制。下面给出一个经过简化的内存地址翻译示意图，虽然经过了简化，但是基本原理与现代计算机真实的情况的一致的。
2.1.3 内存页与磁盘页
我们知道一般将内存看做磁盘的的缓存，有时MMU在工作时，会发现页表表明某个内存页不在物理内存中，此时会触发一个缺页异常（Page Fault），此时系统会到磁盘中相应的地方将磁盘页载入到内存中，然后重新执行由于缺页而失败的机器指令。关于这部分，因为可以看做对malloc实现是透明的，所以不再详细讲述，有兴趣的可以参考《深入理解计算机系统》相关章节。
最后附上一张在维基百科找到的更加符合真实地址翻译的流程供大家参考，这张图加入了TLB和缺页异常的流程（图片来源页）。
2.2 Linux进程级内存管理
2.2.1 内存排布
明白了虚拟内存和物理内存的关系及相关的映射机制，下面看一下具体在一个进程内是如何排布内存的。
以Linux 64位系统为例。理论上，64bit内存地址可用空间为0x0000000000000000 ~ 0xFFFFFFFFFFFFFFFF，这是个相当庞大的空间，Linux实际上只用了其中一小部分（256T）。
根据Linux内核相关文档描述，Linux64位操作系统仅使用低47位，高17位做扩展（只能是全0或全1）。所以，实际用到的地址为空间为0x0000000000000000 ~ 0x00007FFFFFFFFFFF和0xFFFF800000000000 ~ 0xFFFFFFFFFFFFFFFF，其中前面为用户空间（User Space），后者为内核空间（Kernel Space）。图示如下：
对用户来说，主要关注的空间是User Space。将User Space放大后，可以看到里面主要分为如下几段：
Code：这是整个用户空间的最低地址部分，存放的是指令（也就是程序所编译成的可执行机器码）
Data：这里存放的是初始化过的全局变量
BSS：这里存放的是未初始化的全局变量
Heap：堆，这是我们本文重点关注的地方，堆自低地址向高地址增长，后面要讲到的brk相关的系统调用就是从这里分配内存
Mapping Area：这里是与mmap系统调用相关的区域。大多数实际的malloc实现会考虑通过mmap分配较大块的内存区域，本文不讨论这种情况。这个区域自高地址向低地址增长
Stack：这是栈区域，自高地址向低地址增长
下面我们主要关注Heap区域的操作。对整个Linux内存排布有兴趣的同学可以参考其它资料。
2.2.2 Heap内存模型
一般来说，malloc所申请的内存主要从Heap区域分配（本文不考虑通过mmap申请大块内存的情况）。
由上文知道，进程所面对的虚拟内存地址空间，只有按页映射到物理内存地址，才能真正使用。受物理存储容量限制，整个堆虚拟内存空间不可能全部映射到实际的物理内存。Linux对堆的管理示意如下：
Linux维护一个break指针，这个指针指向堆空间的某个地址。从堆起始地址到break之间的地址空间为映射好的，可以供进程访问；而从break往上，是未映射的地址空间，如果访问这段空间则程序会报错。
2.2.3 brk与sbrk
由上文知道，要增加一个进程实际的可用堆大小，就需要将break指针向高地址移动。Linux通过brk和sbrk系统调用操作break指针。两个系统调用的原型如下：
C
int brk(void addr);
void *sbrk(intptr_t increment);
1
2
intbrk(voidaddr);
void *sbrk(intptr_tincrement);
brk将break指针直接设置为某个地址，而sbrk将break从当前位置移动increment所指定的增量。brk在执行成功时返回0，否则返回-1并设置errno为ENOMEM；sbrk成功时返回break移动之前所指向的地址，否则返回(void *)-1。
一个小技巧是，如果将increment设置为0，则可以获得当前break的地址。
另外需要注意的是，由于Linux是按页进行内存映射的，所以如果break被设置为没有按页大小对齐，则系统实际上会在最后映射一个完整的页，从而实际已映射的内存空间比break指向的地方要大一些。但是使用break之后的地址是很危险的（尽管也许break之后确实有一小块可用内存地址）。
2.2.4 资源限制与rlimit
系统对每一个进程所分配的资源不是无限的，包括可映射的内存空间，因此每个进程有一个rlimit表示当前进程可用的资源上限。这个限制可以通过getrlimit系统调用得到，下面代码获取当前进程虚拟内存空间的rlimit：
C
int main() {
struct rlimit *limit = (struct rlimit *)malloc(sizeof(struct rlimit));
getrlimit(RLIMIT_AS, limit);
printf(“soft limit: %ld, hard limit: %ld\n”, limit->rlim_cur, limit->rlim_max);
}
1
2
3
4
5
intmain(){
structrlimit *limit= (structrlimit *)malloc(sizeof(structrlimit));
getrlimit(RLIMIT_AS,limit);
printf(“soft limit: %ld, hard limit: %ld\n”,limit->rlim_cur,limit->rlim_max);
}
其中rlimit是一个结构体：
C
struct rlimit {
rlim_t rlim_cur; /* Soft limit /
rlim_t rlim_max; / Hard limit (ceiling for rlim_cur) /
};
1
2
3
4
structrlimit {
rlim_t rlim_cur; / Soft limit /
rlim_trlim_max; / Hard limit (ceiling for rlim_cur) */
};
每种资源有软限制和硬限制，并且可以通过setrlimit对rlimit进行有条件设置。其中硬限制作为软限制的上限，非特权进程只能设置软限制，且不能超过硬限制。
3 实现malloc
3.1 玩具实现
在正式开始讨论malloc的实现前，我们可以利用上述知识实现一个简单但几乎没法用于真实的玩具malloc，权当对上面知识的复习：
C
/* 一个玩具malloc */
#include <sys/types.h>
#include
void *malloc(size_t size)
{
void *p;
p = sbrk(0);
if (sbrk(size) == (void *)-1)
return NULL;
return p;
}
1
2
3
4
5
6
7
8
9
10
11
/* 一个玩具malloc */
#include <sys/types.h>
#include
void *malloc(size_tsize)
{
void*p;
p= sbrk(0);
if(sbrk(size)== (void*)-1)
returnNULL;
returnp;
}
这个malloc每次都在当前break的基础上增加size所指定的字节数，并将之前break的地址返回。这个malloc由于对所分配的内存缺乏记录，不便于内存释放，所以无法用于真实场景。
3.2 正式实现
下面严肃点讨论malloc的实现方案。
3.2.1 数据结构
首先我们要确定所采用的数据结构。一个简单可行方案是将堆内存空间以块（Block）的形式组织起来，每个块由meta区和数据区组成，meta区记录数据块的元信息（数据区大小、空闲标志位、指针等等），数据区是真实分配的内存区域，并且数据区的第一个字节地址即为malloc返回的地址。
可以用如下结构体定义一个block：
C
typedef struct s_block t_block;
struct s_block {
size_t size; / 数据区大小 /
t_block next; / 指向下个块的指针 /
int free; / 是否是空闲块 /
int padding; / 填充4字节，保证meta块长度为8的倍数 /
char data[1] / 这是一个虚拟字段，表示数据块的第一个字节，长度不应计入meta /
};
1
2
3
4
5
6
7
8
typedefstruct s_blockt_block;
struct s_block{
size_tsize; /* 数据区大小 /
t_block next;/ 指向下个块的指针 /
intfree; / 是否是空闲块 /
intpadding; / 填充4字节，保证meta块长度为8的倍数 /
chardata[1] / 这是一个虚拟字段，表示数据块的第一个字节，长度不应计入meta */
};
由于我们只考虑64位机器，为了方便，我们在结构体最后填充一个int，使得结构体本身的长度为8的倍数，以便内存对齐。示意图如下：
3.2.2 寻找合适的block
现在考虑如何在block链中查找合适的block。一般来说有两种查找算法：
First fit：从头开始，使用第一个数据区大小大于要求size的块所谓此次分配的块
Best fit：从头开始，遍历所有块，使用数据区大小大于size且差值最小的块作为此次分配的块
两种方法各有千秋，best fit具有较高的内存使用率（payload较高），而first fit具有更好的运行效率。这里我们采用first fit算法。
C
/* First fit /
t_block find_block(t_block *last, size_t size) {
t_block b = first_block;
while(b && !(b->free && b->size >= size)) {
*last = b;
b = b->next;
}
return b;
}
1
2
3
4
5
6
7
8
9
/ First fit /
t_block find_block(t_blocklast,size_t size){
t_blockb =first_block;
while(b&& !(b->free&& b->size>= size)){
*last= b;
b= b->next;
}
returnb;
}
find_block从frist_block开始，查找第一个符合要求的block并返回block起始地址，如果找不到这返回NULL。这里在遍历时会更新一个叫last的指针，这个指针始终指向当前遍历的block。这是为了如果找不到合适的block而开辟新block使用的，具体会在接下来的一节用到。
3.2.3 开辟新的block
如果现有block都不能满足size的要求，则需要在链表最后开辟一个新的block。这里关键是如何只使用sbrk创建一个struct：
C
#define BLOCK_SIZE 24 /* 由于存在虚拟的data字段，sizeof不能正确计算meta长度，这里手工设置 */
t_block extend_heap(t_block last, size_t s) {
t_block b;
b = sbrk(0);
if(sbrk(BLOCK_SIZE + s) == (void )-1)
return NULL;
b->size = s;
b->next = NULL;
if(last)
last->next = b;
b->free = 0;
return b;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define BLOCK_SIZE 24 / 由于存在虚拟的data字段，sizeof不能正确计算meta长度，这里手工设置 */
t_blockextend_heap(t_blocklast,size_ts){
t_blockb;
b= sbrk(0);
if(sbrk(BLOCK_SIZE+ s)== (void*)-1)
returnNULL;
b->size= s;
b->next= NULL;
if(last)
last->next= b;
b->free= 0;
returnb;
}
3.2.4 分裂block
First fit有一个比较致命的缺点，就是可能会让很小的size占据很大的一块block，此时，为了提高payload，应该在剩余数据区足够大的情况下，将其分裂为一个新的block，示意如下：
实现代码：
C
void split_block(t_block b, size_t s) {
t_block new;
new = b->data + s;
new->size = b->size - s - BLOCK_SIZE ;
new->next = b->next;
new->free = 1;
b->size = s;
b->next = new;
}
1
2
3
4
5
6
7
8
9
voidsplit_block(t_blockb,size_ts){
t_block new;
new= b->data+ s;
new->size= b->size- s- BLOCK_SIZE;
new->next= b->next;
new->free= 1;
b->size= s;
b->next= new;
}
3.2.5 malloc的实现
有了上面的代码，我们可以利用它们整合成一个简单但初步可用的malloc。注意首先我们要定义个block链表的头first_block，初始化为NULL；另外，我们需要剩余空间至少有BLOCK_SIZE + 8才执行分裂操作。
由于我们希望malloc分配的数据区是按8字节对齐，所以在size不为8的倍数时，我们需要将size调整为大于size的最小的8的倍数：
C
size_t align8(size_t s) {
if(s & 0x7 == 0)
return s;
return ((s » 3) + 1) « 3;
}
1
2
3
4
5
size_talign8(size_ts){
if(s& 0x7== 0)
returns;
return((s» 3)+ 1)« 3;
}
C
#define BLOCK_SIZE 24
void *first_block=NULL;
/* other functions… */
void malloc(size_t size) {
t_block b, last;
size_t s;
/ 对齐地址 /
s = align8(size);
if(first_block) {
/ 查找合适的block /
last = first_block;
b = find_block(&last, s);
if(b) {
/ 如果可以，则分裂 /
if ((b->size - s) >= ( BLOCK_SIZE + 8))
split_block(b, s);
b->free = 0;
} else {
/ 没有合适的block，开辟一个新的 */
b = extend_heap(last, s);
if(!b)
return NULL;
}
} else {
b = extend_heap(NULL, s);
if(!b)
return NULL;
first_block = b;
}
return b->data;
}
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
#define BLOCK_SIZE 24
void *first_block=NULL;
/* other functions… */
void malloc(size_tsize){
t_blockb,last;
size_ts;
/ 对齐地址 /
s= align8(size);
if(first_block){
/ 查找合适的block /
last= first_block;
b= find_block(&last,s);
if(b){
/ 如果可以，则分裂 /
if((b->size- s)>= (BLOCK_SIZE +8))
split_block(b,s);
b->free= 0;
}else {
/ 没有合适的block，开辟一个新的 */
b= extend_heap(last,s);
if(!b)
returnNULL;
}
}else {
b= extend_heap(NULL,s);
if(!b)
returnNULL;
first_block= b;
}
returnb->data;
}
3.2.6 calloc的实现
有了malloc，实现calloc只要两步：
malloc一段内存
将数据区内容置为0
由于我们的数据区是按8字节对齐的，所以为了提高效率，我们可以每8字节一组置0，而不是一个一个字节设置。我们可以通过新建一个size_t指针，将内存区域强制看做size_t类型来实现。
C
void calloc(size_t number, size_t size) {
size_t *new;
size_t s8, i;
new = malloc(number * size);
if(new) {
s8 = align8(number * size) » 3;
for(i = 0; i < s8; i++)
new[i] = 0;
}
return new;
}
1
2
3
4
5
6
7
8
9
10
11
voidcalloc(size_tnumber,size_t size){
size_tnew;
size_ts8,i;
new= malloc(number size);
if(new){
s8= align8(number* size)» 3;
for(i= 0;i <s8;i++)
new[i]= 0;
}
returnnew;
}
3.2.7 free的实现
free的实现并不像看上去那么简单，这里我们要解决两个关键问题：
如何验证所传入的地址是有效地址，即确实是通过malloc方式分配的数据区首地址
如何解决碎片问题
首先我们要保证传入free的地址是有效的，这个有效包括两方面：
地址应该在之前malloc所分配的区域内，即在first_block和当前break指针范围内
这个地址确实是之前通过我们自己的malloc分配的
第一个问题比较好解决，只要进行地址比较就可以了，关键是第二个问题。这里有两种解决方案：一是在结构体内埋一个magic number字段，free之前通过相对偏移检查特定位置的值是否为我们设置的magic number，另一种方法是在结构体内增加一个magic pointer，这个指针指向数据区的第一个字节（也就是在合法时free时传入的地址），我们在free前检查magic pointer是否指向参数所指地址。这里我们采用第二种方案：
首先我们在结构体中增加magic pointer（同时要修改BLOCK_SIZE）：
C
typedef struct s_block t_block;
struct s_block {
size_t size; / 数据区大小 /
t_block next; / 指向下个块的指针 /
int free; / 是否是空闲块 /
int padding; / 填充4字节，保证meta块长度为8的倍数 /
void *ptr; / Magic pointer，指向data /
char data[1] / 这是一个虚拟字段，表示数据块的第一个字节，长度不应计入meta /
};
1
2
3
4
5
6
7
8
9
typedefstruct s_blockt_block;
struct s_block{
size_tsize; /* 数据区大小 /
t_block next;/ 指向下个块的指针 /
intfree; / 是否是空闲块 /
intpadding; / 填充4字节，保证meta块长度为8的倍数 /
voidptr; /* Magic pointer，指向data /
chardata[1] / 这是一个虚拟字段，表示数据块的第一个字节，长度不应计入meta */
};
然后我们定义检查地址合法性的函数：
C
t_block get_block(void *p) {
char *tmp;
tmp = p;
return (p = tmp -= BLOCK_SIZE);
}
int valid_addr(void p) {
if(first_block) {
if(p > first_block && p < sbrk(0)) {
return p == (get_block(p))->ptr;
}
}
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
t_blockget_block(voidp){
char*tmp;
tmp= p;
return(p= tmp-= BLOCK_SIZE);
}
intvalid_addr(void*p){
if(first_block){
if(p> first_block&& p< sbrk(0)){
returnp ==(get_block(p))->ptr;
}
}
return0;
}
当多次malloc和free后，整个内存池可能会产生很多碎片block，这些block很小，经常无法使用，甚至出现许多碎片连在一起，虽然总体能满足某此malloc要求，但是由于分割成了多个小block而无法fit，这就是碎片问题。
一个简单的解决方式时当free某个block时，如果发现它相邻的block也是free的，则将block和相邻block合并。为了满足这个实现，需要将s_block改为双向链表。修改后的block结构如下：
C
typedef struct s_block t_block;
struct s_block {
size_t size; / 数据区大小 /
t_block prev; / 指向上个块的指针 /
t_block next; / 指向下个块的指针 /
int free; / 是否是空闲块 /
int padding; / 填充4字节，保证meta块长度为8的倍数 /
void *ptr; / Magic pointer，指向data /
char data[1] / 这是一个虚拟字段，表示数据块的第一个字节，长度不应计入meta /
};
1
2
3
4
5
6
7
8
9
10
typedefstruct s_blockt_block;
struct s_block{
size_tsize; /* 数据区大小 /
t_block prev;/ 指向上个块的指针 /
t_blocknext;/ 指向下个块的指针 /
intfree; / 是否是空闲块 /
intpadding; / 填充4字节，保证meta块长度为8的倍数 /
voidptr; /* Magic pointer，指向data /
chardata[1] / 这是一个虚拟字段，表示数据块的第一个字节，长度不应计入meta */
};
合并方法如下：
C
t_block fusion(t_block b) {
if (b->next && b->next->free) {
b->size += BLOCK_SIZE + b->next->size;
b->next = b->next->next;
if(b->next)
b->next->prev = b;
}
return b;
}
1
2
3
4
5
6
7
8
9
t_blockfusion(t_blockb){
if(b->next&& b->next->free){
b->size+= BLOCK_SIZE+ b->next->size;
b->next= b->next->next;
if(b->next)
b->next->prev= b;
}
returnb;
}
有了上述方法，free的实现思路就比较清晰了：首先检查参数地址的合法性，如果不合法则不做任何事；否则，将此block的free标为1，并且在可以的情况下与后面的block进行合并。如果当前是最后一个block，则回退break指针释放进程内存，如果当前block是最后一个block，则回退break指针并设置first_block为NULL。实现如下：
C
void free(void p) {
t_block b;
if(valid_addr(p)) {
b = get_block(p);
b->free = 1;
if(b->prev && b->prev->free)
b = fusion(b->prev);
if(b->next)
fusion(b);
else {
if(b->prev)
b->prev->prev = NULL;
else
first_block = NULL;
brk(b);
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
voidfree(voidp){
t_blockb;
if(valid_addr(p)){
b= get_block(p);
b->free= 1;
if(b->prev&& b->prev->free)
b= fusion(b->prev);
if(b->next)
fusion(b);
else{
if(b->prev)
b->prev->prev= NULL;
else
first_block= NULL;
brk(b);
}
}
}
3.2.8 realloc的实现
为了实现realloc，我们首先要实现一个内存复制方法。如同calloc一样，为了效率，我们以8字节为单位进行复制：
C
void copy_block(t_block src, t_block dst) {
size_t sdata, *ddata;
size_t i;
sdata = src->ptr;
ddata = dst->ptr;
for(i = 0; (i * 8) < src->size && (i * 8) < dst->size; i++)
ddata[i] = sdata[i];
}
1
2
3
4
5
6
7
8
voidcopy_block(t_blocksrc,t_block dst){
size_tsdata,ddata;
size_ti;
sdata= src->ptr;
ddata= dst->ptr;
for(i= 0;(i 8)< src->size&& (i* 8)< dst->size;i++)
ddata[i]= sdata[i];
}
然后我们开始实现realloc。一个简单（但是低效）的方法是malloc一段内存，然后将数据复制过去。但是我们可以做的更高效，具体可以考虑以下几个方面：
如果当前block的数据区大于等于realloc所要求的size，则不做任何操作
如果新的size变小了，考虑split
如果当前block的数据区不能满足size，但是其后继block是free的，并且合并后可以满足，则考虑做合并
下面是realloc的实现：
C
void realloc(void *p, size_t size) {
size_t s;
t_block b, new;
void *newp;
if (!p)
/ 根据标准库文档，当p传入NULL时，相当于调用malloc /
return malloc(size);
if(valid_addr(p)) {
s = align8(size);
b = get_block(p);
if(b->size >= s) {
if(b->size - s >= (BLOCK_SIZE + 8))
split_block(b,s);
} else {
/ 看是否可进行合并 /
if(b->next && b->next->free
&& (b->size + BLOCK_SIZE + b->next->size) >= s) {
fusion(b);
if(b->size - s >= (BLOCK_SIZE + 8))
split_block(b, s);
} else {
/ 新malloc /
newp = malloc (s);
if (!newp)
return NULL;
new = get_block(newp);
copy_block(b, new);
free(p);
return(newp);
}
}
return (p);
}
return NULL;
}
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
voidrealloc(voidp,size_t size){
size_ts;
t_blockb,new;
voidnewp;
if(!p)
/* 根据标准库文档，当p传入NULL时，相当于调用malloc /
returnmalloc(size);
if(valid_addr(p)){
s= align8(size);
b= get_block(p);
if(b->size>= s){
if(b->size- s>= (BLOCK_SIZE+ 8))
split_block(b,s);
}else {
/ 看是否可进行合并 /
if(b->next&& b->next->free
&&(b->size+ BLOCK_SIZE+ b->next->size)>= s){
fusion(b);
if(b->size- s>= (BLOCK_SIZE+ 8))
split_block(b,s);
}else {
/ 新malloc */
newp= malloc(s);
if(!newp)
returnNULL;
new= get_block(newp);
copy_block(b,new);
free(p);
return(newp);
}
}
return(p);
}
returnNULL;
}
3.3 遗留问题和优化
以上是一个较为简陋，但是初步可用的malloc实现。还有很多遗留的可能优化点，例如：
在分配较大快内存时，考虑使用mmap而非sbrk，这通常更高效
可以考虑维护多个链表而非单个，每个链表中的block大小均为一个范围内，例如8字节链表、16字节链表、24-32字节链表等等。此时可以根据size到对应链表中做分配，可以有效减少碎片，并提高查询block的速度
可以考虑链表中只存放free的block，而不存放已分配的block，可以减少查找block的次数，提高效率
还有很多可能的优化，这里不一一赘述。下面附上一些参考文献，有兴趣的同学可以更深入研究。
4 其它参考
这篇文章大量参考了A malloc Tutorial，其中一些图片和代码直接引用了文中的内容，这里特别指出
Computer Systems: A Programmer’s Perspective, 2/E一书有许多值得参考的地方
关于Linux的虚拟内存模型，Anatomy of a Program in Memory是很好的参考资料，另外作者还有一篇How the Kernel Manages Your Memory对于Linux内核中虚拟内存管理的部分有很好的讲解
对于真实世界的malloc实现，可以参考glic的实现
https://blog.csdn.net/yeditaba/article/details/53443792
一、为什么要使用内存池技术呢
主要有两个原因：1、减少new、delete次数，减少运行时间；2、避免内存碎片。
1、效率
c语言中使用malloc/free来分配内存，c++中使用new/delete来分配内存，他们的内存申请与释放都是与操作系统进行交互的。具体的内容在严蔚敏数据结构的第八章有相关讲述，主要就是系统要维护一个内存链表，当有一个内存申请过来时，根据相应的分配算法在链表中找个一个合适的内存分配给它。这些算法有的是分配最先找到的不小于申请内存的内存块，有的是分配最大的内存块，有的是分配最接近申请内存大小的内存块。分配的内存块可能会大于所申请的内存大小，这样还有进行切割，将剩余的内存插入到空闲链表中。当释放的时候，系统可能要对内存进行整理，判断free的内存块的前后是否有空闲，若有的话还要进行合并。此外，new/delete还要考虑多线程的情况。总之一句话，调用库中的内存分配函数，十分的耗时~~
2、内存碎片
什么是内存碎片内，从字面意思就很好理解了，就是内存不再是一整块的了，而是碎了。因为连续的这种new/delete操作，一大块内存肯能就被分割成小的内存分配出去了，这些小的内存都是不连续的。当你再去分配大的连续内存的时候，尽管剩余内存的总和可能大于所要分配的内存大小，但系统就找不到连续的内存了，所以导致分配错误。malloc的时候会导致返回NULL，而new的时候再vc6.0中返回NULL，vs2003以上则是抛出异常。
二、原理
要解决上述两个问题，最好的方法就是内存池技术。具体方法就是大小固定、提前申请、重复利用。
因为内存的申请和释放是很低效的，所以我们只在开始时申请一块大的内存（在该块内存不够用时在二次分配），然后每次需要时都从这块内存中取出，并标记下这块内存被用了，释放时标记此内存被释放了。释放时，并不真的把内存释放给操作系统，只要在一大块内存都空闲的时候，才释放给操作系统。这样，就减少了new/delete的操作次数，从而提高了效率。
在调用内存分配函数的时候，大部分时间所分配的内存大小都是一定的，所以可以采用每次都分配固定大小的内存块，这样就避免了内存碎片产生的可能。
三、具体实现
我所采用的内存池的构造方法完全是按照文章1所介绍的方法，内存池的结构图如下：
如图所示MemoryPool是一个内存池类，其中pBlock是一个指向了一个内存块的指针，nUintSzie是分配单元的大小，nInitSize是第一次分配时向系统申请的内存的大小，nGrouSize是后面每次向系统申请的内存的大小。
MemoryBloc代表一个内存块单元，它有两部分构成，一部分时MemoryBlock类的大小，另一部分则是实际的内存部分。一个MemoryBlock的内存是在重载的new操作符中分配的，如下所示：
void* MemoryBlock::operator new(size_t, int nUnitSize,int nUnitAmount )
{
return ::operator new( sizeof(MemoryBlock) + nUnitSize * nUnitAmount );
}
MemoryBlock内中，nSize代码该内存块的大小（系统分配内存大小-MemoryBlock类的大小），nFree是空闲内存单元的个数，nFirst代表的是下一个要分配的内存单元的序号。aData是用来记录待分配内存的位置的。因为要分配的内存是在new中一起向系统申请的，并没有一个指针指向这块内存的位置，但它的位置就在MemoryBlock这个类的地址开始的，所以可以用MemoryBlock的最后一个成员的位置来表示待分配内存的位置。
带分配内存中，是以nUnitSize为单位的，一个内存单元的头两个字节都记录了下一个要分配的内存单元的序号，序号从0开始。这样实际也就构成了一个数组链表。由MemoryBlock的构造函数来完成这个链表的初始化工作：
MemoryBlock::MemoryBlock( int nUnitSize,int nUnitAmount )
: nSize (nUnitAmount * nUnitSize),
nFree (nUnitAmount - 1), //构造的时候，就已将第一个单元分配出去了，所以减一
nFirst (1), //同上
pNext (NULL)
{
//初始化数组链表，将每个分配单元的下一个分配单元的序号写在当前单元的前两个字节中
char* pData = aData;
//最后一个位置不用写入
for( int i = 1; i < nSize - 1; i++)
{
((USHORT)pData) = i;
pData += nUnitSize;
}
}
在MemoryPool的Alloc（）中，遍历block链表，找到nFree大于0的block，从其上分配内存单元。然后将nFree减一，修改nFirst的值。
在MemoryPool的Free（pFree）函数中，根据pFree的值，找到它所在的内存块，然后将它的序号作为nFirst的值（因为它绝对是空闲的），在pFree的头两个字节中写入原来nFirst的值。然后要判断，该block是否全部为free，方法是检测nFree * nUnitSize == nSize。若是，则向系统释放内存，若不是，则将该block放到链表的头部，因为该block上一定含有空隙的内存单元，这样可以减少分配时遍历链表所消耗的时间。
四、使用
内存池一般都是作为一个类的静态成员，或者全局变量。使用时，重载new操作符，使其到MemoryPool中去分配内存，而不是向系统申请。这样，一个类的所以对象都在一个内存池中开辟空间。
void CTest::operator delete( void* pTest )
{
Pool.Free(pTest);
}
void* CTest::operator new(size_t)
{
return (CTest*)Pool.Alloc();
}
五、代码
MemoryPool.h
View Code
MemoryPool.cpp
View Code
CTest.cpp
View Code
六、问题
在编写代码时，遇到了一些小问题，现与大家分享如下：
1、重载new操作符时，编译器要求是第一个参数必须是size_t，返回值必须是void;free的第一个参数必须是void.
2、一般要在类的成员中重载new操作符，而不要重载全局的new操作符。
3、一个类中要是重载了一个new操作符，一定要有一个相应类型的delete操作符，可以什么都不干，但必须有，否则在构造函数失败时，找不到对应的delete函数。
例如：
1
2
static void* operator new (size_t,int nUnitSize,int nUnitAmount);
static void operator delete (void* ,int nUnitSize,int nUnitAmount){};
4、带参数的new操作符
pBlock = (MemoryBlock*)new(nUnitSize,nInitSize) MemoryBlock(nUnitSize,nUnitSize);
第一个nUnitSize nInitSize是new操作符的参数，该new操作符是new了一个MemoryBlock对象，在new返回的地址上构造MemoryBlock的对象。
5、如果在类的内部不能进行静态成员的定义的话，可以只在内部进行声明，在外部定义：
MemoryPool CTest::Pool(sizeof(CTest));
1.当开辟的空间小于128k时，调用brk()函数，malloc的底层实现是系统调用函数brk(),其主要移动指针_enddata（注意此时的_enddata指的是Linux地址空间中堆段的末尾地址。
而不是数据段的末尾地址）来开辟空间、
2.当开辟的空间大于128k时，mmap()系统调用函数来在虚拟地址空间中（堆和栈中间，称为文件映射区域的地方）找一块空间来开辟。
下面是具体的内容，希望有助于读者分析：
当一个进程发生缺页中断的时候，进程会陷入内核态，执行以下操作：
1、检查要访问的虚拟地址是否合法
2、查找/分配一个物理页
3、填充物理页内容（读取磁盘，或者直接置0，或者啥也不干）
4、建立映射关系（虚拟地址到物理地址）
重新执行发生缺页中断的那条指令
如果第3步，需要读取磁盘，那么这次缺页中断就是majflt，否则就是minflt。
内存分配的原理
从操作系统角度来看，进程分配内存有两种方式，分别由两个系统调用完成：brk和mmap（不考虑共享内存）。
1、brk是将数据段(.data)的最高地址指针_edata往高地址推；
2、mmap是在进程的虚拟地址空间中（堆和栈中间，称为文件映射区域的地方）找一块空闲的虚拟内存。
这两种方式分配的都是虚拟内存，没有分配物理内存。在第一次访问已分配的虚拟地址空间的时候，发生缺页中断，操作系统负责分配物理内存，然后建立虚拟内存和物理内存之间的映射关系。
在标准C库中，提供了malloc/free函数分配释放内存，这两个函数底层是由brk，mmap，munmap这些系统调用实现的。
下面以一个例子来说明内存分配的原理：
情况一、malloc小于128k的内存，使用brk分配内存，将_edata往高地址推(只分配虚拟空间，不对应物理内存(因此
没有初始化)，第一次读/写数据时，引起内核缺页中断，内核才分配对应的物理内存，然后虚拟地址空间建立映射关
系)，如下图：
1、进程启动的时候，其（虚拟）内存空间的初始布局如图1所示。
其中，mmap内存映射文件是在堆和栈的中间（例如libc-2.2.93.so，其它数据文件等），为了简单起见，省略了 内存映射文件。
_edata指针（glibc里面定义）指向数据段的最高地址。
2、进程调用A=malloc(30K)以后，内存空间如图2
malloc函数会调用brk系统调用，将_edata指针往高地址推30K，就完成虚拟内存分配。
你可能会问：只要把_edata+30K就完成内存分配了？
事实是这样的，_edata+30K只是完成虚拟地址的分配，A这块内存现在还是没有物理页与之对应的，等到进程第
一次读写A这块内存的时候，发生缺页中断，这个时候，内核才分配A这块内存对应的物理页。也就是说，如果用
malloc分配了A这块内容，然后从来不访问它，那么，A对应的物理页是不会被分配的。
3、进程调用B=malloc(40K)以后，内存空间如图3。
情况二、malloc大于128k的内存，使用mmap分配内存，在堆和栈之间找一块空闲内存分配(对应独立内存，而且初始化为0)，如下图：
4、进程调用C=malloc(200K)以后，内存空间如图4：
默认情况下，malloc函数分配内存，如果请求内存大于128K（可由M_MMAP_THRESHOLD选项调节），那就
不是去推_edata指针了，而是利用mmap系统调用，从堆和栈的中间分配一块虚拟内存。
这样子做主要是因为::
brk分配的内存需要等到高地址内存释放以后才能释放（例如，在B释放之前，A是不可能释放的，这就是内存碎
片产生的原因，什么时候紧缩看下面），而mmap分配的内存可以单独释放。
当然，还有其它的好处，也有坏处，再具体下去，有兴趣的同学可以去看glibc里面malloc的代码了。
5、进程调用D=malloc(100K)以后，内存空间如图5；
6、进程调用free(C)以后，C对应的虚拟内存和物理内存一起释放。
7、进程调用free(B)以后，如图7所示：
B对应的虚拟内存和物理内存都没有释放，因为只有一个_edata指针，如果往回推，那么D这块内存怎么办呢？ 当然，B这块内存，是可以重用的，如果这个时候再来一个40K的请求，那么malloc很可能就把B这块内存返回回去了。 8、进程调用free(D)以后，如图8所示：
B和D连接起来，变成一块140K的空闲内存。
9、默认情况下：
当最高地址空间的空闲内存超过128K（可由M_TRIM_THRESHOLD选项调节）时，执行内存紧缩操作
（trim）。在上一个步骤free的时候，发现最高地址空闲内存超过128K，于是内存紧缩，变成图9所示。
这就是malloc的底层实现。
参考：《深入理解计算机系统》 本文需要比较多的前言基础，在前面的文章中都有体现
malloc实现原理 这位大佬写得也很不错，部分内容参考这里。
要看这个malloc,得先了解静态内存分配和动态内存分配。下面是这两者的区别：（静态内存分配在书中一直没找到。。）
内存的静态分配和动态分配的区别主要是两个：
一是时间不同。静态分配发生在程序编译和连接的时候。动态分配则发生在程序调入和执行的时候。
二是空间不同。堆都是动态分配的，没有静态分配的堆。栈有2种分配方式：静态分配和动态分配。静态分配是编译器完成的，比如局部变量的分配。动态分配由函数malloc进行分配。不过栈的动态分配和堆不同，他的动态分配是由编译器进行释放，无需我们手工实现。
对于一个进程的内存空间而言，可以在逻辑上分成3个部份：代码区，静态数据区和动态数据区。动态数据区一般就是“堆栈”。“栈(stack)”和“堆(heap)”是两种不同的动态数据区，栈是一种线性结构，堆是一种链式结构。进程的每个线程都有私有的“栈”，所以每个线程虽然代码一样，但本地变量的数据都是互不干扰。一个堆栈可以通过“基地址”和“栈顶”地址来描述。全局变量和静态变量分配在静态数据区，本地变量分配在动态数据区，即堆栈中。程序通过堆栈的基地址和偏移量来访问本地变量。
总结一下就是，动态内存分配可以在程序运行的时候动态地获取和使用内存，然后是动态内存分配的区间不同。
动态内存分配器更方便，也有更好的移植性。它维护者一个进程的虚拟内存区域，称为堆（heap）。它在未初始化数据的上边，然后向上生长（即向更高的地址），对于每个进程来说，内核维护着一个brk(break)变量，它指向堆的顶部，如下图：
分配器将堆视为一组不同大小的块（block）的集合来维护。每个块就是一个连续的虚拟内存片（chunk）,要么是已分配的，要么是空闲的。已分配的块显式地保留为供程序使用。空闲块可用来分配。空闲块保持空闲，直到它显式地被应用所分配。一个已分配的块保持已分配状态，直到它被释放，这种释放要么是应用程序显式执行的，要么是内存分配器自身隐式执行。（忽然很庆幸自己学习了一波多级页表，所以对里面这个模型比较容易理解 可参考 何柄融：linux 多级页表 cpu取虚拟地址 TLB 特别是里面的 chunk ）
然后动态的分配器有两种基本风格：显式和隐式。两种风格都要求应用显式地分配块。它们的不同之处在于由哪个实体来负责释放已经分配的块。
显式分配器：要求应用显式地释放任何已经分配的块。例如c标准库中的malloc. c程序通过调用malloc函数来分配一个块，并通过调用free函数来释放一个块。c++中的new和delete操作符和c中搞得malloc和free相当。（就是自己手动释放内存）
隐式分配器：要求分配器检测一个已分配块何时不再被程序所使用，那么就释放这个块。隐式分配器也叫做垃圾收集器，而自动释放未使用的已分配的块的过程叫做垃圾收集。例如java，ML，Lisp之类的高级语言就依赖垃圾收集来释放已分配的块。（就是不用程序猿自己手动释放内存）
例如：图形处理密集的应用程序就经常使用标准分配器来要求获得一大块的虚拟内存，然后使用与应用相关的分配器来管理内存，在该快中创建和销毁图形的节点。（总不能自己手动释放这些内存吧，那多难受啊）
然后我们先讨论显式内存分配器：
c标准库提供了一个称为malloc程序包的显式分配器。程序通过调用malloc函数来从堆中分配块。
void *malloc(size_t size) ;
返回：若成功则为已分配块的指针，若出错则为null.
malloc函数返回一个指针，指向大小至少为size字节的内存块，这个块会为可能包含在这个块内的任何数据对象类型做对齐。（这个会根据系统位数返回相应规格的地址）
如果malloc遇到问题（例如，程序要求的内存块比可用的虚拟内存还要大），那么它就返回null.并设置errno。malloc不初始化它返回的内存。
下面很大一部分参考自文首链接：malloc实现原理
然后来深入了解malloc:
先了解：brk()和sbrk()函数
int brk( const void addr )
void sbrk ( intptr_t incr );
这两个函数的作用主要是扩展heap的上界brk。第一个函数的参数为设置的新的brk上界地址，如果成功返回0，失败返回-1。第二个函数的参数为需要申请的内存的大小，然后返回heap新的上界brk地址。如果sbrk的参数为0，则返回的为原来的brk地址。
然后来了解：mmap
mmap函数第一种用法是映射磁盘文件到内存中（前面讲进程通信的时候讲过）；而malloc使用的mmap函数的第二种用法，即匿名映射，匿名映射不映射磁盘文件，而是向映射区申请一块内存。
void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);
int munmap(void *addr, size_t length);
这里不重复啰嗦了，对mmap不熟悉的同学可以参考何柄融：linux 进程通信方式 pipe无名管道 fifo有名管道 共享内存映射 socket 消息队列 或者文章最前面的连接（感觉我写得比较好，哈哈）
这里要注意的是fd参数，fd为映射的文件描述符，如果是匿名映射，可以设为-1；
当申请小内存的时，malloc使用sbrk分配内存；当申请大内存时，使用mmap函数申请内存；但是这只是分配了虚拟内存，还没有映射到物理内存，当访问申请的内存时，才会因为缺页异常，内核分配物理内存。
然后接着深入：
由于brk/sbrk/mmap属于系统调用，如果每次申请内存，都调用这三个函数中的一个，那么每次都要产生系统调用开销（即cpu从用户态切换到内核态的上下文切换，这里要保存用户态数据，等会还要切换回用户态），这是非常影响性能的；其次，这样申请的内存容易产生碎片，因为堆是从低地址到高地址，如果低地址的内存没有被释放，高地址的内存就不能被回收。
鉴于此，malloc采用的是内存池的实现方式，malloc内存池实现方式更类似于STL分配器和memcached的内存池，先申请一大块内存，然后将内存分成不同大小的内存块，然后用户申请内存时，直接从内存池中选择一块相近的内存块即可。
由于文首的链接里没图，所以从 glibc内存管理那些事儿 这个链接里盗来几张图，而且这个链接讲的内存池也很不错。
先看内存池的整体结构：（感觉下面的都很核心！）
（第一眼看上去有没有很像哈希表？哈哈。）
malloc将内存分成了大小不同的chunk，然后通过bins来组织起来。malloc将相似大小的chunk（图中可以看出同一链表上的chunk大小差不多）用双向链表链接起来，这样一个链表被称为一个bin。malloc一共维护了128个bin，并使用一个数组来存储这些bin。数组中第一个为unsorted bin,数组从2开始编号，前64个bin为small bins，同一个small bin中的chunk具有相同的大小，两个相邻的small bin中的chunk大小相差8bytes。small bins后面的bin被称作large bins。large bins中的每一个bin分别包含了一个给定范围内的chunk，其中的chunk按大小序排列。large bin的每个bin相差64字节。（这里我本来想计算一下加深理解的，8x64=512b, 64x64=4096b 然后加起来发现和图片里的不太匹配，所以不知道自己哪里理解错了？可是前面的88又对啊，怎么后面就12k那么大呢？）
malloc除了有unsorted bin，small bin,large bin三个bin之外，还有一个fast bin。一般的情况是,程序在运行时会经常需要申请和释放一些较小的内存空间。当分配器合并了相邻的几个小的 chunk 之后,也许马上就会有另一个小块内存的请求,这样分配器又需要从大的空闲内存中切分出一块,这样无疑是比较低效的,故而,malloc 中在分配过程中引入了 fast bins,不大于 max_fast(默认值为 64B)的 chunk 被释放后,首先会被放到 fast bins中,fast bins 中的 chunk 并不改变它的使用标志 P。这样也就无法将它们合并,当需要给用户分配的 chunk 小于或等于 max_fast 时,malloc 首先会在 fast bins 中查找相应的空闲块,然后才会去查找 bins 中的空闲 chunk。在某个特定的时候,malloc 会遍历 fast bins 中的 chunk,将相邻的空闲 chunk 进行合并,并将合并后的 chunk 加入 unsorted bin 中,然后再将 usorted bin 里的 chunk 加入 bins 中。
unsorted bin 的队列使用 bins 数组的第一个,如果被用户释放的 chunk 大于 max_fast,或者 fast bins 中的空闲 chunk 合并后,这些 chunk 首先会被放到 unsorted bin 队列中,在进行 malloc 操作的时候,如果在 fast bins 中没有找到合适的 chunk,则malloc 会先在 unsorted bin 中查找合适的空闲 chunk,然后才查找 bins。如果 unsorted bin 不能满足分配要求。 malloc便会将 unsorted bin 中的 chunk 加入 bins 中。然后再从 bins 中继续进行查找和分配过程。从这个过程可以看出来,unsorted bin 可以看做是 bins 的一个缓冲区,增加它只是为了加快分配的速度。（其实感觉在这里还利用了局部性原理，常用的内存块大小差不多，从unsorted bin这里取就行了，这个和TLB之类的都是异曲同工之妙啊！）
除了上述四种bins之外，malloc还有三种内存区。
当fast bin和bins都不能满足内存需求时，malloc会设法在top chunk中分配一块内存给用户；top chunk为在mmap区域分配一块较大的空闲内存模拟sub-heap。（比较大的时候）
当chunk足够大，fast bin和bins都不能满足要求，甚至top chunk都不能满足时，malloc会从mmap来直接使用内存映射来将页映射到进程空间，这样的chunk释放时，直接解除映射，归还给操作系统。（极限大的时候）
Last remainder是另外一种特殊的chunk，就像top chunk和mmaped chunk一样，不会在任何bins中找到这种chunk。当需要分配一个small chunk,但在small bins中找不到合适的chunk，如果last remainder chunk的大小大于所需要的small chunk大小，last remainder chunk被分裂成两个chunk，其中一个chunk返回给用户，另一个chunk变成新的last remainder chunk。（这个应该是fast bins中也找不到合适的时候，用于极限小的）
malloc内存分配（下面算是正常一般的情况了）
一开始时，brk和start_brk是相等的，这时实际heap大小为0；如果第一次用户请求的内存大小小于mmap分配阈值，则malloc会申请(chunk_size+128kb) align 4kb大小的空间作为初始的heap。初始化heap之后，第二次申请的内存如果还是小于mmap分配阈值时，malloc会先查找fast bins,如果不能找到匹配的chunk，则查找small bins。若还是不行，合并fast bins,把chunk 加入到unsorted bin，在unsorted bin中查找，若还是不行，把unsorted bin中的chunk全加入large bins中，并查找large bins。在fast bins和small bins中查找都需要精确匹配，而在large bins中查找时，则遵循”smalest-first,best-fit”的原则，不需要精确匹配。
若以上都失败了，malloc则会考虑使用top chunk。若top chunk也不能满足分配，且所需的chunk大小大于mmap分配阈值，则使用mmap进行分配。否则增加heap，增加top chunk，以满足分配要求。
现在来不上chunk的结构图：
malloc利用chunk结构来管理内存块，malloc就是由不同大小的chunk链表组成的。一个使用中的chunk的结构如下图:
malloc会给用户分配的空间的前后加上一些控制信息，用这样的方法来记录分配的信息，以便完成分配和释放工作。chunk指针指向chunk开始的地方,图中的mem指针才是真正返回给用户的内存指针。
chunk 的第二个域的最低一位为 P,它表示前一个块是否在使用中,P 为 0 则表示前一个 chunk 为空闲,这时chunk的第一个域 prev_size 才有效,prev_size 表示前一个 chunk 的 size,程序可以使用这个值来找到前一个 chunk 的开始地址。当 P 为 1 时,表示前一个 chunk 正在使用中,prev_size程序也就不可以得到前一个 chunk 的大小。不能对前一个 chunk 进行任何操作。malloc分配的第一个块总是将 P 设为 1,以防止程序引用到不存在的区域。(这里就很细！)
Chunk 的第二个域的倒数第二个位为 M,他表示当前 chunk 是从哪个内存区域获得的虚拟内存。M 为 1 表示该 chunk 是从 mmap 映射区域分配的,否则是从 heap 区域分配的。
Chunk 的第二个域倒数第三个位为 A,表示该 chunk 属于主分配区或者非主分配区,如果属于非主分配区,将该位置为 1,否则置为 0。
右边图是空闲的chunk:
当chunk空闲时，其M状态是不存在的，只有AP状态，原本是用户数据区的地方存储了四个指针，指针fd指向后一个空闲的chunk,而bk指向前一个空闲的chunk，malloc通过这两个指针将大小相近的chunk连成一个双向链表。在large bin中的空闲chunk，还有两个指针，fd_nextsize和bk_nextsize，用于加快在large bin中查找最近匹配的空闲chunk。不同的chunk链表又是通过bins或者fastbins来组织的。（这里就很符合网上大多数人说的链表理论了）
以上内容大部分参考阿里华庭写的Glibc内存管理，Ptmalloc2源代码分析。
感觉从这个人这里学到了很多东西，是个大佬。
然后结合网上的一般回答：
链接：https://www.nowcoder.com/questionTerminal/5aae63b290c542f0ab0582d293e6c791
来源：牛客网
malloc可以分别由伙伴系统或基于链表的实现；
1、它有一个将可用的内存块连接为一个长长的列表的所谓空闲链表；
2、 调用malloc函数时，它沿连接表寻找一个大到足以满足用户请求所需要的内存块。然后，将该内存块一分为二（一块的大小与用户请求的大小相等，另一块的大小就是剩下的字节）。接下来，将分配给用户的那块内存传给用户，并将剩下的那块（如果有的话）返回到连接表上。
3、 调用free函数时，它将用户释放的内存块连接到空闲链上。到最后，空闲链会被切成很多的小内存片段，如果这时用户申请一个大的内存片段，那么空闲链上可能没有可以满足用户要求的片段了。于是，malloc函数请求延时，并开始在空闲链上翻箱倒柜地检查各内存片段，对它们进行整理，将相邻的小空闲块合并成较大的内存块。
虽然这个答案比较粗糙，但是也有大概的思想了。
malloc和free的实现原理 这位大哥讲得也不错，可以参考一下。
最后可以结合 腾讯云技术社区：十问 Linux 虚拟内存管理 (glibc) (一) 腾讯的这个实践来理论联系实践。下面参考于这个腾讯的链接（建议可以去点个赞）：
malloc 是 glibc 中内存分配函数，也是最常用的动态内存分配函数，其内存必须通过 free 进行释放，否则导致内存泄露。
关于 malloc 获得虚存空间的实现，与 glibc 的版本有关，但大体逻辑是：
若分配内存小于 128k ，调用 sbrk() ，将堆顶指针向高地址移动，获得新的虚存空间。
若分配内存大于 128k ，调用 mmap() ，在文件映射区域中分配匿名虚存空间。
这里讨论的是简单情况，如果涉及并发可能会复杂一些，不过先不讨论。
其中 sbrk 就是修改栈顶指针位置，而 mmap 可用于生成文件的映射以及匿名页面的内存，这里指的是匿名页面。而这个 128k ，是 glibc 的默认配置，可通过函数 mallopt 来设置
接着： VSZ为虚拟内存 RSS为物理内存
VSZ 并不是每次 malloc 后都增长，是与上一节说的堆顶没发生变化有关，因为可重用堆顶内剩余的空间，这样的 malloc 是很轻量快速的。
但如果 VSZ 发生变化，基本与分配内存量相当，因为 VSZ 是计算虚拟地址空间总大小。
RSS 的增量很少，是因为 malloc 分配的内存并不就马上分配实际存储空间，只有第一次使用，如第一次 memset 后才会分配。
由于每个物理内存页面大小是 4k ，不管 memset 其中的 1k 还是 5k 、 7k ，实际占用物理内存总是 4k 的倍数。所以 RSS 的增量总是 4k 的倍数。
因此，不是 malloc 后就马上占用实际内存，而是第一次使用时发现虚存对应的物理页面未分配，产生缺页中断，才真正分配物理页面，同时更新进程页面的映射关系。这也是 Linux 虚拟内存管理的核心概念之一。
http://luodw.cc/2016/02/17/malloc/
实现一个高并发的内存池
- 什么是内存池
1.1 池化技术
池是在计算技术中经常使用的一种设计模式，其内涵在于：将程序中需要经常使用的核心资源先申请出来，放到一个池内，有程序自管理，这样可以提高资源的利用率，也可以保证本程序占有的资源数量，经常使用的池化技术包括内存池，线程池，和连接池等，其中尤以内存池和线程池使用最多。
1.2 内存池
内存池（Memory Pool）是一种动态内存分配与管理技术，通常情况下，程序员习惯直接使用new，delete，malloc,free等API申请和释放内存，这样导致的后果就是：当程序运行的时间很长的时候，由于所申请的内存块的大小不定，频繁使用时会造成大量的内存碎片从而降低程序和操作系统的性能。
内存池则是在真正使用内存之前，先申请分配一大块内存（内存池）留作备用。当程序员申请内存时，从池中取出一块动态分配，当程序员释放时，将释放的内存放回到池内，再次申请，就可以从池里取出来使用，并尽量与周边的空闲内存块合并。若内存池不够时，则自动扩大内存池，从操作系统中申请更大的内存池。
- 为什么需要内存池
2.1 内存碎片问题
造成堆利用率很低的一个主要原因就是内存碎片化。如果有未使用的存储器，但是这块存储器不能用来满足分配的请求，这时候就会产生内存碎片化问题。内存碎片化分为内部碎片和外部碎片。
内碎片
内部碎片是指一个已分配的块比有效载荷大时发生的。(假设以前分配了10个大小的字节，现在只用了5个字节，则剩下的5个字节就会内碎片)。内部碎片的大小就是已经分配的块的大小和他们的有效载荷之差的和。因此内部碎片取决于以前请求内存的模式和分配器实现(对齐的规则)的模式。
外碎片
假设系统依次分配了16byte、8byte、16byte、4byte，还剩余8byte未分配。这时要分配一个24byte的空间，操作系统回收了一个上面的两个16byte，总的剩余空间有40byte，但是却不能分配出一个连续24byte的空间，这就是外碎片问题。
2.2 申请效率问题
例如：我们上学家里给生活费一样，假设一学期的生活费是6000块。
方式1：开学时6000块直接给你，自己保管，自己分配如何花。
方式2：每次要花钱时，联系父母，父母转钱。
同样是6000块钱，第一种方式的效率肯定更高，因为第二种方式跟父母的沟通交互成本太高了。
同样的道理，程序就像是上学的我们，操作系统就像父母，频繁申请内存的场景下，每次需要内存，都像系统申请效率必然有影响。
3.内存池设计
3.1 为什么要使用内存池
解决内碎片问题
由于向内存申请的内存块都是比较大的，所以能够降低外碎片问题
一次性向内存申请一块大的内存慢慢使用，避免了频繁的向内存请求内存操作，提高内存分配的效率
但是内碎片问题无法避免，只能尽可能的降低
3.2 内存池的演变
最简单的内存分配器
做一个链表指向空闲内存，分配就是取出一块来，改写链表，返回，释放就是放回到链表里面，并做好归并。注意做好标记和保护，避免二次释放，还可以花点力气在如何查找最适合大小的内存快的搜索上，减少内存碎片，有空你了还可以把链表换成伙伴算法。
优点： 实现简单
缺点： 分配时搜索合适的内存块效率低，释放回归内存后归并消耗大，实际中不实用。
定长内存分配器
即实现一个 FreeList，每个 FreeList 用于分配固定大小的内存块，比如用于分配 32字节对象的固定内存分配器，之类的。每个固定内存分配器里面有两个链表，OpenList 用于存储未分配的空闲对象，CloseList用于存储已分配的内存对象，那么所谓的分配就是从 OpenList 中取出一个对象放到 CloseList 里并且返回给用户，释放又是从 CloseList 移回到 OpenList。分配时如果不够，那么就需要增长 OpenList：申请一个大一点的内存块，切割成比如 64 个相同大小的对象添加到 OpenList中。这个固定内存分配器回收的时候，统一把先前向系统申请的内存块全部还给系统。
优点： 简单粗暴，分配和释放的效率高，解决实际中特定场景下的问题有效。
缺点： 功能单一，只能解决定长的内存需求，另外占着内存没有释放。
哈希映射的FreeList 池
在定长分配器的基础上，按照不同对象大小(8，16，32，64，128，256，512，1k…64K),构造十多个固定内存分配器，分配内存时根据要申请内存大小进行对齐然后查H表，决定到底由哪个分配器负责，分配后要在内存头部的 header 处写上 cookie，表示由该块内存哪一个分配器分配的，这样释放时候你才能正确归还。如果大于64K，则直接用系统的 malloc作为分配，如此以浪费内存为代价你得到了一个分配时间近似O(1)的内存分配器。这种内存池的缺点是假设某个 FreeList 如果高峰期占用了大量内存即使后面不用，也无法支援到其他内存不够的 FreeList，达不到分配均衡的效果。
优点： 这个本质是定长内存池的改进，分配和释放的效率高。可以解决一定长度内的问题。
缺点： 存在内碎片的问题，且将一块大内存切小以后，申请大内存无法使用。多线程并发场景下，锁竞争激烈，效率降低。
范例： sgi stl 六大组件中的空间配置器就是这种设计实现的。
关于STL空间配置器参考： https://blog.csdn.net/LF_2016/article/details/53511648
了解malloc底层原理
关于malloc底层: https://blog.csdn.net/hudazhe/article/details/79535220
malloc优点: 使用自由链表的数组，提高分配释放效率；减少内存碎片，可以合并空闲的内存
**malloc缺点: ** 为了维护隐式/显示链表需要维护一些信息，空间利用率不高；在多线程的情况下，会出现线程安全的问题，如果以加锁的方式解决，会大大降低效率。
4.并发内存池
4.1 项目介绍
我写这个项目呢，主要是为了学习，参考的是tc_malloc，项目设计分为三层结构：
第一层是Thread Cache，线程缓存是每个线程独有的，在这里设计的是用于小于64k的内存分配，线程在这里申请不需要加锁，每一个线程都有自己独立的cache，这也就是这个项目并发高效的地方。
第二层是Central Cache，在这里是所有线程共享的，它起着承上启下的作用，Thread Cache是按需要从Central Cache中获取对象，它就要起着平衡多个线程按需调度的作用，既可以将内存对象分配给Thread Cache来的每个线程，又可以将线程归还回来的内存进行管理。Central Cache是存在竞争的，所以在这里取内存对象的时候是需要加锁的，但是锁的力度可以控制得很小。
第三层是Page Cache，存储的是以页为单位存储及分配的，Central Cache没有内存对象(Span)时，从Page cache分配出一定数量的Page，并切割成定长大小的小块内存，分配给Central Cache。Page Cache会回收Central Cache满足条件的Span(使用计数为0)对象，并且合并相邻的页，组成更大的页，缓解内存碎片的问题。
注：怎么实现每个线程都拥有自己唯一的线程缓存呢？
为了避免加锁带来的效率，在Thread Cache中使用（tls）thread local storage保存每个线程本地的Thread Cache的指针，这样Thread Cache在申请释放内存是不需要锁的。因为每一个线程都拥有了自己唯一的一个全局变量。
TLS分为静态的和动态的：
静态的TLS是：直接定义
动态的TLS是：调用系统的API去创建的，我们这个项目里面用到的就是静态的TLS
https://blog.csdn.net/evilswords/article/details/8191230
https://blog.csdn.net/yusiguyuan/article/details/22938671
4.2 设计Thread Cache
ThreadCache.h:
#pragma once
#include “Common.h”
class ThreadCache
{
private:
Freelist _freelist[NLISTS];//自由链表
public:
//申请和释放内存对象
void* Allocate(size_t size);
void Deallocate(void* ptr, size_t size);
//从中心缓存获取对象
void* FetchFromCentralCache(size_t index, size_t size);
//释放对象时，链表过长时，回收内存回到中心堆
void ListTooLong(Freelist* list, size_t size); };
//静态的，不是所有可见
//每个线程有个自己的指针, 用(_declspec (thread))，我们在使用时，每次来都是自己的，就不用加锁了
//每个线程都有自己的tlslist
_declspec (thread) static ThreadCache* tlslist = nullptr;
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
申请内存:
当内存申请size<=64k时在Thread Cache中申请内存，计算size在自由链表中的位置，如果自由链表中有内存对象时，直接从FistList[i]中Pop一下对象，时间复杂度是O(1)，且没有锁竞争。
当FreeList[i]中没有对象时，则批量从Central Cache中获取一定数量的对象，插入到自由链表并返回一个对象。
释放内存：
当释放内存小于64k时将内存释放回Thread Cache，计算size在自由链表中的位置，将对象Push到FreeList[i].
当链表的长度过长，也就是超过一次向中心缓存分配的内存块数目时则回收一部分内存对象到Central Cache。
4.3 对齐大小的设计（对齐规则）
//专门用来计算大小位置的类
class SizeClass
{
public:
//获取Freelist的位置
inline static size_t _Index(size_t size, size_t align)
{
size_t alignnum = 1 « align; //库里实现的方法
return ((size + alignnum - 1) » align) - 1;
}
inline static size_t _Roundup(size_t size, size_t align)
{
size_t alignnum = 1 << align;
return (size + alignnum - 1)&~(alignnum - 1);
}
public:
// 控制在12%左右的内碎片浪费
// [1,128] 8byte对齐 freelist[0,16)
// [129,1024] 16byte对齐 freelist[16,72)
// [1025,81024] 128byte对齐 freelist[72,128)
// [81024+1,64*1024] 1024byte对齐 freelist[128,184)
inline static size_t Index(size_t size)
{
assert(size <= MAX_BYTES);
// 每个区间有多少个链
static int group_array[4] = { 16, 56, 56, 56 };
if (size <= 128)
{
return _Index(size, 3);
}
else if (size <= 1024)
{
return _Index(size - 128, 4) + group_array[0];
}
else if (size <= 8192)
{
return _Index(size - 1024, 7) + group_array[0] + group_array[1];
}
else//if (size <= 65536)
{
return _Index(size - 8 * 1024, 10) + group_array[0] + group_array[1] + group_array[2];
}
}
// 对齐大小计算，向上取整
static inline size_t Roundup(size_t bytes)
{
assert(bytes <= MAX_BYTES);
if (bytes <= 128){
return _Roundup(bytes, 3);
}
else if (bytes <= 1024){
return _Roundup(bytes, 4);
}
else if (bytes <= 8192){
return _Roundup(bytes, 7);
}
else {//if (bytes <= 65536){
return _Roundup(bytes, 10);
}
}
//动态计算从中心缓存分配多少个内存对象到ThreadCache中
static size_t NumMoveSize(size_t size)
{
if (size == 0)
return 0;
int num = (int)(MAX_BYTES / size);
if (num < 2)
num = 2;
if (num > 512)
num = 512;
return num;
}
// 根据size计算中心缓存要从页缓存获取多大的span对象
static size_t NumMovePage(size_t size)
{
size_t num = NumMoveSize(size);
size_t npage = num*size;
npage >>= PAGE_SHIFT;
if (npage == 0)
npage = 1;
return npage;
} }; 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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 4.4 设计Thread Cache
Central Cache本质是由一个哈希映射的Span对象自由双向链表构成
为了保证全局只有唯一的Central Cache，这个类被可以设计成了单例模式
单例模式采用饿汉模式，避免高并发下资源的竞争
CentralCache.h:
#pragma once
#include “Common.h”
//上面的ThreadCache里面没有的话，要从中心获取
/*
进行资源的均衡，对于ThreadCache的某个资源过剩的时候，可以回收ThreadCache内部的的内存
从而可以分配给其他的ThreadCache
只有一个中心缓存，对于所有的线程来获取内存的时候都应该是一个中心缓存
所以对于中心缓存可以使用单例模式来进行创建中心缓存的类
对于中心缓存来说要加锁
*/
//设计成单例模式
class CentralCache
{
public:
static CentralCache* Getinstence()
{
return &_inst;
}
//从page cache获取一个span
Span* GetOneSpan(SpanList& spanlist, size_t byte_size);
//从中心缓存获取一定数量的对象给threa cache
size_t FetchRangeObj(void*& start, void*& end, size_t n, size_t byte_size);
//将一定数量的对象释放给span跨度
void ReleaseListToSpans(void* start, size_t size);
private:
SpanList _spanlist[NLISTS];
private:
CentralCache(){}//声明不实现，防止默认构造，自己创建
CentralCache(CentralCache&) = delete;
static CentralCache _inst; }; 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 41 申请内存：
当Thread Cache中没有内存时，就会批量向Central Cache申请一些内存对象，Central Cache也有一个哈希映射的freelist，freelist中挂着span，从span中取出对象给Thread Cache，这个过程是需要加锁的。
Central Cache中没有非空的span时，则将空的span链在一起，向Page Cache申请一个span对象，span对象中是一些以页为单位的内存，切成需要的内存大小，并链接起来，挂到span中。
Central Cache的span中有一个_usecount，分配一个对象给Thread Cache，就++_usecount。
释放内存：
当Thread Cache过长或者线程销毁，则会将内存释放回Central Cache中的，释放回来时- -_usecount。
当_usecount减到0时则表示所有对象都回到了span，则将Span释放回Page Cache，Page Cache中会对前后相邻的空闲页进行合并。
特别关心：什么是span?一个span是由多个页组成的一个span对象。一页大小是4k。
//Span是一个跨度，既可以分配内存出去，也是负责将内存回收回来到PageCache合并
//是一链式结构，定义为结构体就行，避免需要很多的友元
struct Span
{
PageID _pageid = 0;//页号
size_t _npage = 0;//页数
Span* _prev = nullptr;
Span* _next = nullptr;
void* _list = nullptr;//链接对象的自由链表，后面有对象就不为空，没有对象就是空
size_t _objsize = 0;//对象的大小
size_t _usecount = 0;//对象使用计数, }; 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 特别关心：关于spanlist，设计为一个双向链表，插入删除效率较高。
//和上面的Freelist一样，各个接口自己实现，双向带头循环的Span链表
class SpanList
{
public:
Span* _head;
std::mutex _mutex;
public:
SpanList()
{
_head = new Span;
_head->_next = _head;
_head->_prev = _head;
}
~SpanList()//释放链表的每个节点
{
Span * cur = _head->_next;
while (cur != _head)
{
Span* next = cur->_next;
delete cur;
cur = next;
}
delete _head;
_head = nullptr;
}
//防止拷贝构造和赋值构造，将其封死，没有拷贝的必要，不然就自己会实现浅拷贝
SpanList(const SpanList&) = delete;
SpanList& operator=(const SpanList&) = delete;
//左闭右开
Span* Begin()//返回的一个数据的指针
{
return _head->_next;
}
Span* End()//最后一个的下一个指针
{
return _head;
}
bool Empty()
{
return _head->_next == _head;
}
//在pos位置的前面插入一个newspan
void Insert(Span* cur, Span* newspan)
{
Span* prev = cur->_prev;
//prev newspan cur
prev->_next = newspan;
newspan->_next = cur;
newspan->_prev = prev;
cur->_prev = newspan;
}
//删除pos位置的节点
void Erase(Span* cur)//此处只是单纯的把pos拿出来，并没有释放掉，后面还有用处
{
Span* prev = cur->_prev;
Span* next = cur->_next;
prev->_next = next;
next->_prev = prev;
}
//尾插
void PushBack(Span* newspan)
{
Insert(End(), newspan);
}
//头插
void PushFront(Span* newspan)
{
Insert(Begin(), newspan);
}
//尾删
Span* PopBack()//实际是将尾部位置的节点拿出来
{
Span* span = _head->_prev;
Erase(span);
return span;
}
//头删
Span* PopFront()//实际是将头部位置节点拿出来
{
Span* span = _head->_next;
Erase(span);
return span;
}
void Lock()
{
_mutex.lock();
}
void Unlock()
{
_mutex.unlock();
} }; 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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 特别关心：怎么才能将Thread Cache中的内存对象还给它原来的span呢？ 答：可以在Page Cache中维护一个页号到span的映射，当Span Cache给Central Cache分配一个span时，将这个映射更新到unordered_map中去，在Thread Cache还给Central Cache时，可以查这个unordered_map找到对应的span。 4.5 设计Page Cache
Page cache是一个以页为单位的span自由链表。
为了保证全局只有唯一的Page cache，这个类可以被设计成了单例模式。
本单例模式采用饿汉模式。
PageCache.h
#pragma once
#include “Common.h”
//对于Page Cache也要设置为单例，对于Central Cache获取span的时候
//每次都是从同一个page数组中获取span
//单例模式
class PageCache
{
public:
static PageCache* GetInstence()
{
return &_inst;
}
Span* AllocBigPageObj(size_t size);
void FreeBigPageObj(void* ptr, Span* span);
Span* _NewSpan(size_t n);
Span* NewSpan(size_t n);//获取的是以页为单位
//获取从对象到span的映射
Span* MapObjectToSpan(void* obj);
//释放空间span回到PageCache，并合并相邻的span
void ReleaseSpanToPageCache(Span* span);
private:
SpanList _spanlist[NPAGES];
//std::map<PageID, Span> _idspanmap;
std::unordered_map<PageID, Span> _idspanmap;
std::mutex _mutex; private:
PageCache(){}
PageCache(const PageCache&) = delete;
static PageCache _inst; }; 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 申请内存：
当Central Cache向page cache申请内存时，Page Cache先检查对应位置有没有span，如果没有则向更大页寻找一个span，如果找到则分裂成两个。比如：申请的是4page，4page后面没有挂span，则向后面寻找更大的span，假设在10page位置找到一个span，则将10page span分裂为一个4page span和一个6page span。
如果找到128 page都没有合适的span，则向系统使用mmap、brk或者是VirtualAlloc等方式申请128page span挂在自由链表中，再重复1中的过程。
释放内存：
如果Central Cache释放回一个span，则依次寻找span的前后_pageid的span，看是否可以合并，如果合并继续向前寻找。这样就可以将切小的内存合并收缩成大的span，减少内存碎片。
4.6 向系统申请内存
VirtualAlloc https://baike.baidu.com/item/VirtualAlloc/1606859?fr=aladdin
brk和mmap https://www.cnblogs.com/vinozly/p/5489138.html
- 项目不足及扩展学习
项目的独立性不足：
不足：当前实现的项目中我们并没有完全脱离malloc，比如在内存池自身数据结构的管理中，如SpanList中的span等结构，我们还是使用的new Span这样的操作，new的底层使用的是malloc，所以还不足以替换malloc，因为们本身没有完全脱离它。
解决方案：项目中增加一个定长的ObjectPool的对象池，对象池的内存直接使用brk、VirarulAlloc等向系统申请，new Span替换成对象池申请内存。这样就完全脱离的malloc，就可以替换掉malloc。
平台及兼容性：
linux等系统下面，需要将VirtualAlloc替换为brk等。
x64系统下面，当前的实现支持不足。比如：id查找Span得到的映射，我们当前使用的是map<id,
Span*>。在64位系统下面，这个数据结构在性能和内存等方面都是撑不住。需要改进后基数树。
具体参考：基数树(radix tree) https://blog.csdn.net/weixin_36145588/article/details/78365480
参考资料
几个内存池库的对比： https://blog.csdn.net/junlon2006/article/details/77854898
tcmalloc源码学习： https://www.cnblogs.com/persistentsnail/p/3442185.html
TCMALLOC 源码阅读： https://blog.csdn.net/math715/article/details/80654167
- 项目源码
https://github.com/Winter-Win/ConcurrentMemoryPool
https://blog.csdn.net/qq_41562665/article/details/90546750
内存分配是按照堆块实现的，一个堆块是由头部和有效载荷量组成，其中的有效载荷量就是我们申请的堆的大小。
头部块包括 块大小和是否可用 这两个部分组成。
在内存中这些堆块以链表形势组成
malloc函数的实质体现在，它有一个将可用的内存块连接为一个长长的列表的所谓空闲链表。调用malloc函数时，它沿连接表寻找一个大到足以满足用户请求所需要的内存块。然后，将该内存块一分为二（一块的大小与用户请求的大小相等，另一块的大小就是剩下的字节）。接下来，将分配给用户的那块内存传给用户，并将剩下的那块（如果有的话）返回到连接表上。调用free函数时，它将用户释放的内存块连接到空闲链上。到最后，空闲链会被切成很多的小内存片段，如果这时用户申请一个大的内存片段，那么空闲链上可能没有可以满足用户要求的片段了。于是，malloc函数请求延时，并开始在空闲链上翻箱倒柜地检查各内存片段，对它们进行整理，将相邻的小空闲块合并成较大的内存块。
glibc维护了不止一个不定长的内存块链表，而是好几个，每一个这种链表负责一个大小范围，这种做法有效减少了分配大内存时的遍历开销，类似于哈希的方式，将很大的范围的数据散列到有限的几个小的范围内而不是所有数据都放在一起，虽然最终还是要在小的范围内查找，但是最起码省去了很多的开销，如果只有一个不定长链表那么就要全部遍历，如果分成3个，就省去了2/3的开销，总之这个策略十分类似于散列。glibc另外的策略就是不止维护一类空闲链表，而是另外再维护一个缓冲链表和一个高速缓冲链表，在分配的时候首先在高速缓存中查找，失败之后再在空闲链表查找，如果找到的内存块比较大，那么将切割之后的剩余内存块插入到缓存链表，如果空闲链表查找失败那么就往缓存链表中查找. 如果还是没有合适的空闲块，就向内存申请比请求数更大的内存块，然后把剩下的内存放入链表中。
在对内存块进行了 free 调用之后，我们需要做的是诸如将它们标记为未被使用的等事情，并且，在调用 malloc 时，我们要能够定位未被使用的内存块。因此， malloc返回的每块内存的起始处首先要有这个结构：
这就解释了，为什么在程序中free之后，但是堆的内存还是没有释放。
//清单 3. 内存控制块结构定义
struct mem_control_block {
int is_available;
int size;
};
现在，您可能会认为当程序调用 malloc 时这会引发问题 —— 它们如何知道这个结构？答案是它们不必知道；在返回指针之前，我们会将其移动到这个结构之后，把它隐藏起来。这使得返回的指针指向没有用于任何其他用途的内存。那样，从调用程序的角度来看，它们所得到的全部是空闲的、开放的内存。然后，当通过 free() 将该指针传递回来时，我们只需要倒退几个内存字节就可以再次找到这个结构。
在讨论分配内存之前，我们将先讨论释放，因为它更简单。为了释放内存，我们必须要做的惟一一件事情就是，获得我们给出的指针，回退 sizeof(struct mem_control_block) 个字节，并将其标记为可用的。这里是对应的代码：
清单 4. 解除分配函数
void free(void firstbyte) {
struct mem_control_block *mcb;
/ Backup from the given pointer to find the
- mem_control_block
/
mcb = firstbyte - sizeof(struct mem_control_block);
/ Mark the block as being available /
mcb->is_available = 1;
/ That’’s It! We’‘re done. */
return;
}
如您所见，在这个分配程序中，内存的释放使用了一个非常简单的机制，在固定时间内完成内存释放。
http://blog.163.com/dengminwen@126/blog/static/870226720097189486788/
（总结就一句话，stl没有侯捷书上写的有一个链表管理内存块，而是简单的调用malloc和free，我想这是因为malloc内部已经实现了内存池）
- 背景
前些天在一个技术分享会上，某大牛说，STL使用了内存池，释放内存的时候，并不释放给OS，而是自己由留着用。
听到这些观点后，我就有些着急了，因为我以前一直是直接使用STL的一些工具类的，比如std::string、std::map、std::vector、std::list等等，从来都没有关注过内存的问题。
带着内存的问题，我花了两三天的时间去阅读STL的代码，并且写一些简单的程序进行测试；下面列举一些心得体会，但是却没有什么大的结论 -.-
- 容易误解的简单例子
我们以STL中的map为例，下面有一个使用map的简单例子，大部分人可以在30秒内写好。
void testmap()
{
map<int, float> testmap;
for (int i = 0; i < 1000000; i++) {
testmap[i] = (float)i;
}
testmap.clear();
}
为了在调用map::clear()之后查看进程的内存使用量，我们可以加几行代码让程序暂停一下。
void testmap()
{
map<int, float> testmap;
for (int i = 0; i < 1000000; i++) {
testmap[i] = (float)i;
}
testmap.clear();
// 观察点
int tmp; cout « “use ps to see my momory now, and enter int to continue:”; cin » tmp;
}
编译运行上面的程序，你会看见这样的情况：ps显示进程的内存使用量为40MB多。这时，你会毫不犹豫地说，STL的map使用了内存池（memory pool）。
然后，我就跑去阅读libstdc++的STL的源代码，STL提供了很多种Allocator的实现，有基于内存池的，但是默认的std::allocator的实现是new_allocator，这个实现只是简单的对new和delete进行了简单的封装，并没有使用内存池。这样，怀疑的对象就转移到glibc的malloc函数了。malloc提供的两个函数来查看当前申请的内存的状态，分别是malloc_stats()和mallinfo()，它们都定义在
为了弄清楚这个问题，我们对上面的例子进行如下的改造：
#include
void testmap()
{
malloc_stats(); // <======== 观察点1
map<int, float> testmap;
for (int i = 0; i < 1000000; i++) {
testmap[i] = (float)i;
}
malloc_stats(); // <======== 观察点2
testmap.clear();
malloc_stats(); // <======== 观察点3
}
这个例子的运行环境是这样的：
[dengmw@my ~]$ g++ -v
Reading specs from /usr/lib/gcc/x86_64-redhat-linux/3.4.6/specs
Configured with: ../configure –prefix=/usr –mandir=/usr/share/man –infodir=/usr/share/info –enable-shared –enable-threads=posix –disable-checking –with-system-zlib –enable-__cxa_atexit –disable-libunwind-exceptions –enable-java-awt=gtk –host=x86_64-redhat-linux
Thread model: posix
gcc version 3.4.6 20060404 (Red Hat 3.4.6-9)
程序的运行结果是这样的：
在观察点1：
- system bytes = 0
- in use bytes = 0
在观察点2： - system bytes = 48144384
- in use bytes = 48005120
在观察点3： - system bytes = 48140288 <==== malloc cache the memory here
- in use bytes = 5120
很明显，尽管程序员显式地调用了map::clear()，但是malloc并没有把这些内存归还给OS，而是缓存起来了。所以说，这个例子的罪魁祸首并不是libstdc++的的STL，而是glibc的malloc。
侯捷的《STL源码剖析》有点过时了
在调试上面的例子的时候，我在看了不少的书籍和网上的文章，其中就包括了侯捷的《STL源码剖析》，但是这本书已经过时了，因为他写这本书的时候，g++的版本才2.9。我把g++的各个版本的源代码都下载下来了，并且进行了比较，总结如下：
侯捷的《STL源码剖析》只对于gcc-3.3.及以前的版本是对的；对于gcc-3.4.以后的版本，STL中关于内存的代码变了
当前，大家使用的gcc大都是3.4.6版本或者更加新的版本
gcc-3.3分支从2003-05-13发布第1版，到2005-05-03发布3.3.6
gcc-3.3的默认的Allocator，定义在”include/bits/stl_alloc.h”里，确实是带有cache的 (即常说的memory pool)
gcc-3.4的默认的Allocator，定义在”include/bits/allocator.h”里，它的真实的实现是”include/ext/new_allocator.h”，这个实现不带cache，只是new和delete的简单封装
STL内存管理的基础知识(gcc-3.4.*及以后的)
通过这次对STL的研究，我学到不不少新的知识。可能这些内容你都已经会了，-.-，我比较弱，下面的内容我是第一次知道的：
STL有很多种allocator，默认采用的是std::allocator，我们沿着这样的头文件路线，可以找到它的最终实现：
-> “include/bits/allocator.h”
-> “include/i386-redhat-linux/bits/c++allocator.h”
-> “include/ext/new_allocator.h”（即是说，std::allocator == __gnu_cxx::new_allocator）
根据C++的标准，STL的allocator，把对象的申请和释放分成了4步：
第1步：申请内存空间，对应函数是allocator::allocate()
第2步：执行构造函数，对应函数是allocator::construct()
第3步：执行析构函数，对应函数是allocator::destroy()
第4步：释放内存空间，对应函数是allocator::deallocate()
STL崇尚拷贝，你往容器里放东西或者从容器里取东西，都是要调用拷贝构造函数的。比如，你有一个对象a要插入到map里，过程是这样的：
map先申请一个结点的空间
调用拷贝构造函数初始化该结点
把新结点插入到map的红黑树中
STL中实现了好多种不同的更为具体的allocator，如下（GNU GCC关于Memory的官方文档）：
__gnu_cxx::new_allocator: 简单地封装了new和delete操作符，通常就是std::allocator
__gnu_cxx::malloc_allocator: 简单地封装了malloc和free函数
__gnu_cxx::array_allocator: 申请一堆内存
__gnu_cxx::debug_allocator: 用于debug
__gnu_cxx::throw_allocator: 用于异常
__gnu_cxx::__pool_alloc: 基于内存池
__gnu_cxx::__mt_alloc: 对多线程环境进行了优化
__gnu_cxx::bitmap_allocator: keep track of the used and unused memory locations.
上面的8个allocator的实现中，bitmap_allocator、pool_allocator和__mt_alloc是基于cache的，其它的不基于cache
- 那么？如何指定使用一个特殊的allocator呢？示例如下：
map<int, int> a1; // 方法1
map<int, int, less, std::allocator<pair<int, int> > > a3; // 方法2
// 方法3，方法1、方法2、方法3都是等价的
map<int, int, less, __gnu_cxx::new_allocator<pair<int, int> > > a2;
// 方法4，使用了基于cache的allocator
map<int, int, less, __gnu_cxx::__pool_alloc<pair<int, int> > > a4;
- 内存碎片是容易被忽视的导致OutOfMemory的原因
这个观点有点类似于磁盘碎片，也可以称为内存碎片吧，当内存碎片过多的时候，极容易出现OutOfMemory错误；
使用STL的map特别容易出现这种情况，往map里插入了海量的小对象，然后释放了一些，然后再想申请内存时，就出现OutOfMemory错误了；
这种现象不只是在使用STL的情况会发现，下面举一个例子来说明内存碎片的问题，尽管这个例子没有使用STL。
举例之前，先说明一下这个例子中使用的两个查看当前进程的内存统计量的2个函数：
int get_max_malloc_length_inMB() : 得到当前可以申请的最长的内存长度(MB)；这个函数不停地调用p=malloc(length10241024)；如果成功，则length++，并且free(p)；如果失败，返回(length-1)。
int get_free_mem_inKB() : 得到当前可以申请的内存总量(KB)；这个函数不停地调用malloc(1024)来申请1KB的内存；如果成功，把这1KB的内存存起来，并且count++；如果失败，则把所有的1KB内存释放，再返回count。
为了测试方便，我在运行程序前，设置了进程的最大内存为200MB，使用的命令如下：
ulimit -m 204800;
ulimit -v 204800;
这个例子把申请到的内存以矩阵的形式存储起来，先按列优先把指针存起来，再按行优先进行free，这样会造成大量的内存碎片；例子的伪代码如下：
typedef char* PtrType;
PtrType ** Ptrs = (PtrType*) malloc( ROW * sizeof(PtrType) );
…
// 第1步: 占领所有的内存，按列优先进行申请
for(j=0; j<COL; ++j) {
for(i=0; i<ROW; ++i) {
Ptrs[j][i] = malloc(1024);
}
}
// 第2步：按行优先释放所有的内存，在中间多次调用get_max_malloc_length_inMB和get_free_mem_inKB来查看内存使用情况
for (i=0; i<ROW; ++i) {
for (j=0; j<COL; ++j) {
free( Ptrs[i][j] );
}
free(Ptrs[i]);
// 得到两个关于内存的统计量
get_max_malloc_length_inMB();
get_free_mem_inKB();
}
// 第3步：释放Ptrs，再获取一次内存的统计量
free(Ptrs);
get_max_malloc_length_inMB();
get_free_mem_inKB();
需要关注的是，内存的申请的顺序是按列优先的，而释放的顺序是按行优先的，这种做法就是模拟内存的碎片。
运行上面的程序后，得到的结果是：在释放内存的过程中，max_malloc_length_inMB长期保持在0 MB，当全部释放完后，max_malloc_length_inMB变成了 193 MB
max_malloc_length_inMB:
196 MB -> 0 MB -> 0 MB -> … -> 0 MB -> 0 MB -> …
-> 0 MB -> 0 MB -> 195 MB
free_mem_inKB:
199374 KB -> 528 KB -> 826 KB -> … -> 96037 KB -> 96424 KB -> …
-> 197828 KB -> 198215 KB -> 198730 KB
上面的结果引申出这样的结论：
OutOfMemory错误，并不一定是内存使用得太多；
当一个程序申请了大量的小内存块 (比如往std::map中插入海量的小对象)，导致内存碎片过多的话，一样有可能出现OutOfMemory错误
- 一些别的收获
6.1 libc.so.6和glibc-2.9有什么不同？
参考文献：http://en.wikipedia.org/wiki/GNU_C_Library
在80年代，FSF写了glibc；
后来，linux kernel的人照着glibc，写了”Linux libc”，一直从libc.so.2到libc.so.5
到1997年，FSF发布了glibc-2.0，这个版本有很多优点，比如支持有更多的标准，更可移植；linux kernel的人就把”Linux libc”的项目砍掉了，重新使用glibc-2.0，然后就命名为libc.so.6
如果你运行一下这个命令”ls -lh /lib/libc.so.6”，你会发现它其实是一个符号链接，在我的电脑上，它指向了”/lib/libc-2.9.so”
6.2 申请内存的方式共有多少种？
参考文献：glibc manual中的第3章（见http://www.gnu.org/software/libc/manual/）
exec
fork
进程内：
global var or static var
local var
malloc()
memory map file
在 C 语言的动态申请内存技术中，相比起 alloc/free 系统调用，内存池（memory pool）是与现在系统中请求一大片连续的内存空间，然后在运行时根据实际需要分配出去的技术。使用内存池的优点有：
速度远比 malloc/free 快，因为减少了系统调用的次数，特别是频繁申请/释放内存块的情况
避免了频繁申请/释放内存之后，系统的大量内存碎片
节省空间
分类
根据分配出去的内存大小，内存池可以分为两类：
Fixed-size Allocation
每次分配出去的内存单元（称为 unit 或者 cell）的大小为程序预先定义的值。释放内存块时，则只需要简单地挂回内存池链表中即可。又称为 “固定尺寸缓冲池”。
常规的做法是：将不同 unit size 的内存池整合在一起，以满足不同内存块大小的使用需求
Variable-size allocation
不分配固定长度，内存的分配只是在一大块空闲的内存上滑动。优点是分配效率很高，缺点是成批地回收内存，因为释放的内存无法直接重复利用。
使用这种需要合理规划每块内存的管理区域，所以又叫做 “基于区域的” 内存管理。使用这种做法的分配器，举例有 Apache Portable Runtime 中的 apr_pool 工具。本文不讨论这种内存池。
原理和结构
概念和数据结构
定长内存池有一些基本和必要的概念，需要定义在内存池的结构数据中。以下命名方式使用变体的匈牙利命名法，比如 nNext，n表示变量类型为整形。类似地，p表示指针。
Memory Unit
每次程序调用 MemPool_Alloc 获取一个内存区域后，会获得一块连续的内存区域。管理一个这样的内存区域的单元就成为内存单元 unit，有时也称作 chunk。每个 unit 需要包含以下数据：
nNext：整型数据，表示下一个可供分配的 unit 的标识号。功能请参见后问
pData[]：实际的内存区域，其大小在创建时由调用方指定
Memory Block
一个内存块，内存块中保存着一系列的内存单元。
这个数据结构需要包含以下基本信息：
nSize：整型数据，表示该 block 在内存中的大小
nFree：整型，表示剩下有几个 unit 未被分配
nFirst：整型，表示下一个可供分配的 unit 的标识号
pNext：指针，指向下一个 memory block
Memory Pool
一个内存池总的管理数据结构，换句话说，是一个内存池对象。
pBlock：指针，指向第一个 memory block
nUnitSize：整型，表示每个 unit 的尺寸
nInitSize：整型，表示第一个 block 的 unit 个数
nGrowSize：整型，表示在第一个 block 之外再继续增加的每个 block 的 unit 个数
函数接口
作为一个内存池，需要实现以下一些基本的函数接口，或者说可以是对象方法：
memPoolCreate()
创建一个 memory pool，必须的参数为 unit size，可选参数为上文 memory pool 的 nInitSize 和 nGrowSize。
memPoolDestroy()
销毁整个 memory pool 并交还给操作系统。
memPoolAlloc()
从 memory pool 中分配一个 unit，其尺寸是预先定义的 unit size。
memPoolFree()
释放一个指定的 unit。
工作过程
现在我们用一个 unit size 为 1024、init size 为 4（每一个 block 有 4 个 units）的 memory pool 为例，解释一下内存池的工作原理。下文假设整型的宽度为 4 个字节。
创建 memory pool
程序开始，调用并创建一个 memory pool。此时调用的函数为 memPoolCreate()，程序会创建一个数据结构，相应的结构体成员及其取值如下：
img
memory pool alloc
当调用者第一次请求 memPoolAlloc() 时，内存池发现 block 链表为空，于是想系统申请内存，创建 memory block，并初始化如下（其中地址值为假设值）：
img
其中 nSize = 4112 = sizeof(memPool) + nInitSize * sizeof(memUnit)。每一个 nNext 依次加一，各指代着跟着自己的下一个 unit。最后一个 unit 的 nNext 值无意义，因此不说明其取值。
然后返回需要的 unit 中的内存。返回内存的逻辑如下：
内存池在 block 中查询 nFree 成员
由于 nFree > 0，表示有未分配的 unit，因此继续在该 block 中查看 nFirst 成员
nFirst 等于 0，表示该 block 中位置为 0 的 unit 可用。因此内存池可以将这个 unit 中的 pData 地址返回给调用方。 pData 的地址值计算方式为：pBlock + sizeof(memBlock) + nFirst * (sizeof(memUnit)) + sizeof(nNext) = 0x10010
nFree 减一
修改 nFirst 的值，标记下一个可用的 unit。注意这里的 nFirst 切切不能简单地加一，而是取返回给调用方的 unit 所对应的 nNext 的值，也就是下图(2)处原来的值 1
将 pData 的地址值返回。为便于说明，这块区域我们标记为 CA
操作后各数据结构的状态如下：
img
第二次调用 alloc 的情况类似。调用后各数据结构的状态如下：
img
memory pool free
我们先看看结果：
img
首先程序会检查 CA 的地址值，很快就会发现，地址 0x10010 位于上述第一个 block 的范围之内（0x10000 <= 0x10010 <= (0x10000 + 4112)）。再计算偏移值可以很快得出其对应的 nNext 标号，也就是上图中的(2)位置。
回收 unit，此时需要标记相应的成员值以标示 unit 的回收状态。首先查看 nFirst 的值，参见上前幅图，nFirst 的值为 3，表示位置(3)处的 unit 是可用的。因此我们首先把 (2) 处的 nNext 值设置为 3，将其加回到可用 unit 的链表中
将 nFirst 的值修改为 0，也就是代表刚刚回收回来的 unit 的标号，而(2)处的值赋值为 2，表示b(3)的 unit
其实可以看到，上面就是一个简单的链表操作。根据上面的过程，如果 CB 也释放了的话，那么 memory pool 的状态则会变成这样：
img
到这个时候，由于整个 block 已经完全回收了（nFree == nInitSize），那么根据不同的策略，可以考虑将整个 block 从内存中释放掉。
block 满
我们回到 alloc 的逻辑中，可以看到内存池最开始会检查 block 的 nFree 成员。如果 nFree == 0 的时候，那么就会在该 block 的 pNext 中去找到下一个 block，再去检查 nFree。如果发现 block 链表已经结束了，那就意味着当前所有的 block 已满，必须创建新的 block。
在实际设计中，我们需要考虑选取合适的 init size 和 grow size 值。从上面的算法中可以看到，如果 alloc/free 调用非常频繁时，第一个 block 的使用效率是非常高的。
变体或改进
有些简化的版本中，可以不使用 pNext 来维护链表，也就是只有一个 block，并且内存的使用有一个明确且受控的上限值。这经常用在没有 malloc 系统调用的 RTOS 或者是一些对内存非常敏感的嵌入式系统中。
如果要用于多线程环境中，那么 memory pool 结构体需要加上锁
https://studygolang.com/topics/7126
https://blog.csdn.net/qq_41562665/article/details/90546750
1 Linux系统内存管理
1.1 进程地址空间
一个linux进程的虚拟地址空间分布如图所示，分为内核空间和进程空间，对于一个32位操作系统来说，4GB的空间分成两部分，低地址的0~3G给用户空间，高地址的3G~4G给内核空间。
图源：http://www.dongcoder.com/detail-1060768.html
1.2 系统层面内存分配
从操作系统角度看，进程分配内存有两种方式，分别由两个系统调用完成：brk 和 mmap (不考虑共享内存)
1）brk 是将数据段（.data）的最高地址指针 _edata 往高地址推
2）mmap 是在进程的虚拟地址空间中（堆和栈中间，称为“文件映射区域”的地方）找一块空闲的虚拟内存。
这两种方式分配的都是虚拟内存，没有分配物理内存。在第一次访问已分配的虚拟地址空间的时候，发生缺页中断，操作系统负责分配物理内存，然后建立虚拟内存和物理内存之间的映射关系（一般是硬件单元MMU管理）。
1.3 库函数malloc
1）当开辟的空间小于 128K 时，调用 brk（）函数，malloc 的底层实现是系统调用函数 brk（），其主要移动指针 _enddata(此时的 _enddata 指的是 Linux 地址空间中堆段的末尾地址，不是数据段的末尾地址)
2）当开辟的空间大于 128K 时，mmap（）系统调用函数来在虚拟地址空间中（堆和栈中间，称为“文件映射区域”的地方）找一块空间来开辟。
2 TCMalloc
TCMalloc全称Thread-Caching Malloc，即线程缓存的malloc，是 Google 开发的内存分配器，在不少项目中都有使用，例如在 Golang 中就使用了类似的算法进行内存分配。它具有现代化内存分配器的基本特征：对抗内存碎片、在多核处理器能够 scale。据称，它的内存分配速度是 glibc2.3 中实现的 malloc的数倍。实现了高效的多线程内存管理，用于替代glib等库的内存分配相关的函数（malloc、free，new，new[]等）。
TCMalloc的管理内存的策略可以用一张图描述（源：https://wallenwang.com/2018/11/tcmalloc/）
TCMalloc是gperftools的一部分，除TCMalloc外，gperftools还包括heap-checker、heap-profiler和cpu-profiler。
官方介绍http://goog-perftools.sourceforge.net/doc/tcmalloc.html
3 golang内存管理
3.1 概述
Golang的内存分配器是基于TCMalloc实现的。Golang 的程序在启动之初，会一次性从操作系统那里申请一大块内存(初始堆内存应该是 64M 左右)作为内存池。这块内存空间会放在一个叫 mheap 的 struct 中管理，mheap 负责将这一整块内存切割成不同的区域(spans, bitmap ,areana)，并将其中一部分的内存切割成合适的大小，分配给用户使用。
3.2 内存管理的几个概念
page 内存页，一块 8K 大小的内存空间。Go 与操作系统之间的内存申请和释放，都是以 page 为单位的。
mheap 堆分配器，以8192byte页进行管理
mspan 由mheap管理的页面
mcentral 所有给定大小类的mspan集合，Central组件其实也是一个缓存，但它缓存的不是小对象内存块，而是一组一组的内存page(一个page占4k大小)
mcache 运行时分配池，每个线程都有自己的局部内存缓存mCache，实现goroutine高并发的重要因素(分配小对象可直接从mCache中分配，不用加锁)
arena 区域就是heap，是供分配维护的内存池，对应区域大小是512G；
bitmap 区域是标识arena中那些地址保存了对象，及对象中是否包含了指针，其中1个byte（8bit）对应arena中4个指针大小的内存（即：2bit对应1个指针大小），对应大小16G；
span 是页管理单元，是内存分配的基本单位，其中一个指针对应arena中1个虚拟地址页大小（8kb），对应大小512M
sizeclass 空间规格，每个 span 都带有一个 sizeclass ，标记着该 span 中的 page 应该如何使用。使用上面的比喻，就是 sizeclass 标志着 span 是一个什么样的队伍。
object 对象，用来存储一个变量数据内存空间，一个 span 在初始化时，会被切割成一堆等大的 object 。假设 object 的大小是 16B ， span 大小是 8K ，那么就会把 span 中的 page 就会被初始化 8K / 16B = 512 个 object 。所谓内存分配，就是分配一个 object 出去。
3.3 内存管理器初始化
在golang程序初始化时，runtime中会初始化内存管理器，调用函数 mallocinit()
在文件src/runtime/malloc.go
func mallocinit() {
if class_to_size[_TinySizeClass] != _TinySize {
throw(“bad TinySizeClass”)
}
testdefersizes()
if heapArenaBitmapBytes&(heapArenaBitmapBytes-1) != 0 {
// heapBits expects modular arithmetic on bitmap
// addresses to work.
throw("heapArenaBitmapBytes not a power of 2")
}
// Copy class sizes out for statistics table.
for i := range class_to_size {
memstats.by_size[i].size = uint32(class_to_size[i])
}
// Check physPageSize.
if physPageSize == 0 {
// The OS init code failed to fetch the physical page size.
throw("failed to get system page size")
}
if physPageSize < minPhysPageSize {
print("system page size (", physPageSize, ") is smaller than minimum page size (", minPhysPageSize, ")\n")
throw("bad system page size")
}
if physPageSize&(physPageSize-1) != 0 {
print("system page size (", physPageSize, ") must be a power of 2\n")
throw("bad system page size")
}
if physHugePageSize&(physHugePageSize-1) != 0 {
print("system huge page size (", physHugePageSize, ") must be a power of 2\n")
throw("bad system huge page size")
}
if physHugePageSize != 0 {
// Since physHugePageSize is a power of 2, it suffices to increase
// physHugePageShift until 1<<physHugePageShift == physHugePageSize.
for 1<<physHugePageShift != physHugePageSize {
physHugePageShift++
}
}
// Initialize the heap.
mheap_.init()
_g_ := getg()
_g_.m.mcache = allocmcache()
// Create initial arena growth hints.
if sys.PtrSize == 8 {
// On a 64-bit machine, we pick the following hints
// because:
//
// 1. Starting from the middle of the address space
// makes it easier to grow out a contiguous range
// without running in to some other mapping.
//
// 2. This makes Go heap addresses more easily
// recognizable when debugging.
//
// 3. Stack scanning in gccgo is still conservative,
// so it's important that addresses be distinguishable
// from other data.
//
// Starting at 0x00c0 means that the valid memory addresses
// will begin 0x00c0, 0x00c1, ...
// In little-endian, that's c0 00, c1 00, ... None of those are valid
// UTF-8 sequences, and they are otherwise as far away from
// ff (likely a common byte) as possible. If that fails, we try other 0xXXc0
// addresses. An earlier attempt to use 0x11f8 caused out of memory errors
// on OS X during thread allocations. 0x00c0 causes conflicts with
// AddressSanitizer which reserves all memory up to 0x0100.
// These choices reduce the odds of a conservative garbage collector
// not collecting memory because some non-pointer block of memory
// had a bit pattern that matched a memory address.
//
// However, on arm64, we ignore all this advice above and slam the
// allocation at 0x40 << 32 because when using 4k pages with 3-level
// translation buffers, the user address space is limited to 39 bits
// On darwin/arm64, the address space is even smaller.
// On AIX, mmaps starts at 0x0A00000000000000 for 64-bit.
// processes.
for i := 0x7f; i >= 0; i-- {
var p uintptr
switch {
case GOARCH == "arm64" && GOOS == "darwin":
p = uintptr(i)<<40 | uintptrMask&(0x0013<<28)
case GOARCH == "arm64":
p = uintptr(i)<<40 | uintptrMask&(0x0040<<32)
case GOOS == "aix":
if i == 0 {
// We don't use addresses directly after 0x0A00000000000000
// to avoid collisions with others mmaps done by non-go programs.
continue
}
p = uintptr(i)<<40 | uintptrMask&(0xa0<<52)
case raceenabled:
// The TSAN runtime requires the heap
// to be in the range [0x00c000000000,
// 0x00e000000000).
p = uintptr(i)<<32 | uintptrMask&(0x00c0<<32)
if p >= uintptrMask&0x00e000000000 {
continue
}
default:
p = uintptr(i)<<40 | uintptrMask&(0x00c0<<32)
}
hint := (*arenaHint)(mheap_.arenaHintAlloc.alloc())
hint.addr = p
hint.next, mheap_.arenaHints = mheap_.arenaHints, hint
}
} else {
// On a 32-bit machine, we're much more concerned
// about keeping the usable heap contiguous.
// Hence:
//
// 1. We reserve space for all heapArenas up front so
// they don't get interleaved with the heap. They're
// ~258MB, so this isn't too bad. (We could reserve a
// smaller amount of space up front if this is a
// problem.)
//
// 2. We hint the heap to start right above the end of
// the binary so we have the best chance of keeping it
// contiguous.
//
// 3. We try to stake out a reasonably large initial
// heap reservation.
const arenaMetaSize = (1 << arenaBits) * unsafe.Sizeof(heapArena{})
meta := uintptr(sysReserve(nil, arenaMetaSize))
if meta != 0 {
mheap_.heapArenaAlloc.init(meta, arenaMetaSize)
}
// We want to start the arena low, but if we're linked
// against C code, it's possible global constructors
// have called malloc and adjusted the process' brk.
// Query the brk so we can avoid trying to map the
// region over it (which will cause the kernel to put
// the region somewhere else, likely at a high
// address).
procBrk := sbrk0()
// If we ask for the end of the data segment but the
// operating system requires a little more space
// before we can start allocating, it will give out a
// slightly higher pointer. Except QEMU, which is
// buggy, as usual: it won't adjust the pointer
// upward. So adjust it upward a little bit ourselves:
// 1/4 MB to get away from the running binary image.
p := firstmoduledata.end
if p < procBrk {
p = procBrk
}
if mheap_.heapArenaAlloc.next <= p && p < mheap_.heapArenaAlloc.end {
p = mheap_.heapArenaAlloc.end
}
p = alignUp(p+(256<<10), heapArenaBytes)
// Because we're worried about fragmentation on
// 32-bit, we try to make a large initial reservation.
arenaSizes := []uintptr{
512 << 20,
256 << 20,
128 << 20,
}
for _, arenaSize := range arenaSizes {
a, size := sysReserveAligned(unsafe.Pointer(p), arenaSize, heapArenaBytes)
if a != nil {
mheap_.arena.init(uintptr(a), size)
p = uintptr(a) + size // For hint below
break
}
}
hint := (*arenaHint)(mheap_.arenaHintAlloc.alloc())
hint.addr = p
hint.next, mheap_.arenaHints = mheap_.arenaHints, hint
} }
3.4 内存分配过程
之前说到golang程序初始化时会申请一块内存，放在mheap中管理，如下图：
mheap的关键代码如下：
type mheap struct {
lock mutex
spans []*mspan
// Malloc stats.
largealloc uint64 // bytes allocated for large objects
nlargealloc uint64 // number of large object allocations
largefree uint64 // bytes freed for large objects (>maxsmallsize)
nlargefree uint64 // number of frees for large objects (>maxsmallsize)
// range of addresses we might see in the heap
bitmap uintptr // Points to one byte past the end of the bitmap
bitmap_mapped uintptr
arena_start uintptr
arena_used uintptr // Set with setArenaUsed.
arena_alloc uintptr
arena_end uintptr
arena_reserved bool
central [numSpanClasses]struct {
mcentral mcentral
pad [sys.CacheLineSize - unsafe.Sizeof(mcentral{})%sys.CacheLineSize]byte
}
}
小对象：
将申请的内存大小，向上取整成对应的size class；并且从P的mcache中找对应的mspan。
如果mspan有空闲slot，就分配。这个过程不需要lock，因为只有一个G会向P申请。
如果mspan没有空闲slot，就从mcentral获取新的mspan。这个过程需要lock，因为会有多个G同时申请。
如果mcentral没有mspan，就从mheap申请。
如果mheap空间不足，就想OS申请一组page，最少1MB。
大对象：
大对象都是直接操作mheap，跳过mcache和mcentral
2.2 调试分析
代码：
package main
import(
“fmt”
)
func main() {
aa := 1
fmt.Println(aa)
i := getObj()
fmt.Println(i)
ii := getHeapObj()
fmt.Println(ii,*ii)
}
//栈中分配内存
func getObj() int{
i := 2
return i
}
//堆中分配内存
func getHeapObj() *int{
i := 3
return &i
}
调试过程：
gdb newobj
GNU gdb (GDB) 8.0.1
Copyright (C) 2017 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later http://gnu.org/licenses/gpl.html
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law. Type “show copying”
and “show warranty” for details.
This GDB was configured as “x86_64-apple-darwin17.0.0”.
Type “show configuration” for configuration details.
For bug reporting instructions, please see:
http://www.gnu.org/software/gdb/bugs/.
Find the GDB manual and other documentation resources online at:
http://www.gnu.org/software/gdb/documentation/.
For help, type “help”.
Type “apropos word” to search for commands related to “word”…
Reading symbols from newobj…done.
Loading Go Runtime support.
(gdb)
(gdb) r
Starting program: /opt/newobj
[New Thread 0x2603 of process 93045]
warning: unhandled dyld version (15)
1
2
0xc0000aa020 3
[Inferior 1 (process 93045) exited normally]
(gdb) b main.main
Breakpoint 1 at 0x1094770: file /opt/newobj.go, line 7.
(gdb) n
The program is not being run.
(gdb) r
Starting program: /opt/newobj
[New Thread 0x1b03 of process 93047]
warning: unhandled dyld version (15)
[New Thread 0x190b of process 93047]
[New Thread 0x1c03 of process 93047]
[New Thread 0x1d03 of process 93047]
[New Thread 0x2303 of process 93047]
[New Thread 0x2403 of process 93047]
Thread 2 hit Breakpoint 1, main.main () at /opt/newobj.go:7
7 func main() {
(gdb) n
8 aa := 1
(gdb) s
10 fmt.Println(aa)
(gdb) n
1
12 i := getObj()
(gdb) s
main.getObj (~r0=824634101464) at /opt/newobj.go:22
22 func getObj() int{
(gdb)
23 i := 2
(gdb) s
25 return i
(gdb) s
1
(gdb) n
main.main () at /opt/newobj.go:14
14 fmt.Println(i)
(gdb) n
2
16 ii := getHeapObj()
(gdb) s
main.getHeapObj (~r0=0xc00005ced8) at /opt/newobj.go:28
28 func getHeapObj() *int{
(gdb) s
29 i := 3
(gdb) s
runtime.newobject (typ=0x10a1e60 <type.*+53984>, ~r1=
1150 func newobject(typ *_type) unsafe.Pointer {
(gdb) n
1151 return mallocgc(typ.size, typ, true)
(gdb) n
main.getHeapObj (~r0=0x0) at /opt/newobj.go:31
31 return &i
(gdb) n
main.main () at /opt/newobj.go:18
18 fmt.Println(ii,*ii)
(gdb) n
0xc0000a6020 3
20 }
(gdb) n
runtime.main () at /opt/code/go/src/runtime/proc.go:212
212 if atomic.Load(&runningPanicDefers) != 0 {
(gdb) n
221 if atomic.Load(&panicking) != 0 {
(gdb) n
225 exit(0)
(gdb) n
[Inferior 1 (process 93047) exited normally]
可以看到在函数getHeapObj中，返回了变量i的地址，所以i在堆中分配内存，分配内存调用了runtime中的函数newobject
3 内存回收过程
参考：
malloc 底层实现及原理
图解 TCMalloc
go源码分析之内存池
【golang 源码分析】内存分配与管理
【Golang源码探索】(三) GC的实现原理
http://xiaorui.cc/2018/06/23/strace%E5%88%86%E6%9E%90%E8%BF%BD%E8%B8%AAmalloc%E7%94%B3%E8%AF%B7%E5%86%85%E5%AD%98%E8%BF%87%E7%A8%8B/
https://baijiahao.baidu.com/s?id=1593027501592122915&wfr=spider&for=pc
https://www.cnblogs.com/williamjie/p/9493073.html
