Rights Amplification

[Marcus Brinkmann]

At Sat, 11 Jun 2005 12:15:03 +0200,
Bernhard Kauer <kauer at os.inf.tu-dresden.de> wrote:
> Ok, you need kernel support for that. The remaining open question is: 
> What is the right operation for that?

That's what I want to figure out, with your help.
 
> The map_lookup() has the disadvantage that it is time bound by the depth
> of the mapping tree. And it only works within the mapping hierarchy. This
> is a problem for example with external object caches or different proxies
> which try to map_lookup() siblings of the mapping tree.

I have no such requirements on siblings, but I also don't know how to
implement external object caches or different proxies, and maybe don't
even know what they are.  So, if it is a disadvantage, it's not one to
us, so I can not really comment on that.

cmp() was certainly something I have thought of myself, before I
realized that our own requirements were less broad and thus I could be
much more specific, making it easier for me to justify our own
requirements.  (It would not be proper for me to suggest a cmp()
operation if my own arguments only suggest a comparison within the
hierarchy is necessary).

> So why not use a more general and faster operation like cmp()?
> 
>     bool cmp(Address first, Address second)
> 
> Are there any arguments against this stronger operation?

If only comparison is possible, then we have to carry along an
identifier that allows us to look up the intended object in the first
place, so that lookup can still be O(1).  That's not a big problem, I
guess, but it is not terribly exciting either, because such an
identifier would have some "globalness" to it (if it is shared by the
reference counter and the server providing the object) that
complicates things all throughout the system.  It increases message
size and complicates the message format a bit, and probably makes
orthogonal persistence harder to get right.  But my gut feeling is
that it would still be feasible.

There might be security implications if you can compare across the
mapping hierarchy, in that it reveals information that you could
otherwise not guess.  If you only work within the mapping hierarchy,
at least some argument can be made that not too much information is
revealed: The caller could make---in a random sample of the cases---
an informed guess if the provided mappings were the same by unmapping
one of them and quickly probing if the other is still valid.  This is
not terribly reliable, but at least it shows that you can not make
mappings within the hierarchy completely independent/anonymous.  The
same is not true for mappings across the mapping hierarchy, where no
information can be gained actively without cooperation from other
tasks.  This suggests to me that at least some careful consideration
must be done before the functionality is extended in this way.

But to repeat, for myself I don't see any application for comparisons
across the mapping hierarchy.  That may very well be pure ignorance on
my side: My own use of L4 is pretty narrow in itself.  That's really
something that you have to think about, that's why you are the experts
:) If you say a more generic variant of the same functionality is
best, then that is likely fine for us, too.

As I said in my original mail, I gave the specific semantics of
map_lookup to illustrate what our specific needs are.  There are
potentially many other different ways to achieve the same
functionality, some of them with extra costs and/or extra benefits.
Most of them however with more semantical implications than I am
daring enough to suggest - so minimality was important for me to
originally limit the discussion to what is really relevant to us.

To me personally, it is not obvious that a cmp() function is
"stronger", it just seems to be different, it seems to be sufficient
for us, but also add extra costs for our use of it, which may very
well be acceptable though.  It's also potentially less secure, but in
a way that likely doesn't matter to us.  For us, I don't see a
benefit, but that may be totally different for other users.

I do agree that the semantics of map_lookup seem to be very narrow,
maybe too narrow to be an attractive element of a kernel design.  But
is cmp() the right generalisation?  I am not sure.  You decide.  I am
happy to comment on any ideas you come up with, and interpret them
from our point of view, as good as I can.  But I am sorry to aim
myself so low: If I had a grand design idea about how to do this in a
generic and all-encompassing way, I would share it.  But all I can
point out is our own modest requirements and offer them as a test case
for anything better you can come up with.

Thanks,
Marcus