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>
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;
