blob: a42b45531aac173a337498cfc26fd09ded18baee [file] [log] [blame]
David Howells5d135442009-09-02 09:14:00 +01001/* Key garbage collector
2 *
David Howells0c061b52011-08-22 14:09:36 +01003 * Copyright (C) 2009-2011 Red Hat, Inc. All Rights Reserved.
David Howells5d135442009-09-02 09:14:00 +01004 * Written by David Howells (dhowells@redhat.com)
5 *
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public Licence
8 * as published by the Free Software Foundation; either version
9 * 2 of the Licence, or (at your option) any later version.
10 */
11
12#include <linux/module.h>
David Howells8bc16de2011-08-22 14:09:11 +010013#include <linux/slab.h>
14#include <linux/security.h>
David Howells5d135442009-09-02 09:14:00 +010015#include <keys/keyring-type.h>
16#include "internal.h"
17
18/*
19 * Delay between key revocation/expiry in seconds
20 */
21unsigned key_gc_delay = 5 * 60;
22
23/*
David Howells8bc16de2011-08-22 14:09:11 +010024 * Reaper for unused keys.
25 */
David Howells0c061b52011-08-22 14:09:36 +010026static void key_garbage_collector(struct work_struct *work);
27DECLARE_WORK(key_gc_work, key_garbage_collector);
David Howells8bc16de2011-08-22 14:09:11 +010028
29/*
30 * Reaper for links from keyrings to dead keys.
David Howells5d135442009-09-02 09:14:00 +010031 */
32static void key_gc_timer_func(unsigned long);
David Howells5d135442009-09-02 09:14:00 +010033static DEFINE_TIMER(key_gc_timer, key_gc_timer_func, 0, 0);
David Howells0c061b52011-08-22 14:09:36 +010034
David Howells5d135442009-09-02 09:14:00 +010035static time_t key_gc_next_run = LONG_MAX;
David Howells0c061b52011-08-22 14:09:36 +010036static struct key_type *key_gc_dead_keytype;
37
38static unsigned long key_gc_flags;
39#define KEY_GC_KEY_EXPIRED 0 /* A key expired and needs unlinking */
40#define KEY_GC_REAP_KEYTYPE 1 /* A keytype is being unregistered */
41#define KEY_GC_REAPING_KEYTYPE 2 /* Cleared when keytype reaped */
42
43
44/*
45 * Any key whose type gets unregistered will be re-typed to this if it can't be
46 * immediately unlinked.
47 */
48struct key_type key_type_dead = {
49 .name = "dead",
50};
David Howells5d135442009-09-02 09:14:00 +010051
52/*
David Howells973c9f42011-01-20 16:38:33 +000053 * Schedule a garbage collection run.
54 * - time precision isn't particularly important
David Howells5d135442009-09-02 09:14:00 +010055 */
56void key_schedule_gc(time_t gc_at)
57{
58 unsigned long expires;
59 time_t now = current_kernel_time().tv_sec;
60
61 kenter("%ld", gc_at - now);
62
David Howells0c061b52011-08-22 14:09:36 +010063 if (gc_at <= now || test_bit(KEY_GC_REAP_KEYTYPE, &key_gc_flags)) {
64 kdebug("IMMEDIATE");
David Howellsd1997982011-08-22 14:09:28 +010065 queue_work(system_nrt_wq, &key_gc_work);
David Howells5d135442009-09-02 09:14:00 +010066 } else if (gc_at < key_gc_next_run) {
David Howells0c061b52011-08-22 14:09:36 +010067 kdebug("DEFERRED");
68 key_gc_next_run = gc_at;
David Howells5d135442009-09-02 09:14:00 +010069 expires = jiffies + (gc_at - now) * HZ;
70 mod_timer(&key_gc_timer, expires);
71 }
72}
73
74/*
David Howells0c061b52011-08-22 14:09:36 +010075 * Some key's cleanup time was met after it expired, so we need to get the
76 * reaper to go through a cycle finding expired keys.
David Howells5d135442009-09-02 09:14:00 +010077 */
78static void key_gc_timer_func(unsigned long data)
79{
80 kenter("");
81 key_gc_next_run = LONG_MAX;
David Howells0c061b52011-08-22 14:09:36 +010082 set_bit(KEY_GC_KEY_EXPIRED, &key_gc_flags);
David Howellsd1997982011-08-22 14:09:28 +010083 queue_work(system_nrt_wq, &key_gc_work);
David Howells5d135442009-09-02 09:14:00 +010084}
85
86/*
David Howells0c061b52011-08-22 14:09:36 +010087 * wait_on_bit() sleep function for uninterruptible waiting
88 */
89static int key_gc_wait_bit(void *flags)
90{
91 schedule();
92 return 0;
93}
94
95/*
96 * Reap keys of dead type.
97 *
98 * We use three flags to make sure we see three complete cycles of the garbage
99 * collector: the first to mark keys of that type as being dead, the second to
100 * collect dead links and the third to clean up the dead keys. We have to be
101 * careful as there may already be a cycle in progress.
102 *
103 * The caller must be holding key_types_sem.
104 */
105void key_gc_keytype(struct key_type *ktype)
106{
107 kenter("%s", ktype->name);
108
109 key_gc_dead_keytype = ktype;
110 set_bit(KEY_GC_REAPING_KEYTYPE, &key_gc_flags);
111 smp_mb();
112 set_bit(KEY_GC_REAP_KEYTYPE, &key_gc_flags);
113
114 kdebug("schedule");
115 queue_work(system_nrt_wq, &key_gc_work);
116
117 kdebug("sleep");
118 wait_on_bit(&key_gc_flags, KEY_GC_REAPING_KEYTYPE, key_gc_wait_bit,
119 TASK_UNINTERRUPTIBLE);
120
121 key_gc_dead_keytype = NULL;
122 kleave("");
123}
124
125/*
David Howells973c9f42011-01-20 16:38:33 +0000126 * Garbage collect pointers from a keyring.
127 *
David Howells0c061b52011-08-22 14:09:36 +0100128 * Not called with any locks held. The keyring's key struct will not be
129 * deallocated under us as only our caller may deallocate it.
David Howells5d135442009-09-02 09:14:00 +0100130 */
David Howells0c061b52011-08-22 14:09:36 +0100131static void key_gc_keyring(struct key *keyring, time_t limit)
David Howells5d135442009-09-02 09:14:00 +0100132{
133 struct keyring_list *klist;
134 struct key *key;
135 int loop;
136
137 kenter("%x", key_serial(keyring));
138
139 if (test_bit(KEY_FLAG_REVOKED, &keyring->flags))
140 goto dont_gc;
141
142 /* scan the keyring looking for dead keys */
David Howellscf8304e2010-05-04 14:16:10 +0100143 rcu_read_lock();
144 klist = rcu_dereference(keyring->payload.subscriptions);
David Howells5d135442009-09-02 09:14:00 +0100145 if (!klist)
David Howellscf8304e2010-05-04 14:16:10 +0100146 goto unlock_dont_gc;
David Howells5d135442009-09-02 09:14:00 +0100147
David Howellsefde8b62012-01-17 20:39:40 +0000148 loop = klist->nkeys;
149 smp_rmb();
150 for (loop--; loop >= 0; loop--) {
David Howells5d135442009-09-02 09:14:00 +0100151 key = klist->keys[loop];
152 if (test_bit(KEY_FLAG_DEAD, &key->flags) ||
153 (key->expiry > 0 && key->expiry <= limit))
154 goto do_gc;
155 }
156
David Howellscf8304e2010-05-04 14:16:10 +0100157unlock_dont_gc:
158 rcu_read_unlock();
David Howells5d135442009-09-02 09:14:00 +0100159dont_gc:
David Howells0c061b52011-08-22 14:09:36 +0100160 kleave(" [no gc]");
161 return;
David Howells5d135442009-09-02 09:14:00 +0100162
163do_gc:
David Howellscf8304e2010-05-04 14:16:10 +0100164 rcu_read_unlock();
David Howells0c061b52011-08-22 14:09:36 +0100165
David Howells5d135442009-09-02 09:14:00 +0100166 keyring_gc(keyring, limit);
David Howells0c061b52011-08-22 14:09:36 +0100167 kleave(" [gc]");
David Howells5d135442009-09-02 09:14:00 +0100168}
169
170/*
David Howells0c061b52011-08-22 14:09:36 +0100171 * Garbage collect an unreferenced, detached key
David Howells5d135442009-09-02 09:14:00 +0100172 */
David Howells0c061b52011-08-22 14:09:36 +0100173static noinline void key_gc_unused_key(struct key *key)
David Howells5d135442009-09-02 09:14:00 +0100174{
David Howells8bc16de2011-08-22 14:09:11 +0100175 key_check(key);
176
177 security_key_free(key);
178
179 /* deal with the user's key tracking and quota */
180 if (test_bit(KEY_FLAG_IN_QUOTA, &key->flags)) {
181 spin_lock(&key->user->lock);
182 key->user->qnkeys--;
183 key->user->qnbytes -= key->quotalen;
184 spin_unlock(&key->user->lock);
185 }
186
187 atomic_dec(&key->user->nkeys);
188 if (test_bit(KEY_FLAG_INSTANTIATED, &key->flags))
189 atomic_dec(&key->user->nikeys);
190
191 key_user_put(key->user);
192
193 /* now throw away the key memory */
194 if (key->type->destroy)
195 key->type->destroy(key);
196
197 kfree(key->description);
198
199#ifdef KEY_DEBUGGING
200 key->magic = KEY_DEBUG_MAGIC_X;
201#endif
202 kmem_cache_free(key_jar, key);
David Howells0c061b52011-08-22 14:09:36 +0100203}
David Howells8bc16de2011-08-22 14:09:11 +0100204
David Howells0c061b52011-08-22 14:09:36 +0100205/*
206 * Garbage collector for unused keys.
207 *
208 * This is done in process context so that we don't have to disable interrupts
209 * all over the place. key_put() schedules this rather than trying to do the
210 * cleanup itself, which means key_put() doesn't have to sleep.
211 */
212static void key_garbage_collector(struct work_struct *work)
213{
214 static u8 gc_state; /* Internal persistent state */
215#define KEY_GC_REAP_AGAIN 0x01 /* - Need another cycle */
216#define KEY_GC_REAPING_LINKS 0x02 /* - We need to reap links */
217#define KEY_GC_SET_TIMER 0x04 /* - We need to restart the timer */
218#define KEY_GC_REAPING_DEAD_1 0x10 /* - We need to mark dead keys */
219#define KEY_GC_REAPING_DEAD_2 0x20 /* - We need to reap dead key links */
220#define KEY_GC_REAPING_DEAD_3 0x40 /* - We need to reap dead keys */
221#define KEY_GC_FOUND_DEAD_KEY 0x80 /* - We found at least one dead key */
222
223 struct rb_node *cursor;
224 struct key *key;
225 time_t new_timer, limit;
226
227 kenter("[%lx,%x]", key_gc_flags, gc_state);
228
229 limit = current_kernel_time().tv_sec;
230 if (limit > key_gc_delay)
231 limit -= key_gc_delay;
232 else
233 limit = key_gc_delay;
234
235 /* Work out what we're going to be doing in this pass */
236 gc_state &= KEY_GC_REAPING_DEAD_1 | KEY_GC_REAPING_DEAD_2;
237 gc_state <<= 1;
238 if (test_and_clear_bit(KEY_GC_KEY_EXPIRED, &key_gc_flags))
239 gc_state |= KEY_GC_REAPING_LINKS | KEY_GC_SET_TIMER;
240
241 if (test_and_clear_bit(KEY_GC_REAP_KEYTYPE, &key_gc_flags))
242 gc_state |= KEY_GC_REAPING_DEAD_1;
243 kdebug("new pass %x", gc_state);
244
245 new_timer = LONG_MAX;
246
247 /* As only this function is permitted to remove things from the key
248 * serial tree, if cursor is non-NULL then it will always point to a
249 * valid node in the tree - even if lock got dropped.
250 */
251 spin_lock(&key_serial_lock);
252 cursor = rb_first(&key_serial_tree);
253
254continue_scanning:
255 while (cursor) {
256 key = rb_entry(cursor, struct key, serial_node);
257 cursor = rb_next(cursor);
258
259 if (atomic_read(&key->usage) == 0)
260 goto found_unreferenced_key;
261
262 if (unlikely(gc_state & KEY_GC_REAPING_DEAD_1)) {
263 if (key->type == key_gc_dead_keytype) {
264 gc_state |= KEY_GC_FOUND_DEAD_KEY;
265 set_bit(KEY_FLAG_DEAD, &key->flags);
266 key->perm = 0;
267 goto skip_dead_key;
268 }
269 }
270
271 if (gc_state & KEY_GC_SET_TIMER) {
272 if (key->expiry > limit && key->expiry < new_timer) {
273 kdebug("will expire %x in %ld",
274 key_serial(key), key->expiry - limit);
275 new_timer = key->expiry;
276 }
277 }
278
279 if (unlikely(gc_state & KEY_GC_REAPING_DEAD_2))
280 if (key->type == key_gc_dead_keytype)
281 gc_state |= KEY_GC_FOUND_DEAD_KEY;
282
283 if ((gc_state & KEY_GC_REAPING_LINKS) ||
284 unlikely(gc_state & KEY_GC_REAPING_DEAD_2)) {
285 if (key->type == &key_type_keyring)
286 goto found_keyring;
287 }
288
289 if (unlikely(gc_state & KEY_GC_REAPING_DEAD_3))
290 if (key->type == key_gc_dead_keytype)
291 goto destroy_dead_key;
292
293 skip_dead_key:
294 if (spin_is_contended(&key_serial_lock) || need_resched())
295 goto contended;
296 }
297
298contended:
299 spin_unlock(&key_serial_lock);
300
301maybe_resched:
302 if (cursor) {
303 cond_resched();
304 spin_lock(&key_serial_lock);
305 goto continue_scanning;
306 }
307
308 /* We've completed the pass. Set the timer if we need to and queue a
309 * new cycle if necessary. We keep executing cycles until we find one
310 * where we didn't reap any keys.
311 */
312 kdebug("pass complete");
313
314 if (gc_state & KEY_GC_SET_TIMER && new_timer != (time_t)LONG_MAX) {
315 new_timer += key_gc_delay;
316 key_schedule_gc(new_timer);
317 }
318
319 if (unlikely(gc_state & KEY_GC_REAPING_DEAD_2)) {
320 /* Make sure everyone revalidates their keys if we marked a
321 * bunch as being dead and make sure all keyring ex-payloads
322 * are destroyed.
323 */
324 kdebug("dead sync");
325 synchronize_rcu();
326 }
327
328 if (unlikely(gc_state & (KEY_GC_REAPING_DEAD_1 |
329 KEY_GC_REAPING_DEAD_2))) {
330 if (!(gc_state & KEY_GC_FOUND_DEAD_KEY)) {
331 /* No remaining dead keys: short circuit the remaining
332 * keytype reap cycles.
333 */
334 kdebug("dead short");
335 gc_state &= ~(KEY_GC_REAPING_DEAD_1 | KEY_GC_REAPING_DEAD_2);
336 gc_state |= KEY_GC_REAPING_DEAD_3;
337 } else {
338 gc_state |= KEY_GC_REAP_AGAIN;
339 }
340 }
341
342 if (unlikely(gc_state & KEY_GC_REAPING_DEAD_3)) {
343 kdebug("dead wake");
344 smp_mb();
345 clear_bit(KEY_GC_REAPING_KEYTYPE, &key_gc_flags);
346 wake_up_bit(&key_gc_flags, KEY_GC_REAPING_KEYTYPE);
347 }
348
349 if (gc_state & KEY_GC_REAP_AGAIN)
350 queue_work(system_nrt_wq, &key_gc_work);
351 kleave(" [end %x]", gc_state);
352 return;
353
354 /* We found an unreferenced key - once we've removed it from the tree,
355 * we can safely drop the lock.
356 */
357found_unreferenced_key:
358 kdebug("unrefd key %d", key->serial);
359 rb_erase(&key->serial_node, &key_serial_tree);
360 spin_unlock(&key_serial_lock);
361
362 key_gc_unused_key(key);
363 gc_state |= KEY_GC_REAP_AGAIN;
364 goto maybe_resched;
365
366 /* We found a keyring and we need to check the payload for links to
367 * dead or expired keys. We don't flag another reap immediately as we
368 * have to wait for the old payload to be destroyed by RCU before we
369 * can reap the keys to which it refers.
370 */
371found_keyring:
372 spin_unlock(&key_serial_lock);
373 kdebug("scan keyring %d", key->serial);
374 key_gc_keyring(key, limit);
375 goto maybe_resched;
376
377 /* We found a dead key that is still referenced. Reset its type and
378 * destroy its payload with its semaphore held.
379 */
380destroy_dead_key:
381 spin_unlock(&key_serial_lock);
382 kdebug("destroy key %d", key->serial);
383 down_write(&key->sem);
384 key->type = &key_type_dead;
385 if (key_gc_dead_keytype->destroy)
386 key_gc_dead_keytype->destroy(key);
387 memset(&key->payload, KEY_DESTROY, sizeof(key->payload));
388 up_write(&key->sem);
389 goto maybe_resched;
David Howells8bc16de2011-08-22 14:09:11 +0100390}