So the idea is that once we run into a dead end because we took a left
subtree, we rollback to the next possible rigth subtree and try again.
If we run into another dead end, we repeat ... thus, this can now happen
more than once.

I assume the only implication is that this can now be slower in some
corner cases with larger alignment, because it might take longer to find
something suitable. Fair enough.

Yep, your understanding is correct regarding the tree traversal. If no
suitable block
is found in left sub-tree we roll-back and check right one. So it can
be(the scanning)
more than one time.

I did some performance analyzing using vmalloc test suite to figure
out a performance
loss for allocations with specific alignment. On that syntactic test i
see approx. 30%
of degradation:

2.225 microseconds vs 1.496 microseconds. That time includes both
vmalloc() and vfree()
calls. I do not consider it as a big degrade, but from the other hand
we can still adjust the
search length for alignments > one page:

# add it on top of previous proposal and search length instead of size
length = align > PAGE_SIZE ? size + align:size;

in that case we solve a KASAN issue + do not introduce a degrade. For
the PAGE_SIZE
alignment all free blocks are aligned to it anyway. As for users which
uses a fixed range
that is same as a requested size and at the same time want to apply a
special alignment
is not considered as a common case, also we do not have such users.

Thoughts?

quoted

Could you please help and test the KASAN use case?

Just tried it, works just fine with KASAN and makes sense in general,
thanks!

Good!

Sorry for the delay.

--
Uladzislau Rezki