Crash due to tree travesal depth exceeding 256

[Frooxius]

Hello! It's me again after long time.

I bring you yet another issue stemming from user generated content x3

Recently certain world/items started causing hard crashes. I've narrowed it down due to a tree traversal depth being deeper than 256, causing stack to be stomped over here:

bepuphysics2/BepuPhysics/Trees/Tree_VolumeQuery.cs

Line 41 in ec5082f

Debug.Assert(stackEnd < TraversalStackCapacity - 1, "At the moment, we use a fixed size stack. Until we have explicitly tracked depths, watch out for excessive depth traversals.");

I've added workaround on our end by increasing the traversal depth to 1024, which fixed the issue with the specific content, but this only "delays" the issue, rather than fully solving it.

The code there alludes to explicitly tracked depths - is that something you'd be willing to prioritize at some point?

I'm not sure what the proper handling on our end would be - with user generated content, people can setup colliders in a way that will exceed the limit of 1024 as well (or whatever value we set it to) - we need to be able to handle it more gracefully than making the stack explode.

Would the system see if the depth is excessive and just allocate the list on heap? Meaning it'll be less efficient, but things being slower is better than everything crashing?

Or set some hard limit, above which the bodies will be ignored? Though that feels worse, because it'll cause odd issues, where some colliders randomly don't work.

[RossNordby]

Sorry for slowness! A brief response now:

1. I've seen this kind of thing in the past when something bad is happening to tree insertion. It really shouldn't be possible to trigger this error if the tree builder is working at all reasonably.
2. Allocating on the heap conditionally in response to depth would be a reasonable approach. Would really like to figure out how the tree's getting so messed up, though.

[Frooxius]

@RossNordby No worries, take your time!

1. I can make a repro case for you for this if you'd like to improve the tree handling. It'll take a bit though, I'll try to get back to you as soon as I can with it.
2. I think it'd still be beneficial to do, at least for our use-case. It makes handling of bad trees more graceful - just general slowness, rather than hard crash.

[RossNordby]

A repro would be very nice if you find the time! Another user was encountering something that smelled similar, but struggled to find a reliable repro.

And yes, would definitely also like to actually-fix the overrun!

[RossNordby]

wee update: I think you can probably observe this reliably if you stuff a few thousand (or hundred thousand) statics in the same spot and then shoot a ray at them. Tree insertion actually seems fine; I think the culprit is an incomplete/bad heuristic for handling ties when doing static refinement.

[felix-ri]

Hi.

I have a similar problem:

I have an existing Simulation (from already inserted objects) and then I insert another 6000 objects (with 2 alternating Positions), the tree refinement crashes with Stackoverflow. (some times in Refit2WithCacheOptimizationAndTaskSpawning() sometimes in FindSubtreeRefinementTargets())

I didn't use Statics at all, only normal kinematic bodies.

I could reproduce this issue with the extracted tree from the Simulation (depth12) and then adding 100 objects in it. This causes the tree to be degenerate (depth 48).

When adding 6000 objects to the tree and then running RefitAndRefine(), it produces a tree with depth 2773.

Building the whole tree from scratch with a BinnedBuilder and then running BinnedRefine() produces a more acceptable tree. (depth 26 for 6000 objects added)

Link to repro: https://github.com/felix-ri/bepuphysics2/tree/DegenerateTreeTest

I can't post the binary file of the tree publicly here, but I could send it to you directly.

PS:
If I should open another Issue, please tell me.

[RossNordby]

Thanks, I'll take a look! Repros are always great to have. I do have another repro that gets the depth to 300-ish, but it sounds like you found something far more pathological which is very likely going to be helpful.

Depending on the size, dropbox/google drive/onedrive/e-mail in my profile would all work for me. I guess technically a github fork with release assets might work too, but would be a bit annoying to set up.

[felix-ri]

I sent it to you via email.
I hope it didn't get blocked on the way.

[RossNordby]

Wee update:
#375 fixed a heuristic issue with certain kinds of degeneracy. This may fix the original issue, but it will not fix the insertion repro (which is a separate insertion heuristic problem); I suspect the insertion issue is a more frequent source of issues. It also doesn't yet track depth to guarantee a lack of explosions. Soonish!

[RossNordby]

With #380, the probability of creating the degenerate trees via insertion should be much reduced. I was hoping to get the stackalloc hole fixed today too, but didn't, alas.

Current plan to eliminate the risk of an overrun is to keep track of a conservative maximum depth that gets updated by adds/builds/refines as needed. An exact depth can be calculated directly. That'll then inform the stackalloc size. If the depth is excessively large, I'm planning to just make it fail in debug mode with a 'hey please report this 🥺' but in release mode it'll just grab some memory via NativeMemory or, if provided, a BufferPool. (I'd rather not make a BufferPool parameter required for all ray cast calls for what should be an error condition.)

[RossNordby]

#381 plumbed through BufferPools for tree queries to handle the pathological case without explosions. Ended up being problematic to actually track conservative depth due to the parallel nature of refinement; it's still doable, but more work than I wanted to insert on the critical path to finally getting this fixed. Can revisit it later, but the overhead is pretty minimal (the branch is ~always predicted correctly within the traversal loop, and outside of pathological cases, it still always uses cheapo-allocated stack memory).