运行处理结构指针的程序时偶尔出现堆溢出错误

我一直在在线进行DSA课程,这是我为解决其中一个问题而做的尝试。我承认我对C ++知之甚少,我根本不应该弄乱结构和指针,但是我已经尝试了一段时间,以便自己学一点,但我似乎无法找出问题所在。

问题陈述:给定n个段的集合{[a 0,b 0],[a 1,b 1],。。 。 。 ,[a n-1,b n-1]},并且在一条线上具有整数坐标,找到 最少m个点,以使每个线段至少包含一个点。也就是说,找到一个 最小大小的整数X的集合,使得对于任何段[a i,b i]都有一个点x∈X这样 a i≤x≤b i。

#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>
#include <unistd.h>

std::vector<int> output;

struct linedata
{
    int start;
    int end;
    bool covered = false;
    struct linepoint* sloc = (struct linepoint*)malloc(sizeof(struct linepoint*));
    struct linepoint* eloc = (struct linepoint*)malloc(sizeof(struct linepoint*));
};

struct linepoint
{
    int coord;
    bool start;
    struct linedata* refer = (struct linedata*)malloc(sizeof(struct linedata*));
    struct linepoint* selfrefer = (struct linepoint*)malloc(sizeof(struct linepoint*));
};

bool linesort(struct linepoint a, struct linepoint b)
{
    struct linepoint* atemp = (struct linepoint*)malloc(sizeof(struct linepoint*));
    atemp = a.selfrefer;
    struct linepoint* btemp = (struct linepoint*)malloc(sizeof(struct linepoint*));
    btemp = b.selfrefer;    
    std::cout << a.selfrefer << " " << b.selfrefer << "\n";
    if(a.coord < b.coord)
    {
        if(a.start == true)
        {
            atemp -> refer -> sloc = btemp;
        }
        if(a.start == false)
        {
            atemp -> refer -> eloc = btemp;
        }
        if(b.start == true)
        {
            btemp -> refer -> sloc = atemp;
        }
        if(b.start == true)
        {
            btemp -> refer -> sloc = atemp;
        }
        std::swap(b.selfrefer -> coord, a.selfrefer -> coord);
        std::swap(b.selfrefer -> start, a.selfrefer -> start);
        std::swap(b.selfrefer -> refer, a.selfrefer -> refer);
        std::swap(b.selfrefer -> selfrefer, a.selfrefer -> selfrefer);
        return false;
    }
    if((a.coord == b.coord) && (a.start > b.start))
    {
        if(a.start == true)
        {
            a.selfrefer -> refer -> sloc = b.selfrefer;
        }
        if(a.start == false)
        {
            a.selfrefer -> refer -> eloc = b.selfrefer;
        }
        if(b.start == true)
        {
            b.selfrefer -> refer -> sloc = a.selfrefer;
        }
        if(b.start == true)
        {
            b.selfrefer -> refer -> sloc = a.selfrefer;
        }
        std::swap(b.selfrefer -> coord, a.selfrefer -> coord);
        std::swap(b.selfrefer -> start, a.selfrefer -> start);
        std::swap(b.selfrefer -> refer, a.selfrefer -> refer);
        std::swap(b.selfrefer -> selfrefer, a.selfrefer -> selfrefer);
        return false;
    }
    return false;
}

int rescan(int point, struct linedata lines[], struct linepoint points[], int scanlength, bool tosort)
{
    output.push_back(point);
    int removed = 0;
    for(int i = 0; i < scanlength; i++)
    {
        if((lines[i].covered == false) && (lines[i].start <= point) && (lines[i].end >= point))
        {
            lines[i].covered = true;
            lines[i].sloc -> coord = INT_MAX - lines[i].start;
            lines[i].eloc -> coord = INT_MAX - lines[i].end;    
            removed = removed + 1;
        }
    }
    if(tosort == true)
    {
        std::sort(points, points+2*scanlength, linesort);
    }
    return removed;
}

int main(void)
{
    int num;
    std::cin >> num;
    int left = 0;
    int track = 0;
    struct linedata lines[num];
    struct linepoint points[2*num];
    struct linepoint* indexor[2*num];
    for(int i = 0; i < num; i++)
    {
        std::cin >> lines[i].start >> lines[i].end;
        points[2*i].coord = lines[i].start;
        points[2*i].start = true;
        points[2*i + 1].coord = lines[i].end;
        points[2*i + 1].start = false;
        lines[i].sloc = &points[2*i];
        lines[i].eloc = &points[2*i + 1];
        points[2*i].selfrefer = &points[2*i];
        points[2*i + 1].selfrefer = &points[2*i + 1];
        left = left + 1;
        if(lines[i].start == lines[i].end)
        {
            left = left - rescan(lines[i].start, lines, points, i + 1, false);
        }
    }

    for(int i = 0; i < 2*num; i++)
    {
        std::cout << i << " " << points[i].coord << " " << points[i].start << " " << sizeof(&points[i]) << " " << &points[i] << "\n";
    }

    std::sort(points, points+2*num, linesort);

    while(left)
    {

        for(int i = 0; i < left; i++)
        {
            if(points[i].start == true)
            {
                std::cout << "loop part 1: " << left << " " << i << "\n";
                for(int i = 0; i < 2*num; i++)
                {
                    std::cout << i << " " << points[i].coord << " " << points[i].start << "\n";
                }
                sleep(1);
                track = track + 1;
                continue;
            }
            if((track != 0) && (points[i].start == false))
            {
                left = left - rescan(points[i].coord, lines, points, num, true);
                std::cout << "loop part 2: " << left << " " << i << "\n";
                for(int i = 0; i < 2*num; i++)
                {
                    std::cout << i << " " << points[i].coord << " " << points[i].start << "\n";
                }
                sleep(1);                
                track = 0;
                continue;
            }
        }
    }
    std::cout << output.size() << "\n";
    for(int i = 0; i < output.size(); i++)
    {
        std::cout << output.at(i) << " ";
    }
    std::cout << "\n";
}

至少可以说,该代码的行为异常。我很确定代码中存在一些未定义的条件,并且libasan和valgrind都抱怨linesort函数中的无效写入。看到无效写入的大小为8,我认为这些写入与我将内存地址交换为交叉引用的linepoint和linedata结构有关。但是,看看它是如何随机出错的,我不知道是什么导致了它的行为。

这是来自几次利比亚战役

4 
4 7
1 3
2 5
5 6
0 4 1 8 0x7ffe0c863880
1 7 0 8 0x7ffe0c863898
2 1 1 8 0x7ffe0c8638b0
3 3 0 8 0x7ffe0c8638c8
4 2 1 8 0x7ffe0c8638e0
5 5 0 8 0x7ffe0c8638f8
6 5 1 8 0x7ffe0c863910
7 6 0 8 0x7ffe0c863928
0x7ffe0c863898 0x7ffe0c863880
0x7ffe0c863898 0x7ffe0c863880
0x7ffe0c8638b0 0x7ffe0c863880
=================================================================
==188113==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x6020000001a0 at pc 0x562db1500d54 bp 0x7ffe0c8635e0 sp 0x7ffe0c8635d0
WRITE of size 8 at 0x6020000001a0 thread T0
    #0 0x562db1500d53 in linesort(linepoint, linepoint) /home/kevin/Downloads/Week3_5.cpp:37
    #1 0x562db1502ac0 in bool __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(linepoint, linepoint)>::operator()<linepoint*, linepoint*>(linepoint*, linepoint*) /usr/include/c++/10/bits/predefined_ops.h:156
    #2 0x562db1502ac0 in void std::__insertion_sort<linepoint*, __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(linepoint, linepoint)> >(linepoint*, linepoint*, __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(linepoint, linepoint)>) /usr/include/c++/10/bits/stl_algo.h:1846
    #3 0x562db1500341 in void std::__final_insertion_sort<linepoint*, __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(linepoint, linepoint)> >(linepoint*, linepoint*, __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(linepoint, linepoint)>) /usr/include/c++/10/bits/stl_algo.h:1891
    #4 0x562db1500341 in void std::__sort<linepoint*, __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(linepoint, linepoint)> >(linepoint*, linepoint*, __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(linepoint, linepoint)>) /usr/include/c++/10/bits/stl_algo.h:1977
    #5 0x562db1500341 in void std::sort<linepoint*, bool (*)(linepoint, linepoint)>(linepoint*, linepoint*, bool (*)(linepoint, linepoint)) /usr/include/c++/10/bits/stl_algo.h:4892
    #6 0x562db1500341 in main /home/kevin/Downloads/Week3_5.cpp:137
    #7 0x7febd76450b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
    #8 0x562db150063d in _start (/home/kevin/Downloads/5+0x363d)

0x6020000001a0 is located 8 bytes to the right of 8-byte region [0x602000000190,0x602000000198)
allocated by thread T0 here:
    #0 0x7febd7abc517 in malloc (/lib/x86_64-linux-gnu/libasan.so.6+0xb0517)
    #1 0x562db14ff7e9 in linepoint::linepoint() /home/kevin/Downloads/Week3_5.cpp:18
    #2 0x562db14ff7e9 in main /home/kevin/Downloads/Week3_5.cpp:112
    #3 0x7febd76450b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)

SUMMARY: AddressSanitizer: heap-buffer-overflow /home/kevin/Downloads/Week3_5.cpp:37 in linesort(linepoint, linepoint)
Shadow bytes around the buggy address:
  0x0c047fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff8000: fa fa 00 fa fa fa 00 fa fa fa 00 fa fa fa 00 fa
  0x0c047fff8010: fa fa 00 fa fa fa 00 fa fa fa 00 fa fa fa 00 fa
  0x0c047fff8020: fa fa 00 fa fa fa 00 fa fa fa 00 fa fa fa 00 fa
=>0x0c047fff8030: fa fa 00 fa[fa]fa 00 fa fa fa 00 fa fa fa 00 fa
  0x0c047fff8040: fa fa 00 fa fa fa 00 fa fa fa 00 fa fa fa 00 fa
  0x0c047fff8050: fa fa 00 fa fa fa 00 fa fa fa 00 fa fa fa 00 fa
  0x0c047fff8060: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8070: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8080: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==188113==ABORTING
5 
2 6
8 19
2 5
1 2
56 981
0 2 1 8 0x7ffdc275be20
1 6 0 8 0x7ffdc275be38
2 8 1 8 0x7ffdc275be50
3 19 0 8 0x7ffdc275be68
4 2 1 8 0x7ffdc275be80
5 5 0 8 0x7ffdc275be98
6 1 1 8 0x7ffdc275beb0
7 2 0 8 0x7ffdc275bec8
8 56 1 8 0x7ffdc275bee0
9 981 0 8 0x7ffdc275bef8
0x7ffdc275be38 0x7ffdc275be20
0x7ffdc275be38 0x7ffdc275be20
0x7ffdc275be50 0x7ffdc275be20
0x7ffdc275be50 0x7ffdc275be38
0x7ffdc275be68 0x7ffdc275be20
0x7ffdc275be68 0x7ffdc275be50
0x7ffdc275be80 0x7ffdc275be20
0x7ffdc275be80 0x7ffdc275be68
=================================================================
==188263==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x602000000260 at pc 0x558343333d54 bp 0x7ffdc275ba80 sp 0x7ffdc275ba70
WRITE of size 8 at 0x602000000260 thread T0
    #0 0x558343333d53 in linesort(linepoint, linepoint) /home/kevin/Downloads/Week3_5.cpp:37
    #1 0x55834333568d in bool __gnu_cxx::__ops::_Val_comp_iter<bool (*)(linepoint, linepoint)>::operator()<linepoint, linepoint*>(linepoint&, linepoint*) /usr/include/c++/10/bits/predefined_ops.h:238
    #2 0x55834333568d in void std::__unguarded_linear_insert<linepoint*, __gnu_cxx::__ops::_Val_comp_iter<bool (*)(linepoint, linepoint)> >(linepoint*, __gnu_cxx::__ops::_Val_comp_iter<bool (*)(linepoint, linepoint)>) /usr/include/c++/10/bits/stl_algo.h:1826
    #3 0x558343335af6 in void std::__insertion_sort<linepoint*, __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(linepoint, linepoint)> >(linepoint*, linepoint*, __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(linepoint, linepoint)>) /usr/include/c++/10/bits/stl_algo.h:1854
    #4 0x558343333341 in void std::__final_insertion_sort<linepoint*, __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(linepoint, linepoint)> >(linepoint*, linepoint*, __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(linepoint, linepoint)>) /usr/include/c++/10/bits/stl_algo.h:1891
    #5 0x558343333341 in void std::__sort<linepoint*, __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(linepoint, linepoint)> >(linepoint*, linepoint*, __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(linepoint, linepoint)>) /usr/include/c++/10/bits/stl_algo.h:1977
    #6 0x558343333341 in void std::sort<linepoint*, bool (*)(linepoint, linepoint)>(linepoint*, linepoint*, bool (*)(linepoint, linepoint)) /usr/include/c++/10/bits/stl_algo.h:4892
    #7 0x558343333341 in main /home/kevin/Downloads/Week3_5.cpp:137
    #8 0x7f4b800a50b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
    #9 0x55834333363d in _start (/home/kevin/Downloads/5+0x363d)

0x602000000260 is located 8 bytes to the right of 8-byte region [0x602000000250,0x602000000258)
allocated by thread T0 here:
    #0 0x7f4b8051c517 in malloc (/lib/x86_64-linux-gnu/libasan.so.6+0xb0517)
    #1 0x5583433327e9 in linepoint::linepoint() /home/kevin/Downloads/Week3_5.cpp:18
    #2 0x5583433327e9 in main /home/kevin/Downloads/Week3_5.cpp:112
    #3 0x7f4b800a50b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)

SUMMARY: AddressSanitizer: heap-buffer-overflow /home/kevin/Downloads/Week3_5.cpp:37 in linesort(linepoint, linepoint)
Shadow bytes around the buggy address:
  0x0c047fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff8000: fa fa 00 fa fa fa 00 fa fa fa 00 fa fa fa 00 fa
  0x0c047fff8010: fa fa 00 fa fa fa 00 fa fa fa 00 fa fa fa 00 fa
  0x0c047fff8020: fa fa 00 fa fa fa 00 fa fa fa 00 fa fa fa 00 fa
  0x0c047fff8030: fa fa 00 fa fa fa 00 fa fa fa 00 fa fa fa 00 fa
=>0x0c047fff8040: fa fa 00 fa fa fa 00 fa fa fa 00 fa[fa]fa 00 fa
  0x0c047fff8050: fa fa 00 fa fa fa 00 fa fa fa 00 fa fa fa 00 fa
  0x0c047fff8060: fa fa 00 fa fa fa 00 fa fa fa 00 fa fa fa 00 fa
  0x0c047fff8070: fa fa 00 fa fa fa 00 fa fa fa fa fa fa fa fa fa
  0x0c047fff8080: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8090: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==188263==ABORTING

我已经使用了g ++ 10,并且-O2标志已打开。我在Ubuntu 20.04上运行。 我将对此有任何帮助或指导。再一次,我对C ++经验不足,可能做的事情非常错误。

评论