Re: capabilities and client ids

[Marcus Brinkmann]

At Mon, 29 Nov 2004 10:34:56 +0000,
Neal H. Walfield wrote:
> As I understand client IDs, the entry that a server allocates in the
> current bucket's client_entry array serves as a client's client ID.

The client ID is, from the outside point of the system, just a token
of identification that the client provides.

> I
> don't understand what is won by using this as opposed to the task ID
> of the client.  It seems to be a gratuitous level of indirection which
> only introduces overhead.

The advantage of using a distinct ID that is allocated and managed by
the server is exactly that: The server can decide how client IDs are
allocated.

The server could just use the task ID, as you correctly point out.

The server could however also allocate client IDs differently, as I
implemented it.

I think that my implementation is simply more efficient at the
critical path, looking up a client ID.  task IDs are sparsely
allocated, and rarely reused.  Client IDs can be densely allocated and
reused quickly.

So, what is faster?  Looking up the client in a hash table by its task
ID, or looking up a client by its client ID and checking that the
client ID is correct?  Note that even in a hash table you need to
verify that you got the right entry (because of the potential of
collisions), so I think the latter approach is optimal, while the
former will often be the same, but can vary depending on how much
collisions occur.

My guidung principle in designing the cap library was to try to
provide some guaranteed maximum latency whereever possible.  This is
why I used tables, and not hashes, in the critical path.  I have not
reached my goal (and probably never will, because we are not aiming at
real time designs here), but at least this is the motivation behind
this.

Maybe the best argument in favor of encoding the client ID in the word
specifiying the capability is that it allows for different
implementations, while relying on the task ID restricts what you can
do in the server.  Even if we were to choose to use the task ID as the
client ID in the implementation, I would insist on passing the client
ID in the capability word, and verifying it against the sender's task
ID.

I have not considered very much if using a global identifier is a
problem for (orthogonal) persistency.  It may be another reason for
decoupling client IDs and task IDs.

> Having clients use their task id rather than their client id has two
> advantages for the client: it is another piece of information clients
> don't need to keep track of and it frees some bits in the message.  On
> the server side, this eliminates the check to make sure the client
> passed the right client ID.

I see it differently: Omitting the client ID means that the server
lacks some information it is going to need anyway, and needs to lock
it up itself based on the only information it has: the task/thread ID,
even if that happens to be not the best information to lookup the
client in any particular implementation.  Making it easier for the
client is not a design goal, but in fact I dispute even that: Why is
it easier for the client?  The client could just take the whole
capability word (client ID plus cap ID) as one opaque identifier.
However, by specifying that the client ID is encoded in the upper
bits, the client can in fact mostly ignore this information and make
certain assumptions (ie, that the id is the same for all caps from the
same server).

On the server side, the check can not be eliminated.  Either it is
explicit as in my table lookup, or it is implicit in your hash table
implementation.  You can't get rid of it, unless you do something
insensible like allocate a large table for all possible task IDs and
use just a mask and shift operation, like L4 does for thread IDs.
This is not good though, because the server does not control how task
IDs are allocated, and the way the task server will actually allocate
them will make such a "big table by task ID" infeasible.

It is true that there is a bijection between client IDs and task IDs
(at least it is true now, and I don't see a reason to have that
differently).  But this observation seems of only tangential relevance
here to me.

Thanks,
Marcus