I'm building a small x86-64 kernel that I write completely from scratch. I'm starting to write a very simple memory allocator where I simply iterate on page structs to find a free page and break the loop when I find one. When I began writing the allocator, I stumbled upon an issue.

In my kernel, I managed to get a memory map of RAM using a UEFI call (GetMemoryMap()). By iterating on the memory map, I managed to find that I would have around 1021MB of usable memory (out of 1024MB). I test my kernel on QEMU.

I read here and there that the Linux kernel holds a page struct for every page in the system. I'm guessing that the memory allocator of the Linux kernel uses the page structs to determine what page is free and which isn't. By using a proper binary structure and an efficient algorithm, it attempts to find a free page as fast as possible to use for itself or to provide to a user mode process.

If my assumption is correct, the issue arises here. If the Linux kernel's memory allocator relies on the page struct to work, how does it allocate memory for the page structs themselves?

I thought of a simple algorithm where I simply start at the physical address of the first usable memory region. If this memory region has enough room for all the page structs (representing the whole memory), I stop there. Otherwise, I use the second memory region an so on. This seems quite simple but I wanted to know how the Linux kernel handles that issue.

Even if my above assumption is wrong, the memory allocator probably requires some memory to work. At boot, how does the Linux kernel allocate memory for its own memory allocator?