public inbox for linux-kernel@vger.kernel.org
 help / color / mirror / Atom feed
* [PATCH] KEYS: Fix garbage collector
@ 2009-09-14 16:26 David Howells
  2009-09-15  0:10 ` [GIT] security / creds fixes James Morris
  0 siblings, 1 reply; 11+ messages in thread
From: David Howells @ 2009-09-14 16:26 UTC (permalink / raw)
  To: torvalds, jmorris, eparis, mingo
  Cc: linux-security-module, linux-kernel, David Howells

Fix a number of problems with the new key garbage collector:

 (1) A rogue semicolon in keyring_gc() was causing the initial count of dead
     keys to be miscalculated.

 (2) A missing return in keyring_gc() meant that under certain circumstances,
     the keyring semaphore would be unlocked twice.

 (3) The key serial tree iterator (key_garbage_collector()) part of the garbage
     collector has been modified to:

     (a) Complete each scan of the keyrings before setting the new timer.

     (b) Only set the new timer for keys that have yet to expire.  This means
         that the new timer is now calculated correctly, and the gc doesn't
         get into a loop continually scanning for keys that have expired, and
         preventing other things from happening, like RCU cleaning up the old
         keyring contents.

     (c) Perform an extra scan if any keys were garbage collected in this one
     	 as a key might become garbage during a scan, and (b) could mean we
     	 don't set the timer again.

 (4) Made key_schedule_gc() take the time at which to do a collection run,
     rather than the time at which the key expires.  This means the collection
     of dead keys (key type unregistered) can happen immediately.

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

 security/keys/gc.c      |   78 +++++++++++++++++++++++++++++++----------------
 security/keys/key.c     |    4 +-
 security/keys/keyctl.c  |    2 +
 security/keys/keyring.c |   24 +++++++++++---
 4 files changed, 73 insertions(+), 35 deletions(-)


diff --git a/security/keys/gc.c b/security/keys/gc.c
index 1e616ae..485fc62 100644
--- a/security/keys/gc.c
+++ b/security/keys/gc.c
@@ -26,8 +26,10 @@ 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 bool key_gc_again;
 static unsigned long key_gc_executing;
 static time_t key_gc_next_run = LONG_MAX;
+static time_t key_gc_new_timer;
 
 /*
  * Schedule a garbage collection run
@@ -40,9 +42,7 @@ void key_schedule_gc(time_t gc_at)
 
 	kenter("%ld", gc_at - now);
 
-	gc_at += key_gc_delay;
-
-	if (now >= gc_at) {
+	if (gc_at <= now) {
 		schedule_work(&key_gc_work);
 	} else if (gc_at < key_gc_next_run) {
 		expires = jiffies + (gc_at - now) * HZ;
@@ -112,16 +112,18 @@ 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;
+	time_t new_timer = LONG_MAX, limit, now;
 
-	kenter("");
+	now = current_kernel_time().tv_sec;
+	kenter("[%x,%ld]", key_gc_cursor, key_gc_new_timer - now);
 
 	if (test_and_set_bit(0, &key_gc_executing)) {
-		key_schedule_gc(current_kernel_time().tv_sec);
+		key_schedule_gc(current_kernel_time().tv_sec + 1);
+		kleave(" [busy; deferring]");
 		return;
 	}
 
-	limit = current_kernel_time().tv_sec;
+	limit = now;
 	if (limit > key_gc_delay)
 		limit -= key_gc_delay;
 	else
@@ -129,12 +131,19 @@ static void key_garbage_collector(struct work_struct *work)
 
 	spin_lock(&key_serial_lock);
 
-	if (RB_EMPTY_ROOT(&key_serial_tree))
-		goto reached_the_end;
+	if (unlikely(RB_EMPTY_ROOT(&key_serial_tree))) {
+		spin_unlock(&key_serial_lock);
+		clear_bit(0, &key_gc_executing);
+		return;
+	}
 
 	cursor = key_gc_cursor;
 	if (cursor < 0)
 		cursor = 0;
+	if (cursor > 0)
+		new_timer = key_gc_new_timer;
+	else
+		key_gc_again = false;
 
 	/* find the first key above the cursor */
 	key = NULL;
@@ -160,35 +169,50 @@ static void key_garbage_collector(struct work_struct *work)
 
 	/* trawl through the keys looking for keyrings */
 	for (;;) {
-		if (key->expiry > 0 && key->expiry < new_timer)
+		if (key->expiry > now && key->expiry < new_timer) {
+			kdebug("will expire %x in %ld",
+			       key_serial(key), key->expiry - now);
 			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;
-		}
+		    key_gc_keyring(key, limit))
+			/* the gc had to release our lock so that the keyring
+			 * could be modified, so we have to get it again */
+			goto gc_released_our_lock;
 
 		rb = rb_next(&key->serial_node);
-		if (!rb) {
-			key_gc_cursor = 0;
-			break;
-		}
+		if (!rb)
+			goto reached_the_end;
 		key = rb_entry(rb, struct key, serial_node);
 	}
 
-out:
-	spin_unlock(&key_serial_lock);
-no_unlock:
+gc_released_our_lock:
+	kdebug("gc_released_our_lock");
+	key_gc_new_timer = new_timer;
+	key_gc_again = true;
 	clear_bit(0, &key_gc_executing);
-	if (new_timer < LONG_MAX)
-		key_schedule_gc(new_timer);
-
-	kleave("");
+	schedule_work(&key_gc_work);
+	kleave(" [continue]");
 	return;
 
+	/* when we reach the end of the run, we set the timer for the next one */
 reached_the_end:
+	kdebug("reached_the_end");
+	spin_unlock(&key_serial_lock);
+	key_gc_new_timer = new_timer;
 	key_gc_cursor = 0;
-	goto out;
+	clear_bit(0, &key_gc_executing);
+
+	if (key_gc_again) {
+		/* there may have been a key that expired whilst we were
+		 * scanning, so if we discarded any links we should do another
+		 * scan */
+		new_timer = now + 1;
+		key_schedule_gc(new_timer);
+	} else if (new_timer < LONG_MAX) {
+		new_timer += key_gc_delay;
+		key_schedule_gc(new_timer);
+	}
+	kleave(" [end]");
 }
diff --git a/security/keys/key.c b/security/keys/key.c
index 08531ad..e50d264 100644
--- a/security/keys/key.c
+++ b/security/keys/key.c
@@ -500,7 +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);
+		key_schedule_gc(key->expiry + key_gc_delay);
 
 		if (test_and_clear_bit(KEY_FLAG_USER_CONSTRUCT, &key->flags))
 			awaken = 1;
@@ -909,7 +909,7 @@ void key_revoke(struct key *key)
 	time = now.tv_sec;
 	if (key->revoked_at == 0 || key->revoked_at > time) {
 		key->revoked_at = time;
-		key_schedule_gc(key->revoked_at);
+		key_schedule_gc(key->revoked_at + key_gc_delay);
 	}
 
 	up_write(&key->sem);
diff --git a/security/keys/keyctl.c b/security/keys/keyctl.c
index 60983f3..2fb28ef 100644
--- a/security/keys/keyctl.c
+++ b/security/keys/keyctl.c
@@ -1115,7 +1115,7 @@ long keyctl_set_timeout(key_serial_t id, unsigned timeout)
 	}
 
 	key->expiry = expiry;
-	key_schedule_gc(key->expiry);
+	key_schedule_gc(key->expiry + key_gc_delay);
 
 	up_write(&key->sem);
 	key_put(key);
diff --git a/security/keys/keyring.c b/security/keys/keyring.c
index ac977f6..8ec0274 100644
--- a/security/keys/keyring.c
+++ b/security/keys/keyring.c
@@ -1019,18 +1019,18 @@ void keyring_gc(struct key *keyring, time_t limit)
 	struct key *key;
 	int loop, keep, max;
 
-	kenter("%x", key_serial(keyring));
+	kenter("{%x,%s}", key_serial(keyring), keyring->description);
 
 	down_write(&keyring->sem);
 
 	klist = keyring->payload.subscriptions;
 	if (!klist)
-		goto just_return;
+		goto no_klist;
 
 	/* 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));
+		if (!key_is_dead(klist->keys[loop], limit))
 			keep++;
 
 	if (keep == klist->nkeys)
@@ -1041,7 +1041,7 @@ void keyring_gc(struct key *keyring, time_t limit)
 	new = kmalloc(sizeof(struct keyring_list) + max * sizeof(struct key *),
 		      GFP_KERNEL);
 	if (!new)
-		goto just_return;
+		goto nomem;
 	new->maxkeys = max;
 	new->nkeys = 0;
 	new->delkey = 0;
@@ -1081,7 +1081,21 @@ void keyring_gc(struct key *keyring, time_t limit)
 discard_new:
 	new->nkeys = keep;
 	keyring_clear_rcu_disposal(&new->rcu);
+	up_write(&keyring->sem);
+	kleave(" [discard]");
+	return;
+
 just_return:
 	up_write(&keyring->sem);
-	kleave(" [no]");
+	kleave(" [no dead]");
+	return;
+
+no_klist:
+	up_write(&keyring->sem);
+	kleave(" [no_klist]");
+	return;
+
+nomem:
+	up_write(&keyring->sem);
+	kleave(" [oom]");
 }


^ permalink raw reply related	[flat|nested] 11+ messages in thread
end of thread, other threads:[~2009-09-17 19:52 UTC | newest]

Thread overview: 11+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2009-09-14 16:26 [PATCH] KEYS: Fix garbage collector David Howells
2009-09-15  0:10 ` [GIT] security / creds fixes James Morris
2009-09-15  0:37   ` Linus Torvalds
2009-09-15  0:49     ` Eric Paris
2009-09-16 13:02   ` Ingo Molnar
2009-09-16 13:38     ` Eric Paris
2009-09-16 14:34       ` Ingo Molnar
2009-09-17 15:19         ` BUG avc_node: Objects remaining on kmem_cache_close() Ingo Molnar
2009-09-17 15:26           ` Eric Paris
2009-09-17 16:21             ` Ingo Molnar
2009-09-17 19:51               ` Eric Paris

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox