[PATCH] tsort: avoid use-after-free

[Eric Roshan-Eisner]

The old code freed nodes inline after processing them.
This works fine unless the input has cycles, in which case future iterations will try to decrement in_count for the freed nodes.
The new code defers freeing all nodes until the processing is done.
---
 coreutils/tsort.c | 24 ++++++++++++++++--------
 1 file changed, 16 insertions(+), 8 deletions(-)

diff --git a/coreutils/tsort.c b/coreutils/tsort.c
index dedb65b15..15c8ecbf2 100644
--- a/coreutils/tsort.c
+++ b/coreutils/tsort.c
@@ -101,6 +101,8 @@ int tsort_main(int argc UNUSED_PARAM, char **argv)
 	ssize_t len;
 	struct node *a;
 	int cycles;
+	unsigned i;
+	unsigned remaining;
 
 	INIT_G();
 
@@ -152,16 +154,17 @@ int tsort_main(int argc UNUSED_PARAM, char **argv)
 	 *   - if any nodes are left, they form cycles.
 	 */
 	cycles = 0;
-	while (G.nodes_len) {
+	remaining = G.nodes_len;
+
+	while (remaining) {
 		struct node *n;
-		unsigned i;
 
 		/* Search for first node with no incoming edges */
-		for (i = 0; i < G.nodes_len; i++) {
+		for (i = 0; i < remaining; i++) {
 			if (!G.nodes[i]->in_count)
 				break;
 		}
-		if (i == G.nodes_len) {
+		if (i == remaining) {
 			/* Must be a cycle; arbitraily break it at node 0 */
 			cycles++;
 			i = 0;
@@ -170,17 +173,22 @@ int tsort_main(int argc UNUSED_PARAM, char **argv)
 #endif
 		}
 
-		/* Remove the node (need no longer maintain sort) */
+		/* Swap the node to the back (need no longer maintain sort) */
 		n = G.nodes[i];
-		G.nodes[i] = G.nodes[--G.nodes_len];
+		G.nodes[i] = G.nodes[--remaining];
+		G.nodes[remaining] = n;
 
 		/* 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);
+        }
+
+	/* Free all nodes */
+	for (i = 0; i < G.nodes_len; i++) {
+		free(G.nodes[i]->out);
+		free(G.nodes[i]);
 	}
 	free(G.nodes);
 
-- 
2.39.0.314.g84b9a713c41-goog