arena: allow a nocross xalloc() with a source arena
When we need to import segments from a parent arena to satisfy an
xalloc, we need to make sure that a successful import actually satisfies
the xalloc.
This doesn't seem easily solvable for min/maxaddr, short of pushing the
xalloc all the way down the chain or having some other inter-arena
interface. But it should be solvable for nocross, by getting a large
enough allocation.
Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
diff --git a/kern/src/arena.c b/kern/src/arena.c
index a9adc33..4ebc089 100644
--- a/kern/src/arena.c
+++ b/kern/src/arena.c
@@ -89,7 +89,7 @@
static struct btag *__get_from_freelists(struct arena *arena, int list_idx);
static bool __account_alloc(struct arena *arena, struct btag *bt, size_t size,
struct btag *new);
-static void *__xalloc_nextfit(struct arena *arena, size_t size, size_t align,
+static void *__xalloc_nextfit(struct arena *arena, size_t size, size_t np2sb,
size_t phase, size_t nocross);
static void __try_hash_resize(struct arena *arena, int flags,
void **to_free_addr, size_t *to_free_sz);
@@ -808,47 +808,54 @@
/* Helper: given a BT's start and size, return a starting address within the BT
* that satisfies the constraints. Returns 0 on failure.
*
- * The rough idea is to go from the start, round up to align, add the phase, and
- * see if it's still within the BT. The 'nocross' boundary (also an alignment)
- * complicates things a little. */
+ * The rough idea is to try the two potential starting alloc locations:
+ * - from the bt_start, round *down* to np2sb, which may be below the bt, then
+ * add the phase, which may go back in (or overflow).
+ * - add one more np2sb. this should be > bt_start (mod overflow), since
+ * ROUNDDOWN is -= less than np2sb.
+ *
+ * * The 'nocross' boundary (also an alignment) complicates things a little. */
static uintptr_t __find_sufficient(uintptr_t bt_start, size_t bt_size,
- size_t size, size_t align,
+ size_t size, size_t np2sb,
size_t phase, size_t nocross)
{
uintptr_t try;
size_t try_size;
- try = bt_start;
- try = ROUNDUP(try, align);
- try += phase;
- /* Wraparound due to phase. */
- if (try < bt_start)
- return 0;
- /* Check wraparound */
- if (try + size < try)
- return 0;
- /* Too big for BT, no chance. */
- if (try + size > bt_start + bt_size)
- return 0;
- if (nocross == 0)
- return try;
- /* Got to deal with nocross boundaries. If we round up from our
- * potential start and that is beyond our potential finish, we're OK. */
- if (ROUNDUP(try, nocross) >= try + size)
- return try;
- /* The segment still might have a chance. Perhaps we started right
- * before a nocross. Let's try again, being careful of overflow. The
- * ROUNDUP shouldn't trigger a wraparound. */
- try = ROUNDUP(bt_start, nocross);
- try_size = bt_size - (try - bt_start);
- /* Underflow of bt_size - large_number. */
- if (try_size > bt_size)
- return 0;
- /* The caller has some control over our next invocation's bt_start and
- * bt_size. Let's enforce sanity. */
- if (try + try_size < try)
- return 0;
- return __find_sufficient(try, try_size, size, align, phase, 0);
+ do {
+ try = bt_start;
+ try = ROUNDDOWN(try, np2sb);
+ try += phase;
+ if (try < bt_start)
+ try += np2sb;
+ /* Overflow sanity check. Ultimately, don't look outside bt. */
+ if (try < bt_start)
+ return 0;
+ /* Check wraparound */
+ if (try + size < try)
+ return 0;
+ /* Too big for BT, no chance. */
+ if (try + size > bt_start + bt_size)
+ return 0;
+ if (nocross == 0)
+ return try;
+ /* Got to deal with nocross boundaries. If we round up from our
+ * potential start and that is beyond our potential finish,
+ * we're OK. */
+ if (ALIGN(try, nocross) >= try + size)
+ return try;
+ /* The segment still might have a chance. Perhaps we started
+ * right before a nocross.
+ *
+ * All we're doing here is artificially limiting bt to a subset,
+ * starting at the next nocross, if it is within BT. And we're
+ * checking *all* nocross-aligned chunks in this BT */
+ try = ALIGN(bt_start + 1, nocross);
+ if (try - bt_start >= bt_size)
+ return 0;
+ bt_size -= try - bt_start;
+ bt_start = try;
+ } while (1);
}
/* Helper: splits bt, which is not on any freelist, at @at, and puts the front
@@ -892,7 +899,7 @@
/* Does the a search in min/max for a segment. */
static void *__xalloc_min_max(struct arena *arena, size_t size,
- size_t align, size_t phase, size_t nocross,
+ size_t np2sb, size_t phase, size_t nocross,
uintptr_t minaddr, uintptr_t maxaddr)
{
struct rb_node *node = arena->all_segs.rb_node;
@@ -913,7 +920,7 @@
* Just scan from here. */
for (/* node set */; node; node = rb_next(node)) {
bt = container_of(node, struct btag, all_link);
- try = __find_sufficient(bt->start, bt->size, size, align, phase,
+ try = __find_sufficient(bt->start, bt->size, size, np2sb, phase,
nocross);
if (!try)
continue;
@@ -931,7 +938,7 @@
/* For xalloc, there isn't any real instant fit, due to the nocross issues. We
* can still try to get a quicker fit by starting on a higher order list. */
static void *__xalloc_from_freelists(struct arena *arena, size_t size,
- size_t align, size_t phase, size_t nocross,
+ size_t np2sb, size_t phase, size_t nocross,
bool try_instant_fit)
{
int list_idx;
@@ -946,7 +953,7 @@
for (int i = list_idx; i < ARENA_NR_FREE_LISTS; i++) {
BSD_LIST_FOREACH(bt_i, &arena->free_segs[i], misc_link) {
try = __find_sufficient(bt_i->start, bt_i->size, size,
- align, phase, nocross);
+ np2sb, phase, nocross);
if (try) {
BSD_LIST_REMOVE(bt_i, misc_link);
break;
@@ -963,7 +970,7 @@
return (void*)bt_i->start;
}
-static void *__xalloc_nextfit(struct arena *arena, size_t size, size_t align,
+static void *__xalloc_nextfit(struct arena *arena, size_t size, size_t np2sb,
size_t phase, size_t nocross)
{
void *ret;
@@ -972,10 +979,10 @@
* since the implementation of that helper starts a search from minaddr.
* If it fails, we can try again from 1 (quantum, really), skipping 0.
* */
- ret = __xalloc_min_max(arena, size, align, phase, nocross,
+ ret = __xalloc_min_max(arena, size, np2sb, phase, nocross,
arena->last_nextfit_alloc + arena->quantum, 0);
if (!ret) {
- ret = __xalloc_min_max(arena, size, align, phase, nocross,
+ ret = __xalloc_min_max(arena, size, np2sb, phase, nocross,
arena->quantum, 0);
}
if (!ret)
@@ -985,7 +992,7 @@
}
static void *xalloc_from_arena(struct arena *arena, size_t size,
- size_t align, size_t phase, size_t nocross,
+ size_t np2sb, size_t phase, size_t nocross,
void *minaddr, void *maxaddr, int flags)
{
void *ret;
@@ -999,17 +1006,17 @@
return NULL;
}
if (minaddr || maxaddr) {
- ret = __xalloc_min_max(arena, size, align, phase, nocross,
+ ret = __xalloc_min_max(arena, size, np2sb, phase, nocross,
(uintptr_t)minaddr, (uintptr_t)maxaddr);
} else {
if (flags & ARENA_BESTFIT) {
- ret = __xalloc_from_freelists(arena, size, align, phase,
+ ret = __xalloc_from_freelists(arena, size, np2sb, phase,
nocross, FALSE);
} else if (flags & ARENA_NEXTFIT) {
- ret = __xalloc_nextfit(arena, size, align, phase,
+ ret = __xalloc_nextfit(arena, size, np2sb, phase,
nocross);
} else {
- ret = __xalloc_from_freelists(arena, size, align, phase,
+ ret = __xalloc_from_freelists(arena, size, np2sb, phase,
nocross, TRUE);
}
}
@@ -1027,38 +1034,52 @@
{
void *ret;
size_t req_size;
+ bool ovf = false;
+ size_t np2sb; /* non-power-of 2 start boundary */
size = ROUNDUP(size, arena->quantum);
if (!size)
panic("Arena %s, request for zero", arena->name);
- if (!IS_PWR2(align))
- panic("Arena %s, non-power of two align %p", arena->name,
- align);
- if (nocross && !IS_PWR2(nocross))
- panic("Arena %s, non-power of nocross %p", arena->name,
- nocross);
- if (!ALIGNED(align, arena->quantum))
- panic("Arena %s, non-aligned align %p", arena->name, align);
- if (!ALIGNED(nocross, arena->quantum))
- panic("Arena %s, non-aligned nocross %p", arena->name, nocross);
- if (!ALIGNED(phase, arena->quantum))
- panic("Arena %s, non-aligned phase %p", arena->name, phase);
- if (size + align < size)
- panic("Arena %s, size %p + align %p overflow%p", arena->name,
- size, align);
- if (size + phase < size)
- panic("Arena %s, size %p + phase %p overflow%p", arena->name,
- size, phase);
- if (align + phase < align)
- panic("Arena %s, align %p + phase %p overflow%p", arena->name,
- align, phase);
+ /* align == 0 is basically align == 1: "don't care" */
+ if (!align)
+ align = 1;
+ /* If we make quantum a power of two, we can just take the larger, which
+ * is a multiple of the smaller */
+ np2sb = LCM_PWR2(arena->quantum, align);
+ if (!np2sb)
+ panic("Arena %s, could not find np2sb %p %p",
+ arena->name, arena->quantum, align);
+
+ if (phase >= align)
+ panic("Arena %s, phase %d >= align %d",
+ arena->name, phase, align);
+ if (phase % arena->quantum)
+ panic("Arena %s, non-multiple phase %d %d",
+ arena->name, phase, arena->quantum);
+
+ if (nocross) {
+ if (!IS_PWR2(nocross))
+ panic("Arena %s, non-power of two nocross %p",
+ arena->name, nocross);
+ /* See the discussion on nocross below. Paranoia for overflow
+ * is checked below (our callers are kernel users). */
+ if (size + phase > nocross)
+ panic("Arena %s, unsat size and phase: %p + %p > %p",
+ arena->name, size, phase, nocross);
+ /* This is a little aggressive. This arena or its source might
+ * very well give us something that works. This check covers
+ * cases where we might be unable to ask our source via a
+ * regular alloc for a segment that could satisfy this
+ * allocation request, and we could lock up. */
+ if (arena->source && !ALIGNED(np2sb, nocross) &&
+ !(2 * size - 2 < nocross))
+ panic("Arena %s, unsat size: 2 * %p - 2 > %p",
+ arena->name, size, nocross);
+ }
/* Ok, it's a pain to import resources from a source such that we'll be
* able to guarantee we make progress without stranding resources if we
- * have nocross or min/maxaddr. For min/maxaddr, when we ask the
- * source, we aren't easily able to xalloc from their (it may depend on
- * the afunc). For nocross, we can't easily ask the source for the
- * right span that satisfies the request (again, no real xalloc). Some
- * constraints might not even be possible.
+ * have min/maxaddr. We don't have a way to ask the source for a
+ * particular range: i.e. an xalloc.
*
* If we get a span from the source and never use it, then we run a risk
* of fragmenting and stranding a bunch of spans in our current arena.
@@ -1067,31 +1088,108 @@
* we won't give them back to the source until we allocate and then free
* them (barring some sort of reclaim callback).
*
- * Besides, I don't know if we even need/want nocross/min/maxaddr. */
- if (arena->source && (nocross || minaddr || maxaddr))
- panic("Arena %s, has source, can't xalloc with nocross %p, minaddr %p, or maxaddr %p",
- arena->name, nocross, minaddr, maxaddr);
+ * If we want to support this, we'll need to require an xafunc that gets
+ * called when xalloc needs to get_more_resources(). This means all
+ * arenas in the chain need an xafunc, all the way back to the base.
+ * Otherwise, we don't know that when we ask a source if we get
+ * something back that is usable.
+ *
+ * Note that if we import a segment with xalloc, we need to free it with
+ * xfree. That means this arena needs to track its segment types.
+ * Also, every xalloc call skips the qcache. That might be a
+ * performance issue, so it's better to not do those if you can. */
+ if (arena->source && (minaddr || maxaddr))
+ panic("Arena %s, has source, can't xalloc with minaddr %p or maxaddr %p",
+ arena->name, minaddr, maxaddr);
while (1) {
- ret = xalloc_from_arena(arena, size, align, phase, nocross,
+ ret = xalloc_from_arena(arena, size, np2sb, phase, nocross,
minaddr, maxaddr, flags);
if (ret)
return ret;
- /* We checked earlier than no two of these overflow, so I think
- * we don't need to worry about multiple overflows. */
- req_size = size + align + phase;
- /* Note that this check isn't the same as the one we make when
- * finding a sufficient segment. Here we check overflow on the
- * requested size. Later, we check aligned bt_start + phase.
- * The concern is that this check succeeds, but the other fails.
- * (Say size = PGSIZE, phase =
- * -PGSIZE -1. req_size is very large.
+ /* Ah, nocross. We need to make sure the segment we pull from
+ * the source is sufficient, but we are doing a regular alloc
+ * (not xalloc). One conservative way to do this is to request
+ * space for two of whatever we need, and abort if that block
+ * could contain more than one nocross boundary.
*
- * In this case, we're still fine - if our source is able to
- * satisfy the request, our bt_start and bt_size will be able to
- * express that size without wrapping. */
- if (req_size < size)
- panic("Arena %s, size %p + align %p + phase %p overflw",
- arena->name, size, align, phase);
+ * For starters, if size > nocross, we're completely
+ * unsatisfiable. So there are some requests we just can't do.
+ * Similarly, and slightly stricter: size + phase > nocross is
+ * unsat too. Here's why: phase is a shift off from an
+ * alignment, and nocross is an alignment. The best case
+ * scenario for a potential allocation is if it starts right at
+ * a nocross boundary. (Starting later makes our potential
+ * space even smaller).
+ *
+ * Let's consider nocross >= align. So we know the closest the
+ * boundary could get to the start of the object we want,
+ * without intersecting is phase bytes above nocross. That
+ * leaves us with nocross - phase bytes until the next boundary.
+ *
+ * Now consider align > nocross. Any potential object that
+ * starts at an unaligned nocross will need to get rounded up to
+ * align, and then add phase, and then have that last bit of
+ * space for the object. That's even less space, though it
+ * varies based on which object we look at - some of the nocross
+ * boundaries will be align-aligned.
+ *
+ * Next, any allocation >= 2 bytes could have a boundary
+ * (subject to align and phase). So we're going to have at
+ * least a boundary in most all allocations. (nocross with sz
+ * == 1 is meaningless). If we have a boundary, we have limited
+ * control over where it is in the object - it could be right in
+ * the middle. The safest thing to do is grab 2x the space we
+ * need, and then the one boundary can ruin at most one of the
+ * two objects.
+ *
+ * How many boundaries are there in X bytes? (where X will be
+ * 2*size)
+ * FLOOR((x - 2) / nocross) + 1; (x >= 2)
+ * To have at most one boundary:
+ * x - 2 < nocross
+ * size >= 1, so x >=2. Thus to be sure our alloc will work, we
+ * check 2*size - 2 < nocross. That's for a request of 2*size
+ * from the source arena. If the original request to our arena
+ * was greater than that, then there's no guarantee we can use a
+ * regular alloc from our source and get a result that will be
+ * nocross-sat.
+ *
+ * Oh, and if we have align / phase, we will need to request
+ * more to make sure our 2x block is in the right place, though
+ * we don't need to worry about a boundary falling in the
+ * alignment/phase space.
+ *
+ * The minimum we need for that is (align - 1) - phase. Though
+ * the xalloc algorithms might be simple/lazy, so previously I
+ * just added align + phase. It's actually safe to ask for
+ * more; it might be a waste or might block, but the main
+ * concern is that we get something that is guaranteed to work.
+ *
+ * And since quantum can be a non-power-of-two, we're aligning
+ * to "np2sb" (the LCM of quantum and align), so it's really
+ * np2sb + phase.
+ *
+ * At this point, we're requesting 2*size + np2sb + phase.
+ *
+ * Now, if we have an align (and/or phase), the align can help
+ * us with the nocross too! If np2sb is nocross-aligned, and
+ * size + phase < nocross, which always must be true, then we
+ * know the start of the object is on a boundary (minus phase),
+ * and if it can fit at all, it will certainly fit. So other
+ * than the sanity check, we just ignore nocross. It's somewhat
+ * meaningless to ask for align >= nocross.
+ *
+ * I'm certainly not 100% on any of this. */
+ req_size = size;
+ /* Distilled: need 2x when nocross, and align doesn't help */
+ if (nocross && !ALIGNED(np2sb, nocross))
+ ovf |= check_add_overflow(req_size, size, &req_size);
+ /* TODO: check xalloc internals: could be align - 1 - phase */
+ ovf |= check_add_overflow(req_size, np2sb, &req_size);
+ ovf |= check_add_overflow(req_size, phase, &req_size);
+ if (ovf)
+ panic("Arena %s, size %p + np2sb %p + phase %p overflw",
+ arena->name, size, np2sb, phase);
if (!get_more_resources(arena, req_size, flags))
return NULL;
/* Our source may have given us a segment that is on the BESTFIT
