Rights Amplification

[Espen Skoglund]

[Marcus Brinkmann]
> Each mapping is identified in the mapper's address space via a
> virtual address (or index, or slot number, ...).  Then there could
> be a kernel system call

>   vaddr_t map_lookup (vaddr_t addr);

> which walks up the mapping tree, starting at the mapping entry for
> ADDR and going to the parent of the current node in each iteration
> until a mapping in the same address space is encountered.  The vaddr
> of this mapping is returned.

Since I'm linf of involved with these sort of questions myself it
seems like the right thing for me to share my thoughts on the subject.

I thought about this sort of functionality when doing my own work, but
abandoned it mainly because of the need to traverse the mapping tree.
Before going into detail here let me just give a short note on the two
variants of the operation itself.

As you suggest yourself, one possible variant of this scheme is to
have the lookup occur during IPC.  This is really what you would want
to do because:

  o You don't have to create new (temporary) mappings during IPC.

  o You don't have to later revoke the mapping either explicitly or
    due to overmapping in later IPCs.

What kills you here is the revocation part because revocation (of
memory mappings) involves TLB flushes that can be pretty expensive
(especially if you need to do TLB shootdowns in an MP system).
Moreover, you never really need to have the page mapped into your
address space in the first place since you're only interested in the
"translation" of the page.  Mapping it is therefore overkill.


I agree that having an operation that can identify one's own virtual
address of a mapping can be pretty neat.  Many people on this list
have however pointed out the nasty aspects of it.  The killer
nastiness here (IMO) is that you may potentially need to traverse the
mapping tree all the way up to the root.  This means that no matter
how clever a locking scheme you use for the mapping database, you may
always need to somehow lock the root nodes in the tree.

What you really want is some sort of O(1) opeartion, in partciluar if
you want to make it feasible to implement this lookup as part of the
fast IPC path.  A cmp() operation has been suggested that can indeed
do the lookup in O(1).  Cmp() has a couple of drawbacks, though:

  o It still requires lookups in the page tables---meaning higher
    cache footprints, locking for consistency reasons, etc.

  o It reaveals information across mapping hierachies.  This could be
    a potential security issue.

Another problem with cmp() is that as far as I understand it doesn't
do what Marcus asks for.  That is, it does not identify a particular
vaddr within the address space.  Such functionality must be
implemented by successively comparing each page in the address space.
For this reason it does not make sense to impement cmp() as part of
the IPC opertaion, which means that you have all the side effects of
temporary mappings that I mentioned above.

To summarize, all in all I agree that the map_lookup() function is
semantically really neat.  It's just a pity that the implementation of
it has certain issues.


Now, just for the sake of confusing people even more, let me throw in
another idea I've been playing around with.  My take on the problem of
application specific capability transfer is to introduce another type
of address space; an ID space.  One can fabricate new IDs within one's
ID space and also map/grant/unmap such IDs between ID spaces.

The fabricate operation would take two parameters:

   Fabricate_Id (id, number) --- where id is the location within one's
     ID space and number is a number associated with that ID.

When the user does an IPC it can specify to send an ID as some form of
protected payload to the destination.  On the destination side, the
receiver specifies an ID to use for translation purposes.  During the
transfer of the ID the kernel checks if the two IDs reside within the
same owner space.  If so, the actual transferred value is the number
specified when creating the ID.  If not, an "invalid" value is
transferred.

Translation of an ID takes constant time.  It simply involves checking
whether the owner space of two IDs are the same.  An extension of the
translation process is to allow a small number (say 2--4) IDs be
specified as translation IDs.  Another extension is to have an access
right that allows the ID to be used for translation purposes.  Without
this right the ID can only be used as a protected payload.

An example of how the ID stuff could work:

   A server creates a number of IDs that it maps off to clients.  The
   clients can delegate these IDs off to other applications if it
   wants.  Upon receiving requests from clients the server specifies
   one of its IDs as a translation ID.  If the client has chosen to
   transfer an ID that was created in the server the server will
   receive the number associated with that ID.

Another example:

   A server in the system creates one ID for every principal in the
   system.  The principal IDs are mapped to different ID spaces.  Upon
   receiving an IPC other servers in the system can use their
   principal IDs to figure out the principal IDs of the client
   requests.  Applications can temporarily map their principal IDs to
   other applications to make these applications assume the identity
   of themselves.

The two examples show two different usage cases of IDs.  In the former
case the ID is used to identify something managed by the server
itself.  In the latter case the ID is used to identify something
managed by some other entity in the system.

I realize that these IDs do not directly solve the problems you are
posing.  That is, it doesn't allow you to verify that, e.g., a memory
mapping you receive really is what you expect it to be.  You can do
certain tricks here though.  For example, a server can create an ID
associated with every memory mapping it hands out (i.e., it maps the
ID together with the page frame).  Someone down in the mapping
hierarchy can then use this ID to prove to the server that it has a
capability to the page frame.  This would for example solve the
reference counting problem you posed.


I hope my explanations are clear enough, and perhaps helpful.  I
really do appreciate that someone is trying to use the various models
to actually solve real problems.

	eSk