How can I impliment Paging

[Xeno]

I am working on Pagin in 64bit mode. I have been stuck on this step for about 5 months..., I ahve been working on other stuff but I really need paging to work. When I initiate Paging and I map in kernel then my page tables are not maped in but if I map them in I need to map in the part that maped in the Pagetables then i need to map thopse pages in to, and it seems to me that I need to mape in A to make B map C but A needs too be maped in too. Am I missing something?

[Octocontrabass]

If you want to access something, it needs to be mapped in your page tables, but you can map everything you need at the same time when you set up your page tables. Where are you having problems with that?

[Xeno]

It seems that I have to map in a page to map in a page but the page that maps it in isnt maped in, I'm strugeling with dependencies.

[iansjack]

You create the map before you enable paging and enter long mode.

[Xeno]

I am past that stage and am rebuiilding page table for kernel in kernel init

[Xeno]

Maybe im doing it wrong
This is the virtual structure im working with to handel my page table:

Code: Select all

/*
 * #Core-Data-Structure
 * @brief       Structor of memory map
 * @paragraph   Structered from P1 being the "root" page table and all bellow in decending
 *          order with P4 containning a list of 0x1000 bytes page adresses
*/
struct P4s {
    uint64_t E[512];
} attribute(packed);
struct P3s {
    uint64_t E[512];
    struct P4s P4[512];
} attribute(packed);
struct P2s {
    uint64_t E[512];
    struct P3s P3[512];
} attribute(packed);
struct P1s {
    uint64_t E[512];
    struct P2s P2[512];
} attribute(packed);
struct P1s* MPT = (struct P1s*)((uint64_t)0x0000FF0000000000);


/*
 * #Core-Data-Structure
 * @brief       Adress structor of memory map
*/
typedef struct {
    uint64_t P1;
    uint64_t P2;
    uint64_t P3;
    uint64_t P4;
} MPT_adress_t;

[d4ilyrun]

It seems that I have to map in a page to map in a page but the page that maps it in isnt maped in, I'm strugeling with dependencies.

From what I understand, you might want to have a look at recursive page tables: https://medium.com/@connorstack/recursi ... 1e03b20a85

This method allows you to easily edit your paging structures without having to manually map them to a virtual address, which seems to be your issue here (the typical chicken and egg problem).

[Octocontrabass]

It seems that I have to map in a page to map in a page but the page that maps it in isnt maped in, I'm strugeling with dependencies.

There are two ways you could solve this problem.

One way is to map all memory. Everything is always mapped, so you can access whatever you need at any time.

The other way is to reserve some pages for temporary mappings. When you need to access something that isn't mapped, you modify a temporary mapping to point to that memory.

[nullplan]

Maybe im doing it wrong

With that structure, definitely.

The nice thing about page tables is that each of them takes up a full page. So if you just request a page from your PMM, you can use the entire thing. So that is how I deal with page tables: Each of them is exactly one page, interpreted as array of 64-bit numbers. I just allocate them as needed.

The thing you're stuck on is what everyone stumbles over sooner or later. You need to access physical memory to implement paging, but can only access virtual memory. The most common solutions are to map all of physical memory linearly to some place (which is easy on x86_64, where by definition virtual memory is always at least 4 times larger than physical memory), or to use a known temporary mapping, or to use recursive paging. All of these you initialize when you initialize paging.

My bootloader (running without paging in 32-bit mode) has this:

Code: Select all

#define PF_PRESENT 1
#define PF_WRITE   2
#define PF_USER    4
#define PF_NX      0x8000000000000000ull

static void mmap(uint64_t vaddr, uint64_t paddr, size_t len, uint64_t flags)
{
    static uint64_t *pml4;
    static uint32_t watermark;
    int idx[4], i;
    uint64_t *p;

    if (!pml4)
    {
        pml4 = (void*)0x1000;
        memset(pml4, 0, 0x1000);
        watermark = 0x2000;
    }

    if (vaddr & 0xfff)
    {
        len += vaddr & 0xfff;
        vaddr &= 0xfffffffffffff000;
        paddr &= 0xfffffffffffff000;
    }
    len = (len + 4095) & 0xfffffffffffff000;

    while (len >= 4096)
    {
        p = pml4;
        idx[0] = (vaddr >> 39) & 0x1ff;
        idx[1] = (vaddr >> 30) & 0x1ff;
        idx[2] = (vaddr >> 21) & 0x1ff;
        idx[3] = (vaddr >> 12) & 0x1ff;

        for (i = 0; i < 3 + (paddr & 1); i++)
        {
            if (!(p[idx[i]] & PF_PRESENT))
            {
                if (watermark >= 0xA0000)
                    panic("Out of memory for page table");
                p[idx[i]] = watermark | PF_PRESENT | PF_WRITE;
                memset((void*)watermark, 0, 0x1000);
                watermark += 0x1000;
            }
            p = (void*)(uintptr_t)(p[idx[i]] & 0xfffff000);
        }

        if (!(paddr & 1))
            p[idx[3]] = paddr | flags;
        len -= 4096;
        vaddr += 4096;
        paddr += 4096;
    }
}

With this, I add all the page maps I need to the initial page table, then jump to the kernel. And you can implement all of the above schemes in almost this way. With the linear map I just do

Code: Select all

    if (mmap_len)
    {
        uint32_t *mm = (uint32_t*)(mmap_ptr - 4);
        for (int i = 0; i < mmap_len; i++)
        {
            if (mm[5] == MULTIBOOT_MEMORY_AVAILABLE)
                mmap(0xffff800000000000 | mm[1] | ((uint64_t)mm[2] << 32), mm[1] | ((uint64_t)mm[2] << 32), mm[3] | ((uint64_t)mm[4]), PF_PRESENT | PF_WRITE);
            mm = (uint32_t*)((char*)mm + *mm);
        }
    }

With the known temporary mapping, you map one specific page table into virtual memory, and that page table has one entry that does not get shared to other CPUs, leading to one address you can always use for temporary physical mappings. So you have two constants for the scheme: The address of the known page table and the temporary address. In the above scheme, it might be best to do something like

Code: Select all

mmap(TEMPORARY_ADDRESS, -1, 0x1000, PF_PRESENT|PF_WRITE);
uint64_t pt = pml4[(TEMPORARY_ADDRESS >> 39) & 0x1ff];
pt = ((uint64_t*)(pt & 0xfffff000))[(TEMPORARY_ADDRESS >> 30) & 0x1ff];
pt = ((uint64_t*)(pt & 0xfffff000))[(TEMPORARY_ADDRESS >> 21) & 0x1ff];
mmap(PAGE_TABLE_ADDRESS, pt & 0xfffff000, 0x1000, PF_PRESENT | PF_WRITE);

Something along these lines anyway.

With a recursive mapping, you set one particular entry of the PML4 to point back at the PML4. I will not provide code for this, because I dislike the approach. You end up adding uninitialized memory to the paging structures, which can lead to the processor adding all sorts of nonsense to the TLB that would need to be cleared out once the page is initialized.

I will say that of these options, the linear mapping is by far the easiest to use, because every address in physical RAM just has a virtual address associated with it, and it is unchanging and easy to calculate. With the know temporary, you end up having to juggle the address around constantly. It's not that it doesn't work, it is just harder than it needs to be. And the recursive mapping I already criticized above.

[iansjack]

I’d go for the map all physical memory option. It may seem obvious, but make sure that this mapping is only available to the kernel, not other tasks.

[Xeno]

OK thanks everyone I think I have found my solution, if it doesnt work ill be back

[thewrongchristian]

With a recursive mapping, you set one particular entry of the PML4 to point back at the PML4. I will not provide code for this, because I dislike the approach. You end up adding uninitialized memory to the paging structures, which can lead to the processor adding all sorts of nonsense to the TLB that would need to be cleared out once the page is initialized.

Why would you be adding uninitialised memory to the paging structure?

[nullplan]

Why would you be adding uninitialised memory to the paging structure?

All the recursive paging implementations I've seen allocate a page, then add it to the paging structures, and only then initialize that page to all zero, because only then is it accessible. However, the page is accessible as page table from the moment it is added to the parent page table, and it could in theory be read by the processor.

Most of the time it won't happen, of course. The processor only reads the page table when it encounters a TLB miss. And for a given entry, half the time nothing bad happens because the uninitialized value happens to have a zero bit in the "present" position. Indeed in most emulators all unallocated memory is zeroed. Doesn't help on real hardware, though. So for the above to be a problem you would need a CPU with a large pipeline and some bad luck with the hardware. That doesn't mean I like it any better, though. In order to do it correctly, you'd need to check for each entry if the P bit was set and run invlpg on the relevant address after setting the entry to zero. Or else run invlpg on all 512 possible addresses unconditionally just in case.

It may be possible to avoid this issue somehow, but I haven't seen it yet.

[thewrongchristian]

Why would you be adding uninitialised memory to the paging structure?

All the recursive paging implementations I've seen allocate a page, then add it to the paging structures, and only then initialize that page to all zero, because only then is it accessible. However, the page is accessible as page table from the moment it is added to the parent page table, and it could in theory be read by the processor.

Most of the time it won't happen, of course. The processor only reads the page table when it encounters a TLB miss. And for a given entry, half the time nothing bad happens because the uninitialized value happens to have a zero bit in the "present" position. Indeed in most emulators all unallocated memory is zeroed. Doesn't help on real hardware, though. So for the above to be a problem you would need a CPU with a large pipeline and some bad luck with the hardware. That doesn't mean I like it any better, though. In order to do it correctly, you'd need to check for each entry if the P bit was set and run invlpg on the relevant address after setting the entry to zero. Or else run invlpg on all 512 possible addresses unconditionally just in case.

It may be possible to avoid this issue somehow, but I haven't seen it yet.

Christian quickly shuffles off through his own code and checks...

Bloody hell, I do it like that as well!

Well, that's my project for tonight sorted, and apologies for the judgemental **** response.

In summary, when setting a PTE, I check the page directory level to see if a page table is mapped, and if not, I allocate a page to add to the page directory. This happens unlocked, so I can't update the page structure yet.

Then I lock, check again if I need a page directory, and set page directory mapping, then clear the page table that I just mapped via the recursive page table mapping.

Now, this all happens in a critical section, so interrupts and other processors (if I supported SMP, which I do not yet) can't interrupt this process, but certainly other processors could start using those random mappings without taking a lock, so I'd better fix that.

I think I'll keep a zeroed page per processor in reserve to fill in missing page tables when adding mappings, and a mapping that uses such a page will be responsible for also allocating an filling in the next reserve page.

That, or keep a cache of zeroed pages that I can quickly and painlessly allocate on demand.

[rdos]

Checked mine code too, and apparently, I have locks (a critical section) for user space, but not for kernel space. I don't think this is a problem for kernel space though, but I probably should fix it anyway.

I think I have a similar problem with demand paging that currently is disabled. I suspect the problem there is that I map the page and read & relocate it in user space. This means that if another thread tries to access it, it will not be blocked on the page-not-present fault, rather will read non-relocated stuff while the other thread is relocating it. It might even read random data if the page is not yet read from file. So, since this is not working, I load the whole executable at load time, which could be quite wasteful. To fix this, I would need to do a temporary mapping (in kernel space) and only map it in user space after everything is properly initialized. I suppose a similar method could be used for kernel page directories as well. Alternatively, the page could be mapped as kernel only, which would cause a page fault if another thread tries to use it, but handling that fault could be complicated.

The problem with a temporary mapping is that the un-mapping causes TLB invalidations to be sent to all cores. Might be fixed by keeping one 4k page per core for temporary mappings. OTOH, that would require that the code using temporary mappings must be hindered from being moved to another core, which is problematic too.