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 * - 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 * - return true if we altered the keyring 66 */ 67 static bool key_gc_keyring(struct key *keyring, time_t limit) 68 __releases(key_serial_lock) 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_check(keyring->payload.subscriptions, 81 lockdep_is_held(&key_serial_lock)); 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; 116 time_t new_timer = LONG_MAX, limit, now; 117 118 now = current_kernel_time().tv_sec; 119 kenter("[%x,%ld]", key_gc_cursor, key_gc_new_timer - now); 120 121 if (test_and_set_bit(0, &key_gc_executing)) { 122 key_schedule_gc(current_kernel_time().tv_sec + 1); 123 kleave(" [busy; deferring]"); 124 return; 125 } 126 127 limit = now; 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 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 } 140 141 cursor = key_gc_cursor; 142 if (cursor < 0) 143 cursor = 0; 144 if (cursor > 0) 145 new_timer = key_gc_new_timer; 146 else 147 key_gc_again = false; 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 (;;) { 173 if (key->expiry > limit && key->expiry < new_timer) { 174 kdebug("will expire %x in %ld", 175 key_serial(key), key->expiry - limit); 176 new_timer = key->expiry; 177 } 178 179 if (key->type == &key_type_keyring && 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; 184 185 rb = rb_next(&key->serial_node); 186 if (!rb) 187 goto reached_the_end; 188 key = rb_entry(rb, struct key, serial_node); 189 } 190 191 gc_released_our_lock: 192 kdebug("gc_released_our_lock"); 193 key_gc_new_timer = new_timer; 194 key_gc_again = true; 195 clear_bit(0, &key_gc_executing); 196 schedule_work(&key_gc_work); 197 kleave(" [continue]"); 198 return; 199 200 /* when we reach the end of the run, we set the timer for the next one */ 201 reached_the_end: 202 kdebug("reached_the_end"); 203 spin_unlock(&key_serial_lock); 204 key_gc_new_timer = new_timer; 205 key_gc_cursor = 0; 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]"); 219 } 220