[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