I think you will need to explain a little bit more what you mean by "a mechanism similar to paging" before it will be possible to comment. Paging, to me, means there is some kind of swap drive or backing store to allow more "virtual" pages than "physical" pages.

I spent a lot of time recently digging through the physical memory management code of Linux/ia64. It is very messy because it has to support a wide variety of physical memory layouts. And it makes surprising choices that throw away huge chunks of physical memory (anything that doesn't fit conveniently in a "granule").

Getting this all working on multiple machines will probably be a big challenge. It might be best to use Linux code that is known to work on many machines.

I agree with your concern though that taking TLB misses when looking up a page struct in Xen is likely to cause performance problems and some difficult bugs. It might be worthwhile to put some counters in to see how frequently the memmap is accessed and code some defensive bounds checks to ensure wild accesses are immediately flagged with a BUG rather than resulting in random memory accesses.