Re: [PATCH v3] mm/vmalloc: terminate searching since one node found

[zijun_hu]

On 07/18/2017 04:31 PM, Zhaoyang Huang (黄朝阳) wrote:
> 
> It is no need to find the very beginning of the area within
> alloc_vmap_area, which can be done by judging each node during the process
> 
it seems the original code is wrote to achieve the following two purposes :
A, the result vamp_area has the lowest available address in the required range [vstart, vend)
B, it maybe update the cached vamp_area node info which can speedup other relative allocations
it look redundant but conventional and necessary
this approach maybe destroy the original purposes
> For current approach, the worst case is that the starting node which be found
> for searching the 'vmap_area_list' is close to the 'vstart', while the final
> available one is round to the tail(especially for the left branch).
> This commit have the list searching start at the first available node, which
> will save the time of walking the rb tree'(1)' and walking the list'(2)'.
> 
>       vmap_area_root
>           /      \
>      tmp_next     U
>         /
>       tmp
>        /
>      ...  (1)
>       /
>     first(current approach)
>
 @tmp_next is the next node of @tmp in the ordered list_head, not in the rbtree

> vmap_area_list->...->first->...->tmp->tmp_next
>                             (2)
> 
> Signed-off-by: Zhaoyang Huang <zhaoyang.huang@xxxxxxxxxxxxxx>
> ---
>  mm/vmalloc.c | 9 +++++++++
>  1 file changed, 9 insertions(+)
> 
> diff --git a/mm/vmalloc.c b/mm/vmalloc.c
> index 34a1c3e..9a5c177 100644
> --- a/mm/vmalloc.c
> +++ b/mm/vmalloc.c
> @@ -459,9 +459,18 @@ static struct vmap_area *alloc_vmap_area(unsigned long size,
> 
>                 while (n) {
>                         struct vmap_area *tmp;
> +                       struct vmap_area *tmp_next;
>                         tmp = rb_entry(n, struct vmap_area, rb_node);
> +                       tmp_next = list_next_entry(tmp, list);
>                         if (tmp->va_end >= addr) {
>                                 first = tmp;
> +                               if (ALIGN(tmp->va_end, align) + size
> +                                               < tmp_next->va_start) {
if @tmp node don't locate in the required rang [vstart, vend), but the right of the range it maybe
satisfy this condition, even if it locate it locate within the range, it maybe don't have the lowest free address.
if @tmp don't have the next node, tmp_next->va_start will cause NULL dereference
> +                                       addr = ALIGN(tmp->va_end, align);
> +                                       if (cached_hole_size >= size)
> +                                               cached_hole_size = 0;
it seems a little rough to reset the @cached_hole_size by this way,  it will caused the cached info is updated in the next
allocation regardless the allocation arguments.
> +                                       goto found;
> +                               }
>                                 if (tmp->va_start <= addr)
>                                         break;
>                                 n = n->rb_left;
> --
> 1.9.1
>