BUG: wrap median_filter stability

[tylerjereddy]

• Fixes BUG: median_filter on 1D array crashes with memory corruption using SciPy 1.15.0 #22250

• Fixes BUG: ndimage.median_filter: Heap corruption with scipy 1.15 #22325

• Fixes BUG: signal.medfilt and ndimage.median_filter not returning correct output #22333

• The shims in this branch seem to substantially improve the probability of the new allow test_gh_22250 to pass under high repeat counts with pytest-repeat on Linux. There still seems to be a memory instability that leads to stochastically incorrect results between test incantations though.

• I wonder if any of the memory issues Warren mentions at BUG: ndimage: C++ memory management issues in _rank_filter_1d.cpp #22365 might be related to the instability (Warren suggests the crashes are not related, but I'm no longer seeing crashes on Linux on this branch). (kind of, Warren mentioned unchecked memory for data, but it was specifically the lack of initialization/zeroing out that was causing algorithmic problems on Linux, separate from the index segfault).

[ci skip] [skip cirrus]

[tylerjereddy]

this block is based on an analysis of the indices visited by median_filter in the default reflect mode because of the patterning similarities between the two approaches from the docs:

‘reflect’ d c b a | a b c d | d c b a
‘wrap’ a b c d | a b c d | a b c d

kind of a "flipped" order to boundary handling.

This is a bit of a fishing expedition though.

[tylerjereddy]

One point of caution--with the memory initialization issue repaired, I no longer need this patch, though the patch is also not harmful with the current suite of tests that we have.

Objectively that probably means that we should remove this part of the shim. That said, it may also be sensible to expand the testing to include non-zero origin values vs. 1.14.1 and n-dims vs. 1.14.1 because the lack of sensitivity on the indexing here makes me a bit suspicious.

[tylerjereddy]

On ARM Mac, python dev.py test -t scipy/ndimage/tests/test_filters.py::test_gh_22250 -- --count=1000 passes on this branch, while on Linux it variably produced 382 failures (all for a filter size of 20 that matches the image itself) and 397 failures (mostly size 20 failures, but 1 filter size 15 failure) over two incantations.

Reverting the patch on MacOS ARM results in segfaults.

That might be a decent clue that memory shenanigans and/or something different compilers can optimize differently might be to blame on this branch rather than a fundamental algorithmic misunderstanding (though I probably should add even more 1.14.1-based test cases given that I'm not operating from a place of deep expertise).

[tylerjereddy]

Switching to clang compiler toolchain (FC=gfortran-11 CC=clang-15 CXX=clang++-15) for a clean build on Linux doesn't resolve the test failures. Hmm, so fundamental memory management issue rather than compiler-specific behavior perhaps?

[tylerjereddy]

If I link against address sanitizer on Linux and LD_PRELOAD libasan.so, the tests pass reliably on Linux over thousands of repeat incantations. The actual output from the sanitizer seems completely unhelpful though, and it also detects leaks in other completely unrelated test modules.

Nonetheless, IIUC, the preload intercepts and overrides malloc, so that is probably evidence that memory allocation is indeed the remaining issue.

[ev-br]

it also detects leaks in other completely unrelated test modules.

Quoting from Tyler in an unrelated thread: Open separate issues for separate issues? :-)

[tylerjereddy]

After many more hours of debugging, and static analyzers proving useless, this block of code seems to do the trick. data is uninitialized memory, and the treatment of such memory apparently differs on many Linux platforms vs. MacOS, explaining why pytest-repeat was stochastically exhibiting algorithmic failures.

With this additional shim, test_gh_22250 passes with thousands of repeat incantations on my Linux box vs. failing before.

I'll open this PR for review now and see if the CI agrees with me (there are two unrelated test_batch.py failures I see locally on main as well).

There are many open issues about this machinery, so if there is interest in this patch, I'd appreciate suggestions for which additional test(s) you'd like me to add in (from specific issues, multi-dimensional cases as well? etc.).

[ev-br]

Wow, that was a hard catch!

Confirmed that locally this PR avoids the segfault from gh-22250. The CI seems to agree, modulo an unrelated failure which is safe to ignore.

FWIW, I don't think ndim > 1 tests are essential here, given that the problematic addition of scipy 1.5.1 is specifically a 1D shortcut.

Looking through related issues:

• BUG: ndimage.median_filter: Heap corruption with scipy 1.15 #22325 does not have a reproducible example, and is quite likely to be the same, so IMO it's OK to add closes gh-22325 on this PR unless there's evidence to the contrary
• Warren's MWE at BUG: signal.medfilt and ndimage.median_filter not returning correct output #22333 (comment) seems to be fixed by this PR
• BUG: ndimage: C++ memory management issues in _rank_filter_1d.cpp #22365 highlights several issues which, as Warren notes, are unlikely to be related; I'd agree addressing these in this PR is optional.

All in all, I'd be +1 for landing this as is for 1.5.2, and addressing #22365 in a less hectic pace in the 1.6.0 timeframe.

[j-bowhay]

Also possibly closes #22368 and #22333

[tylerjereddy]

@WarrenWeckesser opinion?

[tylerjereddy]

Also possibly closes #22368 and #22333

For gh-22368, I found no evidence that my patch is helpful per analysis at #22368 (comment)

For gh-22333, the patch here indeed resolves the problem on x86_64 Linux per analysis at #22333 (comment). I've adjusted the original comment above accordingly and added the additional regression test for that issue.

I'm somewhat-tempted to consider self-merging this for the 1.15.2 release if this remains free of objections. The biggest objection is my own at #22402 (comment), I hate having code changes that are poorly understood and not even changing the test results like that. If we backed that out, would need to be careful to pytest-repeat-based probe the new regression tests to be sure it wasn't helping.

[WarrenWeckesser]

@tylerjereddy, I probably won't be able to get back to this until sometime next week, so don't wait for me if you need to wrap this up sooner.

[dschmitz89]

I can't review but this bug is hitting a lot of people and this seems to resolve it based on the tests. I am +1 for back porting into 1.15.2.

[tylerjereddy]

The CI failures are unrelated and covered by the issue Matt opened recently at gh-22534. Given the swath of issues this fixes, the two core developer "approvals," and seriousness of the bugs fixed (segfaults possible on Linux), I think I'll go ahead and squash merge for backporting despite this being a sub-optimal self-merge activity.

I suspect what is going to happen is that the lack of understanding around #22402 (comment) will come back to bite us someday, but I think this at least has support as an incremental improvement we could get more feedback on while preventing some bad results/segfaults.