[Bug] kdtree API "kdtree_remove" Causes a segment error #4779

ynkan · 2024-11-28T11:13:48Z

Describe the bug

Use the kdtree.c method alone to test logical operations such as kdtree_create=>kdtree_insert=>kdtree_dnn=>kdtree_remove=>kdtree_destroy loop execution
. In the kdtree_remove operation, if the node to be removed is t->root node. resulting in a system segment error.

To reproduce

Using the following code will trigger the problem：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include "kdtree.h"

#define MAX_POINTS 5

void generate_random_points(double points[][2], int num_points)
{
    for (int i = 0; i < num_points; i++)
    {
        points[i][0] = (rand() % 2000) / 100.0;
        points[i][1] = (rand() % 2000) / 100.0;
    }
}

int main(int argc, char *argv[]) 
{

    srand(time(NULL));

    while(1)
    {
        int num = MAX_POINTS;
        double points[MAX_POINTS][2];
        generate_random_points(points, num);

        double target[2] = {(rand() % 2000) / 100.0, (rand() % 2000) / 100.0};

        struct kdtree *kdt = kdtree_create(2, NULL);

        for (int i = 0; i < num; i++)
        {
            int result = kdtree_insert(kdt, points[i], i, 0);
            printf("kdtree insert[uid:%d](%.2f, %.2f) :[%d][%s]\r\n", 
                    i, points[i][0], points[i][1], result, result ? "success" : "failure");
        }

        for (int i = 0; i < num; i++)
        {
            int result = kdtree_remove(kdt, points[i], i);
            printf("kdtree remove[uid:%d](%.2f, %.2f) :[%d][%s]\r\n", 
                i, points[i][0], points[i][1], result, result ? "success" : "failure");
        }

        kdtree_destroy(kdt);
    }

    return 0;
}

Expected behavior

Screenshots

System description

Additional context

ynkan · 2024-11-28T11:15:31Z

The test code is as follows

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include "kdtree.h"

#define MAX_POINTS 5

void generate_random_points(double points[][2], int num_points)
{
    for (int i = 0; i < num_points; i++)
    {
        points[i][0] = (rand() % 2000) / 100.0;
        points[i][1] = (rand() % 2000) / 100.0;
    }
}

int main(int argc, char *argv[]) 
{

    srand(time(NULL));

    while(1)
    {
        int num = MAX_POINTS;
        double points[MAX_POINTS][2];
        generate_random_points(points, num);

        double target[2] = {(rand() % 2000) / 100.0, (rand() % 2000) / 100.0};

        struct kdtree *kdt = kdtree_create(2, NULL);

        for (int i = 0; i < num; i++)
        {
            int result = kdtree_insert(kdt, points[i], i, 0);
            printf("kdtree insert[uid:%d](%.2f, %.2f) :[%d][%s]\r\n", 
                    i, points[i][0], points[i][1], result, result ? "success" : "failure");
        }

        for (int i = 0; i < num; i++)
        {
            int result = kdtree_remove(kdt, points[i], i);
            printf("kdtree remove[uid:%d](%.2f, %.2f) :[%d][%s]\r\n", 
                i, points[i][0], points[i][1], result, result ? "success" : "failure");
        }

        kdtree_destroy(kdt);
    }

    return 0;
}

echoix · 2024-11-28T11:26:01Z

Can you update the issue description to fill out the template, so we can understand what it's about and under which conditions and environment?

ynkan · 2024-11-29T04:51:32Z

Hello, it has been updated. It's a logic problem that can be replicated on any platform and environment

neteler · 2024-11-30T14:12:18Z

I managed to replicate it (I will submit a PR with this test added the the Makefile of kdtree):

kdtree insert[uid:4](11.41, 8.06) :[0][failure]
kdtree remove[uid:0](17.32, 10.23) :[1][success]
kdtree remove[uid:1](3.41, 15.48) :[1][success]
kdtree remove[uid:2](11.41, 8.06) :[1][success]
kdtree remove[uid:3](18.53, 12.10) :[1][success]

Program received signal SIGSEGV, Segmentation fault.
0x00007ffff7f0b2a8 in cmpc (a=0x7fffffffbe20, b=0x0, t=0x4052a0) at kdtree.c:54
54	        if (a->c[i] != b->c[i]) {
(gdb) bt
#0  0x00007ffff7f0b2a8 in cmpc (a=0x7fffffffbe20, b=0x0, t=0x4052a0) at kdtree.c:54
#1  0x00007ffff7f0b7de in kdtree_remove (t=0x4052a0, c=0x7fffffffcee0, uid=4) at kdtree.c:223
#2  0x0000000000401408 in main (argc=1, argv=0x7fffffffd018) at test.c:42
(gdb) bt full
#0  0x00007ffff7f0b2a8 in cmpc (a=0x7fffffffbe20, b=0x0, t=0x4052a0) at kdtree.c:54
        i = 0
#1  0x00007ffff7f0b7de in kdtree_remove (t=0x4052a0, c=0x7fffffffcee0, uid=4) at kdtree.c:223
        sn = {dim = 48 '0', depth = 114 'r', balance = 64 '@', c = 0x7fffffffcee0, uid = 4, child = {0x0, 0x0}}
        n = 0x0
        s = {{n = 0x0, dir = 0}, {n = 0x0, dir = 0}, {n = 0x0, dir = 928}, {n = 0x7ffff7fc0200, dir = 928}, {n = 0x44, dir = 68}, {
            n = 0x7fffffffbef0, dir = -134424292}, {n = 0x7fffffffc137, dir = 20}, {n = 0x7ffff7b07ab0, dir = 19}, {n = 0x7fffffffbf40, 
            dir = -134397658}, {n = 0x7fffffffbf40, dir = -139427992}, {n = 0xd, dir = 0}, {n = 0x7ffff7b07a90, dir = 20}, {
            n = 0x2f6572617774666f, dir = -134398425}, {n = 0x7ffff7fc0200, dir = 0}, {n = 0x7ffff7ffd000 <_rtld_local>, 
            dir = -139429200}, {n = 0x7fffffffc0a0, dir = -134413034}, {n = 0x7ffff7ffd000 <_rtld_local>, dir = -2148}, {
            n = 0x7fffffffc150, dir = 4096}, {n = 0x3f7ffd000, dir = -16560}, {n = 0xfd00, dir = 10726}, {n = 0x0, dir = -15976}, {
            n = 0x0, dir = -2148}, {n = 0x0, dir = 778296}, {n = 0x7ffff7b07a90, dir = -135150250}, {n = 0x300000006, dir = -17184}, {
            n = 0xfd00, dir = 10726}, {n = 0x1, dir = 33261}, {n = 0x0, dir = 0}, {n = 0xc02b8, dir = 4096}, {n = 0x608, 
            dir = 1732966134}, {n = 0x1c40d173, dir = 1711670400}, {n = 0x0, dir = 1728314233}, {n = 0x1f4f99e2, dir = 0}, {n = 0x0, 
            dir = -134399052}, {n = 0x7ffff7a1e13a, dir = -139429200}, {n = 0x7fffffffc490, dir = -134410700}, {n = 0x7ffff7e0b5c1, 
            dir = -134476512}, {n = 0x7fffffffc4b0, dir = -134410700}, {n = 0x1, dir = 0}, {n = 0x7fffffffc140, dir = 0}, {n = 0x1, 
            dir = 0}, {n = 0xffffc160, dir = 1}, {n = 0x1, dir = 0}, {n = 0xffffc150, dir = 1}, {n = 0x0, dir = 0}, {n = 0x0, dir = 1}, {
            n = 0x0, dir = -139429232}, {n = 0x7fffffffd010, dir = 1}, {n = 0x340, dir = 1179403647}, {n = 0x0, dir = 4063235}, {n = 0x0, 
            dir = 64}, {n = 0xbfb38, dir = 0}, {n = 0x1d001e0040000b, dir = 1}, {n = 0x0, dir = 0}, {n = 0x0, dir = 16240}, {n = 0x3f70, 
            dir = 4096}, {n = 0x500000001, dir = 16384}, {n = 0x4000, dir = 16384}, {n = 0xab481, dir = 701569}, {n = 0x1000, dir = 1}, {
            n = 0xb0000, dir = 720896}, {n = 0xb0000, dir = 51436}, {n = 0xc8ec, dir = 4096}, {n = 0x600000001, dir = 776080}, {
            n = 0xbd790, dir = 776080}, {n = 0x870, dir = 2216}, {n = 0x1000, dir = 2}, {n = 0xbd9f8, dir = 776696}, {n = 0xbd9f8, 
            dir = 544}, {n = 0x220, dir = 8}, {n = 0x400000004, dir = 680}, {n = 0x2a8, dir = 680}, {n = 0x40, dir = 64}, {n = 0x8, 
            dir = 4}, {n = 0x2e8, dir = 744}, {n = 0x2e8, dir = 172}, {n = 0xac, dir = 4}, {n = 0x46474e553, dir = 680}, {n = 0x2a8, 
            dir = 680}, {n = 0x40, dir = 64}, {n = 0x8, dir = 1685382480}, {n = 0xb5ea0, dir = 745120}, {n = 0x0, dir = 4364}, {n = 0x1, 
            dir = -138010327}, {n = 0x66474e551, dir = 0}, {n = 0x0, dir = 0}, {n = 0x0, dir = -15008}, {n = 0x39, dir = 2}, {n = 0x2, 
            dir = -137983240}, {n = 0x7fffffffcc80, dir = 5}, {n = 0xfffffffb, dir = 2}, {n = 0x7fffffffc600, dir = -137979116}, {
            n = 0x30312e3231cc80, dir = -137980825}, {n = 0xa000000000000000, dir = 0}, {n = 0x4c0010002, dir = 5}, {n = 0x1400000004, 
            dir = 3}, {n = 0x9, dir = 0}, {n = 0x0, dir = -14368}, {n = 0x7ffff7ad89f8, dir = 0}, {n = 0x3ffffffffd8f0000, dir = 6}, {
            n = 0x10, dir = -134477904}, {n = 0x0, dir = -137980241}, {n = 0x1ffffc4e0, dir = 7}, {n = 0x66, dir = 5}, {
            n = 0x7ffff7df43c0 <_nl_global_locale>, dir = 2147483647}, {n = 0x7fffffffc410, dir = 0}, {n = 0x2e00000002, dir = -15342}, {
            n = 0x2, dir = -14384}, {n = 0x7fff00000002, dir = -134476512}, {n = 0x7ffffffffffb, dir = -139429200}, {n = 0x7ffff7fc1250, 
            dir = -134227280}, {n = 0x7ffff7e0037f, dir = -134476512}, {n = 0x89c00000, dir = 0}, {n = 0x6600000000, dir = 1}, {
            n = 0x7fffffffc480, dir = 2}, {n = 0x7fffffffc420, dir = 1}, {n = 0x7fffffffc450, dir = 2}, {n = 0x18333333333333, 
            dir = -134421054}, {n = 0x0, dir = 160}, {n = 0x0, dir = 1771975936}, {n = 0x7ffff7b081e0, dir = -136363072}, {n = 0x0, 
            dir = -14384}, {n = 0x7ffff7dbbb3a, dir = -136587175}, {n = 0x7fffffffc700, dir = -137973116}, {n = 0x7fffffffc680, 
            dir = -14720}, {n = 0x7fffffffcc80, dir = -14408}, {n = 0x7fff00000001, dir = -139430528}, {n = 0x7fffffffc610, 
            dir = -134435544}, {n = 0x7fff00000001, dir = -136594630}, {n = 0x7ffff7dbd859 <dot>, dir = -134479832}, {n = 0x7fff00000001, 
            dir = -134473808}, {n = 0x7fffffffc650, dir = -134435544}, {n = 0x1, dir = -134475184}, {n = 0x7fffffffc670, 
            dir = -134435544}, {n = 0x1, dir = -134476512}, {n = 0x7fffffffc690, dir = 1771975936}, {n = 0x1, dir = -137983240}, {
            n = 0x402010, dir = 4202618}, {n = 0x7fffffffcd80, dir = -13184}, {n = 0x7fffffffcc40, dir = -137946868}, {n = 0x1, dir = -1}, 
          {n = 0xffffc6f0, dir = 4202594}, {n = 0x402050, dir = 0}, {n = 0x0, dir = 2}, {n = 0x0, dir = 100}, {n = 0x7fffffffcc07, 
            dir = -14848}, {n = 0x7fffffffcc08, dir = 1}, {n = 0x500000000, dir = 10}, {n = 0x20, dir = 0}, {n = 0x7fff00000000, dir = 0}, 
          {n = 0x0, dir = -14400}, {n = 0x4028333333333333, dir = 0}, {n = 0x2, dir = 102}, {n = 0x7fff00000020, dir = 0}, {
            n = 0x7ffff7a1ce20, dir = 8}, {n = 0x7fffffffce60, dir = -12896}, {n = 0x7fffffffc820, dir = 1024}, {n = 0x7ffff7fc1250, 
            dir = 0}, {n = 0x0, dir = 0}, {n = 0x7ffff7fc0d20, dir = -134475184}, {n = 0x0, dir = 0}, {n = 0x0, dir = -134406893}, {
            n = 0x0, dir = -134454824}, {n = 0x7ffff7ffe8c0, dir = -134454864}, {n = 0x821e8e0d, dir = -134454464}, {n = 0x7fffffffc990, 
            dir = -134405893}, {n = 0x6, dir = -134454464}, {n = 0x7ffff7ffe8c0, dir = -13992}, {n = 0x7fffffffc954, dir = -138324496}, {
            n = 0x7ffff7fc1250, dir = -138332812}, {n = 0x7c9e7894, dir = -138248776}, {n = 0x7fffffffc9f0, dir = 0}, {n = 0x1, 
            dir = -134223640}, {n = 0x7fffffffca38, dir = -14080}, {n = 0x7fffffffca40, dir = -13996}, {n = 0x7fffffffcae0, 
            dir = -136588277}, {n = 0x0, dir = -134406893}, {n = 0x0, dir = -138324496}, {n = 0x7ffff7fc1250, dir = -138330700}, {
            n = 0x3de00ec7, dir = -138248776}, {n = 0x7fffffffca80, dir = -134405893}, {n = 0x645, dir = -138248776}, {n = 0x7ffff7fc1250, 
            dir = -13752}, {n = 0x7fffffffca44, dir = -137677899}, {n = 0x7ffff7ffe680, dir = 63}, {n = 0x7fffffffcbd8, dir = 4215616}, {
            n = 0x7fffffffcb10, dir = -136365376}, {n = 0x3f, dir = -64}, {n = 0x7ffff7df2050 <_IO_file_jumps>, dir = 48}, {
            n = 0x7fffffffca60, dir = -137674878}, {n = 0x0, dir = -134268968}, {n = 0x7ffff7df45c0 <_IO_2_1_stdout_>, dir = 1024}, {
            n = 0x7fffffffccb0, dir = -136372144}, {n = 0x7fffffffcb30, dir = -137832512}, {n = 0x1a, dir = 9}, {n = 0x1, 
            dir = -137775739}, {n = 0x7ffff7df45c0 <_IO_2_1_stdout_>, dir = -136372144}, {n = 0x405340, dir = 48}, {n = 0x7fffffffcaf0, 
            dir = -137783555}, {n = 0x0, dir = 48}...}
        top = 0
        dir = 1
        found = 0
        balance = 1
        bmode = 1
#2  0x0000000000401408 in main (argc=1, argv=0x7fffffffd018) at test.c:42
        result = 1
        i = 4
        num = 5
        points = {{17.32, 10.23}, {3.4100000000000001, 15.48}, {11.41, 8.0600000000000005}, {18.530000000000001, 12.1}, {11.41, 
            8.0600000000000005}}
        target = {10.57, 7.9699999999999998}
        kdt = 0x4052a0

neteler · 2024-11-30T14:17:46Z

I will submit a PR with this test added the the Makefile of kdtree)

Say: @ynkan do you agree that you code is included in GRASS GIS under the GPL-2.0-or-later license?
You are also kindly invited to submit the test.c with proper file header to lib/btree2/ and I can add in you PR the needed Makefile changes which I have already locally prepared.

ynkan · 2024-12-03T06:01:29Z

I will submit a PR with this test added the the Makefile of kdtree)

Say: @ynkan do you agree that you code is included in GRASS GIS under the GPL-2.0-or-later license? You are also kindly invited to submit the test.c with proper file header to lib/btree2/ and I can add in you PR the needed Makefile changes which I have already locally prepared.

Sorry, haven't paid attention to the above message reply recently; I agree，the above test code is at your disposal and manipulation

This PR adds the kdtree test proposed in OSGeo#4779. At time the test triggers a segmentation fault: ```bash make [...] make lib make[1]: Entering directory '/home/mneteler/software/grass_main/lib/btree2' if [ "" != "" -a -f "".html ] ; then make html ; fi make[1]: Leaving directory '/home/mneteler/software/grass_main/lib/btree2' ==============TEST============= make test make[1]: Entering directory '/home/mneteler/software/grass_main/lib/btree2' gcc -g -Wall -Wstringop-truncation -Wshadow -Wlogical-op -Werror-implicit-function-declaration -fPIC -fno-common -fno-omit-frame-pointer -fexceptions -Wextra -Wunused -Wreturn-type -Wfatal-errors -march=native -std=gnu99 -fexceptions -fstack-protector -m64 -fdiagnostics-color -fPIC -I/home/mneteler/software/grass_main/dist.x86_64-pc-linux-gnu/include -I/home/mneteler/software/grass_main/dist.x86_64-pc-linux-gnu/include -DPACKAGE=\""grasslibs"\" -I/home/mneteler/software/grass_main/dist.x86_64-pc-linux-gnu/include -I/home/mneteler/software/grass_main/dist.x86_64-pc-linux-gnu/include -DRELDIR=\"lib/btree2\" -o OBJ.x86_64-pc-linux-gnu/test.o -c test.c test.c: In function ‘main’: test.c:18:14: warning: unused parameter ‘argc’ [-Wunused-parameter] 18 | int main(int argc, char *argv[]) | ~~~~^~~~ test.c:18:26: warning: unused parameter ‘argv’ [-Wunused-parameter] 18 | int main(int argc, char *argv[]) | ~~~~~~^~~~~~ : && gcc -L/home/mneteler/software/grass_main/dist.x86_64-pc-linux-gnu/lib -L/home/mneteler/software/grass_main/dist.x86_64-pc-linux-gnu/lib -Wl,--no-undefined -Wl,-z,now -Wl,--export-dynamic -Wl,-rpath-link,/home/mneteler/software/grass_main/dist.x86_64-pc-linux-gnu/lib -Wl,-rpath,/usr/local/grass85/lib -Wl,-soname,test -o OBJ.x86_64-pc-linux-gnu/test OBJ.x86_64-pc-linux-gnu/test.o -lgrass_gis.8.5 -lgrass_btree2.8.5 -lgrass_gis.8.5 -lm GISRC=/home/mneteler/software/grass_main/dist.x86_64-pc-linux-gnu/demolocation/.grassrc85 GISBASE=/home/mneteler/software/grass_main/dist.x86_64-pc-linux-gnu PATH="/home/mneteler/software/grass_main/dist.x86_64-pc-linux-gnu/bin:/home/mneteler/software/grass_main/dist.x86_64-pc-linux-gnu/bin:/home/mneteler/software/grass_main/dist.x86_64-pc-linux-gnu/scripts:$PATH" PYTHONPATH="/home/mneteler/software/grass_main/dist.x86_64-pc-linux-gnu/etc/python:/home/mneteler/software/grass_main/dist.x86_64-pc-linux-gnu/gui/wxpython:$PYTHONPATH" LD_LIBRARY_PATH="/home/mneteler/software/grass_main/dist.x86_64-pc-linux-gnu/bin:/home/mneteler/software/grass_main/dist.x86_64-pc-linux-gnu/bin:/home/mneteler/software/grass_main/dist.x86_64-pc-linux-gnu/scripts:/home/mneteler/software/grass_main/dist.x86_64-pc-linux-gnu/lib:/home/mneteler/software/grass_main/dist.x86_64-pc-linux-gnu/lib:" LC_ALL=C LANG=C LANGUAGE=C OBJ.x86_64-pc-linux-gnu/test kdtree insert[uid:0](7.43, 5.41) :[1][success] kdtree insert[uid:1](16.27, 13.36) :[1][success] kdtree insert[uid:2](15.87, 19.59) :[1][success] kdtree insert[uid:3](12.32, 3.86) :[1][success] [...] kdtree insert[uid:2](3.67, 10.96) :[1][success] kdtree insert[uid:3](5.67, 6.99) :[1][success] kdtree insert[uid:4](5.67, 6.99) :[0][failure] kdtree remove[uid:0](19.78, 18.10) :[1][success] kdtree remove[uid:1](4.44, 10.85) :[1][success] kdtree remove[uid:2](3.67, 10.96) :[1][success] kdtree remove[uid:3](5.67, 6.99) :[1][success] make[1]: *** [Makefile:27: test] Segmentation fault (core dumped) ```

neteler · 2024-12-03T07:31:00Z

I agree，the above test code is at your disposal and manipulation

Thanks! I have submitted it in #4797 so that debugging is easier for others (kdtree is not really my expertise).

nilason · 2024-12-03T15:04:05Z

The test doesn't take into account of the result of kdtree_insert() and ends up trying to remove a failed insertion of a node.

kdtree_insert() fails on attempt to insert a node with equal points, in this example uid 2 and 4:

kdtree insert[uid:0](16.08, 1.27) :[1][success]
kdtree insert[uid:1](18.74, 3.04) :[1][success]
kdtree insert[uid:2](14.47, 14.18) :[1][success]
kdtree insert[uid:3](3.39, 6.27) :[1][success]
kdtree insert[uid:4](14.47, 14.18) :[0][failure]
kdtree remove[uid:0](16.08, 1.27) :[1][success]
kdtree remove[uid:1](18.74, 3.04) :[1][success]
kdtree remove[uid:2](14.47, 14.18) :[1][success]
kdtree remove[uid:3](3.39, 6.27) :[1][success]
gmake[1]: *** [Makefile:27: test] Segmentation fault: 11

ynkan added the bug Something isn't working label Nov 28, 2024

nilason added this to the 8.5.0 milestone Dec 2, 2024

nilason added C Related code is in C libraries labels Dec 2, 2024

neteler mentioned this issue Dec 3, 2024

lib/btree2: add kdtree test #4797

Open

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

[Bug] kdtree API "kdtree_remove" Causes a segment error #4779

[Bug] kdtree API "kdtree_remove" Causes a segment error #4779

ynkan commented Nov 28, 2024 •

edited

Loading

ynkan commented Nov 28, 2024 •

edited

Loading

echoix commented Nov 28, 2024

ynkan commented Nov 29, 2024

neteler commented Nov 30, 2024 •

edited

Loading

neteler commented Nov 30, 2024

ynkan commented Dec 3, 2024 •

edited

Loading

neteler commented Dec 3, 2024

nilason commented Dec 3, 2024

[Bug] kdtree API "kdtree_remove" Causes a segment error #4779

[Bug] kdtree API "kdtree_remove" Causes a segment error #4779

Comments

ynkan commented Nov 28, 2024 • edited Loading

Describe the bug

To reproduce

Expected behavior

Screenshots

System description

Additional context

ynkan commented Nov 28, 2024 • edited Loading

echoix commented Nov 28, 2024

ynkan commented Nov 29, 2024

neteler commented Nov 30, 2024 • edited Loading

neteler commented Nov 30, 2024

ynkan commented Dec 3, 2024 • edited Loading

neteler commented Dec 3, 2024

nilason commented Dec 3, 2024

ynkan commented Nov 28, 2024 •

edited

Loading

ynkan commented Nov 28, 2024 •

edited

Loading

neteler commented Nov 30, 2024 •

edited

Loading

ynkan commented Dec 3, 2024 •

edited

Loading