From dc9492928702e6177639ae1a9cfc6c0974cdfbab Mon Sep 17 00:00:00 2001 From: Matthew Fernandez Date: Tue, 5 Jul 2022 17:24:05 -0700 Subject: [PATCH] cgraph: more uniform treatment of sequence IDs MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Sequence IDs are calculated using 64-bit counters in `Agclos_s`. But then the field used to store sequence IDs, `Agtag_s.seq`, is `sizeof(unsigned) * 8 - 4` bits wide, 28-bit on x86 and x86-64. As a result, the compiler believes IDs that exceed 2²⁸ - 1 can occur and overflow `Agtag_s.seq`: edge.c:213:30: warning: conversion from 'int' to 'unsigned int:28' may change value [-Wconversion] 213 | AGSEQ(in) = AGSEQ(out) = seq; | ^~~ ... graph.c: In function 'agopen1': graph.c:77:20: warning: conversion from 'uint64_t' {aka 'long unsigned int'} to 'unsigned int:28' may change value [-Wconversion] 77 | AGSEQ(g) = agnextseq(par, AGRAPH); | ^~~~~~~~~ ... node.c: In function 'newnode': node.c:76:16: warning: conversion from 'uint64_t' {aka 'long unsigned int'} to 'unsigned int:28' may change value [-Wconversion] 76 | AGSEQ(n) = seq; | ^~~ ... node.c: In function 'agnodebefore': node.c:359:22: warning: conversion from 'uint64_t' {aka 'long unsigned int'} to 'unsigned int:28' may change value [-Wconversion] 359 | AGSEQ(snd) = (g->clos->seq[AGNODE] + 2); | ^ In practice, ingesting a graph of this size is not achievable, so these overflows cannot occur. This change introduces assertions and casts in these cases to explain the assumptions to the compiler. It squashes the above warnings. In future, perhaps these fields should all be made to all consistently use the same type. --- lib/cgraph/cghdr.h | 3 +++ lib/cgraph/edge.c | 7 ++++--- lib/cgraph/graph.c | 5 ++++- lib/cgraph/node.c | 11 +++++++++-- 4 files changed, 20 insertions(+), 6 deletions(-) diff --git a/lib/cgraph/cghdr.h b/lib/cgraph/cghdr.h index b607ecea4..241973d14 100644 --- a/lib/cgraph/cghdr.h +++ b/lib/cgraph/cghdr.h @@ -72,6 +72,9 @@ int agstrclose(Agraph_t * g); /* ref string management */ void agmarkhtmlstr(char *s); +/// Mask of `Agtag_s.seq` width +enum { SEQ_MASK = (1 << (sizeof(unsigned) * 8 - 4)) - 1 }; + /* object set management */ Agnode_t *agfindnode_by_id(Agraph_t * g, IDTYPE id); uint64_t agnextseq(Agraph_t * g, int objtype); diff --git a/lib/cgraph/edge.c b/lib/cgraph/edge.c index 20ec358b5..5b8a7558d 100644 --- a/lib/cgraph/edge.c +++ b/lib/cgraph/edge.c @@ -8,6 +8,7 @@ * Contributors: Details at https://graphviz.org *************************************************************************/ +#include #include #include #include @@ -199,18 +200,18 @@ static Agedge_t *newedge(Agraph_t * g, Agnode_t * t, Agnode_t * h, { Agedgepair_t *e2; Agedge_t *in, *out; - int seq; (void)agsubnode(g,t,TRUE); (void)agsubnode(g,h,TRUE); e2 = agalloc(g, sizeof(Agedgepair_t)); in = &(e2->in); out = &(e2->out); - seq = agnextseq(g, AGEDGE); + uint64_t seq = agnextseq(g, AGEDGE); + assert((seq & SEQ_MASK) == seq && "sequence ID overflow"); AGTYPE(in) = AGINEDGE; AGTYPE(out) = AGOUTEDGE; AGID(in) = AGID(out) = id; - AGSEQ(in) = AGSEQ(out) = seq; + AGSEQ(in) = AGSEQ(out) = seq & SEQ_MASK; in->node = t; out->node = h; diff --git a/lib/cgraph/graph.c b/lib/cgraph/graph.c index a2f1aacb2..c688ee489 100644 --- a/lib/cgraph/graph.c +++ b/lib/cgraph/graph.c @@ -8,6 +8,7 @@ * Contributors: Details at https://graphviz.org *************************************************************************/ +#include #include #include @@ -74,7 +75,9 @@ Agraph_t *agopen1(Agraph_t * g) par = agparent(g); if (par) { - AGSEQ(g) = agnextseq(par, AGRAPH); + uint64_t seq = agnextseq(par, AGRAPH); + assert((seq & SEQ_MASK) == seq && "sequence ID overflow"); + AGSEQ(g) = seq & SEQ_MASK; dtinsert(par->g_dict, g); } if (!par || par->desc.has_attrs) diff --git a/lib/cgraph/node.c b/lib/cgraph/node.c index 5074655da..0f96ab778 100644 --- a/lib/cgraph/node.c +++ b/lib/cgraph/node.c @@ -8,6 +8,7 @@ * Contributors: Details at https://graphviz.org *************************************************************************/ +#include #include #include #include @@ -70,10 +71,12 @@ static Agnode_t *newnode(Agraph_t * g, IDTYPE id, uint64_t seq) { Agnode_t *n; + assert((seq & SEQ_MASK) == seq && "sequence ID overflow"); + n = agalloc(g, sizeof(Agnode_t)); AGTYPE(n) = AGNODE; AGID(n) = id; - AGSEQ(n) = seq; + AGSEQ(n) = seq & SEQ_MASK; n->root = agroot(g); if (agroot(g)->desc.has_attrs) (void)agbindrec(n, AgDataRecName, sizeof(Agattr_t), false); @@ -356,7 +359,11 @@ int agnodebefore(Agnode_t *fst, Agnode_t *snd) /* move snd out of the way somewhere */ n = snd; if (agapply (g, (Agobj_t *) n, (agobjfn_t) agnodesetfinger, n, FALSE) != SUCCESS) return FAILURE; - AGSEQ(snd) = (g->clos->seq[AGNODE] + 2); + { + uint64_t seq = g->clos->seq[AGNODE] + 2; + assert((seq & SEQ_MASK) == seq && "sequence ID overflow"); + AGSEQ(snd) = seq & SEQ_MASK; + } if (agapply (g, (Agobj_t *) n, (agobjfn_t) agnoderenew, n, FALSE) != SUCCESS) return FAILURE; n = agprvnode(g,snd); do { -- 2.40.0