[LSF/MM/BPF TOPIC] The future of anon_vma

[LSF/MM/BPF TOPIC] The future of anon_vma

[Lorenzo Stoakes]

Hi all,

Since time immemorial the kernel has maintained two separate realms within
mm - that of file-backed mappings and that of anonymous mappings.

Each of these require a reverse mapping from folio to VMA, utilising
interval trees from an intermediate object referenced by folio->mapping
back to the VMAs which map it.

In the case of a file-backed mapping, this 'intermediate object' is the
shared page cache entry, of type struct address_space. It is non-CoW which
keep things simple(-ish) and the concept is straight-forward - both the
folio and the VMAs which map the page cache object reference it.

In the case of anonymous memory, things are not quite as simple, as a
result of CoW. This is further complicated by forking and the very many
different combinations of CoW'd and non-CoW'd folios that can exist within
a mapping.

This kind of mapping utilises struct anon_vma objects which as a result of
this complexity are pretty well entirely concerned with maintaining the
notion of an anon_vma object rather than describing the underlying memory
in any way.

Of course we can enter further realms of insan^W^W^W^W^Wcomplexity by
maintaining a MAP_PRIVATE file-backed mapping where we can experience both
at once!

The fact that we can have both CoW'd and non-CoW'd folios referencing a VMA
means that we require -yet another- type, a struct anon_vma_chain,
maintained on a linked list, to abstract the link between anon_vma objects
and VMAs, and to provide a means by which one can manage and traverse
anon_vma objects from the VMA as well as looking them up from the reverse
mapping.

Maintaining all of this correctly is very fragile, error-prone and
confusing, not to mention the concerns around maintaining correct locking
semantics, correctly propagating anonymous VMA state on fork, and trying to
reuse state to avoid allocating unnecessary memory to maintain all of this
infrastructure.

An additional consequence of maintaining these two realms is that that
which straddles them - shmem - becomes something of an enigma -
file-backed, but existing on the anonymous LRU list and requiring a lot of
very specific handling.

It is obvious that there is some isomorphism between the representation of
file systems and anonymous memory, less the CoW handling. However there is
a concept which exists within file systems which can somewhat bridge the gap
 - reflinks.

A future where we unify anonymous and file-backed memory mappings would be
one in which a reflinks were implemented at a general level rather than, as
they are now, implemented individually within file systems.

I'd like to discuss how feasible doing so might be, whether this is a sane
line of thought at all, and how a roadmap for working towards the
elimination of anon_vma as it stands might look.

As with my other proposal, I will gather more concrete information before
LSF to ensure the discussion is specific, and of course I would be
interested to discuss the topic in this thread also!

Thanks!

Re: [Lsf-pc] [LSF/MM/BPF TOPIC] The future of anon_vma

[Jan Kara]

Hi!

On Wed 08-01-25 22:23:16, Lorenzo Stoakes via Lsf-pc wrote:
> A future where we unify anonymous and file-backed memory mappings would be
> one in which a reflinks were implemented at a general level rather than, as
> they are now, implemented individually within file systems.
> 
> I'd like to discuss how feasible doing so might be, whether this is a sane
> line of thought at all, and how a roadmap for working towards the
> elimination of anon_vma as it stands might look.

As you can imagine this has been discussed in the past and some folks are
very interested in saving page cache memory for some heavily reflinked
container setups or for various FUSE filesystems. So if someone manages to
come up with a feasible design, the usecases are there. I think reading
e.g. [1] and comments below it is a good preparation for the session to get
some idea what challenges are there :).

								Honza

[1] https://lwn.net/Articles/717950/



-- 
Jan Kara <jack@suse.com>
SUSE Labs, CR

Re: [Lsf-pc] [LSF/MM/BPF TOPIC] The future of anon_vma

[Lorenzo Stoakes]

On Thu, Jan 09, 2025 at 11:21:02AM +0100, Jan Kara wrote:
> Hi!
>
> On Wed 08-01-25 22:23:16, Lorenzo Stoakes via Lsf-pc wrote:
> > A future where we unify anonymous and file-backed memory mappings would be
> > one in which a reflinks were implemented at a general level rather than, as
> > they are now, implemented individually within file systems.
> >
> > I'd like to discuss how feasible doing so might be, whether this is a sane
> > line of thought at all, and how a roadmap for working towards the
> > elimination of anon_vma as it stands might look.
>
> As you can imagine this has been discussed in the past and some folks are
> very interested in saving page cache memory for some heavily reflinked
> container setups or for various FUSE filesystems. So if someone manages to
> come up with a feasible design, the usecases are there. I think reading
> e.g. [1] and comments below it is a good preparation for the session to get
> some idea what challenges are there :).

Oh I certainly imagined that it had :) Perhaps you are volunteering to
assist me from an fs point of view on this Jan? ;)

Thanks for the link, I will have a read!

I am certainly aware of just how huge a topic this is, as LSF is all about
discussion it's really one I wanted to reignite and to see where we stand
and how we might move forward.

It's a bug bear of mine for various reasons (mostly around the locking,
memory consumption and complexity concerns with anon_vma), and something I
certainly hope to do something on - but over the very long term I suspect -
should work on this be feasible.

>
> 								Honza
>
> [1] https://lwn.net/Articles/717950/
>
>
>
> --
> Jan Kara <jack@suse.com>
> SUSE Labs, CR

Thanks!

Re: [Lsf-pc] [LSF/MM/BPF TOPIC] The future of anon_vma

[Jan Kara]

On Thu 09-01-25 12:33:52, Lorenzo Stoakes wrote:
> On Thu, Jan 09, 2025 at 11:21:02AM +0100, Jan Kara wrote:
> > On Wed 08-01-25 22:23:16, Lorenzo Stoakes via Lsf-pc wrote:
> > > A future where we unify anonymous and file-backed memory mappings would be
> > > one in which a reflinks were implemented at a general level rather than, as
> > > they are now, implemented individually within file systems.
> > >
> > > I'd like to discuss how feasible doing so might be, whether this is a sane
> > > line of thought at all, and how a roadmap for working towards the
> > > elimination of anon_vma as it stands might look.
> >
> > As you can imagine this has been discussed in the past and some folks are
> > very interested in saving page cache memory for some heavily reflinked
> > container setups or for various FUSE filesystems. So if someone manages to
> > come up with a feasible design, the usecases are there. I think reading
> > e.g. [1] and comments below it is a good preparation for the session to get
> > some idea what challenges are there :).
> 
> Oh I certainly imagined that it had :) Perhaps you are volunteering to
> assist me from an fs point of view on this Jan? ;)

Sure, I'll be happy to provide you with a FS point of view :)

								Honza
-- 
Jan Kara <jack@suse.com>
SUSE Labs, CR

Re: [LSF/MM/BPF TOPIC] The future of anon_vma

[Lorenzo Stoakes]

Having worked on slides and done further research in this area (I plan to
really attack anon_vma over the coming year it's a real area of interest of
mine), I have decided to modify the topic a little.

Rather than focusing on the possible future ideal very-long-term project of
finding a means of unifying anon + file-backed handling, I'd like to take a
step back and discuss anon_vma in general and then examine:

- short term improvements that I intend to attack shortly (hopefully some
  of which I will have submitted patches for -prior to lsf- as some people
  are apparently adament one should only speak about things one has
  patched).

- medium term improvements that require architectural changes to the
  anon_vma mechanism.

- and long term improvements which is, yes, unifying anon_vma and
  file-backed mappings.

I think this will be more practical and we'll get a better more actionable
discussion out of this approach.

On Wed, Jan 08, 2025 at 10:23:16PM +0000, Lorenzo Stoakes wrote:
> Hi all,
>
> Since time immemorial the kernel has maintained two separate realms within
> mm - that of file-backed mappings and that of anonymous mappings.
>
> Each of these require a reverse mapping from folio to VMA, utilising
> interval trees from an intermediate object referenced by folio->mapping
> back to the VMAs which map it.
>
> In the case of a file-backed mapping, this 'intermediate object' is the
> shared page cache entry, of type struct address_space. It is non-CoW which
> keep things simple(-ish) and the concept is straight-forward - both the
> folio and the VMAs which map the page cache object reference it.
>
> In the case of anonymous memory, things are not quite as simple, as a
> result of CoW. This is further complicated by forking and the very many
> different combinations of CoW'd and non-CoW'd folios that can exist within
> a mapping.
>
> This kind of mapping utilises struct anon_vma objects which as a result of
> this complexity are pretty well entirely concerned with maintaining the
> notion of an anon_vma object rather than describing the underlying memory
> in any way.
>
> Of course we can enter further realms of insan^W^W^W^W^Wcomplexity by
> maintaining a MAP_PRIVATE file-backed mapping where we can experience both
> at once!
>
> The fact that we can have both CoW'd and non-CoW'd folios referencing a VMA
> means that we require -yet another- type, a struct anon_vma_chain,
> maintained on a linked list, to abstract the link between anon_vma objects
> and VMAs, and to provide a means by which one can manage and traverse
> anon_vma objects from the VMA as well as looking them up from the reverse
> mapping.
>
> Maintaining all of this correctly is very fragile, error-prone and
> confusing, not to mention the concerns around maintaining correct locking
> semantics, correctly propagating anonymous VMA state on fork, and trying to
> reuse state to avoid allocating unnecessary memory to maintain all of this
> infrastructure.
>
> An additional consequence of maintaining these two realms is that that
> which straddles them - shmem - becomes something of an enigma -
> file-backed, but existing on the anonymous LRU list and requiring a lot of
> very specific handling.
>
> It is obvious that there is some isomorphism between the representation of
> file systems and anonymous memory, less the CoW handling. However there is
> a concept which exists within file systems which can somewhat bridge the gap
>  - reflinks.
>
> A future where we unify anonymous and file-backed memory mappings would be
> one in which a reflinks were implemented at a general level rather than, as
> they are now, implemented individually within file systems.
>
> I'd like to discuss how feasible doing so might be, whether this is a sane
> line of thought at all, and how a roadmap for working towards the
> elimination of anon_vma as it stands might look.
>
> As with my other proposal, I will gather more concrete information before
> LSF to ensure the discussion is specific, and of course I would be
> interested to discuss the topic in this thread also!
>
> Thanks!

Re: [LSF/MM/BPF TOPIC] The future of anon_vma

[Dev Jain]

On 09/01/25 3:53 am, Lorenzo Stoakes wrote:
> Hi all,
> 
> Since time immemorial the kernel has maintained two separate realms within
> mm - that of file-backed mappings and that of anonymous mappings.
> 
> Each of these require a reverse mapping from folio to VMA, utilising
> interval trees from an intermediate object referenced by folio->mapping
> back to the VMAs which map it.
> 
> In the case of a file-backed mapping, this 'intermediate object' is the
> shared page cache entry, of type struct address_space. It is non-CoW which
> keep things simple(-ish) and the concept is straight-forward - both the
> folio and the VMAs which map the page cache object reference it.
> 
> In the case of anonymous memory, things are not quite as simple, as a
> result of CoW. This is further complicated by forking and the very many
> different combinations of CoW'd and non-CoW'd folios that can exist within
> a mapping.
> 
> This kind of mapping utilises struct anon_vma objects which as a result of
> this complexity are pretty well entirely concerned with maintaining the
> notion of an anon_vma object rather than describing the underlying memory
> in any way.
> 
> Of course we can enter further realms of insan^W^W^W^W^Wcomplexity by
> maintaining a MAP_PRIVATE file-backed mapping where we can experience both
> at once!
> 
> The fact that we can have both CoW'd and non-CoW'd folios referencing a VMA
> means that we require -yet another- type, a struct anon_vma_chain,
> maintained on a linked list, to abstract the link between anon_vma objects
> and VMAs, and to provide a means by which one can manage and traverse
> anon_vma objects from the VMA as well as looking them up from the reverse
> mapping.
> 
> Maintaining all of this correctly is very fragile, error-prone and
> confusing, not to mention the concerns around maintaining correct locking
> semantics, correctly propagating anonymous VMA state on fork, and trying to
> reuse state to avoid allocating unnecessary memory to maintain all of this
> infrastructure.
> 
> An additional consequence of maintaining these two realms is that that
> which straddles them - shmem - becomes something of an enigma -
> file-backed, but existing on the anonymous LRU list and requiring a lot of
> very specific handling.
> 
> It is obvious that there is some isomorphism between the representation of
> file systems and anonymous memory, less the CoW handling. However there is
> a concept which exists within file systems which can somewhat bridge the gap
>   - reflinks.
> 
> A future where we unify anonymous and file-backed memory mappings would be
> one in which a reflinks were implemented at a general level rather than, as
> they are now, implemented individually within file systems.
> 
> I'd like to discuss how feasible doing so might be, whether this is a sane
> line of thought at all, and how a roadmap for working towards the
> elimination of anon_vma as it stands might look.
> 
> As with my other proposal, I will gather more concrete information before
> LSF to ensure the discussion is specific, and of course I would be
> interested to discuss the topic in this thread also!
> 
> Thanks!
> 

Thanks for this, as a beginner I have tried understanding the rmap code 
a million times, after forgetting it a million times, thanks to the 
sheer complexity of the anon_vma and anon_vma_chain. Whenever I read it 
again, the first thought is "surely there has to be some better way, 
someone must figure it out" :)

Re: [LSF/MM/BPF TOPIC] The future of anon_vma

[Lorenzo Stoakes]

On Sun, Feb 23, 2025 at 01:38:08PM +0530, Dev Jain wrote:
>
>
> On 09/01/25 3:53 am, Lorenzo Stoakes wrote:
> > Hi all,
> >
> > Since time immemorial the kernel has maintained two separate realms within
> > mm - that of file-backed mappings and that of anonymous mappings.
> >
> > Each of these require a reverse mapping from folio to VMA, utilising
> > interval trees from an intermediate object referenced by folio->mapping
> > back to the VMAs which map it.
> >
> > In the case of a file-backed mapping, this 'intermediate object' is the
> > shared page cache entry, of type struct address_space. It is non-CoW which
> > keep things simple(-ish) and the concept is straight-forward - both the
> > folio and the VMAs which map the page cache object reference it.
> >
> > In the case of anonymous memory, things are not quite as simple, as a
> > result of CoW. This is further complicated by forking and the very many
> > different combinations of CoW'd and non-CoW'd folios that can exist within
> > a mapping.
> >
> > This kind of mapping utilises struct anon_vma objects which as a result of
> > this complexity are pretty well entirely concerned with maintaining the
> > notion of an anon_vma object rather than describing the underlying memory
> > in any way.
> >
> > Of course we can enter further realms of insan^W^W^W^W^Wcomplexity by
> > maintaining a MAP_PRIVATE file-backed mapping where we can experience both
> > at once!
> >
> > The fact that we can have both CoW'd and non-CoW'd folios referencing a VMA
> > means that we require -yet another- type, a struct anon_vma_chain,
> > maintained on a linked list, to abstract the link between anon_vma objects
> > and VMAs, and to provide a means by which one can manage and traverse
> > anon_vma objects from the VMA as well as looking them up from the reverse
> > mapping.
> >
> > Maintaining all of this correctly is very fragile, error-prone and
> > confusing, not to mention the concerns around maintaining correct locking
> > semantics, correctly propagating anonymous VMA state on fork, and trying to
> > reuse state to avoid allocating unnecessary memory to maintain all of this
> > infrastructure.
> >
> > An additional consequence of maintaining these two realms is that that
> > which straddles them - shmem - becomes something of an enigma -
> > file-backed, but existing on the anonymous LRU list and requiring a lot of
> > very specific handling.
> >
> > It is obvious that there is some isomorphism between the representation of
> > file systems and anonymous memory, less the CoW handling. However there is
> > a concept which exists within file systems which can somewhat bridge the gap
> >   - reflinks.
> >
> > A future where we unify anonymous and file-backed memory mappings would be
> > one in which a reflinks were implemented at a general level rather than, as
> > they are now, implemented individually within file systems.
> >
> > I'd like to discuss how feasible doing so might be, whether this is a sane
> > line of thought at all, and how a roadmap for working towards the
> > elimination of anon_vma as it stands might look.
> >
> > As with my other proposal, I will gather more concrete information before
> > LSF to ensure the discussion is specific, and of course I would be
> > interested to discuss the topic in this thread also!
> >
> > Thanks!
> >
>
> Thanks for this, as a beginner I have tried understanding the rmap code a
> million times, after forgetting it a million times, thanks to the sheer
> complexity of the anon_vma and anon_vma_chain. Whenever I read it again, the
> first thought is "surely there has to be some better way, someone must
> figure it out" :)
>

No problem, this is something I am very interested in putting time into,
and _will_ be at least -attempting- patches for (I have ideas that likely
will land _before_ LSF).

Note the follow up mail - I am providing short, medium + long term
approaches, no longer JUST focusing on the 'how to remove' bit.

I'd be remiss given what you've said if I didn't mention that my book
covers this stuff in a great amount of detail, including anon_vma in a lot
of detail (I steal some diagrams from it for the LSF slides :) and that you
can pre-order and read full draft now... https://linuxmemory.org/ ;)

But also in the slides I have drafted start by (as quickly as I can so it
can be a good discussion) go over how file-backed rmap compares to
anon_vma, the complexities, why and the pitfalls.

This is to provide a basis for the 'So what?' portion as is - what can we
do, why, how.

Point is I'm attacking this one way or another whether I host this topic or
not, as I feel as you (and I am sure many others) do - can't we do better?
So it seems a nice courtesy and great opportunity for discussion to speak
about it in person.

I know for one in VMA merging we almost certainly can. And since I
literally wrote all of that code (latest iteration anyway) that's very much
in my wheelhouse.

Cheers, Lorenzo

Re: [LSF/MM/BPF TOPIC] The future of anon_vma

[Lorenzo Stoakes]

On Sat, Feb 22, 2025 at 06:26:32PM +0000, Lorenzo Stoakes wrote:
> Having worked on slides and done further research in this area (I plan to
> really attack anon_vma over the coming year it's a real area of interest of
> mine), I have decided to modify the topic a little.
>
> Rather than focusing on the possible future ideal very-long-term project of
> finding a means of unifying anon + file-backed handling, I'd like to take a
> step back and discuss anon_vma in general and then examine:
>
> - short term improvements that I intend to attack shortly (hopefully some
>   of which I will have submitted patches for -prior to lsf- as some people
>   are apparently adament one should only speak about things one has
>   patched).
>
> - medium term improvements that require architectural changes to the
>   anon_vma mechanism.
>
> - and long term improvements which is, yes, unifying anon_vma and
>   file-backed mappings.
>
> I think this will be more practical and we'll get a better more actionable
> discussion out of this approach.

I'm going to further refine this to discussing anon_vma in the context of
VMA merging solely, and leave the bigger stuff to later :)

This is in relation to an RFC patch series I have been working on.

>
> On Wed, Jan 08, 2025 at 10:23:16PM +0000, Lorenzo Stoakes wrote:
> > Hi all,
> >
> > Since time immemorial the kernel has maintained two separate realms within
> > mm - that of file-backed mappings and that of anonymous mappings.
> >
> > Each of these require a reverse mapping from folio to VMA, utilising
> > interval trees from an intermediate object referenced by folio->mapping
> > back to the VMAs which map it.
> >
> > In the case of a file-backed mapping, this 'intermediate object' is the
> > shared page cache entry, of type struct address_space. It is non-CoW which
> > keep things simple(-ish) and the concept is straight-forward - both the
> > folio and the VMAs which map the page cache object reference it.
> >
> > In the case of anonymous memory, things are not quite as simple, as a
> > result of CoW. This is further complicated by forking and the very many
> > different combinations of CoW'd and non-CoW'd folios that can exist within
> > a mapping.
> >
> > This kind of mapping utilises struct anon_vma objects which as a result of
> > this complexity are pretty well entirely concerned with maintaining the
> > notion of an anon_vma object rather than describing the underlying memory
> > in any way.
> >
> > Of course we can enter further realms of insan^W^W^W^W^Wcomplexity by
> > maintaining a MAP_PRIVATE file-backed mapping where we can experience both
> > at once!
> >
> > The fact that we can have both CoW'd and non-CoW'd folios referencing a VMA
> > means that we require -yet another- type, a struct anon_vma_chain,
> > maintained on a linked list, to abstract the link between anon_vma objects
> > and VMAs, and to provide a means by which one can manage and traverse
> > anon_vma objects from the VMA as well as looking them up from the reverse
> > mapping.
> >
> > Maintaining all of this correctly is very fragile, error-prone and
> > confusing, not to mention the concerns around maintaining correct locking
> > semantics, correctly propagating anonymous VMA state on fork, and trying to
> > reuse state to avoid allocating unnecessary memory to maintain all of this
> > infrastructure.
> >
> > An additional consequence of maintaining these two realms is that that
> > which straddles them - shmem - becomes something of an enigma -
> > file-backed, but existing on the anonymous LRU list and requiring a lot of
> > very specific handling.
> >
> > It is obvious that there is some isomorphism between the representation of
> > file systems and anonymous memory, less the CoW handling. However there is
> > a concept which exists within file systems which can somewhat bridge the gap
> >  - reflinks.
> >
> > A future where we unify anonymous and file-backed memory mappings would be
> > one in which a reflinks were implemented at a general level rather than, as
> > they are now, implemented individually within file systems.
> >
> > I'd like to discuss how feasible doing so might be, whether this is a sane
> > line of thought at all, and how a roadmap for working towards the
> > elimination of anon_vma as it stands might look.
> >
> > As with my other proposal, I will gather more concrete information before
> > LSF to ensure the discussion is specific, and of course I would be
> > interested to discuss the topic in this thread also!
> >
> > Thanks!

Re: [LSF/MM/BPF TOPIC] The future of anon_vma

[Lorenzo Stoakes]

As with the ongoing evolution of this, as previously discussed, the focus
has settled on merging of anonymous VMAs and improving this mergeability.

I have an RFC series (not upstreamed yet, but should be by LSF) which
optionally permits improved anonymous mapping mergeability by passing a
flag to mremap().

In this topic I'd like to discuss that, anon_vma in general motivations for
it, why it's hard, etc.

This dovetails with the original proposal - bit is a less ambitious, more
short-term 'how can we improve the situation' kind of thing. Maybe next
year there can be more :)

My slides are at ~31 right now, so I wonder whether I could have an hour
slot for this? As I'd also like to have some discussion of course! :)

Thanks!

Re: [LSF/MM/BPF TOPIC] The future of anon_vma

[Lorenzo Stoakes]

Michal has kindly already updated, but the subject in thread is now misleading,
correct one is 'Better anon VMA merging' :)

On Thu, Mar 13, 2025 at 06:41:40PM +0000, Lorenzo Stoakes wrote:
> As with the ongoing evolution of this, as previously discussed, the focus
> has settled on merging of anonymous VMAs and improving this mergeability.
>
> I have an RFC series (not upstreamed yet, but should be by LSF) which
> optionally permits improved anonymous mapping mergeability by passing a
> flag to mremap().

Now posted at
https://lore.kernel.org/all/cover.1742478846.git.lorenzo.stoakes@oracle.com/

Also with a pre-requisite series at
https://lore.kernel.org/all/cover.1742245056.git.lorenzo.stoakes@oracle.com/

>
> In this topic I'd like to discuss that, anon_vma in general motivations for
> it, why it's hard, etc.
>
> This dovetails with the original proposal - bit is a less ambitious, more
> short-term 'how can we improve the situation' kind of thing. Maybe next
> year there can be more :)
>
> My slides are at ~31 right now, so I wonder whether I could have an hour
> slot for this? As I'd also like to have some discussion of course! :)

Just for the record haha - that's no need for this :P I have already cut my
slides down to 1/2 hour.

The remaining ones can perhaps be re-used at a different conference where I
could go into more introductionary depth on anon_vma etc.!

>
> Thanks!

See you all in Montreal! :)

Cheers, Lorenzo