Re: emulating no-senders notifications in L4?

[Marcus Brinkmann]

On Thu, Dec 20, 2001 at 12:37:34AM +0100, Niels Möller wrote:
> I been thinking a little more about how to do this, I think I now
> understand how to do port-rights on L4, and I'd like to share that.

I think basically, you have described that we need a seperate port server
that maintains port rights.  I guess so much was already clear.  Well, at
least nobody offered other ideas so far, although you risk to loose all the
performance gain this way.  However, in the details you are a bit too
optimistic about the data structures etc.  For example, you have to destroy
all port rights if the port receive right is destroyed, and you can't meet
such requirements with a fixed size linear array.  There are other
requirements, like if you insert a port right into a task, the port right
must have the same number if a compatible right for the same port already
exists (like, if you get a send right for a receive right, it is the same
port name number).  Such requirements make it necessary to include some
reference counting.

Basically, I guess what I am saying is that you want to port the Mach IPC
system (ipc/ in the mach source), which already has all the right data
structures and port management routines.  They are quite different from what
you describe here, but they should be more efficient and already make all
the right guarantees.

However, this is only the beginning, and as you illustrate, message
forwardingis achievable (btw, the mach ipc/ stuff should also have all
the port name translation stuff etc you did not cover).

The problem you face with no-sender notifications (and, to some extend I
would gess, also with send-once rights), is that the task termination must
destroy the port rights, and when that happens, you have to make all the
right guarantees for no-sender notifications and send-once rights.  Thomas
mentioned some of them in this thread.  The Mach IPC system is more than
just sending messages between ports, there are certain guarantees (quite a
lot of them!) that must be met by a replacement.  The Hurd in parts relies
on it.  Sending binary data from one task to another is only the simplest of
all problems.  Sending ports between tasks is a bit harder, but not so
difficult either.  However, controlling when a notification or send-once
message is sent seems to be not so easy.  (I guess you can emulate all this
in the port server, at the cost of efficiency).

> It is ultimately trusted by all other processes. It has book-keeping
> rpc-calls for creating and transferring ports and port rights, and for
> generating reliable no-senders notifications, but I won't say anything
> about those here.

What a pity :)  [the calls themselves are defined in the Mach interface
definition files of course, but the implementation would be interesting]

I will now also give some concrete comments on your suggestions, nothing
that isn't fixable, as far as your suggestion goes.

> The port-rights server can be quite simple. It has two essential data
> structures:
> 
>   struct port
>   {
>     /* Perhaps the owner field should not be a task_id, but instead  
>      * a thread_id corresponding to a dedicated thread in the owner task.
>      */
>     task_t owner;
>   };

Port rights are task based.  In Mach, every task has an ipc space
(and the kernel has one, too).  The port rights are managed in these
ipc spaces.  The port itself is not owned by a task (in Mach anyway), but
the task which ownes the receive right can be considered as the owner of the
port.  I guess this is just the orthogonal way of seeing it, but there might
be subtle problems shaking these relationships around.

A port is a message *queue*.  messages are enqueued until a mach_msg (trap)
is made to receive the next message on a port.  This can be seen as sending
an RPC to the receive port (for efficiency, and maybe other reasons, it's a
system trap in Mach).

You choose to ignore a main difference between Mach IPC and L4 IPC here.
IIRC, IPC in L4 always involves sending a message, blocking, and receiving a
reply.  In Mach, the send and receive are always seperate.

You emulate the normal RPC here this way:

A -> port server -> B -> +
|                        |
+--- port server <-------+

Where as in Mach, you would expect it to be more like this:

A -> port server <- B
|    |         |    |
+--<-+         +->--+

In Mach, MiG blocks for us.  I guess from the user site, by changing MiG,
you could make it do something like the above in the synchronous case
(I don't know if this has an advantage), although I have not yet
considered yet what you do about interrupting a message call (!).
However, it seems to me in the server side this would require some more
substantial work (although in the Hurd usually it is clear in libports when
RPCs are accepted and when not, but the generic part is not so easy).

Note that I am tending towards thinking how to get Mach IPC in L4 user space
completely.  This can not be the goal of L4, for performance reasons alone,
I think.  But maybe you can tradeoff some complexity by porting some
parts of the Hurd (libports), and I think this is what Thomas suggested. 
However, most features of Mach IPC are used in the Hurd somewhere, and for
that reason I think it is valid to first consider them all (and later make a
decision what can be dropped).

The two graphics above open two distinct ways to implement asynchronous
messages, btw (the first one requires the reply message to be a full
seperate message that goes the other way, while the second one already is
asynchronous by design, more like it is in Mach).

>   all_ports[MAX_PORTS];

Of course you don't really want a hard limit on the number of ports and port
rights, as long as there is memory.
  
>   struct port_right
>   {
>     unsigned port;
>     task_t owner; /* As above, perhaps a thread_id instead */
>     enum { normal, send_once, invalid } type;
>   };
>   
>   struct port_right
>   all_port_rights[MAX_PORT_RIGHTS];

To repeat, all send rights to a port in one task have the same port name.
I guess you were not careful enough to distinguish between ports,
port-rights and port names (a mistake easy enough to make, as the
documentation and the source often say "port" for "port name" etc).

> 1. It checks that the port-right is not out-of range, and that the originator 
> of the rpc matches the owner of the
>    port right.
> 
>      if (pr >= MAX_PORT_RIGHTS
>          || sender != all_port_rights[pr])
>        fail;

In Mach this would be: It checks that the port name in the tasks ipc space
is valid and denotes a receive right.  I don't see a good reason to do it
differently in L4.

> Is this service good enough? Does it provide the kind of port-right
> abstraction that the Hurd needs?

I think here the answer has to be no.  BTW, one interesting question for L4
is:  How do you prevent that a task sends its own, faked messages to the
server, circumventing the port right server.  In other words, how do you
enforce the port server.  This might involve some more RPCs the server has
to do with the port server.

Thanks,
Marcus

-- 
`Rhubarb is no Egyptian god.' Debian http://www.debian.org address@hidden
Marcus Brinkmann              GNU    http://www.gnu.org    address@hidden
address@hidden
http://www.marcus-brinkmann.de