Intersection between valid and invalid polygon leaks

[sgillies]

Big time. Output of valgrind:

==26636== 15,360 (5,520 direct, 9,840 indirect) bytes in 60 blocks are definitely lost in loss record 69 of 77
==26636==    at 0x4021B59: operator new(unsigned) (vg_replace_malloc.c:163)
==26636==    by 0x500997A: geos::geomgraph::EdgeIntersectionList::createSplitEdge(geos::geomgraph::EdgeIntersection*, geos::geomgraph::EdgeIntersection*) (EdgeIntersectionList.cpp:176)
==26636==    by 0x5009AD8: geos::geomgraph::EdgeIntersectionList::addSplitEdges(std::vector<geos::geomgraph::Edge*, std::allocator<geos::geomgraph::Edge*> >*) (EdgeIntersectionList.cpp:122)
==26636==    by 0x500E0B9: geos::geomgraph::GeometryGraph::computeSplitEdges(std::vector<geos::geomgraph::Edge*, std::allocator<geos::geomgraph::Edge*> >*) (GeometryGraph.cpp:160)
==26636==    by 0x505BFE4: geos::operation::overlay::OverlayOp::computeOverlay(geos::operation::overlay::OverlayOp::OpCode) (OverlayOp.cpp:673)
==26636==    by 0x505C428: geos::operation::overlay::OverlayOp::getResultGeometry(geos::operation::overlay::OverlayOp::OpCode) (OverlayOp.cpp:186)
==26636==    by 0x505CD07: geos::operation::overlay::OverlayOp::overlayOp(geos::geom::Geometry const*, geos::geom::Geometry const*, geos::operation::overlay::OverlayOp::OpCode) (OverlayOp.cpp:92)
==26636==    by 0x4F77156: std::auto_ptr<geos::geom::Geometry> geos::geom::BinaryOp<geos::operation::overlay::overlayOp>(geos::geom::Geometry const*, geos::geom::Geometry const*, geos::operation::overlay::overlayOp) (OverlayOp.h:338)
==26636==    by 0x4F73387: GEOSIntersection (geos_c.cpp:820)
==26636==    by 0x4F66A16: ffi_call_SYSV (sysv.S:60)
==26636==    by 0x4F668A3: ffi_call (ffi.c:221)
==26636==    by 0x4F61203: _CallProc (callproc.c:668)

[denisem]

Sean - can you provide more info (or a test program) on how you created an invalid polygon? I've tried a couple of the interfaces, but keep getting exceptions because as the class is building, it detects the invalid polygon and the returned pointer is null.

I was trying to create a polygon that was simple, no internal rings, and the shell was not closed. Thanks, Denise

[sgillies]

I found the leak running valgrind over Shapely's tests, this one in particular:

​http://trac.gispython.org/lab/browser/Shapely/trunk/tests/invalid_intersection.txt

You may not be able to run it, but you can see the geoms i used. This bug smells like it could be related to the one you fixed.

[denisem]

Thanks for the info, I'll give this a try later in the week.

[denisem]

I have confirmed that the leak still exists even with the memory leak that was fixed as part of issue #169, and trunk from mid Sept. I will continue to investigate.

[denisem]

I have a possible fix for this issue.

Background:

• the memory leak is occurring because the edges allocated and saved in the edge list is not being deallocated when one of the polygons is invalid.
• the leak is multiple Edge objects (92 bytes each) owned by OverlayOp::edgeList of type geomgraph::EdgeList.
• nothing specific in OverlayOp class is being done to clean up edgeList, since its not a pointer
• EdgeList is a vector of pointers to Edge objects. nothing specific in EdgeList class to clean up the Edge objects (since its a vector<Edge *> instead of a vector<Edge>, the Edge objects need to be specifically deleted).

I attempted to add the cleanup within the EdgeList destructor, but in the success case the OverlapOp::edgeList becomes owned (shared?) by a geomgraph::PlanarGraph object; therefore this fix caused problems when the edgeList is deleted twice.

This sharing (?) of ownership takes place in source/operation/overlay/OverlayOp.cpp, around line 708 at the call:

graph.addEdges(edgeList.getEdges());

In the failure case, an exception was thrown from the nv.checkValid() call a few lines before, and ownership was never transferred and Edge objects from edgeList were not cleaned up.

Therefore, the solution was to:

• catch the throw from nv.checkValid,
• explicitly delete the Edge objects, clear the vector, and
• re-throw the exception.

A new method EdgeList::clearList was created as at this point the edgeList is part of the EdgeList class, and further memory leaks can use this code too, without making changes to the destructor.

Further cleanup was required in OverlayOp.cpp around #ifdef GEOS_DEBUG_VALIDATION so there weren't two try / catch blocks doing the same thing, one that prints debug messages and one that doesn't.

This was tested on svn trunk from Oct 23rd.

Ran tests:

• geos_unit - 445 cases passed (0 failed)
• Shapely invalid intersection, as documented ​http://trac.gispython.org/lab/browser/Shapely/trunk/tests/invalid_intersection.txt
• valid intersection using Shapely (modified previous test).

For the Shapely tests ran with valgrind and confirmed the original memory leak is gone and that there are no new memory errors.

Attaching the files that were patched.

[denisem]

Working copy of OverlayOp.cpp

[pramsey]

Denise, I've committed these, but I just thought of one last test... could you test your fix with *two* invalid polygons?

[pramsey]

Committed to branches/3.0 at r2219 and trunk at r2220.

[denisem]

Thanks Paul. Tested with two invalid polygons, no leaks from GEOS code. Script is attached.

[denisem]

Tested 2 invalid polygons with the fix.