In article <1174821956.522892.305310@n59g2000hsh.googlegroups. com>,
"sancho1980" wrote:

> Hi
> page 394 of osdi 3rd edition says (at the bottom):
>
> "The normal way to process a TLB miss, whether in hardware or in
> software, is to go to the page table and perform the indexing
> operations to locate the page referenced. The problem with doing this
> search in software is that the pages holding the page table may not be
> in the TLB, which will cause additional TLB faults during the
> processing."
>
> What? Why is that related to whether I'm doing this in hardware or
> software? If I do the search in hardware, the problem could arise just
> as well, right?

If you do it in hardware, the hardware page table walker can ignore the
TLB if there are any secondary misses. If you do it in software, you may
have to have a reentrant miss handler (i.e., attempting to access a part
of the page table not in the TLB will result in the miss handler being
invoked before it's finished). Not impossible to do but another detail
to get right.

> Then it goes on:
>
> "These faults can be reduced by maintaining a large (e.g., 4-KB or
> larger) software cache of TLB entries in a fixed location whose page
> is always kept in the TLB. By first checking the software cache, the
> operating system can substantially reduce the number of TLB misses."
>
> My question: Instead of having this TLB cache in memory and making
> sure its page frame number is always in the TLB, why not just make
> sure the page table's frame is always in the TLB???

A page table has to cover the whole address space. In practice, parts of
it may never be used. There are likely to be big gaps e.g. between the
stack and heap. The page table in total is a lot smaller than all the
pages in the system but it still may not be practical to represent fully
in memory.

--
Philip Machanick

> If you do it in hardware, the hardware page table walker can ignore the
> TLB if there are any secondary misses. If you do it in software, you may
> have to have a reentrant miss handler (i.e., attempting to access a part
> of the page table not in the TLB will result in the miss handler being
> invoked before it's finished). Not impossible to do but another detail
> to get right.

Ok, so the hardware handler wouldn't even bother to look up the page
table frame in the TLB and thus doesn't risk getting yet another miss?
Is that the performance advantage? Well, it (the page table frame)
could also very well be in the TLB, in which case ignoring the TLB
from start would actually slow things down; so I don't see the
performance gain in it, sorry!


> A page table has to cover the whole address space. In practice, parts of
> it may never be used. There are likely to be big gaps e.g. between the
> stack and heap. The page table in total is a lot smaller than all the
> pages in the system but it still may not be practical to represent fully
> in memory.

So are you saying that instead of having the page table frames
constantly in memory, it is better to have just a RANDOM subset of it
in memory with its frame base in the TLB? I really don't see how this
could possibly speed up things!

Not meaning to sound rude, but I still don't get it!

Thanks,

Martin

In article <1174912588.119423.193660@l77g2000hsb.googlegroups. com>,
"sancho1980" wrote:

> > If you do it in hardware, the hardware page table walker can ignore the
> > TLB if there are any secondary misses. If you do it in software, you may
> > have to have a reentrant miss handler (i.e., attempting to access a part
> > of the page table not in the TLB will result in the miss handler being
> > invoked before it's finished). Not impossible to do but another detail
> > to get right.
>
> Ok, so the hardware handler wouldn't even bother to look up the page
> table frame in the TLB and thus doesn't risk getting yet another miss?
> Is that the performance advantage? Well, it (the page table frame)
> could also very well be in the TLB, in which case ignoring the TLB
> from start would actually slow things down; so I don't see the
> performance gain in it, sorry!

I didn't exactly say that. The HW can look in the TLB and if the
secondary entry isn't there, go straight to memory and not try to fix up
the TLB for the secondary miss. The secondary table (at least the parts
of it close to the last reference) may meanwhile have found its way to
the data cache, making a second use of it in the near future faster.

A HW page table walker will generally also give up and generate an
interrupt in the more complex cases so it isn't strictly a matter of one
or the other.

> > A page table has to cover the whole address space. In practice, parts of
> > it may never be used. There are likely to be big gaps e.g. between the
> > stack and heap. The page table in total is a lot smaller than all the
> > pages in the system but it still may not be practical to represent fully
> > in memory.
>
> So are you saying that instead of having the page table frames
> constantly in memory, it is better to have just a RANDOM subset of it
> in memory with its frame base in the TLB? I really don't see how this
> could possibly speed up things!

If you have a 2GB address space, and 4KB pages, that means you have over
1-million page table entries. If each entry is 4B, you need 2MB for the
entire page table for _every_ process -- unless you can be smart about
allocating a process a subset of the address space. But in a true VM
system, all applications can theoretically expand to the limit of the
address space, even if they leave gaps. If you have 100 processes
(currently 85 running on my Mac with a single user), that's 200MB.

So you generally only want to represent the subset of the page table
that is actually used in memory. The TLB will contain (you hope) the
frequently accessed entries.

All of this is somewhat approximate as there are many variations in
practice in real systems.

Here's some further reading:
* http://www.gelato.unsw.edu.au/~ianw/...iew/report.pdf
* Jacob, B. L. and Mudge, T. N. 1998. A look at several memory
management units, TLB-refill mechanisms, and page table organizations.
SIGOPS Oper. Syst. Rev. 32, 5 (Dec. 1998), 295-306. DOI=
http://doi.acm.org/10.1145/384265.291065

--
Philip Machanick