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