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

Commit Message

Liam R. Howlett Dec. 1, 2021, 2:29 p.m. UTC

From: "Liam R. Howlett" <[e-mail]>

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 <[e-mail]>
---
 mm/mmap.c | 27 +++++++++------------------
 1 file changed, 9 insertions(+), 18 deletions(-)

Comments

Vlastimil Babka Dec. 15, 2021, 1:05 p.m. UTC | #1

On 12/1/21 15:29, Liam Howlett wrote:
> From: "Liam R. Howlett" <[e-mail]>
> 
> 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 <[e-mail]>

Acked-by: Vlastimil Babka <[e-mail]>

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;

Liam R. Howlett Dec. 15, 2021, 6:09 p.m. UTC | #2

* Vlastimil Babka <[e-mail]> [211215 08:05]:
> On 12/1/21 15:29, Liam Howlett wrote:
> > From: "Liam R. Howlett" <[e-mail]>
> > 
> > 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 <[e-mail]>
> 
> Acked-by: Vlastimil Babka <[e-mail]>
> 
> 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.

This is certainly worth fixing.  I am surprised that I did not hit a
random bug as you said above, I would expect it to occur as well.
Although, I didn't run each patch individually for long unless I was
tracking down an issue on a rebase.

As for the performance, I will retest the performance for the vmacache
included and excluded but since the overall performance of the patch set
is still valid, I don't expect a change here.

This is a really good catch, thanks.
Liam

Vlastimil Babka Jan. 13, 2022, 3:46 p.m. UTC | #3

On 12/15/21 19:09, Liam Howlett wrote:
>> - 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.
> This is certainly worth fixing.  I am surprised that I did not hit a
> random bug as you said above, I would expect it to occur as well.
> Although, I didn't run each patch individually for long unless I was
> tracking down an issue on a rebase.

Ah, it doesn't cause a bug because vmacache_find() checks the boundaries of
vmas in the vmacache.

Patch

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);
 	if (vma)
 		vmacache_update(addr, vma);
 	return vma;