OSDev.org

The Place to Start for Operating System Developers
It is currently Sat Apr 13, 2024 10:41 am

All times are UTC - 6 hours




Post new topic Reply to topic  [ 33 posts ]  Go to page 1, 2, 3  Next
Author Message
 Post subject: How can I impliment Paging
PostPosted: Fri Feb 23, 2024 11:51 am 
Offline
Member
Member

Joined: Tue Oct 10, 2023 7:40 pm
Posts: 51
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?


Top
 Profile  
 
 Post subject: Re: How can I impliment Paging
PostPosted: Fri Feb 23, 2024 12:35 pm 
Offline
Member
Member

Joined: Mon Mar 25, 2013 7:01 pm
Posts: 5134
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?


Top
 Profile  
 
 Post subject: Re: How can I impliment Paging
PostPosted: Fri Feb 23, 2024 1:05 pm 
Offline
Member
Member

Joined: Tue Oct 10, 2023 7:40 pm
Posts: 51
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.


Top
 Profile  
 
 Post subject: Re: How can I impliment Paging
PostPosted: Fri Feb 23, 2024 1:29 pm 
Offline
Member
Member
User avatar

Joined: Sat Mar 31, 2012 3:07 am
Posts: 4594
Location: Chichester, UK
You create the map before you enable paging and enter long mode.


Top
 Profile  
 
 Post subject: Re: How can I impliment Paging
PostPosted: Fri Feb 23, 2024 1:47 pm 
Offline
Member
Member

Joined: Tue Oct 10, 2023 7:40 pm
Posts: 51
I am past that stage and am rebuiilding page table for kernel in kernel init


Top
 Profile  
 
 Post subject: Re: How can I impliment Paging
PostPosted: Fri Feb 23, 2024 1:48 pm 
Offline
Member
Member

Joined: Tue Oct 10, 2023 7:40 pm
Posts: 51
Maybe im doing it wrong
This is the virtual structure im working with to handel my page table:
Code:

/*
* #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;


Top
 Profile  
 
 Post subject: Re: How can I impliment Paging
PostPosted: Fri Feb 23, 2024 2:29 pm 
Offline
Member
Member

Joined: Mon Mar 25, 2013 7:01 pm
Posts: 5134
Xeno wrote:
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.


Top
 Profile  
 
 Post subject: Re: How can I impliment Paging
PostPosted: Fri Feb 23, 2024 9:44 pm 
Offline
Member
Member

Joined: Wed Aug 30, 2017 8:24 am
Posts: 1601
Xeno wrote:
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:
#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:
    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:
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.

_________________
Carpe diem!


Top
 Profile  
 
 Post subject: Re: How can I impliment Paging
PostPosted: Sat Feb 24, 2024 12:59 am 
Offline
Member
Member
User avatar

Joined: Sat Mar 31, 2012 3:07 am
Posts: 4594
Location: Chichester, UK
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.


Top
 Profile  
 
 Post subject: Re: How can I impliment Paging
PostPosted: Sat Feb 24, 2024 6:48 pm 
Offline
Member
Member

Joined: Tue Oct 10, 2023 7:40 pm
Posts: 51
OK thanks everyone I think I have found my solution, if it doesnt work ill be back


Top
 Profile  
 
 Post subject: Re: How can I impliment Paging
PostPosted: Sun Feb 25, 2024 10:05 am 
Offline
Member
Member

Joined: Tue Apr 03, 2018 2:44 am
Posts: 402
nullplan wrote:
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?


Top
 Profile  
 
 Post subject: Re: How can I impliment Paging
PostPosted: Sun Feb 25, 2024 12:26 pm 
Offline
Member
Member

Joined: Wed Aug 30, 2017 8:24 am
Posts: 1601
thewrongchristian wrote:
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.

_________________
Carpe diem!


Top
 Profile  
 
 Post subject: Re: How can I impliment Paging
PostPosted: Sun Feb 25, 2024 3:29 pm 
Offline
Member
Member

Joined: Tue Apr 03, 2018 2:44 am
Posts: 402
nullplan wrote:
thewrongchristian wrote:
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.


Top
 Profile  
 
 Post subject: Re: How can I impliment Paging
PostPosted: Mon Feb 26, 2024 8:52 am 
Offline
Member
Member

Joined: Wed Oct 01, 2008 1:55 pm
Posts: 3192
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.


Top
 Profile  
 
 Post subject: Re: How can I impliment Paging
PostPosted: Mon Feb 26, 2024 11:00 am 
Offline
Member
Member

Joined: Mon Mar 25, 2013 7:01 pm
Posts: 5134
Locks by themselves aren't enough to protect you from speculative TLB fills. Any CPU sharing the same set of page tables might mispredict an address and load garbage into its TLB.

Atomics can protect you from speculative TLB fills, but only if you use them to ensure no CPU ever sees an unwanted present entry. You'd still need to clear memory before using it as part of your page tables. The x86 memory model is pretty strict, so there's not much overhead to this strategy - it's mostly preventing compiler optimizations from reordering specific writes.

Flushing the TLB is always an option. It's expensive, but maybe you'll decide that expense is acceptable for your OS.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 33 posts ]  Go to page 1, 2, 3  Next

All times are UTC - 6 hours


Who is online

Users browsing this forum: DotBot [Bot], Google [Bot], WinExperements and 505 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group