View Issue Details
|ID||Project||Category||View Status||Date Submitted||Last Update|
|0005212||The Dark Mod||Coding||public||12.04.2020 03:49||15.04.2020 06:05|
|Product Version||TDM 2.08|
|Target Version||TDM 2.08||Fixed in Version||TDM 2.09|
|Summary||0005212: dmap: crash when merging leaf nodes in AAS|
|Description||During idAASBuild::MergeLeafNodes, sometimes references to deleted nodes are created.|
This usually results in a crash in nearby code without any indication of what happened.
|Steps To Reproduce||Dmap some complex map, and there is a small chance of this happening.|
|Additional Information||Reported on forums here:|
Although the problem itself is quite well-known and was happening long before 2.08 (I guess since original Doom 3).
|Tags||No tags attached.|
The AAS build tool maintains a BSP tree as usual. The leaves of the tree represent subspaces (convex polyhedrons) of the whole space. Polygons between leaves are created and maintained as "portals".
Now the idAASBuild::MergeLeafNodes function attempts to merge some subspaces into larger ones. MergeLeafNodes_r iterates over all BSP leaves and calls MergeWithAdjacentLeafNodes, which in turn merges the leaf with all leaves adjacent by portals, until no more such merges are doable. There is some complicated logic of what can be merged and what not. idBrushBSP::TryMergeLeafNodes is called to actually perform a merge.
Let's denote the currently inspected leaf as A, and the adjacent leaf as B.
When merge is possible, the TryMergeLeafNodes function updates the leaf node A and deletes the leaf node B. All portals and portal-leaf references are updated correctly right here. The problem is how to update the references to leaf B in the internal BSP nodes. In order to achieve it, UpdateTreeAfterMerge_r is called. It takes bounding box of the merged node, increases it by 2 lengths units, and traverse all BSP nodes which intersect this box. If everything is right, then all references to leaf B must be seen during such traversal. They are replaced, and merging continues.
While this works most of the times, in some rare cases the code misses some references. I don't know how it happens: probably portal winding calculation goes wrong. Anyway, there is some reference to deleted leaf in internal node which does not intersect the enlarged box. It is not updated, and remains in the tree: a reference to deleted node. During future traversals things go terribly wrong with this node, resulting in various crashes like double free, access violation, heap corruption, whatever else.
Initially I thought about using backlinks from leaves to internal nodes. Actually, there is already member idBrushBSPNode::parent which serves exactly as such backlink.
The problem is that this member only stores one parent. But after leaves are merged, they can have arbitrary number of parent nodes, which is not captures in this member. And such fully merged nodes can still be merged into something else later, so the parent member does not solve the problem. Turning it into a list does not sound like a good idea...
Eventually, I decided to delay deleting of the nodes. After leaf node B is merged into something, it is turned into a "zombie" node. It is not a real node, but it still occupies its memory region and saves its address, so all references to it are valid yet. In such a zombie, I save a link to the node it was merged into (in the parent member). So when traversal gets into a zombie, it can go through the chain of zombie nodes and find the larger node that should be referenced there instead of the zombie.
Immediately following idAASBuild::MergeLeafNodes_r call, the function idBrushBSP::PruneMergedTree_r is called to simplify the tree: remove internal nodes which point to same merged leaf on both sides. I check for zombie nodes here, and replace any links to zombies to links to corresponding merged nodes. After full BSP tree traversal, all references to zombies are replaced.
Finally, all the zombie nodes are deallocated in idAASBuild::MergeLeafNodes.
I have checked that .aas files are exactly equal before and after my change on the Saint Lucia map. So I'm pretty sure the change does not affect the result, unless there were some problematic references.
|Adding 0004233 and 0005037, since they are probably related.|
|Committed the fix in svn rev 8669.|
|12.04.2020 03:49||stgatilov||New Issue|
|12.04.2020 03:49||stgatilov||Status||new => assigned|
|12.04.2020 03:49||stgatilov||Assigned To||=> stgatilov|
|12.04.2020 03:49||stgatilov||Steps to Reproduce Updated||View Revisions|
|12.04.2020 04:10||stgatilov||Note Added: 0012358|
|12.04.2020 04:22||stgatilov||Note Added: 0012359|
|12.04.2020 05:17||stgatilov||Relationship added||related to 0005137|
|12.04.2020 05:21||stgatilov||Note Added: 0012362|
|12.04.2020 05:21||stgatilov||Relationship added||related to 0004233|
|12.04.2020 05:21||stgatilov||Relationship added||related to 0005037|
|12.04.2020 05:48||stgatilov||Note Added: 0012363|
|12.04.2020 05:48||stgatilov||Status||assigned => resolved|
|12.04.2020 05:48||stgatilov||Resolution||open => fixed|
|12.04.2020 05:48||stgatilov||Fixed in Version||=> TDM 2.09|
|15.04.2020 06:05||stgatilov||Target Version||TDM 2.09 => TDM 2.08|