JAVA内存分配算法分析

内存空洞及内存分配算法研究

前言 .................................................................................................................................................. 2

几个简单的场景(Linux 64位下测试)： ....................................................................................... 2

Linux默认的内存分配机制 ............................................................................................................ 3

1. glibc的内存分配机制：................................................................................................. 4

2. glibc的内存释放机制：................................................................................................. 5

为什么会有内存空洞 ....................................................................................................................... 5

Fastbin介绍 .................................................................................................................................... 6

3. Linux多线程环境下内存空洞所占内存可能会翻数倍 ................................................ 6

4. Stlport内存管理相关说明 ............................................................................................. 8

Glibc常见内存管理参数介绍 ........................................................................................................ 9

如何消除内存空洞的影响 ............................................................................................................. 10

1. 内存空洞的外在现象 ..................................................................................................... 11

2. 一个判断是否有内存空洞的脚本 ................................................................................. 11

3. 自己实现并使用一个内存分配器 ................................................................................. 13

其它的内存分配器介绍及使用 ..................................................................................................... 18

4. 实现的一个内存泄露检查工具 ..................................................................................... 18

总结 ................................................................................................................................................ 19

前言

内存泄露一直是C或C++程序员的一个很头疼的问题，但更严重的是有些时候我们发现即使我们调用free或delete释放了内存，进程占用内存也不下降，这也给很多程序员以藉口，如果发现内存使用量增长，要求排查时，我们往往会说，“内存我都释放了，Purify也跑过了，这是内存空洞造成的，是glibc的行为我也无能为力。事实上也是，简单的分配不释放的内存泄露问题一般在开发者测试阶段甚至之前就可以排查掉，但这并不代表没有内存问题，特别是对于电信领域，很多程序运行数月甚至数年都不会停，很多很小的问题在乘以时间后会无限放大。

本文首先介绍了Linux的内存分配机制，以及在真实场景下引发的问题，并提出了一些解决方法，并介绍了如何实现并使用一个简单的内存分配器，以及项目组实现的判断是否有内存空洞的一个脚本，和一个内存泄露检查工具。

几个简单的场景(Linux 64位下测试)：

 连续分配1001块100K的内存，把前面分配的1000块内存释放掉，此时通过top检查进程所占内存，发现内存完全不会下降；

 每次分配一块8字节内存，和一块100K的内存，连续分配1000次，然后依次把这些内存全部释放，此时通过top检查进程所占内存，发现内存不会下降；

 多线程下同样的内存使用不当的程序，Linux上内存上涨量可能会是数倍于AIX

 10M左右的文本数据，如果以一定的格式存储于stlport的数据结构中，实际占用内存会膨胀100倍以上

上述的几种场景看似简单，但实际上却都是真实的血淋淋的案例抽象出来的，有些案例的定位花费了大量的人力，而这些场景往往都是purify之类工具测试不出来的，下面通过介绍linux的内存分配机制来解释上述场景，并提出解决方案。

Linux默认的内存分配机制

针对内存的管理，Linux内核提供了两个系统调用brk和mmap。brk用于更改堆顶地址，而mmap则为进程分配一块虚拟地址空间，glibc通过这两个系统调用管理内存。

那么是不是我们的程序每一次调用malloc、new时，都会去调用系统调用brk调整堆顶地址或mmap分配一块空间呢？

不会，因为它面对这两个难题：

1. 在用户态进程申请内存是以字节为单位，而在内核中内存的管理是以页面（4K）为单位，这中间存在一个差距。

2. 太多的系统调用，会使进程的速度变得很慢。

为了解决前面所提到了两个难题，我们需要一个代理的机制，它所要完成的工作：

1. 接收程序的内存请求，将其积少成多，然后统一向Linux内核申请内存。

2. 要想办法避免频繁的系统调用导致进程速度变慢。

3. 减少内存碎片的产生。

glibc的内存分配器就是这样一个实现，在用户调用malloc或free时glibc接收这个请求，具体流程参考下图

1. glibc的内存分配机制：

如果分配的内存小于M_MMAP_THRESHOLD(默认128K)，glibc通过brk调整堆顶地址获取内存，并通过内部的算法管理这些内存，这些内存在被释放后，glibc内部会尝试合并这些内存，如果被释放的内存在堆的顶部，而且达到一定阀值才会还给系统，否则会被持有在glibc内部；如果分配的内存大于M_MMAP_THRESHOLD，则通过mmap直接从系统中分配一块内存，这种内存可以马上释放；

2. glibc的内存释放机制：

当调用free去释放内存的时候，对于mmap分配的内存，会立即释放，归还给操作系统。而对于小于128k通过brk方式分配的内存，在一定情况下才会真正还给操作系统。glibc会从堆的最大线性地址开始，从后向前计算用户任务当前有多少空闲的堆内存（直到碰到使用中的堆内存地址为止），只有在该值大于某个特定的阈值时（默认为128k），它才会把这些内存归还给系统。

为什么会有内存空洞

如下图所示，如果8K这段内存不释放，glibc计算出当前空闲的堆内存为仅为64k，小于128k，便不会将此内存还给操作系统，这就是所谓的内存空洞，即堆中间的一块区域，大部分内存都释放了，堆顶还有一些内存；

真实场景：某内存池实现

某内存池实现：每次池内内存用光，都再次分配一大一小两块内存，大的内存切割成固定大小内存块用于存放消息，小的内存切割成大量32个字节的内存，用于指向每个内存块，小块内存小于128K，而且由于小块内存占用内存很少，所以永远不释放，便于下次直接使用。而使用它的进程是一个容器，可以动态加载业务，业务独占线程，而且可能在呼叫过程中动态分配内存，结果由于某个业务在呼叫过程中分配大量内存，而内存池在消息较多时进行了一次内存池的扩充，导致堆顶有一块内存池的小块内存永远不释放，最终导致业

务动态分配的内存始终无法释放，物理内存耗尽系统挂死，后调低M_MMAP_THRESHOLD阀值规避。

Fastbin介绍

Linux默认的内存分配器是启用了fastbin的，fastbins小块内存阀值默认为64字节，小于该阀值的小块空闲内存glibc将不会尝试合并，便于下次避免分配，但这同样会导到上文所描述的内存空洞，这也就是本文前面所描述的第二种场景。

3. Linux多线程环境下内存空洞所占内存可能会翻数倍

malloc在heap里分配内存时需要操作全局数据结构，所以要用锁来保护，同一进程不同线程在malloc时要先获得锁。如果只有一个heap，那么线程多起来之后，这个锁就会成为一个瓶颈。Linux的malloc的解决方式是如果一个线程获得不了当前已存在的heap的锁的时候，就创建一个新的只属于这个线程的heap，称之为arena。这个arena是通过mmap匿名内存（MAP_ANONYMOUS）来获得的。不过malloc不会在不同的arena之间移动内存块，这样可能就会造成内存不能被充分利用。比如某个线程A第一次加载文件的时候可能会造成几百兆的内存空洞。如果下次再加载文件时有别的线程正在操作内存，那它可能会被分配给一个新的arena，那么就要多增加几百M内存的使用量。

真实场景：download，数据量8.5w条(10M左右的unl文件)

某系统，导入一个大的数据文件，导入前先把文件读到内存中的stlport的某些数据结构中，大约占用2G左右，然后调用sqlite导入DB，但sqlite在导

入过程中会分配一些8K左右内存做cache，而且短时间内不会释放，在这种场景下会导致内存空洞，而且同样的场景glibc占用的内存,比另一个内存分配器tcmalloc多出3G，后通过降低内存峰值，不把所有导入内容读入内存解决

下图为：suse 10 64bit环境, 使用glibc的内存分配

可以看到第一次涨了2个G，前面几次大量上涨，在后面几次时，每次导入，会有一个峰值，但基本回落到5G左右

下图为： SUSE 10 64bit环境，使用tcmalloc库进行内存分配

分配内存第一次直接涨了2个G，后面又有几次小量上涨，到大概7次的时候虚拟内存稳定，每次导入，也只是物理内存波动，虚拟内存不波动；

4. Stlport内存管理相关说明

stlport memory pool的整体思想是维护128/8 = 16个自由链表，这里的8是小型区块的上调边界，它有个选项_STLP_USE_MALLOC可以控制是否需要使用stlport自己的内存配置器，每个自由链表串接的区块大小如下：

序号 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

串接8 16 24 32 40 48 56 64 72 80 88 96 104 112 120 128

区块

范围 19-17-25-33-41-49-57-65-73-81-89-97-105-113-121--16 24 32 40 48 56 64 72 80 88 96 104 112 120 128

8

真实场景：stlport使用不当，导致内存大量上涨

某管理服务做统计查询时，是基于session池实现的，session池maxSize为4000，在做统计查询时，会有一些信息会放在session的一个map中一直持有，所以只要通过某个session查询过某个category，那这个category的信息

就会被这个session一直持有，而哪个session对应哪个category是随机的，现网一共1032个category，也就是说最多4000个session每个session持有1032个category信息，每个category内部最多有49个item，虽然每个item所占内存并不大，但由于存储在一个双层map中，本身又是string，stlport为维护整个数据结构所占内存远超过item本身内存，可能是它本身的数十倍，实际情况超过10G，而且随查询次数的增加，同一个session查询同一个category的概率越来越大，所以它的增长曲线很怪异，持续上涨但越来越缓，期间再次大量上涨是由于现网新装了一批业务category数变多了，可以看到最后内存涨到了16G

所以不能因为stlport的变量一般变栈变量，就不考虑它所占内存，使用不当同样会造成灾难性的后果，而且这种问题用一般的泄露工具无法检测，也不是内存空洞，较难定位和发现。

Glibc常见内存管理参数介绍

 M_TRIM_THRESHOLD：堆顶内存回收阀值，当堆顶连续空闲内存数量大于该阀值时，libc的内存管理其将调用系统调用brk，来调整堆顶地址，释

放内存。该值缺省为128k。

 M_TOP_PAD：该参数决定了，当libc内存管理器调用brk释放内存时，堆顶还需要保留的空闲内存数量。该值缺省为0.

 M_MMAP_THRESHOLD：libc中大块内存阀值，大于该阀值的内存申请，内存管理器将使用mmap系统调用申请内存；如果小于该阀值的内存申请，内存管理其使用brk系统调用来扩展堆顶指针。该阀值缺省值为128kB。

 M_MMAP_MAX：该进程中最多使用mmap分配地址段的数量。

 M_MXFAST：fastbin阀值，，当小于或者等于MXFAST的小块内存释放时，并不会触发堆段顶端内存释放，堆顶内存释放被延迟到大于MXFAST的内存释放时触发。

通过禁用fastbin，并适当调低M_MMAP_THRESHOLD和M_TRIM_THRESHOLD可以更大可能的避免内存空洞，但要考虑到这些参数所带来的负面影响，如更多的系统调用导致系统变慢。

如何消除内存空洞的影响

如果想消除内存空洞的影响，就要求我们在申请和释放内存时，要严格依照就近原则，最先释放堆顶地址的内存。可控制内存的申请和释放的顺序难度十分的大；另外由于内存碎片的影响，每次申请得到的内存地址都带有一定的随机性，后面申请的内存，并不一定就意味着在堆顶；这简直是不可完成的任务。

1. 内存空洞的外在现象

实际上内存空洞和内存泄露是有区别的，内存泄露如果持续同样的操作内存基本呈线性增长，内存空洞是申请并释放了的内存由于不处于堆顶无法返还给系统，但是这些内存还是能留给进程自身使用，所以如果你做多次同样的操作，进程所使用的内存应该最终停留在一个水平线上，不怎么增长，或者增长不多，程序员可以根据这个现象来判断，你的进程中存在的是内存泄漏还是内存空洞。

2. 一个判断是否有内存空洞的脚本

这是我写的一个脚本，可以判断是否有内存空洞，直接把进程pid做为参数，即可打印出进程的内存信息，原理为glibc提供了malloc_stats和mallinfo方法，可以打印出进程的堆内存信息。

print_malloc_ 脚本

#!/bin/ksh

if [ $# -ne 1 ]; then

return 1

fi

pid=$1;

gdbpath=./

#echo file ${ENIP_HOME}/bin/container >>$gdbpath

echo attach ${pid} >>$gdbpath

echo "p malloc_stats()" >>$gdbpath

echo q >>$gdbpath

echo y >>$gdbpath

#run containerxx_

gdb -command ./ -quiet 1>/dev/null 2>/dev/null

rm -f ./

return 0

Arena 0为进程本身的heap

arena 1, 2, 3指glibc为某个线程分配出来的heap

system bytes和in use bytes表示堆占用内存大小和用户未释放的内存大小，两者差值即为内存空洞

如果发现是内存空洞该如何解决：

1,自己写一个符合自己要求的内存分配器来替换Linux自带的；

2,使用更符合要求的内存分配器

3. 自己实现并使用一个内存分配器

根据前文描述，所谓的内存分配器实际就是接收程序的内存请求，将其积少成多，然后统一向Linux内核申请或释放内存，本节将通过一个简单的内存分配器的实现来帮助说明管理内存时都涉及到了哪些事情；

全局变量定义

int has_initialized = 0;

void *managed_memory_start;

void *last_valid_address;

内存控制块定义

struct mem_control_block {

int is_available;

int size;

};

内存分配器初始化

void malloc_init()

{

last_valid_address = sbrk(0);

managed_memory_start = last_valid_address;

has_initialized = 1;

}

Free实现

void free(void *firstbyte) {

struct mem_control_block *mcb;

mcb = firstbyte - sizeof(struct mem_control_block);

mcb->is_available = 1;

return;

}

Malloc实现伪代码

1. 如果内存分配器没有初始化，先初始化.

2. 将请求分配的地址加上内存控制块所需地址得到实际需要分配的大小.

3. 找到堆的起始地址

4. 遍历所有当前管理的内存块

5. 如果内存块空闲，且大于请求大小，将其标记为空闲，返回这个内存块的地址

6. 如果没有找到可用或足够大的内存块，通过sbrk去向操作系统请求空间

编译

gcc -shared -fpic malloc.c -o

替换标准的malloc

LD_PRELOAD=./

export LD_PRELOAD

Mymalloc.c代码范例：

/* Include the sbrk function */

#include

int has_initialized = 0;

void *managed_memory_start;

void *last_valid_address;

void malloc_init()

{

last_valid_address = sbrk(0);

managed_memory_start = last_valid_address;

has_initialized = 1;

}

struct mem_control_block {

};

void free(void *firstbyte) {

}

struct mem_control_block *mcb;

mcb = firstbyte - sizeof(struct mem_control_block);

mcb->is_available = 1;

return;

int is_available;

int size;

/*

1. 如果内存分配器没有初始化，先初始化.

2. 将请求分配的地址加上内存控制块所需地址得到实际需要分配的大小.

3. 找到堆的起始地址

4. 遍历所有当前管理的内存块

5. 如果内存块空闲，且大于请求大小，将此内存块标记为空闲，返回这个内存块的地址

6. 如果没有找到可用或足够大的内存块，通过sbrk去向操作系统请求空间

*/

void *malloc(long numbytes) {

struct mem_control_block *current_location_mcb;

void *memory_location;

if(! has_initialized)

}

numbytes = numbytes + sizeof(struct mem_control_block);

memory_location = 0;

current_location = managed_memory_start;

while(current_location != last_valid_address)

malloc_init();

{

void *current_location;

{

}

current_location_mcb =

(struct mem_control_block *)current_location;

if(current_location_mcb->is_available)

{

}

current_location = current_location +

current_location_mcb->size;

if(current_location_mcb->size >= numbytes)

{

}

current_location_mcb->is_available = 0;

memory_location = current_location;

break;

if(! memory_location)

{

sbrk(numbytes);

memory_location = last_valid_address;

last_valid_address = last_valid_address + numbytes;

current_location_mcb = memory_location;

}

current_location_mcb->is_available = 0;

current_location_mcb->size = numbytes;

memory_location = memory_location + sizeof(struct

mem_control_block);

}

这个内存分配器，分配较慢，但释放很快，而且并没有真正把内存还给系统，并不算一个真正的内存分配器，但它可以工作，如果需要定制一个内存分配器至少应该考虑以下几点：

 分配的速度；

 回收的速度；

 多线程环境的行为；

 内存将要被用光时的行为；

 局部缓存；

 簿记（Bookkeeping）内存开销；

 虚拟内存环境中的行为；

 小的或者大的对象的行为；

 实时保证；

return memory_location;

其它的内存分配器介绍及使用

 BSD Malloc：BSD Malloc 是随 4.2 BSD 发行的实现，包含在 FreeBSD

之中，这个分配程序可以从预先确定大小的对象构成的池中分配对象。它有一些用于对象大小的 size 类，这些对象的大小为 2 的若干次幂减去某一常数。所以，如果您请求给定大小的一个对象，它就简单地分配一个与之匹配的 size 类。这样就提供了一个快速的实现，但是可能会浪费内存。据说这种算法可以消除内存空洞，因为它把原来的一个内存段，编程了多个内存段，从而减小了内存空洞的影响，而性能下降不多。

 Tcmalloc：TCMalloc是google-perftools套件的一部分, Google-perftools是Google开发的开放源代码C++性能调整工具库, 特别为多线程C++程序的开发提供支持，它比glic的实现ptmalloc2快6倍，ptmalloc2一次malloc和free操作约要300ns，tcmalloc只需约50ns，周期性的内存回收，避免ptmalloc2中多线程下可能出现的内存爆炸式增长的问题，tcmalloc会在线程cache和中心内存堆栈之间迁移空闲对象。尽量避免加锁（一次加锁解锁约浪费100ns），使用更高效的spinlock，采用更合理的粒度。

4. 实现的一个内存泄露检查工具

核心思想是自己包装现有的内存分配器，在分配与释放时记录，识别出超过一定时间的分配而未释放的内存，再通过一个工具对结果进行扫描，可以轻易的识别出长时间分配而未释放的内存，包括一些stlport分配的，从代码逻辑来看

最终会释放，但实际还未释放的内存，然后再对未释放的内存是进行排查。基于这个工具，项目组发现了不少隐藏很深的内存泄露

总结

 在申请分配内存时，本着就近原则，需要的时候才分配内存，不需要了立刻释放;

 要清楚的了解所使用的第三方库的内存分配和使用策略，如stlport,xerces,sqlite等，以及程序所使用的内存分配器的行为，否则极容易导致内存无法释放;

 尽量分配大小为2的幂的内存块，而最大限度地降低潜在的malloc性能丧失。这样做最大限度地减少了进入空闲链的怪异片段（各种尺寸的小片段都有）的数量;

 尽量减少系统所使用的内存峰值，这样即使出现内存空洞也问题不大；

 基于产品对内存策略进行整体规划，如在某些产品的经验是动态分配尽量在初始阶段完成,运行阶段较少分配和释放内存；

 如果依然使用glibc的内存分配器，可以考虑对部分参数进行调优;

 可以考虑使用现有的更好的内存分配器，或定制一个更适合产品的内存分配器;

 内存空洞还是内存泄露可以用非常简单的方式检查出来，但它们造成的影响是同样恶劣的，都需要找到原因彻底解决;