arena: fix xalloc minaddr|maxaddr

Two problems:
- if you had a single segment that contained minaddr, we'd skip that
segment and start with the *next* one.  Not only did this mean we
skipped a perfectly good segment that could have had the fix, but we
might not have a *next* segment, causing an OOM / failure.

The fix was to find the BT that contained minaddr, not just the strict
upper bound.  This means we need to handle the case where BT contains
minaddr: hence try_start and try_size.

- We'd scan the list of all nodes starting from the upper bound (and now
equality), regardless of whether or not they are free.  Yikes!

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>

kern/src/arena.c

diff --git a/kern/src/arena.c b/kern/src/arena.c
index 4ebc089..ff53d92 100644
--- a/kern/src/arena.c
+++ b/kern/src/arena.c
@@ -882,17 +882,24 @@
 	 * is not. */
 }
 
-/* Helper.  We want the first bt >= mindaddr, with prev < minaddr. */
+/* Helper.  We want either the BT containing minaddr, or the closest to it
+ * (above).  There might be no BTs containing it, above it, or below it. */
 static bool __found_least_upper_btag(struct btag *bt, uintptr_t minaddr)
 {
 	struct rb_node *prev;
+	struct btag *btp;
 
-	if (bt->start < minaddr)
-		return FALSE;
+	if (bt->start + bt->size <= minaddr)
+		return FALSE;	/* We are strictly below */
+	if (bt->start <= minaddr)
+		return TRUE;	/* We contain it */
 	prev = rb_prev(&bt->all_link);
 	if (!prev)
-		return TRUE;
-	if (container_of(prev, struct btag, all_link)->start < minaddr)
+		return TRUE;	 /* We are above, but no one else below */
+	/* We are above and not containing.  If our prev is below min, then
+	 * we're it. */
+	btp = container_of(prev, struct btag, all_link);
+	if (btp->start + btp->size <= minaddr)
 		return TRUE;
 	return FALSE;
 }
@@ -904,9 +911,9 @@
 {
 	struct rb_node *node = arena->all_segs.rb_node;
 	struct btag *bt;
-	uintptr_t try;
+	uintptr_t try, try_start, try_size;
 
-	/* Find the first bt >= minaddr */
+	/* Find the first BT containing, or >= minaddr */
 	while (node) {
 		bt = container_of(node, struct btag, all_link);
 		if (__found_least_upper_btag(bt, minaddr))
@@ -917,10 +924,20 @@
 			node = node->rb_right;
 	}
 	/* Now we're probably at the first start point (or there's no node).
-	 * Just scan from here. */
+	 * Just scan from here.  The first node could contain minaddr, so we
+	 * need to round up.  Also note that this is *all* segs, including
+	 * non-free ones. */
 	for (/* node set */; node; node = rb_next(node)) {
 		bt = container_of(node, struct btag, all_link);
-		try = __find_sufficient(bt->start, bt->size, size, np2sb, phase,
+		if (bt->status != BTAG_FREE)
+			continue;
+		try_start = bt->start;
+		try_size = bt->size;
+		if (bt->start < minaddr) {
+			try_start = minaddr;
+			try_size = bt->size - (minaddr - bt->start);
+		}
+		try = __find_sufficient(try_start, try_size, size, np2sb, phase,
 		                        nocross);
 		if (!try)
 			continue;