| 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
| ||
|
Date: Tue, 17 Oct 2023 09:50:20 -0400
From: "Liam R. Howlett" <Liam.Howlett@...cle.com>
To: Peng Zhang <zhangpeng.00@...edance.com>
Cc: corbet@....net, akpm@...ux-foundation.org, willy@...radead.org,
brauner@...nel.org, surenb@...gle.com, michael.christie@...cle.com,
mjguzik@...il.com, mathieu.desnoyers@...icios.com,
npiggin@...il.com, peterz@...radead.org, oliver.sang@...el.com,
mst@...hat.com, maple-tree@...ts.infradead.org, linux-mm@...ck.org,
linux-doc@...r.kernel.org, linux-kernel@...r.kernel.org,
linux-fsdevel@...r.kernel.org
Subject: Re: [PATCH v5 10/10] fork: Use __mt_dup() to duplicate maple tree in
dup_mmap()
* Peng Zhang <zhangpeng.00@...edance.com> [231015 23:23]:
> In dup_mmap(), using __mt_dup() to duplicate the old maple tree and then
> directly replacing the entries of VMAs in the new maple tree can result
> in better performance. __mt_dup() uses DFS pre-order to duplicate the
> maple tree, so it is efficient.
>
> The average time complexity of __mt_dup() is O(n), where n is the number
> of VMAs. The proof of the time complexity is provided in the commit log
> that introduces __mt_dup(). After duplicating the maple tree, each element
> is traversed and replaced (ignoring the cases of deletion, which are rare).
> Since it is only a replacement operation for each element, this process is
> also O(n).
>
> Analyzing the exact time complexity of the previous algorithm is
> challenging because each insertion can involve appending to a node, pushing
> data to adjacent nodes, or even splitting nodes. The frequency of each
> action is difficult to calculate. The worst-case scenario for a single
> insertion is when the tree undergoes splitting at every level. If we
> consider each insertion as the worst-case scenario, we can determine that
> the upper bound of the time complexity is O(n*log(n)), although this is a
> loose upper bound. However, based on the test data, it appears that the
> actual time complexity is likely to be O(n).
>
> As the entire maple tree is duplicated using __mt_dup(), if dup_mmap()
> fails, there will be a portion of VMAs that have not been duplicated in
> the maple tree. To handle this, we mark the failure point with
> XA_ZERO_ENTRY. In exit_mmap(), if this marker is encountered, stop
> releasing VMAs that have not been duplicated after this point.
>
> There is a "spawn" in byte-unixbench[1], which can be used to test the
> performance of fork(). I modified it slightly to make it work with
> different number of VMAs.
>
> Below are the test results. The first row shows the number of VMAs.
> The second and third rows show the number of fork() calls per ten seconds,
> corresponding to next-20231006 and the this patchset, respectively. The
> test results were obtained with CPU binding to avoid scheduler load
> balancing that could cause unstable results. There are still some
> fluctuations in the test results, but at least they are better than the
> original performance.
>
> 21 121 221 421 821 1621 3221 6421 12821 25621 51221
> 112100 76261 54227 34035 20195 11112 6017 3161 1606 802 393
> 114558 83067 65008 45824 28751 16072 8922 4747 2436 1233 599
> 2.19% 8.92% 19.88% 34.64% 42.37% 44.64% 48.28% 50.17% 51.68% 53.74% 52.42%
>
> [1] https://github.com/kdlucas/byte-unixbench/tree/master
>
> Signed-off-by: Peng Zhang <zhangpeng.00@...edance.com>
> ---
> kernel/fork.c | 39 ++++++++++++++++++++++++++++-----------
> mm/memory.c | 7 ++++++-
> mm/mmap.c | 9 ++++++---
> 3 files changed, 40 insertions(+), 15 deletions(-)
>
> diff --git a/kernel/fork.c b/kernel/fork.c
> index 0ff2e0cd4109..0be15501e52e 100644
> --- a/kernel/fork.c
> +++ b/kernel/fork.c
> @@ -650,7 +650,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
> int retval;
> unsigned long charge = 0;
> LIST_HEAD(uf);
> - VMA_ITERATOR(old_vmi, oldmm, 0);
> VMA_ITERATOR(vmi, mm, 0);
>
> uprobe_start_dup_mmap();
> @@ -678,16 +677,21 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
> goto out;
> khugepaged_fork(mm, oldmm);
>
> - retval = vma_iter_bulk_alloc(&vmi, oldmm->map_count);
> - if (retval)
> + /* Use __mt_dup() to efficiently build an identical maple tree. */
> + retval = __mt_dup(&oldmm->mm_mt, &mm->mm_mt, GFP_KERNEL);
> + if (unlikely(retval))
> goto out;
>
> mt_clear_in_rcu(vmi.mas.tree);
> - for_each_vma(old_vmi, mpnt) {
> + for_each_vma(vmi, mpnt) {
> struct file *file;
>
> vma_start_write(mpnt);
> if (mpnt->vm_flags & VM_DONTCOPY) {
> + retval = mas_store_gfp(&vmi.mas, NULL, GFP_KERNEL);
vma_iter_clear_gfp() exists, but needs to be relocated from internal.h
to mm.h to be used here.
> + if (retval)
> + goto loop_out;
> +
> vm_stat_account(mm, mpnt->vm_flags, -vma_pages(mpnt));
> continue;
> }
> @@ -749,9 +753,11 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
> if (is_vm_hugetlb_page(tmp))
> hugetlb_dup_vma_private(tmp);
>
> - /* Link the vma into the MT */
> - if (vma_iter_bulk_store(&vmi, tmp))
> - goto fail_nomem_vmi_store;
> + /*
> + * Link the vma into the MT. After using __mt_dup(), memory
> + * allocation is not necessary here, so it cannot fail.
> + */
Allocations didn't happen here with the bulk store either, and the
vma_iter_bulk_store() does a mas_store() - see include/linux/mm.h
The vma iterator is used when possible for type safety.
> + mas_store(&vmi.mas, tmp);
>
> mm->map_count++;
> if (!(tmp->vm_flags & VM_WIPEONFORK))
> @@ -760,15 +766,28 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
> if (tmp->vm_ops && tmp->vm_ops->open)
> tmp->vm_ops->open(tmp);
>
> - if (retval)
> + if (retval) {
> + mpnt = vma_next(&vmi);
> goto loop_out;
> + }
> }
> /* a new mm has just been created */
> retval = arch_dup_mmap(oldmm, mm);
> loop_out:
> vma_iter_free(&vmi);
> - if (!retval)
> + if (!retval) {
> mt_set_in_rcu(vmi.mas.tree);
> + } else if (mpnt) {
> + /*
> + * The entire maple tree has already been duplicated. If the
> + * mmap duplication fails, mark the failure point with
> + * XA_ZERO_ENTRY. In exit_mmap(), if this marker is encountered,
> + * stop releasing VMAs that have not been duplicated after this
> + * point.
> + */
> + mas_set_range(&vmi.mas, mpnt->vm_start, mpnt->vm_end - 1);
> + mas_store(&vmi.mas, XA_ZERO_ENTRY);
vma_iter_clear() exists but uses the preallocation call. I really don't
want mas_ calls where unnecessary, but this seems like a special case.
We have a vma iterator here so it's messy.
> + }
> out:
> mmap_write_unlock(mm);
> flush_tlb_mm(oldmm);
> @@ -778,8 +797,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
> uprobe_end_dup_mmap();
> return retval;
>
> -fail_nomem_vmi_store:
> - unlink_anon_vmas(tmp);
> fail_nomem_anon_vma_fork:
> mpol_put(vma_policy(tmp));
> fail_nomem_policy:
> diff --git a/mm/memory.c b/mm/memory.c
> index b320af6466cc..ea48bd4b1feb 100644
> --- a/mm/memory.c
> +++ b/mm/memory.c
> @@ -374,6 +374,8 @@ void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas,
> * be 0. This will underflow and is okay.
> */
> next = mas_find(mas, ceiling - 1);
> + if (unlikely(xa_is_zero(next)))
> + next = NULL;
>
> /*
> * Hide vma from rmap and truncate_pagecache before freeing
> @@ -395,6 +397,8 @@ void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas,
> && !is_vm_hugetlb_page(next)) {
> vma = next;
> next = mas_find(mas, ceiling - 1);
> + if (unlikely(xa_is_zero(next)))
> + next = NULL;
> if (mm_wr_locked)
> vma_start_write(vma);
> unlink_anon_vmas(vma);
> @@ -1743,7 +1747,8 @@ void unmap_vmas(struct mmu_gather *tlb, struct ma_state *mas,
> unmap_single_vma(tlb, vma, start, end, &details,
> mm_wr_locked);
> hugetlb_zap_end(vma, &details);
> - } while ((vma = mas_find(mas, tree_end - 1)) != NULL);
> + vma = mas_find(mas, tree_end - 1);
> + } while (vma && likely(!xa_is_zero(vma)));
> mmu_notifier_invalidate_range_end(&range);
> }
>
> diff --git a/mm/mmap.c b/mm/mmap.c
> index 1855a2d84200..12ce17863e62 100644
> --- a/mm/mmap.c
> +++ b/mm/mmap.c
> @@ -3213,10 +3213,11 @@ void exit_mmap(struct mm_struct *mm)
> arch_exit_mmap(mm);
>
> vma = mas_find(&mas, ULONG_MAX);
> - if (!vma) {
> + if (!vma || unlikely(xa_is_zero(vma))) {
> /* Can happen if dup_mmap() received an OOM */
> mmap_read_unlock(mm);
> - return;
> + mmap_write_lock(mm);
> + goto destroy;
> }
>
> lru_add_drain();
> @@ -3251,11 +3252,13 @@ void exit_mmap(struct mm_struct *mm)
> remove_vma(vma, true);
> count++;
> cond_resched();
> - } while ((vma = mas_find(&mas, ULONG_MAX)) != NULL);
> + vma = mas_find(&mas, ULONG_MAX);
> + } while (vma && likely(!xa_is_zero(vma)));
>
> BUG_ON(count != mm->map_count);
>
> trace_exit_mmap(mm);
> +destroy:
> __mt_destroy(&mm->mm_mt);
> mmap_write_unlock(mm);
> vm_unacct_memory(nr_accounted);
> --
> 2.20.1
>
Powered by blists - more mailing lists