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