[v4,10/66] mm/mmap: Use the maple tree for find_vma_prev() instead of the rbtree

Commit Message

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

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

Use the maple tree's advanced API and a maple state to walk the tree
for the entry at the address of the next vma, then use the maple state
to walk back one entry to find the previous entry.

Add kernel documentation comments for this API.

Signed-off-by: Liam R. Howlett <[e-mail]>
Signed-off-by: Matthew Wilcox (Oracle) <[e-mail]>
---
 mm/mmap.c | 24 ++++++++++++++----------
 1 file changed, 14 insertions(+), 10 deletions(-)

Comments

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

On 12/1/21 15:29, Liam Howlett wrote:
> From: "Liam R. Howlett" <[e-mail]>
> 
> Use the maple tree's advanced API and a maple state to walk the tree
> for the entry at the address of the next vma, then use the maple state
> to walk back one entry to find the previous entry.
> 
> Add kernel documentation comments for this API.
> 
> Signed-off-by: Liam R. Howlett <[e-mail]>
> Signed-off-by: Matthew Wilcox (Oracle) <[e-mail]>

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

> ---
>  mm/mmap.c | 24 ++++++++++++++----------
>  1 file changed, 14 insertions(+), 10 deletions(-)
> 
> diff --git a/mm/mmap.c b/mm/mmap.c
> index 6a7502f74190..8425ab573770 100644
> --- a/mm/mmap.c
> +++ b/mm/mmap.c
> @@ -2454,23 +2454,27 @@ struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
>  }
>  EXPORT_SYMBOL(find_vma);
>  
> -/*
> - * Same as find_vma, but also return a pointer to the previous VMA in *pprev.
> +/**
> + * find_vma_prev() - Find the VMA for a given address, or the next vma and
> + * set %pprev to the previous VMA, if any.
> + * @mm: The mm_struct to check
> + * @addr: The address
> + * @pprev: The pointer to set to the previous VMA
> + *
> + * 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_prev(struct mm_struct *mm, unsigned long addr,
>  			struct vm_area_struct **pprev)
>  {
>  	struct vm_area_struct *vma;
> +	MA_STATE(mas, &mm->mm_mt, addr, addr);
>  
> -	vma = find_vma(mm, addr);
> -	if (vma) {
> -		*pprev = vma->vm_prev;
> -	} else {
> -		struct rb_node *rb_node = rb_last(&mm->mm_rb);
> -
> -		*pprev = rb_node ? rb_entry(rb_node, struct vm_area_struct, vm_rb) : NULL;
> -	}
> +	vma = mas_walk(&mas);
> +	*pprev = mas_prev(&mas, 0);
> +	if (!vma)
> +		vma = mas_next(&mas, ULONG_MAX);
>  	return vma;
>  }
>

Vlastimil Babka Dec. 15, 2021, 4:40 p.m. UTC | #2

On 12/1/21 15:29, Liam Howlett wrote:
> From: "Liam R. Howlett" <[e-mail]>
> 
> Use the maple tree's advanced API and a maple state to walk the tree
> for the entry at the address of the next vma, then use the maple state
> to walk back one entry to find the previous entry.
> 
> Add kernel documentation comments for this API.

Additional note: the previous patch for find_vma() mentioned "Using the
maple tree interface mt_find() will handle the RCU locking" while
find_vma_prev() uses the advanced maple tree API, thus IIUC without RCU
locking, and doesn't add its own. This can easily result in a bug,
especially if the documentation comments don't mention it at all?

> Signed-off-by: Liam R. Howlett <[e-mail]>
> Signed-off-by: Matthew Wilcox (Oracle) <[e-mail]>
> ---
>  mm/mmap.c | 24 ++++++++++++++----------
>  1 file changed, 14 insertions(+), 10 deletions(-)
> 
> diff --git a/mm/mmap.c b/mm/mmap.c
> index 6a7502f74190..8425ab573770 100644
> --- a/mm/mmap.c
> +++ b/mm/mmap.c
> @@ -2454,23 +2454,27 @@ struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
>  }
>  EXPORT_SYMBOL(find_vma);
>  
> -/*
> - * Same as find_vma, but also return a pointer to the previous VMA in *pprev.
> +/**
> + * find_vma_prev() - Find the VMA for a given address, or the next vma and
> + * set %pprev to the previous VMA, if any.
> + * @mm: The mm_struct to check
> + * @addr: The address
> + * @pprev: The pointer to set to the previous VMA
> + *
> + * 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_prev(struct mm_struct *mm, unsigned long addr,
>  			struct vm_area_struct **pprev)
>  {
>  	struct vm_area_struct *vma;
> +	MA_STATE(mas, &mm->mm_mt, addr, addr);
>  
> -	vma = find_vma(mm, addr);
> -	if (vma) {
> -		*pprev = vma->vm_prev;
> -	} else {
> -		struct rb_node *rb_node = rb_last(&mm->mm_rb);
> -
> -		*pprev = rb_node ? rb_entry(rb_node, struct vm_area_struct, vm_rb) : NULL;
> -	}
> +	vma = mas_walk(&mas);
> +	*pprev = mas_prev(&mas, 0);
> +	if (!vma)
> +		vma = mas_next(&mas, ULONG_MAX);
>  	return vma;
>  }
>

Liam R. Howlett Dec. 15, 2021, 6:19 p.m. UTC | #3

* Vlastimil Babka <[e-mail]> [211215 11:40]:
> On 12/1/21 15:29, Liam Howlett wrote:
> > From: "Liam R. Howlett" <[e-mail]>
> > 
> > Use the maple tree's advanced API and a maple state to walk the tree
> > for the entry at the address of the next vma, then use the maple state
> > to walk back one entry to find the previous entry.
> > 
> > Add kernel documentation comments for this API.
> 
> Additional note: the previous patch for find_vma() mentioned "Using the
> maple tree interface mt_find() will handle the RCU locking" while
> find_vma_prev() uses the advanced maple tree API, thus IIUC without RCU
> locking, and doesn't add its own. This can easily result in a bug,
> especially if the documentation comments don't mention it at all?


Yes, you are correct that mt_find() will handle the RCU locking, while
the advanced interface does not use the locking.  However, now that the
maple tree can use an external lock and uses the mmap_lock(), it's not
necessary to use RCU locks in these cases until we have users that are
removed from the mmap_lock().  I will add a comment so that this is not
missed when things are removed from the mmap_lock().

> 
> > Signed-off-by: Liam R. Howlett <[e-mail]>
> > Signed-off-by: Matthew Wilcox (Oracle) <[e-mail]>
> > ---
> >  mm/mmap.c | 24 ++++++++++++++----------
> >  1 file changed, 14 insertions(+), 10 deletions(-)
> > 
> > diff --git a/mm/mmap.c b/mm/mmap.c
> > index 6a7502f74190..8425ab573770 100644
> > --- a/mm/mmap.c
> > +++ b/mm/mmap.c
> > @@ -2454,23 +2454,27 @@ struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
> >  }
> >  EXPORT_SYMBOL(find_vma);
> >  
> > -/*
> > - * Same as find_vma, but also return a pointer to the previous VMA in *pprev.
> > +/**
> > + * find_vma_prev() - Find the VMA for a given address, or the next vma and
> > + * set %pprev to the previous VMA, if any.
> > + * @mm: The mm_struct to check
> > + * @addr: The address
> > + * @pprev: The pointer to set to the previous VMA
> > + *
> > + * 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_prev(struct mm_struct *mm, unsigned long addr,
> >  			struct vm_area_struct **pprev)
> >  {
> >  	struct vm_area_struct *vma;
> > +	MA_STATE(mas, &mm->mm_mt, addr, addr);
> >  
> > -	vma = find_vma(mm, addr);
> > -	if (vma) {
> > -		*pprev = vma->vm_prev;
> > -	} else {
> > -		struct rb_node *rb_node = rb_last(&mm->mm_rb);
> > -
> > -		*pprev = rb_node ? rb_entry(rb_node, struct vm_area_struct, vm_rb) : NULL;
> > -	}
> > +	vma = mas_walk(&mas);
> > +	*pprev = mas_prev(&mas, 0);
> > +	if (!vma)
> > +		vma = mas_next(&mas, ULONG_MAX);
> >  	return vma;
> >  }
> >  
>

Patch

diff --git a/mm/mmap.c b/mm/mmap.c
index 6a7502f74190..8425ab573770 100644
--- a/mm/mmap.c
+++ b/mm/mmap.c
@@ -2454,23 +2454,27 @@  struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
 }
 EXPORT_SYMBOL(find_vma);
 
-/*
- * Same as find_vma, but also return a pointer to the previous VMA in *pprev.
+/**
+ * find_vma_prev() - Find the VMA for a given address, or the next vma and
+ * set %pprev to the previous VMA, if any.
+ * @mm: The mm_struct to check
+ * @addr: The address
+ * @pprev: The pointer to set to the previous VMA
+ *
+ * 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_prev(struct mm_struct *mm, unsigned long addr,
 			struct vm_area_struct **pprev)
 {
 	struct vm_area_struct *vma;
+	MA_STATE(mas, &mm->mm_mt, addr, addr);
 
-	vma = find_vma(mm, addr);
-	if (vma) {
-		*pprev = vma->vm_prev;
-	} else {
-		struct rb_node *rb_node = rb_last(&mm->mm_rb);
-
-		*pprev = rb_node ? rb_entry(rb_node, struct vm_area_struct, vm_rb) : NULL;
-	}
+	vma = mas_walk(&mas);
+	*pprev = mas_prev(&mas, 0);
+	if (!vma)
+		vma = mas_next(&mas, ULONG_MAX);
 	return vma;
 }