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!
