The Place to Start for Operating System Developers
It is currently Sun May 16, 2021 1:22 am

All times are UTC - 6 hours

Post new topic Reply to topic  [ 3 posts ] 
Author Message
 Post subject: The trade offs of struct page
PostPosted: Thu Apr 04, 2019 12:24 pm 

Joined: Thu May 17, 2007 1:27 pm
Posts: 901
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).

managarm: Microkernel-based OS capable of running a Wayland desktop (Discord: https://discord.gg/7WB6Ur3). My OS-dev projects: [mlibc: Portable C library for managarm, qword, Linux, Sigma, ...] [LAI: AML interpreter] [xbstrap: Build system for OS distributions].

 Post subject: Re: The trade offs of struct page
PostPosted: Mon Apr 08, 2019 7:02 am 

Joined: Fri Jun 28, 2013 1:48 am
Posts: 43
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.

Reinventing the Wheel, code: https://github.com/songziming/wheel

 Post subject: Re: The trade offs of struct page
PostPosted: Mon Jan 13, 2020 3:47 pm 
User avatar

Joined: Sun Dec 29, 2019 10:59 pm
Posts: 17
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.

Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 3 posts ] 

All times are UTC - 6 hours

Who is online

Users browsing this forum: No registered users and 3 guests

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group