View Issue Details

IDProjectCategoryView StatusLast Update
0005212The Dark ModCodingpublic03.01.2021 04:33
Reporterstgatilov Assigned Tostgatilov  
PrioritynormalSeveritycrashReproducibilitysometimes
Status resolvedResolutionfixed 
Product VersionTDM 2.08 
Target VersionTDM 2.08Fixed in VersionTDM 2.08 
Summary0005212: dmap: crash when merging leaf nodes in AAS
DescriptionDuring 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 ReproduceDmap some complex map, and there is a small chance of this happening.
Additional InformationReported on forums here:
  https://forums.thedarkmod.com/index.php?/topic/20291-beta-testing-208/&do=findComment&comment=445963

Although the problem itself is quite well-known and was happening long before 2.08 (I guess since original Doom 3).
TagsNo tags attached.

Relationships

related to 0005137 resolvedstgatilov Dmap optimization breaks rain patches 
related to 0004233 resolvedstgatilov Crash during runAAS 
related to 0005037 resolvedstgatilov dmap crashes on specific map 

Activities

stgatilov

stgatilov

12.04.2020 04:10

administrator   ~0012358

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.
stgatilov

stgatilov

12.04.2020 04:22

administrator   ~0012359

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.
stgatilov

stgatilov

12.04.2020 05:21

administrator   ~0012362

Adding 0004233 and 0005037, since they are probably related.
stgatilov

stgatilov

12.04.2020 05:48

administrator   ~0012363

Committed the fix in svn rev 8669.

Issue History

Date Modified Username Field Change
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
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
03.01.2021 04:33 stgatilov Fixed in Version TDM 2.09 => TDM 2.08