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.

ngx wrote:In my memory map all entries are within what I have installed in my emulator(so they all fit in 256mb), but the last entry is at address after 4 billion(which means that it is at 4GB), so should I count the last entry anyway, by the way it is marked as reserved in the memory map?

You should ignore reserved entries when initializing the bitmap.

ngx wrote:The bitmap size should be calculated not by the sum sizes of all entries in memmap divided by 4096. But instead the bitmap size should be determined by the end(base+size-1) of highest entry - start of lowest entry and then divided by 4096, am I right?

Yes.

ngx wrote:If the answer to the previous question is yes, then how do I know that it is really the size of RAM if memory map can have gaps as you said?

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

ngx wrote:You said that the bitmap should be for more entries then installed RAM if there are some free memory at the start and in the end(beyond range of installed RAM), but if there is only reserved RAM that is beyond the installed RAM, then should the bitmap still be that big?

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

ngx wrote:If I should ignore RAM beyond what I have installed that is reserved, then how should I calculate amount of installed RAM?

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

rdos wrote:After all, PAE requires twice as much memory for the paging structure, and if no physical address is above 4G, PAE paging just wastes memory and so 32-bit paging is a better choice.

You also need PAE to use the NX bit.

...

ngx wrote: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?

Right.

ngx wrote: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?

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.

ngx wrote: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 ?

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

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

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.

...

ngx wrote: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?

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

ngx wrote: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?

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

ngx wrote: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?

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.

...

ngx wrote: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)?

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

isaiah0311 wrote:And also, how is it possible there are overlapping areas of different types?

Firmware isn't very smart.

isaiah0311 wrote: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)

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.

...

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

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.

ngx wrote: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?

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.

...

ngx wrote:* The memory map should be fixed before usage - fix overlapping areas and alignment

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.

ngx wrote: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?

131 * 20 bytes = about 2.5KB

ngx wrote:* 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?

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.

ngx wrote:* 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?

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.

ngx wrote:* 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)?

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.

ngx wrote:But here we return to the previous question - how then I track and give out MMIO areas?

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.

ngx wrote: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?

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

...

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

MMIO can't be in the free areas.

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

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