On Wed, Sep 29, 2021 at 4:40 PM David Hildenbrand [off-list ref] wrote:

On 29.09.21 16:30, Uladzislau Rezki wrote:

quoted

quoted

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:

How realistic is that test case? I assume most alignment we're dealing
with is:
* 1/PAGE_SIZE
* huge page size (for automatic huge page placing)

Well that is synthetic test. Most of the alignments are 1 or PAGE_SIZE.
There are users which use internal API where you can specify an alignment
you want but those are mainly like KASAN, module alloc, etc.

quoted

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;

That will not allow to place huge pages in the case of kasan. And I
consider that more important than optimizing a syntactic test :) My 2 cents.

Could you please to be more specific? I mean how is it connected with huge
pages mappings? Huge-pages are which have order > 0. Or you mean that
a special alignments are needed for mapping huge pages?

-- 
Uladzislau Rezki