OSDN Git Service
mm/vmap: keep track of free blocks for vmap allocation
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@gmail.com>