Kernel dynamic structs

[TheLittleWho]

Hello,

I have a misconception. I was thinking of implementing the buddy algorithm for physical memory allocator, but in theory the internal structures for buddy algorithm have dynamic size. E. g. for 1MiB you can have:
- 512KiB 512KiB
- 32KiB 32KiB 64KiB 128KiB 256KiB 256KiB 128KiB 128KiB
In the first case the list will have two nodes, while in the second case the list will have 8 nodes. This is just an example, let's say for 2 nodes we need of 4KiB of memory (4KiB is the minimum for physical page size). When I need a new physical page (also virtual page), how can I map the new virtual page in all processes? This is not the only example, the same situation is for open files. When a process open a file, all processes need to know that a new file have been opened.
Briefly, how do I update the virtual memory of the kernel in all processes when it is changed in a process?

I have 2 solutions, but it seems to me primitive.
1. I have a separate process for kernel and when someone wants to allocate memory or to open a file, he send a message (IPC) to the kernel process and he wait for a response.
2. For the physical memory allocator I calculate the maximum memory I need and reserve it. For open files, I reserve memory for x files and can be maximum x open files at the same time. But, for me, that is not a solution, because if x is 1000, I have reserved memory for 1000 open files but at this point only 5 files are open. So it will be a waste of memory.

I want a better solution. I'm sure there's something better.

[Korona]

Yes, the buddy structures have a variable size. However, you can allocate them once at boot time and then you never need to allocate more buddy structs (disregarding memory hotplug).

The common solution to your second problem is that the kernel shares its highest level page struct entries with all processes. For example, if you're in 32-bit non-PAE mode, the kernel shares its PDEs (lets say PDEs with index 768-1023 for a 1 GiB kernel space) with all processes. If you're in 64-bit mode, the kernel shares its PML4 entries (usualy entries 256-511 for the whole negative address space).

You should also consider mapping all (or at least most of) the physical memory into the kernel space, so that you can change paging structures without explicitly mapping them first.

[TheLittleWho]

I understand the solution. I do not know how I did not think about it. Thank you very much.

[TheLittleWho]

But I have a curiosity. You may have a process with PAE paging and another process with IA32 paging?
Another question about TLB: I map 768-1023 PDE in each PD, but when I map or unmap a page in PT should I invalidate the TLB? As far as I know the invalidation of the TLB for unmapping a page it's a security method, but when I map a new page in PT should I invalidate the TLB for that page in each logical core or if I map a page in core1 and is immediately accessed from core2 everything will be ok or I get page fault? I read somewhere that is recommended to invalidate TLD when map a new page.

[Korona]

PAE is invisible to user space, it only affects the physical addresses that can be mapped. So you'll usually either use PAE in all processes or not at all.

Yes, after you unmap a page you have to invalidate it on all CPUs. OSes generally use IPIs to inform other processes that pages have been unmapped. Invalidation is not a security measure but it is required for correctness: Imagine the following situation:

• Threads S and T both share the same address space but run on different CPUs.
• Page P is mapped at address A.
• Thread S unmaps P and invalidates only locally. Page P is freed.
• The page P is reallocated and mapped into a second process.
• T accesses address A. Because its TLB still contains P, thread T can now manipulate a different process' address space!

The correct solution is to unmap the page immediately but only free it after all CPUs have invalidated it.

[JAAman]

as for mapping a new page:

for most Intel (and AMD, iirc) CPUs, you don't need to invalidate the TLB when mapping a previously not-present page, because Intel CPUs do not cache not-present pages in the TLBs in the first place -- however there are some other brands of CPUs (cyrix?) that do cache not-present pages in the TLBs (for those CPUs, failing to invalidate when mapping a page can result in #PF)

[SukantPal]

The buddy allocator uses a fixed-set of structs for fixed-set of memory. You will need to allocate this data dynamically before setting up your physical memory allocator (PMA). If you use multiboot, you should scan the memory map to allocate the structs in physical memory in a continuous range. Now, you should map the physical memory range to page-tables of kernel memory. For now, all this will be enough for non-hot-plug implementation.

Make sure - You try to allocate the PMA data after the 16th MB to save DMA memory.