Re: On hierarchy

[Jonathan S. Shapiro]

On Fri, 2005-10-21 at 20:01 +0200, ness wrote:
> Jonathan S. Shapiro wrote:
> > Based on my current understanding of the mapping database -- which is
> > incomplete -- I have three concerns about the design:
> > 
> > 1. The hierarchy is unbalanced. In consequence, no time bounds on
> > traversals less than O(n) can be stated, and these do not satisfy the
> > stated requirements.
> > 
> 
> This is not entirely correct, IMHO. The hierarchy _may_ be unbalanced.
> The point is, that the system affects (or better: defines) the
> hierarchy. This means, if the system relies on a balanced hierarchy, it
> can create one.

What I think *you* are saying is: "it is possible for applications to
ensure that the mapping database is a hierarchy." It does not appear to
me that this is correct, because MAP operations form a linear chain, and
the system must represent and traverse this chain.

What *I* am saying is: the kernel must not include *any* operation that
would *ever*, under *any* circumstances, exceed log(n) time (n = number
of in-memory objects).

If there is a mapping database representation that supports this, I
don't know of it. However, I still need to look at Udo and Espen's
responses.

> >        => This relies on the assertion that the mapping database
> >           is purely a cache. I do not think this is entirely correct.
> >           More importantly, Kevin Elphinstone (who knows the design
> >           much better than I do) has expressed doubts about this as
> >           well.
> > 
> I'm don't know the design very good, too, but the mdb is purely a cache,
> AFAIK. In 2 papers I read ([1],[2]) is mentioned that the mdb state
> doesn't have to be exported, as it can be reconstructed.

In one of the discussions at the Dresden meeting it came up that (a) the
L4 teams have always assumed that the mapping database could be
reconstructed on demand, but (b) there is a counter-example to this
belief. This creates a difficulty in responding to your statement
because I do not know whether those papers are written before or after
the difficulty was noticed. Also, I do not know if the difficulty has
been resolved.

I think perhaps I should send a note to Kevin and ask him if he
remembers what the counter-example was.

shap