OSDev.org

The Place to Start for Operating System Developers
It is currently Sun Sep 19, 2021 5:12 am

All times are UTC - 6 hours




Post new topic Reply to topic  [ 6 posts ] 
Author Message
 Post subject: Supporting Multiple Page Frame Allocators
PostPosted: Mon Apr 12, 2021 9:47 pm 
Offline
Member
Member

Joined: Wed Feb 24, 2021 8:52 pm
Posts: 25
So, I just got the GDT and IDT working. I decided that what I'm going to try and tackle now is page frame allocation.

The main thing is that I want to start with a relatively simple page frame allocator (such as a bitmap), but then build a better one later one. Ideally, I would design the page frame allocator so that I could easily switch between different page frame allocators without having to do heavy redesigns in order to accommodate the different types.

The idea I have currently is to design a generic page frame allocator struct. This struct has an enum member that it uses to identify the type of allocator and then a function pointer that actually performs the allocation.

When setting up the page frame allocator, the programmer calls a factory and passes in the enum type of the allocator. The factory then creates a particular page frame allocator (bitmap, for example), and then returns a pointer to a generic allocator (simulating inheritance). The only thing is that this may require heap allocation early on, and so that is one particular weakness. I'll go ahead and post the prototype for the generic allocator:

Code:
#ifndef PAGE_FRAME_H
#define PAGE_FRAME_H
#include <stddef.h>

enum pf_allocator_type {
        BITMAP,
        STACK,
        SIZED_PORTION,
        BUDDY
};

// The allocator is packed in case it is handled in assembly
struct pf_allocator_generic {
        enum pf_allocator_type type;
        void *(*allocate)(struct pf_allocator_generic pfg, size_t *size);
} __attribute__((packed));

/*
* The structure of a particular page frame allocator will
* be something like this:
*
* struct pf_allocator_bitmap {
*      struct pf_allocator_generic generic;
*      void *bitmap;
*      void *last_allocated;
*      size_t size;
* };
*
* void *allocate_page_bitmap(struct pf_allocator_bitmap pfb, size_t *size);
*
* The members of pf_allocator_generic would be as follows:
*
* generic.type = BITMAP;
* generic.allocate = &allocate_page_bitmap;
*
*/

#endif


Is this a good way to support multiple allocators? Is there a better way to approach this? Or maybe I should just bite the bullet and expect to have to rewrite it multiple times as I progress?

EDIT: I just realized that there is a big problem with the allocator itself. The particular allocator will expect particular pf allocator struct, whereas the generic allocator expects a generic pf allocator struct. One way to hack around this is to simply pass in void * for the struct, type cast to generic, and then type cast further depending on the type. However, at that point, I'm not sure much has been gained by the genericness of the code compared to the headache of implementation. But there are a lot of wise people here, and so I will simply wait to hear what everyone else has to say.


Top
 Profile  
 
 Post subject: Re: Supporting Multiple Page Frame Allocators
PostPosted: Mon Apr 12, 2021 10:09 pm 
Offline
Member
Member

Joined: Wed Aug 30, 2017 8:24 am
Posts: 1090
Just isolate the allocator into its own module. Expose the functions it is going to supply. Probably something along the lines of
  • Initialize with memory map
  • Allocate a page
  • Deallocate a page
I don't really see much else that needs to be there. Then implement this module with whatever strategy you see fit. If you later want to try out another one, create a new C file with a new implementation, then add it to the kernel and throw out the old one. There is really no need to tell the rest of the system what kind of strategy the allocator is using, is there? And there is no need to support multiple allocators at the same time.

_________________
Thou hast outraged, not insulted me, sir; but for that I ask thee not to beware of Starbuck; thou wouldst but laugh; but let Ahab beware of Ahab; beware of thyself, old man.


Top
 Profile  
 
 Post subject: Re: Supporting Multiple Page Frame Allocators
PostPosted: Mon Apr 12, 2021 10:17 pm 
Offline
Member
Member

Joined: Wed Feb 24, 2021 8:52 pm
Posts: 25
nullplan wrote:
Just isolate the allocator into its own module. Expose the functions it is going to supply. Probably something along the lines of
  • Initialize with memory map
  • Allocate a page
  • Deallocate a page
I don't really see much else that needs to be there. Then implement this module with whatever strategy you see fit. If you later want to try out another one, create a new C file with a new implementation, then add it to the kernel and throw out the old one. There is really no need to tell the rest of the system what kind of strategy the allocator is using, is there? And there is no need to support multiple allocators at the same time.


That makes sense. The only question is how do I do modules? This is basically a meaty skeleton with GDT and IDT implemented. Are you thinking along the lines of creating the bitmap allocator, creating the associated functions, and implementing them into the kernel, and then later on replacing those functions with one from a different allocator?


Top
 Profile  
 
 Post subject: Re: Supporting Multiple Page Frame Allocators
PostPosted: Tue Apr 13, 2021 11:25 am 
Offline
Member
Member

Joined: Mon Mar 25, 2013 7:01 pm
Posts: 3347
dengeltheyounger wrote:
Are you thinking along the lines of creating the bitmap allocator, creating the associated functions, and implementing them into the kernel, and then later on replacing those functions with one from a different allocator?

Yes.


Top
 Profile  
 
 Post subject: Re: Supporting Multiple Page Frame Allocators
PostPosted: Tue Apr 13, 2021 2:25 pm 
Offline
Member
Member

Joined: Wed Aug 30, 2017 8:24 am
Posts: 1090
dengeltheyounger wrote:
That makes sense. The only question is how do I do modules? This is basically a meaty skeleton with GDT and IDT implemented. Are you thinking along the lines of creating the bitmap allocator, creating the associated functions, and implementing them into the kernel, and then later on replacing those functions with one from a different allocator?

Yes, although I would isolate this stuff into a separate source file. This makes it easier to test different implementations, and eases isolation between different modules. More isolation makes more changes later easier.

_________________
Thou hast outraged, not insulted me, sir; but for that I ask thee not to beware of Starbuck; thou wouldst but laugh; but let Ahab beware of Ahab; beware of thyself, old man.


Top
 Profile  
 
 Post subject: Re: Supporting Multiple Page Frame Allocators
PostPosted: Wed Apr 14, 2021 8:33 pm 
Offline
Member
Member

Joined: Wed Feb 24, 2021 8:52 pm
Posts: 25
nullplan wrote:
dengeltheyounger wrote:
That makes sense. The only question is how do I do modules? This is basically a meaty skeleton with GDT and IDT implemented. Are you thinking along the lines of creating the bitmap allocator, creating the associated functions, and implementing them into the kernel, and then later on replacing those functions with one from a different allocator?

Yes, although I would isolate this stuff into a separate source file. This makes it easier to test different implementations, and eases isolation between different modules. More isolation makes more changes later easier.


That makes a lot of sense. I think I'm seeing how modules can apply to kernel design this early one. Thanks!


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 6 posts ] 

All times are UTC - 6 hours


Who is online

Users browsing this forum: evafzogeg, Google [Bot], LeapofAzzam and 21 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