Re: EROS/Coyotos fault handers vs l4 pager hierarchy

[Jonathan S. Shapiro]

On Fri, 2005-10-21 at 11:17 +0200, Matthieu Lemerre wrote:

> What is hierarchic, though, is the mapping database of course.

Yes, but a consequence of this appears to be that the only practically
feasible pager designs involve hierarchical trust. It may be a shallow
hierarchy, as Marcus has said elsewhere.

> > There is no comparable hierarchy in EROS. A fault handler's job is
> >to repair a page fault or not. Once a COPY is completed, there is no
> >further dependency on the sender's fault handler. In EROS, the
> >hierarchy is a matter of storage allocation, not mapping recovery.
> 
> I really think that there is no dependency on the sender's fault
> handler too on L4.  You can have a system which never invokes your
> pager (like the system I described in my last mails).

I believe that the following is a counter-example:

Let A and B be communicating parties, A' and B' their respective pagers,
and SPG the pager that is responsible for system-wide swap-paging.

A maps a region to B.

In order to evict an LRU page, SPG unmaps a page that exists within this
shared region.

If B later needs to access this page, it must either (a) communicate
with A', which will communicate with SPG, at the time of the re-load, or
(b) make other arrangements at the time the mapping is established so
that B' can communicate with SPG directly.

In either case, you cannot have a system that never invokes your pager.

> With the EROS approach, it seems to me that you can't customize the
> way swapping is done.  

This is only partially correct. The bigger issue is that persistence is
intimately connected to swapping, so you can't get all of what you seem
to want.

> What we originally planned to do was that
> applications could customize the way unused pages are sent to the
> swap, so that applications whose statistical page fault model doesn't
> fit well with the LRU algorithm could take advantage of it.  Would
> that still be possible with EROS?

Yes and no. The problem is that paging is intimately connected to
persistence, so allowing untrusted applications to make the non-advisory
paging decisions is tricky.

Our belief -- and this is not yet validated -- is that LRU is not really
the problem in most cases. The real problem is that LRU is usually
applied to the wrong set of pages. What is needed is a first-class
notion of working set so that an application can say "this group of
pages should only compete with itself". This does not solve the problem
entirely, because there still exist things like LISP systems where the
"old space" access pattern does not interact well with LRU policy. Given
a working set mechanism, the two policies that seem to make sense to
implement are LRU and random replacement. Possibly there are others.
These are the two that I have seen used effectively in practice.

An additional, straightforward mechanism is an *advisory* mechanism that
allows an application to say to the kernel "I am done with this page."
This is straightforward to do, but not currently implemented.

The one thing that is very tricky is to set up a protocol where the
kernel says "I need to replace a page, tell me which one to remove." I
believe that I can see how this might be done safely by introducing the
notion of a working set fault and an appropriate fault handler, and it
is something that Anshumal Sinha tried to look at at one point, but we
did not come to a comprehensive design for the fault handler
interaction.

> > As an aside, I *hate* the name *pager* in the L4 terminology. Every time
> > I try to understand L4 pagers I find myself trying to figure out how
> > they relate to swap-paging. L4 pagers do something that is related, but
> > not closely related, and they clearly have a much more broader role in
> > L4 than merely swap-paging. I find this tremendously confusing, because
> > the name causes me to confuse the concepts. Just to be clear: this is
> > *my* deficiency, not L4's.
> 
> Do you think page-fault handler would be a more appropriate
> terminology?

Remember: we are now discussing my personal opinion only!

I think that "page fault handler" would be worse. The problem is that
the term "page fault" is overloaded. It appears to me that the L4 pager
responds to *hardware* page faults, but in the domain of operating
systems it is more customary for the term "page fault" to refer to
something that has to do with the swap area.

Further: the role of L4 pagers is significantly broader in L4.sec, so I
think that any name including the word "page" is likely to be confusing
in the long term.

Please note: I am NOT suggesting that the name should be changed! I am
only expressing that it causes me confusion.

shap