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 */
key_schedule_gc(time_t gc_at)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 */
key_gc_timer_func(unsigned long data)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 */
key_gc_keyring(struct key * keyring,time_t limit)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 */
key_garbage_collector(struct work_struct * work)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