Page 1 of 1

Supporting Multiple Page Frame Allocators

Posted: Mon Apr 12, 2021 9:47 pm
by dengeltheyounger
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: Select all

#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.

Re: Supporting Multiple Page Frame Allocators

Posted: Mon Apr 12, 2021 10:09 pm
by nullplan
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.

Re: Supporting Multiple Page Frame Allocators

Posted: Mon Apr 12, 2021 10:17 pm
by dengeltheyounger
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?

Re: Supporting Multiple Page Frame Allocators

Posted: Tue Apr 13, 2021 11:25 am
by Octocontrabass
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.

Re: Supporting Multiple Page Frame Allocators

Posted: Tue Apr 13, 2021 2:25 pm
by nullplan
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.

Re: Supporting Multiple Page Frame Allocators

Posted: Wed Apr 14, 2021 8:33 pm
by dengeltheyounger
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!