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

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

[Zhaoyang Huang]

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

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)

vmap_area_list->...->first->...->tmp->tmp_next
                            (2)

Signed-off-by: Zhaoyang Huang <zhaoyang.huang@spreadtrum.com>
---
 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) {
+					addr = ALIGN(tmp->va_end, align);
+			                if (cached_hole_size >= size)
+						cached_hole_size = 0;
+					goto found;
+				}
 				if (tmp->va_start <= addr)
 					break;
 				n = n->rb_left;
-- 
1.9.1

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

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

[zijun_hu]

On 07/18/2017 04:31 PM, Zhaoyang Huang (>>AE3?No) 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@spreadtrum.com>
> ---
>  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
> 


--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

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

[Zhaoyang Huang (黄朝阳)]

________________________________________
From: zijun_hu <zijun_hu@zoho.com>
Sent: Tuesday, July 18, 2017 5:23 PM
To: Zhaoyang Huang (黄朝阳)
Cc: linux-mm@kvack.org; linux-kernel@vger.kernel.org; zijun_hu@htc.com; Andrew Morton; Michal Hocko; Ingo Molnar; Vlastimil Babka; Thomas Garnier; Kirill A. Shutemov; Andrey Ryabinin; linux-mm@kvack.org; linux-kernel@vger.kernel.org
Subject: Re: [PATCH v3] mm/vmalloc: terminate searching since one node found

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
In terms of 'A', I don't think it is neccesarry, for the 'vmap_area_root' and 'vmap_free_list' are all sorted.
whenever you insert data, they will be well sorted according to the address range.
In terms of 'B', the changes are within the process of 'walking the rb tree' where the 'free_vmap_cache'
is NULL, which means the cache have to be updated here.

> 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@spreadtrum.com>
> ---
>  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
>