Track’em Down

刘未鹏

C++的罗浮宫(http://blog.csdn.net/pongba)

P.S. 很多朋友都抱怨说STL出问题的时候debug很难，编译期错误算是轻的，大不了一串串令人头晕的出错信息，至少还能双击定位到错误行。而神秘的运行期崩溃才是真正令人头大的问题。下面就是一个比较典型的、五脏俱全的运行期崩溃事件，从几行简简单单的代码，似乎根本不可能崩溃，一直到最后揪出隐藏在背后的机制。其中的思维分析过程是怎样的呢？希望对一些朋友有点帮助。标题起作”Track’em Down”一方面是暗指整个分析跟踪的过程，而是最后所揭露出的机制的确是个tracking机制:-)

很久没写blog了，一来是诸事缠身，二来也是实在不像以前那么有热情坐下来好好写篇技术文章了。很多时候只是做个旁观者，四处潜水而已。昨天又跟老婆闹了矛盾，心里郁闷，于是给自己一个理由四处乱逛，跑到许久未去的cpper（http://www.cpper.com/c/ ）上，cpper还是一如既往的冷清，看来一个论坛要想火起来光靠技术是不行的，cpper（前身为allaboutprogram）圈子里有一批技术很牛的朋友，也许是太牛了，这两年都开始一个个牛得没影儿了。二来cpper不像CSDN这样有一个门户，主页上有乱七八糟的好玩信息，新闻，八卦，等等不一而足。国内C++社群的大部分朋友想必是不知道cpper的，尤其是初学者。实在是个不小的遗憾…等等…似乎扯远了，刚才说到逛到cpper上，看到tomato的一个帖子，提到一段行为怪异的代码，行为是崩溃，而且是在l析构的时候崩溃：

#include <list>

int main(int argc, char* argv[])
{

  std::list<int> l;

  std::list<int>::iterator* it1 = new std::list<int>::iterator(l.begin());

  memset(it1, 1, sizeof(std::list<int>::iterator));

  l.push_back(1);

  l.begin();
return 0;
}

以上是原贴里的代码，我就不简化了。大伙看着办吧，呵呵。

乍看上去这段代码似乎不应该有什么问题（至少不会崩溃）。最可疑的当然是那行memset，但memset只是把it1指向的一个new出来的iterator给corrupt掉了，况且这个it1也没被delete，所以也就不会因析构而崩溃了（虽然有内存泄漏，但tomato说的是崩溃），另外it1跟l看上去是井水不犯河水。所以怎么看不像有问题的样子。

以上是眼睁睁瞪着代码看出来的结果，然而当我把代码塞到IDE里面，编译运行之后却发现果然如tomato所说，在list析构时程序崩溃了（很凑巧我跟tomato用的IDE都是VC8，这是一个关键条件）。对于这类问题，一般我是先黑箱再白箱。这么短的程序，要出问题肯定出在memset那行，逻辑上可以大致这么说：“由于memset把it1的内存corrupt掉了，结果导致l在析构的时候崩溃。”听到自己下这么个结论我都觉得有点哭笑不得，这压根儿风马牛不相及嘛，it1被corrupt与l析构崩溃有屁关系？！it1只不过是个指向l的迭代器，说穿了就是裹着个指向l中的某个node的指针而已，它的死活怎么会影响到l的析构呢？

但福尔摩斯大致说过，去掉那些绝对不可能的，剩下的就是可能。这里这是唯一的可能，只不过问题是，这个逻辑还不够细致，需要丰满起来。进一步，要想使得l在析构的时候崩溃，这个memset肯定以某种方式影响到了l。又因为memset直接影响的是it1，那么必然是it1和l的某种联系导致memset间接对l产生了影响。于是再来看，it1和l有什么联系呢？得！这下看出来了，it1在构造的时候是通过l.begin()拷贝构造的，哈!问题似乎有点眉目了，但到此我还是想不通，根据常识，iterator的拷贝构造会产生出一个与源iterator不相干的副本，对这个副本干什么事怎么会影响到源呢？更别提影响到源iterator所指向的容器了。开玩笑！甭管他，既然已经肯定下来这是唯一的可能，那么推论只能是：背后还隐藏着什么不为人之的东西。于是进一步注释掉“(l.begin())”，使it1变成缺省构造的迭代器，果然，不再崩溃了。于是，现在可以肯定作出的结论是：“… it1 = new std::list<int>::iterator(l.begin());这行代码使得it1所指向的迭代器与l发生了某些关系（当然，不是it1指向l这样的白痴关系）。很显然，这个关系的建立点不可能是在l.begin()，因为这里还没有涉及到it1，所以唯一的可能就是，这个关系是在std::list<int>::iterator的拷贝构造函数阶段发生的。这次拷贝构造以l.begin()为参数，而l.begin()推测起来应当带了l的信息，因而it1就利用这个机会与l建立起了“某种关系”。OK，到目前为止这个“某种关系”只是一个模糊的概念，我们并不明确知道究竟是什么关系，竟然导致list析构会失败。看来是时候进入白箱了，F5，break，看断在什么地方了，说实话P.J Plauger写的STL代码至少在外观上不像SGI的那么亲近人，nevermind，我看到了我想看到的信息——一个名为_HAS_ITERATOR_DEBUGGING的宏，哈，想起来了，这一版的STL是带有iterator debugging功能的，所以当然能够发现iterator被corrupt掉的情况。疑问来了，怎么发现的呢？直接的答案是，肯定有某种追踪机制，而且根据前面的推理，由于是l在析构的时候发生的崩溃（it1并不析构，因为并没有对它进行delete），所以l在析构的时候必然能以某种方式访问到it1并发现它被corrupt掉的事实，再推广之，l肯定能够访问到所有指向它的迭代器（这才叫iterator debugging嘛），而it1在构建的时候的确是拷贝构造l.begin()来的，也就是说指向l，所以l必然应当知道（跟踪）它（it1）的存在，又因为接下来的memset是个相当low level/native的操作，所以l对此肯定不知情，还以为it1一直好端端的指着它的begin()处呢，最后当它一个个察访指向它内部的迭代器，当查访到it1时就发现it1被corrupt掉了，于是崩溃。呼～一切到这里似乎都串起来了。剩下的就是去发现list<int>::iterator的拷贝构造函数究竟在背后捣了什么鬼才使得l最终能够访问到it1的，在开始之前我就设想一个场景：肯定是l里面有一个链表，把所有指向它内部的迭代器串起来了，这样它就能够逐一检查这些迭代器，看看比如说它们是否越界之类的。而it1在拷贝构造的时候由于是以l.begin()为参数的，l.begin()肯定带有l的信息，说白了，指向l的指针，或l的引用，于是it1的拷贝构造函数就可以把自身链入l内部的链表中去。想到这里似乎情况十分明朗了，剩下的就是跟踪进去验证一下了…但是等一下…刚才说到，程序的现象是…崩溃！如果是在l对它的迭代器check的时候发现错误，大脑没毛病的库设计者肯定会抛出一个异常吧，不会是崩溃的症状…what the hell。反正我已经知道问题的核心在list<int>::iterator的拷贝构造函数那里，那是唯一同时拥有it1与l信息的地方。于是F11到list<int>::iterator的拷贝构造处，即“… it1 = new std::list<int>::iterator(l.begin());”这行代码处，郁闷的是，调试器在这里一跳而过，似乎它拥有的是一个trivial的拷贝构造函数（从后来的结果来看这似乎是VC2005的一个小问题），而且我”go to disassembly”居然也就看到聊聊几行代码，除了一个对list<int>::begin()的调用之外就没有其它调用了，傻眼了，似乎真的是个trivial的copy ctor？如果真是这样的话，就不可能在这里建立起it1跟l之间的联系了，因为trivial的copy constructing只会是把成员按位复制一下，没有其它代码，不涉及函数调用，怎么可能会有机会干其它事情呢？而后面又没有任何地方同时涉及it1跟l的，那又怎么会最终导致l析构崩溃呢？简单的推理，反推上去，既然l最终析构崩溃了，那么这个逻辑的某一环肯定错了，最可能的就是，这并非trivial copy ctor，调试器欺骗了我的眼睛，背后肯定调用了某个拷贝构造函数，然后干了些勾当。于是静态跟踪派上了用场，幸好VS2005的intelli-sense非常强大，两次“go to definition”就置身于了list<int>::iterator的定义里面，刚才不是说关键就在list<int>::iterator的拷贝构造函数里面吗？于是浏览一下list<int>::iterator的定义，VC带的STL的代码真难看啊，好在这个类比较短，很遗憾，没有拷贝构造函数，只有构造函数，不过碰巧，在其中一个由_HAS_ITERATOR_DEBUGGING条件控制的构造函数里面发现了一行宝贵的代码：this->_Adopt(_Plist);，如果没猜错，这肯定是把这个迭代器自身链到它所指向的容器内的跟踪链表中去的。_Plist（该构造函数的第二个参数）是什么？跟踪到l.begin()调用里面就会发现，喂给list<int>::iterator的构造函数的第二个参数（也就是_Plist）是this，呵呵，看来this->_Adopt(_Plist)实际上就是把this（迭代器）“收养（adopt）”给_Plist啊。没猜错，果然是这样的跟踪机制。那么，照理说list<int>::iterator的拷贝构造函数也应该有相应的动作才对啊，不然拷贝构造出的新的iterator就会没人“收养”了（而我们的跟踪机制是应当跟踪到每个“在世”的iterator的，否则就没意义了）。刚才提到，list<int>::iterator本身没有拷贝构造函数，那么只有一种可能，要么其成员具有non-trivial的拷贝构造函数，要么在基类里面。实际上list<int>::iterator只有一个成员，一如我们意料之中的，指向list的node的ptr。所以秘密肯定在基类中，顺着基类一路找下去，_Const_iterator->_Bidit->_Iterator_base。说实话到_Bidit差点放弃，因为我以为_Bidit里面肯定就是一些typedef，就像unary_function那样。事实却不是这样，下面还隐藏了一层_Iterator_base，而这个_Iterator_base就是一切秘密所在了。它是有拷贝构造函数的，代码我就不列了，如果你跟踪到这里，真相也就大白了，简单的来说，它根据源iterator找到其所指的容器，然后取出该容器里面的用于跟踪迭代器的链表头指针，然后把自身（this）链到这个链表里面去。由于一个iterator诞生的方式一共就两种，一种是从某个容器诞生，这时是调用的它的一般构造函数，容器会把自身的指针当作参数传递给这个iterator，后者通过这个容器指针来将其自身链接到容器的跟踪链表中。第二个诞生方式就是这里说的，拷贝构造，拷贝构造时会将其自身链到源iterator所指向的容器内的跟踪链表中去。反正就是，一切现有的iterator都会恰当被它所指的容器跟踪着。

那么是时候揭穿谜底了吧，为什么memset会闯下这么大的祸？因为一个iterator要被链到链表里面，它肯定有next指针，这样才能链成一个链表嘛。而memset粗暴地将这个next指针给重置了（事实上它把it1指向的迭代器整个给memset了，当然包括里面的next指针），这里，next指针被重置为了1（如果memset成0就不会崩溃了，原因很简单，想想看），显然，这就指向了一块无意义的内存。于是，l在析构的时候，试图遍历并check它所跟踪的iterator链表，随着它通过next指针一节节跳转，当到了我们的it1的时候，由于其next指针的值是1，所以试图再跳(next)的时候就非法内存访问了！崩溃！所以，这里的问题并不在于最后的check失败了，而是在于迭代器链表被corrupt掉了，才导致的崩溃。这就解除了前面的关于未发生异常的疑惑。事情到此就大致结束了。

当然，这里还隐藏了很多的细节。例如最后l析构时并不是要去“check”每个迭代器。另外这个iterator tracking的机制还是很有代表性的，boost::signal里面就用了如出一辙的手法，这个手法充分显示出了C++的强大和灵活。原来看上去毫不起眼的构造函数在背后还能做那么多工作。这里就不方方面面总结这一技术了，一是困了，二是这不是这篇blog的初衷，写这篇blog一是为了平静一下郁闷的心情，二是为了显示一个从现象开始分析推理问题，最终接近答案的过程。程序员的大部分时间是在debug，这篇blog其实介绍的就相当于一个debug的思维过程，或许它并不是最好的，但希望你能够在其中发现一些有用的东西。至于我，写累了，看两集friends，睡觉，希望明天老婆能给个好脸色=_=~

P.S. 看上去啰啰嗦嗦一大通，实际上在脑子里转来转去是一瞬间的工夫，加上跟踪（静态/动态）也就十来分钟，而写这篇blog倒花了我四十多分钟（这也是越来越不写blog的原因吧），人类自然语言的表达力某些时候是十分啰唆冗余的…ZZZZzzzz