Re: capabilities and client ids

[Neal H. Walfield]

At Wed, 01 Dec 2004 00:28:09 +0100,
Marcus Brinkmann wrote:
> 
> 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.

As we discussed off line these are semantics that a server may
introduce to a capability handle.  As far as a client is concerned, a
capability handle is an opaque work.  It so happens that the current
libhurd-cap-server separates the capability handle into a client id
and a capability id, however, this is only useful for the server.
This change was introduced in hurd and libhurd-cap-server.  The start
of the ChangeLog for the latter is:

2004-12-01  Neal H. Walfield  <address@hidden>

        * cap-server-intern.h (_HURD_CAP_CLIENT_ID_BITS): Move from
        ../hurd/types.h.  Prepend underscore and update names in
        definition as needed.

> 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.

Given how deeply ingrained the thread ids are in the implemetnation
(both client and server side), I do not think that this can help
unless the client ids are always used instead of task ids.

> 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).

Nevertheless, a client must be prepared for anything a server may give
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.

I might accept this line of argumentation if you could demonstrate
that doing a look up in a hash is significantly more expensive than
looking up up an element in a table.  I agree that it is marginally
more expensive (in terms of CPU time---it is often cheaper in terms of
memory usage).  I am not, however, convinced that this look up
(bucket-manage-mt.c:lookup_client) is even close to the bottle neck:
at most it saves a few memory references.  Either way, we still have
to do a look up in a hash in the fast path to make sure that the
calling thread does not have any extant rpcs; we may have to do some
allocation including that of a new worker thread and hurd_ihash_add to
add the sender to the list of senders, which are potentially very
slow; and there are several condition variables we may have to wait
for.  The very real memory cost introduced by the table just does not
justify for me the few cycles which we can save.

> 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.

However, it does mean that we can unify the client entry
(_hurd_cap_client_entry_t) and client (_hurd_cap_client_t) data
structures thereby eliminating a level of indirection.  The attached
patch does this.  Let me know if it is all right.

Neal

2004-12-01  Neal H. Walfield  <address@hidden>

        * cap-server-intern.h (struct _hurd_cap_client): Fold the struct
        _hurd_cap_client_entry into the struct _hurd_cap_client.
        * bucket-create.c (_hurd_cap_client_death): Change all uses of
        _hurd_cap_client_entry_t to use the merged _hurd_cap_client_t.
        (hurd_cap_bucket_create): Likewise.
        * bucket-manage-mt.c (lookup_client): Likewise.
        * client-create.c (_hurd_cap_client_create): Likewise.
        * client-release.c (_hurd_cap_client_release): Likewise.

Index: cap-server-intern.h
===================================================================
RCS file: /cvsroot/hurd/hurd-l4/libhurd-cap-server/cap-server-intern.h,v
retrieving revision 1.10
diff -u -p -r1.10 cap-server-intern.h
--- cap-server-intern.h 1 Dec 2004 18:12:20 -0000       1.10
+++ cap-server-intern.h 1 Dec 2004 22:05:04 -0000
@@ -224,10 +224,29 @@ error_t _hurd_cap_obj_copy_out (hurd_cap
 
 /* Client connections. */
 
-/* This data type holds all the information about a client
+
+/* Instances of the following data type are pointed to by the client
+   table of a bucket.  Its members are protected by the same lock as
+   the table.  The data type holds all the information about a client
    connection.  */
 struct _hurd_cap_client
 {
+  /* A flag that indicates if this capability client is dead.  This
+     data structure is valid until all references have been removed,
+     though.  Note that because there is one reference for the task
+     info capability, this means that CLIENT is valid until a task
+     death notification has been processed for this client.  Protected
+     by the containing bucket's lock LOCK. */
+  unsigned int dead : 1;
+
+  /* Reference counter.  A reference is held if the client is live
+     (and removed by the task death handler).  One reference is held
+     by each pending RPC.  Temporarily, additional references may be
+     held by RPCs that have just started, but they will rip themselves
+     when they see the DEAD flag.  Protected by the containing
+     bucket's lock LOCK.  */
+  unsigned int refs : 31;
+
   /* The task ID of the client.  */
   hurd_task_id_t task_id;
 
@@ -324,31 +343,6 @@ void _hurd_cap_client_end (hurd_cap_buck
      __attribute__((visibility("hidden")));
 
 
-/* The following data type is used as an entry in the client table of
-   a bucket.  Its members are protected by the same lock as the
-   table.  */
-struct _hurd_cap_client_entry
-{
-  /* This pointer has to be the first element of the struct.  */
-  _hurd_cap_client_t client;
-
-  /* A flag that indicates if this capability client is dead.  CLIENT
-     is valid until all references have been removed, though.  Note
-     that because there is one reference for the task info capability,
-     this means that CLIENT is valid until a task death notification
-     has been processed for this client.  */
-  unsigned int dead : 1;
-
-  /* Reference counter.  There is one reference for the fact that the
-     child lives, and one reference for each pending RPC.
-     Temporarily, there can be additional references for RPC that have
-     just yet started, but they will rip themselves when they see the
-     DEAD flag.  */
-  unsigned int refs : 31;
-};
-typedef struct _hurd_cap_client_entry *_hurd_cap_client_entry_t;
-
-
 /* Buckets are a set of capabilities, on which RPCs are managed
    collectively.  */
 
@@ -431,7 +425,7 @@ struct _hurd_cap_bucket
      to just one RPC at one time.  */
   struct hurd_ihash senders;
 
-  /* Mapping from hurd_cap_client_id_t to _hurd_cap_client_entry_t.  */
+  /* Mapping from hurd_cap_client_id_t to _hurd_cap_client_t.  */
   struct hurd_table clients;
 
   /* Reverse lookup from hurd_task_id_t to _hurd_cap_client_t.  */
Index: bucket-create.c
===================================================================
RCS file: /cvsroot/hurd/hurd-l4/libhurd-cap-server/bucket-create.c,v
retrieving revision 1.5
diff -u -p -r1.5 bucket-create.c
--- bucket-create.c     30 Nov 2004 10:25:39 -0000      1.5
+++ bucket-create.c     1 Dec 2004 22:05:05 -0000
@@ -37,7 +37,6 @@ _hurd_cap_client_death (void *hook, hurd
 {
   hurd_cap_bucket_t bucket = (hurd_cap_bucket_t) hook;
   _hurd_cap_client_t client;
-  _hurd_cap_client_entry_t entry;
 
   pthread_mutex_lock (&bucket->lock);
   client = (_hurd_cap_client_t) hurd_ihash_find (&bucket->clients_reverse,
@@ -50,9 +49,7 @@ _hurd_cap_client_death (void *hook, hurd
         extra reference now.  However, we must mark the client entry
         as dead, so that no further references are acquired by
         anybody else.  */
-      entry = (_hurd_cap_client_entry_t)
-       HURD_TABLE_LOOKUP (&bucket->clients, client->id);
-      entry->dead = 1;
+      client->dead = 1;
     }
   pthread_mutex_unlock (&bucket->lock);
 
@@ -75,13 +72,8 @@ _hurd_cap_client_death (void *hook, hurd
 
 #ifndef NDEBUG
       pthread_mutex_lock (&bucket->lock);
-      /* Reacquire the table entry for this client.  Table entry
-        addresses are not stable under table resize operations.  */
-      entry = (_hurd_cap_client_entry_t)
-       HURD_TABLE_LOOKUP (&bucket->clients, client->id);
-
       /* Now, we should have the last reference for this client.  */
-      assert (entry->refs == 1);
+      assert (client->refs == 1);
       pthread_mutex_unlock (&bucket->lock);
 #endif
 
@@ -143,7 +135,7 @@ hurd_cap_bucket_create (hurd_cap_bucket_
                   offsetof (struct _hurd_cap_list_item, locp));
 
   err = hurd_table_init (&bucket->clients,
-                        sizeof (struct _hurd_cap_client_entry));
+                        sizeof (_hurd_cap_client_t));
   if (err)
     goto err_clients;
 
Index: bucket-manage-mt.c
===================================================================
RCS file: /cvsroot/hurd/hurd-l4/libhurd-cap-server/bucket-manage-mt.c,v
retrieving revision 1.14
diff -u -p -r1.14 bucket-manage-mt.c
--- bucket-manage-mt.c  1 Dec 2004 18:12:20 -0000       1.14
+++ bucket-manage-mt.c  1 Dec 2004 22:05:07 -0000
@@ -101,17 +101,17 @@ lookup_client (hurd_cap_bucket_t bucket,
               hurd_task_id_t task_id, _hurd_cap_client_t *r_client)
 {
   error_t err = 0;
-  _hurd_cap_client_entry_t entry;
+  _hurd_cap_client_t *clientp;
 
   pthread_mutex_lock (&bucket->lock);
   /* Look up the client by its ID.  */
-  entry = hurd_table_lookup (&bucket->clients, client_id);
-  if (!entry || entry->dead || entry->client->task_id != task_id)
+  clientp = hurd_table_lookup (&bucket->clients, client_id);
+  if (!clientp || (*clientp)->dead || (*clientp)->task_id != task_id)
     err = ECAP_NOREPLY;
   else
     {
-      entry->refs++;
-      *r_client = entry->client;
+      (*clientp)->refs++;
+      *r_client = *clientp;
     }
   pthread_mutex_unlock (&bucket->lock);
 
@@ -166,7 +166,7 @@ manage_demuxer (hurd_cap_rpc_context_t c
     return err;
 
   /* At this point, CLIENT_ID and CLIENT are valid, and we have one
-     reference for the client entry.  */
+     reference for the client.  */
 
   pthread_mutex_lock (&client->lock);
   /* First, we have to check if the class is inhibited, and if it is,
@@ -296,10 +296,10 @@ manage_demuxer (hurd_cap_rpc_context_t c
   /* At this point, we have looked up the capability, acquired an
      internal reference for its entry in the client table (which
      implicitely keeps a reference acquired for the object itself),
-     acquired a reference for the capability client entry in the
-     bucket, and have added an item to the pending_rpcs lists in the
-     client, class and object.  The object is locked.  With all this,
-     we can finally start to process the message for real.  */
+     acquired a reference for the capability client in the bucket, and
+     have added an item to the pending_rpcs lists in the client, class
+     and object.  The object is locked.  With all this, we can finally
+     start to process the message for real.  */
 
   /* FIXME: Call the internal demuxer here, for things like reference
      counter modification, cap passing etc.  */
Index: client-create.c
===================================================================
RCS file: /cvsroot/hurd/hurd-l4/libhurd-cap-server/client-create.c,v
retrieving revision 1.8
diff -u -p -r1.8 client-create.c
--- client-create.c     1 Dec 2004 18:12:20 -0000       1.8
+++ client-create.c     1 Dec 2004 22:05:07 -0000
@@ -128,22 +128,18 @@ _hurd_cap_client_create (hurd_cap_bucket
 {
   error_t err = 0;
   _hurd_cap_client_t client;
-  _hurd_cap_client_entry_t entry;
-  struct _hurd_cap_client_entry new_entry;
 
   pthread_mutex_lock (&bucket->lock);
   client = (_hurd_cap_client_t) hurd_ihash_find (&bucket->clients_reverse,
                                                 task_id);
   if (client)
     {
-      entry = (_hurd_cap_client_entry_t)
-       HURD_TABLE_LOOKUP (&bucket->clients, client->id);
-      if (entry->dead)
+      if (client->dead)
        err = EINVAL;   /* FIXME: A more appropriate code?  */
       else
        {
-         entry->refs++;
-         *r_client = entry->client;
+         client->refs++;
+         *r_client = client;
        }
       pthread_mutex_unlock (&bucket->lock);
       return err;
@@ -171,9 +167,7 @@ _hurd_cap_client_create (hurd_cap_bucket
                                                 task_id);
   if (client)
     {
-      entry = (_hurd_cap_client_entry_t)
-       HURD_TABLE_LOOKUP (&bucket->clients, client->id);
-      if (entry->dead)
+      if (client->dead)
        {
          err = EINVAL; /* FIXME: A more appropriate code?  */
          pthread_mutex_unlock (&bucket->lock);
@@ -181,23 +175,21 @@ _hurd_cap_client_create (hurd_cap_bucket
       else
        {
          /* Somebody else was indeed faster.  Use the existing entry.  */
-         entry->refs++;
+         client->refs++;
          pthread_mutex_unlock (&bucket->lock);
          _hurd_cap_client_dealloc (bucket, *r_client);
-         *r_client = entry->client;
+         *r_client = client;
        }
       return err;
     }
 
   client = *r_client;
 
-  /* Enter the new client.  */
-  new_entry.client = client;
   /* One reference for the fact that the client task lives, one for
      the caller. */
-  new_entry.refs = 2;
+  client->refs = 2;
 
-  err = hurd_table_enter (&bucket->clients, &new_entry, &client->id);
+  err = hurd_table_enter (&bucket->clients, &client, &client->id);
   if (!err)
     {
       err = hurd_ihash_add (&bucket->clients_reverse, task_id, client);
Index: client-release.c
===================================================================
RCS file: /cvsroot/hurd/hurd-l4/libhurd-cap-server/client-release.c,v
retrieving revision 1.6
diff -u -p -r1.6 client-release.c
--- client-release.c    1 Dec 2004 18:12:20 -0000       1.6
+++ client-release.c    1 Dec 2004 22:05:07 -0000
@@ -166,26 +166,23 @@ _hurd_cap_client_dealloc (hurd_cap_bucke
 }
 
 
-/* Release a reference for the client with the ID IDX in class
-   CLASS.  */
+/* Release a reference for the client with the ID IDX in bucket
+   BUCKET.  */
 void
 _hurd_cap_client_release (hurd_cap_bucket_t bucket, _hurd_cap_client_id_t idx)
 {
-  _hurd_cap_client_entry_t entry;
+  _hurd_cap_client_t client;
 
   pthread_mutex_lock (&bucket->lock);
-  entry = (_hurd_cap_client_entry_t) HURD_TABLE_LOOKUP (&bucket->clients,
-                                                       idx);
+  client = *(_hurd_cap_client_t *) HURD_TABLE_LOOKUP (&bucket->clients, idx);
 
-  if (EXPECT_TRUE (entry->refs > 1))
+  if (EXPECT_TRUE (client->refs > 1))
     {
-      entry->refs--;
+      client->refs--;
       pthread_mutex_unlock (&bucket->lock);
     }
   else
     {
-      _hurd_cap_client_t client = entry->client;
-
       hurd_table_remove (&bucket->clients, idx);
       hurd_ihash_locp_remove (&bucket->clients_reverse, client->locp);