GitLab

Reviewing !1687 (merged) led me to notice that Graphviz is unnecessarily carrying two implementations of RectArea. This function can be written once in a width-independent way. While working on unifying these two, I realized at least one of the existing overflow checks is broken:

...
  unsigned int area;
...
    long long a_test = area * (r->boundary[i + NUMDIMS] - r->boundary[i]);
    if (a_test > UINT_MAX) {
...

The expression r->boundary[i + NUMDIMS] - r->boundary[i] has type int and is promoted to unsigned int for the multiplication. Unsigned multiplication wraps. Therefore, area * (r->boundary[i + NUMDIMS] - r->boundary[i]) can never be greater than UINT_MAX.

I committed what I believe is a fix in a branch. However, it failed CI. Investigating leads me to conclude the graph rtest/graphs/root.gv actually triggers this overflow but has never been noticed before because the check is broken as described above.

You can see this by applying the following diff to the head of master, 3bd29cca:

diff --git lib/label/rectangle.c lib/label/rectangle.c
index a3285895d..e5eb0fd51 100644
--- lib/label/rectangle.c
+++ lib/label/rectangle.c
@@ -134,7 +134,10 @@ unsigned int RectArea(Rect_t * r)
      * XXX add overflow checks
      */
     area = 1;
+    printf("RectArea calculations:\n");
     for (i = 0; i < NUMDIMS; i++) {
+      printf(" area = %u, r->boundary[i + NUMDIMS] - r->boundary[i] = %d\n",
+        area, r->boundary[i + NUMDIMS] - r->boundary[i]);
       long long a_test = area * (r->boundary[i + NUMDIMS] - r->boundary[i]);
       if( a_test > UINT_MAX) {
        agerr (AGERR, "label: area too large for rtree\n");

On x86-64 Linux, the command dot -Kcirco -Tgv -o /dev/null rtest/graphs/root.gv produces the attached log:

rectarea-overflow.log.xz

There are numerous area, r->boundary[i + NUMDIMS] - r->boundary[i] pairs in this log whose product exceeds UINT_MAX but the overflow error message is not triggered on master. It is triggered after applying my commit from above.

What is the correct fix to the test suite? Drop this graph? Require it to fail?