glibc的malloc–更多的改进_glic多,下。呢

前面说过glibc实现了malloc，它实现linux系统的堆管理，在linux中没有专有的所谓的API，所有的调用几乎都以c库为根本，因此glibc显得尤为重要，glibc的实现抛开自己的独特策略不说它和windows的实现是一样的，都是维护一个全局的链表，然后每一个链表元素由固定大小内存块或者不固定大小的内存块组成，和windows不同的是，glibc维护了不止一个不定长的内存块链表，而是好几个，每一个这种链表负责一个大小范围，这种做法有效减少了分配大内存时的遍历开销，类似于哈希的方式，将很大的范围的数据散列到有限的几个小的范围内而不是所有数据都放在一起，虽然最终还是要在小的范围内查找，但是最起码省去了很多的开销，如果只有一个不定长链表那么就要全部遍历，如果分成3个，就省去了2/3的开销，总之这个策略十分类似于散列。glibc另外的策略就是不止维护一类空闲链表，而是另外再维护一个缓冲链表和一个高速缓冲链表，在分配的时候首先在高速缓存中查找，失败之后再在空闲链表查找，如果找到的内存块比较大，那么将切割之后的剩余内存块插入到缓存链表，如果空闲链表查找失败那么就往缓存链表中查找，这么查找有什么依据吗？实际上是有的，正是这个方式让glibc有了自己的策略。

这种依据在free的时候体现。如果能合并在堆顶，也就是能和堆顶的空闲元素合并，那么就合并，因为堆的缩减仅仅在堆顶的空闲元素达到一定量的时候才会进行，因此为了尽快将内存归还操作系统，尽量优先考虑堆顶的释放，但是如果不能合并，比如它和堆顶根本就没有相邻，那么如果该释放的块大小小于80字节，那么就直接将之挂在高速缓存中，为了防止别的块和它合并所以并不更改使用位，这里可以看到，glibc实际上为小于80字节的小内存块维护了一个高速的内存池，如果有小块内存需求，直接从此池中拿走一个即可，只需要从高速缓存摘除之并不需要修改使用位，因为高速缓存中的元素的使用位均为1，这个高速缓存在有大内存块分配需求并且几个分配策略都失败的时候会被回收，回收进空闲链表的过程涉及到相邻块的合并，合并之后就有可能满足稍微大一些的内存分配需求，这里为何将界限定位为80个字节呢？实际上是一个经验值，那么介于80字节和128k字节之间的内存块在释放的时候要将使用位设置为0，然后试图和相邻块合并，然后挂入缓存链表。

下面的这段话摘自于一篇文章，比较详细的阐述了glibc的内存分配和释放的过程，前提是分配大小小于128k：

1.堆是通过brk的方式来增长或压缩的，如果在现有的堆中不能找到合适的chunk，会通过增长堆的方式来满足分配，如果堆顶的空闲块超过一定的阀值会收缩堆，所以只要堆顶的空间没释放，堆是一直不会收缩的。

2.堆中的分配信息是通过两个方式来记录。第一．是通过chunk的头，chunk中的头一个字是记录前一个chunk的大小，第二个字是记录当前chunk的大小和一些标志位，从第三个字开始是要使用的内存。所以通过内存地址可以找到chunk，通过chunk也可以找到内存地址。还可以找到相邻的下一个chunk，和相邻的前一个chunk。一个堆完全是由n个chunk组成。第二．是由3种队列记录，只用空闲chunk才会出现在队列中，使用的chunk不会出现在队列中。如果内存块是空闲的它会挂到其中一个队列中，它是通过内存复用的方式，使用空闲chunk的第3个字和第4个字当作它的前链和后链（变长块是第5个字和第6个字），省的再分配空间给它。第一种队列是bins，bins有128个队列，前64个队列是定长的，每隔8个字节大小的块分配在一个队列，后面的64个队列是不定长的，就是在一个范围长度的都分配在一个队列中。所有长度小于512字节（大约）的都分配在定长的队列中。后面的64个队列是变长的队列，每个队列中的chunk都是从小到大排列的。第二种队列是unsort队列（只有一个队列），（是一个缓冲）所有free下来的如果要进入bins队列中都要经过unsort队列。第三种队列是fastbins，大约有10个定长队列，（是一个高速缓冲）所有free下来的并且长度是小于80的chunk就会进入这种队列中。进入此队列的chunk在free的时候并不修改使用位，目的是为了避免被相邻的块合并掉。

3.malloc的步骤

-->先在fastbins中找，如果能找到，从队列中取下后（不需要再置使用位为1了）立刻返回。

-->判断需求的块是否在小箱子（bins的前64个bin）范围，如果在小箱子的范围，并且刚好有需求的块，则直接返回内存地址；如果范围在大箱子（bins的后64个bin）里，则触发consolidate。（因为在大箱子找一般都要切割，所以要优先合并，避免过多碎片）

-->然后在unsort中取出一个chunk，如果能找到刚好和想要的chunk相同大小的chunk，立刻返回，如果不是想要chunk大小的chunk，就把他插入到bins对应的队列中去。转3，直到清空，或者一次循环了10000次。

-->然后才在bins中找，找到一个最小的能符合需求的chunk从队列中取下，如果剩下的大小还能建一个chunk，就把chunk分成两个部分，把剩下的chunk插入到unsort队列中去，把chunk的内存地址返回。

-->在topchunk（是堆顶的一个chunk，不会放到任何一个队列里的）找，如果能切出符合要求的，把剩下的一部分当作topchunk，然后返回内存地址。

-->如果fastbins不为空，触发consolidate即把所有的fanbins清空（是把fanbins的使用位置0，把相邻的块合并起来，然后挂到unsort队列中去），然后继续第3步。

-->还找不到话就调用sysalloc，其实就是增长堆了。然后返回内存地址。

4.free的步骤

-->如果和topchunk相邻，直接和topchunk合并，不会放到其他的空闲队列中去。

-->如果释放的大小小于80字节，就把它挂到fastbins中去，使用位仍然为1，当然更不会去合并相邻块。

-->如果释放块大小介于80-128k，把chunk的使用位置成0，然后试图合并相邻块，挂到unsort队列中去，如果合并后的大小大于64k，也会触发consolidate，（可能是周围比较多小块了吧），然后才试图去收缩堆。（收缩堆的条件是当前free的块大小加上前后能合并chunk的大小大于64k，并且要堆顶的大小要达到阀值，才有可能收缩堆）

以上的阐述还是很明确的，glibc分配的关键就是在于采用了一些策略，比如多个变长链表的散列策略，比如高速缓存策略以及一般缓存策略，考虑到的原因就是一般小内存的使用率比大内存要大，因此有必要为小内存维护一个高速的池，另外小内存的释放频率也高，一般都是用于存放一些临时数据的，因此为小内存维护一个池不会对其它需求不公平，缓存的优势在于它容量一般比较小，遍历查找很快，并且里面的数据几乎都是热的，，在这里，所谓的数据要过热的意义不是指内存块的内存，而是内存块的大小，一个内存块比较热的意思是说该大小的内存块被频繁使用，另一句话说就是只有频繁使用的数据才会进入缓存，并且这些数据的量不会太多，如果太多的话缓存就失去了它的查找优势，如果数据不热的话，查找就会频繁失败，最终还是要进入一般的分配模式，因此设计一个缓存系统要考虑的问题很多，绝不仅仅是理论上那么简单。还有一个策略就是堆顶的特殊处理，堆顶不放在任何一个链表中，对它进行照顾就是因为为了更有效的将内存退还操作系统，因为堆的压缩只能从堆顶开始，操作系统只知道给了一个进程虚拟内存连续的一大块叫做堆的内存，别的什么也不知道，应用程序归还的时候同样需要连续的从堆顶归还而不能仅仅归还空洞，归根结底要对堆顶进行特殊的处理