Memory leaks

[Dr.Fuzzy]

Παίδες στον παρακάτω απόσπασμα κώδικα (τον έχω πετσοκόψει επίτηδες) έχω τρία μεγάλα memory leaks λόγω του Point2d *point2d = new Point2d(x); στην InsertSite() και του QuadEdge *ql = new QuadEdge στην MakeEdge() που δεν γίνονταi deallocated, όπως φαίνεται και στο valgrind report. Μπορεί κάποιος να βοηθήσει με το memory deallocation (σε ποια σημεία και πως τα delete); Αν χρειάζεστε όλο τον κώδικα pm me να τον στείλω.

Quote

delk@Lyapunov:~/Desktop/delaunay$ valgrind --tool=memcheck --leak-check=yes ./delaunay -n 80000
==24661== Memcheck, a memory error detector
==24661== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==24661== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==24661== Command: ./delaunay -n 80000
==24661== 
==24661== 
==24661== HEAP SUMMARY:
==24661==     in use at exit: 25,600,336 bytes in 320,003 blocks
==24661==   total heap usage: 320,108 allocs, 105 frees, 25,680,724 bytes allocated
==24661== 
==24661== 104 bytes in 1 blocks are possibly lost in loss record 4 of 10
==24661==    at 0x4C3045A: operator new(unsigned long) (vg_replace_malloc.c:344)
==24661==    by 0x10D764: MakeEdge() (quadedge.cpp:14)
==24661==    by 0x10D931: Subdivision::Subdivision(Point2d const&, Point2d const&, Point2d const&) (quadedge.cpp:56)
==24661==    by 0x10C738: __static_initialization_and_destruction_0(int, int) (test.cpp:58)
==24661==    by 0x10C76B: _GLOBAL__sub_I_program (test.cpp:378)
==24661==    by 0x10EC0C: __libc_csu_init (in /home/delk/Desktop/delaunay/delaunay)
==24661==    by 0x5EE4B27: (below main) (libc-start.c:266)
==24661== 
==24661== 104 bytes in 1 blocks are possibly lost in loss record 5 of 10
==24661==    at 0x4C3045A: operator new(unsigned long) (vg_replace_malloc.c:344)
==24661==    by 0x10D764: MakeEdge() (quadedge.cpp:14)
==24661==    by 0x10D959: Subdivision::Subdivision(Point2d const&, Point2d const&, Point2d const&) (quadedge.cpp:58)
==24661==    by 0x10C738: __static_initialization_and_destruction_0(int, int) (test.cpp:58)
==24661==    by 0x10C76B: _GLOBAL__sub_I_program (test.cpp:378)
==24661==    by 0x10EC0C: __libc_csu_init (in /home/delk/Desktop/delaunay/delaunay)
==24661==    by 0x5EE4B27: (below main) (libc-start.c:266)
==24661== 
==24661== 104 bytes in 1 blocks are possibly lost in loss record 6 of 10
==24661==    at 0x4C3045A: operator new(unsigned long) (vg_replace_malloc.c:344)
==24661==    by 0x10D764: MakeEdge() (quadedge.cpp:14)
==24661==    by 0x10D99F: Subdivision::Subdivision(Point2d const&, Point2d const&, Point2d const&) (quadedge.cpp:61)
==24661==    by 0x10C738: __static_initialization_and_destruction_0(int, int) (test.cpp:58)
==24661==    by 0x10C76B: _GLOBAL__sub_I_program (test.cpp:378)
==24661==    by 0x10EC0C: __libc_csu_init (in /home/delk/Desktop/delaunay/delaunay)
==24661==    by 0x5EE4B27: (below main) (libc-start.c:266)
==24661== 
==24661== 639,968 bytes in 79,996 blocks are possibly lost in loss record 8 of 10
==24661==    at 0x4C3045A: operator new(unsigned long) (vg_replace_malloc.c:344)
==24661==    by 0x10E1D2: Subdivision::InsertSite(Point2d const&) (quadedge.cpp:198)
==24661==    by 0x10B519: getArguments(int, char**) (test.cpp:150)
==24661==    by 0x10AFE9: main (test.cpp:61)
==24661== 
==24661== 8,317,608 bytes in 79,977 blocks are possibly lost in loss record 9 of 10
==24661==    at 0x4C3045A: operator new(unsigned long) (vg_replace_malloc.c:344)
==24661==    by 0x10D764: MakeEdge() (quadedge.cpp:14)
==24661==    by 0x10E1C4: Subdivision::InsertSite(Point2d const&) (quadedge.cpp:197)
==24661==    by 0x10B519: getArguments(int, char**) (test.cpp:150)
==24661==    by 0x10AFE9: main (test.cpp:61)
==24661== 
==24661== 16,642,080 bytes in 160,020 blocks are possibly lost in loss record 10 of 10
==24661==    at 0x4C3045A: operator new(unsigned long) (vg_replace_malloc.c:344)
==24661==    by 0x10D764: MakeEdge() (quadedge.cpp:14)
==24661==    by 0x10DA76: Connect(Edge*, Edge*) (quadedge.cpp:81)
==24661==    by 0x10E251: Subdivision::InsertSite(Point2d const&) (quadedge.cpp:203)
==24661==    by 0x10B519: getArguments(int, char**) (test.cpp:150)
==24661==    by 0x10AFE9: main (test.cpp:61)
==24661== 
==24661== LEAK SUMMARY:
==24661==    definitely lost: 0 bytes in 0 blocks
==24661==    indirectly lost: 0 bytes in 0 blocks
==24661==      possibly lost: 25,599,968 bytes in 319,996 blocks
==24661==    still reachable: 368 bytes in 7 blocks
==24661==         suppressed: 0 bytes in 0 blocks
==24661== Reachable blocks (those to which a pointer was found) are not shown.
==24661== To see them, rerun with: --leak-check=full --show-leak-kinds=all
==24661== 
==24661== For lists of detected and suppressed errors, rerun with: -s
==24661== ERROR SUMMARY: 6 errors from 6 contexts (suppressed: 0 from 0)

QuadEdge.h

class Edge {
    friend QuadEdge;
  private:
    ...
  public:
    ...
};

class QuadEdge {
    friend Edge *MakeEdge();
  private:
    Edge e[4];
  public:
    QuadEdge();
};

QuadEdge.cpp

Edge* MakeEdge() {
	QuadEdge *ql = new QuadEdge;
	return ql->e;
}

Edge* Connect(Edge* a, Edge* b) {
	Edge* e = MakeEdge();
	...
	return e;
}

void Subdivision::InsertSite(const Point2d& x) {
    ...
	Edge* base = MakeEdge();
	Point2d *point2d = new Point2d(x);
	base->EndPoints(e->Org(), point2d);
	Splice(base, e);
	startingEdge = base;
	do {
		base = Connect(e, base->Sym());
		e = base->Oprev();
	} while (e->Lnext() != startingEdge);
    ...
}

 

Επεξ/σία 16 Απριλίου 2020 από Dr.Fuzzy

[kaliakman]

Δεν μπορώ να καταλάβω τι γίνεται χωρίς και άλλο κώδικα.

Για παράδειγμα η connect τι ακριβώς κάνει? Αν εκεί πηγαίνεις σε άλλο edge προφανώς χάνεις την αναφορά στο edge που έκανες new και προκύπτει memory leak. Το e που δημιουργείς έχει μέσα το b? Επίσης το newPoint γιατί το φτιάχνεις και δεν περνάς απευθείας &x στην Endpoints? 

 

Γενικότερα αν είναι κυκλική δομή θέλει προσοχή για να αποφύγεις double delete 

Επεξ/σία 16 Απριλίου 2020 από kaliakman

[Dr.Fuzzy]

4 hours ago, kaliakman said:

Δεν μπορώ να καταλάβω τι γίνεται χωρίς και άλλο κώδικα.

Για παράδειγμα η connect τι ακριβώς κάνει? Αν εκεί πηγαίνεις σε άλλο edge προφανώς χάνεις την αναφορά στο edge που έκανες new και προκύπτει memory leak. Το e που δημιουργείς έχει μέσα το b? Επίσης το newPoint γιατί το φτιάχνεις και δεν περνάς απευθείας &x στην Endpoints? 

Γενικότερα αν είναι κυκλική δομή θέλει προσοχή για να αποφύγεις double delete 

Δες την connect()

Edge* Connect(Edge* a, Edge* b) {
	Edge* e = MakeEdge();
	Splice(e, a->Lnext());
	Splice(e->Sym(), b);
	e->EndPoints(a->Dest(), b->Org());
	return e;
}

και μέρος της Splice()

void Splice(Edge* a, Edge* b) {
	Edge* alpha = a->Onext()->Rot();
  	...
	Edge* t4 = alpha->Onext();
	...
	alpha->next = t3;
	...
}

αν δε βγάζεις άκρη πες μου αν θες να σου στείλω τον κώδικα όλοκληρο.

Επεξ/σία 16 Απριλίου 2020 από Dr.Fuzzy

[Kercyn]

Δεν έχω χρόνο τώρα να το κοιτάξω προσεκτικά, αλλά να τολμήσω να προτείνω smart pointers ή δεν έχει τέτοια;

[Dr.Fuzzy]

16 minutes ago, Kercyn said:

Δεν έχω χρόνο τώρα να το κοιτάξω προσεκτικά, αλλά να τολμήσω να προτείνω smart pointers ή δεν έχει τέτοια;

Δυστυχώς boost library δεν...Απο περιέργεια βέβαια δοκίμασα αλλά κολλούσε το πρόγραμμα και δεν το έψαξα και περισσότερο (μάλλον δεν παίζουν καλά μαζι smart pointers με κανονικούς).

Συγκεκριμένα:

    //Point2d *point2d = new Point2d(x);
    boost::shared_ptr<Point2d> point2d_ptr( new Point2d );
    Point2d *point2d = point2d_ptr.get();
    base->EndPoints(e->Org(), point2d);

 

Επεξ/σία 16 Απριλίου 2020 από Dr.Fuzzy

[Kercyn]

Δεν είναι boost, είναι από C++11. Γενικά αν μπορείς, καλό θα ήταν να χρησιμοποιείς smart pointers. Κάνουν το ίδιο πράγμα με μεγαλύτερη ασφάλεια και πρακτικά δεν έχουν παραπάνω overhead από "κανονικούς" pointers. Έχουν ένα κάποιο learning curve, αλλά once you go smart you never go back. Ενδεικτικά ένα βίντεο. Αν θες ψάξε και του Herb Sutter άρθρα ή βίντεο σχετικά με smart pointers και exception safety.

 

[Dr.Fuzzy]

OK, νόμιζα smart pointers στη boost library. Έχω μείνει λίγο πίσω...

Πάντως και C++11 std::shared_ptr στο προηγούμενο πάλι κολλάει.

Επεξ/σία 16 Απριλίου 2020 από Dr.Fuzzy

[NewProject]

5 ώρες πριν, Dr.Fuzzy είπε

Δυστυχώς boost library δεν...Απο περιέργεια βέβαια δοκίμασα αλλά κολλούσε το πρόγραμμα και δεν το έψαξα και περισσότερο (μάλλον δεν παίζουν καλά μαζι smart pointers με κανονικούς).

Συγκεκριμένα:

    //Point2d *point2d = new Point2d(x);
    boost::shared_ptr<Point2d> point2d_ptr( new Point2d );
    Point2d *point2d = point2d_ptr.get();
    base->EndPoints(e->Org(), point2d);

Δεν κάνεις κάτι με τον shared pointer που έφιαξες εδώ. 

Θα σου πρότεινα να πας κατευθείαν σε C++14 και οτι αντικείμενο έχεις:

class CSomething
{
  int m_filed;
}

using CSomethingPtr = std::shared_ptr<CSomething*>();


// Usage:
CSomethingPtr Add(CSomethingPtr a, CSomethingPtr b);
CSomethingPtr a = ...;
CSomethingPtr b = ...;

auto result = Add(a, b)

( ενδεικτικά τα παραπάνω )

[Dr.Fuzzy]

5 minutes ago, NewProject said:

Θα σου πρότεινα να πας κατευθείαν σε C++14

Δυστυχώς ούτε C++14 αλλά ούτε C++11 υποστηρίζεται! 
 

[NewProject]

22 ώρες πριν, Dr.Fuzzy είπε

 

class Edge {
    friend QuadEdge; // ???
  private:
    ...
  public:
    ...
};

class QuadEdge {
    friend Edge *MakeEdge(); // ???
  private:
    Edge e[4];
  public:
    QuadEdge();
};

 

 

Ή φτιάξε δικό σου shared pointer implementation ή χρησιμοποίησε consistently κάποιο design pattern (ή και τα 2).

[Dr.Fuzzy]

13 hours ago, NewProject said:

Ή φτιάξε δικό σου shared pointer implementation ή χρησιμοποίησε consistently κάποιο design pattern (ή και τα 2).

Η συγκεκριμένη υλοποίηση του quad tree που χρησιμοποιώ είναι από Graphics Gems IV (http://www.karlchenofhell.org/cppswp/lischinski.pdf) και ο original κώδικας υπάρχει εδώ https://github.com/erich666/GraphicsGems/tree/master/gemsiv/delaunay και είναι στην ουσία μια υλοποίηση σε C++ του quad tree pseudocode στο κλασσικό paper των Guibas and Stolfi.

Όπως καταλαβαίνεις ο σκοπός μου εδώ αρχικά ήταν να το πάρω έτοιμο για να δοκιμάσω αλλα πράγματα που με ενδιαφέρουν και όχι το coding καθαυτό (δεν είμαι software engineer). Βεβαίως ακόμα και έτσι πολλά κομμάτια τα έγραψα από την αρχή όπως πχ, το visualization που αν δεις στο κώδικα καλεί SGI IRIS GL libraries όποτε το έκανα rewrite σε OpenGL, κλπ, κλπ.

Δυστυχώς στην πορεία ανακάλυψα τα memory leaks διότι το triangulation που χρησιμοποιεί το quad tree έκανε freeze για περισσότερα από 90000 σημεία και έτσι φτάσαμε εδώ που είμαστε...(πρακτικά να προσπαθώ να διορθώσω τον κώδικα του Lischinski στο βιβλίο!)

Επεξ/σία 17 Απριλίου 2020 από Dr.Fuzzy

[xristos97]

Εγώ βλέπω έχει πολλά new χωρίς delete. Για την makeedge δοκίμασε να έχεις ένα vector που κρατάει τα pointers και στο τέλος να τα κάνεις όλα delete. 

[Dr.Fuzzy]

6 hours ago, xristos97 said:

Εγώ βλέπω έχει πολλά new χωρίς delete.

5 είναι όλα απο τα οποία , το ένα στην MakeEdge, και το άλλο στην InsertSite που δημιουργούν τα mem leaks. Τα υπόλοιπα 3 στoν Subdivision constructor γίνονται delete στον destructor (στον δικό μου modified code, οχι στον original code του link).

Quote

Για την makeedge δοκίμασε να έχεις ένα vector που κρατάει τα pointers και στο τέλος να τα κάνεις όλα delete.

Για δώσε ενα παράδειγμα.

Επεξ/σία 17 Απριλίου 2020 από Dr.Fuzzy

[xristos97]

4 ώρες πριν, Dr.Fuzzy είπε

5 είναι όλα απο τα οποία , το ένα στην MakeEdge, και το άλλο στην InsertSite που δημιουργούν τα mem leaks. Τα υπόλοιπα 3 στoν Subdivision constructor γίνονται delete στον destructor (στον δικό μου modified code, οχι στον original code του link).

Για δώσε ενα παράδειγμα.

std::vector<QuadEdge *> new_quadEdges;
Edge* MakeEdge() {
	QuadEdge *ql = new QuadEdge;
  	new_quadEdges.push_back(ql);
	return ql->e;
}

Και όταν δεν τα χρειάζεσαι τα περνάς μια φορά και τα κάνεις delete. Ισως να υπάρχουν και καλύτεροι τρόποι να το κάνεις, εγώ αυτο σκέφτηκα τώρα.

Επεξ/σία 17 Απριλίου 2020 από xristos97

[Dr.Fuzzy]

1 hour ago, xristos97 said:

Και όταν δεν τα χρειάζεσαι τα περνάς μια φορά και τα κάνεις delete.

Κάτσε δεν νομίζω οτι έχω καταλάβει. Κάνω το new_quadEdges delete; Που;