1 /* Key garbage collector
2 *
3 * Copyright (C) 2009-2011 Red Hat, Inc. All Rights Reserved.
4 * 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>
13 #include <linux/slab.h>
14 #include <linux/security.h>
15 #include <keys/keyring-type.h>
16 #include "internal.h"
17
18 /*
19 * Delay between key revocation/expiry in seconds
20 */
21 unsigned key_gc_delay = 5 * 60;
22
23 /*
24 * Reaper for unused keys.
25 */
26 static void key_garbage_collector(struct work_struct *work);
27 DECLARE_WORK(key_gc_work, key_garbage_collector);
28
29 /*
30 * Reaper for links from keyrings to dead keys.
31 */
32 static void key_gc_timer_func(unsigned long);
33 static DEFINE_TIMER(key_gc_timer, key_gc_timer_func, 0, 0);
34
35 static time_t key_gc_next_run = LONG_MAX;
36 static struct key_type *key_gc_dead_keytype;
37
38 static 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 */
48 struct key_type key_type_dead = {
49 .name = "dead",
50 };
51
52 /*
53 * Schedule a garbage collection run.
54 * - time precision isn't particularly important
55 */
key_schedule_gc(time_t gc_at)56 void 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
63 if (gc_at <= now || test_bit(KEY_GC_REAP_KEYTYPE, &key_gc_flags)) {
64 kdebug("IMMEDIATE");
65 schedule_work(&key_gc_work);
66 } else if (gc_at < key_gc_next_run) {
67 kdebug("DEFERRED");
68 key_gc_next_run = gc_at;
69 expires = jiffies + (gc_at - now) * HZ;
70 mod_timer(&key_gc_timer, expires);
71 }
72 }
73
74 /*
75 * Schedule a dead links collection run.
76 */
key_schedule_gc_links(void)77 void key_schedule_gc_links(void)
78 {
79 set_bit(KEY_GC_KEY_EXPIRED, &key_gc_flags);
80 schedule_work(&key_gc_work);
81 }
82
83 /*
84 * Some key's cleanup time was met after it expired, so we need to get the
85 * reaper to go through a cycle finding expired keys.
86 */
key_gc_timer_func(unsigned long data)87 static void key_gc_timer_func(unsigned long data)
88 {
89 kenter("");
90 key_gc_next_run = LONG_MAX;
91 key_schedule_gc_links();
92 }
93
94 /*
95 * wait_on_bit() sleep function for uninterruptible waiting
96 */
key_gc_wait_bit(void * flags)97 static int key_gc_wait_bit(void *flags)
98 {
99 schedule();
100 return 0;
101 }
102
103 /*
104 * Reap keys of dead type.
105 *
106 * We use three flags to make sure we see three complete cycles of the garbage
107 * collector: the first to mark keys of that type as being dead, the second to
108 * collect dead links and the third to clean up the dead keys. We have to be
109 * careful as there may already be a cycle in progress.
110 *
111 * The caller must be holding key_types_sem.
112 */
key_gc_keytype(struct key_type * ktype)113 void key_gc_keytype(struct key_type *ktype)
114 {
115 kenter("%s", ktype->name);
116
117 key_gc_dead_keytype = ktype;
118 set_bit(KEY_GC_REAPING_KEYTYPE, &key_gc_flags);
119 smp_mb();
120 set_bit(KEY_GC_REAP_KEYTYPE, &key_gc_flags);
121
122 kdebug("schedule");
123 schedule_work(&key_gc_work);
124
125 kdebug("sleep");
126 wait_on_bit(&key_gc_flags, KEY_GC_REAPING_KEYTYPE, key_gc_wait_bit,
127 TASK_UNINTERRUPTIBLE);
128
129 key_gc_dead_keytype = NULL;
130 kleave("");
131 }
132
133 /*
134 * Garbage collect pointers from a keyring.
135 *
136 * Not called with any locks held. The keyring's key struct will not be
137 * deallocated under us as only our caller may deallocate it.
138 */
key_gc_keyring(struct key * keyring,time_t limit)139 static void key_gc_keyring(struct key *keyring, time_t limit)
140 {
141 struct keyring_list *klist;
142 int loop;
143
144 kenter("%x", key_serial(keyring));
145
146 if (keyring->flags & ((1 << KEY_FLAG_INVALIDATED) |
147 (1 << KEY_FLAG_REVOKED)))
148 goto dont_gc;
149
150 /* scan the keyring looking for dead keys */
151 rcu_read_lock();
152 klist = rcu_dereference(keyring->payload.subscriptions);
153 if (!klist)
154 goto unlock_dont_gc;
155
156 loop = klist->nkeys;
157 smp_rmb();
158 for (loop--; loop >= 0; loop--) {
159 struct key *key = rcu_dereference(klist->keys[loop]);
160 if (key_is_dead(key, limit))
161 goto do_gc;
162 }
163
164 unlock_dont_gc:
165 rcu_read_unlock();
166 dont_gc:
167 kleave(" [no gc]");
168 return;
169
170 do_gc:
171 rcu_read_unlock();
172
173 keyring_gc(keyring, limit);
174 kleave(" [gc]");
175 }
176
177 /*
178 * Garbage collect a list of unreferenced, detached keys
179 */
key_gc_unused_keys(struct list_head * keys)180 static noinline void key_gc_unused_keys(struct list_head *keys)
181 {
182 while (!list_empty(keys)) {
183 struct key *key =
184 list_entry(keys->next, struct key, graveyard_link);
185 list_del(&key->graveyard_link);
186
187 kdebug("- %u", key->serial);
188 key_check(key);
189
190 /* Throw away the key data if the key is instantiated */
191 if (test_bit(KEY_FLAG_INSTANTIATED, &key->flags) &&
192 !test_bit(KEY_FLAG_NEGATIVE, &key->flags) &&
193 key->type->destroy)
194 key->type->destroy(key);
195
196 security_key_free(key);
197
198 /* deal with the user's key tracking and quota */
199 if (test_bit(KEY_FLAG_IN_QUOTA, &key->flags)) {
200 spin_lock(&key->user->lock);
201 key->user->qnkeys--;
202 key->user->qnbytes -= key->quotalen;
203 spin_unlock(&key->user->lock);
204 }
205
206 atomic_dec(&key->user->nkeys);
207 if (test_bit(KEY_FLAG_INSTANTIATED, &key->flags))
208 atomic_dec(&key->user->nikeys);
209
210 key_user_put(key->user);
211
212 kfree(key->description);
213
214 #ifdef KEY_DEBUGGING
215 key->magic = KEY_DEBUG_MAGIC_X;
216 #endif
217 kmem_cache_free(key_jar, key);
218 }
219 }
220
221 /*
222 * Garbage collector for unused keys.
223 *
224 * This is done in process context so that we don't have to disable interrupts
225 * all over the place. key_put() schedules this rather than trying to do the
226 * cleanup itself, which means key_put() doesn't have to sleep.
227 */
key_garbage_collector(struct work_struct * work)228 static void key_garbage_collector(struct work_struct *work)
229 {
230 static LIST_HEAD(graveyard);
231 static u8 gc_state; /* Internal persistent state */
232 #define KEY_GC_REAP_AGAIN 0x01 /* - Need another cycle */
233 #define KEY_GC_REAPING_LINKS 0x02 /* - We need to reap links */
234 #define KEY_GC_SET_TIMER 0x04 /* - We need to restart the timer */
235 #define KEY_GC_REAPING_DEAD_1 0x10 /* - We need to mark dead keys */
236 #define KEY_GC_REAPING_DEAD_2 0x20 /* - We need to reap dead key links */
237 #define KEY_GC_REAPING_DEAD_3 0x40 /* - We need to reap dead keys */
238 #define KEY_GC_FOUND_DEAD_KEY 0x80 /* - We found at least one dead key */
239
240 struct rb_node *cursor;
241 struct key *key;
242 time_t new_timer, limit;
243
244 kenter("[%lx,%x]", key_gc_flags, gc_state);
245
246 limit = current_kernel_time().tv_sec;
247 if (limit > key_gc_delay)
248 limit -= key_gc_delay;
249 else
250 limit = key_gc_delay;
251
252 /* Work out what we're going to be doing in this pass */
253 gc_state &= KEY_GC_REAPING_DEAD_1 | KEY_GC_REAPING_DEAD_2;
254 gc_state <<= 1;
255 if (test_and_clear_bit(KEY_GC_KEY_EXPIRED, &key_gc_flags))
256 gc_state |= KEY_GC_REAPING_LINKS | KEY_GC_SET_TIMER;
257
258 if (test_and_clear_bit(KEY_GC_REAP_KEYTYPE, &key_gc_flags))
259 gc_state |= KEY_GC_REAPING_DEAD_1;
260 kdebug("new pass %x", gc_state);
261
262 new_timer = LONG_MAX;
263
264 /* As only this function is permitted to remove things from the key
265 * serial tree, if cursor is non-NULL then it will always point to a
266 * valid node in the tree - even if lock got dropped.
267 */
268 spin_lock(&key_serial_lock);
269 cursor = rb_first(&key_serial_tree);
270
271 continue_scanning:
272 while (cursor) {
273 key = rb_entry(cursor, struct key, serial_node);
274 cursor = rb_next(cursor);
275
276 if (atomic_read(&key->usage) == 0)
277 goto found_unreferenced_key;
278
279 if (unlikely(gc_state & KEY_GC_REAPING_DEAD_1)) {
280 if (key->type == key_gc_dead_keytype) {
281 gc_state |= KEY_GC_FOUND_DEAD_KEY;
282 set_bit(KEY_FLAG_DEAD, &key->flags);
283 key->perm = 0;
284 goto skip_dead_key;
285 }
286 }
287
288 if (gc_state & KEY_GC_SET_TIMER) {
289 if (key->expiry > limit && key->expiry < new_timer) {
290 kdebug("will expire %x in %ld",
291 key_serial(key), key->expiry - limit);
292 new_timer = key->expiry;
293 }
294 }
295
296 if (unlikely(gc_state & KEY_GC_REAPING_DEAD_2))
297 if (key->type == key_gc_dead_keytype)
298 gc_state |= KEY_GC_FOUND_DEAD_KEY;
299
300 if ((gc_state & KEY_GC_REAPING_LINKS) ||
301 unlikely(gc_state & KEY_GC_REAPING_DEAD_2)) {
302 if (key->type == &key_type_keyring)
303 goto found_keyring;
304 }
305
306 if (unlikely(gc_state & KEY_GC_REAPING_DEAD_3))
307 if (key->type == key_gc_dead_keytype)
308 goto destroy_dead_key;
309
310 skip_dead_key:
311 if (spin_is_contended(&key_serial_lock) || need_resched())
312 goto contended;
313 }
314
315 contended:
316 spin_unlock(&key_serial_lock);
317
318 maybe_resched:
319 if (cursor) {
320 cond_resched();
321 spin_lock(&key_serial_lock);
322 goto continue_scanning;
323 }
324
325 /* We've completed the pass. Set the timer if we need to and queue a
326 * new cycle if necessary. We keep executing cycles until we find one
327 * where we didn't reap any keys.
328 */
329 kdebug("pass complete");
330
331 if (gc_state & KEY_GC_SET_TIMER && new_timer != (time_t)LONG_MAX) {
332 new_timer += key_gc_delay;
333 key_schedule_gc(new_timer);
334 }
335
336 if (unlikely(gc_state & KEY_GC_REAPING_DEAD_2) ||
337 !list_empty(&graveyard)) {
338 /* Make sure that all pending keyring payload destructions are
339 * fulfilled and that people aren't now looking at dead or
340 * dying keys that they don't have a reference upon or a link
341 * to.
342 */
343 kdebug("gc sync");
344 synchronize_rcu();
345 }
346
347 if (!list_empty(&graveyard)) {
348 kdebug("gc keys");
349 key_gc_unused_keys(&graveyard);
350 }
351
352 if (unlikely(gc_state & (KEY_GC_REAPING_DEAD_1 |
353 KEY_GC_REAPING_DEAD_2))) {
354 if (!(gc_state & KEY_GC_FOUND_DEAD_KEY)) {
355 /* No remaining dead keys: short circuit the remaining
356 * keytype reap cycles.
357 */
358 kdebug("dead short");
359 gc_state &= ~(KEY_GC_REAPING_DEAD_1 | KEY_GC_REAPING_DEAD_2);
360 gc_state |= KEY_GC_REAPING_DEAD_3;
361 } else {
362 gc_state |= KEY_GC_REAP_AGAIN;
363 }
364 }
365
366 if (unlikely(gc_state & KEY_GC_REAPING_DEAD_3)) {
367 kdebug("dead wake");
368 smp_mb();
369 clear_bit(KEY_GC_REAPING_KEYTYPE, &key_gc_flags);
370 wake_up_bit(&key_gc_flags, KEY_GC_REAPING_KEYTYPE);
371 }
372
373 if (gc_state & KEY_GC_REAP_AGAIN)
374 schedule_work(&key_gc_work);
375 kleave(" [end %x]", gc_state);
376 return;
377
378 /* We found an unreferenced key - once we've removed it from the tree,
379 * we can safely drop the lock.
380 */
381 found_unreferenced_key:
382 kdebug("unrefd key %d", key->serial);
383 rb_erase(&key->serial_node, &key_serial_tree);
384 spin_unlock(&key_serial_lock);
385
386 list_add_tail(&key->graveyard_link, &graveyard);
387 gc_state |= KEY_GC_REAP_AGAIN;
388 goto maybe_resched;
389
390 /* We found a keyring and we need to check the payload for links to
391 * dead or expired keys. We don't flag another reap immediately as we
392 * have to wait for the old payload to be destroyed by RCU before we
393 * can reap the keys to which it refers.
394 */
395 found_keyring:
396 spin_unlock(&key_serial_lock);
397 kdebug("scan keyring %d", key->serial);
398 key_gc_keyring(key, limit);
399 goto maybe_resched;
400
401 /* We found a dead key that is still referenced. Reset its type and
402 * destroy its payload with its semaphore held.
403 */
404 destroy_dead_key:
405 spin_unlock(&key_serial_lock);
406 kdebug("destroy key %d", key->serial);
407 down_write(&key->sem);
408 key->type = &key_type_dead;
409 if (key_gc_dead_keytype->destroy)
410 key_gc_dead_keytype->destroy(key);
411 memset(&key->payload, KEY_DESTROY, sizeof(key->payload));
412 up_write(&key->sem);
413 goto maybe_resched;
414 }
415