The Place to Start for Operating System Developers
It is currently Mon Jun 17, 2019 11:04 pm

All times are UTC - 6 hours

Post new topic Reply to topic  [ 2 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: 581
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: A microkernel-based OS that is capable of running a Wayland desktop

 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: 37
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

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

All times are UTC - 6 hours

Who is online

Users browsing this forum: No registered users and 1 guest

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