[parisc-linux] Proposal for altering our Page Table layouts

[James Bottomley]

On Sat, 2004-04-10 at 17:46, Carlos O'Donell wrote:
> While pgdir might be hot in cache, but the rest of the structures will
> sprawl to fill the entire cache.
> 
> In contrast a hashed page table layout would be extremely dense, and fit
> better in the cache. If you were to have a collision the likelyhood
> that what you want is in the cache can actually be higher.

Well, I challenge you to show me such a dense layout.

The reality in Linux is that the kernel is offset mapped (physical
addresses and virtual addresses differ by PAGE_OFFSET).  This means that
any hash head comes directly out of kernel allocated memory.  Further,
since our tlb miss handlers must operate in physical space, it has to be
physically contiguous.  Given glibc's somewhat prodigious appetite, our
average mapped pages per system process is about a thousand (obviously
not all hot).  That makes the hash size (given that you have to have 16
byte entries) about 16k.  Now look at graphics programs; just pulling in
X gnome/kde and we'll jump to 10,000 or 160k.  The latter is just not
possible (the maximum contiguous allocation is 128k, and we can't do one
of those per process and still live to tell the tale).

By contrast, a multi-level page table can be sparsely allocated and has
no physical contiguity requirements.  I'm willing to be proven wrong,
but I just can't see how we can allocate a cache large enough to avoid
common collisions given the Linux physical allocation constraints.  And
if we don't allocate it contiguously, it's performance is going to be
far worse than a two level lookup.

James


> > In particular, on PA because of our congruence requirements for shared
> > mappings, it would be difficult to find an efficient hashing mechanism
> > that didn't generate deep collision chains (and remember, we're all
> > ILP32 at the moment, so just one collision and we lose to the 2 level).
> 
> Huck & Hayes says "high va bits XOR low va bits."
> 
> http://www.baldric.uwo.ca/~carlos/Architectural-support-for-translation-table-management-in-large-address-space-machines.pdf
> 
> I've been doing some literature searches on the issue, mainly IEEE and
> ACM over the last 10-20 years. Most of the research was done in the mid
> 90's and interestingly enough a lot of it has to do with PA's.
> 
> Read the paper at the above link and tell me what you think of the
> 16-byte PTE presented, and how the allocations happen on a single entry
> by entry basis. Another author suggests that the HAT and the PDIR could
> be merged (you'll have to read the paper to find out what I mean). I'm
> not sure what to do about the aliasing restrictions...
> 
> c.