[PATCH v4 09/66] mm/mmap: Use the maple tree in find_vma() instead of the rbtree.

[Vlastimil Babka]

On 12/1/21 15:29, Liam Howlett wrote:
> From: "Liam R. Howlett" <Liam.Howlett at Oracle.com>
> 
> Using the maple tree interface mt_find() will handle the RCU locking and
> will start searching at the address up to the limit, ULONG_MAX in this
> case.
> 
> Add kernel documentation to this API.
> 
> Signed-off-by: Liam R. Howlett <Liam.Howlett at Oracle.com>

Acked-by: Vlastimil Babka <vbabka at suse.cz>

Note below:

> ---
>  mm/mmap.c | 27 +++++++++------------------
>  1 file changed, 9 insertions(+), 18 deletions(-)
> 
> diff --git a/mm/mmap.c b/mm/mmap.c
> index de78fc0ce809..6a7502f74190 100644
> --- a/mm/mmap.c
> +++ b/mm/mmap.c
> @@ -2429,10 +2429,16 @@ get_unmapped_area(struct file *file, unsigned long addr, unsigned long len,
>  
>  EXPORT_SYMBOL(get_unmapped_area);
>  
> -/* Look up the first VMA which satisfies  addr < vm_end,  NULL if none. */
> +/**
> + * find_vma() - Find the VMA for a given address, or the next vma.
> + * @mm: The mm_struct to check
> + * @addr: The address
> + *
> + * Returns: The VMA associated with addr, or the next vma.
> + * May return %NULL in the case of no vma at addr or above.
> + */
>  struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
>  {
> -	struct rb_node *rb_node;
>  	struct vm_area_struct *vma;
>  
>  	mmap_assert_locked(mm);
> @@ -2441,22 +2447,7 @@ struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
>  	if (likely(vma))
>  		return vma;
>  
> -	rb_node = mm->mm_rb.rb_node;
> -
> -	while (rb_node) {
> -		struct vm_area_struct *tmp;
> -
> -		tmp = rb_entry(rb_node, struct vm_area_struct, vm_rb);
> -
> -		if (tmp->vm_end > addr) {
> -			vma = tmp;
> -			if (tmp->vm_start <= addr)
> -				break;
> -			rb_node = rb_node->rb_left;
> -		} else
> -			rb_node = rb_node->rb_right;
> -	}
> -
> +	vma = mt_find(&mm->mm_mt, &addr, ULONG_MAX);

This updates addr to the end of vma->vm_end.

>  	if (vma)
>  		vmacache_update(addr, vma);

And here vmacache is updated with the updated addr, which wasn't done
before. This AFAIU has two consequences:

- the original addr will not be cached, so this whole vma lookup will not be
cached and will always resort to maple tree search. Possibly affecting any
measurements you made. Especially the vmacache removal later in the series
might now look like it makes not much of a performance difference - but
vmcache is effectively dysfunctional.

- the future lookup of address vma->vm_end will return this vma, although
the address doesn't belong to it. Wouldn't be surprised if this caused
infrequent mysterious bugs?

Both will resolve with vmacache removal later, but better still fix this.

Vlastimil

>  	return vma;