OSDev.org

Hi, I'm having a serious problem in my paging code, the VMMMap function (which maps a virtual address to a physical) sees if the page table is already allocated, if it is, map it (set present bit, user bit , rw bit and the upper 20 bits), but if it is not, it calls MemoryAlignedAlloc to allocate a new page table, MemoryAlignedAlloc calls HeapIncrement, but HeapIncrement allocates a physical address (using PMMAllocFrame) and calls VMMMap, this causes is causing an infinite loop.

Separate the concept of physical allocation and virtual allocation. Physical allocation allocates what you could call 'real' memory, virtual allocation asks for physical allocation then maps that real memory into a process at a 'fake' address using a page directory.

Virtual memory is for processes only, so that apps have a different view of the system's memory layout. This is one aspect of memory protection, hence 'protected mode'.

Long story short, physical allocation should never rely on virtual allocation, because virtual allocation relies on physical allocation to do its own job first.

On a side note, I just noticed your project's name. Ahhh.... nah, you know what? Go ahead, it isn't as if MS have used that codename in 20+ years anyway (and it was never intended as the final name to begin with). I mean really, if you find a perfectly good OS name just lying around untouched where someone threw it away, why not pick it up? Reduce, reuse, recycle...

So, do I have to use a temporary page table to map the allocated physical address (of the new page table)?

If you are using recursive table mapping or similar technique with pre-reserved virtual address space (not to be confused with virtual or physical memory), then you do not have to. The location of PTs can be calculated using simple pointer arithmetic.

You should get the new page frame from your PMM. Then, assuming 32-bit paging, just put the physical address (and appropriate flags) in PD. The location of the PT now have the physical memory backing it, and you may proceed further to set it up.

The Github repo you are linking us to, is useless. It is supposed to contain source code (not compiled binaries), so we could take a look and give you more informed answers.

Edit: I see there was some code, but then you decided to go closed source.

No. Physical memory is allocated based on the memory map you get at boot time. If you have identity mapped your kernel, the physical memory manager doesn't care at all about paging.

All a physical memory manager does is mark blocks of data used or free and finds the next block to use on request. Nothing to do with paging if your kernel is identity mapped.

Your virtual memory manager should ask for 'real' memory from the physical manager, then the VMM deals with page directories/tables to map the 'real' memory to a 'fake' (virtual) address.

Velko made a good point that virtual space management and virtual memory management mean different things, but I may abuse the terminology here and there.

First, let's discuss what constitutes an allocation. Does it mean to provide actual access to to the physical frame or just to manage its allocation state? In user mode, the heap always returns a mapped address. But in kernel mode, the two concerns are usually kept separate. Physical frame allocation by default means to mark it as busy and nothing more. Let's say that you use a bitmap for tracking the state of physical memory. To serve an allocation means to find a cleared bit, to set it, and to return the index. Since the bitmap is a global entity of fixed size, it can be allocated at boot time and kept mapped in all processes, from process creation to process termination. No dynamic mapping is necessary.

If, like linux, you map the entire memory in one contiguous virtual address range, then the bit position returned by the physical allocator can be used to derive the page address in virtual memory. For kernel space servings, this concludes the entire allocation process. You wont need to map anything anywhere.

If you need to serve user space memory, or don't use the linux approach, you also need to find an address space range that is currently free. This involves other structures, such as prefix trees or self-balancing trees. Once you have such an address range, you need to map the physical frame you have allocated into a page somewhere in that range. If you use recursive (aka self-mapping) page tables, a technique to which Velko referred in his answer, you already have direct access to every page table for the process. This access is not dynamically controlled. It becomes automatically available at process creation and automatically reflects changes to the tables (assuming that you invalidate the TLB when making changes to the page directory), and doesn't cost additional table space in physical memory. But it doesn't guarantee that you will not end up in a location for which no page table is currently present. You may still have to allocate one more frame for creating the missing page table. The good news is that the physical allocator will not cause reentry into the mapping code, because it does not concern itself with providing access to the frames. Once the frame for the page table is allocated, the index returned from the physical allocator can be used to fill in the address in the page directory entry, thus making the table visible. You get to a point where a table entry has to be filled in with the address originally retrieved to serve the initial allocation, which will conclude the process.

If you don't use recursive page tables, to bottom out the recursion, you need to keep a few page tables mapped at all times, and dedicate them to bouncing other page tables into visibility. This may save some address space, but is not very performant, hence the relative popularity of the self-mapping approach.

Physical allocators don't have to use bitmaps, and neither does Linux nor Windows. They use free lists, which maintain one list link for each physical frame. The links are actually embedded in a slightly bigger record that also holds other frame related information, and the records are organized in array that is similarly allocated at boot and kept mapped at all times in every process. When a frame is served, the link is detached from the respective free list and can temporarily be used by the requestor. The owner gets to use the link however it chooses until they free the page. OSes usually keep there file caching state/pointer, sub-page allocation state/pointer, or page replacement queue links.

P.S. You can try to google self-mapping page tables or recursive page tables. This is not really an algorithm, but just a way to link the page tables back to themselves in a way that makes them visible in the space they describe. (Edit: To "themselves" is misspoken here, but its better that you read up a really thorough explanation.)