From 34eab93cc6fbd18967810ae984b52615c995b199 Mon Sep 17 00:00:00 2001
From: Rusty Russell <rusty@rustcorp.com.au>
Date: Mon, 21 Mar 2011 13:44:22 +1030
Subject: [PATCH] foreach: fix case where iterators are not on the stack.

The foreach garbage collection assumed that iterators were all on the
stack, but they could be on the heap or a global (or static) variable.
We can prevent the heap case by tricky use of macros to complain on
any iterator which isn't a single token, but we can't prevent
globals/statics.

So, if an iterator already seems to be "off" the stack, mark it as
such and simply never free it.
---
 ccan/foreach/foreach.c               | 18 +++++--
 ccan/foreach/test/run-not-on-stack.c | 76 ++++++++++++++++++++++++++++
 2 files changed, 90 insertions(+), 4 deletions(-)
 create mode 100644 ccan/foreach/test/run-not-on-stack.c

diff --git a/ccan/foreach/foreach.c b/ccan/foreach/foreach.c
index 70040ee9..de79eb59 100644
--- a/ccan/foreach/foreach.c
+++ b/ccan/foreach/foreach.c
@@ -12,19 +12,28 @@ struct iter_info {
 	struct list_node list;
 	const void *index;
 	unsigned int i, num;
+	bool onstack;
 };
 
+/* Is pointer still downstack from some other onstack var? */
+static bool on_stack(const void *ptr, const void *onstack)
+{
+#if HAVE_STACK_GROWS_UPWARDS
+	return ptr < onstack;
+#else
+	return ptr > onstack;
+#endif
+}
+
 static void free_old_iters(const void *index)
 {
 	struct iter_info *i, *next;
 
 	list_for_each_safe(&iters, i, next, list) {
 		/* If we're re-using an index, free the old one.
-		 * Otherwise, if it's past i on the stack, it's old.  Don't
-		 * assume stack direction, but we know index is downstack. */
+		 * Otherwise, discard if it's passed off stack. */
 		if (i->index == index
-		    || (((uintptr_t)index < (uintptr_t)&i)
-			== ((uintptr_t)&i < (uintptr_t)i->index))) {
+		    || (i->onstack && !on_stack(i->index, &i))) {
 			list_del(&i->list);
 			free(i);
 		}
@@ -47,6 +56,7 @@ static struct iter_info *new_iter(const void *index)
 	struct iter_info *info = malloc(sizeof *info);
 	info->index = index;
 	info->i = info->num = 0;
+	info->onstack = on_stack(index, &info);
 	list_add(&iters, &info->list);
 	return info;
 };
diff --git a/ccan/foreach/test/run-not-on-stack.c b/ccan/foreach/test/run-not-on-stack.c
new file mode 100644
index 00000000..20895ecc
--- /dev/null
+++ b/ccan/foreach/test/run-not-on-stack.c
@@ -0,0 +1,76 @@
+#include <ccan/foreach/foreach.h>
+#include <ccan/tap/tap.h>
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+#include <ccan/foreach/foreach.c>
+
+static int global_i;
+static void *allocs[1000];
+static unsigned int num_allocs;
+
+static void iterate(unsigned int depth, bool done_global)
+{
+	int *i, expecti;
+	const char *expectp[] = { "hello", "there" };
+	const char **p;
+	int stack_i;
+
+	if (depth == 4)
+		return;
+
+	if (!done_global) {
+		expecti = 0;
+		foreach_int(global_i, 0, 1) {
+			ok1(global_i == expecti);
+			expecti++;
+			if (global_i == 0)
+				iterate(depth + 1, true);
+		}
+		ok1(expecti == 2);
+	}
+
+	i = allocs[num_allocs++] = malloc(sizeof(*i));
+	expecti = 0;
+	foreach_int(*i, 0, 1) {
+		ok1(*i == expecti);
+		expecti++;
+		if (*i == 0)
+			iterate(depth + 1, done_global);
+	}
+	ok1(expecti == 2);
+
+	p = allocs[num_allocs++] = malloc(sizeof(*p));
+	expecti = 0;
+	foreach_ptr(*p, "hello", "there") {
+		ok1(strcmp(expectp[expecti], *p) == 0);
+		expecti++;
+		if (expecti == 1)
+			iterate(depth + 1, done_global);
+	}
+	ok1(expecti == 2);
+	ok1(*p == NULL);
+
+	expecti = 0;
+	foreach_int(stack_i, 0, 1) {
+		ok1(stack_i == expecti);
+		expecti++;
+		if (stack_i == 0)
+			iterate(depth + 1, done_global);
+	}
+	ok1(expecti == 2);
+}
+
+int main(void)
+{
+	unsigned int i;
+	plan_tests(861);
+
+	iterate(0, false);
+
+	ok1(num_allocs < 1000);
+	for (i = 0; i < num_allocs; i++)
+		free(allocs[i]);
+
+	return exit_status();
+}
-- 
2.39.2