分类: C/C++
2014-09-24 12:48:50
原文地址:定制linux内存管理 作者:尘世间一迷途小码农
对于C/C++开发者,想要开发一款高性能、高稳定性的程序,最重要的问题之一就是内存管理
通常我们会使用malloc(什么,你说new?new是封装malloc的了)来分配内存,并把内存管理交给系统去做。
但是malloc的性能真的够用吗?为什么很多著名开源服务器都会自己写一套内存管理器?如果老板要我优化架构,要不要考虑把malloc给废了?
一 malloc寻根
linux下的malloc实现又叫ptmalloc(ptmalloc是dlmalloc的一种变形,所以有些地方也会直接说成dlmalloc)
当我们调用malloc时,根据申请的大小会分成截然不同的几种处理流程。小内存会进入“定长内存”系统;大内存则进入“变长内存”系统(备注1)。
“定长内存”系统会事先准备好(备注2)一系列空闲内存链表。链表中的空闲内存块都是一样大的。
分配内存时只需找到相应的链表,从链表头部取出一个空闲内存块即可。释放时也是直接插入即可。分配和释放的复杂度都是O(1)
虽然定长内存系统的分配和释放极快。但是在分配大块内存时,定长内存分配会导致大量内存碎片(内碎片),关于内存碎片分类和优化我们会在后续章节再讨论。
“变长内存”系统也会组织一系列空闲内存链表。链表中的空闲块通常是不一样大的:
在很早以前,变长内存只有1条链表,每次分配时需要遍历这个长长长长的链表以找到大小合适的内存块。
后来ptmalloc做了很多的优化,在分配速度上已经提升了很多。
变长内存会按照大小范围组织成很多个不同的链表,例如:
10K-15K属于链表1;
16K-23K属于链表2;
24K-39K属于链表3;
.........
(数值是随手写的,真实数值请google largebin_index_64)
通过分链表(或者叫分箱),每个链表的大小都会缩小很多。这样就能更快的查找到我们需要的size
总体来说,变长内存的性能比定长内存要差。分配时需要遍历会导致耗时增加,而且变长内存通常需要分裂内存块,会导致外碎片增加。
二 细节决定成败
从整体设计上来看,malloc做的相当好。
但是当我们深入一些关键的细节时,会发现malloc针对一些特殊场景,会出现很严重的问题
1 管理小内存块时浪费了大量的空间
每个内存块需要一个size_t的空间来存放本内存块的大小,供释放时使用。以64位机器为例,size_t是8字节长的。而且内存块必须在2*size_t的长度上对齐。所以当我们malloc(26)时,实际消耗的内存是48字节,浪费了45%的内存。
另外内存块有一个最小大小4*size_t。在64位机器上,最小的分配单位就是32字节。当我们需要分配大量小结构体时,malloc会导致极大的内存浪费。
验证代码请参考附件中的mem_little.cpp
2 定长小内存和变长大内存容易交错混在一起
所有内存块都是从top内存区分出来的,并没有专门给不同尺寸的内存划分专属内存池,所以定长小内存有很大几率会和变长大内存交错混在一起。
这将使得小内存块随时可能和大内存块合并(合并后就走变长内存系统了),使得定长内存的优势大打折扣,malloc时的局部性也很不好
3 释放内存时可能因为brk而被卡住
malloc的主分配区是通过brk向内核申请内存的,非主分配区通过mmap模拟brk。而brk是一个线性的分配器,类似栈。
简单来说,如果我先malloc了5G内存;再malloc 16字节,抓住这16字节不释放;然后释放前面的5G内存,这5G内存是无法还给系统的。
验证代码请参考附件中的mem_brk.cpp
malloc的这个特性对于需要长期持有而不释放的内存是极其不友好的。而且一旦出现内存泄漏,哪怕只漏了几个字节,也可能把几个G的内存释放卡住。
4 锁的性能消耗
ptmalloc的内存分配区不是和线程绑定的,所以必须在进入malloc和free时加一把大锁(针对单个分配区的锁)。虽然可以通过建立多个分配区和try_lock来降低等待锁的几率,但是锁本身也是很消耗性能的
5 低效的realloc
当需要扩大已分配的内存块时,ptmalloc将尝试从尾部扩展内存块。但是当系统内存压力较大时,这个尝试的成功率是不高的,这时就需要分配一个全新的内存块并把旧数据拷贝过去,而这将引入极其巨大的性能消耗(备注3)。
三 我们的目标
技术是为需求服务的。我之所以追求性能优化,是因为当时公司的硬件成本占总销售收入的30-40%,而公司的净利润只有10-15%
对于某些土豪行业来说(别躲了,手游,说的就是你),硬件成本只有不到5%的,就不要花太多精力去优化性能了。
我们做的是一款http正向缓存代理服务器,约等于带强大缓存功能的nginx
具体目标是在一台8核16G内存的机器上承载每秒4Gb的http流量,100万并发连接。
我们需要缓存整个互联网,所以需要上亿个10字节的结构体来存储url信息;另外还需要处理每秒4Gb的http socket数据,并尝试进行缓存写入和读出。
在连接建立时我们是不知道每个连接需要多大缓冲区的,这就需要大量的realloc来扩大已有缓冲区。
当用户下载1GB的文件时,原始服务器先将1GB文件发给我们,我们再转发给用户,这将持续相当长的一段时间。在这个过程中,我们可以把已转发给用户的部分内存先释放掉,但是可惜malloc不支持部分free。
总结成一句话就是:我们需要一个内存利用率极高的定长小内存系统和一个支持“高效realloc”和“一次malloc可分为多次free”的变长大内存系统
四 内存系统设计的一般原则
在设计内存管理系统时,我们主要关心三个方面:
内存利用率
分配和释放效率
局部性
1 内存利用率方面主要是三个问题:
内碎片:分配内存时,分配出的内存大于需要的内存叫内碎片。
例如ptmalloc中,需要8字节对齐,再加上8字节管理信息,这一部分就是内碎片(很多论文中不把管理信息算到内碎片中,而是单独计算,个人喜欢合在一起计算,方便)
如果对大内存块采用定长内存系统,前后两个定长内存块之间的大小会差的较大,从而产生较大的内碎片。这也是为什么绝大多数内存管理系统,仅对小内存块使用定长内存。
外碎片:因为空闲内存块太小导致有内存又无法分配叫外碎片
如下图,经过长时间malloc-free后,空闲内存(绿色)被分隔到成很多小碎片,就无法再malloc出大块内存了
外碎片主要是由于把变长的大内存块分裂成两个内存块而导致的。例如空闲内存块为900K,我们需要分配875K,剩下的25K被分裂出来后,就会形成外碎片
无法还给系统:在上一节中已经举例说明过这个问题,free将内存还给内存管理器后可能无法归还给系统,导致其它进程分配内存失败
2 分配释放效率:
定长分配和释放往往都是O(1)的效率
变长内存分配则通常需要遍历链表来找到大小合适的内存块。通常会通过按大小范围分箱来提高分配速度。
如果定长内存和变长内存交错在一起,定长内存会经常和变长内存合并,使得定长内存的优势体现不出来。
另外我们还可以为每个线程分配一个专属的线程池,可以避免加锁解锁的消耗。
3 局部化:
最近20年来,CPU速度提升了上万倍,内存提升了上百倍,硬盘速度提升仅有几倍,所以优化性能的关键,很多时候都不在于减少CPU的运算压力,而在于减少内存总线读写
通过提升内存的局部化,可以大幅优化CPU的cache效果,提高运行效率
验证代码请参考附件中的mem_cache.cpp
五 slab定长内存池
linux内核采用的slab算法是一个极好的定长内存管理算法
通过将若干个小定长内存集中在一个桶里,我们就不必为每个内存块维护独立的管理信息了。当我们需要读取管理信息时,对内存块取模取到桶的头部,就可以读到相关管理信息了。
同时,这还将极大的减少定长内存和变长内存交错的情况,提升分配和释放效率。
要让slab达到最高效率,我们需要事先对slab系统进行初始化,声明我们需要用到定长内存块大小(通常是某个频繁使用的struct/class),最好还能手动设定一下桶的大小。这也是为什么malloc不采用slab算法的原因。
六 大内存支持非连续化
非连续化,即我们不再要求指针指向一段连续内存。例如在传统情况下,一个10MB的缓冲区必须是连续10MB的虚拟地址。而非连续化之后,一个10MB的缓冲区可以由若干个4K的虚拟页拼接而成。
通过支持非连续内存,我们将变长内存池的问题转化成了定长内存的问题,大内存使用过程中碰到的几个最主要问题,都已经解决了。
因为所有内存块都是定长的,我们不再会有任何外碎片的问题,跑上100年也不会有外碎片。
内碎片有可能会较多,这取决于我们对内存块大小的控制。
通过实际测试,对http代理来说,采用4K和512两级内存块就可以达到90%以上的内存利用率。
在realloc重分配问题上有着极高的性能。我们随时可以从已分配内存的头部释放内存(代理服务器已转发数据的释放),也随时可以在已分配内存的尾部追加内存。
非连续内存有一个极大的缺陷:无法用常规的strcmp、memcpy系列函数处理;也无法转换成string;使用时一不小心就会踩内存。必须提供一系列函数对非连续内存池进行处理,例如jump_get_next来获取下一个字符并自动判断是否需要跳到下一个内存块。
在08年阅读nginx代码时,发现nginx就已经实现了一套非连续内存池的代码,但是并没有发现任何代码在使用这个非连续内存池。对于开源这样人员多变的开发环境,确实不太适合使用非连续内存池;但是对于人员稳定性和素质有保障的商业公司,完全可以尝试用非连续内存来提升性能。
备注1:
实际上ptmalloc会按大小维护5个级别的分配算法:
fastbin、smallbin、largebin、top、mmap
fastbin:最小的内存空闲块,属于定长内存。
smallbin:大于等于fastbin,也属于定长内存。
有一些最小的内存块,即可以属于fastbin也可以属于smallbin(优先从fastbin分配,当fastbin为空时走smallbin逻辑)
fastbin和smallbin最大的区别在于fastbin的合并更lazy一些,系统中更容易留下未被合并的fastbin;而smallbin更容易被合并掉(合并指当两个相邻内存块都是空闲时,合并成一个大的空闲内存块)
largebin大于smallbin,属于变长内存,包含大量的内存块链表,每个链表覆盖一个长度范围
top内存:top内存只有一个块,所有从内核brk上来的内存(非主分配区会通过mmap模拟brk)都会先放在这里,再分配给前面的3种内存块。当从上述3种内存块释放内存时,也必须先合并到top之后才能还给内核
mmap内存:大于一定大小的内存会直接通过mmap从内核获取,释放时直接unmmap还给内存。
备注2:
实际上这里有一个lazy的机制。
第一次malloc时并没有事先准备好的定长内存,此时需要从更高层的内存块中(例如largebin或top),速度较慢。
free时,如果大小属于fastbin会直接放入定长内存池中。如果属于smallbin,在尝试和相邻内存块合并失败时,也会放入定长内存池。
在经过一段时间的malloc和free之后,如果没有触发大量的合并,我们就可以幸运的拥有一个快速的定长内存池了
备注3:
在不同的系统中,性能的瓶颈是不一样的。在我们的http代理服务器中,CPU消耗比例大概是:
应用层消耗 5%
Tcp协议栈 20%
copy_to_user等 20%
网卡驱动 15%
其它内核函数 40%
可以看到copy_to_user和copy_from_user加起来占了20%的CPU。这两个内核函数属于recv和send的内核实现,负责在内核和应用层间拷贝socket数据。
换句话说,如果我们通过realloc将所有socket缓冲区拷贝了一遍,就会增加约20%性能消耗
验证代码压缩包: