access violation in update_discarded(...)

classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|

access violation in update_discarded(...)

Volker Schöch

Hi,

 

we have seen an access violation deep inside boost geometry. We are still working on a simple reproduction, which may take while. In the meantime, maybe you have some idea what went wrong, or some suggestion how to avoid this situation?

 

Here is where it happened:

 

template<typename Turns, typename Operations>

inline void update_discarded(Turns& turn_points, Operations& operations)

{

    // Vice-versa, set discarded to true for discarded operations;

    // AND set discarded points to true

    for (typename boost::range_iterator<Operations>::type it = boost::begin(operations);

         it != boost::end(operations);

         ++it)

    {

        if (turn_points[it->index].discarded) <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< access violation

        {

            it->discarded = true;

        }

        else if (it->discarded)

        {

            turn_points[it->index].discarded = true;

        }

    }

}

 

Please find the callstack attached.

 

Regards

   Volker

--
Volker Schöch | [hidden email]
Senior Software Engineer


We are looking for C++ Developers: http://www.think-cell.com/career

think-cell Software GmbH http://www.think-cell.com
Chausseestr. 8/E phone / fax +49 30 666473-10 / -19
10115 Berlin, Germany US phone / fax +1 800 891 8091 / +1 212 504 3039
Amtsgericht Berlin-Charlottenburg, HRB 85229 | European Union VAT Id DE813474306
Directors: Dr. Markus Hannebauer, Dr. Arno Schödl


_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry

callstack.txt (6K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: access violation in update_discarded(...)

Volker Schöch

Hi,

 

Unfortunately I have not hear from you in this regard. It seems that I still cannot reliably reproduce the issue, but when it occurs, it occurs in the following scenario. Apparently, something is broken in your memory management:

 

{      // RT#8837

       _intPolygon polygonA;

       boost::geometry::read_wkt("MULTIPOLYGON(((488 2035,527 2035,527 2093,488 2093)))", polygonA); // does not throw

 

       _intRect rectB;

       boost::geometry::read_wkt("BOX(417 2064,597 2064)", rectB); // does not throw

 

       _intPolygon polygonC;

       boost::geometry::difference(polygonA, rectB, polygonC); // ACCESS VIOLATION

}

 

Maybe you could make an effort and step through this simple example once to see if everything works as expected?

 

I understand that the box and/or the polygon may not conform to all requirements (not spike-free etc.) but in any case, IMO the geometry library should not crash with a memory fault.

 

As always, my points are based on int and my polygons are counter-clockwise and not closed.

 

Regards

   Volker

 

 

--
Volker Schöch | [hidden email]
Senior Software Engineer


We are looking for C++ Developers: http://www.think-cell.com/career

From: Geometry [mailto:[hidden email]] On Behalf Of Volker Schöch
Sent: Freitag, 17. Oktober 2014 16:20
To: Boost.Geometry library mailing list ([hidden email])
Subject: [geometry] access violation in update_discarded(...)

 

Hi,

 

we have seen an access violation deep inside boost geometry. We are still working on a simple reproduction, which may take while. In the meantime, maybe you have some idea what went wrong, or some suggestion how to avoid this situation?

 

Here is where it happened:

 

template<typename Turns, typename Operations>

inline void update_discarded(Turns& turn_points, Operations& operations)

{

    // Vice-versa, set discarded to true for discarded operations;

    // AND set discarded points to true

    for (typename boost::range_iterator<Operations>::type it = boost::begin(operations);

         it != boost::end(operations);

         ++it)

    {

        if (turn_points[it->index].discarded) <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< access violation

        {

            it->discarded = true;

        }

        else if (it->discarded)

        {

            turn_points[it->index].discarded = true;

        }

    }

}

 

Please find the callstack attached.

 

Regards

   Volker

--
Volker Schöch | [hidden email]
Senior Software Engineer


We are looking for C++ Developers: http://www.think-cell.com/career


think-cell Software GmbH

http://www.think-cell.com

Chausseestr. 8/E

phone / fax

+49 30 666473-10 / -19

10115 Berlin, Germany

US phone / fax

+1 800 891 8091 / +1 212 504 3039

Amtsgericht Berlin-Charlottenburg, HRB 85229 | European Union VAT Id DE813474306

Directors: Dr. Markus Hannebauer, Dr. Arno Schödl

 


_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|

Re: access violation in update_discarded(...)

Menelaos Karavelas
Hi Volker.

On 27/10/2014 07:39 μμ, Volker Schöch wrote:

Hi,

 

Unfortunately I have not hear from you in this regard. It seems that I still cannot reliably reproduce the issue, but when it occurs, it occurs in the following scenario. Apparently, something is broken in your memory management:

 

{      // RT#8837

       _intPolygon polygonA;

       boost::geometry::read_wkt("MULTIPOLYGON(((488 2035,527 2035,527 2093,488 2093)))", polygonA); // does not throw

 

       _intRect rectB;

       boost::geometry::read_wkt("BOX(417 2064,597 2064)", rectB); // does not throw

 

       _intPolygon polygonC;

       boost::geometry::difference(polygonA, rectB, polygonC); // ACCESS VIOLATION

}

 

Maybe you could make an effort and step through this simple example once to see if everything works as expected?

 

I understand that the box and/or the polygon may not conform to all requirements (not spike-free etc.) but in any case, IMO the geometry library should not crash with a memory fault.

 

As always, my points are based on int and my polygons are counter-clockwise and not closed.

 


Please see the attached program and its output, which works for me.
Do you think you can reproduce the problem in a standalone program?

All the best,

- m.

Regards

   Volker

 

 

--
Volker Schöch | [hidden email]
Senior Software Engineer


We are looking for C++ Developers: http://www.think-cell.com/career

From: Geometry [[hidden email]] On Behalf Of Volker Schöch
Sent: Freitag, 17. Oktober 2014 16:20
To: Boost.Geometry library mailing list ([hidden email])
Subject: [geometry] access violation in update_discarded(...)

 

Hi,

 

we have seen an access violation deep inside boost geometry. We are still working on a simple reproduction, which may take while. In the meantime, maybe you have some idea what went wrong, or some suggestion how to avoid this situation?

 

Here is where it happened:

 

template<typename Turns, typename Operations>

inline void update_discarded(Turns& turn_points, Operations& operations)

{

    // Vice-versa, set discarded to true for discarded operations;

    // AND set discarded points to true

    for (typename boost::range_iterator<Operations>::type it = boost::begin(operations);

         it != boost::end(operations);

         ++it)

    {

        if (turn_points[it->index].discarded) <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< access violation

        {

            it->discarded = true;

        }

        else if (it->discarded)

        {

            turn_points[it->index].discarded = true;

        }

    }

}

 

Please find the callstack attached.

 

Regards

   Volker

--
Volker Schöch | [hidden email]
Senior Software Engineer


We are looking for C++ Developers:http://www.think-cell.com/career


think-cell Software GmbH

http://www.think-cell.com

Chausseestr. 8/E

phone / fax

+49 30 666473-10 / -19

10115 Berlin, Germany

US phone / fax

+1 800 891 8091 / +1 212 504 3039

Amtsgericht Berlin-Charlottenburg, HRB 85229 | European Union VAT Id DE813474306

Directors: Dr. Markus Hannebauer, Dr. Arno Schödl

 



_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry


_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry

volker_memory.out (194 bytes) Download Attachment
volker_memory.cpp (966 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: access violation in update_discarded(...)

Menelaos Karavelas
Hi again.
I defined my test polygon as closed. Here is the correct program and output.

- m.


On 27/10/2014 08:51 μμ, Menelaos Karavelas wrote:
Hi Volker.

On 27/10/2014 07:39 μμ, Volker Schöch wrote:

Hi,

 

Unfortunately I have not hear from you in this regard. It seems that I still cannot reliably reproduce the issue, but when it occurs, it occurs in the following scenario. Apparently, something is broken in your memory management:

 

{      // RT#8837

       _intPolygon polygonA;

       boost::geometry::read_wkt("MULTIPOLYGON(((488 2035,527 2035,527 2093,488 2093)))", polygonA); // does not throw

 

       _intRect rectB;

       boost::geometry::read_wkt("BOX(417 2064,597 2064)", rectB); // does not throw

 

       _intPolygon polygonC;

       boost::geometry::difference(polygonA, rectB, polygonC); // ACCESS VIOLATION

}

 

Maybe you could make an effort and step through this simple example once to see if everything works as expected?

 

I understand that the box and/or the polygon may not conform to all requirements (not spike-free etc.) but in any case, IMO the geometry library should not crash with a memory fault.

 

As always, my points are based on int and my polygons are counter-clockwise and not closed.

 


Please see the attached program and its output, which works for me.
Do you think you can reproduce the problem in a standalone program?

All the best,

- m.

Regards

   Volker

 

 

--
Volker Schöch | [hidden email]
Senior Software Engineer


We are looking for C++ Developers: http://www.think-cell.com/career

From: Geometry [[hidden email]] On Behalf Of Volker Schöch
Sent: Freitag, 17. Oktober 2014 16:20
To: Boost.Geometry library mailing list ([hidden email])
Subject: [geometry] access violation in update_discarded(...)

 

Hi,

 

we have seen an access violation deep inside boost geometry. We are still working on a simple reproduction, which may take while. In the meantime, maybe you have some idea what went wrong, or some suggestion how to avoid this situation?

 

Here is where it happened:

 

template<typename Turns, typename Operations>

inline void update_discarded(Turns& turn_points, Operations& operations)

{

    // Vice-versa, set discarded to true for discarded operations;

    // AND set discarded points to true

    for (typename boost::range_iterator<Operations>::type it = boost::begin(operations);

         it != boost::end(operations);

         ++it)

    {

        if (turn_points[it->index].discarded) <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< access violation

        {

            it->discarded = true;

        }

        else if (it->discarded)

        {

            turn_points[it->index].discarded = true;

        }

    }

}

 

Please find the callstack attached.

 

Regards

   Volker

--
Volker Schöch | [hidden email]
Senior Software Engineer


We are looking for C++ Developers:http://www.think-cell.com/career


think-cell Software GmbH

http://www.think-cell.com

Chausseestr. 8/E

phone / fax

+49 30 666473-10 / -19

10115 Berlin, Germany

US phone / fax

+1 800 891 8091 / +1 212 504 3039

Amtsgericht Berlin-Charlottenburg, HRB 85229 | European Union VAT Id DE813474306

Directors: Dr. Markus Hannebauer, Dr. Arno Schödl

 



_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry



_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry

volker_memory.out (316 bytes) Download Attachment
volker_memory.cpp (967 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: access violation in update_discarded(...)

Valentin Ziegler
In reply to this post by Volker Schöch

Hi,

 

I investigated Volker's example and found the problems are caused by undefined behaviour within the comparison function object sort_on_segment_and_ratio, which is used for sorting vectors of indexed_turn_operation.

 

Running Volker's code, we get into the following callstack:

 

copy_segment_point(... SegmentIdentifier const& seg_id, .... )

copy_segment_points(...)

sort_on_segment_and_ratio::get_situation_map(...)

sort_on_segment_and_ratio::consider_relative_order(...)

sort_on_segment_and_ratio::operator()(...)

std::sort(...)

enrich_sort(...)

enrich_intersection_points(...)

...

difference(polygonA, rectB, polygonC);

...

 

Note that  the seg_id argument for copy_segment_point is taken from the indexed turn operations being compared (i.e., either subject.seg_id or subject.other_id).

 

If seg_id.source_index == -1, copy_segment_points does not copy any data, thus the computation continues with random junk values from the stack :-(

 

This is exactly what happens in Volker's example, as some of the turning points have other_id.source_index == -1.

As a consequence, sort_on_segment_and_ratio::operator()(...) gives nondeterministic comparision results which confuses Visual Studio's std::sort implementation so much that it starts writing to memory locations outside the input range (Please note that this is NOT a bug of std::sort).

 

I do not have the expertise to tell where these negative source_index values come from and whether these values are to be expected or if they arise due to some issue. It would be nice if someone could look into this.

 

Valentin

 

 

 

--
Valentin Ziegler | [hidden email]
Senior Software Engineer


We are looking for C++ Developers: http://www.think-cell.com/career

think-cell Software GmbH http://www.think-cell.com
Chausseestr. 8/E phone / fax +49 30 666473-10 / -19
10115 Berlin, Germany US phone / fax +1 800 891 8091 / +1 212 504 3039
Amtsgericht Berlin-Charlottenburg, HRB 85229 | European Union VAT Id DE813474306
Directors: Dr. Markus Hannebauer, Dr. Arno Schödl

From: Geometry [[hidden email]] On Behalf Of Volker Schöch
Sent: Montag, 27. Oktober 2014 18:40
To: Boost.Geometry library mailing list ([hidden email])
Subject: Re: [geometry] access violation in update_discarded(...)

 

Hi,

 

Unfortunately I have not hear from you in this regard. It seems that I still cannot reliably reproduce the issue, but when it occurs, it occurs in the following scenario. Apparently, something is broken in your memory management:

 

{      // RT#8837

       _intPolygon polygonA;

       boost::geometry::read_wkt("MULTIPOLYGON(((488 2035,527 2035,527 2093,488 2093)))", polygonA); // does not throw

 

       _intRect rectB;

       boost::geometry::read_wkt("BOX(417 2064,597 2064)", rectB); // does not throw

 

       _intPolygon polygonC;

       boost::geometry::difference(polygonA, rectB, polygonC); // ACCESS VIOLATION

}

 

Maybe you could make an effort and step through this simple example once to see if everything works as expected?

 

I understand that the box and/or the polygon may not conform to all requirements (not spike-free etc.) but in any case, IMO the geometry library should not crash with a memory fault.

 

As always, my points are based on int and my polygons are counter-clockwise and not closed.

 

Regards

   Volker

 


_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|

Re: access violation in update_discarded(...)

Menelaos Karavelas
Hi Valentin.

Thanks for the report. I think with this information we will be able to track down the problem.
In the meantime I suggest that either you of Volker file a bug report.

Many thanks.

Best,

- m.

On 29/10/2014 06:26 μμ, Valentin Ziegler wrote:

Hi,

 

I investigated Volker's example and found the problems are caused by undefined behaviour within the comparison function object sort_on_segment_and_ratio, which is used for sorting vectors of indexed_turn_operation.

 

Running Volker's code, we get into the following callstack:

 

copy_segment_point(... SegmentIdentifier const& seg_id, .... )

copy_segment_points(...)

sort_on_segment_and_ratio::get_situation_map(...)

sort_on_segment_and_ratio::consider_relative_order(...)

sort_on_segment_and_ratio::operator()(...)

std::sort(...)

enrich_sort(...)

enrich_intersection_points(...)

...

difference(polygonA, rectB, polygonC);

...

 

Note that  the seg_id argument for copy_segment_point is taken from the indexed turn operations being compared (i.e., either subject.seg_id or subject.other_id).

 

If seg_id.source_index == -1, copy_segment_points does not copy any data, thus the computation continues with random junk values from the stack :-(

 

This is exactly what happens in Volker's example, as some of the turning points have other_id.source_index == -1.

As a consequence, sort_on_segment_and_ratio::operator()(...) gives nondeterministic comparision results which confuses Visual Studio's std::sort implementation so much that it starts writing to memory locations outside the input range (Please note that this is NOT a bug of std::sort).

 

I do not have the expertise to tell where these negative source_index values come from and whether these values are to be expected or if they arise due to some issue. It would be nice if someone could look into this.

 

Valentin

 

 

 

--
Valentin Ziegler | [hidden email]
Senior Software Engineer


We are looking for C++ Developers: http://www.think-cell.com/career

think-cell Software GmbH http://www.think-cell.com
Chausseestr. 8/E phone / fax +49 30 666473-10 / -19
10115 Berlin, Germany US phone / fax +1 800 891 8091 / +1 212 504 3039
Amtsgericht Berlin-Charlottenburg, HRB 85229 | European Union VAT Id DE813474306
Directors: Dr. Markus Hannebauer, Dr. Arno Schödl

From: Geometry [[hidden email]] On Behalf Of Volker Schöch
Sent: Montag, 27. Oktober 2014 18:40
To: Boost.Geometry library mailing list ([hidden email])
Subject: Re: [geometry] access violation in update_discarded(...)

 

Hi,

 

Unfortunately I have not hear from you in this regard. It seems that I still cannot reliably reproduce the issue, but when it occurs, it occurs in the following scenario. Apparently, something is broken in your memory management:

 

{      // RT#8837

       _intPolygon polygonA;

       boost::geometry::read_wkt("MULTIPOLYGON(((488 2035,527 2035,527 2093,488 2093)))", polygonA); // does not throw

 

       _intRect rectB;

       boost::geometry::read_wkt("BOX(417 2064,597 2064)", rectB); // does not throw

 

       _intPolygon polygonC;

       boost::geometry::difference(polygonA, rectB, polygonC); // ACCESS VIOLATION

}

 

Maybe you could make an effort and step through this simple example once to see if everything works as expected?

 

I understand that the box and/or the polygon may not conform to all requirements (not spike-free etc.) but in any case, IMO the geometry library should not crash with a memory fault.

 

As always, my points are based on int and my polygons are counter-clockwise and not closed.

 

Regards

   Volker

 



_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry


_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|

Re: access violation in update_discarded(...)

Volker Schöch

Done.

https://svn.boost.org/trac/boost/ticket/10719

 

 

--
Volker Schöch | [hidden email]
Senior Software Engineer


We are looking for C++ Developers: http://www.think-cell.com/career

think-cell Software GmbH http://www.think-cell.com
Chausseestr. 8/E phone / fax +49 30 666473-10 / -19
10115 Berlin, Germany US phone / fax +1 800 891 8091 / +1 212 504 3039
Amtsgericht Berlin-Charlottenburg, HRB 85229 | European Union VAT Id DE813474306
Directors: Dr. Markus Hannebauer, Dr. Arno Schödl

From: Geometry [mailto:[hidden email]] On Behalf Of Menelaos Karavelas
Sent: Mittwoch, 29. Oktober 2014 17:32
To: [hidden email]
Subject: Re: [geometry] access violation in update_discarded(...)

 

Hi Valentin.

Thanks for the report. I think with this information we will be able to track down the problem.
In the meantime I suggest that either you of Volker file a bug report.

Many thanks.

Best,

- m.


_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|

Re: access violation in update_discarded(...)

Volker Schöch

Hi,

 

Can you give any perspective on when or how this problem may be solved?

It’s mission critical to our software, so we have to do something about it soon.

 

Thank you

   Volker

 

 

--
Volker Schöch | [hidden email]
Senior Software Engineer


We are looking for C++ Developers: http://www.think-cell.com/career

think-cell Software GmbH http://www.think-cell.com
Chausseestr. 8/E phone / fax +49 30 666473-10 / -19
10115 Berlin, Germany US phone / fax +1 800 891 8091 / +1 212 504 3039
Amtsgericht Berlin-Charlottenburg, HRB 85229 | European Union VAT Id DE813474306
Directors: Dr. Markus Hannebauer, Dr. Arno Schödl

From: Geometry [[hidden email]] On Behalf Of Volker Schöch
Sent: Donnerstag, 30. Oktober 2014 11:34
To: [hidden email]
Subject: Re: [geometry] access violation in update_discarded(...)

 

Done.

https://svn.boost.org/trac/boost/ticket/10719

 

 


_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|

Re: access violation in update_discarded(...)

Barend
Hi Volker,


From: Geometry [[hidden email]] On Behalf Of Volker Schöch
Sent: Donnerstag, 30. Oktober 2014 11:34
To: [hidden email]
Subject: Re: [geometry] access violation in update_discarded(...)

 

Done.

https://svn.boost.org/trac/boost/ticket/10719



Volker Schöch wrote On 6-11-2014 9:55:

Hi,

 

Can you give any perspective on when or how this problem may be solved?

It’s mission critical to our software, so we have to do something about it soon.


1) I think I have to write: it is volunteer work - the ticket is opened one week ago. We appreciate your usage of Boost.Geometry and the feedback too, but take care not to transfer the pressure you feel to us volunteers... At least not to soon.

But I looked.

2) Menelaos send a sample program which works for him, and works for me. Did you try that program? He also asked

Do you think you can reproduce the problem in a standalone program?

but you did not answer that question. Actually the whole mail was unanswered.

3) you already mention that your input is invalid - so you should be able to workaround the problem probably easily.

4) you include a stack-trace (thanks for that) but things have been changed, get_situation_map is gone from enrich_intersection_points, and so might be the whole problem. This is by chance released this week

So my new question is: does it work for you in 1.57?

5) Valentin reports:
If seg_id.source_index == -1, copy_segment_points does not copy any data, thus the computation continues with random junk values from the stack :-(

but that may indeed never be the case in that sort functor. source_index should be either 0 or 1. If it indeed has another value, this indicates an error. But I cannot find or reproduce this error (I used MSVC on the old version, and the new version with clang and valgrind).

Regards, Barend




_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|

Re: access violation in update_discarded(...)

Volker Schöch

Hi Barend,

Thank you for your recent reply. I meant to answer all your questions in one mail, which took a while, so please bear with me while I try to sort it all out.

 

1) I think I have to write: it is volunteer work - the ticket is opened one week ago. We appreciate your usage of Boost.Geometry and the feedback too, but take care not to transfer the pressure you feel to us volunteers... At least not too soon.

Sure, absolutely. I can’t tell you how much I appreciate your work and your availability! Honestly. By “we” I was referring to think-cell: We have to deal with these problems one way or another. Of course, before spending time on working around problems, it’s tremendously helpful to understand if and when there might be a real fix available. I apologize if my way of putting this into words was ambiguous. No harm meant!


2) Menelaos sen
t a sample program which works for him, and works for me. Did you try that program? He also asked
Do you think you can reproduce the problem in a standalone program?

but you did not answer that question. Actually the whole mail was unanswered.

 

The fact that the algorithm accesses uninitialized memory means two things:

-       The problem may be hard to reproduce.

-       Just because it happens to work under certain circumstances, doesn’t mean it’s correct.

For this reason, instead of insisting on the fact that it keeps crashing on my machine when compiled with my compiler, my colleague Valentin made an effort and stepped into the algorithm and found some code where you were (in 1.56.0) accessing uninitialized memory. Whether or not that produces a crash later, depends on the actual values found in that uninitialized memory. For example, most compilers in fact do initialize “uninitialized” memory with a certain value pattern, when compiling with debug build settings, and so when testing you may actually reliably read the same value that doesn’t lead to a crash further down. But that doesn’t mean it’s correct, and it may still crash, e.g., with my release build compiler settings.

 

For all these reasons, I deemed Valentins email an appropriate answer to Menelaos’ question.

3) you already mention that your input is invalid - so you should be able to workaround the problem probably easily.

Yes, you’re right. Running the new is_valid(…) predicate before invoking the actual algorithm helps to suppress the problem in 1.56.0. I’m still struggling with your ideas of valid/invalid, pre conditions and post conditions. Let’s postpone that topic to a separate discussion.


4) you include a stack-trace (thanks for that) but things have been changed, get_situation_map is gone from enrich_intersection_points, and so might be the whole problem. This is by chance released this week
So my new question is: does it work for you in 1.57?

We moved our entire project to 1.57.0 (which is part of the reason why I did not reply earlier). The apparently good news is: I cannot reproduce the crash any more. I even made sure, that copy_segment_point does not return false, and in my quick testing so far, it never did, which (to my understanding) means that point_out actually gets initialized.

 

I still find it suspicious that consider_relative_order calls copy_segment_points without checking for the return value. If copy_segment_point and consequently copy_segment_points would return false, then pi, pj, ri, rj, si, sj would be uninitialized and all kinds of things could happen further down. I would feel much better if at that point there were an assertion, or an exception thrown, because then the problem – if there is any – would become obvious independent of the actual values that happen to be found in uninitialized memory.

 

Thus here is my suggestion: Since this piece of code is vulnerable to problems that lead to errors much later, and those errors are inherently hard to reproduce, you should assert or throw whenever copy_segment_points does not initialize its out-parameters. With this kind of safeguard in place, the issue could be closed for the time being. If there is still a problem in 1.57.0, or if new problems are introduced in later versions, we will then learn soon enough.

https://svn.boost.org/trac/boost/ticket/10719

 

Regards

   Volker

--
Volker Schöch | [hidden email]
Senior Software Engineer


We are looking for C++ Developers: http://www.think-cell.com/career

think-cell Software GmbH http://www.think-cell.com
Chausseestr. 8/E phone / fax +49 30 666473-10 / -19
10115 Berlin, Germany US phone / fax +1 800 891 8091 / +1 212 504 3039
Amtsgericht Berlin-Charlottenburg, HRB 85229 | European Union VAT Id DE813474306
Directors: Dr. Markus Hannebauer, Dr. Arno Schödl


_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|

Re: access violation in update_discarded(...)

Barend
Hi Volker,

Thanks for your clear message ;-)


Volker Schöch wrote On 14-11-2014 15:28:

Hi Barend,

Thank you for your recent reply. I meant to answer all your questions in one mail, which took a while, so please bear with me while I try to sort it all out.

 

1) I think I have to write: it is volunteer work - the ticket is opened one week ago. We appreciate your usage of Boost.Geometry and the feedback too, but take care not to transfer the pressure you feel to us volunteers... At least not too soon.

Sure, absolutely. I can’t tell you how much I appreciate your work and your availability! Honestly. By “we” I was referring to think-cell: We have to deal with these problems one way or another. Of course, before spending time on working around problems, it’s tremendously helpful to understand if and when there might be a real fix available. I apologize if my way of putting this into words was ambiguous. No harm meant!


Thanks - we appreciate all your messages and researches. There is no harm of course, I just wanted to subtle indicate something about pressure but maybe it was not subtle enough... Anyway, no problem at all.


2) Menelaos sen
t a sample program which works for him, and works for me. Did you try that program? He also asked
Do you think you can reproduce the problem in a standalone program?

but you did not answer that question. Actually the whole mail was unanswered.

 

The fact that the algorithm accesses uninitialized memory means two things:

-       The problem may be hard to reproduce.

-       Just because it happens to work under certain circumstances, doesn’t mean it’s correct.

For this reason, instead of insisting on the fact that it keeps crashing on my machine when compiled with my compiler, my colleague Valentin made an effort and stepped into the algorithm and found some code where you were (in 1.56.0) accessing uninitialized memory. Whether or not that produces a crash later, depends on the actual values found in that uninitialized memory. For example, most compilers in fact do initialize “uninitialized” memory with a certain value pattern, when compiling with debug build settings, and so when testing you may actually reliably read the same value that doesn’t lead to a crash further down. But that doesn’t mean it’s correct, and it may still crash, e.g., with my release build compiler settings.

 

For all these reasons, I deemed Valentins email an appropriate answer to Menelaos’ question.


The answer was helpful indeed.


3) you already mention that your input is invalid - so you should be able to workaround the problem probably easily.

Yes, you’re right. Running the new is_valid(…) predicate before invoking the actual algorithm helps to suppress the problem in 1.56.0. I’m still struggling with your ideas of valid/invalid, pre conditions and post conditions. Let’s postpone that topic to a separate discussion.


4) you include a stack-trace (thanks for that) but things have been changed, get_situation_map is gone from enrich_intersection_points, and so might be the whole problem. This is by chance released this week
So my new question is: does it work for you in 1.57?

We moved our entire project to 1.57.0 (which is part of the reason why I did not reply earlier). The apparently good news is: I cannot reproduce the crash any more. I even made sure, that copy_segment_point does not return false, and in my quick testing so far, it never did, which (to my understanding) means that point_out actually gets initialized.

 

I still find it suspicious that consider_relative_order calls copy_segment_points without checking for the return value. If copy_segment_point and consequently copy_segment_points would return false, then pi, pj, ri, rj, si, sj would be uninitialized and all kinds of things could happen further down. I would feel much better if at that point there were an assertion, or an exception thrown, because then the problem – if there is any – would become obvious independent of the actual values that happen to be found in uninitialized memory.


Yes you are right. Actually I already did, because of your last mail. After inspecting the code I made a fix. For open polygons, copying the very last segment, it did not work correctly and therefore failed. This was because the size of the range was inspected before the view. Most probably this was the problem. That was after 1.57 was released, so you don't have it. It's this commit:

https://github.com/boostorg/geometry/commit/16fb68921763ca188397d5e1bebf6ff005ecdaa8

In fact I implemented your suggestion too, because it asserts now and always return true. We can remove its return value now (I think I will do).

 

Thus here is my suggestion: Since this piece of code is vulnerable to problems that lead to errors much later, and those errors are inherently hard to reproduce, you should assert or throw whenever copy_segment_points does not initialize its out-parameters. With this kind of safeguard in place, the issue could be closed for the time being. If there is still a problem in 1.57.0, or if new problems are introduced in later versions, we will then learn soon enough.

https://svn.boost.org/trac/boost/ticket/10719

 


So reading this, I could indeed close the ticket now..

Thanks again for your message.

Regards, Barend


_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|

Re: access violation in update_discarded(...)

Volker Schöch

> After inspecting the code I made a fix. For open polygons, copying the very last segment, it did not work correctly and therefore failed. This was because the size of the range was inspected before the view. Most probably this was the problem. That was after 1.57 was released, so you don't have it. It's this commit:
>
>
https://github.com/boostorg/geometry/commit/16fb68921763ca188397d5e1bebf6ff005ecdaa8
>
> In fact I implemented your suggestion too, because it asserts now and always return true. We can remove its return value now (I think I will do).

That’s cool! J You made my day. Thank you so much!

Have a nice rest of the weekend

   Volker

 

--
Volker Schöch | [hidden email]
Senior Software Engineer


We are looking for C++ Developers: http://www.think-cell.com/career

think-cell Software GmbH http://www.think-cell.com
Chausseestr. 8/E phone / fax +49 30 666473-10 / -19
10115 Berlin, Germany US phone / fax +1 800 891 8091 / +1 212 504 3039
Amtsgericht Berlin-Charlottenburg, HRB 85229 | European Union VAT Id DE813474306
Directors: Dr. Markus Hannebauer, Dr. Arno Schödl


_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry