by pluskid, on 2011-08-23, in 
久别重逢是说，自从在教科书上见过它一面之后，这才是第二次碰面。也就是说，在这些年的编程经历中，从来没有遇到过吧——至少在我印象中是这样的。以至于我都开始怀疑在“平常的”程序中，它是否真正存在了。内存分配，C 里的 malloc （或者配套的函数） ，如果分配失败了会返回地址 0 ，所以，“作为良好的编程习惯，每次申请内存之后，应该检查一下返回值是不是 NULL ”，这样的“良好习惯”也许刚开始写几个程序的时候还能坚持，到后来就完全不管了——因为从来没有遇到过 malloc 返回 0 的情况，申请内存怎么会失败呢？如果连内存都申请失败了，那接下去估计也没有什么好做的了，估计系统已经处于崩溃边缘了，与其每次都费力去检查，还不如让它自生自灭好了——反正之后如果尝试去访问这个 0 地址，肯定会碰到段错误 (segment fault) 而挂掉的，当然，一个不好的地方可能就是这个挂掉的位置和最初申请内存失败的位置已经相差了十万八千里，可能追踪起来会比较麻烦。
至于 C++ 里，就更简单了，new 的时候如果申请不到那么多内存的话，会抛出 std::bad_alloc 异常，如果没把这个异常接住，让它一直跳到最顶层的话，程序会立即挂掉。比 C 更加“人性化”——当场挂掉，而不是在某个未知的其他地方 segment fault 。如此一来，就更加熟视无睹了。
总而言之，渐渐地有了这样一种印象：像内存申请失败之类的情况，大概只有在嵌入式设备等非常极端的资源匮乏的平台上编程的时候才会碰到吧。结果这次却在一个内存很大很大（256G 物理内存）的环境里遇到了。果然是和车祸之类的类似，越是在看上去很太平的路段，越会让驾驶员掉以轻心呀。
情况是这样的，在跑的是一个很大的聚类程序，聚类开始之前先要把数据从 MongoDB 读出来，由于内存很大，所有的后续操作都是在内存中进行的。不过，第二天来看状态的时候，却发现一堆的 std::bad_alloc 输出。因为程序的整个框架里用了 worker ，在里面把所有的异常都接住了，所以程序没有挂掉，而是继续很欢地跑，不过，从满屏的 bad_alloc 来看，后续的许多许多次内存分配的尝试都失败了——至少有两千个 exception 的 LOG 吧，因为 tmux 的 history buffer 被设成了那么多，所以没法看到更早的结果。
这件事情刷新了我的两个认识：第一，原来世界上真的有“内存申请失败”这种玩意啊；第二，原来内存申请失败之后程序还是可以继续“正常”运行的啊。第一点果然还是因为内存比较大，所以就当白菜一样用了，殊不知白菜也有吃光的时候啊。第二点是我之前一直觉得如果系统连内存这种基本资源都已经给不出来了，那肯定已经是日薄西山气息奄奄了，却忽略了一个参数——申请失败的时候想要申请的那块内存的大小。比如，如果我要申请 1T 的内存，系统给不出来，不能因此直接断定系统已经内存耗尽，就等 panic 了，说不定 1T 虽然给不出，但是 500G 还游刃有余呢。
不过，碰到这个问题，和寒仔商量了下，都觉得大概是因为我当时一次开了好几个程序在跑的缘故吧，其他几个程序虽然没有这么吃内存，但是加起来也许就有点吃不消了。于是我第二天再跑了一遍，其他无关的程序尽量不开起来。顺便还把 tmux 的 history limit 设成了一百万行 =.= 。又过了很久很久，跑去看结果，发现总共有超过 16 万行的 std::bad_alloc 输出。
总之还是 bad_alloc 了。看来还是程序自己的问题啊，可恨的是 C++ 的 exception 没有 stack trace ，就看到一个 bad_alloc ，却不知道具体是在哪个位置抛出来的。因为我和寒仔讨论的结论是，一是程序代码哪里有 bug ，比如用 int （32 位） 来计算 size ，结果给溢出了变成一个负数了，于是在 new 那里被转成 size_t （64 位）的时候，成为了一个超级大超级大的数，自然要 bad_alloc 了；第二种可能性就是代码本身是没有问题的，但是程序占用的内存确实太多了，以至于系统无法提供那么多内存。
寒仔比较倾向于第一种可能，因为我们大致估算了一下总的数据量，由于使用了抽样，并没有取出所有的数据，所以总量是在 100G 以下的。不过我比较倾向于第二种可能，因为相关的代码就那么一点点，两人仔细看了一遍代码，虽然修正了一个可能会造成刚才那种溢出的隐患，但是程序出现 bad_alloc 的时候还没有运行到那里呢，即便是个 bug ，那都只能是另一个 bug 了…… -,-|| 看来看去，也只有 std::vector::insert 的调用那里最可疑了。
因为我印象中 STL 的 vector 在插入元素的时候，容量增长是翻倍的。比如 vector 分配了足够容纳 128 个元素的内存空间，如果插入了 128 个元素之后再插入更多的元素，它就会重新分配一块容纳得下 256 (=128*2) 个元素的内存块。这样会导致分配的内存空间以 2 的指数级别增长，看上去很可怕，实际却比较好用，因为频繁地释放原来的内存块再重新分配内存块的操作实际上是不太好的，这种增长方式可以有效地减少重新分配的次数。不过可能出现的情况就是：虽然实际数据没有那么多，但是占用的内存可能会多近一倍。比如，257 个元素，实际会占用 512 个元素那么多的空间。
为了确认问题到底出在哪里，我又把程序跑了第三遍，这次去掉了 exception 的 catch ，并关闭了 shell 的 core dump 的 ulimit 限制。又过了很久很久，它如期被 abort 了，dump 出来一个 65G 的 core 。在 gdb 里把 core 加载进来，看了一下 backtrace
#0 0x00007f9c72b87165 in *__GI_raise (sig=<value optimized out>) at ../nptl/sysdeps/unix/sysv/linux/raise.c:64
#1 0x00007f9c72b89f70 in *__GI_abort () at abort.c:92
#2 0x00007f9c7341adc5 in __gnu_cxx::__verbose_terminate_handler() () from /usr/lib/libstdc++.so.6
#3 0x00007f9c73419166 in ?? () from /usr/lib/libstdc++.so.6
#4 0x00007f9c73419193 in std::terminate() () from /usr/lib/libstdc++.so.6
#5 0x00007f9c7341928e in __cxa_throw () from /usr/lib/libstdc++.so.6
#6 0x00007f9c7341971d in operator new(unsigned long) () from /usr/lib/libstdc++.so.6
#7 0x000000000041f1aa in __gnu_cxx::new_allocator<float>::allocate (this=0x7fff7c709608, __position=..., __first=0x7f9c60017c34, __last=0xffffffffffffffff)
at /usr/include/c++/4.4/ext/new_allocator.h:89
#8 std::_Vector_base<float, std::allocator<float> >::_M_allocate (this=0x7fff7c709608, __position=..., __first=0x7f9c60017c34, __last=0xffffffffffffffff)
at /usr/include/c++/4.4/bits/stl_vector.h:140
#9 std::vector<float, std::allocator<float> >::_M_range_insert<float*> (this=0x7fff7c709608, __position=..., __first=0x7f9c60017c34,
__last=0xffffffffffffffff) at /usr/include/c++/4.4/bits/vector.tcc:521
#10 0x0000000000428bca in _M_insert_dispatch<float*> (this=0x7fff7c709500, obj=<value optimized out>) at /usr/include/c++/4.4/bits/stl_vector.h:1102
#11 insert<float*> (this=0x7fff7c709500, obj=<value optimized out>) at /usr/include/c++/4.4/bits/stl_vector.h:874
... |
果然是在 vector::insert 那里挂掉了。切换到 vector 所在的那个 frame ，左右看了一下，好多变量都被优化没了，没法看。vector::size() 也被优化成了 inline 函数，没法在 gdb 里调用，结果连 vector 的大小都看不了，真是不方便呀。就调试 STL 来说，gdb 和 Visual Studio 相比还是不够人性化啊。索性把整个 vector 打印一下：
{<std::_Vector_base<float, std::allocator<float> >> = {
_M_impl = {<std::allocator<float>> = {<__gnu_cxx::new_allocator<float>> = {<No data fields>}, <No data fields>}, _M_start = 0x7f7c5fff1010,
_M_finish = 0x7f8c5fff1010, _M_end_of_storage = 0x7f8c5fff1010}}, <No data fields>} |
这里总算可以推算出 vector 的大小了，猜测一下，_M_start 和 _M_finish 应该是使用的内存区段了，算了一下：
(0x7f8c5fff1010 - 0x7f7c5fff1010)/1024/1024/1024 |
刚好等于 64 ，也就是说 vector 已经用了 64G 的内存了。其实从 core 文件的大小应该也大概可以猜到了。也就是说，下一步要翻倍为 128G 的时候挂掉了？虽然我听说 STL 的 vector 的空间分配是按照翻倍的方式，但是这似乎是从某本书上看到的，不排除是比较学院派的代码库里的做法，到底是不是在 industrial 里用的呢，我还不是很清楚呢，索性打开刚才 backtrace 里的 /usr/include/c++/4.4/bits/vector.tcc:521 去看一下，仿佛听到一个声音在喊：欢迎来到一堆模版和下划线组成的世界：
const size_type __len = _M_check_len(__n, "vector::_M_range_insert"); pointer __new_start(this->_M_allocate(__len)); pointer __new_finish(__new_start); |
看来 __len 就是我要找的那个新的 size 了，于是接下来去找 _M_check_len 这个函数，没有 IDE 在一个裸的 editor 里找这种函数的定义还真是一件麻烦的事情（我又不知何故非常抵制 ctags），不过这样也并不是全无好处。在 look around 之后，我发现这个 vector.tcc （扩展名就比较奇怪了）是 export 的模版定义，也就是那个号称几乎没有任何编译器支持（至少在我学 C++ 的那个年代）的 C++ 特性：不把模版定义放在头文件里，而是单独放在另一个地方。总之 vector 的本体是在 stl_vector.h 里面：
size_type _M_check_len(size_type __n, const char* __s) const { if (max_size() - size() < __n) __throw_length_error(__N(__s)); const size_type __len = size() + std::max(size(), __n); return (__len < size() || __len > max_size()) ? max_size() : __len; } |
可以看到 size 确实是（至少）翻一倍的。不过我比较好奇这个 max_size() 是什么，如果大于这个 max_size() 的话，还是会被截断的。于是再找到 max_size() 的定义：
size_type max_size() const { return _M_get_Tp_allocator().max_size(); } |
唔，好吧，调用了某个 allocator 的 max_size() ，那么这个 allocator 是什么？于是去找 _M_get_Tp_allocator 的定义，发现 vector 实际上是继承自一个叫做 _Vector_base 的东西：
template<typename _Tp, typename _Alloc = std::allocator<_Tp> > class vector : protected _Vector_base<_Tp, _Alloc> { // Concept requirements. typedef typename _Alloc::value_type _Alloc_value_type; __glibcxx_class_requires(_Tp, _SGIAssignableConcept) __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept) typedef _Vector_base<_Tp, _Alloc> _Base; typedef typename _Base::_Tp_alloc_type _Tp_alloc_type; public: typedef _Tp value_type; typedef typename _Tp_alloc_type::pointer pointer; typedef typename _Tp_alloc_type::const_pointer const_pointer; typedef typename _Tp_alloc_type::reference reference; typedef typename _Tp_alloc_type::const_reference const_reference; typedef __gnu_cxx::__normal_iterator<pointer, vector> iterator; typedef __gnu_cxx::__normal_iterator<const_pointer, vector> const_iterator; typedef std::reverse_iterator<const_iterator> const_reverse_iterator; typedef std::reverse_iterator<iterator> reverse_iterator; typedef size_t size_type; typedef ptrdiff_t difference_type; typedef _Alloc allocator_type; protected: using _Base::_M_allocate; using _Base::_M_deallocate; using _Base::_M_impl; using _Base::_M_get_Tp_allocator; |
那里的 using _Base::_M_get_Tp_allocator （还第一次见到这样用 using 的），看来这是 _Base 里的一个函数，而 _Base 是 _Vector_base<_Tp, _Alloc> 这么一个东西的 typedef 。于是再去看 _Vector_base ：
template<typename _Tp, typename _Alloc> struct _Vector_base { typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type; struct _Vector_impl : public _Tp_alloc_type { typename _Tp_alloc_type::pointer _M_start; typename _Tp_alloc_type::pointer _M_finish; typename _Tp_alloc_type::pointer _M_end_of_storage; _Vector_impl() : _Tp_alloc_type(), _M_start(0), _M_finish(0), _M_end_of_storage(0) { } _Vector_impl(_Tp_alloc_type const& __a) : _Tp_alloc_type(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0) { } }; public: typedef _Alloc allocator_type; // <omitted snippet>... _Tp_alloc_type& _M_get_Tp_allocator() { return *static_cast<_Tp_alloc_type*>(&this->_M_impl); } const _Tp_alloc_type& _M_get_Tp_allocator() const { return *static_cast<const _Tp_alloc_type*>(&this->_M_impl); } |
可以看到这家伙把 _M_impl 类型转换为一个 _Tp_alloc_type 的东西返回了。_M_impl 是一个 _Vector_impl 类型的成员变量，这个家伙继承自 _Tp_alloc_type 类型，其实就是加了几个 typedef 和构造函数，所以类型转换一下其实就是原来那个东西。
只是我有一点不太明白的地方是，它有一个 allocator_type （也就是模版参数 _Alloc），构造函数也是接受的这个类型，并用它来初始化的 _M_impl ：
_Vector_base() : _M_impl() { } _Vector_base(const allocator_type& __a) : _M_impl(__a) { } _Vector_base(size_t __n, const allocator_type& __a) : _M_impl(__a) { this->_M_impl._M_start = this->_M_allocate(__n); this->_M_impl._M_finish = this->_M_impl._M_start; this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; } |
可是为什么又搞出一个 _Tp_alloc_type 来？根据这个关系，allocator_type 类型的对象似乎是可以转换为 _Tp_alloc_type 类型的对象，或者用来构造一个后者的对象。并且这个类型的定义也比较奇怪：
typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type; |
刚看到的时候差点以为 rebind 不会是 C++11 新加入的某关键字吧？果断 google ，发现不是，不过找到了一个 C++ 模版的 FAQ 里讲何时要用 template 何时要用 typename 的，举了一个例子居然就是类似这里的。明白它不是个关键字之后（C++11 好像引入了好多新功能啊，好想尝试啊！！），再看这个 typedef 就仿佛如纸老虎一般了，其实打开 allocator.h 一看便明白：
template<typename _Tp> class allocator: public __glibcxx_base_allocator<_Tp> { public: typedef size_t size_type; typedef ptrdiff_t difference_type; typedef _Tp* pointer; typedef const _Tp* const_pointer; typedef _Tp& reference; typedef const _Tp& const_reference; typedef _Tp value_type; template<typename _Tp1> struct rebind { typedef allocator<_Tp1> other; }; allocator() throw() { } allocator(const allocator& __a) throw() : __glibcxx_base_allocator<_Tp>(__a) { } template<typename _Tp1> allocator(const allocator<_Tp1>&) throw() { } ~allocator() throw() { } // Inherit everything else. }; |
所谓 rebind 其实是一个模版 trick ，因为 C++ 这该死的类型系统最大的麻烦之处应该属于写出某个类型的名字吧，特别是使用模版编程的时候（每当这个时候就会想起 Haskell 来）。这里这个 rebind 顾名思义，其实就是从 FooBarAllocator （我就不写 template 、typename 什么的了……）得到 FooBarAllocator 这个类型。为什么要这么波折呢？因为有时候 FooBarAllocator 这个类型本身是通过（模版）参数传进来的，你并不事先知道它是什么类型，所以没法写出 FooBarAllocator 来。这倒是一个有趣的 trick ，想起来好像几天前我也遇到一个比较类似的问题，面对一堆 T ，想要拿到一个和 T 相关的类型，但是由于不知道 T 是什么，显得非常无力。
回到刚才的代码，结果这个 _Tp_alloc_type 和 _Alloc 是“差不多”的类型，不过换了一下模版参数。也就是说 vector 实际上要得到 allocator 类型，不过难道构造的时候不就是 allocator 吗？这样的话 _Tp_alloc_type 和 _Alloc 实际上根本就是同一个类型了。亦或者也许可以用 allocator 之类的东西来构造，然后这个东西可以转换或者构造一个 generic 的 allocator 。不过这一堆 allocator 相当复杂，比如对小尺寸对象应该有采用对象池等方式来优化内存使用减少碎片吧：
$ ls /usr/include/c++/4.4/ext/*alloc* /usr/include/c++/4.4/ext/array_allocator.h /usr/include/c++/4.4/ext/bitmap_allocator.h /usr/include/c++/4.4/ext/debug_allocator.h /usr/include/c++/4.4/ext/extptr_allocator.h /usr/include/c++/4.4/ext/malloc_allocator.h /usr/include/c++/4.4/ext/mt_allocator.h /usr/include/c++/4.4/ext/new_allocator.h /usr/include/c++/4.4/ext/pool_allocator.h /usr/include/c++/4.4/ext/throw_allocator.h |
所以那些就先不管了，总之是个 allocator ，我现在要看它的 max_size() 怎么定义的。不过在 allocator.h 里并没有定义，于是找了 ext/ 下的 new_allocator.h 和 malloc_allocator.h 来看，两个差不多的：
size_type max_size() const throw() { return size_t(-1) / sizeof(_Tp); } |
好啦，到这里谜底终于揭晓啦！原来所谓的 max_size ，其实就是 size_t 能够表示的最大值啊，和系统内存什么的一点关系都没有……-,-bb 费了我不少周折，不过想想其实也是正常的。那么，所以说问题还是出在分配内存的时候 double 了一下 size 咯？64G 变成 128G 的时候挂了？按理系统的内存是够的，其他的一些服务占去了几十 G，也还有不少呢，不过 MongoDB 这个内存大户估计不好惹，但是按理说 MongoDB 应该是使用内存映射，内存不够的时候操作系统应该可以自动帮他释放一些的。那问题出在哪里呢？
后来寒仔突然顿悟，说，因为有个时刻 64G 和 128G 是同时存在的啊！果然如此！看 new_allocator 里的代码并没有用特殊的内存操作，只是普通的 new 出一块新的空间，把内存复制过去，然后再释放原来的空间。这样子一来，192G 的内存的话，好像确实有些吃不消了，因为系统还在跑一些其他的服务，合计起来占去的内存也挺多，128G 应该没有问题，但是 192G 就有问题了。
既然是在 size double 的问题上，倒是好解决的——因为实际内存占用并不会超过物理内存，STL 提供了一个函数叫做 reserve ，告诉它需要预留多少空间，如果这个 size 估算得好的话，就不会出现刚才那样的问题了。编译、运行、等待………………耶，果然 OK 啦！
唔，到这里为止，发现我果然大量篇幅都在跑题啊，也许是因为 N 年没有用 C++ 了，突然又回头开始用，心里头比较激动的缘故吧！ 😀 顺便，C++11 的标准出来了，有点小热血沸腾呢！其实应该大部分的标准在 draft 的时候 gcc 就已经支持了吧，可是 Debian stable 上的 gcc 版本真的好老好老啊。还有 Clang 也想尝试一下的，因为听说它的错误输出可读性非常好，前几日在重构一坨依赖比较多的模版代码的时候，同数万行（也许小夸张了下 :p ，不过那满屏满屏的阵势，你懂的~） gcc 的模版编译错误血拼了一个下午，深感恶心啊，这些年来似乎都没啥改进呢，果然是块难啃的肉啊。
其实虚存是实际内存的2~3倍甚至10倍以上都是可以的, 只要不去用这些内存, 就不会有物理内存被分配. 内核有个参数控制分配的虚存可以是实际内存的多少倍
/proc/sys/vm/overcommit_memory
/proc/sys/vm/overcommit_ratio
按照你描述的这个情况, 只需要改一下这个参数就应该能解决问题.
一旦前面的64G内存被拷贝到新申请到的128G内存中之后, 这64G内存就会被释放, 峰值内存使用依然只有128G, 不会OOM的.
这个文件可以看到实际可申请的内存量, 有可能远大于物理内存.
$ cat /proc/meminfo | grep Commit
CommitLimit: 606540 kB
Committed_AS: 240008 kB
唔，说得有道理！这样子确实不会超过 128G 的使用量。
看了下 overcommit_ratio 是 50 ，swap 为零的话，那应该能申请的内存大致上限就是一半的内存，减去所谓的给 root 保留的一些内存之类的，在 /proc/meminfo 看到的 CommitLimit 大约是 126G 。
不过因为 /proc/sys/vm/overcommit_memory 是 0 ，所以实际是没有使用这个 commit_limit 的对吧？系统是根据当前内存使用量和可回收的情况来动态计算可申请的内存数量的，所以在 192G 的时候超标了。
你说的解决办法是不是把 overcommit_memory 设置为 2 (strict overcommit) 然后再把 overcommit_ratio 调大？
overcommit 只影响 malloc 后没有实际使用的（全为 0）的情况，此处改了也没用…
-.- 更正：删去”（全为 0）”
对啊，原本就是 malloc 了还没有使用，malloc 太多了，直接被操作系统 refuse 了，所以 bad_alloc ，实际使用是没有那么多的，等到用到那么多的时候原来的 64G 已经释放掉了，所有又是够用的了啊。
可能需要用到 C++ 新功能的 std::move ?
std::move 不能解决吧？move 只是改下指针，现在的问题是要得到一块更大的内存块。当然如果 STL 能够和非常底层的页面映射什么的打交道的话也许能够很高效地做到，或者是有像 realloc 之类的 API （但是其实也是不能保证原地扩大的吧）应该会好弄一些。
如果是需要把一个 vector map 到另一个，然后原先的就不用了的话，可以处理完一个 item 后就销毁掉那个 item -.-
不是把一个 map 到另一个，而是 vector 自己在 size grow 的时候出问题了啊。
现在终于应该看懂了 -.-b
在 push_back 一个新的 item 的时候原先的 64G vector 不够用了，于是在变成 128G 的过程中，需要申请 192G 的内存… 在这个过程中拷贝构造全部完成之后才会删除旧的 item，所以至少会实际用到 128G 内存，如果事先指定比如 65G 的话就好许多。
overcommit_memory 设为 2 不解决问题，因为 overcommit_ratio 不能设成大于物理内存。可以试试设成 1 无限 overcommit。
altdevblogaday.com/2011/05/28/implementing-a-true-realloc-in-cpp/ 提到了用 C 的 realloc。但 realloc 自己也不能保证不是重新分配一块内存，还是有隐患。
之后再遇到类似的情况，我觉得最好的办法还是找老板买新内存 -.-
realloc 确实不能保证一定不是重新分配。
overcommit_ratio 不能超过物理内存？感觉你理解错了吧？我觉得 overcommit 的 “over” 就是指超过物理内存的意思，就是说你可以申请很多很多，超过物理内存都没有关系，只要你任意时刻的实际使用总量不超过物理内存就没关系了。和我这里碰到的问题刚好是完全吻合的啊。
很久之前我经常遇到 OOM killer 的时候看过这些设置的说明，写上一条评论的时候特意再看了一遍内核文档，现在又看了一遍，果然之前都理解错了… -.-
momo ，我是刚刚才知道还有这样的参数。不过，如果默认情况下 overcommit_memory 是 0 的话，基本上就确实是不能分配超过可用内存数量的空间了。
第一篇看得懂的kid的blog，甚感欣慰…学到不少啊~
寒仔V587！
经常把16GB物理内存加16GB swap用光而弹出bad_alloc的人飘过。
当时好像是因为另外一个版本的聚类程序太吃内存, 然后总是触发系统的 OOM Killer 把进程乱杀一通, 然后貌似改过 overcommit 的设置…
呃……那现在的配置是啥样的？ @@
海量数据的聚类就是麻烦，不知道最近有什么好算了了不
@水寒
September 3rd, 2011 at 12:58 pm · Reply
当时好像是因为另外一个版本的聚类程序太吃内存, 然后总是触发系统的 OOM Killer 把进程乱杀一通, 然后貌似改过 overcommit 的设置…
今天也遇到了同样的问题。程序中存在内存泄露，导致程序不能够申请到足够的内存而产生崩溃。
看了这些大师的评论之后，理解更深刻了