memory corruption w std::vector::push_back

0

Dzień dobry.

Mam problem z wektorem. Z niewiadomych mi przyczyn powoduje on błąd memory corruption, kiedy używam motody push_back(element).

Załączę fragment kodu:

for (int j = 0; j < trees.size(); j++)
{
    if (findV(trees[j], edges[i].A) == true && findV(trees[j], edges[i].B) == true)
    {
        found = true;
        break;
    }

    if (findV(trees[j], edges[i].A) == true || findV(trees[j], edges[i].B) == true)
    {
        trees[j].push_back(edges[i]);
        found = true;

        index = j;
        break;
    }
}

Błąd występuje w 11 linii.

Zmienne w funkcji:

vector<Edge> & edges // parametr funkcji
vector<vector<Edge>> trees; // zmienna lokalna

Co może powodować taki błąd?

Dzięki
M.

1

Daj całość kodu, ponieważ błąd jest w innym fragmencie kodu.

0

https://pastebin.pl/view/9b035cfd

Wklejka ważna 1 dzień, proszę nie kopiować na forum ;)

Błąd w linii 310
PS

Link do pliku z danymi https://bit.ly/2Ajlq6V

0

To jest dużo kodu; mógłbyś przygotować MRE?

Edit: tak na oko - robisz trees[j].push_back(edges[i]);, a gdzie inicjujesz trees[j]?

0

W 322 linii. Z tym MRE to będzie mały problem. Ale zobaczę co da się zrobić

0

Zgaduj zgadula: jakaś referencja/coś innego już nie istnieje, wskazuje w próżnię z meteorytami, gdy jest użyta???
Postawa merytoryczna: zobaczyłem to na chmurach.

0

Dostaję jeszcze inne błędy w gdb, jednak program daje się kontynuować:

Program received signal SIGTRAP, Trace/breakpoint trap.
In ?? () ()
#8  0x00405d88 in __gnu_cxx::new_allocator<Edge>::deallocate (this=0x361e1cc, __p=0xcddbc8) at c:/mingw/lib/gcc/mingw32/9.2.0/include/c++/ext/new_allocator.h:128
c:\mingw\lib\gcc\mingw32\9.2.0\include\c++\ext\new_allocator.h:128:3907:beg:0x405d88
At c:\mingw\lib\gcc\mingw32\9.2.0\include\c++\ext\new_allocator.h:128

Nie mam pojęcia o co w tym chodzi. Szukałem na Stacku, ale nic z tego nie rozumiem :(

1

Problemem jest funkcja generateMST która zawiera aż 100 linijek kodu! Podziel to na osobne funkcje, to będzie łatwiej znaleźć błąd. Dodatkowo będziesz mógł bardziej zoptymalizować swój kod.
Najbardziej podejrzana jest tutaj funkcja merge w unionE, w której dokonywany jest zapisu wyniku do kontenera będącego równocześnie jej parametrem.

0

Nie wiem jeszcze czemu się wywala, ale jedno wiem na pewno, implementacja lambdy unionE zawiera błąd. Zobacz:

bool myCompare(const Edge & i, const Edge & j)
{
    return i.weight < j.weight;
};
    auto unionE = [&trees](int i, int j)
    {
        merge(trees[i].begin(), trees[i].end(), trees[j].begin(), trees[j].end(), trees[i].begin(), myCompare);
        trees.erase(trees.begin() + j);
    };

Merge nigdy nie zadziała tak jak oczekujesz, bo użycie myCompare w tym kontekscie jest bez sensu. Funkcja porównania w tym kontekście powinna porównywać krawędzie, a porównuje tylko wagi.

Poza tym jeżeli chodzi o implementację find-union, to poszedłeś na skróty. Implementacja zbioru rozłącznego jest warta nauczenia się i pewnie jakbyś użył odpowiedniego algorytmu to byś nie miał owego problemu..

2
/tmp $ ./a.out
=================================================================
==204207==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7fff8409a259 at pc 0x7f57150c8bbd bp 0x7fff8409a1b0 sp 0x7fff84099958
READ of size 31 at 0x7fff8409a259 thread T0
    #0 0x7f57150c8bbc  (/lib64/libasan.so.5+0x67bbc)
    #1 0x7f5714fb370b in std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::basic_string(char const*, std::allocator<char> const&) (/lib64/libstdc++.so.6+0x14b70b)
    #2 0x405254 in readName(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >&) (/tmp/a.out+0x405254)
    #3 0x4063a3 in readCities(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >&, std::vector<City, std::allocator<City> >&) (/tmp/a.out+0x4063a3)
    #4 0x40399b in main (/tmp/a.out+0x40399b)
    #5 0x7f57141fe1a2 in __libc_start_main (/lib64/libc.so.6+0x271a2)
    #6 0x4035ad in _start (/tmp/a.out+0x4035ad)

Address 0x7fff8409a259 is located in stack of thread T0 at offset 89 in frame
    #0 0x404c82 in readName(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >&) (/tmp/a.out+0x404c82)

  This frame has 6 object(s):
    [32, 33) '<unknown>'
    [48, 49) '<unknown>'
    [64, 89) 'data' (line 131) <== Memory access at offset 89 overflows this variable
    [128, 160) 'part' (line 133)
    [192, 224) '<unknown>'
    [256, 288) 'test' (line 155)
HINT: this may be a false positive if your program uses some custom stack unwind mechanism, swapcontext or vfork
      (longjmp and C++ exceptions *are* supported)
SUMMARY: AddressSanitizer: stack-buffer-overflow (/lib64/libasan.so.5+0x67bbc) 
Shadow bytes around the buggy address:
  0x10007080b3f0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007080b400: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007080b410: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007080b420: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007080b430: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x10007080b440: f1 f1 f1 f1 01 f2 01 f2 00 00 00[01]f2 f2 f2 f2
  0x10007080b450: 00 00 00 00 f2 f2 f2 f2 f8 f8 f8 f8 f2 f2 f2 f2
  0x10007080b460: 00 00 00 00 f3 f3 f3 f3 00 00 00 00 00 00 00 00
  0x10007080b470: 00 00 00 00 f1 f1 f1 f1 f1 f1 00 00 00 00 f2 f2
  0x10007080b480: f2 f2 00 00 00 00 f2 f2 f2 f2 00 00 00 00 00 00
  0x10007080b490: f3 f3 f3 f3 00 00 00 00 00 00 00 00 f1 f1 f1 f1
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
==204207==ABORTING
0

wartość zwracana z lambdy isMSTComplete używasz jako indeks do wektora a w niej taki kwiatek return -1;

1
TomaszLiMoon napisał(a):

Najbardziej podejrzana jest tutaj funkcja merge w unionE, w której dokonywany jest zapisu wyniku do kontenera będącego równocześnie jej parametrem.

To też racja. The behavior is undefined if the destination range overlaps either of the input ranges (the input ranges may overlap each other). https://en.cppreference.com/w/cpp/algorithm/merge

0

Jeszcze może być błąd w erase. Podaję tam iterator do którego dodaję liczbę całkowitą,a to nie jest zwykła tablica i może inaczej obliczać adres jotego elementu. Jak zatem mogę usunąć joty element?

PS. Mieliście rację z tym merge. Tam był problem!

Zastąpiłem unionE przez:

auto unionE = [](vector<vector<Edge>> & tr, int i, int j)
    {
        vector<Edge> newOne;
        auto it = newOne.end();

        it = newOne.insert(it, tr[i].begin(), tr[i].end());
        it = newOne.insert(it, tr[j].begin(), tr[j].end());
        sort(newOne.begin(), newOne.end(), myCompare);

        tr[i] = newOne;
        tr.erase(tr.begin() + j);
    };

I już się nie wywala. Jeszcze nie działa idealnie, ale krok do przodu. Dzięki

0

Weź zaimplementuj to find-union porządnie: https://en.wikipedia.org/wiki/Disjoint-set_data_structure

3

enedil ci dobrze pisze, ale bez wyjaśnien dla początkującego.
U mnie to wygląda tak:

$ clang++ -O1 -g -fsanitize=address buff.cpp -o buff -std=c++17
$ ./buff
=================================================================
==65295==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7ffee5906519 at pc 0x00010a357948 bp 0x7ffee59064b0 sp 0x7ffee5905c70
READ of size 30 at 0x7ffee5906519 thread T0
    #0 0x10a357947 in wrap_strlen (libclang_rt.asan_osx_dynamic.dylib:x86_64h+0x17947)
    #1 0x10a304c09 in std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >::basic_string<std::nullptr_t>(char const*) string:819
    #2 0x10a2fc8bb in readName(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >&) buff.cpp:155
    #3 0x10a2faba3 in readCities(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >&, std::__1::vector<City, std::__1::allocator<City> >&) buff.cpp:213
    #4 0x10a2f9fab in main buff.cpp:57
    #5 0x7fff7168bcc8 in start (libdyld.dylib:x86_64+0x1acc8)

Address 0x7ffee5906519 is located in stack of thread T0 at offset 57 in frame
    #0 0x10a2fc64f in readName(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >&) buff.cpp:124

  This frame has 4 object(s):
    [32, 57) 'data' (line 131) <== Memory access at offset 57 overflows this variable
    [96, 120) 'part' (line 133)
    [160, 184) 'ref.tmp' (line 134)
    [224, 248) 'test' (line 155)

Idąc po kolei wywołania #0 i #1 cię nie interesują, bo to jest standardowa biblioteka.
#2 kieruję cię na fukcję:

string readName(string & str)
{
    if (str.size() < 10)
    {
        // "Pusty str"
        return "";
    }

    char data[25];

    string part = str.substr(0, str.find("\n"));
    strncpy(data, part.substr(0, 24).c_str(), 24);

    bool space = false;

    for (int i = 0; i < 24; i++)
    {
        if (isspace(data[i]))
        {
            if (space == true)
            {
                data[i - 1] = '\0';
                break;
            }

            space = true;
            continue;
        }

        space = false;
    }

    string test = data; // to jest linia 155, gdzie błąd się manifestuje
    return test;
}

Błąd mówi, że jest czytanie poza buforem, a w tym momencie odczytywany jest data.
Przy konwersji char* do std::string, koniec napisu jest oznaczany wartością, zero. Jeśli jej brakuje, to nastąpi próba odczytania poza bufor.

Co to niby ma robić? Czemu tak to strasznie przekombinowałeś?
Te dane są proste do odczytania.

A twój kod się pewnie wykłada dlatego, że pierwsz kolumna tych danych ma więcej znaków niż 20.
Np Baranow (skierniewickie) ma 24 znaki.

Swoją drogą, te dane są dziwne. Z jednej strony jest użyty UTF-8, bo tak zakodowany jest znak °, a polskich znaków nie ma.

0

Dzięki! Po trudach i znojach, program działa! ;)

string readName(string & str)
{
    if (str.size() < 10)
    {
        // "Pusty str"
        return "";
    }

    string part = str.substr(0, str.find("\n"));
    string test = part.substr(0, 24);

    bool space = false;

    for (int i = 0; i < 24; i++)
    {
        if (isspace(test[i]))
        {
            if (space == true)
            {
                test.resize(i - 1);
                break;
            }

            space = true;
            continue;
        }

        space = false;
    }

    return test;
}
     if (index != -1) /* do poprawy */
            for (int j = 0; j < trees.size(); j++)
                if (findV(trees[j], edges[i].A) == true || findV(trees[j], edges[i].B) == true)
                    if (j != index)
                    {
                        unionE(trees, index, j);
                        break;
                    }

Danke schein ;)

Co prawda pracuje przez kilkadziesiąt (20, 30) sekund, ale przy tej liczbie danych (ok 3'000'000 krawędzi) to chyba normalne. Dzięki
M

0

Tu masz bardziej strawne wczytywanie tych danych:
https://wandbox.org/permlink/UvahtKFobA5gXHrI

std::istream& loadFixedSize(std::istream& in, std::string& s, size_t n)
{
    s.clear();
    s.reserve(n);
    auto it = std::istreambuf_iterator<char>(in);
    std::copy_n(it, n, std::back_inserter(s));
    ++it;
    return in;
}

1 użytkowników online, w tym zalogowanych: 0, gości: 1