Managing page tables question

[Goswin von Brederlow <goswin-v-b@web.de>]

Hi,

I'm wondering what the best way is to manage page tables for my own
toy OS. I'm working with xen on amd64 so I have 64bit address space
and 4 levels of page tables (L4 -> L3 -> L2 -> L1 -> page) with 512
entries each.

Now here is the problem:

- to change a page table entry I need the machine frame number
- the machine frame number is stored in the page table above it
- to read the table above it I need the virtual address (and have it mapped)

To keep track of the virtual address of each page tables there seem to
be 3 ideas:

1) Map all physical ram to virtual addresses

For xen this gives 2 choices:
a) Map machine frames to virtual addresses 1:1
   Machine frames can be all over the place meaning lots of gaps in the
   page tables mapping those pages. -> wastes pages
b) Map pseudo physical frames to virtual addresses 1:1
   This is continious but it always needs the phys_to_mach and
   mach_to_phys conversions. -> wastes time

Both of those will use up pages for the mapping although only a
fraction of the total. And they will use up pages for regions where no
page table is actually located.


2) Maintain a shadow page table with virtual addresses

So instead of 1 page per page table you use 2 pages. The first
contains the hardware entries with the machine frame and the second
contains the virtual address of that machine frame in coresponding
slots.

For the L1 page tables you don't need the physical addresses of the
pages it points to as that is already determined by the offsets you
followed (or the address you are trying to locate in the first
place).

Again you use up pages. One per page table. If you have a lot of page
tables this will use up more pages than 1 though.


3) Recursive mapping. Map the Page Tables into themself.

In the L4 table you would add an entry at 0xFF that points to the L4
table itself. That would automatically map all page tables into the
end of the address space (with signed addresses and xen taking up the
negative half).

Now this idea sounds interesting. You waste one entry in the L4 page
table (or 512GB of virtual address space that you will never miss) and
no pages at all. And every single page table would be at a well
defined virtual address in a 1:1 mapping to the offsets they are at.

BUT CAN YOU DO THAT IN XEN?

The L4 table is pined to PIN_L4_TABLE and each entry in the L4 table
must point to a page pined to PIN_L3_TABLE. The self reference would
have the wrong pinning. I wonder if it possible to allow such a
mapping without compromising the security of the page tables.



If method 3 is impossible then it seems like method 1b is best. It
uses a small fixed amount of pages for mapping and the mach/phys
conversion should be negible compared to a page fault exception.

So what is your favourite method? Any I didn't mention?

MfG
        Goswin