Segmentation fault with KDTree

[dopplershift]

When running the code below (boiled down from the original producer) I get a segmentation fault.

Reproducing code example:

import numpy as np
from scipy.spatial import KDTree

points = np.arange(34.).reshape(-1, 2)
points[0] = np.nan
points[8] = np.nan
KDTree(points)

Error message:

❯ python test_crash.py
[1]    89987 segmentation fault  python test_crash.py

Scipy/Numpy/Python version information:

1.7.1 1.21.1 sys.version_info(major=3, minor=9, micro=6, releaselevel='final', serial=0)

I'm running this locally on macOS 11.5 (x86_64), but original issue was seen on Ubuntu 20.04.2 (GitHub Actions). The MetPy test that now segfaults passes fine with Scipy 1.7.0.

[czgdp1807]

The error code works fine on my system (Ubuntu 18.04).

Versions

NumPy - 1.21.1
SciPy - 1.8.0.dev0+1473.2d251cb
Python - sys.version_info(major=3, minor=9, micro=5, releaselevel='final', serial=0)

May be, the fix can be applied to 1.7.1 from 1.8.0.dev?

[jkelling]

The test also works on my system (Ubuntu 18.04) with

Numpy - 1.21.1
Python - sys.version_info(major=3, minor=8, micro=11, releaselevel='final', serial=0)

With both SciPy 1.7.1 and master.

import numpy as np
from scipy.spatial import KDTree

import scipy
print(scipy.__version__)

points = np.arange(34.).reshape(-1, 2)
points[0] = np.nan
points[8] = np.nan

tree = KDTree(points)

print(tree.query(x=(1,2)))

Output:

1.7.1
(1.4142135623730951, 1)

[dopplershift]

I'll note that my copy of 1.7.1 was installed from PyPI, not built locally. Not sure if that's important here or not.

[czgdp1807]

I checked on Google colab by installing SciPy and NumPy from PyPI (using pip). There was no segmentation fault thrown by the code in the description of the issue. Let me know if I am something out.

sys.version_info(major=3, minor=7, micro=11, releaselevel='final', serial=0)

[jkelling]

@dopplershift as noone else appears to be able to reproduce this, can you please run (requires gdb):

gdb python -ex "run test_crash.py" -ex bt

[dopplershift]

I'm on macOS, so it needed to be lldb, but that did the job. The crash backtrace is 7.1M uncompressed.

[darrivau]

The following code does crash on Windows (conda or pip) with N > 13 but does not on Ubuntu:

import sys
import numpy as np
from scipy.spatial import KDTree as KDTree

def calc_kdtree(xys):
    tree = KDTree(xys)
    segments = np.array([*tree.query_pairs(2)])
    return segments

if __name__ == "__main__":
    if len(sys.argv) > 1:
        N = int(sys.argv[1])
        print(N)
    else:
        N = 10
    np.show_config()
    xys = np.full((N, 2), np.nan)
    xys[0:N:2,0] = np.arange(0,N/2)
    xys[0:N:2,1] = 0
    print(xys)
    
    print("----------------Start-----------------")    
    print(calc_kdtree(xys))
    print("----------------The end---------------")

I think this is related to this issue. Running gdb.exe -ex r --args powershell.exe python tmp.py 14 -ex bt on windows with mkl gives:

blas_info:
    libraries = ['cblas', 'blas', 'cblas', 'blas', 'cblas', 'blas']
    library_dirs = ['C:/Users/Denis/miniconda3/envs/mkl\\Library\\lib']
    include_dirs = ['C:/Users/Denis/miniconda3/envs/mkl\\Library\\include']
    language = f77
    define_macros = [('HAVE_CBLAS', None)]
blas_opt_info:
    define_macros = [('NO_ATLAS_INFO', 1), ('HAVE_CBLAS', None)]
    libraries = ['cblas', 'blas', 'cblas', 'blas', 'cblas', 'blas']
    library_dirs = ['C:/Users/Denis/miniconda3/envs/mkl\\Library\\lib']
    include_dirs = ['C:/Users/Denis/miniconda3/envs/mkl\\Library\\include']
    language = f77
lapack_info:
    libraries = ['lapack', 'blas', 'lapack', 'blas']
    library_dirs = ['C:/Users/Denis/miniconda3/envs/mkl\\Library\\lib']
    language = f77
lapack_opt_info:
    libraries = ['lapack', 'blas', 'lapack', 'blas', 'cblas', 'blas', 'cblas', 'blas', 'cblas', 'blas']
    library_dirs = ['C:/Users/Denis/miniconda3/envs/mkl\\Library\\lib']
    language = f77
    define_macros = [('NO_ATLAS_INFO', 1), ('HAVE_CBLAS', None)]
    include_dirs = ['C:/Users/Denis/miniconda3/envs/mkl\\Library\\include']
Supported SIMD extensions in this NumPy install:
    baseline = SSE,SSE2,SSE3
    found = SSSE3,SSE41,POPCNT,SSE42,AVX,AVX2
    not found = F16C,FMA3,AVX512F,AVX512CD,AVX512_SKX,AVX512_CLX,AVX512_CNL
[[ 0.  0.]
 [nan nan]
 [ 1.  0.]
 [nan nan]
 [ 2.  0.]
 [nan nan]
 [ 3.  0.]
 [nan nan]
 [ 4.  0.]
 [nan nan]
 [ 5.  0.]
 [nan nan]
 [ 6.  0.]
 [nan nan]]
----------------Start-----------------
----------------Start-----------------
[New Thread 6796.0x15bc]
[New Thread 6796.0x1470]
[Inferior 1 (process 6796) exited with code 01]
(gdb) bt
No stack.

and with openblas:

blas_mkl_info:
  NOT AVAILABLE
blis_info:
  NOT AVAILABLE
openblas_info:
    library_dirs = ['D:\\a\\1\\s\\numpy\\build\\openblas_info']
    libraries = ['openblas_info']
    language = f77
    define_macros = [('HAVE_CBLAS', None)]
blas_opt_info:
    library_dirs = ['D:\\a\\1\\s\\numpy\\build\\openblas_info']
    libraries = ['openblas_info']
    language = f77
    define_macros = [('HAVE_CBLAS', None)]
lapack_mkl_info:
  NOT AVAILABLE
openblas_lapack_info:
    library_dirs = ['D:\\a\\1\\s\\numpy\\build\\openblas_lapack_info']
    libraries = ['openblas_lapack_info']
    language = f77
    define_macros = [('HAVE_CBLAS', None)]
lapack_opt_info:
    library_dirs = ['D:\\a\\1\\s\\numpy\\build\\openblas_lapack_info']
    libraries = ['openblas_lapack_info']
    language = f77
    define_macros = [('HAVE_CBLAS', None)]
Supported SIMD extensions in this NumPy install:
    baseline = SSE,SSE2,SSE3
    found = SSSE3,SSE41,POPCNT,SSE42,AVX,AVX2
    not found = F16C,FMA3,AVX512F,AVX512CD,AVX512_SKX,AVX512_CLX,AVX512_CNL
[[ 0.  0.]
 [nan nan]
 [ 1.  0.]
 [nan nan]
 [ 2.  0.]
 [nan nan]
 [ 3.  0.]
 [nan nan]
 [ 4.  0.]
 [nan nan]
 [ 5.  0.]
 [nan nan]
 [ 6.  0.]
 [nan nan]]
----------------Start-----------------
[New Thread 700.0x1794]
[New Thread 700.0x170]
[Inferior 1 (process 700) exited with code 01]
(gdb) bt
No stack.

[rgommers]

I'm on macOS, so it needed to be lldb, but that did the job. The crash backtrace is 7.1M uncompressed.

This seems to be an infinite recursion, it's 55,000 lines of exactly the same

* thread #1, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=2, address=0x7ffeeebffff8)
  * frame #0: 0x00007fff2014a662 libsystem_malloc.dylib`szone_malloc_should_clear + 61
    frame #1: 0x00007fff20163f3b libsystem_malloc.dylib`_malloc_zone_malloc + 118
    frame #2: 0x00007fff202e782a libc++abi.dylib`operator new(unsigned long) + 26
    frame #3: 0x0000000106fbed9b ckdtree.cpython-39-darwin.so`build(ckdtree*, long, long, double*, double*, int, int) + 4763
    frame #4: 0x0000000106fbee6e ckdtree.cpython-39-darwin.so`build(ckdtree*, long, long, double*, double*, int, int) + 4974
    frame #5: 0x0000000106fbee6e ckdtree.cpython-39-darwin.so`build(ckdtree*, long, long, double*, double*, int, int) + 4974
...
    frame #55170: 0x0000000106fbee6e ckdtree.cpython-39-darwin.so`build(ckdtree*, long, long, double*, double*, int, int) + 4974

I cannot reproduce this on macOS with current main. I could reproduce it on Linux recently though.

[charris]

Does optimization level make a difference?