OSDev.org

Paging tricks can really speed up the huge-bitmap initialization. Fill single page with 0 or FF, then set up paging structures to fill the bitmap 4K, 2M or 1G at a time. Obviously mark those as copy-on-write. There will be few regions where you can not do much this way, but it should be fine for bulk of the memory.

The initialization and runtime handling gets a bit more complicated, there might arise some chicken-and-egg problems. But sophisticated OSes implement CoW anyway, this is just another use for it.

That's a great idea! Thanks for sharing.

You should ignore reserved entries when initializing the bitmap.


Yes.


It isn't the size of RAM. It could be bigger or smaller. (Usually it will be bigger.)


No. Reserved memory will never be free, so you don't need to track it in your bitmap.


Why do you want to calculate the amount of installed RAM? You don't need it to set up your bitmap.


You also need PAE to use the NX bit.

Okay so I can just ignore the size of RAM as I will never get it, and I can just calculate bitmap size based on the memory map highest point and lowest point, right?

But the thing you said about reserved memory - that I shouldn't track it in my bitmap, if I ignore the reserved areas and don't track them in my memory map then how do I give out these areas to drivers that might have MMIO there?

Should I add up to nearest address aligned by 4096 the start of the lowest area in memory map(as it may not be aligned), and should I decrease the end of highest to get a 4096 aligned address ?

Also, just if you know - how do OSs like windows or linux get the amount of RAM ?

Right.


You can let the driver access whatever it wants, the driver will know where its MMIO is. MMIO is not always in the reserved areas; it can also be in areas that aren't part of the memory map.


Something like that. It gets tricky because you can also have ranges that overlap.


Which one, the amount of RAM the OS can use or the amount of RAM physically installed? The amount the OS can use is calculated by adding up all usable memory from the memory map (after cleaning up unaligned and overlapping areas). The amount installed is in the SMBIOS tables.

What do you mean by overlapping areas so for example it might say that 0x0 - 0x200 is free and other entry might say that 0x150-0x300 is free?

How would I handle the overlapping areas, so I setup frame allocation and then I should clean up the memory map and set it up again?

How would I fix unaligned areas - just add needed amount to start address to make it 4096 algined, and if there is not enough space in it's memory map entry for that then just remove this entry and the same thing with the end, but there I should remove till it is not 4096 algined?

Yes, that sort of thing. They might not be the same type.


Why would you set up the allocator twice? Build a clean memory map first, then set up the allocator.


It depends on the type of the entry. For usable memory, increase the start address and decrease the end address (make it smaller) until both are aligned. For reserved memory, decrease the start address and increase the end address (make it bigger) until both are aligned.

Thanks, I would never probably guessed there should be so much details taken in to account in the memory map?


Wow, that looks harder and harder. Do you know any code that handles memory map cleaning that I might look at that is in C and not SUPER long(like several thousand line PMM)?
And also, how is it possible there are overlapping areas of different types?


Because the first time I don't have an allocator so I have nothing to allocate space for the new memory map(the previous is obtained from the bootloader)

I don't know of any that are short, but you could try looking at how Linux does it.


Firmware isn't very smart.


Linux puts the buffer for the new memory map in the .bss section. That way, the bootloader is in charge of figuring out how to allocate space.

I think it's possible to calculate individual sanitized memory map entries using only the original memory map, which would mean you could figure out the lowest and highest valid addresses and find a range of memory big enough for the PMM without needing to dynamically allocate any memory. I've never worked out exactly how to do it, though.

I am using the UEFI memory map, is the BIOS one similar(as understand this driver is for BIOS memory map)?


If we put it in bss then we need to know the size of it at write/compile time, but we don't so how does linux do it?

Since you're using UEFI, you can take some shortcuts. The UEFI memory map is always properly aligned, and shouldn't have any overlaps. You don't need to check alignment at all, and you can refuse to boot if you find overlaps.

Linux uses that code for all memory maps, including the UEFI memory map.


Linux chooses a big number for E820_MAX_ENTRIES. It's always at least 131, and increases by 3 for each additional CPU the kernel can run in parallel.

So the size that linux pre-allocates for the memory map is 131 * (64(base address size) + 64(length size) + 32(type size)) which means it uses about 20 KB - isn't it a very large amount?


And all the things that I should take into account when setting up bitmap from the memory map summed up and my questions about them if any(please correct me if I forgot something)
* The memory map should be fixed before usage - fix overlapping areas and alignment
* So as there are gaps in the memory map - all of the bitmap should be marked as reserved at the initialization
* You said that I should ignore the reserved memory areas, but they are in between the usable areas so I probably can't not include them in my bitmap, or should I have several bitmaps for each free area without including reserved regions?
* Another question related to previous is that if reserved areas are not tracked in the bitmap then how would I give them out to the driver when it is requesting MMIO and make sure that what he is asking for is not intersecting with other areas(like free or allocated) or that another driver would not request this area for MMIO(for example if it has a bug) or that this MMIO even exists?
* So if I use the ((highest_entry_start + highest_entry_size - 1) - lowest_entry_start) / 4096 to calculate the size of the bitmap then should I do this only between lowest free entry and highest free entry(and if the lowest one is reserved find next a bit higher which is free and the same with the highest, so the reserved regions like 3.5-4GB(ACPI and MMIO) area would not skyrocket my bitmap size when I have much less RAM. I mean that if bitmap is only from lowest free to highest free then if there even is something reserved higher it would not increase the bitmap size)? But here we return to the previous question - how then I track and give out MMIO areas?
* Also I wanted to ask how to allocate space for memory map(I think that pre-allocating 20 is a pretty BIG), bitmap and others while there is no allocator. Is my method of just pointing them to largest free area good or is there anything more safe and easy?

The UEFI memory map is always aligned, so you don't need to fix alignment. You could fix overlapping areas, but it might be better to refuse to boot if you find any.


131 * 20 bytes = about 2.5KB


You already mark everything reserved at the beginning, you don't need to mark it reserved again.

I don't think multiple bitmaps will have any benefit over a single bitmap. You can always come back later and change it once you can benchmark your PMM to see which one is better.


You should use a different structure to track non-memory physical address usage. Reserved ranges are not always MMIO, and MMIO is not always in reserved ranges.


That's the idea. (Divide by 8 for one bit per page.) Just about every PC has a reserved range near 4GB for the BIOS ROM, so if you include it your bitmap will be at least 128kB even when you have very small amounts of RAM.


Perhaps a linked list? MMIO is not allocated or freed very frequently, so it doesn't need to be fast, and it can't be fragmented like ordinary memory.


It works fine as long as it doesn't overlap a reserved area.

Forgot to translate bits to bytes)))


By reserved I mean everything that is not free, or MMIO could be in free?


Like a linked list that is separate from frames(because I can't write into the reserved ones)?

MMIO can't be in the free areas.


Yes. Once your bitmap is initialized, you'll be able to allocate memory to store the linked list.