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 */ 29 static bool key_gc_again; 30 static unsigned long key_gc_executing; 31 static time_t key_gc_next_run = LONG_MAX; 32 static time_t key_gc_new_timer; 33 34 /* 35 * Schedule a garbage collection run. 36 * - time 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 45 if (gc_at <= now) { 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 * 66 * Return true if we altered the keyring. 67 */ 68 static bool key_gc_keyring(struct key *keyring, time_t limit) 69 __releases(key_serial_lock) 70 { 71 struct keyring_list *klist; 72 struct key *key; 73 int loop; 74 75 kenter("%x", key_serial(keyring)); 76 77 if (test_bit(KEY_FLAG_REVOKED, &keyring->flags)) 78 goto dont_gc; 79 80 /* scan the keyring looking for dead keys */ 81 rcu_read_lock(); 82 klist = rcu_dereference(keyring->payload.subscriptions); 83 if (!klist) 84 goto unlock_dont_gc; 85 86 for (loop = klist->nkeys - 1; loop >= 0; loop--) { 87 key = klist->keys[loop]; 88 if (test_bit(KEY_FLAG_DEAD, &key->flags) || 89 (key->expiry > 0 && key->expiry <= limit)) 90 goto do_gc; 91 } 92 93 unlock_dont_gc: 94 rcu_read_unlock(); 95 dont_gc: 96 kleave(" = false"); 97 return false; 98 99 do_gc: 100 rcu_read_unlock(); 101 key_gc_cursor = keyring->serial; 102 key_get(keyring); 103 spin_unlock(&key_serial_lock); 104 keyring_gc(keyring, limit); 105 key_put(keyring); 106 kleave(" = true"); 107 return true; 108 } 109 110 /* 111 * Garbage collector for keys. This involves scanning the keyrings for dead, 112 * expired and revoked keys that have overstayed their welcome 113 */ 114 static void key_garbage_collector(struct work_struct *work) 115 { 116 struct rb_node *rb; 117 key_serial_t cursor; 118 struct key *key, *xkey; 119 time_t new_timer = LONG_MAX, limit, now; 120 121 now = current_kernel_time().tv_sec; 122 kenter("[%x,%ld]", key_gc_cursor, key_gc_new_timer - now); 123 124 if (test_and_set_bit(0, &key_gc_executing)) { 125 key_schedule_gc(current_kernel_time().tv_sec + 1); 126 kleave(" [busy; deferring]"); 127 return; 128 } 129 130 limit = now; 131 if (limit > key_gc_delay) 132 limit -= key_gc_delay; 133 else 134 limit = key_gc_delay; 135 136 spin_lock(&key_serial_lock); 137 138 if (unlikely(RB_EMPTY_ROOT(&key_serial_tree))) { 139 spin_unlock(&key_serial_lock); 140 clear_bit(0, &key_gc_executing); 141 return; 142 } 143 144 cursor = key_gc_cursor; 145 if (cursor < 0) 146 cursor = 0; 147 if (cursor > 0) 148 new_timer = key_gc_new_timer; 149 else 150 key_gc_again = false; 151 152 /* find the first key above the cursor */ 153 key = NULL; 154 rb = key_serial_tree.rb_node; 155 while (rb) { 156 xkey = rb_entry(rb, struct key, serial_node); 157 if (cursor < xkey->serial) { 158 key = xkey; 159 rb = rb->rb_left; 160 } else if (cursor > xkey->serial) { 161 rb = rb->rb_right; 162 } else { 163 rb = rb_next(rb); 164 if (!rb) 165 goto reached_the_end; 166 key = rb_entry(rb, struct key, serial_node); 167 break; 168 } 169 } 170 171 if (!key) 172 goto reached_the_end; 173 174 /* trawl through the keys looking for keyrings */ 175 for (;;) { 176 if (key->expiry > limit && key->expiry < new_timer) { 177 kdebug("will expire %x in %ld", 178 key_serial(key), key->expiry - limit); 179 new_timer = key->expiry; 180 } 181 182 if (key->type == &key_type_keyring && 183 key_gc_keyring(key, limit)) 184 /* the gc had to release our lock so that the keyring 185 * could be modified, so we have to get it again */ 186 goto gc_released_our_lock; 187 188 rb = rb_next(&key->serial_node); 189 if (!rb) 190 goto reached_the_end; 191 key = rb_entry(rb, struct key, serial_node); 192 } 193 194 gc_released_our_lock: 195 kdebug("gc_released_our_lock"); 196 key_gc_new_timer = new_timer; 197 key_gc_again = true; 198 clear_bit(0, &key_gc_executing); 199 schedule_work(&key_gc_work); 200 kleave(" [continue]"); 201 return; 202 203 /* when we reach the end of the run, we set the timer for the next one */ 204 reached_the_end: 205 kdebug("reached_the_end"); 206 spin_unlock(&key_serial_lock); 207 key_gc_new_timer = new_timer; 208 key_gc_cursor = 0; 209 clear_bit(0, &key_gc_executing); 210 211 if (key_gc_again) { 212 /* there may have been a key that expired whilst we were 213 * scanning, so if we discarded any links we should do another 214 * scan */ 215 new_timer = now + 1; 216 key_schedule_gc(new_timer); 217 } else if (new_timer < LONG_MAX) { 218 new_timer += key_gc_delay; 219 key_schedule_gc(new_timer); 220 } 221 kleave(" [end]"); 222 } 223