Merge tag 'modules-next-for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git...
[linux-3.10.git] / security / keys / gc.c
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  */
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  */
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  */
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  */
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  */
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  */
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  */
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                 security_key_free(key);
191
192                 /* deal with the user's key tracking and quota */
193                 if (test_bit(KEY_FLAG_IN_QUOTA, &key->flags)) {
194                         spin_lock(&key->user->lock);
195                         key->user->qnkeys--;
196                         key->user->qnbytes -= key->quotalen;
197                         spin_unlock(&key->user->lock);
198                 }
199
200                 atomic_dec(&key->user->nkeys);
201                 if (test_bit(KEY_FLAG_INSTANTIATED, &key->flags))
202                         atomic_dec(&key->user->nikeys);
203
204                 key_user_put(key->user);
205
206                 /* now throw away the key memory */
207                 if (key->type->destroy)
208                         key->type->destroy(key);
209
210                 kfree(key->description);
211
212 #ifdef KEY_DEBUGGING
213                 key->magic = KEY_DEBUG_MAGIC_X;
214 #endif
215                 kmem_cache_free(key_jar, key);
216         }
217 }
218
219 /*
220  * Garbage collector for unused keys.
221  *
222  * This is done in process context so that we don't have to disable interrupts
223  * all over the place.  key_put() schedules this rather than trying to do the
224  * cleanup itself, which means key_put() doesn't have to sleep.
225  */
226 static void key_garbage_collector(struct work_struct *work)
227 {
228         static LIST_HEAD(graveyard);
229         static u8 gc_state;             /* Internal persistent state */
230 #define KEY_GC_REAP_AGAIN       0x01    /* - Need another cycle */
231 #define KEY_GC_REAPING_LINKS    0x02    /* - We need to reap links */
232 #define KEY_GC_SET_TIMER        0x04    /* - We need to restart the timer */
233 #define KEY_GC_REAPING_DEAD_1   0x10    /* - We need to mark dead keys */
234 #define KEY_GC_REAPING_DEAD_2   0x20    /* - We need to reap dead key links */
235 #define KEY_GC_REAPING_DEAD_3   0x40    /* - We need to reap dead keys */
236 #define KEY_GC_FOUND_DEAD_KEY   0x80    /* - We found at least one dead key */
237
238         struct rb_node *cursor;
239         struct key *key;
240         time_t new_timer, limit;
241
242         kenter("[%lx,%x]", key_gc_flags, gc_state);
243
244         limit = current_kernel_time().tv_sec;
245         if (limit > key_gc_delay)
246                 limit -= key_gc_delay;
247         else
248                 limit = key_gc_delay;
249
250         /* Work out what we're going to be doing in this pass */
251         gc_state &= KEY_GC_REAPING_DEAD_1 | KEY_GC_REAPING_DEAD_2;
252         gc_state <<= 1;
253         if (test_and_clear_bit(KEY_GC_KEY_EXPIRED, &key_gc_flags))
254                 gc_state |= KEY_GC_REAPING_LINKS | KEY_GC_SET_TIMER;
255
256         if (test_and_clear_bit(KEY_GC_REAP_KEYTYPE, &key_gc_flags))
257                 gc_state |= KEY_GC_REAPING_DEAD_1;
258         kdebug("new pass %x", gc_state);
259
260         new_timer = LONG_MAX;
261
262         /* As only this function is permitted to remove things from the key
263          * serial tree, if cursor is non-NULL then it will always point to a
264          * valid node in the tree - even if lock got dropped.
265          */
266         spin_lock(&key_serial_lock);
267         cursor = rb_first(&key_serial_tree);
268
269 continue_scanning:
270         while (cursor) {
271                 key = rb_entry(cursor, struct key, serial_node);
272                 cursor = rb_next(cursor);
273
274                 if (atomic_read(&key->usage) == 0)
275                         goto found_unreferenced_key;
276
277                 if (unlikely(gc_state & KEY_GC_REAPING_DEAD_1)) {
278                         if (key->type == key_gc_dead_keytype) {
279                                 gc_state |= KEY_GC_FOUND_DEAD_KEY;
280                                 set_bit(KEY_FLAG_DEAD, &key->flags);
281                                 key->perm = 0;
282                                 goto skip_dead_key;
283                         }
284                 }
285
286                 if (gc_state & KEY_GC_SET_TIMER) {
287                         if (key->expiry > limit && key->expiry < new_timer) {
288                                 kdebug("will expire %x in %ld",
289                                        key_serial(key), key->expiry - limit);
290                                 new_timer = key->expiry;
291                         }
292                 }
293
294                 if (unlikely(gc_state & KEY_GC_REAPING_DEAD_2))
295                         if (key->type == key_gc_dead_keytype)
296                                 gc_state |= KEY_GC_FOUND_DEAD_KEY;
297
298                 if ((gc_state & KEY_GC_REAPING_LINKS) ||
299                     unlikely(gc_state & KEY_GC_REAPING_DEAD_2)) {
300                         if (key->type == &key_type_keyring)
301                                 goto found_keyring;
302                 }
303
304                 if (unlikely(gc_state & KEY_GC_REAPING_DEAD_3))
305                         if (key->type == key_gc_dead_keytype)
306                                 goto destroy_dead_key;
307
308         skip_dead_key:
309                 if (spin_is_contended(&key_serial_lock) || need_resched())
310                         goto contended;
311         }
312
313 contended:
314         spin_unlock(&key_serial_lock);
315
316 maybe_resched:
317         if (cursor) {
318                 cond_resched();
319                 spin_lock(&key_serial_lock);
320                 goto continue_scanning;
321         }
322
323         /* We've completed the pass.  Set the timer if we need to and queue a
324          * new cycle if necessary.  We keep executing cycles until we find one
325          * where we didn't reap any keys.
326          */
327         kdebug("pass complete");
328
329         if (gc_state & KEY_GC_SET_TIMER && new_timer != (time_t)LONG_MAX) {
330                 new_timer += key_gc_delay;
331                 key_schedule_gc(new_timer);
332         }
333
334         if (unlikely(gc_state & KEY_GC_REAPING_DEAD_2) ||
335             !list_empty(&graveyard)) {
336                 /* Make sure that all pending keyring payload destructions are
337                  * fulfilled and that people aren't now looking at dead or
338                  * dying keys that they don't have a reference upon or a link
339                  * to.
340                  */
341                 kdebug("gc sync");
342                 synchronize_rcu();
343         }
344
345         if (!list_empty(&graveyard)) {
346                 kdebug("gc keys");
347                 key_gc_unused_keys(&graveyard);
348         }
349
350         if (unlikely(gc_state & (KEY_GC_REAPING_DEAD_1 |
351                                  KEY_GC_REAPING_DEAD_2))) {
352                 if (!(gc_state & KEY_GC_FOUND_DEAD_KEY)) {
353                         /* No remaining dead keys: short circuit the remaining
354                          * keytype reap cycles.
355                          */
356                         kdebug("dead short");
357                         gc_state &= ~(KEY_GC_REAPING_DEAD_1 | KEY_GC_REAPING_DEAD_2);
358                         gc_state |= KEY_GC_REAPING_DEAD_3;
359                 } else {
360                         gc_state |= KEY_GC_REAP_AGAIN;
361                 }
362         }
363
364         if (unlikely(gc_state & KEY_GC_REAPING_DEAD_3)) {
365                 kdebug("dead wake");
366                 smp_mb();
367                 clear_bit(KEY_GC_REAPING_KEYTYPE, &key_gc_flags);
368                 wake_up_bit(&key_gc_flags, KEY_GC_REAPING_KEYTYPE);
369         }
370
371         if (gc_state & KEY_GC_REAP_AGAIN)
372                 schedule_work(&key_gc_work);
373         kleave(" [end %x]", gc_state);
374         return;
375
376         /* We found an unreferenced key - once we've removed it from the tree,
377          * we can safely drop the lock.
378          */
379 found_unreferenced_key:
380         kdebug("unrefd key %d", key->serial);
381         rb_erase(&key->serial_node, &key_serial_tree);
382         spin_unlock(&key_serial_lock);
383
384         list_add_tail(&key->graveyard_link, &graveyard);
385         gc_state |= KEY_GC_REAP_AGAIN;
386         goto maybe_resched;
387
388         /* We found a keyring and we need to check the payload for links to
389          * dead or expired keys.  We don't flag another reap immediately as we
390          * have to wait for the old payload to be destroyed by RCU before we
391          * can reap the keys to which it refers.
392          */
393 found_keyring:
394         spin_unlock(&key_serial_lock);
395         kdebug("scan keyring %d", key->serial);
396         key_gc_keyring(key, limit);
397         goto maybe_resched;
398
399         /* We found a dead key that is still referenced.  Reset its type and
400          * destroy its payload with its semaphore held.
401          */
402 destroy_dead_key:
403         spin_unlock(&key_serial_lock);
404         kdebug("destroy key %d", key->serial);
405         down_write(&key->sem);
406         key->type = &key_type_dead;
407         if (key_gc_dead_keytype->destroy)
408                 key_gc_dead_keytype->destroy(key);
409         memset(&key->payload, KEY_DESTROY, sizeof(key->payload));
410         up_write(&key->sem);
411         goto maybe_resched;
412 }