blob: 4770be375ffece3d506ea86b769aee3bf8607595 [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 */
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
91dont_gc:
92 kleave(" = false");
93 return false;
94
95do_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 */
110static void key_garbage_collector(struct work_struct *work)
111{
112 struct rb_node *rb;
113 key_serial_t cursor;
114 struct key *key, *xkey;
David Howellsc08ef802009-09-14 17:26:13 +0100115 time_t new_timer = LONG_MAX, limit, now;
David Howells5d135442009-09-02 09:14:00 +0100116
David Howellsc08ef802009-09-14 17:26:13 +0100117 now = current_kernel_time().tv_sec;
118 kenter("[%x,%ld]", key_gc_cursor, key_gc_new_timer - now);
David Howells5d135442009-09-02 09:14:00 +0100119
120 if (test_and_set_bit(0, &key_gc_executing)) {
David Howellsc08ef802009-09-14 17:26:13 +0100121 key_schedule_gc(current_kernel_time().tv_sec + 1);
122 kleave(" [busy; deferring]");
David Howells5d135442009-09-02 09:14:00 +0100123 return;
124 }
125
David Howellsc08ef802009-09-14 17:26:13 +0100126 limit = now;
David Howells5d135442009-09-02 09:14:00 +0100127 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
David Howellsc08ef802009-09-14 17:26:13 +0100134 if (unlikely(RB_EMPTY_ROOT(&key_serial_tree))) {
135 spin_unlock(&key_serial_lock);
136 clear_bit(0, &key_gc_executing);
137 return;
138 }
David Howells5d135442009-09-02 09:14:00 +0100139
140 cursor = key_gc_cursor;
141 if (cursor < 0)
142 cursor = 0;
David Howellsc08ef802009-09-14 17:26:13 +0100143 if (cursor > 0)
144 new_timer = key_gc_new_timer;
145 else
146 key_gc_again = false;
David Howells5d135442009-09-02 09:14:00 +0100147
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 (;;) {
David Howells606531c2009-09-16 15:54:14 +0100172 if (key->expiry > limit && key->expiry < new_timer) {
David Howellsc08ef802009-09-14 17:26:13 +0100173 kdebug("will expire %x in %ld",
David Howells606531c2009-09-16 15:54:14 +0100174 key_serial(key), key->expiry - limit);
David Howells5d135442009-09-02 09:14:00 +0100175 new_timer = key->expiry;
David Howellsc08ef802009-09-14 17:26:13 +0100176 }
David Howells5d135442009-09-02 09:14:00 +0100177
178 if (key->type == &key_type_keyring &&
David Howellsc08ef802009-09-14 17:26:13 +0100179 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;
David Howells5d135442009-09-02 09:14:00 +0100183
184 rb = rb_next(&key->serial_node);
David Howellsc08ef802009-09-14 17:26:13 +0100185 if (!rb)
186 goto reached_the_end;
David Howells5d135442009-09-02 09:14:00 +0100187 key = rb_entry(rb, struct key, serial_node);
188 }
189
David Howellsc08ef802009-09-14 17:26:13 +0100190gc_released_our_lock:
191 kdebug("gc_released_our_lock");
192 key_gc_new_timer = new_timer;
193 key_gc_again = true;
David Howells5d135442009-09-02 09:14:00 +0100194 clear_bit(0, &key_gc_executing);
David Howellsc08ef802009-09-14 17:26:13 +0100195 schedule_work(&key_gc_work);
196 kleave(" [continue]");
David Howells5d135442009-09-02 09:14:00 +0100197 return;
198
David Howellsc08ef802009-09-14 17:26:13 +0100199 /* when we reach the end of the run, we set the timer for the next one */
David Howells5d135442009-09-02 09:14:00 +0100200reached_the_end:
David Howellsc08ef802009-09-14 17:26:13 +0100201 kdebug("reached_the_end");
202 spin_unlock(&key_serial_lock);
203 key_gc_new_timer = new_timer;
David Howells5d135442009-09-02 09:14:00 +0100204 key_gc_cursor = 0;
David Howellsc08ef802009-09-14 17:26:13 +0100205 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]");
David Howells5d135442009-09-02 09:14:00 +0100218}