blob: 19902319d097acc75ef6246d6981e33b43a8c69f [file] [log] [blame]
David Howells5d135442009-09-02 09:14:00 +01001/* 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 */
19unsigned key_gc_delay = 5 * 60;
20
21/*
22 * Reaper
23 */
24static void key_gc_timer_func(unsigned long);
25static void key_garbage_collector(struct work_struct *);
26static DEFINE_TIMER(key_gc_timer, key_gc_timer_func, 0, 0);
27static DECLARE_WORK(key_gc_work, key_garbage_collector);
28static key_serial_t key_gc_cursor; /* the last key the gc considered */
David Howellsc08ef802009-09-14 17:26:13 +010029static bool key_gc_again;
David Howells5d135442009-09-02 09:14:00 +010030static unsigned long key_gc_executing;
31static time_t key_gc_next_run = LONG_MAX;
David Howellsc08ef802009-09-14 17:26:13 +010032static time_t key_gc_new_timer;
David Howells5d135442009-09-02 09:14:00 +010033
34/*
35 * Schedule a garbage collection run
36 * - precision isn't particularly important
37 */
38void 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 Howellsc08ef802009-09-14 17:26:13 +010045 if (gc_at <= now) {
David Howells5d135442009-09-02 09:14:00 +010046 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 */
56static 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 */
67static bool key_gc_keyring(struct key *keyring, time_t limit)
David Howellsee18d642009-09-02 09:14:21 +010068 __releases(key_serial_lock)
David Howells5d135442009-09-02 09:14:00 +010069{
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 */
Paul E. McKenneye7b0a612010-02-22 17:04:56 -080080 klist = rcu_dereference_check(keyring->payload.subscriptions,
81 lockdep_is_held(&key_serial_lock));
David Howells5d135442009-09-02 09:14:00 +010082 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
92dont_gc:
93 kleave(" = false");
94 return false;
95
96do_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 */
111static void key_garbage_collector(struct work_struct *work)
112{
113 struct rb_node *rb;
114 key_serial_t cursor;
115 struct key *key, *xkey;
David Howellsc08ef802009-09-14 17:26:13 +0100116 time_t new_timer = LONG_MAX, limit, now;
David Howells5d135442009-09-02 09:14:00 +0100117
David Howellsc08ef802009-09-14 17:26:13 +0100118 now = current_kernel_time().tv_sec;
119 kenter("[%x,%ld]", key_gc_cursor, key_gc_new_timer - now);
David Howells5d135442009-09-02 09:14:00 +0100120
121 if (test_and_set_bit(0, &key_gc_executing)) {
David Howellsc08ef802009-09-14 17:26:13 +0100122 key_schedule_gc(current_kernel_time().tv_sec + 1);
123 kleave(" [busy; deferring]");
David Howells5d135442009-09-02 09:14:00 +0100124 return;
125 }
126
David Howellsc08ef802009-09-14 17:26:13 +0100127 limit = now;
David Howells5d135442009-09-02 09:14:00 +0100128 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
David Howellsc08ef802009-09-14 17:26:13 +0100135 if (unlikely(RB_EMPTY_ROOT(&key_serial_tree))) {
136 spin_unlock(&key_serial_lock);
137 clear_bit(0, &key_gc_executing);
138 return;
139 }
David Howells5d135442009-09-02 09:14:00 +0100140
141 cursor = key_gc_cursor;
142 if (cursor < 0)
143 cursor = 0;
David Howellsc08ef802009-09-14 17:26:13 +0100144 if (cursor > 0)
145 new_timer = key_gc_new_timer;
146 else
147 key_gc_again = false;
David Howells5d135442009-09-02 09:14:00 +0100148
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 (;;) {
David Howells606531c2009-09-16 15:54:14 +0100173 if (key->expiry > limit && key->expiry < new_timer) {
David Howellsc08ef802009-09-14 17:26:13 +0100174 kdebug("will expire %x in %ld",
David Howells606531c2009-09-16 15:54:14 +0100175 key_serial(key), key->expiry - limit);
David Howells5d135442009-09-02 09:14:00 +0100176 new_timer = key->expiry;
David Howellsc08ef802009-09-14 17:26:13 +0100177 }
David Howells5d135442009-09-02 09:14:00 +0100178
179 if (key->type == &key_type_keyring &&
David Howellsc08ef802009-09-14 17:26:13 +0100180 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;
David Howells5d135442009-09-02 09:14:00 +0100184
185 rb = rb_next(&key->serial_node);
David Howellsc08ef802009-09-14 17:26:13 +0100186 if (!rb)
187 goto reached_the_end;
David Howells5d135442009-09-02 09:14:00 +0100188 key = rb_entry(rb, struct key, serial_node);
189 }
190
David Howellsc08ef802009-09-14 17:26:13 +0100191gc_released_our_lock:
192 kdebug("gc_released_our_lock");
193 key_gc_new_timer = new_timer;
194 key_gc_again = true;
David Howells5d135442009-09-02 09:14:00 +0100195 clear_bit(0, &key_gc_executing);
David Howellsc08ef802009-09-14 17:26:13 +0100196 schedule_work(&key_gc_work);
197 kleave(" [continue]");
David Howells5d135442009-09-02 09:14:00 +0100198 return;
199
David Howellsc08ef802009-09-14 17:26:13 +0100200 /* when we reach the end of the run, we set the timer for the next one */
David Howells5d135442009-09-02 09:14:00 +0100201reached_the_end:
David Howellsc08ef802009-09-14 17:26:13 +0100202 kdebug("reached_the_end");
203 spin_unlock(&key_serial_lock);
204 key_gc_new_timer = new_timer;
David Howells5d135442009-09-02 09:14:00 +0100205 key_gc_cursor = 0;
David Howellsc08ef802009-09-14 17:26:13 +0100206 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]");
David Howells5d135442009-09-02 09:14:00 +0100219}