vmem: Allocate btags before looping in vmem_xalloc()

[markj]

Summary

BT_MAXALLOC (4) is the number of boundary tags required to complete an
allocation in the worst case: two to clip a free segment, and two to
import from a parent arena. bt_fill() preallocates four boundary tags
before attempting a search to simplify the segment allocation code.

vmem_xalloc() and vmem_xalloc_nextfit() are implemented using a loop
which:

1. ensures that BT_MAXALLOC boundary tags are available,
2. attempts to find a free segment satisfying the allocation constraints, and failing that,
3. attempts to import a segment

On !UMA_MD_SMALL_ALLOC platforms the btag zone has to handle recusion:
it needs boundary tags to allocate boundary tags. Thus we reserve
2 * BT_MAXALLOC * mp_ncpus tags for use when recursing: the factor of 2
is because there are two layers of vmem arenas, the per-domain arena and
global arena. For a single thread, 2 * BT_MAXALLOC tags should be
sufficient.

Because of the way the loop is structured, BT_MAXALLOC tags are not
sufficient. The first bt_fill() call may allocate BT_MAXALLOC tags,
then import a segment (consuming two tags), then attempt to top up the
preallocation before carving into the imported free segment, thus
requiring up to six tags in the worst case. Because we don't
preallocate that many, this bug can cause deadlocks in rare scenarios.

Fix the problem by moving the preallocation out the loop. I believe
that a given allocation should only ever require a single import.

[rlibby]

So, is it the case that if we do a successful vmem_import under vmem_try_fetch that that new segment must be able to satisfy the request (and we won't do a second etc import)? I notice that there are several arguments to vmem_fit which are not arguments to vmem_import.

sys/kern/subr_vmem.c

1051–1056 ↗

(On Diff #78192)

We drop and reacquire the lock here in vmem_try_fetch. I think at the least we may have to "Hide MAXALLOC tags" like we do in vmem_import.

[markj]

In D26770#596923, @rlibby wrote:

So, is it the case that if we do a successful vmem_import under vmem_try_fetch that that new segment must be able to satisfy the request (and we won't do a second etc import)? I notice that there are several arguments to vmem_fit which are not arguments to vmem_import.

Yes, this is an assumption I'm making. The XXX comment in vmem_try_fetch() hints at this. I think it's a reasonable assumption - if the first import fails to yield a segment that can satisfy the allocation constraints, there's no reason a subsequent import should succeed. vmem_import() tries to ensure that the imported segment can at least satisfy the alignment constraint and I believe the phase constraint as well. For some usages of vmem_xalloc(), imports won't be able to satisfy the allocation and vmem users just have to be aware of that. I don't think it's a problem for existing consumers of vmem arenas with import functions, but I'm not sure how best to enforce correct usage of the interface. There are few enough users of vmem_set_import() that we could perhaps just pass all constraints through to the import function and force them to deal with it (or KASSERT otherwise).

sys/kern/subr_vmem.c

1051–1056 ↗

(On Diff #78192)

Yes, same for the VMEM_CONDVAR_WAIT() below.

[markj]

Hide preallocated tags before dropping the arena lock in
vmem_try_fetch(). Introduce bt_save() and bt_restore() for this
purpose.

[rlibby]

Change looks good.

Yeah, it looks like we'd have to do some plumbing if we wanted to KASSERT about vmem_import giving a useful segment. I guess it is not worth the effort for this change, but maybe something to chew on.

[alc]

sys/kern/subr_vmem.c

1413–1414 ↗

(On Diff #78213)

This sentence will now fit on one line.