libavoid in Inkscape: bug with compiler optimization
Hello Michael, While running a static analyzer on Inkscape's codebase [1], I found a fairly severe bug in our copy of libavoid. I checked your git repository, and the bug is still present.
In graph.cpp, from line 643:
void EdgeList::clear(void) { while (_firstEdge) { delete _firstEdge; } COLA_ASSERT(_count == 0); _lastEdge = NULL; }
The bug here is that the compiler might optimize the loop-condition and only check it once, assuming that the destructor of _firstEdge does not have the side-effect of changing _firstEdge. In fact, libavoid's design is such that the destructor does have such a side effect. I find this a *very* questionable design, that is bound to cause bugs for developers contributing code or, in this case, by a (afaik fairly common, see [2]) compiler optimization. I am surprised you have not had programs run into this problem. However, I cannot rewrite all the code that relies on that behavior. I hope you would consider redesigning the list implementation, such that it does not have unintuitive side effects.
For now, I am planning to "fix" this bug by:
void EdgeList::clear(void) { EdgeInf *edge = _firstEdge; while (edge) { EdgeInf *next_edge = edge->lstNext; delete edge; edge = next_edge; } COLA_ASSERT(_count == 0); COLA_ASSERT(_firstEdge == NULL); _lastEdge = NULL; }
Do you agree with this fix?
Thank you for your comment. Kind regards, Johan
[1] http://ec2-54-69-235-61.us-west-2.compute.amazonaws.com:8080/job/Inkscape_tr...
[2] http://stackoverflow.com/questions/9495856/how-to-prevent-g-from-optimizing-...
Hi Johan,
I disagree that this is a bug. Compilers can't assume that non-trivial (programmer defined) destructors have no side-effects and optimise them away. They can only do that kind of elimination of code when they can *prove* the observable behaviour of the program is that same after the optimisation. AFAIK, trivial destructors can get optimised away but not when explicitly called via 'delete'.
It looks like the clang static analyser is confused when it reports 'Use of memory after it is freed.' I see it has had other problems understanding this sort of code, e.g., see [3]. As part of development I frequently run valgrind and the clang AddressSanitizer on libavoid so I can assure you that that code doesn't result in any use-after-free.
I do however agree the behaviour of the libavoid code is not obvious. I have added a comment to that code in the git repository to explain the behaviour. I also realise the design of some of the data structures in libavoid are not ideal from a code clarity standpoint. They were originally implemented with STL containers, but have been redesigned in this complicated way due performance reasons.
In terms of other issues reported by clang, I will look at addressing these in our git repository and then we should look at replace Inkscape libavoid version with this since it contains many other improvements and fixes. (Last time I looked there was some change that made this replacement non-trivial, but I've long since forgotten what it was exactly.)
Cheers, Michael
[3] http://stackoverflow.com/questions/23431859/is-the-clang-static-analyzer-con...
On 12 Oct 2014, at 3:46 am, Johan Engelen <jbc.engelen@...2592...> wrote:
Hello Michael, While running a static analyzer on Inkscape's codebase [1], I found a fairly severe bug in our copy of libavoid. I checked your git repository, and the bug is still present.
In graph.cpp, from line 643:
void EdgeList::clear(void) { while (_firstEdge) { delete _firstEdge; } COLA_ASSERT(_count == 0); _lastEdge = NULL; }
The bug here is that the compiler might optimize the loop-condition and only check it once, assuming that the destructor of _firstEdge does not have the side-effect of changing _firstEdge. In fact, libavoid's design is such that the destructor does have such a side effect. I find this a *very* questionable design, that is bound to cause bugs for developers contributing code or, in this case, by a (afaik fairly common, see [2]) compiler optimization. I am surprised you have not had programs run into this problem. However, I cannot rewrite all the code that relies on that behavior. I hope you would consider redesigning the list implementation, such that it does not have unintuitive side effects.
For now, I am planning to "fix" this bug by:
void EdgeList::clear(void) { EdgeInf *edge = _firstEdge; while (edge) { EdgeInf *next_edge = edge->lstNext; delete edge; edge = next_edge; } COLA_ASSERT(_count == 0); COLA_ASSERT(_firstEdge == NULL); _lastEdge = NULL; }
Do you agree with this fix?
Thank you for your comment. Kind regards, Johan
[1] http://ec2-54-69-235-61.us-west-2.compute.amazonaws.com:8080/job/Inkscape_tr...
[2] http://stackoverflow.com/questions/9495856/how-to-prevent-g-from-optimizing-...
----- Dr. Michael Wybrow, Lecturer Monash Adaptive Visualisation Lab (MArVL) Faculty of Information Technology Monash University, Caulfield, Australia Office: Rm 6.35, Level 6, Building H, Caulfield Campus Phone: +613 9905 2479 Mobile: +614 2577 2053
Note: I'm part-time and don't work Wednesdays.
Hi Michael, Thanks for your quick reply, and for looking at the other reports.
I'm sorry for calling it a "bug". You are right, it technically isn't. But I feel it is very close to one, perhaps when using a compiler with very aggressive optimization enabled (at some point, optimizations become non-standard compliant). In any case, I checked with clang -O3, and the loop predicate seems to be left intact when it contains an object member variable. Not surprising, because otherwise the bug would surface instantly. However, I still feel it'd be wise to try to get rid of this false positive (the fix I proposed is reasonable I think) so that it does not clobber-up the total report; but thanks for adding a comment about it, so that it will not take up developer time needlessly.
It'd be great if you could spend some time on upgrading our libavoid copy. Please do so in our lp:inkscape/experimental branch. We are close to releasing trunk.
cheers, Johan
On 13-10-2014 2:04, Michael Wybrow wrote:
Hi Johan,
I disagree that this is a bug. Compilers can't assume that non-trivial (programmer defined) destructors have no side-effects and optimise them away. They can only do that kind of elimination of code when they can *prove* the observable behaviour of the program is that same after the optimisation. AFAIK, trivial destructors can get optimised away but not when explicitly called via 'delete'.
It looks like the clang static analyser is confused when it reports 'Use of memory after it is freed.' I see it has had other problems understanding this sort of code, e.g., see [3]. As part of development I frequently run valgrind and the clang AddressSanitizer on libavoid so I can assure you that that code doesn't result in any use-after-free.
I do however agree the behaviour of the libavoid code is not obvious. I have added a comment to that code in the git repository to explain the behaviour. I also realise the design of some of the data structures in libavoid are not ideal from a code clarity standpoint. They were originally implemented with STL containers, but have been redesigned in this complicated way due performance reasons.
In terms of other issues reported by clang, I will look at addressing these in our git repository and then we should look at replace Inkscape libavoid version with this since it contains many other improvements and fixes. (Last time I looked there was some change that made this replacement non-trivial, but I've long since forgotten what it was exactly.)
Cheers, Michael
[3] http://stackoverflow.com/questions/23431859/is-the-clang-static-analyzer-con...
On 12 Oct 2014, at 3:46 am, Johan Engelen <jbc.engelen@...2592...> wrote:
Hello Michael, While running a static analyzer on Inkscape's codebase [1], I found a fairly severe bug in our copy of libavoid. I checked your git repository, and the bug is still present.
In graph.cpp, from line 643:
void EdgeList::clear(void) { while (_firstEdge) { delete _firstEdge; } COLA_ASSERT(_count == 0); _lastEdge = NULL; }
The bug here is that the compiler might optimize the loop-condition and only check it once, assuming that the destructor of _firstEdge does not have the side-effect of changing _firstEdge. In fact, libavoid's design is such that the destructor does have such a side effect. I find this a *very* questionable design, that is bound to cause bugs for developers contributing code or, in this case, by a (afaik fairly common, see [2]) compiler optimization. I am surprised you have not had programs run into this problem. However, I cannot rewrite all the code that relies on that behavior. I hope you would consider redesigning the list implementation, such that it does not have unintuitive side effects.
For now, I am planning to "fix" this bug by:
void EdgeList::clear(void) { EdgeInf *edge = _firstEdge; while (edge) { EdgeInf *next_edge = edge->lstNext; delete edge; edge = next_edge; } COLA_ASSERT(_count == 0); COLA_ASSERT(_firstEdge == NULL); _lastEdge = NULL; }
Do you agree with this fix?
Thank you for your comment. Kind regards, Johan
[1] http://ec2-54-69-235-61.us-west-2.compute.amazonaws.com:8080/job/Inkscape_tr...
[2] http://stackoverflow.com/questions/9495856/how-to-prevent-g-from-optimizing-...
Dr. Michael Wybrow, Lecturer Monash Adaptive Visualisation Lab (MArVL) Faculty of Information Technology Monash University, Caulfield, Australia Office: Rm 6.35, Level 6, Building H, Caulfield Campus Phone: +613 9905 2479 Mobile: +614 2577 2053
Note: I'm part-time and don't work Wednesdays.
participants (2)
-
Johan Engelen -
Michael Wybrow