gc.c 9.73 KB
Newer Older
1 2
/* Key garbage collector
 *
3
 * Copyright (C) 2009-2011 Red Hat, Inc. All Rights Reserved.
4 5 6 7 8 9 10 11 12
 * 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>
13 14
#include <linux/slab.h>
#include <linux/security.h>
15 16 17 18 19 20 21 22 23
#include <keys/keyring-type.h>
#include "internal.h"

/*
 * Delay between key revocation/expiry in seconds
 */
unsigned key_gc_delay = 5 * 60;

/*
24 25
 * Reaper for unused keys.
 */
26 27
static void key_garbage_collector(struct work_struct *work);
DECLARE_WORK(key_gc_work, key_garbage_collector);
28 29 30

/*
 * Reaper for links from keyrings to dead keys.
31 32 33
 */
static void key_gc_timer_func(unsigned long);
static DEFINE_TIMER(key_gc_timer, key_gc_timer_func, 0, 0);
34

35
static time_t key_gc_next_run = LONG_MAX;
36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
static struct key_type *key_gc_dead_keytype;

static unsigned long key_gc_flags;
#define KEY_GC_KEY_EXPIRED	0	/* A key expired and needs unlinking */
#define KEY_GC_REAP_KEYTYPE	1	/* A keytype is being unregistered */
#define KEY_GC_REAPING_KEYTYPE	2	/* Cleared when keytype reaped */


/*
 * Any key whose type gets unregistered will be re-typed to this if it can't be
 * immediately unlinked.
 */
struct key_type key_type_dead = {
	.name = "dead",
};
51 52

/*
53 54
 * Schedule a garbage collection run.
 * - time precision isn't particularly important
55 56 57 58 59 60 61 62
 */
void key_schedule_gc(time_t gc_at)
{
	unsigned long expires;
	time_t now = current_kernel_time().tv_sec;

	kenter("%ld", gc_at - now);

63 64
	if (gc_at <= now || test_bit(KEY_GC_REAP_KEYTYPE, &key_gc_flags)) {
		kdebug("IMMEDIATE");
65
		schedule_work(&key_gc_work);
66
	} else if (gc_at < key_gc_next_run) {
67 68
		kdebug("DEFERRED");
		key_gc_next_run = gc_at;
69 70 71 72 73
		expires = jiffies + (gc_at - now) * HZ;
		mod_timer(&key_gc_timer, expires);
	}
}

74 75 76 77 78 79
/*
 * Schedule a dead links collection run.
 */
void key_schedule_gc_links(void)
{
	set_bit(KEY_GC_KEY_EXPIRED, &key_gc_flags);
80
	schedule_work(&key_gc_work);
81 82
}

83
/*
84 85
 * Some key's cleanup time was met after it expired, so we need to get the
 * reaper to go through a cycle finding expired keys.
86 87 88 89 90
 */
static void key_gc_timer_func(unsigned long data)
{
	kenter("");
	key_gc_next_run = LONG_MAX;
91
	key_schedule_gc_links();
92 93
}

94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113
/*
 * Reap keys of dead type.
 *
 * We use three flags to make sure we see three complete cycles of the garbage
 * collector: the first to mark keys of that type as being dead, the second to
 * collect dead links and the third to clean up the dead keys.  We have to be
 * careful as there may already be a cycle in progress.
 *
 * The caller must be holding key_types_sem.
 */
void key_gc_keytype(struct key_type *ktype)
{
	kenter("%s", ktype->name);

	key_gc_dead_keytype = ktype;
	set_bit(KEY_GC_REAPING_KEYTYPE, &key_gc_flags);
	smp_mb();
	set_bit(KEY_GC_REAP_KEYTYPE, &key_gc_flags);

	kdebug("schedule");
114
	schedule_work(&key_gc_work);
115 116

	kdebug("sleep");
117
	wait_on_bit(&key_gc_flags, KEY_GC_REAPING_KEYTYPE,
118 119 120 121 122 123
		    TASK_UNINTERRUPTIBLE);

	key_gc_dead_keytype = NULL;
	kleave("");
}

124
/*
125
 * Garbage collect a list of unreferenced, detached keys
126
 */
127
static noinline void key_gc_unused_keys(struct list_head *keys)
128
{
129 130 131 132 133 134 135 136
	while (!list_empty(keys)) {
		struct key *key =
			list_entry(keys->next, struct key, graveyard_link);
		list_del(&key->graveyard_link);

		kdebug("- %u", key->serial);
		key_check(key);

137 138 139 140
		/* Throw away the key data if the key is instantiated */
		if (test_bit(KEY_FLAG_INSTANTIATED, &key->flags) &&
		    !test_bit(KEY_FLAG_NEGATIVE, &key->flags) &&
		    key->type->destroy)
141 142
			key->type->destroy(key);

143 144 145 146 147 148 149 150 151
		security_key_free(key);

		/* deal with the user's key tracking and quota */
		if (test_bit(KEY_FLAG_IN_QUOTA, &key->flags)) {
			spin_lock(&key->user->lock);
			key->user->qnkeys--;
			key->user->qnbytes -= key->quotalen;
			spin_unlock(&key->user->lock);
		}
152

153 154 155
		atomic_dec(&key->user->nkeys);
		if (test_bit(KEY_FLAG_INSTANTIATED, &key->flags))
			atomic_dec(&key->user->nikeys);
156

157 158
		key_user_put(key->user);

159
		kfree(key->description);
160

161
#ifdef KEY_DEBUGGING
162
		key->magic = KEY_DEBUG_MAGIC_X;
163
#endif
164 165
		kmem_cache_free(key_jar, key);
	}
166
}
167 168 169 170 171 172 173 174

/*
 * Garbage collector for unused keys.
 *
 * This is done in process context so that we don't have to disable interrupts
 * all over the place.  key_put() schedules this rather than trying to do the
 * cleanup itself, which means key_put() doesn't have to sleep.
 */
175
static void key_garbage_collector(struct work_struct *work)
176
{
177
	static LIST_HEAD(graveyard);
178 179 180 181 182 183 184 185 186 187
	static u8 gc_state;		/* Internal persistent state */
#define KEY_GC_REAP_AGAIN	0x01	/* - Need another cycle */
#define KEY_GC_REAPING_LINKS	0x02	/* - We need to reap links */
#define KEY_GC_SET_TIMER	0x04	/* - We need to restart the timer */
#define KEY_GC_REAPING_DEAD_1	0x10	/* - We need to mark dead keys */
#define KEY_GC_REAPING_DEAD_2	0x20	/* - We need to reap dead key links */
#define KEY_GC_REAPING_DEAD_3	0x40	/* - We need to reap dead keys */
#define KEY_GC_FOUND_DEAD_KEY	0x80	/* - We found at least one dead key */

	struct rb_node *cursor;
188
	struct key *key;
189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209
	time_t new_timer, limit;

	kenter("[%lx,%x]", key_gc_flags, gc_state);

	limit = current_kernel_time().tv_sec;
	if (limit > key_gc_delay)
		limit -= key_gc_delay;
	else
		limit = key_gc_delay;

	/* Work out what we're going to be doing in this pass */
	gc_state &= KEY_GC_REAPING_DEAD_1 | KEY_GC_REAPING_DEAD_2;
	gc_state <<= 1;
	if (test_and_clear_bit(KEY_GC_KEY_EXPIRED, &key_gc_flags))
		gc_state |= KEY_GC_REAPING_LINKS | KEY_GC_SET_TIMER;

	if (test_and_clear_bit(KEY_GC_REAP_KEYTYPE, &key_gc_flags))
		gc_state |= KEY_GC_REAPING_DEAD_1;
	kdebug("new pass %x", gc_state);

	new_timer = LONG_MAX;
210

211 212 213 214
	/* As only this function is permitted to remove things from the key
	 * serial tree, if cursor is non-NULL then it will always point to a
	 * valid node in the tree - even if lock got dropped.
	 */
215
	spin_lock(&key_serial_lock);
216
	cursor = rb_first(&key_serial_tree);
217

218 219 220 221
continue_scanning:
	while (cursor) {
		key = rb_entry(cursor, struct key, serial_node);
		cursor = rb_next(cursor);
222 223

		if (atomic_read(&key->usage) == 0)
224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259
			goto found_unreferenced_key;

		if (unlikely(gc_state & KEY_GC_REAPING_DEAD_1)) {
			if (key->type == key_gc_dead_keytype) {
				gc_state |= KEY_GC_FOUND_DEAD_KEY;
				set_bit(KEY_FLAG_DEAD, &key->flags);
				key->perm = 0;
				goto skip_dead_key;
			}
		}

		if (gc_state & KEY_GC_SET_TIMER) {
			if (key->expiry > limit && key->expiry < new_timer) {
				kdebug("will expire %x in %ld",
				       key_serial(key), key->expiry - limit);
				new_timer = key->expiry;
			}
		}

		if (unlikely(gc_state & KEY_GC_REAPING_DEAD_2))
			if (key->type == key_gc_dead_keytype)
				gc_state |= KEY_GC_FOUND_DEAD_KEY;

		if ((gc_state & KEY_GC_REAPING_LINKS) ||
		    unlikely(gc_state & KEY_GC_REAPING_DEAD_2)) {
			if (key->type == &key_type_keyring)
				goto found_keyring;
		}

		if (unlikely(gc_state & KEY_GC_REAPING_DEAD_3))
			if (key->type == key_gc_dead_keytype)
				goto destroy_dead_key;

	skip_dead_key:
		if (spin_is_contended(&key_serial_lock) || need_resched())
			goto contended;
260 261
	}

262
contended:
263 264
	spin_unlock(&key_serial_lock);

265 266 267 268 269 270
maybe_resched:
	if (cursor) {
		cond_resched();
		spin_lock(&key_serial_lock);
		goto continue_scanning;
	}
271

272 273 274 275 276
	/* We've completed the pass.  Set the timer if we need to and queue a
	 * new cycle if necessary.  We keep executing cycles until we find one
	 * where we didn't reap any keys.
	 */
	kdebug("pass complete");
277

278 279 280 281
	if (gc_state & KEY_GC_SET_TIMER && new_timer != (time_t)LONG_MAX) {
		new_timer += key_gc_delay;
		key_schedule_gc(new_timer);
	}
282

283 284 285 286 287 288
	if (unlikely(gc_state & KEY_GC_REAPING_DEAD_2) ||
	    !list_empty(&graveyard)) {
		/* Make sure that all pending keyring payload destructions are
		 * fulfilled and that people aren't now looking at dead or
		 * dying keys that they don't have a reference upon or a link
		 * to.
289
		 */
290
		kdebug("gc sync");
291
		synchronize_rcu();
292 293
	}

294 295 296 297 298
	if (!list_empty(&graveyard)) {
		kdebug("gc keys");
		key_gc_unused_keys(&graveyard);
	}

299 300 301 302 303 304 305 306 307 308 309 310 311
	if (unlikely(gc_state & (KEY_GC_REAPING_DEAD_1 |
				 KEY_GC_REAPING_DEAD_2))) {
		if (!(gc_state & KEY_GC_FOUND_DEAD_KEY)) {
			/* No remaining dead keys: short circuit the remaining
			 * keytype reap cycles.
			 */
			kdebug("dead short");
			gc_state &= ~(KEY_GC_REAPING_DEAD_1 | KEY_GC_REAPING_DEAD_2);
			gc_state |= KEY_GC_REAPING_DEAD_3;
		} else {
			gc_state |= KEY_GC_REAP_AGAIN;
		}
	}
312

313 314 315 316 317 318
	if (unlikely(gc_state & KEY_GC_REAPING_DEAD_3)) {
		kdebug("dead wake");
		smp_mb();
		clear_bit(KEY_GC_REAPING_KEYTYPE, &key_gc_flags);
		wake_up_bit(&key_gc_flags, KEY_GC_REAPING_KEYTYPE);
	}
319

320
	if (gc_state & KEY_GC_REAP_AGAIN)
321
		schedule_work(&key_gc_work);
322 323
	kleave(" [end %x]", gc_state);
	return;
324

325 326 327 328 329 330 331
	/* We found an unreferenced key - once we've removed it from the tree,
	 * we can safely drop the lock.
	 */
found_unreferenced_key:
	kdebug("unrefd key %d", key->serial);
	rb_erase(&key->serial_node, &key_serial_tree);
	spin_unlock(&key_serial_lock);
332

333
	list_add_tail(&key->graveyard_link, &graveyard);
334 335
	gc_state |= KEY_GC_REAP_AGAIN;
	goto maybe_resched;
336

337 338 339 340 341 342 343
	/* We found a keyring and we need to check the payload for links to
	 * dead or expired keys.  We don't flag another reap immediately as we
	 * have to wait for the old payload to be destroyed by RCU before we
	 * can reap the keys to which it refers.
	 */
found_keyring:
	spin_unlock(&key_serial_lock);
344
	keyring_gc(key, limit);
345 346 347 348 349 350 351 352 353 354 355 356 357 358 359
	goto maybe_resched;

	/* We found a dead key that is still referenced.  Reset its type and
	 * destroy its payload with its semaphore held.
	 */
destroy_dead_key:
	spin_unlock(&key_serial_lock);
	kdebug("destroy key %d", key->serial);
	down_write(&key->sem);
	key->type = &key_type_dead;
	if (key_gc_dead_keytype->destroy)
		key_gc_dead_keytype->destroy(key);
	memset(&key->payload, KEY_DESTROY, sizeof(key->payload));
	up_write(&key->sem);
	goto maybe_resched;
360
}