[Bug 60265] New: d2d1: ID2D1GeometrySink::Close() never completes on paths with coincident bezier nodes
http://bugs.winehq.org/show_bug.cgi?id=60265 Bug ID: 60265 Summary: d2d1: ID2D1GeometrySink::Close() never completes on paths with coincident bezier nodes Product: Wine Version: 11.16 Hardware: x86-64 OS: Linux Status: UNCONFIRMED Severity: normal Priority: P2 Component: d2d Assignee: wine-bugs@list.winehq.org Reporter: werner.bundschuh@pm.me Target Milestone: --- Distribution: --- Created attachment 81981 --> http://bugs.winehq.org/attachment.cgi?id=81981 Standalone reproducer (build with mingw, see bug description) # d2d1: ID2D1GeometrySink::Close() never completes on paths with coincident bezier nodes ## Summary `d2d_geometry_resolve_beziers()` subdivides overlapping bezier control triangles until they no longer overlap. When the underlying curves genuinely cross -- or when several nodes sit on (nearly) the same coordinates -- subdividing never separates them, and the loop only terminates once the control points become collinear in float precision. Every split appends a segment that is then tested against all earlier ones, so the segment count grows combinatorially. On a real world document this exhausts memory instead of finishing. ## Affected code `dlls/d2d1/geometry.c`, `d2d_geometry_resolve_beziers()`, first phase: /* Split overlapping bezier control triangles. */ while (d2d_geometry_get_next_bezier_segment_idx(geometry, &idx_p)) { d2d_geometry_get_first_bezier_segment_idx(geometry, &idx_q); while (idx_q.figure_idx < idx_p.figure_idx || idx_q.vertex_idx < idx_p.vertex_idx) { while (d2d_geometry_check_bezier_overlap(geometry, &idx_p, &idx_q)) { ... d2d_geometry_split_bezier(geometry, &idx_q or &idx_p); } d2d_geometry_get_next_bezier_segment_idx(geometry, &idx_q); } } Unchanged since 2187a1edb ("d2d1: Split overlapping bezier control triangles.", Henri Verbeet, 2017, Wine 2.15). The only termination condition is in `d2d_geometry_check_bezier_overlap()`: if (d2d_point_ccw(a[0], a[1], a[2]) == 0.0f || d2d_point_ccw(b[0], b[1], b[2]) == 0.0f) return FALSE; That is float exhaustion, not an algorithmic bound. ## Measurements Instrumenting the loop to record the subdivision depth per segment, on the attached reproducer: segments start end max depth avg depth 20 220 1544 25 5.51 40 872 2336 25 3.91 80 3312 14948 25 4.82 160 14144 54057 25 4.18 The maximum depth is exactly 25 in every run -- the point at which halving a control triangle with coordinates around 500 no longer changes the float32 mantissa. The average depth is 4 to 5.5, so only a small tail of pairs runs all the way down; those are the pairs whose curves actually cross. Wall clock for `ID2D1GeometrySink::Close()` on the reproducer, Wine 11.16 release build, measured A/B/A/B interleaved on an otherwise unchanged machine (medians; the two runs per variant agree within 3%): segments unpatched patched factor 20 39.2 ms 20.9 ms 1.87 40 85.1 ms 56.7 ms 1.50 80 3114.2 ms 1844.2 ms 1.69 160 42132.9 ms 28794.4 ms 1.46 Note that the reproducer is dominated by the overlap tests, not by the array shifting, so it mostly exercises the subdivision bound. The array shifting is what dominates in the real world case below, where the unpatched version does not finish at all and no ratio can be given. ## Real world case Affinity Designer 3 (via Wine) freezes when selecting a specific object in a customer document. The object contains a cluster of nodes at practically identical coordinates. Sampled with gdb, 30 samples over three minutes, 100% of the time is in `memmove` reached through: d2d_geometry_sink_Close -> d2d_geometry_resolve_beziers -> d2d_geometry_split_bezier -> d2d_figure_insert_vertex -> memmove The figure had grown to roughly 915,000 vertices and was still growing by about 23,000 per minute after eight minutes; each insertion memmoves 1.3 to 6.5 MB. The operation never completes. ## Two independent problems 1. `d2d_geometry_split_bezier()` inserts into the middle of the figure's vertex, vertex type and control arrays. That is O(n) per split, so the phase is O(splits * vertices) -- this is what dominates in the real world case. The splitting phase only ever reads three points per segment (`d2d_geometry_check_bezier_overlap`, `d2d_geometry_bezier_ccw`), so the array bookkeeping is not needed until the phase ends. 2. The number of splits is not bounded by anything except float precision. ## Reproducer `repro.c` (attached) builds a closed path of N quadratic bezier segments whose control points sit near the centre, so the control triangles overlap, and times `ID2D1GeometrySink::Close()`. No render target is needed. Build with mingw: x86_64-w64-mingw32-gcc -O2 -o repro.exe repro.c -ld2d1 -lole32 -lm ## Notes Also observed while reading this code, not addressed here: the middle loop condition while (idx_q.figure_idx < idx_p.figure_idx || idx_q.vertex_idx < idx_p.vertex_idx) is an OR where lexicographic ordering is intended. It happens to be safe only because q always meets p exactly; the return value of the following `d2d_geometry_get_next_bezier_segment_idx()` is not checked, so if q ever ran past p the loop would index `figures[figure_count]`. -- 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.
http://bugs.winehq.org/show_bug.cgi?id=60265 --- Comment #1 from werner.bundschuh@pm.me --- Created attachment 81982 --> http://bugs.winehq.org/attachment.cgi?id=81982 Patch 1/2: avoid shifting the figure arrays while splitting (no behaviour change) -- 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.
http://bugs.winehq.org/show_bug.cgi?id=60265 --- Comment #2 from werner.bundschuh@pm.me --- Created attachment 81983 --> http://bugs.winehq.org/attachment.cgi?id=81983 Patch 2/2: bound subdivision (changes rendering output for degenerate input) -- 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.
http://bugs.winehq.org/show_bug.cgi?id=60265 --- Comment #3 from werner.bundschuh@pm.me --- Follow-up measurement from the real world document, with the two attached patches applied and the subdivision depth instrumented. The document triggers 6805 calls to d2d_geometry_resolve_beziers(). 6759 of them need no splitting at all. The problematic object is one figure: bezier segments before splitting: 6994 bezier segments after splitting: 10109 growth factor: 1.45 maximum subdivision depth: 8 (the cap) average subdivision depth: 0.92 Two things worth noting for the review of patch 2/2: - The depth cap is what does the work. It binds -- the maximum depth is exactly the cap value -- and without it those pairs run to the float exhaustion depth of 25. Seventeen further levels of halving on the affected pairs is what produced the runaway; before the patches the figure had passed 900,000 vertices and the process was killed by the OOM killer at 66 GB of virtual memory. - The segment budget (16x the initial count) never triggered, not once in the whole session. With a growth factor of 1.45 it is nowhere near. It is a backstop, not the mechanism, and could be dropped or raised freely without affecting this case. With the patches, selecting the object takes 2-5 seconds instead of never completing, and the rendering is visually correct. -- 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.
http://bugs.winehq.org/show_bug.cgi?id=60265 Ken Sharp <imwellcushtymelike@gmail.com> changed: What |Removed |Added ---------------------------------------------------------------------------- Keywords| |patch, testcase --- Comment #4 from Ken Sharp <imwellcushtymelike@gmail.com> --- Patches are not picked up from Bugzilla. See https://gitlab.winehq.org/wine/wine/-/wikis/Submitting-Patches Note that patches written by AI will not be accepted. -- 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