OSDev.org

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?

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?

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.

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

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

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

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.

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:
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
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
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.

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.

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

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.

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.

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.