Re: Page Frame Allocation
Posted: Thu Mar 11, 2021 1:10 pm
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.
The Place to Start for Operating System Developers
http://f.osdev.org/
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.ngx wrote: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 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?Octocontrabass wrote: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.ngx wrote:I have finally implemented the Physical Memory Allocator, am I correct with how I have implemented the bitmap algorithm, are there any serious bugs?
Your bitmap only needs to include usable memory. If those entries are not usable memory, you can ignore them.ngx wrote: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?
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.ngx wrote:So the end should be - “ last entry address + last entry size - 1”
So if I only have 256 mb, then I should ignore mmap entries beyond that?Octocontrabass wrote:Your bitmap only needs to include usable memory. If those entries are not usable memory, you can ignore them.ngx wrote: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?
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.ngx wrote:So the end should be - “ last entry address + last entry size - 1”
You should ignore entries that are not usable memory.ngx wrote:So if I only have 256 mb, then I should ignore mmap entries beyond that?
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.ngx wrote:How do I calculate the RAM size if memory map has gaps?
Look for the entry for usable memory with the lowest start address.ngx wrote:If you say mmap is not always sorted, then how do I determine start of RAM?
How should I know if entry is not usable RAM to ignore it?Octocontrabass wrote:You should ignore entries that are not usable memory.ngx wrote:So if I only have 256 mb, then I should ignore mmap entries beyond that?
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.ngx wrote:How do I calculate the RAM size if memory map has gaps?
Look for the entry for usable memory with the lowest start address.ngx wrote:If you say mmap is not always sorted, then how do I determine start of RAM?
Each entry includes type information, doesn't it?ngx wrote:How should I know if entry is not usable RAM to ignore it?
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.ngx wrote:If you say that there are gaps in usable memory, then how do i determine bitmap size?
If those entries are for usable memory, yes.ngx wrote: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?
Bitmaps will be much more cache friendly to initialize as well.rdos wrote: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.
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.thewrongchristian wrote: 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.
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 wrote:Each entry includes type information, doesn't it?ngx wrote:How should I know if entry is not usable RAM to ignore it?
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.ngx wrote:If you say that there are gaps in usable memory, then how do i determine bitmap size?
If those entries are for usable memory, yes.ngx wrote: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?
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.ngx wrote:Octocontrabass wrote: So if I only have 256 mb, then I should ignore mmap entries beyond that?
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?Octocontrabass wrote: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.