Differences between revisions 6 and 11 (spanning 5 versions)

The ultimate goal of the folios project is to turn struct page into:

struct page {
        u64 memdesc;
};

Bits 0-3 of memdesc are a type field that describes what the remaining bits are used for.

type	Meaning	Remaining bits
0	Misc	See below
1	Buddy	Embedded struct buddy
2	File	Pointer to struct folio
3	Anon	Pointer to struct anon_folio
4	KSM	Pointer to struct ksm (TBD)
5	Slab	Pointer to struct slab
6	Movable	Pointer to struct movable (TBD)
7	PageTable	Pointer to struct ptdesc
8	NetPool	Pointer to struct netpool (TBD)
9	HWPoison	Pointer to struct hwpoison (TBD)
10	PerCPU	Pointer to struct pcpudesc (TBD)
11-15	not yet assigned

Misc memory

Type 0 is used for memory which needs no further data associated with it. Bits 4-10 are used as a subtype to determine what the memory is used for:

Subtype	Meaning
0	PageReserved
1	A Zero Page (maybe PTE or PMD)
2	Unknown (probably device driver)
3	Vmalloc
4	Guard
5	Offline
6	kmalloc_large
7	Exact
8	brd
9-127	not yet assigned

Bit 11 is set if the page may be mapped to userspace.

Bits 12-17 are used to store the order of the page. The high bits are used to store section/node/zone information, as is done today with the page flags.

XXX: How to indicate that a page was allocated from reserves like pfmemalloc today?

NOTE! There is no refcount for this kind of memory! Nor mapcount! get_page() / put_page() will throw an error for them. You can free the pages, and they will go straight back to the page allocator. If you need a refcount, allocate a folio instead. You can still map them to userspace, but they will be treated like a PFNMAP.

struct buddy

Type 1 is used for pages which are in the MatthewWilcox/BuddyAllocator. This is either one or two words of data which is used to manage the pages (see the link for more detail).

Memdesc pointers

All structs pointed to from a memdesc must be allocated from a slab which has its alignment set to 16 bytes (in order to allow the bottom 4 bits to be used for the type). That implies that they are a multiple of 16 bytes in size. The slab must also have the TYPESAFE_BY_RCU flag set as some page walkers will attempt to look up the memdesc from the page while holding only the RCU read lock.

struct folio

struct folio {
    unsigned long flags;
    struct list_head lru;
    struct address_space *mapping;
    pgoff_t index;
    void *private;
    atomic_t _refcount;
    atomic_t _mapcount;
    unsigned long pfn;
    unsigned long memcg_data;
};

This looks very similar to today. The only addition is the pfn, which we can use for getting the struct page if needed.

Other structs

TBD

Allocating memory

Device drivers that do not touch the contents of struct page can continue calling alloc_pages() as they do today. They will get back a struct page pointer which will have subtype "Unknown" but they won't care.

We'll add a new memdesc_alloc_pages() family which allocate the memory and set each page->memdesc to the passed-in memdesc. So each memdesc allocator will first use slab to allocate a memdesc, then allocate the pages that point to that memdesc.

alloc_pages_exact

We'll follow the same approach as today; allocate a buddy of sufficient size, but we'll expose a new primitive buddy_free_tail() which will release the tail pages back to the buddy allocator.

Slab memdesc

There's a minor recursion problem for the slab memdesc. This can be avoided by special-casing the struct slab allocation; any time we need to allocate a new slab for the slab memdesc cache, we _do not_ allocate a struct slab for it; we use the first object in the allocated memory for its own struct slab.

Freeing memory

Folios (file/anon/ksm) have a refcount. These should be freed with folio_put(). Other memdescs may not have a refcount (eg slab).

Misc allocations (type 0) are simply passed back to the page allocator which will turn them into Buddy pages.

Memory control group

Splitting folios

It is going to be stupidly expensive to split an order-9 allocation into 512 order-0 allocations. We'll have to allocate 512 folios. We may want to optimise split_page() to only allocate folios for pages we're not going to immediately free.

Mapping memory into userspace

File, anon memory and KSM memory is rmappable. The rmap does not apply to other kinds of memory (networking, device driver, vmalloc, etc). These kinds of memory should be added to VM_MIXEDMAP or VM_PFNMAP mappings only.

Things to remember

ext4 attaches a buffer_head to memory allocated from slab. virt_to_folio() should probably return NULL in this case?

-  ⇤ ← Revision 6 as of 2024-01-06 14:40:12 → 
  Size: 7868
  Editor: MatthewWilcox
  Comment: Exact allocation, option 3 for buddy allocation, split_page discussion
+   ← Revision 11 as of 2024-05-15 16:07:59 → ⇥
  Size: 5641
  Editor: MatthewWilcox
  Comment:
-Deletions are marked like this.
+Additions are marked like this.
 Line 5:
-        unsigned long memdesc;
+        u64 memdesc;
 Line 12:
-||     0 || Irregular memory   || See below                         ||
||     1 || Buddy              || Pointer to struct buddy           ||
+||     0 || Misc               || See below                         ||
||     1 || Buddy              || Embedded struct buddy             ||
 Line 22:
-|| 10-15 || not yet assigned   || ||
+||    10 || PerCPU             || Pointer to struct pcpudesc (TBD)  ||
|| 11-15 || not yet assigned   ||                                   ||
-Line 25:
+Line 26:
-=== Irregular memory ===
+=== Misc memory ===
-Line 27:
+Line 28:
-Type 0 is used for pages which will never be freed.  Bits 4-7 distinguish why this page is irregular:
+Type 0 is used for memory which needs no further data associated with it.  Bits 4-10 are used as a subtype to determine what the memory is used for:
-Line 29:
+Line 30:
-|| subtype || Meaning                             ||
||       0 || The Zero Page                       ||
||       1 || PageReserved                        ||
||    2-15 || not yet assigned                    ||
+|| Subtype || Meaning                          ||
||       0 || PageReserved                     ||
||       1 || A Zero Page (maybe PTE or PMD)   ||
||       2 || Unknown (probably device driver) ||
||       3 || Vmalloc                          ||
||       4 || Guard                            ||
||       5 || Offline                          ||
||       6 || kmalloc_large                    ||
||       7 || Exact                            ||
||       8 || brd                              ||
||   9-127 || not yet assigned                 ||
-Line 34:
+Line 42:
-Bits 8-13 are also used to store the order of the page.
+Bit 11 is set if the page may be mapped to userspace.

Bits 12-17 are used to store the order of the page.
-Line 37:
+Line 47:
+XXX: How to indicate that a page was allocated from reserves like pfmemalloc today?

NOTE!  There is no refcount for this kind of memory!  Nor mapcount!  get_page() / put_page() will throw an error for them.  You can free the pages, and they will go straight back to the page allocator.  If you need a refcount, allocate a folio instead.  You can still map them to userspace, but they will be treated like a PFNMAP.

=== struct buddy ===

Type 1 is used for pages which are in the MatthewWilcox/BuddyAllocator.  This is either one or two words of data which is used to manage the pages (see the link for more detail).
-Line 42:
+Line 59:
-Other than struct buddy, all memdescs must have a pointer to struct buddy as the first word.  See below.


=== struct buddy ===
+=== struct folio ===
-Line 48:
+Line 62:
-struct buddy {
        unsigned long flags;
        struct list_head buddy_list;
        struct page *first;
+struct folio {
    unsigned long flags;
    struct list_head lru;
    struct address_space *mapping;
    pgoff_t index;
    void *private;
    atomic_t _refcount;
    atomic_t _mapcount;
    unsigned long pfn;
    unsigned long memcg_data;
-Line 55:
+Line 75:
-This is used by the buddy allocator to track free pages.  It is also used when the user does not need to store significant auxiliary information.  The upper bits of the flags word contains section/node/zone information as page->flags does today.  However the lower bits are quite different:
+This looks very similar to today.  The only addition is the pfn, which we can use for getting the struct page if needed.
-Line 57:
+Line 77:
-|| Bits  || Meaning            ||
||  0-3  || Subtype            ||
||  4-9  || Order              ||
|| 10-13 || Migratetype        ||
||    14 || pfmemalloc         ||
||    15 || Userspace mappable ||
+=== Other structs ===
-Line 64:
+Line 79:
-|| Subtype || Meaning                  ||
||       0 || Free                     ||
||       1 || Device driver allocation ||
||       2 || Vmalloc                  ||
||       3 || Guard                    ||
||       4 || Offline                  ||
||       5 || kmalloc_large            ||
||       6 || PMD-sized Zero Page      ||
||       7 || Exact           ||
||    8-15 || not yet assigned         ||
+TBD
-Line 77:
+Line 83:
-Device drivers that do not touch the contents of struct page can continue calling alloc_pages() as they do today.  They will get back a struct page pointer which will have a struct buddy memdesc, but they won't care.
+Device drivers that do not touch the contents of struct page can continue calling alloc_pages() as they do today.  They will get back a struct page pointer which will have subtype "Unknown" but they won't care.
-Line 79:
+Line 85:
-We'll add a new buddy_alloc() which will return the buddy memdesc pointer instead.  Each allocator can change the subtype from 'Free' to whatever subtype it has.

We'll add a new memdesc_alloc_pages() family which allocate the memory and set each page->memdesc to the passed-in memdesc.  So each memdesc allocator will first use slab to allocate a memdesc, then allocate the pages that point to that memdesc.  As an optimisation, if sizeof(struct my_memdesc) is <= sizeof(struct buddy), we can avoid allocating a new memdesc and cast the pointer returned from buddy_alloc().
+We'll add a new memdesc_alloc_pages() family which allocate the memory and set each page->memdesc to the passed-in memdesc.  So each memdesc allocator will first use slab to allocate a memdesc, then allocate the pages that point to that memdesc.
-Line 91:
+Line 95:
-=== Buddy memdesc ===

When the page allocator wants to split an order-N page into two lower-order pages, it has to allocate a new buddy.  Which comes from the slab allocator.  So when allocating a folio, we might see:

 * Allocate folio memdesc
 * Folio slab cache has no free objects, allocates a new slab (order 0)
 * The smallest order that the page allocator has on hand is order-3
 * Page allocator asks slab for 3 new buddy memdescs (one for each level)
 * Buddy slab cache has no free objects, allocates a new slab (order 0)
 * ... oh dear ...

Here are a few options for solving it.

 1. When allocating buddy slabs, slab could pass order -1 to the page allocator, which would mean to hand back _any_ order page.  Slab would then use the first N objects in the first page to be the buddy memdescs for (in this example) page 1, 2 and 4.  Then it would give the extra pages back to the page allocator.
 2. The page allocator could avoid using the slab allocator to allocate buddies.  They're 16 byte objects, and it's relatively easy to split a 4kB page into 256 equal pieces.  But then the page allocator is duplicating something that slab is good at.
 3. Pass -1 as the order when allocating buddy slabs. Treat it as an order-0 slab and use buddy_free_pages() to free all but the first page. The page allocator will allocate fresh buddies from the slab allocator which will be able to satisfy them.

So the new worst-case scenario looks like:

 * Allocate folio memdesc
 * Folio slab cache has no free objects, allocates a new slab (order 0)
 * The smallest order that the page allocator has on hand is order-3
 * Page allocator asks slab for 3 new buddy memdescs (one for each level)
 * Buddy slab cache has no free objects, allocates a new slab (order -1)
 * Page allocator returns the order-3 buddy it was going to use for slab
 * Slab returns 7 pages to the page allocator
 * Page allocator allocates 3 buddies
 * Page allocator returns the order-0 page
 * Slab allocator gives itself the struct slab it needed

This can be made more complex by, e.g., an interrupt coming in and stealing all the buddy objects, but since we get 256 per 4kB page this is unlikely, and the consequence is simply going around the loop again.
-Line 125:
+Line 97:
-Folios (file/anon/ksm) have a refcount.  These should be freed with folio_put().  Other memdescs may not have a refcount,
+Folios (file/anon/ksm) have a refcount.  These should be freed with folio_put().  Other memdescs may not have a refcount (eg slab).
-Line 127:
+Line 99:
-Allocations which use a buddy memdesc are simply passed back to the page allocator.  Other memdescs will copy the buddy pointer from the memdesc before RCU freeing it, and update each struct page with the buddy memdesc.
+Misc allocations (type 0) are simply passed back to the page allocator which will turn them into Buddy pages.
-Line 133:
+Line 105:
-It is going to be stupidly expensive to split an order-9 allocation into 512 order-0 allocations. We'll have to allocate 512 buddys and 512 folios. We may want to optimise split_page() to only allocate folios for pages we're not going to immediately free, and to allocate higher order buddies for pages we are going to free.
+It is going to be stupidly expensive to split an order-9 allocation into 512 order-0 allocations. We'll have to allocate 512 folios. We may want to optimise split_page() to only allocate folios for pages we're not going to immediately free.
-Line 138:
+Line 110:
+= Things to remember =

ext4 attaches a buffer_head to memory allocated from slab.  virt_to_folio() should probably return NULL in this case?