Commit | Line | Data |
---|---|---|
5d135440 DH |
1 | /* Key garbage collector |
2 | * | |
0c061b57 | 3 | * Copyright (C) 2009-2011 Red Hat, Inc. All Rights Reserved. |
5d135440 DH |
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> | |
8bc16dea DH |
13 | #include <linux/slab.h> |
14 | #include <linux/security.h> | |
5d135440 DH |
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 | /* | |
8bc16dea DH |
24 | * Reaper for unused keys. |
25 | */ | |
0c061b57 DH |
26 | static void key_garbage_collector(struct work_struct *work); |
27 | DECLARE_WORK(key_gc_work, key_garbage_collector); | |
8bc16dea DH |
28 | |
29 | /* | |
30 | * Reaper for links from keyrings to dead keys. | |
5d135440 DH |
31 | */ |
32 | static void key_gc_timer_func(unsigned long); | |
5d135440 | 33 | static DEFINE_TIMER(key_gc_timer, key_gc_timer_func, 0, 0); |
0c061b57 | 34 | |
5d135440 | 35 | static time_t key_gc_next_run = LONG_MAX; |
0c061b57 DH |
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 | }; | |
5d135440 DH |
51 | |
52 | /* | |
973c9f4f DH |
53 | * Schedule a garbage collection run. |
54 | * - time precision isn't particularly important | |
5d135440 DH |
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 | ||
0c061b57 DH |
63 | if (gc_at <= now || test_bit(KEY_GC_REAP_KEYTYPE, &key_gc_flags)) { |
64 | kdebug("IMMEDIATE"); | |
d199798b | 65 | queue_work(system_nrt_wq, &key_gc_work); |
5d135440 | 66 | } else if (gc_at < key_gc_next_run) { |
0c061b57 DH |
67 | kdebug("DEFERRED"); |
68 | key_gc_next_run = gc_at; | |
5d135440 DH |
69 | expires = jiffies + (gc_at - now) * HZ; |
70 | mod_timer(&key_gc_timer, expires); | |
71 | } | |
72 | } | |
73 | ||
74 | /* | |
0c061b57 DH |
75 | * 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. | |
5d135440 DH |
77 | */ |
78 | static void key_gc_timer_func(unsigned long data) | |
79 | { | |
80 | kenter(""); | |
81 | key_gc_next_run = LONG_MAX; | |
0c061b57 | 82 | set_bit(KEY_GC_KEY_EXPIRED, &key_gc_flags); |
d199798b | 83 | queue_work(system_nrt_wq, &key_gc_work); |
5d135440 DH |
84 | } |
85 | ||
0c061b57 DH |
86 | /* |
87 | * wait_on_bit() sleep function for uninterruptible waiting | |
88 | */ | |
89 | static 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 | */ | |
105 | void 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 | ||
5d135440 | 125 | /* |
973c9f4f DH |
126 | * Garbage collect pointers from a keyring. |
127 | * | |
0c061b57 DH |
128 | * 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. | |
5d135440 | 130 | */ |
0c061b57 | 131 | static void key_gc_keyring(struct key *keyring, time_t limit) |
5d135440 DH |
132 | { |
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 */ | |
cf8304e8 DH |
143 | rcu_read_lock(); |
144 | klist = rcu_dereference(keyring->payload.subscriptions); | |
5d135440 | 145 | if (!klist) |
cf8304e8 | 146 | goto unlock_dont_gc; |
5d135440 | 147 | |
efde8b6e DH |
148 | loop = klist->nkeys; |
149 | smp_rmb(); | |
150 | for (loop--; loop >= 0; loop--) { | |
5d135440 DH |
151 | 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 | ||
cf8304e8 DH |
157 | unlock_dont_gc: |
158 | rcu_read_unlock(); | |
5d135440 | 159 | dont_gc: |
0c061b57 DH |
160 | kleave(" [no gc]"); |
161 | return; | |
5d135440 DH |
162 | |
163 | do_gc: | |
cf8304e8 | 164 | rcu_read_unlock(); |
0c061b57 | 165 | |
5d135440 | 166 | keyring_gc(keyring, limit); |
0c061b57 | 167 | kleave(" [gc]"); |
5d135440 DH |
168 | } |
169 | ||
170 | /* | |
0c061b57 | 171 | * Garbage collect an unreferenced, detached key |
5d135440 | 172 | */ |
0c061b57 | 173 | static noinline void key_gc_unused_key(struct key *key) |
5d135440 | 174 | { |
0c061b57 | 175 | key_check(key); |
5d135440 | 176 | |
0c061b57 | 177 | security_key_free(key); |
5d135440 | 178 | |
0c061b57 DH |
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); | |
5d135440 DH |
185 | } |
186 | ||
0c061b57 DH |
187 | atomic_dec(&key->user->nkeys); |
188 | if (test_bit(KEY_FLAG_INSTANTIATED, &key->flags)) | |
189 | atomic_dec(&key->user->nikeys); | |
5d135440 | 190 | |
0c061b57 | 191 | key_user_put(key->user); |
5d135440 | 192 | |
0c061b57 DH |
193 | /* now throw away the key memory */ |
194 | if (key->type->destroy) | |
195 | key->type->destroy(key); | |
5d135440 | 196 | |
0c061b57 | 197 | kfree(key->description); |
5d135440 | 198 | |
0c061b57 DH |
199 | #ifdef KEY_DEBUGGING |
200 | key->magic = KEY_DEBUG_MAGIC_X; | |
201 | #endif | |
202 | kmem_cache_free(key_jar, key); | |
5d135440 | 203 | } |
8bc16dea DH |
204 | |
205 | /* | |
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 | */ | |
0c061b57 | 212 | static void key_garbage_collector(struct work_struct *work) |
8bc16dea | 213 | { |
0c061b57 DH |
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; | |
8bc16dea | 224 | struct key *key; |
0c061b57 DH |
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; | |
8bc16dea | 246 | |
0c061b57 DH |
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 | */ | |
8bc16dea | 251 | spin_lock(&key_serial_lock); |
0c061b57 | 252 | cursor = rb_first(&key_serial_tree); |
8bc16dea | 253 | |
0c061b57 DH |
254 | continue_scanning: |
255 | while (cursor) { | |
256 | key = rb_entry(cursor, struct key, serial_node); | |
257 | cursor = rb_next(cursor); | |
8bc16dea DH |
258 | |
259 | if (atomic_read(&key->usage) == 0) | |
0c061b57 DH |
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; | |
8bc16dea DH |
296 | } |
297 | ||
0c061b57 | 298 | contended: |
8bc16dea | 299 | spin_unlock(&key_serial_lock); |
8bc16dea | 300 | |
0c061b57 DH |
301 | maybe_resched: |
302 | if (cursor) { | |
303 | cond_resched(); | |
304 | spin_lock(&key_serial_lock); | |
305 | goto continue_scanning; | |
306 | } | |
8bc16dea | 307 | |
0c061b57 DH |
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"); | |
8bc16dea | 313 | |
0c061b57 DH |
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 | } | |
8bc16dea | 318 | |
0c061b57 DH |
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(); | |
8bc16dea DH |
326 | } |
327 | ||
0c061b57 DH |
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 | } | |
8bc16dea | 341 | |
0c061b57 DH |
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 | } | |
8bc16dea | 348 | |
0c061b57 DH |
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; | |
8bc16dea | 353 | |
0c061b57 DH |
354 | /* We found an unreferenced key - once we've removed it from the tree, |
355 | * we can safely drop the lock. | |
356 | */ | |
357 | found_unreferenced_key: | |
358 | kdebug("unrefd key %d", key->serial); | |
359 | rb_erase(&key->serial_node, &key_serial_tree); | |
360 | spin_unlock(&key_serial_lock); | |
8bc16dea | 361 | |
0c061b57 DH |
362 | key_gc_unused_key(key); |
363 | gc_state |= KEY_GC_REAP_AGAIN; | |
364 | goto maybe_resched; | |
8bc16dea | 365 | |
0c061b57 DH |
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 | */ | |
371 | found_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 | */ | |
380 | destroy_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; | |
8bc16dea | 390 | } |