Root/
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 | queue_work(system_nrt_wq, &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 | queue_work(system_nrt_wq, &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 | queue_work(system_nrt_wq, &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 | queue_work(system_nrt_wq, &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 | } |
413 |
Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master
Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9