Re: [PATCH v4 1/3] mm/vmap: keep track of free blocks for vmap allocation

[Roman Gushchin]

On Sat, Apr 06, 2019 at 08:35:06PM +0200, Uladzislau Rezki (Sony) wrote:
> Currently an allocation of the new vmap area is done over busy
> list iteration(complexity O(n)) until a suitable hole is found
> between two busy areas. Therefore each new allocation causes
> the list being grown. Due to over fragmented list and different
> permissive parameters an allocation can take a long time. For
> example on embedded devices it is milliseconds.
> 
> This patch organizes the KVA memory layout into free areas of the
> 1-ULONG_MAX range. It uses an augment red-black tree that keeps
> blocks sorted by their offsets in pair with linked list keeping
> the free space in order of increasing addresses.
> 
> Nodes are augmented with the size of the maximum available free
> block in its left or right sub-tree. Thus, that allows to take a
> decision and traversal toward the block that will fit and will
> have the lowest start address, i.e. it is sequential allocation.
> 
> Allocation: to allocate a new block a search is done over the
> tree until a suitable lowest(left most) block is large enough
> to encompass: the requested size, alignment and vstart point.
> If the block is bigger than requested size - it is split.
> 
> De-allocation: when a busy vmap area is freed it can either be
> merged or inserted to the tree. Red-black tree allows efficiently
> find a spot whereas a linked list provides a constant-time access
> to previous and next blocks to check if merging can be done. In case
> of merging of de-allocated memory chunk a large coalesced area is
> created.
> 
> Complexity: ~O(log(N))
> 
> Signed-off-by: Uladzislau Rezki (Sony) <urezki@xxxxxxxxx>

Reviewed-by: Roman Gushchin <guro@xxxxxx>

Thanks!