OSDev.org

Posted: **Mon Jun 24, 2013 10:27 am**

I was banging my head over this problem forever, and I was convinced it was an implementation problem in my mapping code.
BUT. It was a conceptual design flaw. I'm sure all the smart people here have solved this problem already.

Basically, this is how the mapping code works:

Code: Select all

void MapAddr(uint64_t v, uint64_t p)
{
        ...
        if(ParentStructure->Entry[Index1]_Does_not_exist())
                ParentStructure->Entry[Index1] = (Entry*)(AllocateMappedPage() | FLAGS);

        ...
}

So this pseudo-code might look all fine and dandy (forgive me if I left out some details). However, the issue comes where AllocateMappedPage() returns an *unmapped* physical address that is beyond what is currently mapped.

No problem right? Just map it! So it calls MapAddr(returning_address, returning_address)... Which realises that the Page Structure for the virtual address (return_address) doesn't exist, therefore it calls AllocateMappedPage()...

See the problem?

Right now I've solved it by dedicating 1MB of physical and virtual address space right above my kernel (because in my naïve PMM implementation, if you want a mapped address it's gonna be identity mapped), where the VMM can get its memory that is guaranteed to be mapped already.

This will, of course, come back to bite me in my @$$; it is totally inelegant, and will eventually deplete the 1MB set aside.

Thoughts?

Posted: **Mon Jun 24, 2013 11:04 am**

I also keep a number of reserved unmapped pages for fixed purposes, and keep locks on them per address space. Each of them serves as a fixed point to access a page not mapped in the current address space - page directories and tables of a different address space, but also for memory allocation structures and the last task to have used the FPU on the current core. When needed, I get the lock, update the page table to map the required memory, perform the updates, then unlock again. That way a fixed control path exists to solve any chicken-and-egg problems that might arise otherwise.

Posted: **Mon Jun 24, 2013 11:07 am**

I do it this way:

VMM don't care much on page structure, it just manage the mapping logistic.
When VMM tries to write to page directory that was not present, it will be handled by demand paging.

In reality this will be a bit more complex to detect #PF from demand paging and actual protection fault.

Posted: **Tue Jun 25, 2013 1:56 am**

Combuster wrote:I also keep a number of reserved unmapped pages for fixed purposes, and keep locks on them per address space. Each of them serves as a fixed point to access a page not mapped in the current address space - page directories and tables of a different address space, but also for memory allocation structures and the last task to have used the FPU on the current core. When needed, I get the lock, update the page table to map the required memory, perform the updates, then unlock again. That way a fixed control path exists to solve any chicken-and-egg problems that might arise otherwise.

So essentially there's a reserved space from which the VMM gets space to make the page structures? The problem is that it's not infinite... and can't be freed once used (that would trigger a page fault or something, or waste more memory)...

bluemoon wrote:
VMM don't care much on page structure, it just manage the mapping logistic.
When VMM tries to write to page directory that was not present, it will be handled by demand paging.

In reality this will be a bit more complex to detect #PF from demand paging and actual protection fault.

If the not-present page is handled by demand paging; that would work fine on most occasions, but what if the returned memory is in a page that is not present? (Such as a 2MB page-table border)

That would involve creating it, which would send another call to the VMM...

Posted: **Tue Jun 25, 2013 2:29 am**

requimrar wrote:So essentially there's a reserved space from which the VMM gets space to make the page structures? The problem is that it's not infinite... and can't be freed once used

There is never physical memory reserved for VMM purposes, only virtual. You don't need to keep page structures mapped when they're not being read or written by your own code. The processor walks them in the physical address space anyway. Therefore you can evict them from virtual memory and not require infinite space, just constant space.

Posted: **Tue Jun 25, 2013 3:15 am**

I use a variation of lazy allocation for paging structures along with recursive mapping. Basically you can translate the virtual faulting address to which level of the page table you need to place an entry in. Recursive mapping means you give up some virtual address space, but also have the guarantee that all your paging structures are always accessible without having to unmap/remap.

Posted: **Tue Jun 25, 2013 5:07 am**

requimrar wrote:If the not-present page is handled by demand paging; that would work fine on most occasions, but what if the returned memory is in a page that is not present? (Such as a 2MB page-table border)

I'm not sure what you meant by returned memory not present.
#PF handler may check if the fault address is on-demand allocation (by some bit on the entry), if access is granted, it invoke PMM to allocate physical memory, and then map this physical address by putting it onto the page structure.

This may also be extended to support different page sizes, you designate some sort of mechanism to detect the size (eg. by flags on page entry, or by address range)

Posted: **Wed Jun 26, 2013 8:07 am**

bluemoon wrote:... it invoke PMM to allocate physical memory, and then map this physical address by putting it onto the page structure...

This is the crux of the problem I'm facing now: What if the PMM returns an address whose virtual page structures (appropriate PTs, PDPTs etc) have not been created? This is not an unlikely scenario, assuming memory would be mapped 1:1.

Putting it onto the page structure

Exactly, what if the 'page structure' (be it Page Table, Page Directory or whatever) doesn't exist? It needs to be created, and that requires memory of some description. That will result in a call to the PMM to allocate more memory. That will very likely result in an allocated address that is maybe 0x1000 higher than the previous allocation, which, of course, still isn't mapped anywhere.

Stack overflow?
Again, this might be a simple problem for some but to me it's quite a tough nut to crack.

Thanks.

Posted: **Wed Jun 26, 2013 8:20 am**

requimrar wrote:What if the PMM returns an address whose virtual page structures (appropriate PTs, PDPTs etc) have not been created?

Do we have different terminology here?
PMM, physical memory manager, only return physical address, which is a number, the number is not automatically mapped (LMM does this however).

A very simple PMM may work like this:

Code: Select all

phyaddr_t PMM_alloc() {
  return pool.pop();
}
void PMM_free(phyadd_t addr) {
  pool.push(addr);
}

requimrar wrote: Exactly, what if the 'page structure' (be it Page Table, Page Directory or whatever) doesn't exist? It needs to be created, and that requires memory of some description. That will result in a call to the PMM to allocate more memory.

For my design I just access it anyway and generate another #PF and allocate a page there. It is however also possible to actively invoke PMM_alloc and put the physical address on the page map. I don't see any issue either ways.

Posted: **Thu Jun 27, 2013 12:03 am**

bluemoon wrote:Do we have different terminology here?
PMM, physical memory manager, only return physical address, which is a number, the number is not automatically mapped (LMM does this however).

No, I know what a PMM does; it returns a free address in the physical address space without mapping it anywhere.

bluemoon wrote:... allocate a page there. It is however also possible to actively invoke PMM_alloc and put the physical address on the page map

Exactly this! The problem is that, *what if* the PMM returns an address, that in the Virtual Address Space, doesn't have a page table?
Here's an example:

Code: Select all

current_addr = 0x00200000;
AllocPage()
{
        current_addr += 0x1000;
        return current_addr;
}

MapPage(uint64 virtual, uint64 physical)
{
        ...
        if(!PageDirectory[PTIndex])
        {
                // Create new page table
                uint64 addr = AllocPage();
                // Assume here AllocPage() returns 2MB + 4K (0x00201000)
                MapPage(addr, addr);

                // Never gets here!
                PageDirectory[PTIndex] = (addr & 0xFFFFF000) | 0x3;
        }
}

Explanation:
Let's assume AllocPage() is an over-simplistic placement allocator.
MapPage() maps the physical address to the virtual address.

In this example, current_addr is at 2MB. For x64 paging at least, a PageTable can address 512 * 4K of memory = 2MB. Assuming during bootstrap to long mode, only the first 2MB is identity mapped. Meaning, no other PageTables/PageDirectories are created.

In the above, a call to MapPage(0x00300000, 0x00300000), will result in control entering the IF statement, because the PageTable addressing 0x00200000 -> 0x00400000 does not exist.
Therefore, MapPage() calls AllocPage(), to return a physical address to place the new PageTable in. In the above, it will return 0x00201000.

------
In your demand-paging example, you would simply write put this physical address in the PageDirectory anyway. When the time comes (later in the MapPage() function), to put the PageAddress into the PageTable, you cannot; you say you'd write to it anyway, generating a #PF which would map the faulting address somewhere and IRET.

Where would it map to? Assuming everything below 2MB in the VirtualAddressSpace is already mapped. That is, you have no existing PageStructures in which to place the faulting address... A call to MapPage() would therefore call AllocPage(), after which calling MapPage(), that calls AllocPage()...
------

Without demand-paging, much of what is described above would still happen. AllocPage() returns an address whose PageStructures are not created (say 0x00201000, assuming only 2MB was mapped at boot-time). When MapPage() is called with this address, the PageStructure addressing 2MB+4K still doesn't exist, which results in another call to MapPage()...

-- Thanks

Posted: **Thu Jun 27, 2013 4:33 am**

Did you read about recursive paging? for that method you don't need to manually map the paging structures and still able to access them directly.

Take a simple example, which is part of my previous kernel, using recursive paging and demand paging:

Code: Select all

int MMU_mark(uintptr_t addr, MMU_PADDR paddr, unsigned int flag) {
    // index: entry of page structure, 0~512
    // pml4, pdpt, pd, pt: direct accessible address for page structure
    uint64_t pml4_index = MMU_PML4_INDEX(addr);
    uint64_t pdpt_index = MMU_PDPT_INDEX(addr);
    uint64_t pd_index   = MMU_PD_INDEX(addr);
    uint64_t pt_index   = MMU_PT_INDEX(addr);
    uint64_t* pml4 = MMU_PML4(addr);
    uint64_t* pdpt = MMU_PDPT(addr);
    uint64_t* pd   = MMU_PD  (addr);
    uint64_t* pt   = MMU_PT  (addr);
   int changed = 0;

    // Set on-demand allocation if page structure not present yet.    
    if ( (pml4[pml4_index] & (MMU_PROT_PRESENT|MMU_K_ONDEMAND)) == 0 ) {
        pml4[pml4_index] = MMU_K_ONDEMAND|MMU_PROT_RW|MMU_PROT_USER;
        changed = 1;
    }
    if ( (pdpt[pdpt_index] & (MMU_PROT_PRESENT|MMU_K_ONDEMAND) ) == 0 ) {
        pdpt[pdpt_index] = MMU_K_ONDEMAND|MMU_PROT_RW|MMU_PROT_USER;
        changed = 1;
    }
    if ( (pd[pd_index] & (MMU_PROT_PRESENT|MMU_K_ONDEMAND) ) == 0 ) {
        pd[pd_index] = MMU_K_ONDEMAND|MMU_PROT_RW|MMU_PROT_USER;
        changed = 1;
    }
    if ( (pt[pt_index] & MMU_PROT_PRESENT ) == 0 ) {
        if ( (flag & MMU_MMAP_MAPPHY ) == 0 ) {
             // Map address provided by caller
             pt[pt_index] = (uint64_t) (MMU_K_ONDEMAND | (flag & MMU_PROT_MASK));
        } else {
             // Allocate on demand
            pt[pt_index] = (uint64_t) (paddr | (flag & MMU_PROT_MASK) | MMU_PROT_PRESENT);
        }
        changed = 1;
    } else {
        if ( (flag & MMU_MMAP_MAPPHY ) == 0 ) {
            // just change flags
            pt[pt_index] = (pt[pt_index] & (~(uint64_t)MMU_PROT_MASK)) | ((uint64_t)flag & MMU_PROT_MASK) | MMU_PROT_PRESENT;
            changed = 1;
        } else {
            kprintf ("    MMU : map fail, addr:%X paddr:%X flag=%d entry:%X\n", addr, paddr, flag, pt[pt_index]);
            return -1;
        }
    }

   if ( changed ) _INVLPG(addr);
   return 0;
}


void INT_0E(long code, uint64_t addr, unsigned long ip) {
    uint64_t  page, prot;
    uint64_t* pt;

    //    kprintf ("  INT0E : #PF Page Fault Exception. IP:%X CODE:%d ADDR:%X\n"
    //         "        : PML4[%d] PDPT[%d] PD[%d] PT[%d]\n", ip, code, addr,
    //         MMU_PML4_INDEX(addr), MMU_PDPT_INDEX(addr), MMU_PD_INDEX(addr), MMU_PT_INDEX(addr) );
    
    pt = MMU_PT(addr);
    if ( (code&1) == 0 ) {  // Page Not Present
        if (( pt[MMU_PT_INDEX(addr)] & MMU_K_ONDEMAND ) == 0 ) {
            kprintf ("  INT0E : #PF Page Fault Exception. IP:%X CODE:%d ADDR:%X\n"
                     "        : PML4[%d] PDPT[%d] PD[%d] PT[%d]\n", ip, code, addr,
                     MMU_PML4_INDEX(addr), MMU_PDPT_INDEX(addr), MMU_PD_INDEX(addr), MMU_PT_INDEX(addr) );
            kprintf ("    #PF : Access to unallocated memory. CODE: %d\n", code);
            kprintf ("        : ADDR: %X PT[%d]: %X\n", addr, MMU_PT_INDEX(addr), pt[MMU_PT_INDEX(addr)]);
            __asm volatile ("cli; hlt");
        }
    
        page = MMU_alloc();
        prot = pt[MMU_PT_INDEX(addr)] & MMU_PROT_MASK;
        pt[MMU_PT_INDEX(addr)] = page | prot | MMU_PROT_PRESENT;
        _INVLPG(addr);
        memset ((void*)((addr>>12)<<12), 0, 4096);
    } else {
        kprintf ("  INT0E : #PF Page Fault Exception. IP:%X CODE:%d ADDR:%X\n"
                 "        : PML4[%d] PDPT[%d] PD[%d] PT[%d]\n", ip, code, addr,
                 MMU_PML4_INDEX(addr), MMU_PDPT_INDEX(addr), MMU_PD_INDEX(addr), MMU_PT_INDEX(addr) );
        kprintf ("      #PF : Access to protected memory. CODE: %d\n", code);
        kprintf ("          : ADDR: %X PTE[%d]: %X\n", addr, MMU_PT_INDEX(addr), pt[MMU_PT_INDEX(addr)]);
        __asm volatile ("cli; hlt");
    }
}

As you may notice, the #PF don't care if the faulting address is generated by accessing non-existence page structure itself.
And there is no infinite loops.

OSDev.org

Allocating Space for VMM to place Page Structures

Allocating Space for VMM to place Page Structures

Re: Allocating Space for VMM to place Page Structures

Re: Allocating Space for VMM to place Page Structures

Re: Allocating Space for VMM to place Page Structures

Re: Allocating Space for VMM to place Page Structures

Re: Allocating Space for VMM to place Page Structures

Re: Allocating Space for VMM to place Page Structures

Re: Allocating Space for VMM to place Page Structures

Re: Allocating Space for VMM to place Page Structures

Re: Allocating Space for VMM to place Page Structures

Re: Allocating Space for VMM to place Page Structures