From 00a066754c31ed45661f688132a221b9ad02feaf Mon Sep 17 00:00:00 2001 From: Matthew Fernandez Date: Fri, 24 Dec 2021 10:11:06 -0800 Subject: [PATCH] remove reused buffer in spline routing Code in routespl.c used a long-lived buffer, `ps`, that it resized to deal with various operations. This made the code thread-unsafe, and note that there are also various work arounds in routespl.c to deal with re-entrancy which is complicated by this design. This commit rephrases `simpleSplineRoute` and `_routesplines` to dynamically allocate a fresh buffer for each operation. The ergonomics cost of this is that callers of `simpleSplineRoute`, `routesplines`, and `routepolylines` now need to eventually free the returned pointer. This is unfortunately fairly noisy to deal with in C and would have been cleaner in C++. In future, this direction should probably be taken further to allow `routesplinesinit` and `routesplinesterm` to be removed. This design that relies on static globals is incompatible with multi-threading, so if Graphviz ever wants to support multi-threading, this will need to be removed. Note that this commit introduce two new warnings (for the `calloc` calls with `int` values). The cost seems worth it and hopefully these warnings can be removed in future. This change has a performance impact. For smaller graphs, this likely slightly degrades performance due to repeated small allocations that previously would not have been required. For larger graphs, this perhaps improves performance as the allocator no longer (spuriously) believes it needs to retain the contents of `ps` across calls. --- lib/common/routespl.c | 33 ++++++----------------- lib/dotgen/dotsplines.c | 59 ++++++++++++++++++++++++++++++----------- 2 files changed, 52 insertions(+), 40 deletions(-) diff --git a/lib/common/routespl.c b/lib/common/routespl.c index dc612342c..9d31d598b 100644 --- a/lib/common/routespl.c +++ b/lib/common/routespl.c @@ -23,15 +23,12 @@ static int nedges, nboxes; /* total no. of edges and boxes used in routing */ static int routeinit; /* static data used across multiple edges */ -static pointf *ps; /* final spline points */ -static int maxpn; /* size of ps[] */ static Ppoint_t *polypoints; /* vertices of polygon defined by boxes */ static int polypointn; /* size of polypoints[] */ static Pedge_t *edges; /* polygon edges passed to Proutespline */ static int edgen; /* size of edges[] */ static int checkpath(int, boxf*, path*); -static int mkspacep(int size); static void printpath(path * pp); #ifdef DEBUG static void printboxes(int boxn, boxf* boxes) @@ -249,8 +246,11 @@ simpleSplineRoute (pointf tp, pointf hp, Ppoly_t poly, int* n_spl_pts, return NULL; } - if (mkspacep(spl.pn)) + pointf *ps = calloc(spl.pn, sizeof(ps[0])); + if (ps == NULL) { + agerr(AGERR, "cannot allocate ps\n"); return NULL; + } for (i = 0; i < spl.pn; i++) { ps[i] = spl.ps[i]; } @@ -266,11 +266,6 @@ int routesplinesinit() { if (++routeinit > 1) return 0; - if (!(ps = calloc(PINC, sizeof(pointf)))) { - agerr(AGERR, "routesplinesinit: cannot allocate ps\n"); - return 1; - } - maxpn = PINC; #ifdef DEBUG if (Show_boxes) { for (int i = 0; Show_boxes[i]; i++) @@ -290,7 +285,6 @@ routesplinesinit() void routesplinesterm() { if (--routeinit > 0) return; - free(ps); if (Verbose) fprintf(stderr, "routesplines: %d edges, %d boxes %.2f sec\n", @@ -559,8 +553,11 @@ static pointf *_routesplines(path * pp, int *npoints, int polyline) } #endif } - if (mkspacep(spl.pn)) + pointf *ps = calloc(spl.pn, sizeof(ps[0])); + if (ps == NULL) { + agerr(AGERR, "cannot allocate ps\n"); return NULL; /* Bailout if no memory left */ + } for (bi = 0; bi < boxn; bi++) { boxes[bi].LL.x = INT_MAX; @@ -784,20 +781,6 @@ static int checkpath(int boxn, boxf* boxes, path* thepath) return 0; } -static int mkspacep(int size) -{ - if (size > maxpn) { - int newmax = maxpn + (size / PINC + 1) * PINC; - ps = realloc(ps, newmax * sizeof(pointf)); - if (!ps) { - agerr(AGERR, "cannot re-allocate ps\n"); - return 1; - } - maxpn = newmax; - } - return 0; -} - static void printpath(path * pp) { int bi; diff --git a/lib/dotgen/dotsplines.c b/lib/dotgen/dotsplines.c index a40e86a11..f95ab8da6 100644 --- a/lib/dotgen/dotsplines.c +++ b/lib/dotgen/dotsplines.c @@ -1033,7 +1033,6 @@ static int edgelblcmpfn(edge_t** ptr0, edge_t** ptr1) static void makeSimpleFlatLabels (node_t* tn, node_t* hn, edge_t** edges, int ind, int cnt, int et, int n_lbls) { - pointf *ps; Ppoly_t poly; int pn; edge_t* e = edges[ind]; @@ -1120,12 +1119,16 @@ makeSimpleFlatLabels (node_t* tn, node_t* hn, edge_t** edges, int ind, int cnt, } poly.pn = 8; poly.ps = (Ppoint_t*)points; - ps = simpleSplineRoute (tp, hp, poly, &pn, et == EDGETYPE_PLINE); - if (pn == 0) return; + pointf *ps = simpleSplineRoute(tp, hp, poly, &pn, et == EDGETYPE_PLINE); + if (pn == 0) { + free(ps); + return; + } ED_label(e)->pos.x = ctrx; ED_label(e)->pos.y = ctry; ED_label(e)->set = TRUE; clip_and_install(e, aghead(e), ps, pn, &sinfo); + free(ps); } /* edges with no labels */ @@ -1172,9 +1175,13 @@ makeSimpleFlatLabels (node_t* tn, node_t* hn, edge_t** edges, int ind, int cnt, } poly.pn = 8; poly.ps = (Ppoint_t*)points; - ps = simpleSplineRoute (tp, hp, poly, &pn, et == EDGETYPE_PLINE); - if (pn == 0) return; + pointf *ps = simpleSplineRoute(tp, hp, poly, &pn, et == EDGETYPE_PLINE); + if (pn == 0) { + free(ps); + return; + } clip_and_install(e, aghead(e), ps, pn, &sinfo); + free(ps); } free (earray); @@ -1428,6 +1435,7 @@ make_flat_labeled_edge(graph_t* g, spline_info_t* sp, path* P, edge_t* e, int et { node_t *tn, *hn, *ln; pointf *ps; + bool ps_needs_free = false; pathend_t tend, hend; boxf lb; int i, pn, ydelta; @@ -1483,11 +1491,17 @@ make_flat_labeled_edge(graph_t* g, spline_info_t* sp, path* P, edge_t* e, int et for (size_t j = 0; j < boxn; j++) add_box(P, boxes[j]); for (i = hend.boxn - 1; i >= 0; i--) add_box(P, hend.boxes[i]); + ps_needs_free = true; if (et == EDGETYPE_SPLINE) ps = routesplines(P, &pn); else ps = routepolylines(P, &pn); - if (pn == 0) return; + if (pn == 0) { + free(ps); + return; + } } clip_and_install(e, aghead(e), ps, pn, &sinfo); + if (ps_needs_free) + free(ps); } /* make_flat_bottom_edges: @@ -1500,8 +1514,6 @@ make_flat_bottom_edges(graph_t* g, spline_info_t* sp, path * P, edge_t ** edges, int j, i, r; double stepx, stepy, vspace; rank_t* nextr; - int pn; - pointf *ps; pathend_t tend, hend; tn = agtail(e); @@ -1551,11 +1563,16 @@ make_flat_bottom_edges(graph_t* g, spline_info_t* sp, path * P, edge_t ** edges, for (size_t k = 0; k < boxn; k++) add_box(P, boxes[k]); for (j = hend.boxn - 1; j >= 0; j--) add_box(P, hend.boxes[j]); + pointf *ps = NULL; + int pn = 0; if (splines) ps = routesplines(P, &pn); else ps = routepolylines(P, &pn); - if (pn == 0) + if (pn == 0) { + free(ps); return; + } clip_and_install(e, aghead(e), ps, pn, &sinfo); + free(ps); P->nbox = 0; } } @@ -1578,8 +1595,7 @@ make_flat_edge(graph_t* g, spline_info_t* sp, path * P, edge_t ** edges, int ind edge_t *e; int j, i, r, isAdjacent; double stepx, stepy, vspace; - int tside, hside, pn; - pointf *ps; + int tside, hside; pathend_t tend, hend; fwdedge.out.base.data = (Agrec_t*)&fwdedgei; @@ -1672,11 +1688,16 @@ make_flat_edge(graph_t* g, spline_info_t* sp, path * P, edge_t ** edges, int ind for (size_t k = 0; k < boxn; k++) add_box(P, boxes[k]); for (j = hend.boxn - 1; j >= 0; j--) add_box(P, hend.boxes[j]); + pointf *ps = NULL; + int pn = 0; if (et == EDGETYPE_SPLINE) ps = routesplines(P, &pn); else ps = routepolylines(P, &pn); - if (pn == 0) + if (pn == 0) { + free(ps); return; + } clip_and_install(e, aghead(e), ps, pn, &sinfo); + free(ps); P->nbox = 0; } } @@ -1783,10 +1804,9 @@ make_regular_edge(graph_t* g, spline_info_t* sp, path * P, edge_t ** edges, int Agedgeinfo_t fwdedgeai, fwdedgebi, fwdedgei; Agedgepair_t fwdedgea, fwdedgeb, fwdedge; edge_t *e, *fe, *le, *segfirst; - pointf *ps; pathend_t tend, hend; boxf b; - int sl, si, smode, i, j, dx, pn, hackflag, longedge; + int sl, si, smode, i, j, dx, hackflag, longedge; static pointf* pointfs; static pointf* pointfs2; static int numpts; @@ -1888,6 +1908,8 @@ make_regular_edge(graph_t* g, spline_info_t* sp, path * P, edge_t ** edges, int assert(boxes.size <= (size_t)INT_MAX && "integer overflow"); completeregularpath(P, segfirst, e, &tend, &hend, boxes.data, (int)boxes.size, 1); + pointf *ps = NULL; + int pn = 0; if (is_spline) ps = routesplines(P, &pn); else { ps = routepolylines (P, &pn); @@ -1898,6 +1920,7 @@ make_regular_edge(graph_t* g, spline_info_t* sp, path * P, edge_t ** edges, int } } if (pn == 0) { + free(ps); boxes_free(&boxes); return; } @@ -1912,6 +1935,7 @@ make_regular_edge(graph_t* g, spline_info_t* sp, path * P, edge_t ** edges, int for (i = 0; i < pn; i++) { pointfs[pointn++] = ps[i]; } + free(ps); e = straight_path(ND_out(hn).list[0], sl, pointfs, &pointn); recover_slack(segfirst, P); segfirst = e; @@ -1941,6 +1965,8 @@ make_regular_edge(graph_t* g, spline_info_t* sp, path * P, edge_t ** edges, int completeregularpath(P, segfirst, e, &tend, &hend, boxes.data, (int)boxes.size, longedge); boxes_free(&boxes); + pointf *ps = NULL; + int pn = 0; if (is_spline) ps = routesplines(P, &pn); else ps = routepolylines (P, &pn); if (et == EDGETYPE_LINE && pn > 4) { @@ -1952,8 +1978,10 @@ make_regular_edge(graph_t* g, spline_info_t* sp, path * P, edge_t ** edges, int ps[3] = ps[2] = ps[pn-1]; pn = 4; } - if (pn == 0) + if (pn == 0) { + free(ps); return; + } if (pointn + pn > numpts) { numpts = 2*(pointn+pn); pointfs = RALLOC(numpts, pointfs, pointf); @@ -1961,6 +1989,7 @@ make_regular_edge(graph_t* g, spline_info_t* sp, path * P, edge_t ** edges, int for (i = 0; i < pn; i++) { pointfs[pointn++] = ps[i]; } + free(ps); recover_slack(segfirst, P); hn = hackflag ? aghead(&fwdedgeb.out) : aghead(e); } -- 2.40.0