Re: Capability object revocation

[Matthieu Lemerre]

"Neal H. Walfield" <address@hidden> writes:

> At Sat, 09 Apr 2005 22:55:02 +0100,
> Neal H. Walfield wrote:
>> To destroy a capability, you'll want to do the same as before except
>> revoke all capability entries and instead of calling
>> hurd_cap_obj_resume, call hurd_cap_obj_end.  As you'll notice
>> hurd_cap_obj_end is not yet implemented.  It should set OBJ->STATE to
>> _HURD_CAP_STATE_BLACK a la _hurd_cap_client_end and
>> _hurd_cap_bucket_end.  This is necessary because in,
>> e.g. manager_demuxer, after looking up the capability entry and
>> verifying that it is not dead, we wait until OBJ->STATE returns to
>> _GREEN but don't again check that the entry is not dead.
>
> This is incorrect.  We do verify that the object entry is not dead
> after checking OBJ->STATE (cf. line 284 of bucket-manage-mt.c).  As
> such, we don't need to implement hurd_cap_obj_end as I recommend
> above; just marking the capability entry as dead is sufficient.
>
> Thanks,
> Neal

Thank you Neal.

I wrote the below patch which implements all this.  I had to spend a
lot of time to fully understand when are all the references
incremented/decremented, but now I hope to better understand the
capability system.

I have to make a couple of observations:

-Newly-created object are allocated with one refererence. When they
 are injected in a bucket, one more reference is added (which is fully
 understandable).

So we once the object in injected in the bucket, we have to drop it.

One problem is that bucket_inject wants an unlocked object, and then
lock it. 

Wouldn't it be possible to create the object with no references in it?
When it is in no bucket, only the creating function is going to use it
anyway, so it would be much simpler.

We could also drop the extra reference in obj-revoke or obj-destroy,
but in this case we have to change the initialisation code (for
instance in task.c/create_bootstrap_caps) so that it does not drop one
reference.

-I had to remove some asserts to get this patch to work, but I still
 hope that my patch is correct.  Bucket-manage-mt assumed that you
 could not revoke a capability object while there is a RPC on it; but
 I don't know how I can do it in another way (I mean, we have to do a
 RPC on the capability object to say to revoke it.  Or maybe I should
 have used a root capability object?)

So when hurd_cap_obj_destroy is called, it removes every external
references to the entries in every client (and as many internal
references as there were external references) (eventually deallocating
the entries if there were no pending RPCs on it) , and when the
function return, bucket-manage-mt will dealloc the entry when it drops
its own reference.

-I think I still have to change ctx-cap-use to use the
 hurd_cap_obj_entry_release function.  I will do if you find that my
 patch is correct.  And, I'm waiting for Marcus's agreement on Neal's
 proposal for speeding research up to enhance the patch.
 
The patch relies on the previous one I sent on the mailing list, which
modified obj-copy-out.c to work.

Here's the associated Changelog for libhurd-cap-server:

2005-04-15  Matthieu Lemerre  <address@hidden>

        * obj-revoke.c : New file.
        * obj-entry-drop-release.c : New file.
        * obj-destroy.c : New file.
        * cap-server.h (hurd_cap_obj_revoke): New declaration.
        (hurd_cap_obj_destroy): New declaration.
        * cap-server-intern.h (_hurd_cap_obj_entry_drop): New declaration.
        (_hurd_cap_obj_entry_release): New declaration.
        * bucket-manage-mt.c (manage_demuxer): Use _hurd_cap_obj_entry_release.
        * Makefile.am (libhurd_cap_server_a_SOURCES): Add obj-revoke.c,
        obj-entry-drop-release.c, obj-destroy.c.


diff -Nup 
/home/racin/src/hurd/mainline/darcs/hurd-l4/libhurd-cap-server/ChangeLog 
hurd-l4/libhurd-cap-server/ChangeLog
--- /home/racin/src/hurd/mainline/darcs/hurd-l4/libhurd-cap-server/ChangeLog    
2005-03-12 03:21:10.000000000 +0100
+++ hurd-l4/libhurd-cap-server/ChangeLog        2005-04-15 01:59:27.695342136 
+0200
@@ -1,3 +1,16 @@
+2005-04-15  Matthieu Lemerre  <address@hidden>
+
+       * obj-revoke.c : New file.
+       * obj-entry-drop-release.c : New file.
+       * obj-destroy.c : New file.
+       * cap-server.h (hurd_cap_obj_revoke): New declaration.
+       (hurd_cap_obj_destroy): New declaration.
+       * cap-server-intern.h (_hurd_cap_obj_entry_drop): New declaration.
+       (_hurd_cap_obj_entry_release): New declaration.
+       * bucket-manage-mt.c (manage_demuxer): Use _hurd_cap_obj_entry_release.
+       * Makefile.am (libhurd_cap_server_a_SOURCES): Add obj-revoke.c,
+       obj-entry-drop-release.c, obj-destroy.c
+
 2005-03-08  Neal H. Walfield  <address@hidden>
 
        * Makefile.am (libhurd_cap_server_a_SOURCES): Add ctx-cap-use.c.
diff -Nup 
/home/racin/src/hurd/mainline/darcs/hurd-l4/libhurd-cap-server/Makefile.am 
hurd-l4/libhurd-cap-server/Makefile.am
--- /home/racin/src/hurd/mainline/darcs/hurd-l4/libhurd-cap-server/Makefile.am  
2005-03-12 03:21:10.000000000 +0100
+++ hurd-l4/libhurd-cap-server/Makefile.am      2005-04-14 21:14:33.693025488 
+0200
@@ -34,7 +34,8 @@ libhurd_cap_server_a_SOURCES = table.h t
        class-destroy.c class-free.c                                    \
        class-alloc.c class-inhibit.c                                   \
        obj-dealloc.c obj-drop.c obj-inhibit.c                          \
-       obj-entry-space.c obj-copy-out.c                                \
+       obj-revoke.c obj-destroy.c                                      \
+       obj-entry-space.c obj-copy-out.c obj-entry-drop-release.c       \
        client-create.c client-release.c client-inhibit.c               \
        bucket-create.c bucket-free.c bucket-inhibit.c                  \
        bucket-manage-mt.c bucket-worker-alloc.c bucket-inject.c        \
diff -Nup 
/home/racin/src/hurd/mainline/darcs/hurd-l4/libhurd-cap-server/bucket-manage-mt.c
 hurd-l4/libhurd-cap-server/bucket-manage-mt.c
--- 
/home/racin/src/hurd/mainline/darcs/hurd-l4/libhurd-cap-server/bucket-manage-mt.c
   2005-03-12 03:21:10.000000000 +0100
+++ hurd-l4/libhurd-cap-server/bucket-manage-mt.c       2005-04-14 
22:22:50.730181168 +0200
@@ -333,15 +333,8 @@ manage_demuxer (hurd_cap_rpc_context_t c
   _hurd_cap_list_item_remove (&worker_client);
   _hurd_cap_client_cond_check (bucket, client);
 
-  /* You are not allowed to revoke a capability while there are
-     pending RPCs on it.  This is the reason why we know that there
-     must be at least one extra internal reference.  FIXME: For
-     cleanliness, this could still call some inline function that does
-     the decrement.  The assert can be a hint to the compiler to
-     optimize the inline function expansion anyway.  */
-  assert (!obj_entry->dead);
-  assert (obj_entry->internal_refs > 1);
-  obj_entry->internal_refs--;
+  _hurd_cap_obj_entry_release (obj_entry);
+  
   pthread_mutex_unlock (&client->lock);
 
   _hurd_cap_client_release (bucket, client->id);
diff -Nup 
/home/racin/src/hurd/mainline/darcs/hurd-l4/libhurd-cap-server/cap-server-intern.h
 hurd-l4/libhurd-cap-server/cap-server-intern.h
--- 
/home/racin/src/hurd/mainline/darcs/hurd-l4/libhurd-cap-server/cap-server-intern.h
  2005-03-12 03:21:10.000000000 +0100
+++ hurd-l4/libhurd-cap-server/cap-server-intern.h      2005-04-14 
21:39:07.177021872 +0200
@@ -221,6 +221,22 @@ error_t _hurd_cap_obj_copy_out (hurd_cap
                                _hurd_cap_client_t client, _hurd_cap_id_t *r_id)
      __attribute__((visibility("hidden")));
 
+/* Drop all references to the capability object entry ENTRY, except
+   the (potential) one used by the bucket manager.  Dealloc ENTRY if
+   needed.  The corresponding client and capability object must be
+   locked, and the RPCs on the capability object must be
+   inhibited.  */
+void
+_hurd_cap_obj_entry_drop (_hurd_cap_obj_entry_t entry);
+  
+/* Release one (internal) reference for the capability object entry
+   ENTRY.  If there is no more internal references, then the object
+   entry is deallocated.  The corresponding client and capability object
+   must be locked, and the RPCs on the capability object must be
+   inhibited.  */
+void
+_hurd_cap_obj_entry_release (_hurd_cap_obj_entry_t entry);
+
 
 /* Client connections. */
 
diff -Nup 
/home/racin/src/hurd/mainline/darcs/hurd-l4/libhurd-cap-server/cap-server.h 
hurd-l4/libhurd-cap-server/cap-server.h
--- /home/racin/src/hurd/mainline/darcs/hurd-l4/libhurd-cap-server/cap-server.h 
2005-03-12 03:21:10.000000000 +0100
+++ hurd-l4/libhurd-cap-server/cap-server.h     2005-04-14 21:38:54.892889344 
+0200
@@ -458,6 +458,19 @@ error_t hurd_cap_obj_inhibit (hurd_cap_o
    waiters.  */
 void hurd_cap_obj_resume (hurd_cap_obj_t obj);
 
+
+/* Revoke the capability object OBJ, which must not be locked.  The
+   capability is removed from all the clients table which holded the
+   capability, except the client calling this function.  */
+void
+hurd_cap_obj_revoke (hurd_cap_obj_t obj, hurd_cap_rpc_context_t ctx);
+
+/* Destroy the capability object OBJ, which must not be locked.  The
+   capability is removed from all the clients table which hold the
+   capability.  */
+void
+hurd_cap_obj_destroy (hurd_cap_obj_t obj);
+
 
 /* Buckets are a set of capabilities, on which RPCs are managed
    collectively.  */
diff -Nup 
/home/racin/src/hurd/mainline/darcs/hurd-l4/libhurd-cap-server/obj-destroy.c 
hurd-l4/libhurd-cap-server/obj-destroy.c
--- 
/home/racin/src/hurd/mainline/darcs/hurd-l4/libhurd-cap-server/obj-destroy.c    
    1970-01-01 01:00:00.000000000 +0100
+++ hurd-l4/libhurd-cap-server/obj-destroy.c    2005-04-14 20:06:45.884426392 
+0200
@@ -0,0 +1,59 @@
+/* obj-destroy.c - Destroy a capability object.
+   Copyright (C) 2005 Free Software Foundation, Inc.
+   Written by Matthieu Lemerre <address@hidden>
+
+   This file is part of the GNU Hurd.
+
+   This program is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful, but
+   WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with this program; if not, write to the Free
+   Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+   02111-1307 USA.  */
+
+#if HAVE_CONFIG_H
+#include <config.h>
+#endif
+
+#include "cap-server-intern.h"
+
+
+/* Destroy the capability object OBJ, which must not be locked.  The
+   capability is removed from all the clients table which hold the
+   capability.  */
+void
+hurd_cap_obj_destroy (hurd_cap_obj_t obj)
+{
+  hurd_cap_obj_inhibit (obj);
+  assert (obj->state == _HURD_CAP_STATE_RED);
+
+  /* For each client, remove the entry for OBJ.  */
+  _hurd_cap_list_item_t client_item = obj->clients;
+  
+  while (client_item)
+    {
+      _hurd_cap_client_t client = client_item->client;
+      _hurd_cap_obj_entry_t entry;
+
+      pthread_mutex_lock (&client->lock);
+      entry = (_hurd_cap_obj_entry_t) hurd_ihash_find (&client->caps_reverse,
+                                                      (hurd_ihash_key_t) obj);
+      assert (entry);
+
+      _hurd_cap_obj_entry_drop (entry);
+      pthread_mutex_unlock (&client->lock);
+
+      client_item = client_item->next;
+    }      
+
+  obj->clients = NULL;
+  hurd_cap_obj_resume (obj);
+}
diff -Nup 
/home/racin/src/hurd/mainline/darcs/hurd-l4/libhurd-cap-server/obj-entry-drop-release.c
 hurd-l4/libhurd-cap-server/obj-entry-drop-release.c
--- 
/home/racin/src/hurd/mainline/darcs/hurd-l4/libhurd-cap-server/obj-entry-drop-release.c
     1970-01-01 01:00:00.000000000 +0100
+++ hurd-l4/libhurd-cap-server/obj-entry-drop-release.c 2005-04-14 
22:54:09.783521640 +0200
@@ -0,0 +1,101 @@
+/* obj-entry-drop-release.c - Drop or release a capability object
+   entry.
+   Copyright (C) 2005 Free Software Foundation, Inc.
+   Written by Matthieu Lemerre <address@hidden>
+
+   This file is part of the GNU Hurd.
+
+   This program is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful, but
+   WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with this program; if not, write to the Free
+   Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+   02111-1307 USA.  */
+
+#if HAVE_CONFIG_H
+#include <config.h>
+#endif
+
+#include <errno.h>
+
+#include "cap-server-intern.h"
+
+
+
+/* Deallocate the object entry from capability object entries' slab
+   space.  */
+void
+_hurd_cap_obj_entry_dealloc (_hurd_cap_obj_entry_t entry)
+{
+  int found;
+  _hurd_cap_client_t client = entry->client_item.client;
+  hurd_cap_obj_t obj = entry->cap_obj;
+
+  /* Reinitialize the object entry for future reallocation.  */
+  entry->dead = 0;
+  entry->internal_refs = 1;
+  entry->external_refs = 1;
+
+  hurd_table_remove (&client->caps, entry->id);
+  found = hurd_ihash_remove (&client->caps_reverse,
+                            (hurd_ihash_key_t) obj);
+  assert (found);
+
+  /* Deallocate the object entry from capability object entries' slab
+     space.  */
+  hurd_slab_dealloc (&_hurd_cap_obj_entry_space, entry);
+
+  /* Now drop the reference to the capability object.  */
+  hurd_cap_obj_drop (obj);
+}
+
+/* Release one (internal) reference for the capability object entry
+   ENTRY.  If there is no more internal references, then the object
+   entry is deallocated.  The corresponding client and capability
+   object must be locked.  */
+void
+_hurd_cap_obj_entry_release (_hurd_cap_obj_entry_t entry)
+{
+  entry->internal_refs --;
+  if (entry->internal_refs == 0)
+    {
+      /* There is no need for the capability object to be inhibited,
+        because the internal reference comes to 0, that is to say
+        that the capability entry can be accessed only by the current
+        caller.  */
+      hurd_cap_obj_inhibit (entry->cap_obj);
+      _hurd_cap_obj_entry_dealloc (entry);
+      hurd_cap_obj_resume (entry->cap_obj);
+    }
+}
+
+/* Drop all references to the capability object entry ENTRY, except
+   the (potential) one used by the bucket manager.  Dealloc ENTRY if
+   needed.  The corresponding client and capability object must be
+   locked, and the RPCs on the capability object must be
+   inhibited.  */
+void
+_hurd_cap_obj_entry_drop (_hurd_cap_obj_entry_t entry)
+{
+  entry->internal_refs -= entry->external_refs;
+  
+  if (entry->internal_refs)
+    {
+      entry->dead = 1;
+      
+      /* There is still one pending RPC on the capability.  */
+      assert (entry->internal_refs == 1);
+
+      /* The entry will be cleaned when the RPC is finished.  */
+    }
+  else
+    _hurd_cap_obj_entry_dealloc (entry);
+}
diff -Nup 
/home/racin/src/hurd/mainline/darcs/hurd-l4/libhurd-cap-server/obj-revoke.c 
hurd-l4/libhurd-cap-server/obj-revoke.c
--- /home/racin/src/hurd/mainline/darcs/hurd-l4/libhurd-cap-server/obj-revoke.c 
1970-01-01 01:00:00.000000000 +0100
+++ hurd-l4/libhurd-cap-server/obj-revoke.c     2005-04-14 21:15:54.214784320 
+0200
@@ -0,0 +1,68 @@
+/* obj-revoke.c - Revoke a capability object.
+   Copyright (C) 2005 Free Software Foundation, Inc.
+   Written by Matthieu Lemerre <address@hidden>
+
+   This file is part of the GNU Hurd.
+
+   This program is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful, but
+   WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with this program; if not, write to the Free
+   Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+   02111-1307 USA.  */
+
+#if HAVE_CONFIG_H
+#include <config.h>
+#endif
+
+#include "cap-server-intern.h"
+
+
+/* Revoke the capability object OBJ, which must not be locked.  The
+   capability is removed from all the clients table which holded the
+   capability, except the client calling this function.  */
+void
+hurd_cap_obj_revoke (hurd_cap_obj_t obj, hurd_cap_rpc_context_t ctx)
+{
+  hurd_cap_obj_inhibit (obj);
+  assert (obj->state == _HURD_CAP_STATE_RED);
+
+  _hurd_cap_list_item_t client_item = obj->clients;
+  _hurd_cap_list_item_t kept_client_item = NULL;
+  
+  while (client_item)
+    {
+      _hurd_cap_client_t client = client_item->client;
+      
+      if (client == ctx->client)
+       {
+         kept_client_item = client_item;
+       }
+      else
+       {
+         _hurd_cap_obj_entry_t entry;
+         
+         pthread_mutex_lock (&client->lock);
+         entry = (_hurd_cap_obj_entry_t) hurd_ihash_find 
(&client->caps_reverse,
+                                                          (hurd_ihash_key_t) 
obj);
+         assert (entry);
+         
+         _hurd_cap_obj_entry_drop (entry);
+         pthread_mutex_unlock (&client->lock);
+       }
+      
+      client_item = client_item->next;
+    }
+
+  assert (kept_client_item);
+  obj->clients = kept_client_item;
+  hurd_cap_obj_resume (obj);
+}


Thanks,
Matthieu