David Howells | 5d13544 | 2009-09-02 09:14:00 +0100 | [diff] [blame] | 1 | /* Key garbage collector |
| 2 | * |
| 3 | * Copyright (C) 2009 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 <keys/keyring-type.h> |
| 14 | #include "internal.h" |
| 15 | |
| 16 | /* |
| 17 | * Delay between key revocation/expiry in seconds |
| 18 | */ |
| 19 | unsigned key_gc_delay = 5 * 60; |
| 20 | |
| 21 | /* |
| 22 | * Reaper |
| 23 | */ |
| 24 | static void key_gc_timer_func(unsigned long); |
| 25 | static void key_garbage_collector(struct work_struct *); |
| 26 | static DEFINE_TIMER(key_gc_timer, key_gc_timer_func, 0, 0); |
| 27 | static DECLARE_WORK(key_gc_work, key_garbage_collector); |
| 28 | static key_serial_t key_gc_cursor; /* the last key the gc considered */ |
David Howells | c08ef80 | 2009-09-14 17:26:13 +0100 | [diff] [blame] | 29 | static bool key_gc_again; |
David Howells | 5d13544 | 2009-09-02 09:14:00 +0100 | [diff] [blame] | 30 | static unsigned long key_gc_executing; |
| 31 | static time_t key_gc_next_run = LONG_MAX; |
David Howells | c08ef80 | 2009-09-14 17:26:13 +0100 | [diff] [blame] | 32 | static time_t key_gc_new_timer; |
David Howells | 5d13544 | 2009-09-02 09:14:00 +0100 | [diff] [blame] | 33 | |
| 34 | /* |
| 35 | * Schedule a garbage collection run |
| 36 | * - precision isn't particularly important |
| 37 | */ |
| 38 | void key_schedule_gc(time_t gc_at) |
| 39 | { |
| 40 | unsigned long expires; |
| 41 | time_t now = current_kernel_time().tv_sec; |
| 42 | |
| 43 | kenter("%ld", gc_at - now); |
| 44 | |
David Howells | c08ef80 | 2009-09-14 17:26:13 +0100 | [diff] [blame] | 45 | if (gc_at <= now) { |
David Howells | 5d13544 | 2009-09-02 09:14:00 +0100 | [diff] [blame] | 46 | schedule_work(&key_gc_work); |
| 47 | } else if (gc_at < key_gc_next_run) { |
| 48 | expires = jiffies + (gc_at - now) * HZ; |
| 49 | mod_timer(&key_gc_timer, expires); |
| 50 | } |
| 51 | } |
| 52 | |
| 53 | /* |
| 54 | * The garbage collector timer kicked off |
| 55 | */ |
| 56 | static void key_gc_timer_func(unsigned long data) |
| 57 | { |
| 58 | kenter(""); |
| 59 | key_gc_next_run = LONG_MAX; |
| 60 | schedule_work(&key_gc_work); |
| 61 | } |
| 62 | |
| 63 | /* |
| 64 | * Garbage collect pointers from a keyring |
| 65 | * - return true if we altered the keyring |
| 66 | */ |
| 67 | static bool key_gc_keyring(struct key *keyring, time_t limit) |
David Howells | ee18d64 | 2009-09-02 09:14:21 +0100 | [diff] [blame] | 68 | __releases(key_serial_lock) |
David Howells | 5d13544 | 2009-09-02 09:14:00 +0100 | [diff] [blame] | 69 | { |
| 70 | struct keyring_list *klist; |
| 71 | struct key *key; |
| 72 | int loop; |
| 73 | |
| 74 | kenter("%x", key_serial(keyring)); |
| 75 | |
| 76 | if (test_bit(KEY_FLAG_REVOKED, &keyring->flags)) |
| 77 | goto dont_gc; |
| 78 | |
| 79 | /* scan the keyring looking for dead keys */ |
Paul E. McKenney | e7b0a61 | 2010-02-22 17:04:56 -0800 | [diff] [blame^] | 80 | klist = rcu_dereference_check(keyring->payload.subscriptions, |
| 81 | lockdep_is_held(&key_serial_lock)); |
David Howells | 5d13544 | 2009-09-02 09:14:00 +0100 | [diff] [blame] | 82 | if (!klist) |
| 83 | goto dont_gc; |
| 84 | |
| 85 | for (loop = klist->nkeys - 1; loop >= 0; loop--) { |
| 86 | key = klist->keys[loop]; |
| 87 | if (test_bit(KEY_FLAG_DEAD, &key->flags) || |
| 88 | (key->expiry > 0 && key->expiry <= limit)) |
| 89 | goto do_gc; |
| 90 | } |
| 91 | |
| 92 | dont_gc: |
| 93 | kleave(" = false"); |
| 94 | return false; |
| 95 | |
| 96 | do_gc: |
| 97 | key_gc_cursor = keyring->serial; |
| 98 | key_get(keyring); |
| 99 | spin_unlock(&key_serial_lock); |
| 100 | keyring_gc(keyring, limit); |
| 101 | key_put(keyring); |
| 102 | kleave(" = true"); |
| 103 | return true; |
| 104 | } |
| 105 | |
| 106 | /* |
| 107 | * Garbage collector for keys |
| 108 | * - this involves scanning the keyrings for dead, expired and revoked keys |
| 109 | * that have overstayed their welcome |
| 110 | */ |
| 111 | static void key_garbage_collector(struct work_struct *work) |
| 112 | { |
| 113 | struct rb_node *rb; |
| 114 | key_serial_t cursor; |
| 115 | struct key *key, *xkey; |
David Howells | c08ef80 | 2009-09-14 17:26:13 +0100 | [diff] [blame] | 116 | time_t new_timer = LONG_MAX, limit, now; |
David Howells | 5d13544 | 2009-09-02 09:14:00 +0100 | [diff] [blame] | 117 | |
David Howells | c08ef80 | 2009-09-14 17:26:13 +0100 | [diff] [blame] | 118 | now = current_kernel_time().tv_sec; |
| 119 | kenter("[%x,%ld]", key_gc_cursor, key_gc_new_timer - now); |
David Howells | 5d13544 | 2009-09-02 09:14:00 +0100 | [diff] [blame] | 120 | |
| 121 | if (test_and_set_bit(0, &key_gc_executing)) { |
David Howells | c08ef80 | 2009-09-14 17:26:13 +0100 | [diff] [blame] | 122 | key_schedule_gc(current_kernel_time().tv_sec + 1); |
| 123 | kleave(" [busy; deferring]"); |
David Howells | 5d13544 | 2009-09-02 09:14:00 +0100 | [diff] [blame] | 124 | return; |
| 125 | } |
| 126 | |
David Howells | c08ef80 | 2009-09-14 17:26:13 +0100 | [diff] [blame] | 127 | limit = now; |
David Howells | 5d13544 | 2009-09-02 09:14:00 +0100 | [diff] [blame] | 128 | if (limit > key_gc_delay) |
| 129 | limit -= key_gc_delay; |
| 130 | else |
| 131 | limit = key_gc_delay; |
| 132 | |
| 133 | spin_lock(&key_serial_lock); |
| 134 | |
David Howells | c08ef80 | 2009-09-14 17:26:13 +0100 | [diff] [blame] | 135 | if (unlikely(RB_EMPTY_ROOT(&key_serial_tree))) { |
| 136 | spin_unlock(&key_serial_lock); |
| 137 | clear_bit(0, &key_gc_executing); |
| 138 | return; |
| 139 | } |
David Howells | 5d13544 | 2009-09-02 09:14:00 +0100 | [diff] [blame] | 140 | |
| 141 | cursor = key_gc_cursor; |
| 142 | if (cursor < 0) |
| 143 | cursor = 0; |
David Howells | c08ef80 | 2009-09-14 17:26:13 +0100 | [diff] [blame] | 144 | if (cursor > 0) |
| 145 | new_timer = key_gc_new_timer; |
| 146 | else |
| 147 | key_gc_again = false; |
David Howells | 5d13544 | 2009-09-02 09:14:00 +0100 | [diff] [blame] | 148 | |
| 149 | /* find the first key above the cursor */ |
| 150 | key = NULL; |
| 151 | rb = key_serial_tree.rb_node; |
| 152 | while (rb) { |
| 153 | xkey = rb_entry(rb, struct key, serial_node); |
| 154 | if (cursor < xkey->serial) { |
| 155 | key = xkey; |
| 156 | rb = rb->rb_left; |
| 157 | } else if (cursor > xkey->serial) { |
| 158 | rb = rb->rb_right; |
| 159 | } else { |
| 160 | rb = rb_next(rb); |
| 161 | if (!rb) |
| 162 | goto reached_the_end; |
| 163 | key = rb_entry(rb, struct key, serial_node); |
| 164 | break; |
| 165 | } |
| 166 | } |
| 167 | |
| 168 | if (!key) |
| 169 | goto reached_the_end; |
| 170 | |
| 171 | /* trawl through the keys looking for keyrings */ |
| 172 | for (;;) { |
David Howells | 606531c | 2009-09-16 15:54:14 +0100 | [diff] [blame] | 173 | if (key->expiry > limit && key->expiry < new_timer) { |
David Howells | c08ef80 | 2009-09-14 17:26:13 +0100 | [diff] [blame] | 174 | kdebug("will expire %x in %ld", |
David Howells | 606531c | 2009-09-16 15:54:14 +0100 | [diff] [blame] | 175 | key_serial(key), key->expiry - limit); |
David Howells | 5d13544 | 2009-09-02 09:14:00 +0100 | [diff] [blame] | 176 | new_timer = key->expiry; |
David Howells | c08ef80 | 2009-09-14 17:26:13 +0100 | [diff] [blame] | 177 | } |
David Howells | 5d13544 | 2009-09-02 09:14:00 +0100 | [diff] [blame] | 178 | |
| 179 | if (key->type == &key_type_keyring && |
David Howells | c08ef80 | 2009-09-14 17:26:13 +0100 | [diff] [blame] | 180 | key_gc_keyring(key, limit)) |
| 181 | /* the gc had to release our lock so that the keyring |
| 182 | * could be modified, so we have to get it again */ |
| 183 | goto gc_released_our_lock; |
David Howells | 5d13544 | 2009-09-02 09:14:00 +0100 | [diff] [blame] | 184 | |
| 185 | rb = rb_next(&key->serial_node); |
David Howells | c08ef80 | 2009-09-14 17:26:13 +0100 | [diff] [blame] | 186 | if (!rb) |
| 187 | goto reached_the_end; |
David Howells | 5d13544 | 2009-09-02 09:14:00 +0100 | [diff] [blame] | 188 | key = rb_entry(rb, struct key, serial_node); |
| 189 | } |
| 190 | |
David Howells | c08ef80 | 2009-09-14 17:26:13 +0100 | [diff] [blame] | 191 | gc_released_our_lock: |
| 192 | kdebug("gc_released_our_lock"); |
| 193 | key_gc_new_timer = new_timer; |
| 194 | key_gc_again = true; |
David Howells | 5d13544 | 2009-09-02 09:14:00 +0100 | [diff] [blame] | 195 | clear_bit(0, &key_gc_executing); |
David Howells | c08ef80 | 2009-09-14 17:26:13 +0100 | [diff] [blame] | 196 | schedule_work(&key_gc_work); |
| 197 | kleave(" [continue]"); |
David Howells | 5d13544 | 2009-09-02 09:14:00 +0100 | [diff] [blame] | 198 | return; |
| 199 | |
David Howells | c08ef80 | 2009-09-14 17:26:13 +0100 | [diff] [blame] | 200 | /* when we reach the end of the run, we set the timer for the next one */ |
David Howells | 5d13544 | 2009-09-02 09:14:00 +0100 | [diff] [blame] | 201 | reached_the_end: |
David Howells | c08ef80 | 2009-09-14 17:26:13 +0100 | [diff] [blame] | 202 | kdebug("reached_the_end"); |
| 203 | spin_unlock(&key_serial_lock); |
| 204 | key_gc_new_timer = new_timer; |
David Howells | 5d13544 | 2009-09-02 09:14:00 +0100 | [diff] [blame] | 205 | key_gc_cursor = 0; |
David Howells | c08ef80 | 2009-09-14 17:26:13 +0100 | [diff] [blame] | 206 | clear_bit(0, &key_gc_executing); |
| 207 | |
| 208 | if (key_gc_again) { |
| 209 | /* there may have been a key that expired whilst we were |
| 210 | * scanning, so if we discarded any links we should do another |
| 211 | * scan */ |
| 212 | new_timer = now + 1; |
| 213 | key_schedule_gc(new_timer); |
| 214 | } else if (new_timer < LONG_MAX) { |
| 215 | new_timer += key_gc_delay; |
| 216 | key_schedule_gc(new_timer); |
| 217 | } |
| 218 | kleave(" [end]"); |
David Howells | 5d13544 | 2009-09-02 09:14:00 +0100 | [diff] [blame] | 219 | } |