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