linux内存寻址

3种地址：虚拟地址、物理地址、逻辑地址
物理地址：内存的电路地址，对应内存地址线上的高低电平，物理可见的。
虚拟地址：分页机制的产物，也叫线性地址，是进程能看见的地址。
逻辑地址：分段机制的产物，属于inter cpu的历史遗留问题，linux可以当做不存在。
3种地址的转换：进程访问逻辑地址，linux内核根据分段机制装换成虚拟地址，然后把进程的页表和虚拟地址都告诉cpu，cpu就可以根据分页机制将虚拟地址装换成物理地址，然后访问内存。
linux内核中巧妙地屏蔽里分段机制，就是逻辑地址等于虚拟地址，访问内存只需要利用分页机制把虚拟地址转换成物理地址。

linux进程地址空间

linux会为每个进程创建自己的虚拟地址空间，就是进程地址空间，64位系统就是128T的内存空间。需要注意的是，虚拟地址就是假的，一开始不和物理地址对应，也就是说不占用物理内存，只有当虚拟地址有写入操作是，内核会触发缺页，分配真实的物理地址给虚拟地址。物理地址的管理可参考内核内存管理

image.png

linux进程内存分配

从进程空间看，用户态闲置内存有3块，Stack、Memory Mapping Region、Heap，Stack是程序函数调用运行时需要的，不可控，能自由分配的内存就剩Memory Mapping Region、Heap了，linux系统提供的内存分配函数就是针对这两个区域的。
Heap操作函数：int brk(void *addr)、void *sbrk(intptr_t increment)
Memory Mapping Region操作函数：mmap()、munmap()

内存管理模块

当然进程可以直接使用系统调用去申请内存，但是如果不管理的话，经过大量的申请和释放，会把进程空间切割的乱七八糟，导致不能申请大块的连续空间，为此就出现了内存管理模块，封装了系统调用，对进程提供malloc和free等高级函数。实际上，除了一些特殊程序，我们也很少用系统调用，一般都是使用内存管理模块提供的malloc和free，关系如下图：

内存管理.png

内存管理模块用各种好处，例如不会每次操作都去执行系统调用，减少内存碎片的产生等等。
当然也有很多实现方式，例如常用的glibc的Ptmalloc，google的tcmalloc，facebook的jemalloc等。各有各的应用场景，blablabla....
使用时，gcc默认会链接glibc的，如果想使用其他lib，gcc链接时指定就能覆盖掉glibc的。

Ptmalloc

我们重点讲Ptmalloc，从而启发程序员在写程序时多考虑下内存分配情况，可以选择或自己实现适合自己程序的内存管理lib。
Ptmalloc的历史发展，blablabla......，Ptmalloc采取内存池管理，进程malloc时，通过brk（小于128K的内存）、mmap（大内存）从系统获取地址空间，给进程使用，进程free时，不会立即通过brk、munmap将地址空间还给系统，会自己维护起来，叫做空闲内存，这些空闲内存在进程再次malloc时，还会被分出去，并且空闲内存会在特定条件下合并起来还给系统。

arena

内存分配区，管理了一片内存，对外分发和回收，可以理解为一个内存池，分main arena和non main arena。
main arena：最早的分配区，管理着所有可分配的内存，通过brk，mmap等系统调用向系统申请内存。注意只有main arena可以操作Heap。
non main arena：由于多线程的出现，如果多有线程都操作main arena就会有竞争，需要加锁控制，所以出现了non main arena，通过mmap向main arena申请一大块内存，然后自己管理，可以理解为内存分销商。
只有主线程在main arena上申请内存，子线程在non main arena上，non main arena的个数是有上限的，所以non main arena允许多个子线程共用，这样就涉及到加锁，所以程序涉及应避免子线程个数太多。

chunk

进程申请到的一块内存叫做一个内存片，arena内部使用chunk数据结构来描述内存片，包括进程正在使用的内存片，和进程free掉的空闲内存片

image.png

A：是否main arena内存
M：使用mmap内存
P：上一块是否被使用
size of previous chunk：上一块没有被使用时，表示上块长度，被使用时是上块用来存User data的。
Size of chunk：就是下一块的size of previous chunk，释放时填上本块长度，供下块合并用。

空闲chunk的组织

分给进程的内存片arena可以不管，但是进程free回来的，arena需要通过一定方式组织起来，方便进程再次使用。组织方式有下面几种：

bins

bins是个数组，包含128个bin，每个bin是个链表，分small bin和large bin两种，各64个，small bin中chunk大小固定，两个相邻的small bin中的chunk大小相差8bytes，large bin中chunk大小是一定范围内的，其中的chunk按大小排列。
空闲chunk按大小选择合适的bin，按新旧顺序挂到链表上，优先分配旧的chunk。

image.png

fast bins

不大于max_fast （默认值为64B）的chunk被释放后，首先会被放到fast bins 中，fast bins中的chunk并不改变它的使用标志P。这样也就无法将它们合并，当需要给用户分配的chunk小于或等于max_fast时，ptmalloc首先会在fast bins中查找相应的空闲块。在特定的时候，ptmalloc会遍历fast bins中的chunk，将相邻的空闲chunk进行合并，并将合并后的chunk加入unsorted bin中。

unsorted bin

进行malloc时，如果在fast bins中没有找到合适的chunk，则ptmalloc会先在unsorted bin中查找合适的空闲chunk，如果unsorted bin不能满足分配要求。malloc便会将unsorted bin中的chunk加入bins中。然后再从bins中继续进行查找和分配过程。从这个过程可以看出来，unsorted bin可以看做是bins的一个缓冲区，增加它只是为了加快分配的速度。

特殊chunk

top chunk

前面的bin中都是回收回来的内存，top chunk才是内存的初始来源，每个arena都有一个top chunk，用来管理Heap的，Heap会在arena第一次分配内存时初始化，会分配一块(chunk_size + 128K) align 4K的空间（132K）作为初始的Heap，top chunk占据整个空间，每次分配会在低地址出切出一片，如下图：

top chunk (1).png

回收时，只有和top chunk相连的内存才能和top chunk合并，才能进而还给系统。

子线程Heap：在main arena中mmap出64M的空间，叫做sub-heap，再在sub-heap上初始化Heap。
主线程的Heap才是真Heap，使用进程Heap，使用brk申请内存。

image.png

子线程的heap不够用时，会在申请新的sub-heap，和老的sub-heap单向链表连起来，top chunk会搬到新sub-heap上。

image.png

mmaped chunk

描述mmap出来的内存，单独管理，free时按阈值来决定是否munmap，有动态调整阈值功能，防止太频繁的mmap和munmap。本文不关注。

Last remainder

即最后一次small request中因分割而得到的剩余部分，它有利于改进引用局部性，也即后续对 small chunk 的 malloc 请求可能最终被分配得彼此靠近。
当用户请求 small chunk而无法从small bin和unsorted bin得到时，会在large bin中找最合适的chunk，然后做切割，返回给用户的User chunk，剩下的是Remainder chunk添加到unsorted bin中。这一Remainder chunk就将成为last remainder chunk。

分配和回收

malloc小于128K的内存

1. 获取arena锁。
2. 将用户的请求大小转换为实际需要分配的chunk空间大小。
3. 判断所需分配chunk的大小是否满足chunk_size <= max_fast (max_fast 默认为 64B)，如果是的话，则转下一步，否则跳到第5步。
4. 首先尝试在fast bins中取一个所需大小的chunk分配给用户。如果可以找到，则分配结束。否则转到下一步。
5. 判断所需大小是否处在small bins中，即判断chunk_size < 512B是否成立。如果chunk大小处在small bins中，则转下一步，否则转到第6步。
6. 根据所需分配的chunk的大小，找到具体所在的某个small bin，从该bin的尾部摘取一个恰好满足大小的chunk。若成功，则分配结束，否则，转到下一步。
7. 到了这一步，说明需要分配的是一块大的内存，或者small bins中找不到合适的 chunk。于是，ptmalloc首先会遍历fast bins中的chunk，将相邻的chunk进行合并，并链接到unsorted bin中，然后遍历unsorted bin中的chunk，如果unsorted bin只有一个chunk，并且这个chunk在上次分配时被使用过，并且所需分配的chunk大小属于small bins，并且chunk的大小大于等于需要分配的大小，这种情况下就直接将该chunk进行切割，分配结束，否则将根据chunk的空间大小将其放入small bins或是large bins中，遍历完成后，转入下一步。
8. 到了这一步，说明需要分配的是一块大的内存，或者small bins和unsorted bin中都找不到合适的 chunk，并且fast bins和unsorted bin中所有的chunk都清除干净了。从large bins中按照“smallest-first，best-fit”原则，找一个合适的 chunk，从中划分一块所需大小的chunk，并将剩下的部分链接回到bins中。若操作成功，则分配结束，否则转到下一步。
9. 如果搜索fast bins和bins都没有找到合适的chunk，那么就需要操作top chunk来进行分配了。判断top chunk大小是否满足所需chunk的大小，如果是，则从top chunk中分出一块来。否则转到下一步。
10. 到了这一步，说明top chunk也不能满足分配要求，所以，于是就有了两个选择: 如果是主分配区，调用sbrk()，增加top chunk大小；如果是非主分配区，调用mmap来分配一个新的sub-heap，增加top chunk大小。扩大top chunk后，切分内存片，返回给用户。

free过程

下一块为高地址，前一块为低地址。

1. free()函数同样首先需要获取分配区的锁，来保证线程安全。
2. 若chunk_size <= max_fast，并且chunk不在heap顶部，也就是说不与top chunk相邻，则转到下一步，否则跳到第4步。
3. 将chunk放到fast bins中，函数返回。
4. 判断前一个chunk是否处在使用中，如果也是空闲块，则合并。并转下一步。
5. 判断当前释放chunk的下一个块是否为top chunk，如果是，则转第7步，否则转下一步。
6. 判断下一个chunk是否处在使用中，如果下一个chunk也是空闲的，则合并，并将合并后的chunk放到unsorted bin中。并转到第8步。
7. 如果执行到这一步，说明释放了一个与top chunk相邻的chunk。则无论它有多大，都将它与top chunk合并，并更新top chunk的大小等信息。转下一步。
8. 判断合并后的chunk的大小是否大于FASTBIN_CONSOLIDATION_THRESHOLD（默认64K），如果是，进行fast bins的合并操作，遍历fast bins中的chunk，与相邻的空闲chunk合并，合并后的chunk会被放到unsorted bin中。fast bins将变为空，操作完成之后转下一步。
9. 判断top chunk的大小是否大于mmap收缩阈值（默认为128KB），如果是的话，对于主分配区，则会试图归还top chunk中的一部分给操作系统，但是初始化的132KB空间是不会归还的；如果为非主分配区，会进行sub-heap收缩，将top chunk的一部分返回给操作系统，如果top chunk为整个sub-heap，会把整个sub-heap还回给操作系统。做完这一步之后，释放结束，从 free() 函数退出。

使用注意事项

1. 后分配的内存先释放，因为ptmalloc收缩内存是从top chunk开始，如果与top chunk相邻的chunk不能释放，top chunk以下的chunk都无法释放。
2. 尽量减少程序的线程数量和避免频繁分配/释放内存。频繁分配，会导致锁的竞争，最终导致非主分配区增加，内存碎片增高，并且性能降低。
3. 防止内存泄露，ptmalloc对内存泄露是相当敏感的，根据它的内存收缩机制，如果与top chunk相邻的那个chunk没有回收，将导致top chunk一下很多的空闲内存都无法返回给操作系统。

引用

Glibc内存管理 华庭（庄明强）