Allocating second level page tables.

[chickendinner]

I'm developing a OS for the raspberry pi, I've got basic drivers for all the peripherals (framebuffer, clock, interrupt controller, timer) and built a rudimentary task scheduler that switches between 2 pieces of code. In order to develop a proper scheduler and implement processes in separate address spaces i need some form of memory management. I've managed to turn the mmu on and map the kernel at a high address and get a physical memory manager working, so i can reserve and allocate physical pages. My next step is to implement a virtual memory manager to map those physical pages onto the page table.

Ideally I want the page table to start with just a first level table entries and allocate second level page tables onto it as necessary (So i don't need every page table to be 4mb initially). So when I map a page i'll check to see if that first level entry points to a second level table or if it is unmapped, and if unmapped allocate a second level page table, add the required entries to it and then set the first level entry to it.

The problem is in order to change the second level page table it also needs to be mapped into virtual memory. Which means in order to map memory I need to be able to map memory. A catch 22 situation.

So i'm trying to figure out the best way to handle this situation in the most elegant way possible. I have a few ideas.

1. Initialise the page table to have a 1 second level page table already set. Reserve that area of memory for the mapper to use as scratch space to map the second level table to. Simple but i don't really like it.

2. Have just the kernel address space have all of it's second level page tables setup to begin with (one time cost of 2mb address space). And as a result i can build a separate kernel address mapper that doesn't need to worry about allocating second level page tables. The separate user mapper that does need to create second level tables can use the kernel mapper to map the second level table into kernel memory to edit it.

What kind of approach would you guys recommend/use?

[OSwhatever]

What I do is having the 8KB L1 page table in kernel virtual memory at all times and then it will be always available. This is necessary for ARMv6,v7, for x86 or ARMv8 (also in v7 with LPAE) this will not be necessary because they allow recursive page tables.

Scratch pages is also necessary as you have to map the page table itself somewhere, then you need an L2 page as well mapped somewhere in order to set it up before you change to the new page table. I use a scratch location for this. Not that nice but I don't know another way to do it. Scratch pages is also not needed when you have recursive page tables. ARM is what it is when it comes to this and that's why they changed it with LPAE.

[jnc100]

Given that the RPi has a maximum of 512 MiB of memory (currently) you could map all physical memory to part of kernel space and then access it there. Obviously this would not be portable to other ARM devices with substantially more memory.

Regards,
John.

[Brendan]

Hi,

The problem is in order to change the second level page table it also needs to be mapped into virtual memory. Which means in order to map memory I need to be able to map memory. A catch 22 situation.

You can:

• permanently map all physical pages that can be used for second level page tables into kernel space (which may or may not be all physical pages). Note: already suggested by jnc100
• temporarily map the physical pages needed into a special/reserved area of kernel space so you can modify them
• do the "recursive paging trick" where you only ever modify a virtual address space when it's being used. If you ever need to modify a different virtual address space, you can:
  • temporarily switch virtual address spaces, or
  • keep a "log of pending changes" and postpone the virtual address space changes until you need to switch to that virtual address space anyway. Note: may be slightly tricky - you'd have to check if changes effect previous entries in the "log of pending changes"

I'm not sure if there are any other ways...


Cheers,

Brendan

[Owen]

Recursive paging requires that a "page directory entry" and a "page table entry" look the same.

This isn't the case on ARM (Hell, your "page directory" entries cover 1MB of address space, for very historical reasons)

[chickendinner]

Thankyou for the responses.

Given that the RPi has a maximum of 512 MiB of memory (currently) you could map all physical memory to part of kernel space and then access it there. Obviously this would not be portable to other ARM devices with substantially more memory.

I've implemented my kernel on top of a basic abstraction layer, that provides generic interfaces for registering interrupts, mapping memory, creating new contexts and the like (So porting won't need an entire rewrite) so allocating the entire memory while a valid solution would defeat the point of that abstraction. My target is actually the bcm2835 SoC, which may not necessarily be a Rpi and it supports up to 2GB of memory (I doubt one exists with this much however) so I don't want to assume it only has 256mb/512mb of memory either. This would work great if i was just developing for solely the pi, so thank you for mentioning it.

• do the "recursive paging trick" where you only ever modify a virtual address space when it's being used. If you ever need to modify a different virtual address space, you can:
  • temporarily switch virtual address spaces, or
  • keep a "log of pending changes" and postpone the virtual address space changes until you need to switch to that virtual address space anyway. Note: may be slightly tricky - you'd have to check if changes effect previous entries in the "log of pending changes"

Storing pending changes or additional address space switches seems like a pretty messy way of handling pages compared to scratch tables. Ideally I want a hack that i can keep contained in the mmu interface. Having pending changes for address spaces makes the address spaces not current and would mean changing the way i write the rest of the kernel. And since non-recursive pages seem to be a legacy thing i don't want to design my kernel around that.

It looks like having a scratch table mapped to the current second level entry is the cleanest way I can handle this due to the hardware constraints of the MMU. I have a board_init function that runs at startup and reserves the IO regions/Sets up the heap region .etc, i'll reserve a page in there mapped just above the IO region for the mmu interface to use.

I'm not too far from getting a barebones kernel running, once i've ported newlib, I'll share the repo since i haven't seen many kernel running on ARM around, so someone might find it useful.

[Combuster]

[*]do the "recursive paging trick" where you only ever modify a virtual address space when it's being used. If you ever need to modify a different virtual address space, you can:(...)
I'm not sure if there are any other ways...

If recursive paging works, you can also include the CR3 of another address space as a top-level paging entry in the current address space. But basically that's just an optimisation of "reserving dedicated pages for cross-address-space structures". The advantage of that base method is that the idea works everywhere, and you don't suffer the cost of an entire context switch (and it's typical bad effect on TLBs).