The trade offs of struct page
Page 1 of 1

Author:  Korona [ Thu Apr 04, 2019 12:24 pm ]
Post subject:  The trade offs of struct page

In the last few weeks, I made a lot of changes to my MM code. My current issue is whether I want to have 'struct page' for every physical page in the system or not. I discuss the issue below and raise some questions.

To get get everybody on the same page: AFAICS, the two main issues that a 'struct page' can solve are:
  • Caching and swapping. The structs can be linked together to form a LRU list which is necessary to implement page caches.
  • Memory locking. You can store a lock counter in the struct to quickly lock a page of memory in place (e.g., so that DMA can be performed without worrying about swapping).

Q1: Do you (plan) to use a 'struct page' to solve these problems? If not, how would you solve the issues above?

In my current design, I have 'struct page's for all pages in the page cache, but not for non-swapable pages.

To map physical addresses to the structs, several approaches are possible:
  • Do not have a global mapping. Instead, let individual memory objects (i.e., the objects managing the pages or the page cache) provide their own mappings.
  • Map them contiguously somewhere in virtual memory and do an indexed lookup. This is the fastest options; however, it does not really allow you to allocate those structs selectively: they have to be allocated and mapped, otherwise you get page faults.
  • Use a global radix tree to do the mapping. This has the advantage that it allows you even to determine if a 'struct page' exists for a certain physical page.

Q2: How do you map physical addresses to 'struct page's?

Right now, I am using the first approach. However, I contemplate switching to the third variant with a radix tree. This would make lookup faster (as it would not have to go through a virtual call anymore). Hence, it would also speed up memory locking. The latter needs to be performed quite often (as my microkernel frequently needs access to pages in other address spaces).

Author:  songziming [ Mon Apr 08, 2019 7:02 am ]
Post subject:  Re: The trade offs of struct page

Currently I have no plan to support swapping, but I still think `struct page` is necessary.

The most simple version of `struct page` is just one double linked list item, so a page can be put in any list. That list can be free page list, allocated pages for process, heap, stack, etc. Memory manager is not the only one that access `struct page`.

This is my design of `struct page`:

typedef struct page {
    pfn_t prev;                 // previous page in the list
    pfn_t next;                 // next page in the list
    u32   type : 4;
    union {
        struct {                // free
            u32 order : 4;      // only valid when block=1
            u32 block : 1;      // is it the first page in block
        struct {                // pool
            u16 objects;        // first free object
            u16 inuse;          // number of allocated objects
} page_t;

I use buddy algorithm like Linux does, multiple continuous free pages are grouped as a block. I use union and bit-fields to save some space.

Author:  nyc [ Mon Jan 13, 2020 3:47 pm ]
Post subject:  Re: The trade offs of struct page

Q1: There is trouble with an O(RAM) (O(M)??) memory and boot-time initialisation footprint, so I don't intend to use a struct page analogue. For things like a page cache and swapping I intend to use a working set memory scheduling model based on Mach-esque memory objects or to otherwise wing something based on some other precedent I can draw upon. Things like cached kernel metadata like Linux' directory entry, radix tree, etc. slab caches are unclear how to handle in a rigorous way, but I'd probably try to crossdress them as being similar to memory objects.

Q2: I would probably have analogues of Linux' struct pgdat or zones in a B+ tree or maybe even just a sorted array to map page frame numbers to struct page if I used struct page.

Page 1 of 1 All times are UTC - 6 hours
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group