From 7bd8d205ee969452986b80de0dcd82ec9dff8180 Mon Sep 17 00:00:00 2001 From: Vito Caputo Date: Sun, 3 Sep 2023 14:46:50 -0700 Subject: modules/voronoi: spot-fix a crash Phil reported The repro is: --seed=0x64f6820b '--module=compose,layers=blank\,pixbounce\\\,pixmap_size\\\=0.8\\\,pixmap\\\=err\,pixbounce\\\,pixmap_size\\\=0.4\\\,pixmap\\\=ignignokt,texture=voronoi\,cells\=512\,randomize\=on' '--video=mem,size=3840x2160' The major culprit seems to be the combination of high resolution, and small number of voronoi cells (cells=512), with randomize=on which exercises jumpfill every frame. The way jumpfill is implemented currently is racy by design to allow threading, and mostly works fine despite not really being how the algorithm is intended to work. The assumption has been, something like: "the seeds are already placed before the threaded phase, so the threaded jumpfill should at least find stable seed cells in the face of racing against other tiles being jumpfilled simultaneously" But it appears that assumption isn't always true, in that we won't necessarily find one of the seed cells at the start of the jumpfill when there aren't that many cells (512) compared to the area of the voronoi (3840x2160). By noticing when we've finished a tile's jumpfill with remaining unassigned cells, we can just repeat the jumpfill, with time passed, and the other tiles will have made progress on their work propagating more knowledge of where cells are... so the subsequent pass will probably leave nothing unassigned. This approach sucks, but stops the crashing. It'd also be possible to just change the way cells are looked up so there's no potential for a NULL pointer dereference, just have some uninitialized cell color which gets shown erroneously in the output. That avoids the computational cost of repeating the tile's jumpfill, and likely nobody would notice the likely single pixel of error for a single frame. I'm just doing this quick and dirty fix to prevent the crashing for now, and would like to just revisit voronoi more thoroughly with an eye towards decoupling the voronoi cost from the resolution. It's a cheap hack the way there's a distance entry per pixel, done just to simplify the implementation when I slapped it together on a Zephyr train ride. --- src/modules/voronoi/voronoi.c | 24 ++++++++++++++++++++---- 1 file changed, 20 insertions(+), 4 deletions(-) diff --git a/src/modules/voronoi/voronoi.c b/src/modules/voronoi/voronoi.c index 0c06c1d..5b38705 100644 --- a/src/modules/voronoi/voronoi.c +++ b/src/modules/voronoi/voronoi.c @@ -126,9 +126,10 @@ static inline size_t voronoi_cell_origin_to_distance_idx(const voronoi_context_t } -static void voronoi_jumpfill_pass(voronoi_context_t *ctxt, v2f_t *db, v2f_t *ds, size_t step, const til_fb_fragment_t *fragment) +static size_t voronoi_jumpfill_pass(voronoi_context_t *ctxt, const v2f_t *db, const v2f_t *ds, size_t step, const til_fb_fragment_t *fragment) { - v2f_t dp = {}; + size_t n_unassigned = 0; + v2f_t dp = {}; dp.y = db->y; for (int y = 0; y < fragment->height; y++, dp.y += ds->y) { @@ -214,8 +215,13 @@ static void voronoi_jumpfill_pass(voronoi_context_t *ctxt, v2f_t *db, v2f_t *ds, VORONOI_JUMPFILL; } + + if (!d->cell) + n_unassigned++; } } + + return n_unassigned; } @@ -256,6 +262,7 @@ static void voronoi_calculate_distances_render_pass(voronoi_context_t *ctxt, con .x = fragment->x * ds.x - 1.f, .y = fragment->y * ds.y - 1.f, }; + size_t n_unassigned; /* An attempt at implementing https://en.wikipedia.org/wiki/Jump_flooding_algorithm */ @@ -275,8 +282,17 @@ static void voronoi_calculate_distances_render_pass(voronoi_context_t *ctxt, con * changing the cell pointers while we try dereference them. But all we really care about is finding * seeds reliably, and those should already be populated in the prepare phase. */ - for (size_t step = MAX(fragment->frame_width, fragment->frame_height) / 2; step > 0; step >>= 1) - voronoi_jumpfill_pass(ctxt, &db, &ds, step, fragment); + do { + for (size_t step = MAX(fragment->frame_width, fragment->frame_height) >> 1; step > 0; step >>= 1) + n_unassigned = voronoi_jumpfill_pass(ctxt, &db, &ds, step, fragment); + } while (n_unassigned); /* FIXME: there seems to be bug/race potential with sparse voronois at high res, + * especially w/randomize=on where jumpfill constantly recurs, it could leave a + * spurious NULL cell resulting in a segfault. The simplest thing to do here is + * just repeat the jumpfill for the fragment. It's inefficient, but rare, and doing + * voronoi as-is that way on a high resolution is brutally slow anyways, this all needs + * revisiting to make things scale better. So for now this prevents crashing, which is + * all that matters. + */ } -- cgit v1.2.3