[Bug 52492] New: stack overflow from GdipFlattenPath
https://bugs.winehq.org/show_bug.cgi?id=52492 Bug ID: 52492 Summary: stack overflow from GdipFlattenPath Product: Wine Version: 7.1 Hardware: x86-64 OS: Mac OS X Status: UNCONFIRMED Severity: normal Priority: P2 Component: gdiplus Assignee: wine-bugs(a)winehq.org Reporter: rjfeuerbach(a)gmail.com Created attachment 71787 --> https://bugs.winehq.org/attachment.cgi?id=71787 test patch to replicate the curves and stack overflow I have a third party application, unfortunately not available for download, that is generating a virtual stack overflow error. Using +replay and eventually +gdiplus messages, the cause was narrowed down to be due to calls to GdipFlattenPath. Attached is a patch to gdiplus/test/graphicspath.c to include the precise curves that cause the stack overflow. I believe the problem is due to the comparison of REALs with == in the flatten_bezier helper function. -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=52492 Fabian Maurer <dark.shadow4(a)web.de> changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |dark.shadow4(a)web.de --- Comment #1 from Fabian Maurer <dark.shadow4(a)web.de> --- Seems to work fine on my Arch installation. Wouldn't be too surprising when it comes to floating point math, though. What exactly are your compile options? -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=52492 Fabian Maurer <dark.shadow4(a)web.de> changed: What |Removed |Added ---------------------------------------------------------------------------- Keywords| |testcase -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=52492 --- Comment #2 from Rob F <rjfeuerbach(a)gmail.com> --- Thanks for following up. So I'm on MacOS 11.6.2, using clang and the wine64 build. I'm not sure which compile options you are referring to, but in case it is how configure is being called, it is: CC=clang CXX=clang++ GPHOTO2_CFLAGS=-I/usr/local/opt/libgphoto2/include -I/usr/local/opt/libgphoto2/include/gphoto2 GPHOTO2_PORT_CFLAGS=-I/usr/local/opt/libgphoto2/include -I/usr/local/opt/libgphoto2/include/gphoto2 SDL2_CFLAGS=-I/usr/local/opt/sdl2/include/SDL2 /Users/feuerrj1/Documents/SW/wine/configure --enable-win64 --without-x --with-mingw --with-png --with-sdl The test code I posted generates a number of sucesses, including on one of the flatten tests, but finally generates a "stack overflow" error for me. I have tried replacing the float "==" in gdiplus/graphicspath.c:flatten_bezier with an "isclose" variation using the FLT_EPSILON and the problem appears fixed. However, I'm not sure if this is really the best solution. -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=52492 --- Comment #3 from Rob F <rjfeuerbach(a)gmail.com> --- As for compile options, the compile line for gdiplus/graphicpath.c looks like: x86_64-w64-mingw32-gcc -c -o dlls/gdiplus/graphicspath.cross.o /Users/feuerrj1/Documents/SW/wine/dlls/gdiplus/graphicspath.c -Idlls/gdiplus \ -I/Users/feuerrj1/Documents/SW/wine/dlls/gdiplus -Iinclude \ -I/Users/feuerrj1/Documents/SW/wine/include -I/Users/feuerrj1/Documents/SW/wine/include/msvcrt \ -D__WINESRC__ -DWINE_NO_LONG_TYPES -D_UCRT -D__WINE_PE_BUILD -Wall -fno-strict-aliasing \ -Wdeclaration-after-statement -Wempty-body -Wignored-qualifiers -Winit-self \ -Wno-packed-not-aligned -Wshift-overflow=2 -Wstrict-prototypes -Wtype-limits \ -Wunused-but-set-parameter -Wvla -Wwrite-strings -Wpointer-arith -Wlogical-op -Wabsolute-value \ -Wno-format -Wformat-overflow -Wnonnull -mcx16 -gdwarf-4 -g -O2 -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=52492 David Kahurani <k.kahurani(a)gmail.com> changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |k.kahurani(a)gmail.com --- Comment #4 from David Kahurani <k.kahurani(a)gmail.com> --- (In reply to Rob F from comment #2)
The test code I posted generates a number of sucesses, including on one of the flatten tests, but finally generates a "stack overflow" error for me. I have tried replacing the float "==" in gdiplus/graphicspath.c:flatten_bezier with an "isclose" variation using the FLT_EPSILON and the problem appears fixed. However, I'm not sure if this is really the best solution.
It looks like this the function that causes the overflow static BOOL flatten_bezier(path_list_node_t *start, REAL x2, REAL y2, REAL x3, REAL y3, path_list_node_t *end, REAL flatness) { /* this 5 middle points with start/end define to half-curves */ GpPointF mp[5]; GpPointF pt, pt_st; path_list_node_t *node; /* calculate bezier curve middle points == new control points */ mp[0].X = (start->pt.X + x2) / 2.0; mp[0].Y = (start->pt.Y + y2) / 2.0; /* middle point between control points */ pt.X = (x2 + x3) / 2.0; pt.Y = (y2 + y3) / 2.0; mp[1].X = (mp[0].X + pt.X) / 2.0; mp[1].Y = (mp[0].Y + pt.Y) / 2.0; mp[4].X = (end->pt.X + x3) / 2.0; mp[4].Y = (end->pt.Y + y3) / 2.0; mp[3].X = (mp[4].X + pt.X) / 2.0; mp[3].Y = (mp[4].Y + pt.Y) / 2.0; mp[2].X = (mp[1].X + mp[3].X) / 2.0; mp[2].Y = (mp[1].Y + mp[3].Y) / 2.0; if ((x2 == mp[0].X && y2 == mp[0].Y && x3 == mp[1].X && y3 == mp[1].Y) || (x2 == mp[3].X && y2 == mp[3].Y && x3 == mp[4].X && y3 == mp[4].Y)) return TRUE; pt = end->pt; pt_st = start->pt; /* check flatness as a half of distance between middle point and a linearized path */ if(fabs(((pt.Y - pt_st.Y)*mp[2].X + (pt_st.X - pt.X)*mp[2].Y + (pt_st.Y*pt.X - pt_st.X*pt.Y))) <= (0.5 * flatness*sqrtf((powf(pt.Y - pt_st.Y, 2.0) + powf(pt_st.X - pt.X, 2.0))))){ return TRUE; } else /* add a middle point */ if(!(node = add_path_list_node(start, mp[2].X, mp[2].Y, PathPointTypeLine))) return FALSE; /* do the same with halves */ flatten_bezier(start, mp[0].X, mp[0].Y, mp[1].X, mp[1].Y, node, flatness); flatten_bezier(node, mp[3].X, mp[3].Y, mp[4].X, mp[4].Y, end, flatness); return TRUE; } The overflow happens only with small values of flatness. Small values of flatness make the function recurse many more times which is the cause of the overflow. The solution would be to come up with a non-recursive implementation of this method. -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=52492 --- Comment #5 from Fabian Maurer <dark.shadow4(a)web.de> --- Created attachment 74614 --> https://bugs.winehq.org/attachment.cgi?id=74614 Make flatten_bezier iterative Added patch to make flatten_bezier iterative. Should be correct, but no guarantees I didn't break something in the process of conversion. Since the bug doesn't appear for me, can you try if this helps (and is still correct)? Probably pretty bad for performance, since stack is so much faster, but since stack seems limited... -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=52492 --- Comment #6 from David Kahurani <k.kahurani(a)gmail.com> --- (In reply to Fabian Maurer from comment #5)
Created attachment 74614 [details] Make flatten_bezier iterative
Added patch to make flatten_bezier iterative. Should be correct, but no guarantees I didn't break something in the process of conversion.
Since the bug doesn't appear for me, can you try if this helps (and is still correct)? Probably pretty bad for performance, since stack is so much faster, but since stack seems limited...
It looks like this patch makes my PC crash. I don't know how correct it is but, personally, to re-write this function, I'd try to construct it into a quadratic loop. for(initial;constraint;advance){ for (initial;constraint;advance) { } } Time complexity would probably be equal to that of the original recursive approach. My 2 cents... -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=52492 Fabian Maurer <dark.shadow4(a)web.de> changed: What |Removed |Added ---------------------------------------------------------------------------- Status|UNCONFIRMED |NEW Ever confirmed|0 |1 --- Comment #7 from Fabian Maurer <dark.shadow4(a)web.de> ---
It looks like this patch makes my PC crash.
Yeah sorry, looks like there is an endless loop that just eats up more and more memory.
I don't know how correct it is but, personally, to re-write this function, I'd try to construct it into a quadratic loop.
for(initial;constraint;advance){ for (initial;constraint;advance) {
} }
Not sure how exactly you mean. Although I begin to suspect that the stackoverflow is due to an infinite loop, not the recursion itself. I'll keep looking. -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=52492 --- Comment #8 from David Kahurani <k.kahurani(a)gmail.com> --- (In reply to Fabian Maurer from comment #7)
I don't know how correct it is but, personally, to re-write this function, I'd try to construct it into a quadratic loop.
for(initial;constraint;advance){ for (initial;constraint;advance) {
} }
Not sure how exactly you mean.
I realized that the solution I had in my mind would be performance intensive. Probably so very much so that it would not be viable. So, well, never mind I said that. -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=52492 --- Comment #9 from Fabian Maurer <dark.shadow4(a)web.de> --- Created attachment 74623 --> https://bugs.winehq.org/attachment.cgi?id=74623 Patch to keep precision in flatten_bezier Attaching a patch to avoid the issue. IMHO the issue is that during a calculation we multiply two number together, losing precision in the last digits. Could you test if that works for you? Especially the original application would be interesting. @Rob F
I have tried replacing the float "==" in gdiplus/graphicspath.c:flatten_bezier with an "isclose" variation using the FLT_EPSILON and the problem appears fixed. However, I'm not sure if this is really the best solution.
May I ask what exactly you did? Also, could I get permission to include your tests when I try to submit that as a fix? -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=52492 --- Comment #10 from Rob F <rjfeuerbach(a)gmail.com> ---
@Rob F
May I ask what exactly you did?
Also, could I get permission to include your tests when I try to submit that as a fix?
Certainly -- please feel free to incorporate the tests that were originally submitted. The problem was the limited precision of the floating-point calculations can result in the equality-test failing. The patch I have been using locally replaces the equality test with a taxi-cab distance check of the closeness between the end-points and mid-point against flatness: .... mp[2].X = (mp[1].X + mp[3].X) / 2.0; mp[2].Y = (mp[1].Y + mp[3].Y) / 2.0; pt = end->pt; pt_st = start->pt; /* test for closely spaced points to avoid limited-precision errors in flatness check */ if((fabs(pt.X - mp[2].X) + fabs(pt.Y - mp[2].Y) + fabs(pt_st.X - mp[2].X) + fabs(pt_st.Y - mp[2].Y) ) <= flatness) return TRUE; /* check flatness as a half of distance between middle point and a linearized path */ .... There are other places in the wine codebase (opengl32/wgl.c:bezier_approximate is one) that do something similar. -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=52492 --- Comment #11 from David Kahurani <k.kahurani(a)gmail.com> --- (In reply to Rob F from comment #10)
@Rob F
May I ask what exactly you did?
Also, could I get permission to include your tests when I try to submit that as a fix?
Certainly -- please feel free to incorporate the tests that were originally submitted. The problem was the limited precision of the floating-point calculations can result in the equality-test failing.
I wonder why you would flatten to a flatness of 1.0 because this is probably the default flatness when drawing, unless I am terribly mistaken. -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=52492 --- Comment #12 from Fabian Maurer <dark.shadow4(a)web.de> --- (In reply to Rob F from comment #10)
@Rob F
May I ask what exactly you did?
Also, could I get permission to include your tests when I try to submit that as a fix?
Certainly -- please feel free to incorporate the tests that were originally submitted. The problem was the limited precision of the floating-point calculations can result in the equality-test failing.
The patch I have been using locally replaces the equality test with a taxi-cab distance check of the closeness between the end-points and mid-point against flatness:
.... mp[2].X = (mp[1].X + mp[3].X) / 2.0; mp[2].Y = (mp[1].Y + mp[3].Y) / 2.0;
pt = end->pt; pt_st = start->pt; /* test for closely spaced points to avoid limited-precision errors in flatness check */ if((fabs(pt.X - mp[2].X) + fabs(pt.Y - mp[2].Y) + fabs(pt_st.X - mp[2].X) + fabs(pt_st.Y - mp[2].Y) ) <= flatness) return TRUE;
/* check flatness as a half of distance between middle point and a linearized path */ ....
Seems like a sensible approach to me. Although I admit I don't understand why you just add up all the differences, why not sqrt to get the distance between the points? And don't you need flatness * 0.5 like below? Don't take that as critique though, I just don't understand what exactly you're doing. While we're at it, do you plan to send this to wine? IMHO you got a good fix, or a possibly at least a good start. If there's need for improvement, Wine devs will point it out, and they know a lot more than me. -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=52492 --- Comment #13 from Rob F <rjfeuerbach(a)gmail.com> --- (In reply to Fabian Maurer from comment #12)
Seems like a sensible approach to me. Although I admit I don't understand why you just add up all the differences, why not sqrt to get the distance between the points? And don't you need flatness * 0.5 like below? Don't take that as critique though, I just don't understand what exactly you're doing.
While we're at it, do you plan to send this to wine? IMHO you got a good fix, or a possibly at least a good start. If there's need for improvement, Wine devs will point it out, and they know a lot more than me.
I chose the taxi-cab distance to (needlessly) avoid more expensive calls. The original test functioned as a stopping condition for the recursive calls, and I was just trying to make the stopping condition less strict, since the original test was failing to stop. The flatness * 0.5 could be added. A patch with this fix and the test-modification was submitted in Feb 2022, but was not accepted as-it-was. (Adding a test that causes a stack-overflow did not work well.) I'd be happy if someone fixed the issue, with my solution or another one. In Feb 2022, the problem was only evident on the 64-bit debian test platform, and of course, the 64-bit MacOS I was using. -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=52492 --- Comment #14 from Fabian Maurer <dark.shadow4(a)web.de> --- I see, thanks for the explanation. If you want, I can see what I can do. But I have a few open MRs already that I want to get in first, so it might take some time. -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=52492 --- Comment #15 from David Kahurani <k.kahurani(a)gmail.com> --- Created attachment 74912 --> https://bugs.winehq.org/attachment.cgi?id=74912 modified patch (In reply to Fabian Maurer from comment #14)
I see, thanks for the explanation. If you want, I can see what I can do. But I have a few open MRs already that I want to get in first, so it might take some time.
Hey Fabian. I modified the patch(conversion from recursive to iterative) and the code seems to work perfectly. The modification was to remove the list nodes if they're no longer needed which fixes the problem with too much memory usage. You can see the changes I made in the attached patch. Basically adding jobs to the tail of the list and removing nodes which are no longer required. Can you please submit the patch? -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=52492 --- Comment #16 from Fabian Maurer <dark.shadow4(a)web.de> ---
I modified the patch(conversion from recursive to iterative) and the code seems to work perfectly.
The modification was to remove the list nodes if they're no longer needed which fixes the problem with too much memory usage. You can see the changes I made in the attached patch. Basically adding jobs to the tail of the list and removing nodes which are no longer required.
The conversion to iterative should not fix the issue, it would only turn the stackoverflow into an infinite loop. Did you do the reverse check, aka that removing your modifications breaks the code again? Because just removing list nodes when they're no longer needed might prevent memory issues, but doesn't fix the infinite loop. Keep in mind that compiler optimizations might mess with your results. -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=52492 --- Comment #17 from Fabian Maurer <dark.shadow4(a)web.de> --- Created a MR for making it iterative here: https://gitlab.winehq.org/wine/wine/-/merge_requests/3394 After that I planned to propose the fix as https://gitlab.winehq.org/DarkShadow44/wine/-/tree/gdiplus_2 Does this branch work for you? -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=52492 --- Comment #18 from David Kahurani <k.kahurani(a)gmail.com> --- (In reply to Fabian Maurer from comment #17)
Created a MR for making it iterative here: https://gitlab.winehq.org/wine/wine/-/merge_requests/3394
After that I planned to propose the fix as https://gitlab.winehq.org/DarkShadow44/wine/-/tree/gdiplus_2
Does this branch work for you?
Yes, the second MR does work and produces a curve that looks similar to the unflattened curve. I just noticed my modification, mentioned earlier is broken which was making the making me think that the problem is solved but anyways, that's mostly irrelevant here. I don't know, maybe we shouldn't bother converting from recursive to iterative and just fix the problem with accuracy? -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=52492 Fabian Maurer <dark.shadow4(a)web.de> changed: What |Removed |Added ---------------------------------------------------------------------------- Resolution|--- |FIXED Fixed by SHA1| |36c3a51d6abbdba4054e02c2a10 | |b9fd38f8a3d5d Status|NEW |RESOLVED --- Comment #19 from Fabian Maurer <dark.shadow4(a)web.de> --- Fixed by https://gitlab.winehq.org/wine/wine/-/commit/36c3a51d6abbdba4054e02c2a10b9fd... -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=52492 --- Comment #20 from Fabian Maurer <dark.shadow4(a)web.de> --- @Rob F Could you please test with https://gitlab.winehq.org/wine/wine/-/merge_requests/3461/ ? Just to make sure the new changes don't break your application. -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=52492 Alexandre Julliard <julliard(a)winehq.org> changed: What |Removed |Added ---------------------------------------------------------------------------- Status|RESOLVED |CLOSED --- Comment #21 from Alexandre Julliard <julliard(a)winehq.org> --- Closing bugs fixed in 8.14. -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
participants (1)
-
WineHQ Bugzilla