[PATCH 1/6] KEYS: Deal with dead-type keys appropriately [ver #2]

[PATCH 1/6] KEYS: Deal with dead-type keys appropriately [ver #2]

[David Howells]

Allow keys for which the key type has been removed to be unlinked.  Currently
dead-type keys can only be disposed of by completely clearing the keyrings
that point to them.

Signed-off-by: David Howells <dhowells@redhat.com>
Acked-by: Serge Hallyn <serue@us.ibm.com>
---

 security/keys/internal.h     |    5 +++-
 security/keys/key.c          |    6 ++---
 security/keys/keyctl.c       |   50 ++++++++++++++++++++++++------------------
 security/keys/process_keys.c |   18 +++++++++++----
 4 files changed, 48 insertions(+), 31 deletions(-)


diff --git a/security/keys/internal.h b/security/keys/internal.h
index 9fb679c..a7252e7 100644
--- a/security/keys/internal.h
+++ b/security/keys/internal.h
@@ -124,8 +124,11 @@ extern struct key *request_key_and_link(struct key_type *type,
 					struct key *dest_keyring,
 					unsigned long flags);
 
-extern key_ref_t lookup_user_key(key_serial_t id, int create, int partial,
+extern key_ref_t lookup_user_key(key_serial_t id, unsigned long flags,
 				 key_perm_t perm);
+#define KEY_LOOKUP_CREATE	0x01
+#define KEY_LOOKUP_PARTIAL	0x02
+#define KEY_LOOKUP_FOR_UNLINK	0x04
 
 extern long join_session_keyring(const char *name);
 
diff --git a/security/keys/key.c b/security/keys/key.c
index 4a1297d..3762d5b 100644
--- a/security/keys/key.c
+++ b/security/keys/key.c
@@ -642,10 +642,8 @@ struct key *key_lookup(key_serial_t id)
 	goto error;
 
  found:
-	/* pretend it doesn't exist if it's dead */
-	if (atomic_read(&key->usage) == 0 ||
-	    test_bit(KEY_FLAG_DEAD, &key->flags) ||
-	    key->type == &key_type_dead)
+	/* pretend it doesn't exist if it is awaiting deletion */
+	if (atomic_read(&key->usage) == 0)
 		goto not_found;
 
 	/* this races with key_put(), but that doesn't matter since key_put()
diff --git a/security/keys/keyctl.c b/security/keys/keyctl.c
index 7f09fb8..b85ace2 100644
--- a/security/keys/keyctl.c
+++ b/security/keys/keyctl.c
@@ -103,7 +103,7 @@ SYSCALL_DEFINE5(add_key, const char __user *, _type,
 	}
 
 	/* find the target keyring (which must be writable) */
-	keyring_ref = lookup_user_key(ringid, 1, 0, KEY_WRITE);
+	keyring_ref = lookup_user_key(ringid, KEY_LOOKUP_CREATE, KEY_WRITE);
 	if (IS_ERR(keyring_ref)) {
 		ret = PTR_ERR(keyring_ref);
 		goto error3;
@@ -185,7 +185,8 @@ SYSCALL_DEFINE4(request_key, const char __user *, _type,
 	/* get the destination keyring if specified */
 	dest_ref = NULL;
 	if (destringid) {
-		dest_ref = lookup_user_key(destringid, 1, 0, KEY_WRITE);
+		dest_ref = lookup_user_key(destringid, KEY_LOOKUP_CREATE,
+					   KEY_WRITE);
 		if (IS_ERR(dest_ref)) {
 			ret = PTR_ERR(dest_ref);
 			goto error3;
@@ -233,9 +234,11 @@ SYSCALL_DEFINE4(request_key, const char __user *, _type,
 long keyctl_get_keyring_ID(key_serial_t id, int create)
 {
 	key_ref_t key_ref;
+	unsigned long lflags;
 	long ret;
 
-	key_ref = lookup_user_key(id, create, 0, KEY_SEARCH);
+	lflags = create ? KEY_LOOKUP_CREATE : 0;
+	key_ref = lookup_user_key(id, lflags, KEY_SEARCH);
 	if (IS_ERR(key_ref)) {
 		ret = PTR_ERR(key_ref);
 		goto error;
@@ -309,7 +312,7 @@ long keyctl_update_key(key_serial_t id,
 	}
 
 	/* find the target key (which must be writable) */
-	key_ref = lookup_user_key(id, 0, 0, KEY_WRITE);
+	key_ref = lookup_user_key(id, 0, KEY_WRITE);
 	if (IS_ERR(key_ref)) {
 		ret = PTR_ERR(key_ref);
 		goto error2;
@@ -337,7 +340,7 @@ long keyctl_revoke_key(key_serial_t id)
 	key_ref_t key_ref;
 	long ret;
 
-	key_ref = lookup_user_key(id, 0, 0, KEY_WRITE);
+	key_ref = lookup_user_key(id, 0, KEY_WRITE);
 	if (IS_ERR(key_ref)) {
 		ret = PTR_ERR(key_ref);
 		goto error;
@@ -363,7 +366,7 @@ long keyctl_keyring_clear(key_serial_t ringid)
 	key_ref_t keyring_ref;
 	long ret;
 
-	keyring_ref = lookup_user_key(ringid, 1, 0, KEY_WRITE);
+	keyring_ref = lookup_user_key(ringid, KEY_LOOKUP_CREATE, KEY_WRITE);
 	if (IS_ERR(keyring_ref)) {
 		ret = PTR_ERR(keyring_ref);
 		goto error;
@@ -389,13 +392,13 @@ long keyctl_keyring_link(key_serial_t id, key_serial_t ringid)
 	key_ref_t keyring_ref, key_ref;
 	long ret;
 
-	keyring_ref = lookup_user_key(ringid, 1, 0, KEY_WRITE);
+	keyring_ref = lookup_user_key(ringid, KEY_LOOKUP_CREATE, KEY_WRITE);
 	if (IS_ERR(keyring_ref)) {
 		ret = PTR_ERR(keyring_ref);
 		goto error;
 	}
 
-	key_ref = lookup_user_key(id, 1, 0, KEY_LINK);
+	key_ref = lookup_user_key(id, KEY_LOOKUP_CREATE, KEY_LINK);
 	if (IS_ERR(key_ref)) {
 		ret = PTR_ERR(key_ref);
 		goto error2;
@@ -423,13 +426,13 @@ long keyctl_keyring_unlink(key_serial_t id, key_serial_t ringid)
 	key_ref_t keyring_ref, key_ref;
 	long ret;
 
-	keyring_ref = lookup_user_key(ringid, 0, 0, KEY_WRITE);
+	keyring_ref = lookup_user_key(ringid, 0, KEY_WRITE);
 	if (IS_ERR(keyring_ref)) {
 		ret = PTR_ERR(keyring_ref);
 		goto error;
 	}
 
-	key_ref = lookup_user_key(id, 0, 0, 0);
+	key_ref = lookup_user_key(id, KEY_LOOKUP_FOR_UNLINK, 0);
 	if (IS_ERR(key_ref)) {
 		ret = PTR_ERR(key_ref);
 		goto error2;
@@ -465,7 +468,7 @@ long keyctl_describe_key(key_serial_t keyid,
 	char *tmpbuf;
 	long ret;
 
-	key_ref = lookup_user_key(keyid, 0, 1, KEY_VIEW);
+	key_ref = lookup_user_key(keyid, KEY_LOOKUP_PARTIAL, KEY_VIEW);
 	if (IS_ERR(key_ref)) {
 		/* viewing a key under construction is permitted if we have the
 		 * authorisation token handy */
@@ -474,7 +477,8 @@ long keyctl_describe_key(key_serial_t keyid,
 			if (!IS_ERR(instkey)) {
 				key_put(instkey);
 				key_ref = lookup_user_key(keyid,
-							  0, 1, 0);
+							  KEY_LOOKUP_PARTIAL,
+							  0);
 				if (!IS_ERR(key_ref))
 					goto okay;
 			}
@@ -558,7 +562,7 @@ long keyctl_keyring_search(key_serial_t ringid,
 	}
 
 	/* get the keyring at which to begin the search */
-	keyring_ref = lookup_user_key(ringid, 0, 0, KEY_SEARCH);
+	keyring_ref = lookup_user_key(ringid, 0, KEY_SEARCH);
 	if (IS_ERR(keyring_ref)) {
 		ret = PTR_ERR(keyring_ref);
 		goto error2;
@@ -567,7 +571,8 @@ long keyctl_keyring_search(key_serial_t ringid,
 	/* get the destination keyring if specified */
 	dest_ref = NULL;
 	if (destringid) {
-		dest_ref = lookup_user_key(destringid, 1, 0, KEY_WRITE);
+		dest_ref = lookup_user_key(destringid, KEY_LOOKUP_CREATE,
+					   KEY_WRITE);
 		if (IS_ERR(dest_ref)) {
 			ret = PTR_ERR(dest_ref);
 			goto error3;
@@ -637,7 +642,7 @@ long keyctl_read_key(key_serial_t keyid, char __user *buffer, size_t buflen)
 	long ret;
 
 	/* find the key first */
-	key_ref = lookup_user_key(keyid, 0, 0, 0);
+	key_ref = lookup_user_key(keyid, 0, 0);
 	if (IS_ERR(key_ref)) {
 		ret = -ENOKEY;
 		goto error;
@@ -700,7 +705,8 @@ long keyctl_chown_key(key_serial_t id, uid_t uid, gid_t gid)
 	if (uid == (uid_t) -1 && gid == (gid_t) -1)
 		goto error;
 
-	key_ref = lookup_user_key(id, 1, 1, KEY_SETATTR);
+	key_ref = lookup_user_key(id, KEY_LOOKUP_CREATE | KEY_LOOKUP_PARTIAL,
+				  KEY_SETATTR);
 	if (IS_ERR(key_ref)) {
 		ret = PTR_ERR(key_ref);
 		goto error;
@@ -805,7 +811,8 @@ long keyctl_setperm_key(key_serial_t id, key_perm_t perm)
 	if (perm & ~(KEY_POS_ALL | KEY_USR_ALL | KEY_GRP_ALL | KEY_OTH_ALL))
 		goto error;
 
-	key_ref = lookup_user_key(id, 1, 1, KEY_SETATTR);
+	key_ref = lookup_user_key(id, KEY_LOOKUP_CREATE | KEY_LOOKUP_PARTIAL,
+				  KEY_SETATTR);
 	if (IS_ERR(key_ref)) {
 		ret = PTR_ERR(key_ref);
 		goto error;
@@ -847,7 +854,7 @@ static long get_instantiation_keyring(key_serial_t ringid,
 
 	/* if a specific keyring is nominated by ID, then use that */
 	if (ringid > 0) {
-		dkref = lookup_user_key(ringid, 1, 0, KEY_WRITE);
+		dkref = lookup_user_key(ringid, KEY_LOOKUP_CREATE, KEY_WRITE);
 		if (IS_ERR(dkref))
 			return PTR_ERR(dkref);
 		*_dest_keyring = key_ref_to_ptr(dkref);
@@ -1083,7 +1090,8 @@ long keyctl_set_timeout(key_serial_t id, unsigned timeout)
 	time_t expiry;
 	long ret;
 
-	key_ref = lookup_user_key(id, 1, 1, KEY_SETATTR);
+	key_ref = lookup_user_key(id, KEY_LOOKUP_CREATE | KEY_LOOKUP_PARTIAL,
+				  KEY_SETATTR);
 	if (IS_ERR(key_ref)) {
 		ret = PTR_ERR(key_ref);
 		goto error;
@@ -1170,7 +1178,7 @@ long keyctl_get_security(key_serial_t keyid,
 	char *context;
 	long ret;
 
-	key_ref = lookup_user_key(keyid, 0, 1, KEY_VIEW);
+	key_ref = lookup_user_key(keyid, KEY_LOOKUP_PARTIAL, KEY_VIEW);
 	if (IS_ERR(key_ref)) {
 		if (PTR_ERR(key_ref) != -EACCES)
 			return PTR_ERR(key_ref);
@@ -1182,7 +1190,7 @@ long keyctl_get_security(key_serial_t keyid,
 			return PTR_ERR(key_ref);
 		key_put(instkey);
 
-		key_ref = lookup_user_key(keyid, 0, 1, 0);
+		key_ref = lookup_user_key(keyid, KEY_LOOKUP_PARTIAL, 0);
 		if (IS_ERR(key_ref))
 			return PTR_ERR(key_ref);
 	}
diff --git a/security/keys/process_keys.c b/security/keys/process_keys.c
index 276d278..349c315 100644
--- a/security/keys/process_keys.c
+++ b/security/keys/process_keys.c
@@ -487,7 +487,7 @@ static int lookup_user_key_possessed(const struct key *key, const void *target)
  * - don't create special keyrings unless so requested
  * - partially constructed keys aren't found unless requested
  */
-key_ref_t lookup_user_key(key_serial_t id, int create, int partial,
+key_ref_t lookup_user_key(key_serial_t id, unsigned long lflags,
 			  key_perm_t perm)
 {
 	struct request_key_auth *rka;
@@ -503,7 +503,7 @@ try_again:
 	switch (id) {
 	case KEY_SPEC_THREAD_KEYRING:
 		if (!cred->thread_keyring) {
-			if (!create)
+			if (!(lflags & KEY_LOOKUP_CREATE))
 				goto error;
 
 			ret = install_thread_keyring();
@@ -521,7 +521,7 @@ try_again:
 
 	case KEY_SPEC_PROCESS_KEYRING:
 		if (!cred->tgcred->process_keyring) {
-			if (!create)
+			if (!(lflags & KEY_LOOKUP_CREATE))
 				goto error;
 
 			ret = install_process_keyring();
@@ -642,7 +642,14 @@ try_again:
 		break;
 	}
 
-	if (!partial) {
+	/* unlink does not use the nominated key in any way, so can skip all
+	 * the permission checks as it is only concerned with the keyring */
+	if (lflags & KEY_LOOKUP_FOR_UNLINK) {
+		ret = 0;
+		goto error;
+	}
+
+	if (!(lflags & KEY_LOOKUP_PARTIAL)) {
 		ret = wait_for_key_construction(key, true);
 		switch (ret) {
 		case -ERESTARTSYS:
@@ -660,7 +667,8 @@ try_again:
 	}
 
 	ret = -EIO;
-	if (!partial && !test_bit(KEY_FLAG_INSTANTIATED, &key->flags))
+	if (!(lflags & KEY_LOOKUP_PARTIAL) &&
+	    !test_bit(KEY_FLAG_INSTANTIATED, &key->flags))
 		goto invalid_key;
 
 	/* check the permissions */

[PATCH 2/6] KEYS: Allow keyctl_revoke() on keys that have SETATTR but not WRITE perm [ver #2]

[David Howells]

Allow keyctl_revoke() to operate on keys that have SETATTR but not WRITE
permission, rather than only on keys that have WRITE permission.

Signed-off-by: David Howells <dhowells@redhat.com>
Acked-by: Serge Hallyn <serue@us.ibm.com>
---

 security/keys/keyctl.c |    8 +++++++-
 1 files changed, 7 insertions(+), 1 deletions(-)


diff --git a/security/keys/keyctl.c b/security/keys/keyctl.c
index b85ace2..1160b64 100644
--- a/security/keys/keyctl.c
+++ b/security/keys/keyctl.c
@@ -343,7 +343,13 @@ long keyctl_revoke_key(key_serial_t id)
 	key_ref = lookup_user_key(id, 0, KEY_WRITE);
 	if (IS_ERR(key_ref)) {
 		ret = PTR_ERR(key_ref);
-		goto error;
+		if (ret != -EACCES)
+			goto error;
+		key_ref = lookup_user_key(id, 0, KEY_SETATTR);
+		if (IS_ERR(key_ref)) {
+			ret = PTR_ERR(key_ref);
+			goto error;
+		}
 	}
 
 	key_revoke(key_ref_to_ptr(key_ref));

[PATCH 3/6] KEYS: Flag dead keys to induce EKEYREVOKED [ver #2]

[David Howells]

Set the KEY_FLAG_DEAD flag on keys for which the type has been removed.  This
causes the key_permission() function to return EKEYREVOKED in response to
various commands.  It does not, however, prevent unlinking or clearing of
keyrings from detaching the key.

Signed-off-by: David Howells <dhowells@redhat.com>
Acked-by: Serge Hallyn <serue@us.ibm.com>
---

 security/keys/key.c |    4 +++-
 1 files changed, 3 insertions(+), 1 deletions(-)


diff --git a/security/keys/key.c b/security/keys/key.c
index 3762d5b..bd9d267 100644
--- a/security/keys/key.c
+++ b/security/keys/key.c
@@ -956,8 +956,10 @@ void unregister_key_type(struct key_type *ktype)
 	for (_n = rb_first(&key_serial_tree); _n; _n = rb_next(_n)) {
 		key = rb_entry(_n, struct key, serial_node);
 
-		if (key->type == ktype)
+		if (key->type == ktype) {
 			key->type = &key_type_dead;
+			set_bit(KEY_FLAG_DEAD, &key->flags);
+		}
 	}
 
 	spin_unlock(&key_serial_lock);

[PATCH 4/6] KEYS: Add garbage collection for dead, revoked and expired keys. [ver #2]

[David Howells]

Add garbage collection for dead, revoked and expired keys.  This involved
erasing all links to such keys from keyrings that point to them.  At that
point, the key will be deleted in the normal manner.

Keyrings from which garbage collection occurs are shrunk and their quota
consumption reduced as appropriate.

Dead keys (for which the key type has been removed) will be garbage collected
immediately.

Revoked and expired keys will hang around for a number of seconds, as set in
/proc/sys/kernel/keys/gc_delay before being automatically removed.  The default
is 5 minutes.

Signed-off-by: David Howells <dhowells@redhat.com>
---

 Documentation/keys.txt   |   19 ++++-
 include/linux/key.h      |    5 +
 security/keys/Makefile   |    1 
 security/keys/gc.c       |  193 ++++++++++++++++++++++++++++++++++++++++++++++
 security/keys/internal.h |    4 +
 security/keys/key.c      |   14 +++
 security/keys/keyctl.c   |    1 
 security/keys/keyring.c  |   85 ++++++++++++++++++++
 security/keys/sysctl.c   |   28 ++++++-
 9 files changed, 344 insertions(+), 6 deletions(-)
 create mode 100644 security/keys/gc.c


diff --git a/Documentation/keys.txt b/Documentation/keys.txt
index b56aacc..203487e 100644
--- a/Documentation/keys.txt
+++ b/Documentation/keys.txt
@@ -26,7 +26,7 @@ This document has the following sections:
 	- Notes on accessing payload contents
 	- Defining a key type
 	- Request-key callback service
-	- Key access filesystem
+	- Garbage collection
 
 
 ============
@@ -113,6 +113,9 @@ Each key has a number of attributes:
 
      (*) Dead. The key's type was unregistered, and so the key is now useless.
 
+Keys in the last three states are subject to garbage collection.  See the
+section on "Garbage collection".
+
 
 ====================
 KEY SERVICE OVERVIEW
@@ -1231,3 +1234,17 @@ by executing:
 
 In this case, the program isn't required to actually attach the key to a ring;
 the rings are provided for reference.
+
+
+==================
+GARBAGE COLLECTION
+==================
+
+Dead keys (for which the type has been removed) will be automatically unlinked
+from those keyrings that point to them and deleted as soon as possible by a
+background garbage collector.
+
+Similarly, revoked and expired keys will be garbage collected, but only after a
+certain amount of time has passed.  This time is set as a number of seconds in:
+
+	/proc/sys/kernel/keys/gc_delay
diff --git a/include/linux/key.h b/include/linux/key.h
index e544f46..33e0165 100644
--- a/include/linux/key.h
+++ b/include/linux/key.h
@@ -129,7 +129,10 @@ struct key {
 	struct rw_semaphore	sem;		/* change vs change sem */
 	struct key_user		*user;		/* owner of this key */
 	void			*security;	/* security data for this key */
-	time_t			expiry;		/* time at which key expires (or 0) */
+	union {
+		time_t		expiry;		/* time at which key expires (or 0) */
+		time_t		revoked_at;	/* time at which key was revoked */
+	};
 	uid_t			uid;
 	gid_t			gid;
 	key_perm_t		perm;		/* access permissions */
diff --git a/security/keys/Makefile b/security/keys/Makefile
index 747a464..74d5447 100644
--- a/security/keys/Makefile
+++ b/security/keys/Makefile
@@ -3,6 +3,7 @@
 #
 
 obj-y := \
+	gc.o \
 	key.o \
 	keyring.o \
 	keyctl.o \
diff --git a/security/keys/gc.c b/security/keys/gc.c
new file mode 100644
index 0000000..44adc32
--- /dev/null
+++ b/security/keys/gc.c
@@ -0,0 +1,193 @@
+/* Key garbage collector
+ *
+ * Copyright (C) 2009 Red Hat, Inc. All Rights Reserved.
+ * Written by David Howells (dhowells@redhat.com)
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public Licence
+ * as published by the Free Software Foundation; either version
+ * 2 of the Licence, or (at your option) any later version.
+ */
+
+#include <linux/module.h>
+#include <keys/keyring-type.h>
+#include "internal.h"
+
+/*
+ * Delay between key revocation/expiry in seconds
+ */
+unsigned key_gc_delay = 5 * 60;
+
+/*
+ * Reaper
+ */
+static void key_gc_timer_func(unsigned long);
+static void key_garbage_collector(struct work_struct *);
+static DEFINE_TIMER(key_gc_timer, key_gc_timer_func, 0, 0);
+static DECLARE_WORK(key_gc_work, key_garbage_collector);
+static key_serial_t key_gc_cursor; /* the last key the gc considered */
+static unsigned long key_gc_executing;
+static time_t key_gc_next_run = LONG_MAX;
+
+/*
+ * Schedule a garbage collection run
+ * - precision isn't particularly important
+ */
+void key_schedule_gc(time_t gc_at)
+{
+	unsigned long expires;
+	time_t now = current_kernel_time().tv_sec;
+
+	kenter("%ld", gc_at - now);
+
+	gc_at += key_gc_delay;
+
+	if (now >= gc_at) {
+		schedule_work(&key_gc_work);
+	} else if (gc_at < key_gc_next_run) {
+		expires = jiffies + (gc_at - now) * HZ;
+		mod_timer(&key_gc_timer, expires);
+	}
+}
+
+/*
+ * The garbage collector timer kicked off
+ */
+static void key_gc_timer_func(unsigned long data)
+{
+	kenter("");
+	key_gc_next_run = LONG_MAX;
+	schedule_work(&key_gc_work);
+}
+
+/*
+ * Garbage collect pointers from a keyring
+ * - return true if we altered the keyring
+ */
+static bool key_gc_keyring(struct key *keyring, time_t limit)
+{
+	struct keyring_list *klist;
+	struct key *key;
+	int loop;
+
+	kenter("%x", key_serial(keyring));
+
+	if (test_bit(KEY_FLAG_REVOKED, &keyring->flags))
+		goto dont_gc;
+
+	/* scan the keyring looking for dead keys */
+	klist = rcu_dereference(keyring->payload.subscriptions);
+	if (!klist)
+		goto dont_gc;
+
+	for (loop = klist->nkeys - 1; loop >= 0; loop--) {
+		key = klist->keys[loop];
+		if (test_bit(KEY_FLAG_DEAD, &key->flags) ||
+		    (key->expiry > 0 && key->expiry <= limit))
+			goto do_gc;
+	}
+
+dont_gc:
+	kleave(" = false");
+	return false;
+
+do_gc:
+	key_gc_cursor = keyring->serial;
+	key_get(keyring);
+	spin_unlock(&key_serial_lock);
+	keyring_gc(keyring, limit);
+	key_put(keyring);
+	kleave(" = true");
+	return true;
+}
+
+/*
+ * Garbage collector for keys
+ * - this involves scanning the keyrings for dead, expired and revoked keys
+ *   that have overstayed their welcome
+ */
+static void key_garbage_collector(struct work_struct *work)
+{
+	struct rb_node *rb;
+	key_serial_t cursor;
+	struct key *key, *xkey;
+	time_t new_timer = LONG_MAX, limit;
+
+	kenter("");
+
+	if (test_and_set_bit(0, &key_gc_executing)) {
+		key_schedule_gc(current_kernel_time().tv_sec);
+		return;
+	}
+
+	limit = current_kernel_time().tv_sec;
+	if (limit > key_gc_delay)
+		limit -= key_gc_delay;
+	else
+		limit = key_gc_delay;
+
+	spin_lock(&key_serial_lock);
+
+	if (RB_EMPTY_ROOT(&key_serial_tree))
+		goto reached_the_end;
+
+	cursor = key_gc_cursor;
+	if (cursor < 0)
+		cursor = 0;
+
+	/* find the first key above the cursor */
+	key = NULL;
+	rb = key_serial_tree.rb_node;
+	while (rb) {
+		xkey = rb_entry(rb, struct key, serial_node);
+		if (cursor < xkey->serial) {
+			key = xkey;
+			rb = rb->rb_left;
+		} else if (cursor > xkey->serial) {
+			rb = rb->rb_right;
+		} else {
+			rb = rb_next(rb);
+			if (!rb)
+				goto reached_the_end;
+			key = rb_entry(rb, struct key, serial_node);
+			break;
+		}
+	}
+
+	if (!key)
+		goto reached_the_end;
+
+	/* trawl through the keys looking for keyrings */
+	for (;;) {
+		if (key->expiry > 0 && key->expiry < new_timer)
+			new_timer = key->expiry;
+
+		if (key->type == &key_type_keyring &&
+		    key_gc_keyring(key, limit)) {
+			/* the gc ate our lock */
+			schedule_work(&key_gc_work);
+			goto no_unlock;
+		}
+
+		rb = rb_next(&key->serial_node);
+		if (!rb) {
+			key_gc_cursor = 0;
+			break;
+		}
+		key = rb_entry(rb, struct key, serial_node);
+	}
+
+out:
+	spin_unlock(&key_serial_lock);
+no_unlock:
+	clear_bit(0, &key_gc_executing);
+	if (new_timer < LONG_MAX)
+		key_schedule_gc(new_timer);
+
+	kleave("");
+	return;
+
+reached_the_end:
+	key_gc_cursor = 0;
+	goto out;
+}
diff --git a/security/keys/internal.h b/security/keys/internal.h
index a7252e7..fb83051 100644
--- a/security/keys/internal.h
+++ b/security/keys/internal.h
@@ -132,6 +132,10 @@ extern key_ref_t lookup_user_key(key_serial_t id, unsigned long flags,
 
 extern long join_session_keyring(const char *name);
 
+extern unsigned key_gc_delay;
+extern void keyring_gc(struct key *keyring, time_t limit);
+extern void key_schedule_gc(time_t expiry_at);
+
 /*
  * check to see whether permission is granted to use a key in the desired way
  */
diff --git a/security/keys/key.c b/security/keys/key.c
index bd9d267..08531ad 100644
--- a/security/keys/key.c
+++ b/security/keys/key.c
@@ -500,6 +500,7 @@ int key_negate_and_link(struct key *key,
 		set_bit(KEY_FLAG_INSTANTIATED, &key->flags);
 		now = current_kernel_time();
 		key->expiry = now.tv_sec + timeout;
+		key_schedule_gc(key->expiry);
 
 		if (test_and_clear_bit(KEY_FLAG_USER_CONSTRUCT, &key->flags))
 			awaken = 1;
@@ -888,6 +889,9 @@ EXPORT_SYMBOL(key_update);
  */
 void key_revoke(struct key *key)
 {
+	struct timespec now;
+	time_t time;
+
 	key_check(key);
 
 	/* make sure no one's trying to change or use the key when we mark it
@@ -900,6 +904,14 @@ void key_revoke(struct key *key)
 	    key->type->revoke)
 		key->type->revoke(key);
 
+	/* set the death time to no more than the expiry time */
+	now = current_kernel_time();
+	time = now.tv_sec;
+	if (key->revoked_at == 0 || key->revoked_at > time) {
+		key->revoked_at = time;
+		key_schedule_gc(key->revoked_at);
+	}
+
 	up_write(&key->sem);
 
 } /* end key_revoke() */
@@ -984,6 +996,8 @@ void unregister_key_type(struct key_type *ktype)
 	spin_unlock(&key_serial_lock);
 	up_write(&key_types_sem);
 
+	key_schedule_gc(0);
+
 } /* end unregister_key_type() */
 
 EXPORT_SYMBOL(unregister_key_type);
diff --git a/security/keys/keyctl.c b/security/keys/keyctl.c
index 1160b64..736d780 100644
--- a/security/keys/keyctl.c
+++ b/security/keys/keyctl.c
@@ -1115,6 +1115,7 @@ long keyctl_set_timeout(key_serial_t id, unsigned timeout)
 	}
 
 	key->expiry = expiry;
+	key_schedule_gc(key->expiry);
 
 	up_write(&key->sem);
 	key_put(key);
diff --git a/security/keys/keyring.c b/security/keys/keyring.c
index 3dba81c..ac977f6 100644
--- a/security/keys/keyring.c
+++ b/security/keys/keyring.c
@@ -1000,3 +1000,88 @@ static void keyring_revoke(struct key *keyring)
 	}
 
 } /* end keyring_revoke() */
+
+/*
+ * Determine whether a key is dead
+ */
+static bool key_is_dead(struct key *key, time_t limit)
+{
+	return test_bit(KEY_FLAG_DEAD, &key->flags) ||
+		(key->expiry > 0 && key->expiry <= limit);
+}
+
+/*
+ * Collect garbage from the contents of a keyring
+ */
+void keyring_gc(struct key *keyring, time_t limit)
+{
+	struct keyring_list *klist, *new;
+	struct key *key;
+	int loop, keep, max;
+
+	kenter("%x", key_serial(keyring));
+
+	down_write(&keyring->sem);
+
+	klist = keyring->payload.subscriptions;
+	if (!klist)
+		goto just_return;
+
+	/* work out how many subscriptions we're keeping */
+	keep = 0;
+	for (loop = klist->nkeys - 1; loop >= 0; loop--)
+		if (!key_is_dead(klist->keys[loop], limit));
+			keep++;
+
+	if (keep == klist->nkeys)
+		goto just_return;
+
+	/* allocate a new keyring payload */
+	max = roundup(keep, 4);
+	new = kmalloc(sizeof(struct keyring_list) + max * sizeof(struct key *),
+		      GFP_KERNEL);
+	if (!new)
+		goto just_return;
+	new->maxkeys = max;
+	new->nkeys = 0;
+	new->delkey = 0;
+
+	/* install the live keys
+	 * - must take care as expired keys may be updated back to life
+	 */
+	keep = 0;
+	for (loop = klist->nkeys - 1; loop >= 0; loop--) {
+		key = klist->keys[loop];
+		if (!key_is_dead(key, limit)) {
+			if (keep >= max)
+				goto discard_new;
+			new->keys[keep++] = key_get(key);
+		}
+	}
+	new->nkeys = keep;
+
+	/* adjust the quota */
+	key_payload_reserve(keyring,
+			    sizeof(struct keyring_list) +
+			    KEYQUOTA_LINK_BYTES * keep);
+
+	if (keep == 0) {
+		rcu_assign_pointer(keyring->payload.subscriptions, NULL);
+		kfree(new);
+	} else {
+		rcu_assign_pointer(keyring->payload.subscriptions, new);
+	}
+
+	up_write(&keyring->sem);
+
+	call_rcu(&klist->rcu, keyring_clear_rcu_disposal);
+	kleave(" [yes]");
+	return;
+
+discard_new:
+	new->nkeys = keep;
+	keyring_clear_rcu_disposal(&new->rcu);
+just_return:
+	up_write(&keyring->sem);
+	kleave(" [no]");
+}
diff --git a/security/keys/sysctl.c b/security/keys/sysctl.c
index b611d49..5e05dc0 100644
--- a/security/keys/sysctl.c
+++ b/security/keys/sysctl.c
@@ -13,6 +13,8 @@
 #include <linux/sysctl.h>
 #include "internal.h"
 
+static const int zero, one = 1, max = INT_MAX;
+
 ctl_table key_sysctls[] = {
 	{
 		.ctl_name = CTL_UNNUMBERED,
@@ -20,7 +22,9 @@ ctl_table key_sysctls[] = {
 		.data = &key_quota_maxkeys,
 		.maxlen = sizeof(unsigned),
 		.mode = 0644,
-		.proc_handler = &proc_dointvec,
+		.proc_handler = &proc_dointvec_minmax,
+		.extra1 = (void *) &one,
+		.extra2 = (void *) &max,
 	},
 	{
 		.ctl_name = CTL_UNNUMBERED,
@@ -28,7 +32,9 @@ ctl_table key_sysctls[] = {
 		.data = &key_quota_maxbytes,
 		.maxlen = sizeof(unsigned),
 		.mode = 0644,
-		.proc_handler = &proc_dointvec,
+		.proc_handler = &proc_dointvec_minmax,
+		.extra1 = (void *) &one,
+		.extra2 = (void *) &max,
 	},
 	{
 		.ctl_name = CTL_UNNUMBERED,
@@ -36,7 +42,9 @@ ctl_table key_sysctls[] = {
 		.data = &key_quota_root_maxkeys,
 		.maxlen = sizeof(unsigned),
 		.mode = 0644,
-		.proc_handler = &proc_dointvec,
+		.proc_handler = &proc_dointvec_minmax,
+		.extra1 = (void *) &one,
+		.extra2 = (void *) &max,
 	},
 	{
 		.ctl_name = CTL_UNNUMBERED,
@@ -44,7 +52,19 @@ ctl_table key_sysctls[] = {
 		.data = &key_quota_root_maxbytes,
 		.maxlen = sizeof(unsigned),
 		.mode = 0644,
-		.proc_handler = &proc_dointvec,
+		.proc_handler = &proc_dointvec_minmax,
+		.extra1 = (void *) &one,
+		.extra2 = (void *) &max,
+	},
+	{
+		.ctl_name = CTL_UNNUMBERED,
+		.procname = "gc_delay",
+		.data = &key_gc_delay,
+		.maxlen = sizeof(unsigned),
+		.mode = 0644,
+		.proc_handler = &proc_dointvec_minmax,
+		.extra1 = (void *) &zero,
+		.extra2 = (void *) &max,
 	},
 	{ .ctl_name = 0 }
 };

[PATCH 5/6] KEYS: Make /proc/keys use keyid not numread as file position [ver #2]

[David Howells]

From: Serge E. Hallyn <serue@us.ibm.com>

Make the file position maintained by /proc/keys represent the ID of the key
just read rather than the number of keys read.  This should make it faster to
perform a lookup as we don't have to scan the key ID tree from the beginning to
find the current position.

Signed-off-by: Serge E. Hallyn <serue@us.ibm.com>
Signed-off-by: David Howells <dhowells@redhat.com>
---

 security/keys/proc.c |   62 +++++++++++++++++++++++++++++++++-----------------
 1 files changed, 41 insertions(+), 21 deletions(-)


diff --git a/security/keys/proc.c b/security/keys/proc.c
index 769f9bd..643ecf0 100644
--- a/security/keys/proc.c
+++ b/security/keys/proc.c
@@ -91,8 +91,9 @@ __initcall(key_proc_init);
  */
 #ifdef CONFIG_KEYS_DEBUG_PROC_KEYS
 
-static struct rb_node *__key_serial_next(struct rb_node *n)
+static struct rb_node *key_serial_next(struct rb_node *n)
 {
+	n = rb_next(n);
 	while (n) {
 		struct key *key = rb_entry(n, struct key, serial_node);
 		if (key->user->user_ns == current_user_ns())
@@ -102,45 +103,64 @@ static struct rb_node *__key_serial_next(struct rb_node *n)
 	return n;
 }
 
-static struct rb_node *key_serial_next(struct rb_node *n)
+static int proc_keys_open(struct inode *inode, struct file *file)
 {
-	return __key_serial_next(rb_next(n));
+	return seq_open(file, &proc_keys_ops);
 }
 
-static struct rb_node *key_serial_first(struct rb_root *r)
+static struct key *find_ge_key(key_serial_t id)
 {
-	struct rb_node *n = rb_first(r);
-	return __key_serial_next(n);
-}
+	struct rb_node *n = key_serial_tree.rb_node;
+	struct key *minkey = NULL;
 
-static int proc_keys_open(struct inode *inode, struct file *file)
-{
-	return seq_open(file, &proc_keys_ops);
+	while (n) {
+		struct key *key = rb_entry(n, struct key, serial_node);
+		if (id < key->serial) {
+			if (!minkey || minkey->serial > key->serial)
+				minkey = key;
+			n = n->rb_left;
+		} else if (id > key->serial) {
+			n = n->rb_right;
+		} else {
+			minkey = key;
+			break;
+		}
+		key = NULL;
+	}
 
+	return minkey;
 }
 
 static void *proc_keys_start(struct seq_file *p, loff_t *_pos)
 {
-	struct rb_node *_p;
-	loff_t pos = *_pos;
+	key_serial_t pos = *_pos;
+	struct key *key;
 
 	spin_lock(&key_serial_lock);
 
-	_p = key_serial_first(&key_serial_tree);
-	while (pos > 0 && _p) {
-		pos--;
-		_p = key_serial_next(_p);
-	}
-
-	return _p;
+	if (*_pos > INT_MAX)
+		return NULL;
+	key = find_ge_key(pos);
+	if (!key)
+		return NULL;
+	*_pos = key->serial;
+	return &key->serial_node;
+}
 
+static inline key_serial_t key_node_serial(struct rb_node *n)
+{
+	struct key *key = rb_entry(n, struct key, serial_node);
+	return key->serial;
 }
 
 static void *proc_keys_next(struct seq_file *p, void *v, loff_t *_pos)
 {
-	(*_pos)++;
-	return key_serial_next((struct rb_node *) v);
+	struct rb_node *n;
 
+	n = key_serial_next(v);
+	if (n)
+		*_pos = key_node_serial(n);
+	return n;
 }
 
 static void proc_keys_stop(struct seq_file *p, void *v)

[PATCH 6/6] KEYS: Do some whitespace cleanups [ver #2]

[David Howells]

Do some whitespace cleanups in the key management code.

Signed-off-by: David Howells <dhowells@redhat.com>
Acked-by: Serge Hallyn <serue@us.ibm.com>
---

 security/keys/proc.c |   12 +++---------
 1 files changed, 3 insertions(+), 9 deletions(-)


diff --git a/security/keys/proc.c b/security/keys/proc.c
index 643ecf0..e4fde23 100644
--- a/security/keys/proc.c
+++ b/security/keys/proc.c
@@ -194,11 +194,9 @@ static int proc_keys_show(struct seq_file *m, void *v)
 	/* come up with a suitable timeout value */
 	if (key->expiry == 0) {
 		memcpy(xbuf, "perm", 5);
-	}
-	else if (now.tv_sec >= key->expiry) {
+	} else if (now.tv_sec >= key->expiry) {
 		memcpy(xbuf, "expd", 5);
-	}
-	else {
+	} else {
 		timo = key->expiry - now.tv_sec;
 
 		if (timo < 60)
@@ -238,9 +236,7 @@ static int proc_keys_show(struct seq_file *m, void *v)
 	seq_putc(m, '\n');
 
 	rcu_read_unlock();
-
 	return 0;
-
 }
 
 #endif /* CONFIG_KEYS_DEBUG_PROC_KEYS */
@@ -266,6 +262,7 @@ static struct rb_node *key_user_first(struct rb_root *r)
 	struct rb_node *n = rb_first(r);
 	return __key_user_next(n);
 }
+
 /*****************************************************************************/
 /*
  * implement "/proc/key-users" to provides a list of the key users
@@ -273,7 +270,6 @@ static struct rb_node *key_user_first(struct rb_root *r)
 static int proc_key_users_open(struct inode *inode, struct file *file)
 {
 	return seq_open(file, &proc_key_users_ops);
-
 }
 
 static void *proc_key_users_start(struct seq_file *p, loff_t *_pos)
@@ -290,14 +286,12 @@ static void *proc_key_users_start(struct seq_file *p, loff_t *_pos)
 	}
 
 	return _p;
-
 }
 
 static void *proc_key_users_next(struct seq_file *p, void *v, loff_t *_pos)
 {
 	(*_pos)++;
 	return key_user_next((struct rb_node *) v);
-
 }
 
 static void proc_key_users_stop(struct seq_file *p, void *v)

Re: [PATCH 4/6] KEYS: Add garbage collection for dead, revoked and expired keys. [ver #2]

[Serge E. Hallyn]

Quoting David Howells (dhowells@redhat.com):
> Add garbage collection for dead, revoked and expired keys.  This involved
> erasing all links to such keys from keyrings that point to them.  At that
> point, the key will be deleted in the normal manner.
> 
> Keyrings from which garbage collection occurs are shrunk and their quota
> consumption reduced as appropriate.
> 
> Dead keys (for which the key type has been removed) will be garbage collected
> immediately.
> 
> Revoked and expired keys will hang around for a number of seconds, as set in
> /proc/sys/kernel/keys/gc_delay before being automatically removed.  The default
> is 5 minutes.
> 
> Signed-off-by: David Howells <dhowells@redhat.com>

Acked-by: Serge Hallyn <serue@us.ibm.com>

Re: [PATCH 4/6] KEYS: Add garbage collection for dead, revoked and expired keys. [ver #2]

[James Morris]

On Tue, 4 Aug 2009, David Howells wrote:

> +void key_schedule_gc(time_t gc_at)
> +{
> +	unsigned long expires;
> +	time_t now = current_kernel_time().tv_sec;
> +
> +	kenter("%ld", gc_at - now);
> +
> +	gc_at += key_gc_delay;
> +
> +	if (now >= gc_at) {

Should you be using time_after() and friends for these comparisons?


-- 
James Morris
<jmorris@namei.org>

Re: [PATCH 4/6] KEYS: Add garbage collection for dead, revoked and expired keys. [ver #2]

[David Howells]

James Morris <jmorris@namei.org> wrote:

> > +	if (now >= gc_at) {
> 
> Should you be using time_after() and friends for these comparisons?

Ummm...  Possibly.  Isn't time_after() normally used for jiffies comparisons?

David

Re: [PATCH 5/6] KEYS: Make /proc/keys use keyid not numread as file position [ver #2]

[James Morris]

On Tue, 4 Aug 2009, David Howells wrote:

> From: Serge E. Hallyn <serue@us.ibm.com>
> 
> Make the file position maintained by /proc/keys represent the ID of the key
> just read rather than the number of keys read.  This should make it faster to
> perform a lookup as we don't have to scan the key ID tree from the beginning to
> find the current position.
> 
> Signed-off-by: Serge E. Hallyn <serue@us.ibm.com>
> Signed-off-by: David Howells <dhowells@redhat.com>


This does not apply to my tree:

git://git.kernel.org/pub/scm/linux/kernel/git/jmorris/security-testing-2.6#next

Looks like it's due to pending changes in the same file.  Could you please 
generate this patch against my tree? 


- James
-- 
James Morris
<jmorris@namei.org>