Applied, thank you.
On Tue, Aug 22, 2023 at 10:38 AM Ron Yorston <[email protected]> wrote: > > When the input data contained a cycle it was possible for tsort to > attempt to access freed nodes. This sometimes resulted in the > test case 'echo a b b a | tsort' crashing. > > Don't free nodes when they're removed from the graph. > > function old new delta > tsort_main 621 596 -25 > ------------------------------------------------------------------------------ > (add/remove: 0/0 grow/shrink: 0/1 up/down: 0/-25) Total: -25 bytes > > Signed-off-by: Ron Yorston <[email protected]> > --- > coreutils/tsort.c | 20 +++++++++++++++++--- > 1 file changed, 17 insertions(+), 3 deletions(-) > > diff --git a/coreutils/tsort.c b/coreutils/tsort.c > index a451ed2ff..3e7aa48f4 100644 > --- a/coreutils/tsort.c > +++ b/coreutils/tsort.c > @@ -101,6 +101,10 @@ int tsort_main(int argc UNUSED_PARAM, char **argv) > ssize_t len; > struct node *a; > int cycles; > + unsigned i; > +#if ENABLE_FEATURE_CLEAN_UP > + unsigned max_len; > +#endif > > INIT_G(); > > @@ -152,9 +156,11 @@ int tsort_main(int argc UNUSED_PARAM, char **argv) > * - if any nodes are left, they form cycles. > */ > cycles = 0; > +#if ENABLE_FEATURE_CLEAN_UP > + max_len = G.nodes_len; > +#endif > while (G.nodes_len) { > struct node *n; > - unsigned i; > > /* Search for first node with no incoming edges */ > for (i = 0; i < G.nodes_len; i++) { > @@ -173,16 +179,24 @@ int tsort_main(int argc UNUSED_PARAM, char **argv) > /* Remove the node (need no longer maintain sort) */ > n = G.nodes[i]; > G.nodes[i] = G.nodes[--G.nodes_len]; > +#if ENABLE_FEATURE_CLEAN_UP > + /* Keep reference to removed node so it can be freed */ > + G.nodes[G.nodes_len] = n; > +#endif > > /* And remove its outgoing edges */ > for (i = 0; i < n->out_count; i++) > n->out[i]->in_count--; > - free(n->out); > > puts(n->name); > - free(n); > + } > +#if ENABLE_FEATURE_CLEAN_UP > + for (i = 0; i < max_len; i++) > + free(G.nodes[i].out); > + free(G.nodes[i]); > } > free(G.nodes); > +#endif > > fflush_stdout_and_exit(cycles ? 1 : 0); > } > -- > 2.41.0 > > _______________________________________________ > busybox mailing list > [email protected] > http://lists.busybox.net/mailman/listinfo/busybox _______________________________________________ busybox mailing list [email protected] http://lists.busybox.net/mailman/listinfo/busybox
