2019-06-03 07:45:04 +02:00
|
|
|
|
2012-10-08 16:31:25 -07:00
|
|
|
|
2026-07-10 21:16:46 +01:00
|
|
|
|
|
|
|
|
|
2012-10-08 16:31:25 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
mm anon rmap: replace same_anon_vma linked list with an interval tree.
When a large VMA (anon or private file mapping) is first touched, which
will populate its anon_vma field, and then split into many regions through
the use of mprotect(), the original anon_vma ends up linking all of the
vmas on a linked list. This can cause rmap to become inefficient, as we
have to walk potentially thousands of irrelevent vmas before finding the
one a given anon page might fall into.
By replacing the same_anon_vma linked list with an interval tree (where
each avc's interval is determined by its vma's start and last pgoffs), we
can make rmap efficient for this use case again.
While the change is large, all of its pieces are fairly simple.
Most places that were walking the same_anon_vma list were looking for a
known pgoff, so they can just use the anon_vma_interval_tree_foreach()
interval tree iterator instead. The exception here is ksm, where the
page's index is not known. It would probably be possible to rework ksm so
that the index would be known, but for now I have decided to keep things
simple and just walk the entirety of the interval tree there.
When updating vma's that already have an anon_vma assigned, we must take
care to re-index the corresponding avc's on their interval tree. This is
done through the use of anon_vma_interval_tree_pre_update_vma() and
anon_vma_interval_tree_post_update_vma(), which remove the avc's from
their interval tree before the update and re-insert them after the update.
The anon_vma stays locked during the update, so there is no chance that
rmap would miss the vmas that are being updated.
Signed-off-by: Michel Lespinasse <walken@google.com>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Cc: Rik van Riel <riel@redhat.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Daniel Santos <daniel.santos@pobox.com>
Cc: Hugh Dickins <hughd@google.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2012-10-08 16:31:39 -07:00
|
|
|
|
2012-10-08 16:31:35 -07:00
|
|
|
|
2012-10-08 16:31:25 -07:00
|
|
|
|
2026-07-10 21:16:46 +01:00
|
|
|
|
|
|
|
|
|
2015-02-10 14:10:02 -08:00
|
|
|
|
2026-07-10 21:16:47 +01:00
|
|
|
|
|
|
|
|
|
2026-07-10 21:16:49 +01:00
|
|
|
|
2012-10-08 16:31:35 -07:00
|
|
|
|
2026-07-10 21:16:49 +01:00
|
|
|
|
2026-07-10 21:16:47 +01:00
|
|
|
|
|
|
|
|
|
2026-07-10 21:16:49 +01:00
|
|
|
|
2026-07-10 21:16:47 +01:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2026-07-10 21:16:49 +01:00
|
|
|
|
2012-10-08 16:31:35 -07:00
|
|
|
|
2026-07-10 21:16:47 +01:00
|
|
|
|
2012-10-08 16:31:25 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2026-07-10 21:16:47 +01:00
|
|
|
|
2012-10-08 16:31:25 -07:00
|
|
|
|
2026-07-10 21:16:47 +01:00
|
|
|
|
2012-10-08 16:31:25 -07:00
|
|
|
|
2015-02-10 14:10:02 -08:00
|
|
|
|
2012-10-08 16:31:35 -07:00
|
|
|
|
2015-02-10 14:10:02 -08:00
|
|
|
|
2012-10-08 16:31:25 -07:00
|
|
|
|
2015-02-10 14:10:02 -08:00
|
|
|
|
|
|
|
|
|
2026-07-10 21:16:47 +01:00
|
|
|
|
|
|
|
|
|
2015-02-10 14:10:02 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2026-07-10 21:16:47 +01:00
|
|
|
|
|
|
|
|
|
2012-10-08 16:31:25 -07:00
|
|
|
|
2015-02-10 14:10:02 -08:00
|
|
|
|
2012-10-08 16:31:25 -07:00
|
|
|
|
|
|
|
|
|
2026-07-10 21:16:47 +01:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2026-07-10 21:16:49 +01:00
|
|
|
|
2026-07-10 21:16:47 +01:00
|
|
|
|
|
|
|
|
|
2026-07-10 21:16:49 +01:00
|
|
|
|
2026-07-10 21:16:47 +01:00
|
|
|
|
|
|
|
|
|
2026-07-10 21:16:49 +01:00
|
|
|
|
2026-07-10 21:16:47 +01:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2026-07-10 21:16:49 +01:00
|
|
|
|
2026-07-10 21:16:47 +01:00
|
|
|
|
|
|
|
|
|
2026-07-10 21:16:49 +01:00
|
|
|
|
2026-07-10 21:16:47 +01:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2026-07-10 21:16:49 +01:00
|
|
|
|
2026-07-10 21:16:47 +01:00
|
|
|
|
|
|
|
|
|
2026-07-10 21:16:49 +01:00
|
|
|
|
2012-10-08 16:31:25 -07:00
|
|
|
|
mm anon rmap: replace same_anon_vma linked list with an interval tree.
When a large VMA (anon or private file mapping) is first touched, which
will populate its anon_vma field, and then split into many regions through
the use of mprotect(), the original anon_vma ends up linking all of the
vmas on a linked list. This can cause rmap to become inefficient, as we
have to walk potentially thousands of irrelevent vmas before finding the
one a given anon page might fall into.
By replacing the same_anon_vma linked list with an interval tree (where
each avc's interval is determined by its vma's start and last pgoffs), we
can make rmap efficient for this use case again.
While the change is large, all of its pieces are fairly simple.
Most places that were walking the same_anon_vma list were looking for a
known pgoff, so they can just use the anon_vma_interval_tree_foreach()
interval tree iterator instead. The exception here is ksm, where the
page's index is not known. It would probably be possible to rework ksm so
that the index would be known, but for now I have decided to keep things
simple and just walk the entirety of the interval tree there.
When updating vma's that already have an anon_vma assigned, we must take
care to re-index the corresponding avc's on their interval tree. This is
done through the use of anon_vma_interval_tree_pre_update_vma() and
anon_vma_interval_tree_post_update_vma(), which remove the avc's from
their interval tree before the update and re-insert them after the update.
The anon_vma stays locked during the update, so there is no chance that
rmap would miss the vmas that are being updated.
Signed-off-by: Michel Lespinasse <walken@google.com>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Cc: Rik van Riel <riel@redhat.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Daniel Santos <daniel.santos@pobox.com>
Cc: Hugh Dickins <hughd@google.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2012-10-08 16:31:39 -07:00
|
|
|
|
2026-07-10 21:16:46 +01:00
|
|
|
|
|
|
|
|
|
2026-07-10 21:16:51 +01:00
|
|
|
|
mm anon rmap: replace same_anon_vma linked list with an interval tree.
When a large VMA (anon or private file mapping) is first touched, which
will populate its anon_vma field, and then split into many regions through
the use of mprotect(), the original anon_vma ends up linking all of the
vmas on a linked list. This can cause rmap to become inefficient, as we
have to walk potentially thousands of irrelevent vmas before finding the
one a given anon page might fall into.
By replacing the same_anon_vma linked list with an interval tree (where
each avc's interval is determined by its vma's start and last pgoffs), we
can make rmap efficient for this use case again.
While the change is large, all of its pieces are fairly simple.
Most places that were walking the same_anon_vma list were looking for a
known pgoff, so they can just use the anon_vma_interval_tree_foreach()
interval tree iterator instead. The exception here is ksm, where the
page's index is not known. It would probably be possible to rework ksm so
that the index would be known, but for now I have decided to keep things
simple and just walk the entirety of the interval tree there.
When updating vma's that already have an anon_vma assigned, we must take
care to re-index the corresponding avc's on their interval tree. This is
done through the use of anon_vma_interval_tree_pre_update_vma() and
anon_vma_interval_tree_post_update_vma(), which remove the avc's from
their interval tree before the update and re-insert them after the update.
The anon_vma stays locked during the update, so there is no chance that
rmap would miss the vmas that are being updated.
Signed-off-by: Michel Lespinasse <walken@google.com>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Cc: Rik van Riel <riel@redhat.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Daniel Santos <daniel.santos@pobox.com>
Cc: Hugh Dickins <hughd@google.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2012-10-08 16:31:39 -07:00
|
|
|
|
mm/rmap: use anon pgoff to track MAP_PRIVATE file-backed anon folios
Currently anonymous folios belonging to CoW'd MAP_PRIVATE file-backed
mappings are indexed by their page offset within the file in which they
were originally mapped.
This differs from anonymous folios belonging to pure anon mappings which
are indexed by their anonymous page offset (the address at which they'd
belong in the VMA when first faulted).
This change fixes this inconsistency, always indexing anonymous folios by
their anonymous page offset regardless of the VMA to which they belong.
The foundations have been laid such that we need only switch this
functionality on such by:
* Using linear_anon_page_index() in __folio_set_anon() to assign the
folio's index to the anonymous linear index rather than the file-backed
one.
* Otherwise using linear_anon_page_index() in all instances where
anonymous folios are being referenced or manipulated.
* Replacing vma_address() with vma_filebacked_address() or
vma_anon_address() as appropriate.
* Updating the merging logic to check that anonymous page offsets are
aligned as well as filebacked ones for MAP_PRIVATE file-backed VMAs,
introducing needs_adjacent_anon_pgoff() to figure out when this is
required.
* Updating linear_folio_page_index() to invoke linear_anon_page_index()
if the folio is anonymous.
* Updating vma_address_end() to use the VMA's anonymous page offset when
pvmw->pgoff is anonymous.
* Correcting folio_within_range() to use anonymous page offset for
anonymous folios.
This will have no impact on merging of anonymous VMAs, whose page offset
and anonymous page offset are identical, nor will it impact shared
file-backed VMAs, which will continue to be merged based on the
file-backed page offset.
However, MAP_PRIVATE file-backed mappings must now be aligned on anonymous
page offset as well.
In most instances this should have no impact on merging of file-backed
mappings, which are usually not merged all that often, let alone
MAP_PRIVATE mapped ones, and rarely remapped and faulted before being
moved back in place (the case in which a merge may now fail).
One subtle impact of this change is in NUMA interleaving - since commit
88c91dc58582 ("mempolicy: migration attempt to match interleave nodes"),
migration heuristically tries to maintain interleaving behaviour matching
the policy using folio indices.
When doing migration of CoW'd MAP_PRIVATE-file backed ranges, the 'base'
upon which the interleaving behaviour is performed will vary for these
ranges. However the commit notes that ranges spanning multiple VMAs will
already cause varying bases, and that this is an acceptable approximation.
It is very unlikely real world use-cases will be impacted by this
(MAP_PRIVATE file-backed mappings are already an edge case), and all that
will happen is that such ranges will cause interleaving to be rotated over
the CoW'd range, with little to no impact.
This commit lays the foundations for future scalable CoW work which needs
to track some remaps, meaning that most remap tracking can be avoided, and
in nearly all cases the anonymous page offset will be able to be used to
quickly find the VMA in an mm.
Note that the need_rmap_locks check doesn't need to be updated, as any
remapping will offset both the anonymous and file-backed page offset, so
it suffices to check only one.
Link: https://lore.kernel.org/20260813-b4-scalable-cow-virt-pgoff-v5-14-c21581c0c3c8@kernel.org
Signed-off-by: Lorenzo Stoakes (ARM) <ljs@kernel.org>
Acked-by: David Hildenbrand (Arm) <david@kernel.org>
Cc: Adrian Hunter <adrian.hunter@intel.com>
Cc: Alexander Deucher <alexander.deucher@amd.com>
Cc: Alexander Gordeev <agordeev@linux.ibm.com>
Cc: Alexander Shishkin <alexander.shishkin@linux.intel.com>
Cc: Alistair Popple <apopple@nvidia.com>
Cc: Arnaldo Carvalho de Melo <acme@kernel.org>
Cc: Arnd Bergmann <arnd@arndb.de>
Cc: Baolin Wang <baolin.wang@linux.alibaba.com>
Cc: Baoquan He <baoquan.he@linux.dev>
Cc: Barry Song <baohua@kernel.org>
Cc: Boris Brezillon <boris.brezillon@collabora.com>
Cc: Byungchul Park <byungchul@sk.com>
Cc: Chengming Zhou <chengming.zhou@linux.dev>
Cc: Chris Li <chrisl@kernel.org>
Cc: Christan König <christian.koenig@amd.com>
Cc: Christian Borntraeger <borntraeger@linux.ibm.com>
Cc: Claudio Imbrenda <imbrenda@linux.ibm.com>
Cc: Dave Airlie <airlied@gmail.com>
Cc: Dev Jain <dev.jain@arm.com>
Cc: Gerald Schaefer <gerald.schaefer@linux.ibm.com>
Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
Cc: Gregory Price (Meta) <gourry@gourry.net>
Cc: Harry Yoo <harry@kernel.org>
Cc: Heiko Carstens <hca@linux.ibm.com>
Cc: Huang Ray <Ray.Huang@amd.com>
Cc: "Huang, Ying" <ying.huang@linux.alibaba.com>
Cc: Ian Rogers <irogers@google.com>
Cc: Ingo Molnar <mingo@redhat.com>
Cc: James Clark <james.clark@linaro.org>
Cc: Jan Kara <jack@suse.cz>
Cc: Jann Horn <jannh@google.com>
Cc: Janosch Frank <frankja@linux.ibm.com>
Cc: Jason Gunthorpe <jgg@ziepe.ca>
Cc: Jiri Olsa <jolsa@kernel.org>
Cc: John Hubbard <jhubbard@nvidia.com>
Cc: Joshua Hahn <joshua.hahnjy@gmail.com>
Cc: Kairui Song <kasong@tencent.com>
Cc: Kees Cook <kees@kernel.org>
Cc: Kemeng Shi <shikemeng@huaweicloud.com>
Cc: Lance Yang <lance.yang@linux.dev>
Cc: Liam R. Howlett <liam@infradead.org>
Cc: Liviu Dudau <liviu.dudau@arm.com>
Cc: Maarten Lankhorst <maarten.lankhorst@linux.intel.com>
Cc: Marc Rutland <mark.rutland@arm.com>
Cc: "Masami Hiramatsu (Google)" <mhiramat@kernel.org>
Cc: Matthew Auld <matthew.auld@intel.com>
Cc: Matthew Brost <matthew.brost@intel.com>
Cc: Matthew Wilcox (Oracle) <willy@infradead.org>
Cc: Maxime Ripard <mripard@kernel.org>
Cc: Miaohe Lin <linmiaohe@huawei.com>
Cc: Michal Hocko <mhocko@suse.com>
Cc: Mike Rapoport <rppt@kernel.org>
Cc: Muchun Song <muchun.song@linux.dev>
Cc: Namhyung kim <namhyung@kernel.org>
Cc: Naoya Horiguchi <nao.horiguchi@gmail.com>
Cc: Nhat Pham <nphamcs@gmail.com>
Cc: Nico Pache <npache@redhat.com>
Cc: Oleg Nesterov <oleg@redhat.com>
Cc: Oscar Salvador <osalvador@suse.de>
Cc: Pedro Falcato <pfalcato@suse.de>
Cc: Peter Xu <peterx@redhat.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Rakie Kim <rakie.kim@sk.com>
Cc: Rik van Riel <riel@surriel.com>
Cc: Rodrigo Vivi <rodrigo.vivi@intel.com>
Cc: Ryan Roberts <ryan.roberts@arm.com>
Cc: Steven Price <steven.price@arm.com>
Cc: Suren Baghdasaryan <surenb@google.com>
Cc: Sven Schnelle <svens@linux.ibm.com>
Cc: Thomas Hellström <thomas.hellstrom@linux.intel.com>
Cc: Thomas Zimemrmann <tzimmermann@suse.de>
Cc: Vasily Gorbik <gor@linux.ibm.com>
Cc: Vlastimil Babka <vbabka@kernel.org>
Cc: xu xin <xu.xin16@zte.com.cn>
Cc: Zi Yan <ziy@nvidia.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
2026-08-13 18:32:31 +01:00
|
|
|
|
mm anon rmap: replace same_anon_vma linked list with an interval tree.
When a large VMA (anon or private file mapping) is first touched, which
will populate its anon_vma field, and then split into many regions through
the use of mprotect(), the original anon_vma ends up linking all of the
vmas on a linked list. This can cause rmap to become inefficient, as we
have to walk potentially thousands of irrelevent vmas before finding the
one a given anon page might fall into.
By replacing the same_anon_vma linked list with an interval tree (where
each avc's interval is determined by its vma's start and last pgoffs), we
can make rmap efficient for this use case again.
While the change is large, all of its pieces are fairly simple.
Most places that were walking the same_anon_vma list were looking for a
known pgoff, so they can just use the anon_vma_interval_tree_foreach()
interval tree iterator instead. The exception here is ksm, where the
page's index is not known. It would probably be possible to rework ksm so
that the index would be known, but for now I have decided to keep things
simple and just walk the entirety of the interval tree there.
When updating vma's that already have an anon_vma assigned, we must take
care to re-index the corresponding avc's on their interval tree. This is
done through the use of anon_vma_interval_tree_pre_update_vma() and
anon_vma_interval_tree_post_update_vma(), which remove the avc's from
their interval tree before the update and re-insert them after the update.
The anon_vma stays locked during the update, so there is no chance that
rmap would miss the vmas that are being updated.
Signed-off-by: Michel Lespinasse <walken@google.com>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Cc: Rik van Riel <riel@redhat.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Daniel Santos <daniel.santos@pobox.com>
Cc: Hugh Dickins <hughd@google.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2012-10-08 16:31:39 -07:00
|
|
|
|
|
|
|
|
|
2026-07-10 21:16:51 +01:00
|
|
|
|
mm anon rmap: replace same_anon_vma linked list with an interval tree.
When a large VMA (anon or private file mapping) is first touched, which
will populate its anon_vma field, and then split into many regions through
the use of mprotect(), the original anon_vma ends up linking all of the
vmas on a linked list. This can cause rmap to become inefficient, as we
have to walk potentially thousands of irrelevent vmas before finding the
one a given anon page might fall into.
By replacing the same_anon_vma linked list with an interval tree (where
each avc's interval is determined by its vma's start and last pgoffs), we
can make rmap efficient for this use case again.
While the change is large, all of its pieces are fairly simple.
Most places that were walking the same_anon_vma list were looking for a
known pgoff, so they can just use the anon_vma_interval_tree_foreach()
interval tree iterator instead. The exception here is ksm, where the
page's index is not known. It would probably be possible to rework ksm so
that the index would be known, but for now I have decided to keep things
simple and just walk the entirety of the interval tree there.
When updating vma's that already have an anon_vma assigned, we must take
care to re-index the corresponding avc's on their interval tree. This is
done through the use of anon_vma_interval_tree_pre_update_vma() and
anon_vma_interval_tree_post_update_vma(), which remove the avc's from
their interval tree before the update and re-insert them after the update.
The anon_vma stays locked during the update, so there is no chance that
rmap would miss the vmas that are being updated.
Signed-off-by: Michel Lespinasse <walken@google.com>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Cc: Rik van Riel <riel@redhat.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Daniel Santos <daniel.santos@pobox.com>
Cc: Hugh Dickins <hughd@google.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2012-10-08 16:31:39 -07:00
|
|
|
|
mm/rmap: use anon pgoff to track MAP_PRIVATE file-backed anon folios
Currently anonymous folios belonging to CoW'd MAP_PRIVATE file-backed
mappings are indexed by their page offset within the file in which they
were originally mapped.
This differs from anonymous folios belonging to pure anon mappings which
are indexed by their anonymous page offset (the address at which they'd
belong in the VMA when first faulted).
This change fixes this inconsistency, always indexing anonymous folios by
their anonymous page offset regardless of the VMA to which they belong.
The foundations have been laid such that we need only switch this
functionality on such by:
* Using linear_anon_page_index() in __folio_set_anon() to assign the
folio's index to the anonymous linear index rather than the file-backed
one.
* Otherwise using linear_anon_page_index() in all instances where
anonymous folios are being referenced or manipulated.
* Replacing vma_address() with vma_filebacked_address() or
vma_anon_address() as appropriate.
* Updating the merging logic to check that anonymous page offsets are
aligned as well as filebacked ones for MAP_PRIVATE file-backed VMAs,
introducing needs_adjacent_anon_pgoff() to figure out when this is
required.
* Updating linear_folio_page_index() to invoke linear_anon_page_index()
if the folio is anonymous.
* Updating vma_address_end() to use the VMA's anonymous page offset when
pvmw->pgoff is anonymous.
* Correcting folio_within_range() to use anonymous page offset for
anonymous folios.
This will have no impact on merging of anonymous VMAs, whose page offset
and anonymous page offset are identical, nor will it impact shared
file-backed VMAs, which will continue to be merged based on the
file-backed page offset.
However, MAP_PRIVATE file-backed mappings must now be aligned on anonymous
page offset as well.
In most instances this should have no impact on merging of file-backed
mappings, which are usually not merged all that often, let alone
MAP_PRIVATE mapped ones, and rarely remapped and faulted before being
moved back in place (the case in which a merge may now fail).
One subtle impact of this change is in NUMA interleaving - since commit
88c91dc58582 ("mempolicy: migration attempt to match interleave nodes"),
migration heuristically tries to maintain interleaving behaviour matching
the policy using folio indices.
When doing migration of CoW'd MAP_PRIVATE-file backed ranges, the 'base'
upon which the interleaving behaviour is performed will vary for these
ranges. However the commit notes that ranges spanning multiple VMAs will
already cause varying bases, and that this is an acceptable approximation.
It is very unlikely real world use-cases will be impacted by this
(MAP_PRIVATE file-backed mappings are already an edge case), and all that
will happen is that such ranges will cause interleaving to be rotated over
the CoW'd range, with little to no impact.
This commit lays the foundations for future scalable CoW work which needs
to track some remaps, meaning that most remap tracking can be avoided, and
in nearly all cases the anonymous page offset will be able to be used to
quickly find the VMA in an mm.
Note that the need_rmap_locks check doesn't need to be updated, as any
remapping will offset both the anonymous and file-backed page offset, so
it suffices to check only one.
Link: https://lore.kernel.org/20260813-b4-scalable-cow-virt-pgoff-v5-14-c21581c0c3c8@kernel.org
Signed-off-by: Lorenzo Stoakes (ARM) <ljs@kernel.org>
Acked-by: David Hildenbrand (Arm) <david@kernel.org>
Cc: Adrian Hunter <adrian.hunter@intel.com>
Cc: Alexander Deucher <alexander.deucher@amd.com>
Cc: Alexander Gordeev <agordeev@linux.ibm.com>
Cc: Alexander Shishkin <alexander.shishkin@linux.intel.com>
Cc: Alistair Popple <apopple@nvidia.com>
Cc: Arnaldo Carvalho de Melo <acme@kernel.org>
Cc: Arnd Bergmann <arnd@arndb.de>
Cc: Baolin Wang <baolin.wang@linux.alibaba.com>
Cc: Baoquan He <baoquan.he@linux.dev>
Cc: Barry Song <baohua@kernel.org>
Cc: Boris Brezillon <boris.brezillon@collabora.com>
Cc: Byungchul Park <byungchul@sk.com>
Cc: Chengming Zhou <chengming.zhou@linux.dev>
Cc: Chris Li <chrisl@kernel.org>
Cc: Christan König <christian.koenig@amd.com>
Cc: Christian Borntraeger <borntraeger@linux.ibm.com>
Cc: Claudio Imbrenda <imbrenda@linux.ibm.com>
Cc: Dave Airlie <airlied@gmail.com>
Cc: Dev Jain <dev.jain@arm.com>
Cc: Gerald Schaefer <gerald.schaefer@linux.ibm.com>
Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
Cc: Gregory Price (Meta) <gourry@gourry.net>
Cc: Harry Yoo <harry@kernel.org>
Cc: Heiko Carstens <hca@linux.ibm.com>
Cc: Huang Ray <Ray.Huang@amd.com>
Cc: "Huang, Ying" <ying.huang@linux.alibaba.com>
Cc: Ian Rogers <irogers@google.com>
Cc: Ingo Molnar <mingo@redhat.com>
Cc: James Clark <james.clark@linaro.org>
Cc: Jan Kara <jack@suse.cz>
Cc: Jann Horn <jannh@google.com>
Cc: Janosch Frank <frankja@linux.ibm.com>
Cc: Jason Gunthorpe <jgg@ziepe.ca>
Cc: Jiri Olsa <jolsa@kernel.org>
Cc: John Hubbard <jhubbard@nvidia.com>
Cc: Joshua Hahn <joshua.hahnjy@gmail.com>
Cc: Kairui Song <kasong@tencent.com>
Cc: Kees Cook <kees@kernel.org>
Cc: Kemeng Shi <shikemeng@huaweicloud.com>
Cc: Lance Yang <lance.yang@linux.dev>
Cc: Liam R. Howlett <liam@infradead.org>
Cc: Liviu Dudau <liviu.dudau@arm.com>
Cc: Maarten Lankhorst <maarten.lankhorst@linux.intel.com>
Cc: Marc Rutland <mark.rutland@arm.com>
Cc: "Masami Hiramatsu (Google)" <mhiramat@kernel.org>
Cc: Matthew Auld <matthew.auld@intel.com>
Cc: Matthew Brost <matthew.brost@intel.com>
Cc: Matthew Wilcox (Oracle) <willy@infradead.org>
Cc: Maxime Ripard <mripard@kernel.org>
Cc: Miaohe Lin <linmiaohe@huawei.com>
Cc: Michal Hocko <mhocko@suse.com>
Cc: Mike Rapoport <rppt@kernel.org>
Cc: Muchun Song <muchun.song@linux.dev>
Cc: Namhyung kim <namhyung@kernel.org>
Cc: Naoya Horiguchi <nao.horiguchi@gmail.com>
Cc: Nhat Pham <nphamcs@gmail.com>
Cc: Nico Pache <npache@redhat.com>
Cc: Oleg Nesterov <oleg@redhat.com>
Cc: Oscar Salvador <osalvador@suse.de>
Cc: Pedro Falcato <pfalcato@suse.de>
Cc: Peter Xu <peterx@redhat.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Rakie Kim <rakie.kim@sk.com>
Cc: Rik van Riel <riel@surriel.com>
Cc: Rodrigo Vivi <rodrigo.vivi@intel.com>
Cc: Ryan Roberts <ryan.roberts@arm.com>
Cc: Steven Price <steven.price@arm.com>
Cc: Suren Baghdasaryan <surenb@google.com>
Cc: Sven Schnelle <svens@linux.ibm.com>
Cc: Thomas Hellström <thomas.hellstrom@linux.intel.com>
Cc: Thomas Zimemrmann <tzimmermann@suse.de>
Cc: Vasily Gorbik <gor@linux.ibm.com>
Cc: Vlastimil Babka <vbabka@kernel.org>
Cc: xu xin <xu.xin16@zte.com.cn>
Cc: Zi Yan <ziy@nvidia.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
2026-08-13 18:32:31 +01:00
|
|
|
|
mm anon rmap: replace same_anon_vma linked list with an interval tree.
When a large VMA (anon or private file mapping) is first touched, which
will populate its anon_vma field, and then split into many regions through
the use of mprotect(), the original anon_vma ends up linking all of the
vmas on a linked list. This can cause rmap to become inefficient, as we
have to walk potentially thousands of irrelevent vmas before finding the
one a given anon page might fall into.
By replacing the same_anon_vma linked list with an interval tree (where
each avc's interval is determined by its vma's start and last pgoffs), we
can make rmap efficient for this use case again.
While the change is large, all of its pieces are fairly simple.
Most places that were walking the same_anon_vma list were looking for a
known pgoff, so they can just use the anon_vma_interval_tree_foreach()
interval tree iterator instead. The exception here is ksm, where the
page's index is not known. It would probably be possible to rework ksm so
that the index would be known, but for now I have decided to keep things
simple and just walk the entirety of the interval tree there.
When updating vma's that already have an anon_vma assigned, we must take
care to re-index the corresponding avc's on their interval tree. This is
done through the use of anon_vma_interval_tree_pre_update_vma() and
anon_vma_interval_tree_post_update_vma(), which remove the avc's from
their interval tree before the update and re-insert them after the update.
The anon_vma stays locked during the update, so there is no chance that
rmap would miss the vmas that are being updated.
Signed-off-by: Michel Lespinasse <walken@google.com>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Cc: Rik van Riel <riel@redhat.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Daniel Santos <daniel.santos@pobox.com>
Cc: Hugh Dickins <hughd@google.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2012-10-08 16:31:39 -07:00
|
|
|
|
|
|
|
|
|
2026-07-10 21:16:51 +01:00
|
|
|
|
2012-10-08 16:31:45 -07:00
|
|
|
|
2026-07-10 21:16:52 +01:00
|
|
|
|
2012-10-08 16:31:45 -07:00
|
|
|
|
2026-07-10 21:16:52 +01:00
|
|
|
|
|
|
|
|
|
2012-10-08 16:31:45 -07:00
|
|
|
|
|
|
|
|
|
2026-07-10 21:16:51 +01:00
|
|
|
|
|
|
|
|
|
2012-10-08 16:31:45 -07:00
|
|
|
|
2026-07-10 21:16:52 +01:00
|
|
|
|
2012-10-08 16:31:45 -07:00
|
|
|
|
|
|
|
|
|
2026-07-10 21:16:52 +01:00
|
|
|
|
|
|
|
|
|
2012-10-08 16:31:45 -07:00
|
|
|
|
2026-07-10 21:16:52 +01:00
|
|
|
|
2012-10-08 16:31:45 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2026-07-10 21:16:52 +01:00
|
|
|
|
|
|
|
|
|
2012-10-08 16:31:45 -07:00
|
|
|
|
2026-07-10 21:16:52 +01:00
|
|
|
|
|
|
|
|
|
2012-10-08 16:31:45 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2026-07-10 21:16:52 +01:00
|
|
|
|
|
|
|
|
|
2012-10-08 16:31:45 -07:00
|
|
|
|
2026-07-10 21:16:52 +01:00
|
|
|
|
2012-10-08 16:31:45 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2026-07-10 21:16:52 +01:00
|
|
|
|
2012-10-08 16:31:45 -07:00
|
|
|
|
2026-07-10 21:16:51 +01:00
|
|
|
|
|
|
|
|
|
2012-10-08 16:31:45 -07:00
|
|
|
|
|
|
|
|
|
