Android needs to move large memory regions for garbage collection.
The GC requires moving physical pages of multi-gigabyte heap
using mremap. During this move, the application threads have to
be paused for correctness. It is critical to keep this pause as
short as possible to avoid jitters during user interaction.
Optimize mremap for >= 1GB-sized regions by moving at the PUD/PGD
level if the source and destination addresses are PUD-aligned.
For CONFIG_PGTABLE_LEVELS == 3, moving at the PUD level in effect moves
PGD entries, since the PUD entry is “folded back” onto the PGD entry.
Add HAVE_MOVE_PUD so that architectures where moving at the PUD level
isn't supported/tested can turn this off by not selecting the config.
Fix build test error from v1 of this series reported by
kernel test robot in [1].
[1] https://lists.01.org/hyperkitty/list/[email protected]/thread/CKPGL4FH4NG7TGH2CVYX2UX76L25BTA3/
Signed-off-by: Kalesh Singh <[email protected]>
Reported-by: kernel test robot <[email protected]>
Acked-by: Kirill A. Shutemov <[email protected]>
Cc: Andrew Morton <[email protected]>
---
Changes in v2:
- Update commit message with description of Android GC's use case.
- Move set_pud_at() to a separate patch.
- Use switch() instead of ifs in move_pgt_entry()
- Fix build test error reported by kernel test robot on x86_64 in [1].
Guard move_huge_pmd() with IS_ENABLED(CONFIG_TRANSPARENT_HUGEPAGE),
since this section doesn't get optimized out in the kernel test
robot's build test when HAVE_MOVE_PUD is enabled.
- Keep WARN_ON_ONCE(1) instead of BUILD_BUG() for the aforementioned
reason.
Changes in v3:
- Move get_old_pud() and alloc_new_pud() out of
#ifdef CONFIG_HAVE_MOVE_PUD.
- Have get_old_pmd() and alloc_new_pmd() use get_old_pud() and
alloc_old_pud().
- Use switch() in get_extent() instead of ifs.
- Add BUILD_BUG() to default case of get_extent().
- Replace #ifdef CONFIG_HAVE_MOVE_PMD/PUD in move_page_tables() with
IS_ENABLED(CONFIG_HAVE_MOVE_PMD/PUD).
- Make lines 80 cols or less, where they don’t need to be longer.
- s/= /= /g (Fixed double spaces after '=').
Changes in v4:
- Add Kirill's Acked-by.
arch/Kconfig | 7 ++
mm/mremap.c | 230 ++++++++++++++++++++++++++++++++++++++++++---------
2 files changed, 197 insertions(+), 40 deletions(-)
diff --git a/arch/Kconfig b/arch/Kconfig
index 76ec3395b843..79da6d714264 100644
--- a/arch/Kconfig
+++ b/arch/Kconfig
@@ -608,6 +608,13 @@ config HAVE_IRQ_TIME_ACCOUNTING
Archs need to ensure they use a high enough resolution clock to
support irq time accounting and then call enable_sched_clock_irqtime().
+config HAVE_MOVE_PUD
+ bool
+ help
+ Architectures that select this are able to move page tables at the
+ PUD level. If there are only 3 page table levels, the move effectively
+ happens at the PGD level.
+
config HAVE_MOVE_PMD
bool
help
diff --git a/mm/mremap.c b/mm/mremap.c
index 138abbae4f75..078f731277b6 100644
--- a/mm/mremap.c
+++ b/mm/mremap.c
@@ -30,12 +30,11 @@
#include "internal.h"
-static pmd_t *get_old_pmd(struct mm_struct *mm, unsigned long addr)
+static pud_t *get_old_pud(struct mm_struct *mm, unsigned long addr)
{
pgd_t *pgd;
p4d_t *p4d;
pud_t *pud;
- pmd_t *pmd;
pgd = pgd_offset(mm, addr);
if (pgd_none_or_clear_bad(pgd))
@@ -49,6 +48,18 @@ static pmd_t *get_old_pmd(struct mm_struct *mm, unsigned long addr)
if (pud_none_or_clear_bad(pud))
return NULL;
+ return pud;
+}
+
+static pmd_t *get_old_pmd(struct mm_struct *mm, unsigned long addr)
+{
+ pud_t *pud;
+ pmd_t *pmd;
+
+ pud = get_old_pud(mm, addr);
+ if (!pud)
+ return NULL;
+
pmd = pmd_offset(pud, addr);
if (pmd_none(*pmd))
return NULL;
@@ -56,19 +67,27 @@ static pmd_t *get_old_pmd(struct mm_struct *mm, unsigned long addr)
return pmd;
}
-static pmd_t *alloc_new_pmd(struct mm_struct *mm, struct vm_area_struct *vma,
+static pud_t *alloc_new_pud(struct mm_struct *mm, struct vm_area_struct *vma,
unsigned long addr)
{
pgd_t *pgd;
p4d_t *p4d;
- pud_t *pud;
- pmd_t *pmd;
pgd = pgd_offset(mm, addr);
p4d = p4d_alloc(mm, pgd, addr);
if (!p4d)
return NULL;
- pud = pud_alloc(mm, p4d, addr);
+
+ return pud_alloc(mm, p4d, addr);
+}
+
+static pmd_t *alloc_new_pmd(struct mm_struct *mm, struct vm_area_struct *vma,
+ unsigned long addr)
+{
+ pud_t *pud;
+ pmd_t *pmd;
+
+ pud = alloc_new_pud(mm, vma, addr);
if (!pud)
return NULL;
@@ -249,14 +268,148 @@ static bool move_normal_pmd(struct vm_area_struct *vma, unsigned long old_addr,
return true;
}
+#else
+static inline bool move_normal_pmd(struct vm_area_struct *vma,
+ unsigned long old_addr, unsigned long new_addr, pmd_t *old_pmd,
+ pmd_t *new_pmd)
+{
+ return false;
+}
#endif
+#ifdef CONFIG_HAVE_MOVE_PUD
+static bool move_normal_pud(struct vm_area_struct *vma, unsigned long old_addr,
+ unsigned long new_addr, pud_t *old_pud, pud_t *new_pud)
+{
+ spinlock_t *old_ptl, *new_ptl;
+ struct mm_struct *mm = vma->vm_mm;
+ pud_t pud;
+
+ /*
+ * The destination pud shouldn't be established, free_pgtables()
+ * should have released it.
+ */
+ if (WARN_ON_ONCE(!pud_none(*new_pud)))
+ return false;
+
+ /*
+ * We don't have to worry about the ordering of src and dst
+ * ptlocks because exclusive mmap_lock prevents deadlock.
+ */
+ old_ptl = pud_lock(vma->vm_mm, old_pud);
+ new_ptl = pud_lockptr(mm, new_pud);
+ if (new_ptl != old_ptl)
+ spin_lock_nested(new_ptl, SINGLE_DEPTH_NESTING);
+
+ /* Clear the pud */
+ pud = *old_pud;
+ pud_clear(old_pud);
+
+ VM_BUG_ON(!pud_none(*new_pud));
+
+ /* Set the new pud */
+ set_pud_at(mm, new_addr, new_pud, pud);
+ flush_tlb_range(vma, old_addr, old_addr + PUD_SIZE);
+ if (new_ptl != old_ptl)
+ spin_unlock(new_ptl);
+ spin_unlock(old_ptl);
+
+ return true;
+}
+#else
+static inline bool move_normal_pud(struct vm_area_struct *vma,
+ unsigned long old_addr, unsigned long new_addr, pud_t *old_pud,
+ pud_t *new_pud)
+{
+ return false;
+}
+#endif
+
+enum pgt_entry {
+ NORMAL_PMD,
+ HPAGE_PMD,
+ NORMAL_PUD,
+};
+
+/*
+ * Returns an extent of the corresponding size for the pgt_entry specified if
+ * valid. Else returns a smaller extent bounded by the end of the source and
+ * destination pgt_entry.
+ */
+static unsigned long get_extent(enum pgt_entry entry, unsigned long old_addr,
+ unsigned long old_end, unsigned long new_addr)
+{
+ unsigned long next, extent, mask, size;
+
+ switch (entry) {
+ case HPAGE_PMD:
+ case NORMAL_PMD:
+ mask = PMD_MASK;
+ size = PMD_SIZE;
+ break;
+ case NORMAL_PUD:
+ mask = PUD_MASK;
+ size = PUD_SIZE;
+ break;
+ default:
+ BUILD_BUG();
+ break;
+ }
+
+ next = (old_addr + size) & mask;
+ /* even if next overflowed, extent below will be ok */
+ extent = (next > old_end) ? old_end - old_addr : next - old_addr;
+ next = (new_addr + size) & mask;
+ if (extent > next - new_addr)
+ extent = next - new_addr;
+ return extent;
+}
+
+/*
+ * Attempts to speedup the move by moving entry at the level corresponding to
+ * pgt_entry. Returns true if the move was successful, else false.
+ */
+static bool move_pgt_entry(enum pgt_entry entry, struct vm_area_struct *vma,
+ unsigned long old_addr, unsigned long new_addr,
+ void *old_entry, void *new_entry, bool need_rmap_locks)
+{
+ bool moved = false;
+
+ /* See comment in move_ptes() */
+ if (need_rmap_locks)
+ take_rmap_locks(vma);
+
+ switch (entry) {
+ case NORMAL_PMD:
+ moved = move_normal_pmd(vma, old_addr, new_addr, old_entry,
+ new_entry);
+ break;
+ case NORMAL_PUD:
+ moved = move_normal_pud(vma, old_addr, new_addr, old_entry,
+ new_entry);
+ break;
+ case HPAGE_PMD:
+ moved = IS_ENABLED(CONFIG_TRANSPARENT_HUGEPAGE) &&
+ move_huge_pmd(vma, old_addr, new_addr, old_entry,
+ new_entry);
+ break;
+ default:
+ WARN_ON_ONCE(1);
+ break;
+ }
+
+ if (need_rmap_locks)
+ drop_rmap_locks(vma);
+
+ return moved;
+}
+
unsigned long move_page_tables(struct vm_area_struct *vma,
unsigned long old_addr, struct vm_area_struct *new_vma,
unsigned long new_addr, unsigned long len,
bool need_rmap_locks)
{
- unsigned long extent, next, old_end;
+ unsigned long extent, old_end;
struct mmu_notifier_range range;
pmd_t *old_pmd, *new_pmd;
@@ -269,53 +422,50 @@ unsigned long move_page_tables(struct vm_area_struct *vma,
for (; old_addr < old_end; old_addr += extent, new_addr += extent) {
cond_resched();
- next = (old_addr + PMD_SIZE) & PMD_MASK;
- /* even if next overflowed, extent below will be ok */
- extent = next - old_addr;
- if (extent > old_end - old_addr)
- extent = old_end - old_addr;
- next = (new_addr + PMD_SIZE) & PMD_MASK;
- if (extent > next - new_addr)
- extent = next - new_addr;
+ /*
+ * If extent is PUD-sized try to speed up the move by moving at the
+ * PUD level if possible.
+ */
+ extent = get_extent(NORMAL_PUD, old_addr, old_end, new_addr);
+ if (IS_ENABLED(CONFIG_HAVE_MOVE_PUD) && extent == PUD_SIZE) {
+ pud_t *old_pud, *new_pud;
+
+ old_pud = get_old_pud(vma->vm_mm, old_addr);
+ if (!old_pud)
+ continue;
+ new_pud = alloc_new_pud(vma->vm_mm, vma, new_addr);
+ if (!new_pud)
+ break;
+ if (move_pgt_entry(NORMAL_PUD, vma, old_addr, new_addr,
+ old_pud, new_pud, need_rmap_locks))
+ continue;
+ }
+
+ extent = get_extent(NORMAL_PMD, old_addr, old_end, new_addr);
old_pmd = get_old_pmd(vma->vm_mm, old_addr);
if (!old_pmd)
continue;
new_pmd = alloc_new_pmd(vma->vm_mm, vma, new_addr);
if (!new_pmd)
break;
- if (is_swap_pmd(*old_pmd) || pmd_trans_huge(*old_pmd) || pmd_devmap(*old_pmd)) {
- if (extent == HPAGE_PMD_SIZE) {
- bool moved;
- /* See comment in move_ptes() */
- if (need_rmap_locks)
- take_rmap_locks(vma);
- moved = move_huge_pmd(vma, old_addr, new_addr,
- old_pmd, new_pmd);
- if (need_rmap_locks)
- drop_rmap_locks(vma);
- if (moved)
- continue;
- }
+ if (is_swap_pmd(*old_pmd) || pmd_trans_huge(*old_pmd) ||
+ pmd_devmap(*old_pmd)) {
+ if (extent == HPAGE_PMD_SIZE &&
+ move_pgt_entry(HPAGE_PMD, vma, old_addr, new_addr,
+ old_pmd, new_pmd, need_rmap_locks))
+ continue;
split_huge_pmd(vma, old_pmd, old_addr);
if (pmd_trans_unstable(old_pmd))
continue;
- } else if (extent == PMD_SIZE) {
-#ifdef CONFIG_HAVE_MOVE_PMD
+ } else if (IS_ENABLED(CONFIG_HAVE_MOVE_PMD) &&
+ extent == PMD_SIZE) {
/*
* If the extent is PMD-sized, try to speed the move by
* moving at the PMD level if possible.
*/
- bool moved;
-
- if (need_rmap_locks)
- take_rmap_locks(vma);
- moved = move_normal_pmd(vma, old_addr, new_addr,
- old_pmd, new_pmd);
- if (need_rmap_locks)
- drop_rmap_locks(vma);
- if (moved)
+ if (move_pgt_entry(NORMAL_PMD, vma, old_addr, new_addr,
+ old_pmd, new_pmd, need_rmap_locks))
continue;
-#endif
}
if (pte_alloc(new_vma->vm_mm, new_pmd))
--
2.28.0.1011.ga647a8990f-goog
On Wed, Oct 14, 2020 at 12:53:08AM +0000, Kalesh Singh wrote:
> Android needs to move large memory regions for garbage collection.
> The GC requires moving physical pages of multi-gigabyte heap
> using mremap. During this move, the application threads have to
> be paused for correctness. It is critical to keep this pause as
> short as possible to avoid jitters during user interaction.
>
> Optimize mremap for >= 1GB-sized regions by moving at the PUD/PGD
> level if the source and destination addresses are PUD-aligned.
> For CONFIG_PGTABLE_LEVELS == 3, moving at the PUD level in effect moves
> PGD entries, since the PUD entry is “folded back” onto the PGD entry.
> Add HAVE_MOVE_PUD so that architectures where moving at the PUD level
> isn't supported/tested can turn this off by not selecting the config.
>
> Fix build test error from v1 of this series reported by
> kernel test robot in [1].
>
> [1] https://lists.01.org/hyperkitty/list/[email protected]/thread/CKPGL4FH4NG7TGH2CVYX2UX76L25BTA3/
>
> Signed-off-by: Kalesh Singh <[email protected]>
> Reported-by: kernel test robot <[email protected]>
> Acked-by: Kirill A. Shutemov <[email protected]>
> Cc: Andrew Morton <[email protected]>
I thought I reported it, but maybe I didn't. This patch causes all
'parisc' qemu emulations to fail. Typical log:
Freeing unused kernel memory: 604K
Write protected read-only-after-init data: 2k
rodata_test: end of .rodata is not page size aligned
Run /sbin/init as init process
process '/bin/busybox' started with executable stack
Failed to execute /sbin/init (error -12)
Reverting this patch fixes the problem.
Bisect log from linux-next below. The patch (and thus the problem)
are now in mainline Linux.
Guenter
---
# bad: [7bba37a1591369e2e506d599b8f5d7d0516b2dbc] Add linux-next specific files for 20201214
# good: [0477e92881850d44910a7e94fc2c46f96faa131f] Linux 5.10-rc7
git bisect start 'HEAD' 'v5.10-rc7'
# good: [fe5c40ab90a1f82ba97294637eaf875cfdd7a05f] Merge remote-tracking branch 'nand/nand/next'
git bisect good fe5c40ab90a1f82ba97294637eaf875cfdd7a05f
# good: [674a0d6de8bd290671f7dff405205871a70300b3] Merge remote-tracking branch 'spi/for-next'
git bisect good 674a0d6de8bd290671f7dff405205871a70300b3
# good: [8623dae312f73a2ea3230b1c648d3004cfc224ce] Merge remote-tracking branch 'vfio/next'
git bisect good 8623dae312f73a2ea3230b1c648d3004cfc224ce
# good: [dd26635f54bcd8e5d4e875a209f82a0423ba9c08] Merge remote-tracking branch 'gpio/for-next'
git bisect good dd26635f54bcd8e5d4e875a209f82a0423ba9c08
# good: [86e9c9a734889fe437442e0a35eb4c61d319cb47] Merge remote-tracking branch 'memblock/for-next'
git bisect good 86e9c9a734889fe437442e0a35eb4c61d319cb47
# bad: [3452331fda80b1cb5e121e6718ca6c07264382b2] userfaultfd: add user-mode only option to unprivileged_userfaultfd sysctl knob
git bisect bad 3452331fda80b1cb5e121e6718ca6c07264382b2
# bad: [19f468d54fcffc3f98b71e3e12ff23726767d953] mremap: don't allow MREMAP_DONTUNMAP on special_mappings and aio
git bisect bad 19f468d54fcffc3f98b71e3e12ff23726767d953
# good: [d89f3ababcac54493a4cb0582c61eb5f426b44e3] mm: remove pagevec_lookup_range_nr_tag()
git bisect good d89f3ababcac54493a4cb0582c61eb5f426b44e3
# good: [eba8373dcb40d30952f31d5fc0cff56b78f46273] mm/mlock: remove __munlock_isolate_lru_page()
git bisect good eba8373dcb40d30952f31d5fc0cff56b78f46273
# good: [8831d3f3564beba0f3f1b5291c88b35725bc45c9] xen/unpopulated-alloc: consolidate pgmap manipulation
git bisect good 8831d3f3564beba0f3f1b5291c88b35725bc45c9
# bad: [b8d53d70851821d8a2040ddca3aa6ee88fc8aaec] mm/page_vma_mapped.c: add colon to fix kernel-doc markups error for check_pte
git bisect bad b8d53d70851821d8a2040ddca3aa6ee88fc8aaec
# bad: [e77846c3da1862faa25c08e186a62b03e98c862f] x86: mremap speedup - Enable HAVE_MOVE_PUD
git bisect bad e77846c3da1862faa25c08e186a62b03e98c862f
# bad: [72ad8951bac1c559ea1b691a0b035fb339e4d71d] mm: speedup mremap on 1GB or larger regions
git bisect bad 72ad8951bac1c559ea1b691a0b035fb339e4d71d
# good: [fa94bfe31609787501a1ff8d7659ade5734ec4e5] kselftests: vm: add mremap tests
git bisect good fa94bfe31609787501a1ff8d7659ade5734ec4e5
# first bad commit: [72ad8951bac1c559ea1b691a0b035fb339e4d71d] mm: speedup mremap on 1GB or larger regions
On Thu, Dec 17, 2020 at 12:28 PM Guenter Roeck <[email protected]> wrote:
>
> On Wed, Oct 14, 2020 at 12:53:08AM +0000, Kalesh Singh wrote:
> > Android needs to move large memory regions for garbage collection.
> > The GC requires moving physical pages of multi-gigabyte heap
> > using mremap. During this move, the application threads have to
> > be paused for correctness. It is critical to keep this pause as
> > short as possible to avoid jitters during user interaction.
> >
> > Optimize mremap for >= 1GB-sized regions by moving at the PUD/PGD
> > level if the source and destination addresses are PUD-aligned.
> > For CONFIG_PGTABLE_LEVELS == 3, moving at the PUD level in effect moves
> > PGD entries, since the PUD entry is “folded back” onto the PGD entry.
> > Add HAVE_MOVE_PUD so that architectures where moving at the PUD level
> > isn't supported/tested can turn this off by not selecting the config.
> >
> > Fix build test error from v1 of this series reported by
> > kernel test robot in [1].
> >
> > [1] https://lists.01.org/hyperkitty/list/[email protected]/thread/CKPGL4FH4NG7TGH2CVYX2UX76L25BTA3/
> >
> > Signed-off-by: Kalesh Singh <[email protected]>
> > Reported-by: kernel test robot <[email protected]>
> > Acked-by: Kirill A. Shutemov <[email protected]>
> > Cc: Andrew Morton <[email protected]>
>
> I thought I reported it, but maybe I didn't. This patch causes all
> 'parisc' qemu emulations to fail. Typical log:
>
> Freeing unused kernel memory: 604K
> Write protected read-only-after-init data: 2k
> rodata_test: end of .rodata is not page size aligned
> Run /sbin/init as init process
> process '/bin/busybox' started with executable stack
> Failed to execute /sbin/init (error -12)
>
> Reverting this patch fixes the problem.
>
> Bisect log from linux-next below. The patch (and thus the problem)
> are now in mainline Linux.
Hi Guenter,
Thanks for reporting. We enabled this on x86 and arm64. Investigating
what the root cause is now.
Kalesh
>
> Guenter
>
> ---
> # bad: [7bba37a1591369e2e506d599b8f5d7d0516b2dbc] Add linux-next specific files for 20201214
> # good: [0477e92881850d44910a7e94fc2c46f96faa131f] Linux 5.10-rc7
> git bisect start 'HEAD' 'v5.10-rc7'
> # good: [fe5c40ab90a1f82ba97294637eaf875cfdd7a05f] Merge remote-tracking branch 'nand/nand/next'
> git bisect good fe5c40ab90a1f82ba97294637eaf875cfdd7a05f
> # good: [674a0d6de8bd290671f7dff405205871a70300b3] Merge remote-tracking branch 'spi/for-next'
> git bisect good 674a0d6de8bd290671f7dff405205871a70300b3
> # good: [8623dae312f73a2ea3230b1c648d3004cfc224ce] Merge remote-tracking branch 'vfio/next'
> git bisect good 8623dae312f73a2ea3230b1c648d3004cfc224ce
> # good: [dd26635f54bcd8e5d4e875a209f82a0423ba9c08] Merge remote-tracking branch 'gpio/for-next'
> git bisect good dd26635f54bcd8e5d4e875a209f82a0423ba9c08
> # good: [86e9c9a734889fe437442e0a35eb4c61d319cb47] Merge remote-tracking branch 'memblock/for-next'
> git bisect good 86e9c9a734889fe437442e0a35eb4c61d319cb47
> # bad: [3452331fda80b1cb5e121e6718ca6c07264382b2] userfaultfd: add user-mode only option to unprivileged_userfaultfd sysctl knob
> git bisect bad 3452331fda80b1cb5e121e6718ca6c07264382b2
> # bad: [19f468d54fcffc3f98b71e3e12ff23726767d953] mremap: don't allow MREMAP_DONTUNMAP on special_mappings and aio
> git bisect bad 19f468d54fcffc3f98b71e3e12ff23726767d953
> # good: [d89f3ababcac54493a4cb0582c61eb5f426b44e3] mm: remove pagevec_lookup_range_nr_tag()
> git bisect good d89f3ababcac54493a4cb0582c61eb5f426b44e3
> # good: [eba8373dcb40d30952f31d5fc0cff56b78f46273] mm/mlock: remove __munlock_isolate_lru_page()
> git bisect good eba8373dcb40d30952f31d5fc0cff56b78f46273
> # good: [8831d3f3564beba0f3f1b5291c88b35725bc45c9] xen/unpopulated-alloc: consolidate pgmap manipulation
> git bisect good 8831d3f3564beba0f3f1b5291c88b35725bc45c9
> # bad: [b8d53d70851821d8a2040ddca3aa6ee88fc8aaec] mm/page_vma_mapped.c: add colon to fix kernel-doc markups error for check_pte
> git bisect bad b8d53d70851821d8a2040ddca3aa6ee88fc8aaec
> # bad: [e77846c3da1862faa25c08e186a62b03e98c862f] x86: mremap speedup - Enable HAVE_MOVE_PUD
> git bisect bad e77846c3da1862faa25c08e186a62b03e98c862f
> # bad: [72ad8951bac1c559ea1b691a0b035fb339e4d71d] mm: speedup mremap on 1GB or larger regions
> git bisect bad 72ad8951bac1c559ea1b691a0b035fb339e4d71d
> # good: [fa94bfe31609787501a1ff8d7659ade5734ec4e5] kselftests: vm: add mremap tests
> git bisect good fa94bfe31609787501a1ff8d7659ade5734ec4e5
> # first bad commit: [72ad8951bac1c559ea1b691a0b035fb339e4d71d] mm: speedup mremap on 1GB or larger regions
>
> --
> To unsubscribe from this group and stop receiving emails from it, send an email to [email protected].
>