The memory map chicken and egg dilemma.

[Neolander]

Hi everybody !

Lately, I've been working on my "bootstrap kernel", whose goal is to turn longmode on and make the real kernel's life easier. One of the thing I want it to do is create a nice memory map which, contrary to the one from the BIOS that I get through GRUB, is complete, meaning that it includes memory zones occupied by the kernel and its modules.

However, this map uses strings, and its size can't be guessed in advance. So I should use dynamic memory allocation. But to do so, I need a map of the memory...
And BAM, chicken and egg paradox !

I see two ways of solving this problem :
-Static memory allocation. Let's claim we'll need a maximum of x kB of memory for that map of memory, and reserve a buffer of that size in the kernel. It's ugly, and not very robust since it relies on an assumption, but it's simple and it works.
-Another way would be to use the following algorithm :

• Parse the memory once, deduce the size required by the memory map.
• Parse memory another time, find a hole in memory to hold the memory map using first fit or best fit.
• Finally, parse memory for the third time, this time actually writing the memory map

I have to say, I'm tempted by the second option. It's cleaner, and no one cares about it being a bit computationally intensive since the needed CPU time remains ridiculous (no I/O, pure RAM and computation. It's going to take a few miliseconds in the worst case). However, I wondered : I'm sure that many of you have encountered that problem. How did you solve it ?

[bewing]

Detecting stuff, and keeping structures of information in memory about what you detected, is the first and most important thing the kernel (or the kernel initialization routine) does. Since it is the first thing you do, you do not have to be formal about it. You do not need to formally allocate space for the memory structures. You do not need to precalculate their sizes.

Assume that you are going to load your kernel at the bottom of memory. Start your memory map growing down from the top of memory. When it grows down past the beginning of each legal memory region, set its 'next' pointer to the top of the next memory region down. Keep track of the total length. When you are done with your detection phase, you can copy that memory region anywhere, and you know its total size. If it overflows available memory, then your kernel could not have booted anyway.

[gravaera]

Hi:

I created a simple, uniform, non-hacky solution which is even extensible. The thing is, the memory layout, and even the location of the kernel in physical RAM is determined mostly the chipset itself. You won't load the kernel at the 1MB physical mark on most embedded platforms. You also can't rely on physical RAM of X size being at address 0x12345678 on all chipsets.

So I place the responsibility for determining the kernel's physical load address and the location of a range of free RAM on the person porting whatever chipset it is. For IBM-PC, whoever (me) is porting the kernel to IBM-PC would be aware of its memory internals, and know that it's safe to load @ 1MB. By extension, the person would also know what areas of RAM are almost guaranteed to be free for use by the kernel ( anywhere between 1MB and a bit under 16MB ). So a bitmap or other memory management structure is compiled into the kernel, which treats that allocatable range as...an allocatable range, and uses that as a temporary bootstrap frame allocator.

You need only set aside 4MB of RAM in the temporary space, since that will more than allow your memory manager to bootstrap itself and discover the true memory capacity of the machine through the firmware.

--Good luck,
gravaera

[Neolander]

Detecting stuff, and keeping structures of information in memory about what you detected, is the first and most important thing the kernel (or the kernel initialization routine) does. Since it is the first thing you do, you do not have to be formal about it. You do not need to formally allocate space for the memory structures. You do not need to precalculate their sizes.

Assume that you are going to load your kernel at the bottom of memory. Start your memory map growing down from the top of memory. When it grows down past the beginning of each legal memory region, set its 'next' pointer to the top of the next memory region down. Keep track of the total length. When you are done with your detection phase, you can copy that memory region anywhere, and you know its total size. If it overflows available memory, then your kernel could not have booted anyway.

But I don't know about legal memory regions since I don't have a map of them yet !
At the moment, I have various informations coming from several places (ld script, modules from GRUB, and mmap from GRUB, plus some pointer+sizeof() data*), and I want to put it together in one place, basically listing legal and reserved memory regions.
At the moment, anytime I want to find out something about them, I have to parse through all that stuff (which I called "parsing memory" earlier, I apologize for that confusing term)

So with your method (memory map as a linked list going from top to bottom, avoiding illegal regions), I'd have to
-Parse stuff and find where the top and the bottom of the last legal region are.
-Parse stuff again, starting to write my map, until I'm done with it or I've hit the bottom of my legal region.
-In the latter case, parse stuff in order to find the next available legal region.
-Go back to parsing in step 2, trying to get done with my map.
And so on...

I don't understand how this is simpler than my method. Have I misunderstood something ?

(PS : Pfew... It's in such case that I wish I was a native english speaker... Going technical in a non-native language is hard ^^')

[Owen]

I would make a simple assumption:

The memory from 1MB to 4MB is available and usable.

You're targeting AMD64 systems, which will never have less than 4MB of RAM installed. Your memory map will probably never exceed 4kb, so you should never encounter issues.

It will work everywhere and it is simple. Simplicity is always important: The more you conflate the design, the harder maintenance becomes, and the more bugs you introduce.

[gerryg400]

Neolander,

When you talk about map, are you talking about a bitmap to keep track of memory allocation ? You perhaps don't need a bitmap until much later when the real memory manager starts. Here's what I do

1. Get all information (from grub mbi, module info etc.) into a table that contains simply physical address and length of each memory region. Since this table is very small you might statically allocate it. Mine is 256 bytes long to support maximum 16 memory regions.

2. Check that the information gathered makes sense and remove part pages (my pc has these!!!!) and the areas occupied by your kernel etc. This might require splitting some areas.

3. Use a simple boot allocator that can take physical pages from the above table and map them to virtual addresses after the end of the kernel. My boot allocator cannot free memory but it is only used for permanent things like the SMP kernel stacks, tss, top level pagedirs etc. so that doesn't matter.

4. Use the boot allocator is to allocate the map that tracks physical memory usage. After that I have the real memory manager running.

I hope I understood your question and that this helps

- gerryg400

[Neolander]

OK, guess I'm reserving 1 MB in the bootstrap kernel for the memory map and other stuff. Even with 100 modules, each one having a 255-char long UTF16 name, and a much more complex memory map structure, I wouldn't get past 75 kB, so you're right, trying to use dynamic memory allocation may be overkill here since I assume that people have 512+ MB RAM.

Let's just hope that I won't encounter a bug due to that problem someday, because it looks hard as hell to find out what's going on.