linux-kernel - Re: [PATCH v4 09/66] mm/mmap: Use the maple tree in find

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <4207b5a3-efac-40f3-6b42-6713c9283cdd@suse.cz>
Date:   Wed, 15 Dec 2021 14:05:18 +0100
From:   Vlastimil Babka <vbabka@...e.cz>
To:     Liam Howlett <liam.howlett@...cle.com>,
        "maple-tree@...ts.infradead.org" <maple-tree@...ts.infradead.org>,
        "linux-mm@...ck.org" <linux-mm@...ck.org>,
        "linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
        Andrew Morton <akpm@...ux-foundation.org>
Cc:     Song Liu <songliubraving@...com>,
        Davidlohr Bueso <dave@...olabs.net>,
        "Paul E . McKenney" <paulmck@...nel.org>,
        Matthew Wilcox <willy@...radead.org>,
        Laurent Dufour <ldufour@...ux.ibm.com>,
        David Rientjes <rientjes@...gle.com>,
        Axel Rasmussen <axelrasmussen@...gle.com>,
        Suren Baghdasaryan <surenb@...gle.com>,
        Rik van Riel <riel@...riel.com>,
        Peter Zijlstra <peterz@...radead.org>,
        Michel Lespinasse <walken.cr@...il.com>,
        Jerome Glisse <jglisse@...hat.com>,
        Minchan Kim <minchan@...gle.com>,
        Joel Fernandes <joelaf@...gle.com>,
        Rom Lemarchand <romlem@...gle.com>
Subject: Re: [PATCH v4 09/66] mm/mmap: Use the maple tree in find_vma()
 instead of the rbtree.

On 12/1/21 15:29, Liam Howlett wrote:
> From: "Liam R. Howlett" <Liam.Howlett@...cle.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@...cle.com>

Acked-by: Vlastimil Babka <vbabka@...e.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;