Commit | Line | Data |
---|---|---|
69664cf1 | 1 | /* Keyring handling |
1da177e4 | 2 | * |
69664cf1 | 3 | * Copyright (C) 2004-2005, 2008 Red Hat, Inc. All Rights Reserved. |
1da177e4 LT |
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 License | |
8 | * as published by the Free Software Foundation; either version | |
9 | * 2 of the License, or (at your option) any later version. | |
10 | */ | |
11 | ||
12 | #include <linux/module.h> | |
13 | #include <linux/init.h> | |
14 | #include <linux/sched.h> | |
15 | #include <linux/slab.h> | |
29db9190 | 16 | #include <linux/security.h> |
1da177e4 LT |
17 | #include <linux/seq_file.h> |
18 | #include <linux/err.h> | |
e9e349b0 | 19 | #include <keys/keyring-type.h> |
512ea3bc | 20 | #include <linux/uaccess.h> |
1da177e4 LT |
21 | #include "internal.h" |
22 | ||
f0641cba DH |
23 | #define rcu_dereference_locked_keyring(keyring) \ |
24 | (rcu_dereference_protected( \ | |
25 | (keyring)->payload.subscriptions, \ | |
26 | rwsem_is_locked((struct rw_semaphore *)&(keyring)->sem))) | |
27 | ||
1da177e4 LT |
28 | /* |
29 | * when plumbing the depths of the key tree, this sets a hard limit set on how | |
30 | * deep we're willing to go | |
31 | */ | |
32 | #define KEYRING_SEARCH_MAX_DEPTH 6 | |
33 | ||
34 | /* | |
35 | * we keep all named keyrings in a hash to speed looking them up | |
36 | */ | |
37 | #define KEYRING_NAME_HASH_SIZE (1 << 5) | |
38 | ||
39 | static struct list_head keyring_name_hash[KEYRING_NAME_HASH_SIZE]; | |
40 | static DEFINE_RWLOCK(keyring_name_lock); | |
41 | ||
42 | static inline unsigned keyring_hash(const char *desc) | |
43 | { | |
44 | unsigned bucket = 0; | |
45 | ||
46 | for (; *desc; desc++) | |
c5b60b5e | 47 | bucket += (unsigned char)*desc; |
1da177e4 LT |
48 | |
49 | return bucket & (KEYRING_NAME_HASH_SIZE - 1); | |
50 | } | |
51 | ||
52 | /* | |
53 | * the keyring type definition | |
54 | */ | |
55 | static int keyring_instantiate(struct key *keyring, | |
56 | const void *data, size_t datalen); | |
1da177e4 | 57 | static int keyring_match(const struct key *keyring, const void *criterion); |
31204ed9 | 58 | static void keyring_revoke(struct key *keyring); |
1da177e4 LT |
59 | static void keyring_destroy(struct key *keyring); |
60 | static void keyring_describe(const struct key *keyring, struct seq_file *m); | |
61 | static long keyring_read(const struct key *keyring, | |
62 | char __user *buffer, size_t buflen); | |
63 | ||
64 | struct key_type key_type_keyring = { | |
65 | .name = "keyring", | |
66 | .def_datalen = sizeof(struct keyring_list), | |
67 | .instantiate = keyring_instantiate, | |
1da177e4 | 68 | .match = keyring_match, |
31204ed9 | 69 | .revoke = keyring_revoke, |
1da177e4 LT |
70 | .destroy = keyring_destroy, |
71 | .describe = keyring_describe, | |
72 | .read = keyring_read, | |
73 | }; | |
74 | ||
7318226e DH |
75 | EXPORT_SYMBOL(key_type_keyring); |
76 | ||
1da177e4 LT |
77 | /* |
78 | * semaphore to serialise link/link calls to prevent two link calls in parallel | |
79 | * introducing a cycle | |
80 | */ | |
1ae8f407 | 81 | static DECLARE_RWSEM(keyring_serialise_link_sem); |
1da177e4 | 82 | |
1da177e4 LT |
83 | /* |
84 | * publish the name of a keyring so that it can be found by name (if it has | |
85 | * one) | |
86 | */ | |
69664cf1 | 87 | static void keyring_publish_name(struct key *keyring) |
1da177e4 LT |
88 | { |
89 | int bucket; | |
90 | ||
91 | if (keyring->description) { | |
92 | bucket = keyring_hash(keyring->description); | |
93 | ||
94 | write_lock(&keyring_name_lock); | |
95 | ||
96 | if (!keyring_name_hash[bucket].next) | |
97 | INIT_LIST_HEAD(&keyring_name_hash[bucket]); | |
98 | ||
99 | list_add_tail(&keyring->type_data.link, | |
100 | &keyring_name_hash[bucket]); | |
101 | ||
102 | write_unlock(&keyring_name_lock); | |
103 | } | |
a8b17ed0 | 104 | } |
1da177e4 | 105 | |
1da177e4 LT |
106 | /* |
107 | * initialise a keyring | |
108 | * - we object if we were given any data | |
109 | */ | |
110 | static int keyring_instantiate(struct key *keyring, | |
111 | const void *data, size_t datalen) | |
112 | { | |
113 | int ret; | |
114 | ||
115 | ret = -EINVAL; | |
116 | if (datalen == 0) { | |
117 | /* make the keyring available by name if it has one */ | |
118 | keyring_publish_name(keyring); | |
119 | ret = 0; | |
120 | } | |
121 | ||
122 | return ret; | |
a8b17ed0 | 123 | } |
1da177e4 | 124 | |
1da177e4 LT |
125 | /* |
126 | * match keyrings on their name | |
127 | */ | |
128 | static int keyring_match(const struct key *keyring, const void *description) | |
129 | { | |
130 | return keyring->description && | |
131 | strcmp(keyring->description, description) == 0; | |
a8b17ed0 | 132 | } |
1da177e4 | 133 | |
1da177e4 LT |
134 | /* |
135 | * dispose of the data dangling from the corpse of a keyring | |
136 | */ | |
137 | static void keyring_destroy(struct key *keyring) | |
138 | { | |
139 | struct keyring_list *klist; | |
140 | int loop; | |
141 | ||
142 | if (keyring->description) { | |
143 | write_lock(&keyring_name_lock); | |
94efe72f DH |
144 | |
145 | if (keyring->type_data.link.next != NULL && | |
146 | !list_empty(&keyring->type_data.link)) | |
147 | list_del(&keyring->type_data.link); | |
148 | ||
1da177e4 LT |
149 | write_unlock(&keyring_name_lock); |
150 | } | |
151 | ||
e7b0a61b PM |
152 | klist = rcu_dereference_check(keyring->payload.subscriptions, |
153 | rcu_read_lock_held() || | |
154 | atomic_read(&keyring->usage) == 0); | |
1da177e4 LT |
155 | if (klist) { |
156 | for (loop = klist->nkeys - 1; loop >= 0; loop--) | |
157 | key_put(klist->keys[loop]); | |
158 | kfree(klist); | |
159 | } | |
a8b17ed0 | 160 | } |
1da177e4 | 161 | |
1da177e4 LT |
162 | /* |
163 | * describe the keyring | |
164 | */ | |
165 | static void keyring_describe(const struct key *keyring, struct seq_file *m) | |
166 | { | |
167 | struct keyring_list *klist; | |
168 | ||
c8563473 | 169 | if (keyring->description) |
1da177e4 | 170 | seq_puts(m, keyring->description); |
c8563473 | 171 | else |
1da177e4 | 172 | seq_puts(m, "[anon]"); |
1da177e4 | 173 | |
76d8aeab DH |
174 | rcu_read_lock(); |
175 | klist = rcu_dereference(keyring->payload.subscriptions); | |
1da177e4 LT |
176 | if (klist) |
177 | seq_printf(m, ": %u/%u", klist->nkeys, klist->maxkeys); | |
178 | else | |
179 | seq_puts(m, ": empty"); | |
76d8aeab | 180 | rcu_read_unlock(); |
a8b17ed0 | 181 | } |
1da177e4 | 182 | |
1da177e4 LT |
183 | /* |
184 | * read a list of key IDs from the keyring's contents | |
76d8aeab | 185 | * - the keyring's semaphore is read-locked |
1da177e4 LT |
186 | */ |
187 | static long keyring_read(const struct key *keyring, | |
188 | char __user *buffer, size_t buflen) | |
189 | { | |
190 | struct keyring_list *klist; | |
191 | struct key *key; | |
192 | size_t qty, tmp; | |
193 | int loop, ret; | |
194 | ||
195 | ret = 0; | |
f0641cba | 196 | klist = rcu_dereference_locked_keyring(keyring); |
1da177e4 LT |
197 | if (klist) { |
198 | /* calculate how much data we could return */ | |
199 | qty = klist->nkeys * sizeof(key_serial_t); | |
200 | ||
201 | if (buffer && buflen > 0) { | |
202 | if (buflen > qty) | |
203 | buflen = qty; | |
204 | ||
205 | /* copy the IDs of the subscribed keys into the | |
206 | * buffer */ | |
207 | ret = -EFAULT; | |
208 | ||
209 | for (loop = 0; loop < klist->nkeys; loop++) { | |
210 | key = klist->keys[loop]; | |
211 | ||
212 | tmp = sizeof(key_serial_t); | |
213 | if (tmp > buflen) | |
214 | tmp = buflen; | |
215 | ||
216 | if (copy_to_user(buffer, | |
217 | &key->serial, | |
218 | tmp) != 0) | |
219 | goto error; | |
220 | ||
221 | buflen -= tmp; | |
222 | if (buflen == 0) | |
223 | break; | |
224 | buffer += tmp; | |
225 | } | |
226 | } | |
227 | ||
228 | ret = qty; | |
229 | } | |
230 | ||
c5b60b5e | 231 | error: |
1da177e4 | 232 | return ret; |
a8b17ed0 | 233 | } |
1da177e4 | 234 | |
1da177e4 LT |
235 | /* |
236 | * allocate a keyring and link into the destination keyring | |
237 | */ | |
238 | struct key *keyring_alloc(const char *description, uid_t uid, gid_t gid, | |
d84f4f99 | 239 | const struct cred *cred, unsigned long flags, |
d720024e | 240 | struct key *dest) |
1da177e4 LT |
241 | { |
242 | struct key *keyring; | |
243 | int ret; | |
244 | ||
245 | keyring = key_alloc(&key_type_keyring, description, | |
d84f4f99 | 246 | uid, gid, cred, |
29db9190 | 247 | (KEY_POS_ALL & ~KEY_POS_SETATTR) | KEY_USR_ALL, |
7e047ef5 | 248 | flags); |
1da177e4 LT |
249 | |
250 | if (!IS_ERR(keyring)) { | |
3e30148c | 251 | ret = key_instantiate_and_link(keyring, NULL, 0, dest, NULL); |
1da177e4 LT |
252 | if (ret < 0) { |
253 | key_put(keyring); | |
254 | keyring = ERR_PTR(ret); | |
255 | } | |
256 | } | |
257 | ||
258 | return keyring; | |
a8b17ed0 | 259 | } |
1da177e4 | 260 | |
1da177e4 LT |
261 | /* |
262 | * search the supplied keyring tree for a key that matches the criterion | |
263 | * - perform a breadth-then-depth search up to the prescribed limit | |
264 | * - we only find keys on which we have search permission | |
265 | * - we use the supplied match function to see if the description (or other | |
266 | * feature of interest) matches | |
3e30148c | 267 | * - we rely on RCU to prevent the keyring lists from disappearing on us |
1da177e4 LT |
268 | * - we return -EAGAIN if we didn't find any matching key |
269 | * - we return -ENOKEY if we only found negative matching keys | |
664cceb0 | 270 | * - we propagate the possession attribute from the keyring ref to the key ref |
1da177e4 | 271 | */ |
664cceb0 | 272 | key_ref_t keyring_search_aux(key_ref_t keyring_ref, |
d84f4f99 | 273 | const struct cred *cred, |
664cceb0 DH |
274 | struct key_type *type, |
275 | const void *description, | |
276 | key_match_func_t match) | |
1da177e4 LT |
277 | { |
278 | struct { | |
76d8aeab | 279 | struct keyring_list *keylist; |
1da177e4 LT |
280 | int kix; |
281 | } stack[KEYRING_SEARCH_MAX_DEPTH]; | |
282 | ||
283 | struct keyring_list *keylist; | |
284 | struct timespec now; | |
dceba994 | 285 | unsigned long possessed, kflags; |
664cceb0 DH |
286 | struct key *keyring, *key; |
287 | key_ref_t key_ref; | |
1da177e4 | 288 | long err; |
76d8aeab | 289 | int sp, kix; |
1da177e4 | 290 | |
664cceb0 DH |
291 | keyring = key_ref_to_ptr(keyring_ref); |
292 | possessed = is_key_possessed(keyring_ref); | |
1da177e4 LT |
293 | key_check(keyring); |
294 | ||
295 | /* top keyring must have search permission to begin the search */ | |
512ea3bc | 296 | err = key_task_permission(keyring_ref, cred, KEY_SEARCH); |
29db9190 DH |
297 | if (err < 0) { |
298 | key_ref = ERR_PTR(err); | |
1da177e4 | 299 | goto error; |
29db9190 | 300 | } |
1da177e4 | 301 | |
664cceb0 | 302 | key_ref = ERR_PTR(-ENOTDIR); |
1da177e4 LT |
303 | if (keyring->type != &key_type_keyring) |
304 | goto error; | |
305 | ||
664cceb0 DH |
306 | rcu_read_lock(); |
307 | ||
1da177e4 LT |
308 | now = current_kernel_time(); |
309 | err = -EAGAIN; | |
310 | sp = 0; | |
311 | ||
dceba994 KC |
312 | /* firstly we should check to see if this top-level keyring is what we |
313 | * are looking for */ | |
314 | key_ref = ERR_PTR(-EAGAIN); | |
315 | kflags = keyring->flags; | |
316 | if (keyring->type == type && match(keyring, description)) { | |
317 | key = keyring; | |
318 | ||
319 | /* check it isn't negative and hasn't expired or been | |
320 | * revoked */ | |
321 | if (kflags & (1 << KEY_FLAG_REVOKED)) | |
322 | goto error_2; | |
323 | if (key->expiry && now.tv_sec >= key->expiry) | |
324 | goto error_2; | |
325 | key_ref = ERR_PTR(-ENOKEY); | |
326 | if (kflags & (1 << KEY_FLAG_NEGATIVE)) | |
327 | goto error_2; | |
328 | goto found; | |
329 | } | |
330 | ||
331 | /* otherwise, the top keyring must not be revoked, expired, or | |
332 | * negatively instantiated if we are to search it */ | |
333 | key_ref = ERR_PTR(-EAGAIN); | |
334 | if (kflags & ((1 << KEY_FLAG_REVOKED) | (1 << KEY_FLAG_NEGATIVE)) || | |
335 | (keyring->expiry && now.tv_sec >= keyring->expiry)) | |
336 | goto error_2; | |
337 | ||
1da177e4 | 338 | /* start processing a new keyring */ |
664cceb0 | 339 | descend: |
76d8aeab | 340 | if (test_bit(KEY_FLAG_REVOKED, &keyring->flags)) |
1da177e4 LT |
341 | goto not_this_keyring; |
342 | ||
76d8aeab | 343 | keylist = rcu_dereference(keyring->payload.subscriptions); |
1da177e4 LT |
344 | if (!keylist) |
345 | goto not_this_keyring; | |
346 | ||
347 | /* iterate through the keys in this keyring first */ | |
348 | for (kix = 0; kix < keylist->nkeys; kix++) { | |
349 | key = keylist->keys[kix]; | |
dceba994 | 350 | kflags = key->flags; |
1da177e4 LT |
351 | |
352 | /* ignore keys not of this type */ | |
353 | if (key->type != type) | |
354 | continue; | |
355 | ||
356 | /* skip revoked keys and expired keys */ | |
dceba994 | 357 | if (kflags & (1 << KEY_FLAG_REVOKED)) |
1da177e4 LT |
358 | continue; |
359 | ||
360 | if (key->expiry && now.tv_sec >= key->expiry) | |
361 | continue; | |
362 | ||
363 | /* keys that don't match */ | |
364 | if (!match(key, description)) | |
365 | continue; | |
366 | ||
367 | /* key must have search permissions */ | |
29db9190 | 368 | if (key_task_permission(make_key_ref(key, possessed), |
d84f4f99 | 369 | cred, KEY_SEARCH) < 0) |
1da177e4 LT |
370 | continue; |
371 | ||
dceba994 KC |
372 | /* we set a different error code if we pass a negative key */ |
373 | if (kflags & (1 << KEY_FLAG_NEGATIVE)) { | |
1da177e4 LT |
374 | err = -ENOKEY; |
375 | continue; | |
376 | } | |
377 | ||
378 | goto found; | |
379 | } | |
380 | ||
381 | /* search through the keyrings nested in this one */ | |
382 | kix = 0; | |
664cceb0 | 383 | ascend: |
76d8aeab | 384 | for (; kix < keylist->nkeys; kix++) { |
1da177e4 LT |
385 | key = keylist->keys[kix]; |
386 | if (key->type != &key_type_keyring) | |
76d8aeab | 387 | continue; |
1da177e4 LT |
388 | |
389 | /* recursively search nested keyrings | |
390 | * - only search keyrings for which we have search permission | |
391 | */ | |
392 | if (sp >= KEYRING_SEARCH_MAX_DEPTH) | |
76d8aeab | 393 | continue; |
1da177e4 | 394 | |
0f6ed7c2 | 395 | if (key_task_permission(make_key_ref(key, possessed), |
d84f4f99 | 396 | cred, KEY_SEARCH) < 0) |
76d8aeab | 397 | continue; |
1da177e4 LT |
398 | |
399 | /* stack the current position */ | |
76d8aeab | 400 | stack[sp].keylist = keylist; |
1da177e4 LT |
401 | stack[sp].kix = kix; |
402 | sp++; | |
403 | ||
404 | /* begin again with the new keyring */ | |
405 | keyring = key; | |
406 | goto descend; | |
1da177e4 LT |
407 | } |
408 | ||
409 | /* the keyring we're looking at was disqualified or didn't contain a | |
410 | * matching key */ | |
664cceb0 | 411 | not_this_keyring: |
1da177e4 LT |
412 | if (sp > 0) { |
413 | /* resume the processing of a keyring higher up in the tree */ | |
414 | sp--; | |
76d8aeab | 415 | keylist = stack[sp].keylist; |
1da177e4 LT |
416 | kix = stack[sp].kix + 1; |
417 | goto ascend; | |
418 | } | |
419 | ||
664cceb0 DH |
420 | key_ref = ERR_PTR(err); |
421 | goto error_2; | |
1da177e4 LT |
422 | |
423 | /* we found a viable match */ | |
664cceb0 | 424 | found: |
1da177e4 | 425 | atomic_inc(&key->usage); |
1da177e4 | 426 | key_check(key); |
664cceb0 DH |
427 | key_ref = make_key_ref(key, possessed); |
428 | error_2: | |
76d8aeab | 429 | rcu_read_unlock(); |
664cceb0 DH |
430 | error: |
431 | return key_ref; | |
a8b17ed0 | 432 | } |
1da177e4 | 433 | |
1da177e4 LT |
434 | /* |
435 | * search the supplied keyring tree for a key that matches the criterion | |
436 | * - perform a breadth-then-depth search up to the prescribed limit | |
437 | * - we only find keys on which we have search permission | |
438 | * - we readlock the keyrings as we search down the tree | |
439 | * - we return -EAGAIN if we didn't find any matching key | |
440 | * - we return -ENOKEY if we only found negative matching keys | |
441 | */ | |
664cceb0 DH |
442 | key_ref_t keyring_search(key_ref_t keyring, |
443 | struct key_type *type, | |
444 | const char *description) | |
1da177e4 | 445 | { |
3e30148c DH |
446 | if (!type->match) |
447 | return ERR_PTR(-ENOKEY); | |
448 | ||
d84f4f99 | 449 | return keyring_search_aux(keyring, current->cred, |
3e30148c | 450 | type, description, type->match); |
a8b17ed0 | 451 | } |
1da177e4 LT |
452 | |
453 | EXPORT_SYMBOL(keyring_search); | |
454 | ||
1da177e4 LT |
455 | /* |
456 | * search the given keyring only (no recursion) | |
457 | * - keyring must be locked by caller | |
c3a9d654 | 458 | * - caller must guarantee that the keyring is a keyring |
1da177e4 | 459 | */ |
664cceb0 DH |
460 | key_ref_t __keyring_search_one(key_ref_t keyring_ref, |
461 | const struct key_type *ktype, | |
462 | const char *description, | |
463 | key_perm_t perm) | |
1da177e4 LT |
464 | { |
465 | struct keyring_list *klist; | |
664cceb0 DH |
466 | unsigned long possessed; |
467 | struct key *keyring, *key; | |
1da177e4 LT |
468 | int loop; |
469 | ||
664cceb0 DH |
470 | keyring = key_ref_to_ptr(keyring_ref); |
471 | possessed = is_key_possessed(keyring_ref); | |
472 | ||
76d8aeab DH |
473 | rcu_read_lock(); |
474 | ||
475 | klist = rcu_dereference(keyring->payload.subscriptions); | |
1da177e4 LT |
476 | if (klist) { |
477 | for (loop = 0; loop < klist->nkeys; loop++) { | |
478 | key = klist->keys[loop]; | |
479 | ||
480 | if (key->type == ktype && | |
3e30148c DH |
481 | (!key->type->match || |
482 | key->type->match(key, description)) && | |
664cceb0 | 483 | key_permission(make_key_ref(key, possessed), |
db1d1d57 | 484 | perm) == 0 && |
76d8aeab | 485 | !test_bit(KEY_FLAG_REVOKED, &key->flags) |
1da177e4 LT |
486 | ) |
487 | goto found; | |
488 | } | |
489 | } | |
490 | ||
664cceb0 DH |
491 | rcu_read_unlock(); |
492 | return ERR_PTR(-ENOKEY); | |
1da177e4 | 493 | |
c5b60b5e | 494 | found: |
1da177e4 | 495 | atomic_inc(&key->usage); |
76d8aeab | 496 | rcu_read_unlock(); |
664cceb0 | 497 | return make_key_ref(key, possessed); |
a8b17ed0 | 498 | } |
1da177e4 | 499 | |
1da177e4 LT |
500 | /* |
501 | * find a keyring with the specified name | |
502 | * - all named keyrings are searched | |
69664cf1 | 503 | * - normally only finds keyrings with search permission for the current process |
1da177e4 | 504 | */ |
69664cf1 | 505 | struct key *find_keyring_by_name(const char *name, bool skip_perm_check) |
1da177e4 LT |
506 | { |
507 | struct key *keyring; | |
508 | int bucket; | |
509 | ||
1da177e4 | 510 | if (!name) |
cea7daa3 | 511 | return ERR_PTR(-EINVAL); |
1da177e4 LT |
512 | |
513 | bucket = keyring_hash(name); | |
514 | ||
515 | read_lock(&keyring_name_lock); | |
516 | ||
517 | if (keyring_name_hash[bucket].next) { | |
518 | /* search this hash bucket for a keyring with a matching name | |
519 | * that's readable and that hasn't been revoked */ | |
520 | list_for_each_entry(keyring, | |
521 | &keyring_name_hash[bucket], | |
522 | type_data.link | |
523 | ) { | |
2ea190d0 SH |
524 | if (keyring->user->user_ns != current_user_ns()) |
525 | continue; | |
526 | ||
76d8aeab | 527 | if (test_bit(KEY_FLAG_REVOKED, &keyring->flags)) |
1da177e4 LT |
528 | continue; |
529 | ||
530 | if (strcmp(keyring->description, name) != 0) | |
531 | continue; | |
532 | ||
69664cf1 DH |
533 | if (!skip_perm_check && |
534 | key_permission(make_key_ref(keyring, 0), | |
0f6ed7c2 | 535 | KEY_SEARCH) < 0) |
1da177e4 LT |
536 | continue; |
537 | ||
cea7daa3 TO |
538 | /* we've got a match but we might end up racing with |
539 | * key_cleanup() if the keyring is currently 'dead' | |
540 | * (ie. it has a zero usage count) */ | |
541 | if (!atomic_inc_not_zero(&keyring->usage)) | |
542 | continue; | |
543 | goto out; | |
1da177e4 LT |
544 | } |
545 | } | |
546 | ||
1da177e4 | 547 | keyring = ERR_PTR(-ENOKEY); |
cea7daa3 TO |
548 | out: |
549 | read_unlock(&keyring_name_lock); | |
1da177e4 | 550 | return keyring; |
a8b17ed0 | 551 | } |
1da177e4 | 552 | |
1da177e4 LT |
553 | /* |
554 | * see if a cycle will will be created by inserting acyclic tree B in acyclic | |
555 | * tree A at the topmost level (ie: as a direct child of A) | |
556 | * - since we are adding B to A at the top level, checking for cycles should | |
557 | * just be a matter of seeing if node A is somewhere in tree B | |
558 | */ | |
559 | static int keyring_detect_cycle(struct key *A, struct key *B) | |
560 | { | |
561 | struct { | |
76d8aeab | 562 | struct keyring_list *keylist; |
1da177e4 LT |
563 | int kix; |
564 | } stack[KEYRING_SEARCH_MAX_DEPTH]; | |
565 | ||
566 | struct keyring_list *keylist; | |
567 | struct key *subtree, *key; | |
568 | int sp, kix, ret; | |
569 | ||
76d8aeab DH |
570 | rcu_read_lock(); |
571 | ||
1da177e4 LT |
572 | ret = -EDEADLK; |
573 | if (A == B) | |
76d8aeab | 574 | goto cycle_detected; |
1da177e4 LT |
575 | |
576 | subtree = B; | |
577 | sp = 0; | |
578 | ||
579 | /* start processing a new keyring */ | |
c5b60b5e | 580 | descend: |
76d8aeab | 581 | if (test_bit(KEY_FLAG_REVOKED, &subtree->flags)) |
1da177e4 LT |
582 | goto not_this_keyring; |
583 | ||
76d8aeab | 584 | keylist = rcu_dereference(subtree->payload.subscriptions); |
1da177e4 LT |
585 | if (!keylist) |
586 | goto not_this_keyring; | |
587 | kix = 0; | |
588 | ||
c5b60b5e | 589 | ascend: |
1da177e4 LT |
590 | /* iterate through the remaining keys in this keyring */ |
591 | for (; kix < keylist->nkeys; kix++) { | |
592 | key = keylist->keys[kix]; | |
593 | ||
594 | if (key == A) | |
595 | goto cycle_detected; | |
596 | ||
597 | /* recursively check nested keyrings */ | |
598 | if (key->type == &key_type_keyring) { | |
599 | if (sp >= KEYRING_SEARCH_MAX_DEPTH) | |
600 | goto too_deep; | |
601 | ||
602 | /* stack the current position */ | |
76d8aeab | 603 | stack[sp].keylist = keylist; |
1da177e4 LT |
604 | stack[sp].kix = kix; |
605 | sp++; | |
606 | ||
607 | /* begin again with the new keyring */ | |
608 | subtree = key; | |
609 | goto descend; | |
610 | } | |
611 | } | |
612 | ||
613 | /* the keyring we're looking at was disqualified or didn't contain a | |
614 | * matching key */ | |
c5b60b5e | 615 | not_this_keyring: |
1da177e4 LT |
616 | if (sp > 0) { |
617 | /* resume the checking of a keyring higher up in the tree */ | |
618 | sp--; | |
76d8aeab | 619 | keylist = stack[sp].keylist; |
1da177e4 LT |
620 | kix = stack[sp].kix + 1; |
621 | goto ascend; | |
622 | } | |
623 | ||
624 | ret = 0; /* no cycles detected */ | |
625 | ||
c5b60b5e | 626 | error: |
76d8aeab | 627 | rcu_read_unlock(); |
1da177e4 LT |
628 | return ret; |
629 | ||
c5b60b5e | 630 | too_deep: |
1da177e4 | 631 | ret = -ELOOP; |
76d8aeab DH |
632 | goto error; |
633 | ||
c5b60b5e | 634 | cycle_detected: |
1da177e4 | 635 | ret = -EDEADLK; |
1da177e4 | 636 | goto error; |
a8b17ed0 | 637 | } |
1da177e4 | 638 | |
cab8eb59 DH |
639 | /* |
640 | * dispose of a keyring list after the RCU grace period, freeing the unlinked | |
641 | * key | |
642 | */ | |
643 | static void keyring_unlink_rcu_disposal(struct rcu_head *rcu) | |
644 | { | |
645 | struct keyring_list *klist = | |
646 | container_of(rcu, struct keyring_list, rcu); | |
647 | ||
4be929be | 648 | if (klist->delkey != USHRT_MAX) |
f70e2e06 | 649 | key_put(klist->keys[klist->delkey]); |
cab8eb59 | 650 | kfree(klist); |
f70e2e06 | 651 | } |
cab8eb59 | 652 | |
1da177e4 | 653 | /* |
f70e2e06 | 654 | * preallocate memory so that a key can be linked into to a keyring |
1da177e4 | 655 | */ |
f70e2e06 DH |
656 | int __key_link_begin(struct key *keyring, const struct key_type *type, |
657 | const char *description, | |
658 | struct keyring_list **_prealloc) | |
659 | __acquires(&keyring->sem) | |
1da177e4 LT |
660 | { |
661 | struct keyring_list *klist, *nklist; | |
662 | unsigned max; | |
663 | size_t size; | |
cab8eb59 | 664 | int loop, ret; |
1da177e4 | 665 | |
f70e2e06 | 666 | kenter("%d,%s,%s,", key_serial(keyring), type->name, description); |
1da177e4 | 667 | |
1da177e4 | 668 | if (keyring->type != &key_type_keyring) |
f70e2e06 DH |
669 | return -ENOTDIR; |
670 | ||
671 | down_write(&keyring->sem); | |
672 | ||
673 | ret = -EKEYREVOKED; | |
674 | if (test_bit(KEY_FLAG_REVOKED, &keyring->flags)) | |
675 | goto error_krsem; | |
1da177e4 | 676 | |
f70e2e06 DH |
677 | /* serialise link/link calls to prevent parallel calls causing a cycle |
678 | * when linking two keyring in opposite orders */ | |
679 | if (type == &key_type_keyring) | |
553d603c DH |
680 | down_write(&keyring_serialise_link_sem); |
681 | ||
f70e2e06 | 682 | klist = rcu_dereference_locked_keyring(keyring); |
1da177e4 | 683 | |
cab8eb59 | 684 | /* see if there's a matching key we can displace */ |
cab8eb59 | 685 | if (klist && klist->nkeys > 0) { |
cab8eb59 DH |
686 | for (loop = klist->nkeys - 1; loop >= 0; loop--) { |
687 | if (klist->keys[loop]->type == type && | |
688 | strcmp(klist->keys[loop]->description, | |
f70e2e06 | 689 | description) == 0 |
cab8eb59 | 690 | ) { |
f70e2e06 DH |
691 | /* found a match - we'll replace this one with |
692 | * the new key */ | |
cab8eb59 DH |
693 | size = sizeof(struct key *) * klist->maxkeys; |
694 | size += sizeof(*klist); | |
695 | BUG_ON(size > PAGE_SIZE); | |
696 | ||
697 | ret = -ENOMEM; | |
48ad504e | 698 | nklist = kmemdup(klist, size, GFP_KERNEL); |
cab8eb59 | 699 | if (!nklist) |
f70e2e06 | 700 | goto error_sem; |
cab8eb59 | 701 | |
f70e2e06 DH |
702 | /* note replacement slot */ |
703 | klist->delkey = nklist->delkey = loop; | |
cab8eb59 DH |
704 | goto done; |
705 | } | |
706 | } | |
707 | } | |
708 | ||
1da177e4 LT |
709 | /* check that we aren't going to overrun the user's quota */ |
710 | ret = key_payload_reserve(keyring, | |
711 | keyring->datalen + KEYQUOTA_LINK_BYTES); | |
712 | if (ret < 0) | |
f70e2e06 | 713 | goto error_sem; |
1da177e4 | 714 | |
1da177e4 | 715 | if (klist && klist->nkeys < klist->maxkeys) { |
f70e2e06 DH |
716 | /* there's sufficient slack space to append directly */ |
717 | nklist = NULL; | |
512ea3bc | 718 | } else { |
1da177e4 LT |
719 | /* grow the key list */ |
720 | max = 4; | |
721 | if (klist) | |
722 | max += klist->maxkeys; | |
723 | ||
724 | ret = -ENFILE; | |
4be929be | 725 | if (max > USHRT_MAX - 1) |
f70e2e06 | 726 | goto error_quota; |
a4014d8f | 727 | size = sizeof(*klist) + sizeof(struct key *) * max; |
1da177e4 | 728 | if (size > PAGE_SIZE) |
f70e2e06 | 729 | goto error_quota; |
1da177e4 LT |
730 | |
731 | ret = -ENOMEM; | |
732 | nklist = kmalloc(size, GFP_KERNEL); | |
733 | if (!nklist) | |
f70e2e06 | 734 | goto error_quota; |
1da177e4 | 735 | |
f70e2e06 | 736 | nklist->maxkeys = max; |
1da177e4 | 737 | if (klist) { |
f70e2e06 | 738 | memcpy(nklist->keys, klist->keys, |
1da177e4 | 739 | sizeof(struct key *) * klist->nkeys); |
f70e2e06 DH |
740 | nklist->delkey = klist->nkeys; |
741 | nklist->nkeys = klist->nkeys + 1; | |
4be929be | 742 | klist->delkey = USHRT_MAX; |
f70e2e06 DH |
743 | } else { |
744 | nklist->nkeys = 1; | |
745 | nklist->delkey = 0; | |
1da177e4 LT |
746 | } |
747 | ||
748 | /* add the key into the new space */ | |
f70e2e06 | 749 | nklist->keys[nklist->delkey] = NULL; |
1da177e4 LT |
750 | } |
751 | ||
cab8eb59 | 752 | done: |
f70e2e06 DH |
753 | *_prealloc = nklist; |
754 | kleave(" = 0"); | |
755 | return 0; | |
1da177e4 | 756 | |
f70e2e06 | 757 | error_quota: |
1da177e4 LT |
758 | /* undo the quota changes */ |
759 | key_payload_reserve(keyring, | |
760 | keyring->datalen - KEYQUOTA_LINK_BYTES); | |
f70e2e06 DH |
761 | error_sem: |
762 | if (type == &key_type_keyring) | |
763 | up_write(&keyring_serialise_link_sem); | |
764 | error_krsem: | |
765 | up_write(&keyring->sem); | |
766 | kleave(" = %d", ret); | |
767 | return ret; | |
768 | } | |
1da177e4 | 769 | |
f70e2e06 DH |
770 | /* |
771 | * check already instantiated keys aren't going to be a problem | |
772 | * - the caller must have called __key_link_begin() | |
773 | * - don't need to call this for keys that were created since __key_link_begin() | |
774 | * was called | |
775 | */ | |
776 | int __key_link_check_live_key(struct key *keyring, struct key *key) | |
777 | { | |
778 | if (key->type == &key_type_keyring) | |
779 | /* check that we aren't going to create a cycle by linking one | |
780 | * keyring to another */ | |
781 | return keyring_detect_cycle(keyring, key); | |
782 | return 0; | |
783 | } | |
784 | ||
785 | /* | |
786 | * link a key into to a keyring | |
787 | * - must be called with __key_link_begin() having being called | |
788 | * - discard already extant link to matching key if there is one | |
789 | */ | |
790 | void __key_link(struct key *keyring, struct key *key, | |
791 | struct keyring_list **_prealloc) | |
792 | { | |
793 | struct keyring_list *klist, *nklist; | |
794 | ||
795 | nklist = *_prealloc; | |
796 | *_prealloc = NULL; | |
797 | ||
798 | kenter("%d,%d,%p", keyring->serial, key->serial, nklist); | |
799 | ||
800 | klist = rcu_dereference_protected(keyring->payload.subscriptions, | |
801 | rwsem_is_locked(&keyring->sem)); | |
802 | ||
803 | atomic_inc(&key->usage); | |
804 | ||
805 | /* there's a matching key we can displace or an empty slot in a newly | |
806 | * allocated list we can fill */ | |
807 | if (nklist) { | |
808 | kdebug("replace %hu/%hu/%hu", | |
809 | nklist->delkey, nklist->nkeys, nklist->maxkeys); | |
810 | ||
811 | nklist->keys[nklist->delkey] = key; | |
812 | ||
813 | rcu_assign_pointer(keyring->payload.subscriptions, nklist); | |
814 | ||
815 | /* dispose of the old keyring list and, if there was one, the | |
816 | * displaced key */ | |
817 | if (klist) { | |
818 | kdebug("dispose %hu/%hu/%hu", | |
819 | klist->delkey, klist->nkeys, klist->maxkeys); | |
820 | call_rcu(&klist->rcu, keyring_unlink_rcu_disposal); | |
821 | } | |
822 | } else { | |
823 | /* there's sufficient slack space to append directly */ | |
824 | klist->keys[klist->nkeys] = key; | |
825 | smp_wmb(); | |
826 | klist->nkeys++; | |
827 | } | |
828 | } | |
829 | ||
830 | /* | |
831 | * finish linking a key into to a keyring | |
832 | * - must be called with __key_link_begin() having being called | |
833 | */ | |
834 | void __key_link_end(struct key *keyring, struct key_type *type, | |
835 | struct keyring_list *prealloc) | |
836 | __releases(&keyring->sem) | |
837 | { | |
838 | BUG_ON(type == NULL); | |
839 | BUG_ON(type->name == NULL); | |
840 | kenter("%d,%s,%p", keyring->serial, type->name, prealloc); | |
841 | ||
842 | if (type == &key_type_keyring) | |
843 | up_write(&keyring_serialise_link_sem); | |
844 | ||
845 | if (prealloc) { | |
846 | kfree(prealloc); | |
847 | key_payload_reserve(keyring, | |
848 | keyring->datalen - KEYQUOTA_LINK_BYTES); | |
849 | } | |
850 | up_write(&keyring->sem); | |
851 | } | |
1da177e4 | 852 | |
1da177e4 LT |
853 | /* |
854 | * link a key to a keyring | |
855 | */ | |
856 | int key_link(struct key *keyring, struct key *key) | |
857 | { | |
f70e2e06 | 858 | struct keyring_list *prealloc; |
1da177e4 LT |
859 | int ret; |
860 | ||
861 | key_check(keyring); | |
862 | key_check(key); | |
863 | ||
f70e2e06 DH |
864 | ret = __key_link_begin(keyring, key->type, key->description, &prealloc); |
865 | if (ret == 0) { | |
866 | ret = __key_link_check_live_key(keyring, key); | |
867 | if (ret == 0) | |
868 | __key_link(keyring, key, &prealloc); | |
869 | __key_link_end(keyring, key->type, prealloc); | |
870 | } | |
1da177e4 LT |
871 | |
872 | return ret; | |
f70e2e06 | 873 | } |
1da177e4 LT |
874 | |
875 | EXPORT_SYMBOL(key_link); | |
876 | ||
1da177e4 LT |
877 | /* |
878 | * unlink the first link to a key from a keyring | |
879 | */ | |
880 | int key_unlink(struct key *keyring, struct key *key) | |
881 | { | |
76d8aeab | 882 | struct keyring_list *klist, *nklist; |
1da177e4 LT |
883 | int loop, ret; |
884 | ||
885 | key_check(keyring); | |
886 | key_check(key); | |
887 | ||
888 | ret = -ENOTDIR; | |
889 | if (keyring->type != &key_type_keyring) | |
890 | goto error; | |
891 | ||
892 | down_write(&keyring->sem); | |
893 | ||
f0641cba | 894 | klist = rcu_dereference_locked_keyring(keyring); |
1da177e4 LT |
895 | if (klist) { |
896 | /* search the keyring for the key */ | |
897 | for (loop = 0; loop < klist->nkeys; loop++) | |
898 | if (klist->keys[loop] == key) | |
899 | goto key_is_present; | |
900 | } | |
901 | ||
902 | up_write(&keyring->sem); | |
903 | ret = -ENOENT; | |
904 | goto error; | |
905 | ||
76d8aeab DH |
906 | key_is_present: |
907 | /* we need to copy the key list for RCU purposes */ | |
a4014d8f DH |
908 | nklist = kmalloc(sizeof(*klist) + |
909 | sizeof(struct key *) * klist->maxkeys, | |
76d8aeab DH |
910 | GFP_KERNEL); |
911 | if (!nklist) | |
912 | goto nomem; | |
913 | nklist->maxkeys = klist->maxkeys; | |
914 | nklist->nkeys = klist->nkeys - 1; | |
915 | ||
916 | if (loop > 0) | |
917 | memcpy(&nklist->keys[0], | |
918 | &klist->keys[0], | |
a4014d8f | 919 | loop * sizeof(struct key *)); |
76d8aeab DH |
920 | |
921 | if (loop < nklist->nkeys) | |
922 | memcpy(&nklist->keys[loop], | |
923 | &klist->keys[loop + 1], | |
a4014d8f | 924 | (nklist->nkeys - loop) * sizeof(struct key *)); |
76d8aeab | 925 | |
1da177e4 LT |
926 | /* adjust the user's quota */ |
927 | key_payload_reserve(keyring, | |
928 | keyring->datalen - KEYQUOTA_LINK_BYTES); | |
929 | ||
76d8aeab | 930 | rcu_assign_pointer(keyring->payload.subscriptions, nklist); |
1da177e4 | 931 | |
76d8aeab | 932 | up_write(&keyring->sem); |
1da177e4 | 933 | |
76d8aeab DH |
934 | /* schedule for later cleanup */ |
935 | klist->delkey = loop; | |
936 | call_rcu(&klist->rcu, keyring_unlink_rcu_disposal); | |
1da177e4 | 937 | |
1da177e4 LT |
938 | ret = 0; |
939 | ||
76d8aeab | 940 | error: |
1da177e4 | 941 | return ret; |
76d8aeab DH |
942 | nomem: |
943 | ret = -ENOMEM; | |
944 | up_write(&keyring->sem); | |
945 | goto error; | |
a8b17ed0 | 946 | } |
1da177e4 LT |
947 | |
948 | EXPORT_SYMBOL(key_unlink); | |
949 | ||
76d8aeab DH |
950 | /* |
951 | * dispose of a keyring list after the RCU grace period, releasing the keys it | |
952 | * links to | |
953 | */ | |
954 | static void keyring_clear_rcu_disposal(struct rcu_head *rcu) | |
955 | { | |
956 | struct keyring_list *klist; | |
957 | int loop; | |
958 | ||
959 | klist = container_of(rcu, struct keyring_list, rcu); | |
960 | ||
961 | for (loop = klist->nkeys - 1; loop >= 0; loop--) | |
962 | key_put(klist->keys[loop]); | |
963 | ||
964 | kfree(klist); | |
a8b17ed0 | 965 | } |
76d8aeab | 966 | |
1da177e4 LT |
967 | /* |
968 | * clear the specified process keyring | |
969 | * - implements keyctl(KEYCTL_CLEAR) | |
970 | */ | |
971 | int keyring_clear(struct key *keyring) | |
972 | { | |
973 | struct keyring_list *klist; | |
76d8aeab | 974 | int ret; |
1da177e4 LT |
975 | |
976 | ret = -ENOTDIR; | |
977 | if (keyring->type == &key_type_keyring) { | |
978 | /* detach the pointer block with the locks held */ | |
979 | down_write(&keyring->sem); | |
980 | ||
f0641cba | 981 | klist = rcu_dereference_locked_keyring(keyring); |
1da177e4 LT |
982 | if (klist) { |
983 | /* adjust the quota */ | |
984 | key_payload_reserve(keyring, | |
985 | sizeof(struct keyring_list)); | |
986 | ||
76d8aeab DH |
987 | rcu_assign_pointer(keyring->payload.subscriptions, |
988 | NULL); | |
1da177e4 LT |
989 | } |
990 | ||
991 | up_write(&keyring->sem); | |
992 | ||
993 | /* free the keys after the locks have been dropped */ | |
76d8aeab DH |
994 | if (klist) |
995 | call_rcu(&klist->rcu, keyring_clear_rcu_disposal); | |
1da177e4 LT |
996 | |
997 | ret = 0; | |
998 | } | |
999 | ||
1000 | return ret; | |
a8b17ed0 | 1001 | } |
1da177e4 LT |
1002 | |
1003 | EXPORT_SYMBOL(keyring_clear); | |
31204ed9 | 1004 | |
31204ed9 DH |
1005 | /* |
1006 | * dispose of the links from a revoked keyring | |
1007 | * - called with the key sem write-locked | |
1008 | */ | |
1009 | static void keyring_revoke(struct key *keyring) | |
1010 | { | |
f0641cba DH |
1011 | struct keyring_list *klist; |
1012 | ||
1013 | klist = rcu_dereference_locked_keyring(keyring); | |
31204ed9 DH |
1014 | |
1015 | /* adjust the quota */ | |
1016 | key_payload_reserve(keyring, 0); | |
1017 | ||
1018 | if (klist) { | |
1019 | rcu_assign_pointer(keyring->payload.subscriptions, NULL); | |
1020 | call_rcu(&klist->rcu, keyring_clear_rcu_disposal); | |
1021 | } | |
a8b17ed0 | 1022 | } |
5d135440 DH |
1023 | |
1024 | /* | |
1025 | * Determine whether a key is dead | |
1026 | */ | |
1027 | static bool key_is_dead(struct key *key, time_t limit) | |
1028 | { | |
1029 | return test_bit(KEY_FLAG_DEAD, &key->flags) || | |
1030 | (key->expiry > 0 && key->expiry <= limit); | |
1031 | } | |
1032 | ||
1033 | /* | |
1034 | * Collect garbage from the contents of a keyring | |
1035 | */ | |
1036 | void keyring_gc(struct key *keyring, time_t limit) | |
1037 | { | |
1038 | struct keyring_list *klist, *new; | |
1039 | struct key *key; | |
1040 | int loop, keep, max; | |
1041 | ||
c08ef808 | 1042 | kenter("{%x,%s}", key_serial(keyring), keyring->description); |
5d135440 DH |
1043 | |
1044 | down_write(&keyring->sem); | |
1045 | ||
f0641cba | 1046 | klist = rcu_dereference_locked_keyring(keyring); |
5d135440 | 1047 | if (!klist) |
c08ef808 | 1048 | goto no_klist; |
5d135440 DH |
1049 | |
1050 | /* work out how many subscriptions we're keeping */ | |
1051 | keep = 0; | |
1052 | for (loop = klist->nkeys - 1; loop >= 0; loop--) | |
c08ef808 | 1053 | if (!key_is_dead(klist->keys[loop], limit)) |
5d135440 DH |
1054 | keep++; |
1055 | ||
1056 | if (keep == klist->nkeys) | |
1057 | goto just_return; | |
1058 | ||
1059 | /* allocate a new keyring payload */ | |
1060 | max = roundup(keep, 4); | |
1061 | new = kmalloc(sizeof(struct keyring_list) + max * sizeof(struct key *), | |
1062 | GFP_KERNEL); | |
1063 | if (!new) | |
c08ef808 | 1064 | goto nomem; |
5d135440 DH |
1065 | new->maxkeys = max; |
1066 | new->nkeys = 0; | |
1067 | new->delkey = 0; | |
1068 | ||
1069 | /* install the live keys | |
1070 | * - must take care as expired keys may be updated back to life | |
1071 | */ | |
1072 | keep = 0; | |
1073 | for (loop = klist->nkeys - 1; loop >= 0; loop--) { | |
1074 | key = klist->keys[loop]; | |
1075 | if (!key_is_dead(key, limit)) { | |
1076 | if (keep >= max) | |
1077 | goto discard_new; | |
1078 | new->keys[keep++] = key_get(key); | |
1079 | } | |
1080 | } | |
1081 | new->nkeys = keep; | |
1082 | ||
1083 | /* adjust the quota */ | |
1084 | key_payload_reserve(keyring, | |
1085 | sizeof(struct keyring_list) + | |
1086 | KEYQUOTA_LINK_BYTES * keep); | |
1087 | ||
1088 | if (keep == 0) { | |
1089 | rcu_assign_pointer(keyring->payload.subscriptions, NULL); | |
1090 | kfree(new); | |
1091 | } else { | |
1092 | rcu_assign_pointer(keyring->payload.subscriptions, new); | |
1093 | } | |
1094 | ||
1095 | up_write(&keyring->sem); | |
1096 | ||
1097 | call_rcu(&klist->rcu, keyring_clear_rcu_disposal); | |
1098 | kleave(" [yes]"); | |
1099 | return; | |
1100 | ||
1101 | discard_new: | |
1102 | new->nkeys = keep; | |
1103 | keyring_clear_rcu_disposal(&new->rcu); | |
c08ef808 DH |
1104 | up_write(&keyring->sem); |
1105 | kleave(" [discard]"); | |
1106 | return; | |
1107 | ||
5d135440 DH |
1108 | just_return: |
1109 | up_write(&keyring->sem); | |
c08ef808 DH |
1110 | kleave(" [no dead]"); |
1111 | return; | |
1112 | ||
1113 | no_klist: | |
1114 | up_write(&keyring->sem); | |
1115 | kleave(" [no_klist]"); | |
1116 | return; | |
1117 | ||
1118 | nomem: | |
1119 | up_write(&keyring->sem); | |
1120 | kleave(" [oom]"); | |
5d135440 | 1121 | } |