Page Frame Allocation

[kzinti]

I agree, linking all your pages would be even slower. I think some kind of partial + lazy or delayed initialization is the way to go for scalability.

[Octocontrabass]

I have finally implemented the Physical Memory Allocator, am I correct with how I have implemented the bitmap algorithm, are there any serious bugs?

I found a bug. You're using the total size of all the memory map entries instead of the highest usable address to determine the bitmap size. There are gaps in the memory map, so the total size is less than the highest usable address.

[rpio]

I have finally implemented the Physical Memory Allocator, am I correct with how I have implemented the bitmap algorithm, are there any serious bugs?

I found a bug. You're using the total size of all the memory map entries instead of the highest usable address to determine the bitmap size. There are gaps in the memory map, so the total size is less than the highest usable address.

I have also thought about it - there are entries in the memory that are at 3 GB when I only have 200mb(QEMU), but then if I make a map for 3GB won’t it just waste a lot of space - or is it required?

So the end should be - “ last entry address + last entry size - 1”

[Octocontrabass]

I have also thought about it - there are entries in the memory that are at 3 GB when I only have 200mb(QEMU), but then if I make a map for 3GB won’t it just waste a lot of space - or is it required?

Your bitmap only needs to include usable memory. If those entries are not usable memory, you can ignore them.

So the end should be - “ last entry address + last entry size - 1”

Don't assume the memory map will be sorted. SeaBIOS (QEMU) is nice enough to sort the memory map, but not every BIOS will do that.

[rpio]

I have also thought about it - there are entries in the memory that are at 3 GB when I only have 200mb(QEMU), but then if I make a map for 3GB won’t it just waste a lot of space - or is it required?

Your bitmap only needs to include usable memory. If those entries are not usable memory, you can ignore them.

So the end should be - “ last entry address + last entry size - 1”

Don't assume the memory map will be sorted. SeaBIOS (QEMU) is nice enough to sort the memory map, but not every BIOS will do that.

So if I only have 256 mb, then I should ignore mmap entries beyond that?
How do I calculate the RAM size and end if memory map has gaps?
If you say mmap is not always sorted, then how do I determine start(and end)of RAM?

[Octocontrabass]

So if I only have 256 mb, then I should ignore mmap entries beyond that?

You should ignore entries that are not usable memory.

How do I calculate the RAM size if memory map has gaps?

Add up all of the usable memory. This still doesn't tell you how big your bitmap needs to be, since there can be gaps in the usable memory.

If you say mmap is not always sorted, then how do I determine start of RAM?

Look for the entry for usable memory with the lowest start address.

[rpio]

So if I only have 256 mb, then I should ignore mmap entries beyond that?

You should ignore entries that are not usable memory.

How do I calculate the RAM size if memory map has gaps?

Add up all of the usable memory. This still doesn't tell you how big your bitmap needs to be, since there can be gaps in the usable memory.

If you say mmap is not always sorted, then how do I determine start of RAM?

Look for the entry for usable memory with the lowest start address.

How should I know if entry is not usable RAM to ignore it?
If you say that there are gaps in usable memory, then how do i determine bitmap size?
So to find end of RAM I should find the entry with highest memory address and find it’s end(base + size - 1)?
And to find the start of RAM i just find lowest address in memory map?

[Octocontrabass]

How should I know if entry is not usable RAM to ignore it?

Each entry includes type information, doesn't it?

If you say that there are gaps in usable memory, then how do i determine bitmap size?

Take the difference between the highest usable page and the lowest usable page. That's how many pages your bitmap needs to track. Don't forget to round up to the nearest whole byte.

So to find end of RAM I should find the entry with highest memory address and find it’s end(base + size - 1)?
And to find the start of RAM i just find lowest address in memory map?

If those entries are for usable memory, yes.

[thewrongchristian]

I think bitmap initialization will be much faster than linking pages. For linking pages, you will need one write per 4k entry. For a bitmap, you can init 32 4k entries with one 32-bit write, and 64 with a 64-bit write.

Bitmaps will be much more cache friendly to initialize as well.

But. Who cares? Initialization is a one time cost, saving a few seconds even once a day won't make a bad data structure worth keeping, if it costs more than that on an ongoing basis to maintain. And initialization of a free list is trivially concurrent, and can happen while other parts of the system initialize.

FWIW, I use a bitmap as well. But that's because it was quick and simple to set up. I am aware that page allocation will be O(n). But my n is small, and when I get serious about performance, I'll measure bottlenecks and address them as necessary, but I am tempted to replace my bitmap with a free list or buddy based system. The former being as easy to write as a bitmap system, and O(1) to allocate and free (assuming single page allocations), the latter being more scalable when multi-page allocations are taken into consideration.

[rdos]

FWIW, I use a bitmap as well. But that's because it was quick and simple to set up. I am aware that page allocation will be O(n). But my n is small, and when I get serious about performance, I'll measure bottlenecks and address them as necessary, but I am tempted to replace my bitmap with a free list or buddy based system. The former being as easy to write as a bitmap system, and O(1) to allocate and free (assuming single page allocations), the latter being more scalable when multi-page allocations are taken into consideration.

There are possible optimizations with the bitmap. By loading a 32-bit value from the bitmap I can quickly check if it will possible to allocate something from these 32 entries, and if not, then I advance the position to the next dword. I save the current position. I think in practise, this will make it more like O(1). Free is always O(1), just like with a list, but using bitmap can also detect double frees which will corrupt a list.

[rpio]

How should I know if entry is not usable RAM to ignore it?

Each entry includes type information, doesn't it?

If you say that there are gaps in usable memory, then how do i determine bitmap size?

Take the difference between the highest usable page and the lowest usable page. That's how many pages your bitmap needs to track. Don't forget to round up to the nearest whole byte.

So to find end of RAM I should find the entry with highest memory address and find it’s end(base + size - 1)?
And to find the start of RAM i just find lowest address in memory map?

If those entries are for usable memory, yes.

Oh, we were probably talking about different things, so by usable you mean = free RAM, but my bitmap also includes the reserved(what you called unusable) RAM, so what is wrong with dividing size of all fields added by 4096 to find size of bitmap because it got me the right number I think - I gave my emulator 200 mb and the total RAM with my calculation was 211m, I don't know how it is possible but it is right I think, so what is the problem?

[Octocontrabass]

The offset into the bitmap indicates the address of memory, so your bitmap needs to be big enough to cover all addresses that can be free memory. The amount of memory is irrelevant. If you have one page of usable memory at address 0 and one page of usable memory at address 0x10000, your bitmap needs to cover all addresses between those as well.

[linguofreak]

So if I only have 256 mb, then I should ignore mmap entries beyond that?

No, because you might have an arrangement where the computer has half of its RAM at the bottom of the physical address space, and half of its RAM at the top.

For any given address:

If it's in the mmap and marked usable, then there is usable RAM there.
If it's in the mmap and marked unusable, then there is something there*, but it's not usable RAM.
If it's not in the mmap, then there's nothing there.

*Actually, I'm not sure if it's valid for a BIOS to list an address range as unusable if there's nothing there. If it is, then in principle, you could have a machine that had its whole address space catalogued in the memory map. In general though, the memory map will only tell you where usable RAM and things with addresses that aren't usable RAM are.

[rpio]

The offset into the bitmap indicates the address of memory, so your bitmap needs to be big enough to cover all addresses that can be free memory. The amount of memory is irrelevant. If you have one page of usable memory at address 0 and one page of usable memory at address 0x10000, your bitmap needs to cover all addresses between those as well.

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?

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?

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?

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?

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

[rdos]

I don't think there is any reason to assume that the lower limit is not zero, and so only the highest possible address is interesting. For a 32-bit kernel, the highest possible physical address also determines if 32-bit paging or PAE paging should be used. 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.

There is also a need to group memory in different categories, at least below and above 4G, as some MMIO devices only can handle 32-bit addresses.