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 */ |
| 80 | klist = rcu_dereference(keyring->payload.subscriptions); |
| 81 | if (!klist) |
| 82 | goto dont_gc; |
| 83 | |
| 84 | for (loop = klist->nkeys - 1; loop >= 0; loop--) { |
| 85 | key = klist->keys[loop]; |
| 86 | if (test_bit(KEY_FLAG_DEAD, &key->flags) || |
| 87 | (key->expiry > 0 && key->expiry <= limit)) |
| 88 | goto do_gc; |
| 89 | } |
| 90 | |
| 91 | dont_gc: |
| 92 | kleave(" = false"); |
| 93 | return false; |
| 94 | |
| 95 | do_gc: |
| 96 | key_gc_cursor = keyring->serial; |
| 97 | key_get(keyring); |
| 98 | spin_unlock(&key_serial_lock); |
| 99 | keyring_gc(keyring, limit); |
| 100 | key_put(keyring); |
| 101 | kleave(" = true"); |
| 102 | return true; |
| 103 | } |
| 104 | |
| 105 | /* |
| 106 | * Garbage collector for keys |
| 107 | * - this involves scanning the keyrings for dead, expired and revoked keys |
| 108 | * that have overstayed their welcome |
| 109 | */ |
| 110 | static void key_garbage_collector(struct work_struct *work) |
| 111 | { |
| 112 | struct rb_node *rb; |
| 113 | key_serial_t cursor; |
| 114 | struct key *key, *xkey; |
David Howells | c08ef80 | 2009-09-14 17:26:13 +0100 | [diff] [blame] | 115 | time_t new_timer = LONG_MAX, limit, now; |
David Howells | 5d13544 | 2009-09-02 09:14:00 +0100 | [diff] [blame] | 116 | |
David Howells | c08ef80 | 2009-09-14 17:26:13 +0100 | [diff] [blame] | 117 | now = current_kernel_time().tv_sec; |
| 118 | kenter("[%x,%ld]", key_gc_cursor, key_gc_new_timer - now); |
David Howells | 5d13544 | 2009-09-02 09:14:00 +0100 | [diff] [blame] | 119 | |
| 120 | if (test_and_set_bit(0, &key_gc_executing)) { |
David Howells | c08ef80 | 2009-09-14 17:26:13 +0100 | [diff] [blame] | 121 | key_schedule_gc(current_kernel_time().tv_sec + 1); |
| 122 | kleave(" [busy; deferring]"); |
David Howells | 5d13544 | 2009-09-02 09:14:00 +0100 | [diff] [blame] | 123 | return; |
| 124 | } |
| 125 | |
David Howells | c08ef80 | 2009-09-14 17:26:13 +0100 | [diff] [blame] | 126 | limit = now; |
David Howells | 5d13544 | 2009-09-02 09:14:00 +0100 | [diff] [blame] | 127 | if (limit > key_gc_delay) |
| 128 | limit -= key_gc_delay; |
| 129 | else |
| 130 | limit = key_gc_delay; |
| 131 | |
| 132 | spin_lock(&key_serial_lock); |
| 133 | |
David Howells | c08ef80 | 2009-09-14 17:26:13 +0100 | [diff] [blame] | 134 | if (unlikely(RB_EMPTY_ROOT(&key_serial_tree))) { |
| 135 | spin_unlock(&key_serial_lock); |
| 136 | clear_bit(0, &key_gc_executing); |
| 137 | return; |
| 138 | } |
David Howells | 5d13544 | 2009-09-02 09:14:00 +0100 | [diff] [blame] | 139 | |
| 140 | cursor = key_gc_cursor; |
| 141 | if (cursor < 0) |
| 142 | cursor = 0; |
David Howells | c08ef80 | 2009-09-14 17:26:13 +0100 | [diff] [blame] | 143 | if (cursor > 0) |
| 144 | new_timer = key_gc_new_timer; |
| 145 | else |
| 146 | key_gc_again = false; |
David Howells | 5d13544 | 2009-09-02 09:14:00 +0100 | [diff] [blame] | 147 | |
| 148 | /* find the first key above the cursor */ |
| 149 | key = NULL; |
| 150 | rb = key_serial_tree.rb_node; |
| 151 | while (rb) { |
| 152 | xkey = rb_entry(rb, struct key, serial_node); |
| 153 | if (cursor < xkey->serial) { |
| 154 | key = xkey; |
| 155 | rb = rb->rb_left; |
| 156 | } else if (cursor > xkey->serial) { |
| 157 | rb = rb->rb_right; |
| 158 | } else { |
| 159 | rb = rb_next(rb); |
| 160 | if (!rb) |
| 161 | goto reached_the_end; |
| 162 | key = rb_entry(rb, struct key, serial_node); |
| 163 | break; |
| 164 | } |
| 165 | } |
| 166 | |
| 167 | if (!key) |
| 168 | goto reached_the_end; |
| 169 | |
| 170 | /* trawl through the keys looking for keyrings */ |
| 171 | for (;;) { |
David Howells | 606531c | 2009-09-16 15:54:14 +0100 | [diff] [blame] | 172 | if (key->expiry > limit && key->expiry < new_timer) { |
David Howells | c08ef80 | 2009-09-14 17:26:13 +0100 | [diff] [blame] | 173 | kdebug("will expire %x in %ld", |
David Howells | 606531c | 2009-09-16 15:54:14 +0100 | [diff] [blame] | 174 | key_serial(key), key->expiry - limit); |
David Howells | 5d13544 | 2009-09-02 09:14:00 +0100 | [diff] [blame] | 175 | new_timer = key->expiry; |
David Howells | c08ef80 | 2009-09-14 17:26:13 +0100 | [diff] [blame] | 176 | } |
David Howells | 5d13544 | 2009-09-02 09:14:00 +0100 | [diff] [blame] | 177 | |
| 178 | if (key->type == &key_type_keyring && |
David Howells | c08ef80 | 2009-09-14 17:26:13 +0100 | [diff] [blame] | 179 | key_gc_keyring(key, limit)) |
| 180 | /* the gc had to release our lock so that the keyring |
| 181 | * could be modified, so we have to get it again */ |
| 182 | goto gc_released_our_lock; |
David Howells | 5d13544 | 2009-09-02 09:14:00 +0100 | [diff] [blame] | 183 | |
| 184 | rb = rb_next(&key->serial_node); |
David Howells | c08ef80 | 2009-09-14 17:26:13 +0100 | [diff] [blame] | 185 | if (!rb) |
| 186 | goto reached_the_end; |
David Howells | 5d13544 | 2009-09-02 09:14:00 +0100 | [diff] [blame] | 187 | key = rb_entry(rb, struct key, serial_node); |
| 188 | } |
| 189 | |
David Howells | c08ef80 | 2009-09-14 17:26:13 +0100 | [diff] [blame] | 190 | gc_released_our_lock: |
| 191 | kdebug("gc_released_our_lock"); |
| 192 | key_gc_new_timer = new_timer; |
| 193 | key_gc_again = true; |
David Howells | 5d13544 | 2009-09-02 09:14:00 +0100 | [diff] [blame] | 194 | clear_bit(0, &key_gc_executing); |
David Howells | c08ef80 | 2009-09-14 17:26:13 +0100 | [diff] [blame] | 195 | schedule_work(&key_gc_work); |
| 196 | kleave(" [continue]"); |
David Howells | 5d13544 | 2009-09-02 09:14:00 +0100 | [diff] [blame] | 197 | return; |
| 198 | |
David Howells | c08ef80 | 2009-09-14 17:26:13 +0100 | [diff] [blame] | 199 | /* 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] | 200 | reached_the_end: |
David Howells | c08ef80 | 2009-09-14 17:26:13 +0100 | [diff] [blame] | 201 | kdebug("reached_the_end"); |
| 202 | spin_unlock(&key_serial_lock); |
| 203 | key_gc_new_timer = new_timer; |
David Howells | 5d13544 | 2009-09-02 09:14:00 +0100 | [diff] [blame] | 204 | key_gc_cursor = 0; |
David Howells | c08ef80 | 2009-09-14 17:26:13 +0100 | [diff] [blame] | 205 | clear_bit(0, &key_gc_executing); |
| 206 | |
| 207 | if (key_gc_again) { |
| 208 | /* there may have been a key that expired whilst we were |
| 209 | * scanning, so if we discarded any links we should do another |
| 210 | * scan */ |
| 211 | new_timer = now + 1; |
| 212 | key_schedule_gc(new_timer); |
| 213 | } else if (new_timer < LONG_MAX) { |
| 214 | new_timer += key_gc_delay; |
| 215 | key_schedule_gc(new_timer); |
| 216 | } |
| 217 | kleave(" [end]"); |
David Howells | 5d13544 | 2009-09-02 09:14:00 +0100 | [diff] [blame] | 218 | } |