OSDev.org

Thanks for your answear, I would also like to ask:
1. How do I allocate several frames one after another and return them as a chunk(for example for 1GB Huge pages on x86)?
2. What if the drivers have MMIO in areas that are marked as free and some frame is allocated there before the driver says that this space should be reserved. Or is it impossible for MMIO to be located in free memory areas in memory map(what about the bootloader framebuffers?)?

Look for enough contiguous frames with appropriate alignment to satisfy the allocation, then allocate all of them at once. You only need to return the address of the first frame, since they're contiguous. Freeing will require the caller to inform you how many frames there are.


MMIO is not memory, so it will never be listed as free memory in the memory map. The framebuffer is MMIO.

How should I determine the size of the bitmap because base address of last entry + it's size is bigger then sum of sizes all entries, so which one of these numbers should I use to determine the bitmap size - end of last area in memmap or size of all size?

The offset within the bitmap indicates the address of the frame, so your bitmap needs to be big enough to cover all addresses that contain memory.

The basic operations are pretty easy to implement lock free:

Allocate a single page:


Free a single page:


Allocate 32 pages:


Free 32 pages:

This bitmap talk got me thinking...

If 4 GB fits in 128 KB, then the maximum amount of memory a PC can address - 64 TB - would need a 2 GB bitmap. That would be quite slow to initialize.

I suppose there aren't that many PCs around with 64 TB of RAM, but still... This doesn't seem to scale. I suppose one can incrementally build the bitmap as needed by walking the memory map provided by the firmware (and not do everything up-front).

How did you come up with 64TiB? The architectural limit is 4096TiB, which would need a 128GiB bitmap. (That ought to make 2GiB look pretty fast!)


The first "PC" with 64TiB of RAM will be a server with many CPUs and hundreds of cores (if it doesn't already exist - I'm not sure if it does). You'll have bigger scaling problems than just initializing the bitmap.

Consumer hardware with 64TiB of RAM is far enough off that I'm not sure it's worth worrying about right now. Check back in a decade or so.

It is my understanding that current x86 processors can only address 64 TB of physical memory. I understand that more bits are being added and that we could one day reach 4096 TB. But we are not there yet.


Indeed.

I believe there are such issues with my PC with only 128 GB of physical memory. It boots considerably slower than other PCs, and it's BIOS that is slower at initializing things (probably memory).

A few decades ago, I think many BIOSes actually tested most of the physical memory at boot up, but this no longer is the case, however, with 100s of GB of memory initialization seems to be slow even without testing all memory.

And it would almost certainly have some degree of NUMA partitioning, so you can easily have each CPU setting up its own bitmaps in parallel. Or, you could initialize, say, the first 10% to get the machine up and running, and spin off a kernel thread to set up the rest later in the boot process.

The machine you describe does exist in the server space. The highest end IBM p-series supports up to 64TB of RAM and 192 cores.

I wouldn't worry too much about how much memory you need for free page bitmaps. There's just a certain amount of overhead a kernel has to consume to be able to do anything. At least the need is predictably linear. If you need X% of your memory to store free page bitmaps, you'll also need X% with 100x the RAM. You're sure to consume more memory storing page maps anyway.

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

It's not the amount of memory consumed by the bitmap that is of concern, it's how much time it is going to take to initialize it (and by extension managing it).

Managing your memory using a bitmap tends to produce algorithms of linear complexity, and that is not going to scale well.

Whatever scheme you use is going to have to be initialized.

But not all schemes will have linear initialization time.

I am happy with the proposed solution above for bitmaps: initialize a subset (say the first 4GB) to get the kernel going and when you have SMP up and running, spawn tasks to finish initializing the bitmaps.

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.