[LSF/MM/BPF TOPIC] Flexible orders for anonymous folios

[LSF/MM/BPF TOPIC] Flexible orders for anonymous folios

[Yu Zhao]

Currently anonymous folios only support two orders: 0 and the PMD
order. Flexible orders for anonymous folios can resist both internal
or external fragmentations when the PMD order is too underutilized or
costly to allocate. Flexible orders can also leverage the TLB
coalescing feature, .e.g., order 3 for AMD and order 4 for ARM CPUs.

Discussion points:
1. The page fault path: determining the best order and the fallback policy.
2. The reclaim path: detecting the utilization and the splitting policy.
3. The refcount and the mapcount models, e.g., reuse the PMD-mapped
THP model or not.
4. The splitting, and the collapsing if needed.
5. Other paths: COW, GUP, madvise(), mprotect(), page migration, etc.

A bit of history:
I discussed this topic at Matthew's THP Cabal meeting a couple of
years ago, as one of the major use cases of folios. Around the same
time, I tried to get Hugh to work with me on it, since he tried
something similar back in 2001 [1]. William's page clustering from
2003 [2] is also based on that, btw. Then I put the idea on the back
burner.

Now it seems to be a good time to revisit. Yang Shi and I have been
looking at some details, trying to scope out the work that would be
required. We don't have anything definitive yet, but we should have
enough to share by the time of the LSF/MM/BPF.

[1] https://lore.kernel.org/linux-mm/Pine.LNX.4.21.0107051737340.1577-100000@localhost.localdomain/
[2] https://lwn.net/Articles/23785/

Re: [LSF/MM/BPF TOPIC] Flexible orders for anonymous folios

[Suren Baghdasaryan]

On Wed, Feb 22, 2023 at 3:56 PM Yu Zhao <yuzhao@google.com> wrote:
>
> Currently anonymous folios only support two orders: 0 and the PMD
> order. Flexible orders for anonymous folios can resist both internal
> or external fragmentations when the PMD order is too underutilized or
> costly to allocate. Flexible orders can also leverage the TLB
> coalescing feature, .e.g., order 3 for AMD and order 4 for ARM CPUs.
>
> Discussion points:
> 1. The page fault path: determining the best order and the fallback policy.
> 2. The reclaim path: detecting the utilization and the splitting policy.
> 3. The refcount and the mapcount models, e.g., reuse the PMD-mapped
> THP model or not.
> 4. The splitting, and the collapsing if needed.
> 5. Other paths: COW, GUP, madvise(), mprotect(), page migration, etc.
>
> A bit of history:
> I discussed this topic at Matthew's THP Cabal meeting a couple of
> years ago, as one of the major use cases of folios. Around the same
> time, I tried to get Hugh to work with me on it, since he tried
> something similar back in 2001 [1]. William's page clustering from
> 2003 [2] is also based on that, btw. Then I put the idea on the back
> burner.
>
> Now it seems to be a good time to revisit. Yang Shi and I have been
> looking at some details, trying to scope out the work that would be
> required. We don't have anything definitive yet, but we should have
> enough to share by the time of the LSF/MM/BPF.

This might be useful for Android. I would like to participate in this
discussion.

>
> [1] https://lore.kernel.org/linux-mm/Pine.LNX.4.21.0107051737340.1577-100000@localhost.localdomain/
> [2] https://lwn.net/Articles/23785/
>

Re: [LSF/MM/BPF TOPIC] Flexible orders for anonymous folios

[Matthew Wilcox]

On Wed, Feb 22, 2023 at 04:55:20PM -0700, Yu Zhao wrote:
> Currently anonymous folios only support two orders: 0 and the PMD
> order. Flexible orders for anonymous folios can resist both internal
> or external fragmentations when the PMD order is too underutilized or
> costly to allocate. Flexible orders can also leverage the TLB
> coalescing feature, .e.g., order 3 for AMD and order 4 for ARM CPUs.
> 
> Discussion points:
> 1. The page fault path: determining the best order and the fallback policy.
> 2. The reclaim path: detecting the utilization and the splitting policy.
> 3. The refcount and the mapcount models, e.g., reuse the PMD-mapped
> THP model or not.
> 4. The splitting, and the collapsing if needed.
> 5. Other paths: COW, GUP, madvise(), mprotect(), page migration, etc.

6. Swap out an entire folio instead of splitting it before swap.
7. At some point we're going to want Zi Yan's patches to split a folio
   into arbitrary order folios instead of just to order-0.
8. For file folios, folio->index % folio->nr_pages is 0.  Do we want
   to maintain that invariant for anon folios?  It helps tile the
   folios so we don't end up with say, order-0, order-4, order-2 folios
   in a sequence.
9. How do we ensure that two page faults do not overwrite each others
   folios, eg PF1 decides to allocate an order-0 folio at index 6 and
   PF2 decides to allocate an order-2 folio at index 4?

Probably some other things left to decide.

> Now it seems to be a good time to revisit. Yang Shi and I have been
> looking at some details, trying to scope out the work that would be
> required. We don't have anything definitive yet, but we should have
> enough to share by the time of the LSF/MM/BPF.

Excellent.  There are other people also interested in this.  eg:

Ryan Roberts: https://lore.kernel.org/linux-mm/4c991dcb-c5bb-86bb-5a29-05df24429607@arm.com/
Fengwei Yin: https://lore.kernel.org/linux-mm/20230109072232.2398464-1-fengwei.yin@intel.com/

Obviously I'm keenly interested.
https://lore.kernel.org/linux-mm/Y%2FU8bQd15aUO97vS@casper.infradead.org/

This is definitely worth its own session in the MM track.

Re: [LSF/MM/BPF TOPIC] Flexible orders for anonymous folios

[Yin, Fengwei]

On 2/23/2023 12:01 PM, Matthew Wilcox wrote:
> On Wed, Feb 22, 2023 at 04:55:20PM -0700, Yu Zhao wrote:
>> Currently anonymous folios only support two orders: 0 and the PMD
>> order. Flexible orders for anonymous folios can resist both internal
>> or external fragmentations when the PMD order is too underutilized or
>> costly to allocate. Flexible orders can also leverage the TLB
>> coalescing feature, .e.g., order 3 for AMD and order 4 for ARM CPUs.
>>
>> Discussion points:
>> 1. The page fault path: determining the best order and the fallback policy.
>> 2. The reclaim path: detecting the utilization and the splitting policy.
>> 3. The refcount and the mapcount models, e.g., reuse the PMD-mapped
>> THP model or not.
>> 4. The splitting, and the collapsing if needed.
>> 5. Other paths: COW, GUP, madvise(), mprotect(), page migration, etc.
> 
> 6. Swap out an entire folio instead of splitting it before swap.
> 7. At some point we're going to want Zi Yan's patches to split a folio
>    into arbitrary order folios instead of just to order-0.
> 8. For file folios, folio->index % folio->nr_pages is 0.  Do we want
>    to maintain that invariant for anon folios?  It helps tile the
>    folios so we don't end up with say, order-0, order-4, order-2 folios
>    in a sequence.
> 9. How do we ensure that two page faults do not overwrite each others
>    folios, eg PF1 decides to allocate an order-0 folio at index 6 and
>    PF2 decides to allocate an order-2 folio at index 4?
> 
> Probably some other things left to decide.
> 
>> Now it seems to be a good time to revisit. Yang Shi and I have been
>> looking at some details, trying to scope out the work that would be
>> required. We don't have anything definitive yet, but we should have
>> enough to share by the time of the LSF/MM/BPF.
> 
> Excellent.  There are other people also interested in this.  eg:
> 
> Ryan Roberts: https://lore.kernel.org/linux-mm/4c991dcb-c5bb-86bb-5a29-05df24429607@arm.com/
> Fengwei Yin: https://lore.kernel.org/linux-mm/20230109072232.2398464-1-fengwei.yin@intel.com/
Yes. I definitely have interesting to join.


Regards
Yin, Fengwei

> 
> Obviously I'm keenly interested.
> https://lore.kernel.org/linux-mm/Y%2FU8bQd15aUO97vS@casper.infradead.org/
> 
> This is definitely worth its own session in the MM track.

Re: [LSF/MM/BPF TOPIC] Flexible orders for anonymous folios

[Yang Shi]

On Wed, Feb 22, 2023 at 8:01 PM Matthew Wilcox <willy@infradead.org> wrote:
>
> On Wed, Feb 22, 2023 at 04:55:20PM -0700, Yu Zhao wrote:
> > Currently anonymous folios only support two orders: 0 and the PMD
> > order. Flexible orders for anonymous folios can resist both internal
> > or external fragmentations when the PMD order is too underutilized or
> > costly to allocate. Flexible orders can also leverage the TLB
> > coalescing feature, .e.g., order 3 for AMD and order 4 for ARM CPUs.
> >
> > Discussion points:
> > 1. The page fault path: determining the best order and the fallback policy.
> > 2. The reclaim path: detecting the utilization and the splitting policy.
> > 3. The refcount and the mapcount models, e.g., reuse the PMD-mapped
> > THP model or not.
> > 4. The splitting, and the collapsing if needed.
> > 5. Other paths: COW, GUP, madvise(), mprotect(), page migration, etc.
>
> 6. Swap out an entire folio instead of splitting it before swap.

Yeah, the THP swap should be extended to support arbitrary order.
Other than swap out, swap in large folios should be considered as well
at some point

> 7. At some point we're going to want Zi Yan's patches to split a folio
>    into arbitrary order folios instead of just to order-0.

I agree.

> 8. For file folios, folio->index % folio->nr_pages is 0.  Do we want
>    to maintain that invariant for anon folios?  It helps tile the
>    folios so we don't end up with say, order-0, order-4, order-2 folios
>    in a sequence.

I think so. The TLB has alignment requirements anyway.

> 9. How do we ensure that two page faults do not overwrite each others
>    folios, eg PF1 decides to allocate an order-0 folio at index 6 and
>    PF2 decides to allocate an order-2 folio at index 4?

Good question. I don't have a good answer right now, but anyway the
kernel should make sure all the PTEs in the region covered by the
folio should be none off the top of my head.

>
> Probably some other things left to decide.
>
> > Now it seems to be a good time to revisit. Yang Shi and I have been
> > looking at some details, trying to scope out the work that would be
> > required. We don't have anything definitive yet, but we should have
> > enough to share by the time of the LSF/MM/BPF.
>
> Excellent.  There are other people also interested in this.  eg:
>
> Ryan Roberts: https://lore.kernel.org/linux-mm/4c991dcb-c5bb-86bb-5a29-05df24429607@arm.com/
> Fengwei Yin: https://lore.kernel.org/linux-mm/20230109072232.2398464-1-fengwei.yin@intel.com/
>
> Obviously I'm keenly interested.
> https://lore.kernel.org/linux-mm/Y%2FU8bQd15aUO97vS@casper.infradead.org/
>
> This is definitely worth its own session in the MM track.

Absolutely.

Re: [LSF/MM/BPF TOPIC] Flexible orders for anonymous folios

[Ryan Roberts]

On 23/02/2023 04:01, Matthew Wilcox wrote:
> On Wed, Feb 22, 2023 at 04:55:20PM -0700, Yu Zhao wrote:
>> Currently anonymous folios only support two orders: 0 and the PMD
>> order. Flexible orders for anonymous folios can resist both internal
>> or external fragmentations when the PMD order is too underutilized or
>> costly to allocate. Flexible orders can also leverage the TLB
>> coalescing feature, .e.g., order 3 for AMD and order 4 for ARM CPUs.
>>
>> Discussion points:
>> 1. The page fault path: determining the best order and the fallback policy.
>> 2. The reclaim path: detecting the utilization and the splitting policy.
>> 3. The refcount and the mapcount models, e.g., reuse the PMD-mapped
>> THP model or not.
>> 4. The splitting, and the collapsing if needed.
>> 5. Other paths: COW, GUP, madvise(), mprotect(), page migration, etc.
> 
> 6. Swap out an entire folio instead of splitting it before swap.
> 7. At some point we're going to want Zi Yan's patches to split a folio
>    into arbitrary order folios instead of just to order-0.
> 8. For file folios, folio->index % folio->nr_pages is 0.  Do we want
>    to maintain that invariant for anon folios?  It helps tile the
>    folios so we don't end up with say, order-0, order-4, order-2 folios
>    in a sequence.
> 9. How do we ensure that two page faults do not overwrite each others
>    folios, eg PF1 decides to allocate an order-0 folio at index 6 and
>    PF2 decides to allocate an order-2 folio at index 4?
> 
> Probably some other things left to decide.
> 
>> Now it seems to be a good time to revisit. Yang Shi and I have been
>> looking at some details, trying to scope out the work that would be
>> required. We don't have anything definitive yet, but we should have
>> enough to share by the time of the LSF/MM/BPF.
> 
> Excellent.  There are other people also interested in this.  eg:
> 
> Ryan Roberts: https://lore.kernel.org/linux-mm/4c991dcb-c5bb-86bb-5a29-05df24429607@arm.com/

Yes, I'm very interested, and would be keen to join the discussion. I have some
thoughts in this mail, if you want to have a look:
https://lore.kernel.org/linux-mm/a7cd938e-a86f-e3af-f56c-433c92ac69c2@arm.com/

Feel free to CC me on any discussion.

> Fengwei Yin: https://lore.kernel.org/linux-mm/20230109072232.2398464-1-fengwei.yin@intel.com/
> 
> Obviously I'm keenly interested.
> https://lore.kernel.org/linux-mm/Y%2FU8bQd15aUO97vS@casper.infradead.org/
> 
> This is definitely worth its own session in the MM track.
> 
> 

Re: [LSF/MM/BPF TOPIC] Flexible orders for anonymous folios

[Zi Yan]

[-- Attachment #1: Type: text/plain, Size: 2512 bytes --]

On 22 Feb 2023, at 23:01, Matthew Wilcox wrote:

> On Wed, Feb 22, 2023 at 04:55:20PM -0700, Yu Zhao wrote:
>> Currently anonymous folios only support two orders: 0 and the PMD
>> order. Flexible orders for anonymous folios can resist both internal
>> or external fragmentations when the PMD order is too underutilized or
>> costly to allocate. Flexible orders can also leverage the TLB
>> coalescing feature, .e.g., order 3 for AMD and order 4 for ARM CPUs.
>>
>> Discussion points:
>> 1. The page fault path: determining the best order and the fallback policy.
>> 2. The reclaim path: detecting the utilization and the splitting policy.
>> 3. The refcount and the mapcount models, e.g., reuse the PMD-mapped
>> THP model or not.
>> 4. The splitting, and the collapsing if needed.
>> 5. Other paths: COW, GUP, madvise(), mprotect(), page migration, etc.
>
> 6. Swap out an entire folio instead of splitting it before swap.
> 7. At some point we're going to want Zi Yan's patches to split a folio
>    into arbitrary order folios instead of just to order-0.

Since you mentioned it, I rebased it here: https://github.com/x-y-z/linux-1gb-thp/tree/split_thp_to_any_order_mm-everything-2023-03-04-00-19 . I will send it
out whenever it is needed. :)

> 8. For file folios, folio->index % folio->nr_pages is 0.  Do we want
>    to maintain that invariant for anon folios?  It helps tile the
>    folios so we don't end up with say, order-0, order-4, order-2 folios
>    in a sequence.
> 9. How do we ensure that two page faults do not overwrite each others
>    folios, eg PF1 decides to allocate an order-0 folio at index 6 and
>    PF2 decides to allocate an order-2 folio at index 4?
>
> Probably some other things left to decide.
>
>> Now it seems to be a good time to revisit. Yang Shi and I have been
>> looking at some details, trying to scope out the work that would be
>> required. We don't have anything definitive yet, but we should have
>> enough to share by the time of the LSF/MM/BPF.
>
> Excellent.  There are other people also interested in this.  eg:
>
> Ryan Roberts: https://lore.kernel.org/linux-mm/4c991dcb-c5bb-86bb-5a29-05df24429607@arm.com/
> Fengwei Yin: https://lore.kernel.org/linux-mm/20230109072232.2398464-1-fengwei.yin@intel.com/
>
> Obviously I'm keenly interested.
> https://lore.kernel.org/linux-mm/Y%2FU8bQd15aUO97vS@casper.infradead.org/
>
> This is definitely worth its own session in the MM track.


--
Best Regards,
Yan, Zi

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 854 bytes --]

Re: [LSF/MM/BPF TOPIC] Flexible orders for anonymous folios

[Jason Gunthorpe]

On Wed, Feb 22, 2023 at 04:55:20PM -0700, Yu Zhao wrote:
> Currently anonymous folios only support two orders: 0 and the PMD
> order. Flexible orders for anonymous folios can resist both internal
> or external fragmentations when the PMD order is too underutilized or
> costly to allocate. Flexible orders can also leverage the TLB
> coalescing feature, .e.g., order 3 for AMD and order 4 for ARM CPUs.

I'm interested in this too - we've started to look at using 64K as a
base page size on ARM systems and having an order 3 folio would be the
usual 2M "THP" size with the coalescing feature. Keeping THP is a
desirable thing.

We also have some IOMMU HW that can do flexible orders, so even if the
CPU TLB cannot store odd folio sizes the IOMMU TLB can, which can be
interesting for KVM & VFIO.

Thanks,
Jason

Re: [LSF/MM/BPF TOPIC] Flexible orders for anonymous folios

[Hillf Danton]

On Wed, Feb 22, 2023 at 04:55:20PM -0700, Yu Zhao wrote:
> Currently anonymous folios only support two orders: 0 and the PMD
> order. Flexible orders for anonymous folios can resist both internal
> or external fragmentations when the PMD order is too underutilized or
> costly to allocate. Flexible orders can also leverage the TLB
> coalescing feature, .e.g., order 3 for AMD and order 4 for ARM CPUs.
> 
> Discussion points:
> 1. The page fault path: determining the best order and the fallback policy.
> 2. The reclaim path: detecting the utilization and the splitting policy.
> 3. The refcount and the mapcount models, e.g., reuse the PMD-mapped
> THP model or not.
> 4. The splitting, and the collapsing if needed.
> 5. Other paths: COW, GUP, madvise(), mprotect(), page migration, etc.

  6. Given the number of TLB is farrr less than the number of pages,
     what workload prefers MADV_ORDER6 over MADV_HUGEPAGE for instance? 

Re: [LSF/MM/BPF TOPIC] Flexible orders for anonymous folios

[Matthew Wilcox]

On Sun, Feb 26, 2023 at 09:30:31AM +0800, Hillf Danton wrote:
> On Wed, Feb 22, 2023 at 04:55:20PM -0700, Yu Zhao wrote:
> > Currently anonymous folios only support two orders: 0 and the PMD
> > order. Flexible orders for anonymous folios can resist both internal
> > or external fragmentations when the PMD order is too underutilized or
> > costly to allocate. Flexible orders can also leverage the TLB
> > coalescing feature, .e.g., order 3 for AMD and order 4 for ARM CPUs.
> > 
> > Discussion points:
> > 1. The page fault path: determining the best order and the fallback policy.
> > 2. The reclaim path: detecting the utilization and the splitting policy.
> > 3. The refcount and the mapcount models, e.g., reuse the PMD-mapped
> > THP model or not.
> > 4. The splitting, and the collapsing if needed.
> > 5. Other paths: COW, GUP, madvise(), mprotect(), page migration, etc.
> 
>   6. Given the number of TLB is farrr less than the number of pages,
>      what workload prefers MADV_ORDER6 over MADV_HUGEPAGE for instance? 

Many.  https://lore.kernel.org/linux-mm/Y%2FWRlX+MkmxelNbg@casper.infradead.org/

Re: [LSF/MM/BPF TOPIC] Flexible orders for anonymous folios

[Hillf Danton]

On Sun, 26 Feb 2023 02:34:05 +0000 Matthew Wilcox <willy@infradead.org>
> On Sun, Feb 26, 2023 at 09:30:31AM +0800, Hillf Danton wrote:
> > On Wed, Feb 22, 2023 at 04:55:20PM -0700, Yu Zhao wrote:
> > > Currently anonymous folios only support two orders: 0 and the PMD
> > > order. Flexible orders for anonymous folios can resist both internal
> > > or external fragmentations when the PMD order is too underutilized or
> > > costly to allocate. Flexible orders can also leverage the TLB
> > > coalescing feature, .e.g., order 3 for AMD and order 4 for ARM CPUs.
> > > 
> > > Discussion points:
> > > 1. The page fault path: determining the best order and the fallback policy.
> > > 2. The reclaim path: detecting the utilization and the splitting policy.
> > > 3. The refcount and the mapcount models, e.g., reuse the PMD-mapped
> > > THP model or not.
> > > 4. The splitting, and the collapsing if needed.
> > > 5. Other paths: COW, GUP, madvise(), mprotect(), page migration, etc.
> > 
> >   6. Given the number of TLB is farrr less than the number of pages,
> >      what workload prefers MADV_ORDER6 over MADV_HUGEPAGE for instance? 
> 
> Many.  https://lore.kernel.org/linux-mm/Y%2FWRlX+MkmxelNbg@casper.infradead.org/

Which one, supposedly given Apache Spark, MariaDB, Memcached, MongoDB,
Apache Cassandra, Apache Hadoop, PostgreSQL and Redis to ease the anwser?

Re: [LSF/MM/BPF TOPIC] Flexible orders for anonymous folios

[Hillf Danton]

On Sun, 26 Feb 2023 12:12:59 +0800 Hillf Danton wrote:
> On Sun, 26 Feb 2023 02:34:05 +0000 Matthew Wilcox <willy@infradead.org>
> > On Sun, Feb 26, 2023 at 09:30:31AM +0800, Hillf Danton wrote:
> > > On Wed, Feb 22, 2023 at 04:55:20PM -0700, Yu Zhao wrote:
> > > > Currently anonymous folios only support two orders: 0 and the PMD
> > > > order. Flexible orders for anonymous folios can resist both internal
> > > > or external fragmentations when the PMD order is too underutilized or
> > > > costly to allocate. Flexible orders can also leverage the TLB
> > > > coalescing feature, .e.g., order 3 for AMD and order 4 for ARM CPUs.
> > > > 
> > > > Discussion points:
> > > > 1. The page fault path: determining the best order and the fallback policy.
> > > > 2. The reclaim path: detecting the utilization and the splitting policy.
> > > > 3. The refcount and the mapcount models, e.g., reuse the PMD-mapped
> > > > THP model or not.
> > > > 4. The splitting, and the collapsing if needed.
> > > > 5. Other paths: COW, GUP, madvise(), mprotect(), page migration, etc.
> > > 
> > >   6. Given the number of TLB is farrr less than the number of pages,
> > >      what workload prefers MADV_ORDER6 over MADV_HUGEPAGE for instance? 

        7. Given p4d_t, is 2023-25 the right time to add the PUD order?

> > 
> > Many.  https://lore.kernel.org/linux-mm/Y%2FWRlX+MkmxelNbg@casper.infradead.org/
> 
> Which one, supposedly given Apache Spark, MariaDB, Memcached, MongoDB,
> Apache Cassandra, Apache Hadoop, PostgreSQL and Redis to ease the anwser?

Re: [LSF/MM/BPF TOPIC] Flexible orders for anonymous folios

[Chris Li]

On Wed, Feb 22, 2023 at 04:55:20PM -0700, Yu Zhao wrote:
> Discussion points:
> 1. The page fault path: determining the best order and the fallback policy.
> 2. The reclaim path: detecting the utilization and the splitting policy.
> 3. The refcount and the mapcount models, e.g., reuse the PMD-mapped
> THP model or not.
> 4. The splitting, and the collapsing if needed.
> 5. Other paths: COW, GUP, madvise(), mprotect(), page migration, etc.
>

I am interested in this topic and I would like to partition the
discussion as well.

Chris

Re: [LSF/MM/BPF TOPIC] Flexible orders for anonymous folios

[Yu Zhao]

First of all, if you have not filled out the form yet, please do it now :)

https://forms.gle/VKVXjWGBHZbnsz226

If you wish to present, please let me know. We probably can fit in two
more speakers, and I'll try to negotiate a one-hour session for this
topic. (The worst case: I'll give up my spot, which I have no problem
with.)

Also you don't have to wait until the conference to discuss this
topic. The biweekly THP Cabal meeting is open to everyone. Please ask
Matthew for the Zoom link. (I can't post it on the mailing list here
because of Zoom bombing concerns.)

Thank you.