Where should I put page descriptors in the buddy allocator?

[RichardC1ay]

Hello! I am confused about the initialization of the buddy system allocator. I use it as my primary physical page frame allocator, but I don't know where to put the page descriptors in the memory.

Code: Select all

typedef struct pageframe
{
    lklist_head_t listnode;
    struct
    {
        uint8_t order: 4;
        bool free: 1;
        bool reserved: 1;
        uint32_t ign: 26;
    };
    spinlock_t lock;
    uintptr_t addr;
} pageframe_t;

A page descriptor takes 32 bytes. Unfortunately, the size of physical memory is unknown, which means that I cannot reserve spaces in bss section just like what bitmap allocator do.
In my opinion, I have to find a free space to store the initial page descriptors, it cannot overlap with the kernel address. And I think that there are some other structs reserved in the memory, such as ACPI table? It is easy for me to find where the kernel is, but not other structs.

In the other words, if I want to initialize the physical memory management, I have to find a free space to store my page descriptors, but the page descriptors tell me where is free or not. Currently, I don't know if is there another way to indicate which space is free. Saving it into bss section takes a lot of memory. In the worst situation (in my mind), this allocator takes a least 1/128 memory to store the page descriptors (for example, 128MB in 16GB).

Could anyone tell me whether there is another way to find a space to save the descriptors? or just point out problems in my logic? I am using stivale2 (limine) protocol to boot the kernel. I think the memory map might help me solve the problem. What if possible I just initialize all the memory regions marked as "available"?

Code: Select all

#define PAGE_MAX_SIZE (4 * 1024 * 1024)
#define PAGE_MAX_ORDER 10

typedef struct pageframe_list
{
    lklist_head_t handle;
    uint32_t count;
} pageframe_list_t;

typedef struct pageframe_block
{
    uint32_t count;
    uintptr_t addr;
    pageframe_list_t freelist[PAGE_MAX_ORDER + 1];
} pageframe_node_t;

This is the repo of my kernel: https://github.com/CubikOSProject/CubikOS

[Octocontrabass]

A page descriptor takes 32 bytes.

If you use a series of bitmaps instead of a linked list, a page descriptor takes no more than two bits per page to track free memory. Your allocator should only track whether or not a page is free; if you want to track other information, you should do it elsewhere.

In my opinion, I have to find a free space to store the initial page descriptors, it cannot overlap with the kernel address. And I think that there are some other structs reserved in the memory, such as ACPI table? It is easy for me to find where the kernel is, but not other structs.

Your bootloader guarantees that none of those structures will be located in "free" memory.

I am using stivale2 (limine) protocol to boot the kernel.

Limine has dropped support for stivale2.

I think the memory map might help me solve the problem.

It will. You'll use the memory map to find enough free pages to initialize your allocator, and when you initialize the allocator you'll mark those pages as "not free".