本文共 7503 字,大约阅读时间需要 25 分钟。
还是要认真看深入理解计算机系统
内存分配是按照堆块实现的,一个堆块是由头部和有效载荷量组成,其中的有效载荷量就是我们申请的堆的大小。
头部块包括 块大小和是否可用 这两个部分组成。
在内存中这些堆块以链表形势组成
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;
}
如您所见,在这个分配程序中,内存的释放使用了一个非常简单的机制,在固定时间内完成内存释放。
(总结就一句话,stl没有侯捷书上写的有一个链表管理内存块,而是简单的调用malloc和free,我想这是因为malloc内部已经实现了内存池)
1. 背景 前些天在一个技术分享会上,某大牛说,STL使用了内存池,释放内存的时候,并不释放给OS,而是自己由留着用。 听到这些观点后,我就有些着急了,因为我以前一直是直接使用STL的一些工具类的,比如std::string、std::map、std::vector、std::list等等,从来都没有关注过内存的问题。 带着内存的问题,我花了两三天的时间去阅读STL的代码,并且写一些简单的程序进行测试;下面列举一些心得体会,但是却没有什么大的结论 -.-
2. 容易误解的简单例子 我们以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(),它们都定义在<malloc.h>里。 为了弄清楚这个问题,我们对上面的例子进行如下的改造: #include <malloc.h> 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。
3. 侯捷的《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的简单封装
4. 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_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 a1; // 方法1map