云风的 BLOG: 正确的迭代处理对象

昨天在写一个 AOI 模块，设计时又碰到一个对象迭代的老问题，必须谨慎对待，文以记之。

缘起：

当对象 A 进入 B 的 AOI 区域时，会触发一个 Enter 事件。这个事件处理是以回调函数的形式完成，如果回调函数中再次调用 AOI 模块，产生一次间接递归，就有可能破坏 AOI 模块内部的某些迭代过程。

更要命的是，如果回调函数内删除了一些相关对象，很有可能引起对已释放对象的访问错误。

这类问题在各种对象管理的程序框架中经常出现。除了上面提到的 AOI 模块，在 GUI 模块设计中也极其常见。下面谈谈我的解决方案吧。

首先，由于回调函数内部逻辑的不可预知性，我们一定要把实际的处理放在每个 API 实现的末尾。一旦真正的处理在中间，因为间接递归的可能性，极有可能保存在模块内部的上下文信息被其破坏。

正确的做法是在模块环境中创建一个唯一消息处理队列，把可能引发回调的消息都暂入到队列。由于队列只有 enter 和 leave 两个方法可以改变内部状态，迭代处理队列本身是不会出问题的。

另一个必须考虑的对象的释放时机。当我们用 C 或 C++ 这类没有 gc 机制的语言实现的时候，它是个相当头痛的问题。

因为，任何一个消息处理的回调函数都可能删除某些对象。而这些对象的指针极有可能放在消息队列中。不要跟我说在消息队列中放对象的智能指针，然后每个用到该对象的地方都使用智能指针访问。那样我会疯掉的，尤其是需要把回调函数这样的接口暴露给最终用户时，我可不希望在接口上暴露一个难看的智能指针类。即使拐弯没角的把接口问题解决掉，额外的性能付出也让人心里不大舒服。

解决方法有两个：

消息里不记对象的指针，而用一个进程生命期唯一 id 标识。再用一张 hash 表做映射。对象删除后，id 不再找的到对应的对象。这个方案在上次的一篇文章的留言中提过。
用一个间接指针。对象删除后把间接指针置一个标记。再次调用时就可以知道对象被删除了。间接指针本身占用的空间从额外的备用池里分配。定期回收，和真正的删除垃圾对象。

个人比较推荐性价比更高的第 2 方案。接下来展开谈一下细节。

所谓定期回收，应当隐藏起来让用户不可见。我们可以把回收过程放在新对象创建的时候，因为这个时候恰巧需要新的内存资源，是释放旧资源的最好时机。由于对象创建也可能发生在消息处理的过程中，我们不能在消息处理期间做这个工作。所以垃圾收集的时候必须检查消息队列为空，才可以开始。

回收分两个步骤：

一是删除垃圾对象，这个去检查间接指针中的删除标记位就可以了。

二是删除间接指针本身。当消息队列为空时，完全可以把所有间接指针整个一起拿掉。

以上问题考虑周全后，基本上万无一失了。:D

Comments

"对象池加句柄看起来舒服写。" 呵呵，概念而已，这种深入理解，娓娓道来的文章看起来很爽

Posted by: 尉迟方 | (28) September 25, 2007 04:17 PM

对象池加句柄看起来舒服写。

Posted by: Zwinger | (27) September 21, 2007 12:52 PM

看来高手所见略同啊,只不过他们岁数大了些,早些用了而已

Posted by: zetorchen | (26) September 21, 2007 11:34 AM

方案2这个做法和Unreal里的gc做法一模一样

Posted by: zetorchen | (25) September 21, 2007 11:32 AM

我也想问同样的问题

Posted by: nothanks | (24) September 21, 2007 11:21 AM

请问什么叫做 AOI ?

Posted by: david | (23) September 21, 2007 10:52 AM

搞错，应该是创建计数

Posted by: dfk | (22) September 20, 2007 04:16 PM

这个问题我感觉和另外一个问题很像：在一个vector的循环内，删除对象 - -! 以前有过一个实现，就是对象不释放，而是放回等待队列，这样就可以直接保存指针，然后如果重用，更新一个引用计数来区别前后对象

Posted by: dfk | (21) September 20, 2007 04:15 PM

好吧，我承认我对你的问题不太了解，理解得不对。我错了。

Posted by: Atry | (20) September 20, 2007 11:02 AM

你真的明白问题是什么吗？ AOI 模块里，当 A 进入 B 的 AOI 区域，会触发 enter(A,B) 这件事情。 on enter 这个 callback 事先知道 A 和　B 对象？你叫提供 callback 的用户自己去绑定？队列是模块具体实现的一部分。如果找到别的方案，甚至可以不用队列而换一种数据结构和算法来做。你认为用这个模块的人一定要用事件驱动来实现业务？程序一定要用一个主循环来支撑整个框架？他要做的可能仅仅只是加载好数据，测试地图上的某个点会不会被 NPC 看到而已。

Posted by: Cloud | (19) September 20, 2007 12:49 AM

我们的分歧不在于用不用队列，而在于怎么用。你的观点是，“把可能引发回调的消息都暂入到队列。” 我的观点是，内部逻辑不涉及队列，而是直接把所有的回调函数扔到队列上去。和你的方案相比，我这样做的优势在于，回调函数的参数很简单，不会持有对象。而如果用户自己一定要绑上某个对象的指针，那应该他自己负责。你一直纠缠的问题，要把队列独立出来还是放在里面，这根本不重要。我倾向于独立出来，但是如果需要把队列整合到里面去也很容易。顺便说一下，我实际工作中，那个回调函数是用虚函数，因为我的同事更习惯虚函数。而且，事件队列也真的是不透明的放在模块里面的。结果就是，我写的几个东西里面都有各自的事件队列的实例。我觉得这并不好，还不如让用户自己传进来一个他自己维护的事件队列。

Posted by: Atry | (18) September 20, 2007 12:30 AM

用消息队列是用来解决重入的问题。就是我正文中写的那样。至于消息队列如何实现跟这个问题无关。你贴的代码无助于解决对象生命期管理的问题。隐藏消息队列的实现可以在内部用专有实现主动解决这个问题，方法我正文中写了。由于，是专有实现，用户并不知道队列的存在，也不能主动向队列中放任何东西，callback 函数从参数拿到的对象由模块内部保证其有效性。暴露出来后，用户可以在上面做任何事情，队列中可以放任何东西。这种自由度就遗留了风险。模块本身不能再帮你保证相关资源的有效，转嫁到 boost.function 这样的复杂对象自身去保证。如果你用引用记数来保证，那么就需要写 callback function 的人了解如何保持正确计数的细节。我没有生气，只是觉得好笑。我谈的是设计问题，你非要用实现方式来驳斥。至于在模块对外接口上暴露 boost.function 这样的复杂对象类型做参数。我只能说，天呐，这做出来的东西还让人用吗？

Posted by: Cloud | (17) September 19, 2007 11:52 PM

其实我帖代码的原因是看到你这句话：用户可以在任何时候自己去处理队列里面的事件。" 这就包括了用户可以在回调函数中处理队列里的事件。在这种情况下，队列中事件处理时用到的对象的生命期是难以控制的。你可以在文档中注明不要这么干，但不能从接口设计上阻止这种做法。这就是设计问题。你这段话我觉得不知所云，所以只好帖代码。

Posted by: Atry | (16) September 19, 2007 11:17 PM

我是把你的需求给改了，我改变你的需求的原因是你的需求太容易解决。只要保证事件都是简单的，单向的，一层简单的包装就可以满足需求。

Posted by: Atry | (15) September 19, 2007 11:08 PM

哈哈，看来把云风惹怒了。挑起代码毛病来了。老实说吧，那个接口就是 Boost.Asio 的简化版。Boost.Asio 里面的回调函数是个可变的模板参数，他内部用了一个类似于 Boost.Function 的东西把函数对象复制出来。但是在这里帖模版怕被鄙视，所以自己改成了typedef，反正是什么类型不重要。至于隐藏的问题其实不是问题，想要隐藏很容易，只要把队列整合进去，并且在每一个公开方法结尾的地方检查一下就行了。至于队列分离出来的原因是因为，对用户来说，他可能需要使用多个模块，但是可以把这些模块的事件放到同一个队列。有可能用户的主循环需要挂在这个队列上。

Posted by: Atry | (14) September 19, 2007 11:06 PM

你最终把需求给变了。我们是先有需求再做实现的不是？需求就是，AOI 模块里的类似 move 这样的 api 调用完毕后，该完成的 callback 动作就做完了。你想异步应该在 callback 里再发消息出去。强迫用户选择异步的方式，就好象 Windows 只提供 PostMessage 不给你用 SendMessage 一样。看过你下面列的代码，让我觉得争论毫无意义。因为你列出的部分是最基本形式，除了同样用一个消息队列解决上述提到的如何避免在容器遍历时避免重入问题外，没有展现额外的东西。至于这个消息队列用 C 实现还是　C++ 或是 Pyhon Java ，不是需要争论的东西。第二个问题，如何确保在消息处理时，被处理对象生命期的正确性，跟这段代码就没有关系了。 btw, 下面已给出的接口设计的显得缺乏实作经验。一般情况下，若选择用 C++ 方式提供 callback, 应该提供一个 callback 的 interface, 里面供有 execute 方法（这样至少 execute 时可能拿到一个 this 指针）；如果想提供一个 C 函数指针的话，通常至少需要一个函数指针和一个 void * 的userdata。不然会让模块的使用者很难使用。 queue 这个 class 的分离设计也是一大败笔，它会导致不必要的模块间强耦合。这里就不展开说了。让用户更多选择是指提供一个怎么用都不会出错的简单语义的接口，而不是一大堆将内部控制逻辑暴露给用户的多项选择。这样的结果往往就是让用户写出更烂的代码。看看 Windows API 的糟糕设计就知道了。 ps. 我们这里没有多个团队，只有一个。另外也的确在研究 ErLang, 但这跟这里的话题没有联系。

Posted by: Cloud | (13) September 19, 2007 10:14 PM

其实只要模块设计的时候方法和回调都是单向无返回值的。只须简单增加一个事件队列，一层包装就可以避免你说的重入问题。甚至，如果希望这个模块在另一个线程运行，也只需要增加一个正向调用方法的队列。就可以保证无锁的线程安全。至于什么封装，既然可以把这个队列明确的暴露给用户，想要隐藏起来就更容易。只不过，不隐藏队列有一个好处，就是把这个选择权交给了用户。听说你们还有一个团队在研究 erlang ，应该让那个团队跟你们讲讲课。

Posted by: Atry | (12) September 19, 2007 09:42 PM

// 这个类代表一个事件队列 class event_queue { public: void run_events(); }; // 某个功能模块，可能会被单件使用 class foo1 { public: typedef ... callback_type1; typedef ... callback_type2; foo(io_service*); void op1(..., ..., callback_type1 callback); void op2(..., ..., callback_type1 callback); }; // 另一个功能模块 class foo2 { public: typedef ... callback_type1; typedef ... callback_type2; foo(io_service*); void op1(..., ..., callback_type1 callback); void op2(..., ..., callback_type1 callback); }; 用户自己持有一个事件队列，在构造模块的时候把这个队列传进去。以后所有的回调函数都会被发到队列上，需要用户自己调 run_events 这些回调函数才会运行。

Posted by: Atry | (11) September 19, 2007 09:34 PM

"用户可以在任何时候自己去处理队列里面的事件。" 这就包括了用户可以在回调函数中处理队列里的事件。在这种情况下，队列中事件处理时用到的对象的生命期是难以控制的。你可以在文档中注明不要这么干，但不能从接口设计上阻止这种做法。这就是设计问题。把队列本身暴露给用户违背了设计模块的原则：隐藏内部信息。作为应用模块程序员，凭什么需要知道你的实现细节才能正确的让程序正确工作起来？ AOI 的模块对外的接口本身不应该告诉用户：我有一个消息队列，你在合适的时候去处理；我有垃圾回收机制，但是请主动调用收集函数，等等。用户的需求是：我将对象移动了位置，事前注册的相关函数立刻被触发了。移动方法完成后，相应的回调动作就已经完成。无论怎么实现回调函数都不会引起模块内的错误。

Posted by: Cloud | (10) September 19, 2007 07:03 PM

你用的队列和我想象的有一些差异。你的队列涉及模块内部逻辑处理，这是不对的。一个模块应该假设所有的外部调用就已经是同步的，并且在这些外部调用里面不会产生回调事件。所有的回调事件都发到一个队列中去。用户可以在任何时候自己去处理队列里面的事件。

Posted by: Atry | (9) September 19, 2007 04:55 PM

正确的做法是在模块环境中创建一个唯一消息处理队列，把可能引发回调的消息都暂入到队列。刚才这句话看走眼了，我以为你是把回调函数放到队列里面，因为我通常就是这么做的。我的做法比你的做法好。

Posted by: Atry | (8) September 19, 2007 04:39 PM

你真的知道这里说的问题是什么吗？问题如何产生如何被解决的？

Posted by: Cloud | (7) September 19, 2007 03:09 PM

还有，让消息队列持有对象就是很糟糕的，消息队列里面可以包含的数据只应该是最简单的结构。这样的话，这个结构的生命周期用人肉智能指针控制就足够了。先把复杂的对象放到消息队列里面，碰到问题了再用丑陋的办法搞出什么 id 。这是把顺序搞反了。

Posted by: Atry | (6) September 19, 2007 01:21 PM

引用计数并不要求要把加减引用计数放在基类，那个计数可以创建以后再绑上去，就像 boost::shared_ptr 做的那样。你这种做法把垃圾收集和消息队列的代码绑在一起，才是真正的坏味道。而且也是重复发明轮子。

Posted by: Atry | (5) September 19, 2007 01:14 PM

在这个具体问题上，引用计数是最丑陋和低效的解决方法。他强迫用户在实现对象的时候必须留出引用记数的位置，并把加减引用的方法放在基类。而且强制要求用户在传递对象的时候加减引用。

Posted by: Cloud | (4) September 19, 2007 01:05 PM

直接处理消息的确会有不少问题。把消息统一起来放在一块儿处理是个好办法

Posted by: nothanks | (3) September 19, 2007 01:00 PM

简化版的个人专用gc,呵呵.

Posted by: Anonymous | (2) September 19, 2007 12:28 PM

把回调函数暴露给用户并不等于要把智能指针暴露给用户。对于已经引入 boost 的 C++ 来说，用引用计数是最直观的解决办法。

Posted by: Atry | (1) September 19, 2007 12:02 PM

云风的 BLOG

思绪来得快去得也快，偶尔会在这里停留

正确的迭代处理对象

Comments

Post a comment