PMM: Do I ever need to allocate a specific address?

[sebihepp]

Dear colleagues,

I wonder if I ever need to allocate a specific address in my physical memory manager?

If not, it would make implementation much easier, as I just keep a pointer to the first free page and every free page contains a pointer to the next free page, resulting in O(1) for allocating and freeing.

But if I ever need to allocate/free a specific address, this algorithm becomes unfeasible, because it would result in O(n) (traversing all pages until I have found the address)
For that case I thought of something like

Code: Select all

struct PhysicalMemoryChunk_t {
	size_t mSize;
	PhysicalMemoryChunk_t *mPrev;
	PhysicalMemoryChunk_t *mNext;
	PhysicalMemoryChunk_t *mParentByAddress;
	PhysicalMemoryChunk_t *mLeftByAddress;
	PhysicalMemoryChunk_t *mRightByAddress;
	PhysicalMemoryChunk_t *mParentBySize;
	PhysicalMemoryChunk_t *mLeftBySize;
	PhysicalMemoryChunk_t *mRightBySize;
};

this structure is at the beginning of each free physical page. The pointers are then used for double-linked-list-access, an AVL-tree by Address and an AVL-tree by Size. Implementation of this is much harder (I forgot avl-trees after not using them for more than 10 years and need to figure out/learn the implementation again) but makes access much faster at O(log n).

So, is stack-like for a physical page frame allocator really good enough? I heard that nearly all devices today are capable of uncontigous DMA. Is this correct? How is it in regard of Bochs and especially QEMU?
Did I made a thinking mistake in my alternate approach?

Best regards
Sebi

[nullplan]

There are cases where you need to allocate addresses satisfying certain conditions for reasons of DMA. For example, 32-bit EHCI devices place control structures in RAM, and can typically only talk to the first 4GB of physical address space, so you need to allocate memory in the low 4GB. Even the 64-bit EHCI devices only allow you to pick a specific 32-bit "page" to use, they don't let you allocate any 64-bit address.

Or if you want to start secondary CPUs with the SIPI method, you need to allocate at least a page in the low 1MB for that.

So no, you never need a specific address, but you might need more than just "the next free address".

[sebihepp]

Thanks @nullplan

Below 1M, Below 4G and the rest are all memory regions I know of, with special requirements.
In that case I could simply have 3 stack-likes - one for each region.

Currently I ignore multiple CPUs/Cores and plan to add them later. Or would you recommend directly plan with SMP in mind?

[nullplan]

Below 1M, Below 4G and the rest are all memory regions I know of, with special requirements.
In that case I could simply have 3 stack-likes - one for each region.

According to the Linux source, there are also certain EHCI devices that only support 31-bit addresses. I would wager such silliness can occur with other devices as well. So this region approach might not be flexible enough. The gold standard is of course 16-bit ISA DMA: Allocate a contiguous buffer that lives in the low 24 MB and does not cross a 64kB boundary. That is probably the most complicated physical allocation you will need to support.

Currently I ignore multiple CPUs/Cores and plan to add them later. Or would you recommend directly plan with SMP in mind?

Some changes are hard to retrofit. If you started out writing your code with the idea that "cli" is the same as taking a global lock, then changing that decision later is hard. In the specific case of the PMM, I will tell you that you should write it to cope with the requirements your device drivers will have. More generally, I will tell you that writing your code to be SMP-ready, just starting with the special case of only supporting a single CPU, makes your code easier to actually parallelize. Always assume there are other threads accessing your global data, for example. This also reduces the amount of code that has to run with interrupts disabled.

[zaval]

But if I ever need to allocate/free a specific address, this algorithm becomes unfeasible, because it would result in O(n) (traversing all pages until I have found the address)

How about a list, every entry of which describes a page? The index of such an entry becomes a page frame number, giving you constant time search for a specific address. Also, searches through avl tree (or any other binary tree), describing ranges is not O(n) aren't they?

[rdos]

Using bitmaps instead of lists solves the region issues a lot better. Additionally, there are devices that need more than one 4k page of continious physical memory, and you also might want to allocate 2M pages since they are more efficient with one less paging level and requires less entries in the TLB.

As for ISA DMA, I would simply skip that. It's not necessary to support.

Another definite issue with lists is that all physical memory must be mapped. Impossible for a 32-bit kernel, and unwanted for a 64-bit.

[sebihepp]

Another definite issue with lists is that all physical memory must be mapped. Impossible for a 32-bit kernel, and unwanted for a 64-bit

Ist this really such a big issue, to map all physical memory in 64bit? The virtual address space is big enough. i could also get along with only one Page that i always map wherever i need it.

For a Bitmap i need to know the highest physical address and then allocate physical Pages without yet having a physical Page frame allocator. And it uses Up much space. In case of a list of only free pages, it uses much less space.