1 /* Keyring handling 2 * 3 * Copyright (C) 2004-2005, 2008 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 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> 16 #include <linux/security.h> 17 #include <linux/seq_file.h> 18 #include <linux/err.h> 19 #include <keys/keyring-type.h> 20 #include <linux/uaccess.h> 21 #include "internal.h" 22 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 28 #define rcu_deref_link_locked(klist, index, keyring) \ 29 (rcu_dereference_protected( \ 30 (klist)->keys[index], \ 31 rwsem_is_locked((struct rw_semaphore *)&(keyring)->sem))) 32 33 #define MAX_KEYRING_LINKS \ 34 min_t(size_t, USHRT_MAX - 1, \ 35 ((PAGE_SIZE - sizeof(struct keyring_list)) / sizeof(struct key *))) 36 37 #define KEY_LINK_FIXQUOTA 1UL 38 39 /* 40 * When plumbing the depths of the key tree, this sets a hard limit 41 * set on how deep we're willing to go. 42 */ 43 #define KEYRING_SEARCH_MAX_DEPTH 6 44 45 /* 46 * We keep all named keyrings in a hash to speed looking them up. 47 */ 48 #define KEYRING_NAME_HASH_SIZE (1 << 5) 49 50 static struct list_head keyring_name_hash[KEYRING_NAME_HASH_SIZE]; 51 static DEFINE_RWLOCK(keyring_name_lock); 52 53 static inline unsigned keyring_hash(const char *desc) 54 { 55 unsigned bucket = 0; 56 57 for (; *desc; desc++) 58 bucket += (unsigned char)*desc; 59 60 return bucket & (KEYRING_NAME_HASH_SIZE - 1); 61 } 62 63 /* 64 * The keyring key type definition. Keyrings are simply keys of this type and 65 * can be treated as ordinary keys in addition to having their own special 66 * operations. 67 */ 68 static int keyring_instantiate(struct key *keyring, 69 struct key_preparsed_payload *prep); 70 static int keyring_match(const struct key *keyring, const void *criterion); 71 static void keyring_revoke(struct key *keyring); 72 static void keyring_destroy(struct key *keyring); 73 static void keyring_describe(const struct key *keyring, struct seq_file *m); 74 static long keyring_read(const struct key *keyring, 75 char __user *buffer, size_t buflen); 76 77 struct key_type key_type_keyring = { 78 .name = "keyring", 79 .def_datalen = sizeof(struct keyring_list), 80 .instantiate = keyring_instantiate, 81 .match = keyring_match, 82 .revoke = keyring_revoke, 83 .destroy = keyring_destroy, 84 .describe = keyring_describe, 85 .read = keyring_read, 86 }; 87 EXPORT_SYMBOL(key_type_keyring); 88 89 /* 90 * Semaphore to serialise link/link calls to prevent two link calls in parallel 91 * introducing a cycle. 92 */ 93 static DECLARE_RWSEM(keyring_serialise_link_sem); 94 95 /* 96 * Publish the name of a keyring so that it can be found by name (if it has 97 * one). 98 */ 99 static void keyring_publish_name(struct key *keyring) 100 { 101 int bucket; 102 103 if (keyring->description) { 104 bucket = keyring_hash(keyring->description); 105 106 write_lock(&keyring_name_lock); 107 108 if (!keyring_name_hash[bucket].next) 109 INIT_LIST_HEAD(&keyring_name_hash[bucket]); 110 111 list_add_tail(&keyring->type_data.link, 112 &keyring_name_hash[bucket]); 113 114 write_unlock(&keyring_name_lock); 115 } 116 } 117 118 /* 119 * Initialise a keyring. 120 * 121 * Returns 0 on success, -EINVAL if given any data. 122 */ 123 static int keyring_instantiate(struct key *keyring, 124 struct key_preparsed_payload *prep) 125 { 126 int ret; 127 128 ret = -EINVAL; 129 if (prep->datalen == 0) { 130 /* make the keyring available by name if it has one */ 131 keyring_publish_name(keyring); 132 ret = 0; 133 } 134 135 return ret; 136 } 137 138 /* 139 * Match keyrings on their name 140 */ 141 static int keyring_match(const struct key *keyring, const void *description) 142 { 143 return keyring->description && 144 strcmp(keyring->description, description) == 0; 145 } 146 147 /* 148 * Clean up a keyring when it is destroyed. Unpublish its name if it had one 149 * and dispose of its data. 150 * 151 * The garbage collector detects the final key_put(), removes the keyring from 152 * the serial number tree and then does RCU synchronisation before coming here, 153 * so we shouldn't need to worry about code poking around here with the RCU 154 * readlock held by this time. 155 */ 156 static void keyring_destroy(struct key *keyring) 157 { 158 struct keyring_list *klist; 159 int loop; 160 161 if (keyring->description) { 162 write_lock(&keyring_name_lock); 163 164 if (keyring->type_data.link.next != NULL && 165 !list_empty(&keyring->type_data.link)) 166 list_del(&keyring->type_data.link); 167 168 write_unlock(&keyring_name_lock); 169 } 170 171 klist = rcu_access_pointer(keyring->payload.subscriptions); 172 if (klist) { 173 for (loop = klist->nkeys - 1; loop >= 0; loop--) 174 key_put(rcu_access_pointer(klist->keys[loop])); 175 kfree(klist); 176 } 177 } 178 179 /* 180 * Describe a keyring for /proc. 181 */ 182 static void keyring_describe(const struct key *keyring, struct seq_file *m) 183 { 184 struct keyring_list *klist; 185 186 if (keyring->description) 187 seq_puts(m, keyring->description); 188 else 189 seq_puts(m, "[anon]"); 190 191 if (key_is_instantiated(keyring)) { 192 rcu_read_lock(); 193 klist = rcu_dereference(keyring->payload.subscriptions); 194 if (klist) 195 seq_printf(m, ": %u/%u", klist->nkeys, klist->maxkeys); 196 else 197 seq_puts(m, ": empty"); 198 rcu_read_unlock(); 199 } 200 } 201 202 /* 203 * Read a list of key IDs from the keyring's contents in binary form 204 * 205 * The keyring's semaphore is read-locked by the caller. 206 */ 207 static long keyring_read(const struct key *keyring, 208 char __user *buffer, size_t buflen) 209 { 210 struct keyring_list *klist; 211 struct key *key; 212 size_t qty, tmp; 213 int loop, ret; 214 215 ret = 0; 216 klist = rcu_dereference_locked_keyring(keyring); 217 if (klist) { 218 /* calculate how much data we could return */ 219 qty = klist->nkeys * sizeof(key_serial_t); 220 221 if (buffer && buflen > 0) { 222 if (buflen > qty) 223 buflen = qty; 224 225 /* copy the IDs of the subscribed keys into the 226 * buffer */ 227 ret = -EFAULT; 228 229 for (loop = 0; loop < klist->nkeys; loop++) { 230 key = rcu_deref_link_locked(klist, loop, 231 keyring); 232 233 tmp = sizeof(key_serial_t); 234 if (tmp > buflen) 235 tmp = buflen; 236 237 if (copy_to_user(buffer, 238 &key->serial, 239 tmp) != 0) 240 goto error; 241 242 buflen -= tmp; 243 if (buflen == 0) 244 break; 245 buffer += tmp; 246 } 247 } 248 249 ret = qty; 250 } 251 252 error: 253 return ret; 254 } 255 256 /* 257 * Allocate a keyring and link into the destination keyring. 258 */ 259 struct key *keyring_alloc(const char *description, kuid_t uid, kgid_t gid, 260 const struct cred *cred, key_perm_t perm, 261 unsigned long flags, struct key *dest) 262 { 263 struct key *keyring; 264 int ret; 265 266 keyring = key_alloc(&key_type_keyring, description, 267 uid, gid, cred, perm, flags); 268 if (!IS_ERR(keyring)) { 269 ret = key_instantiate_and_link(keyring, NULL, 0, dest, NULL); 270 if (ret < 0) { 271 key_put(keyring); 272 keyring = ERR_PTR(ret); 273 } 274 } 275 276 return keyring; 277 } 278 EXPORT_SYMBOL(keyring_alloc); 279 280 /** 281 * keyring_search_aux - Search a keyring tree for a key matching some criteria 282 * @keyring_ref: A pointer to the keyring with possession indicator. 283 * @cred: The credentials to use for permissions checks. 284 * @type: The type of key to search for. 285 * @description: Parameter for @match. 286 * @match: Function to rule on whether or not a key is the one required. 287 * @no_state_check: Don't check if a matching key is bad 288 * 289 * Search the supplied keyring tree for a key that matches the criteria given. 290 * The root keyring and any linked keyrings must grant Search permission to the 291 * caller to be searchable and keys can only be found if they too grant Search 292 * to the caller. The possession flag on the root keyring pointer controls use 293 * of the possessor bits in permissions checking of the entire tree. In 294 * addition, the LSM gets to forbid keyring searches and key matches. 295 * 296 * The search is performed as a breadth-then-depth search up to the prescribed 297 * limit (KEYRING_SEARCH_MAX_DEPTH). 298 * 299 * Keys are matched to the type provided and are then filtered by the match 300 * function, which is given the description to use in any way it sees fit. The 301 * match function may use any attributes of a key that it wishes to to 302 * determine the match. Normally the match function from the key type would be 303 * used. 304 * 305 * RCU is used to prevent the keyring key lists from disappearing without the 306 * need to take lots of locks. 307 * 308 * Returns a pointer to the found key and increments the key usage count if 309 * successful; -EAGAIN if no matching keys were found, or if expired or revoked 310 * keys were found; -ENOKEY if only negative keys were found; -ENOTDIR if the 311 * specified keyring wasn't a keyring. 312 * 313 * In the case of a successful return, the possession attribute from 314 * @keyring_ref is propagated to the returned key reference. 315 */ 316 key_ref_t keyring_search_aux(key_ref_t keyring_ref, 317 const struct cred *cred, 318 struct key_type *type, 319 const void *description, 320 key_match_func_t match, 321 bool no_state_check) 322 { 323 struct { 324 /* Need a separate keylist pointer for RCU purposes */ 325 struct key *keyring; 326 struct keyring_list *keylist; 327 int kix; 328 } stack[KEYRING_SEARCH_MAX_DEPTH]; 329 330 struct keyring_list *keylist; 331 struct timespec now; 332 unsigned long possessed, kflags; 333 struct key *keyring, *key; 334 key_ref_t key_ref; 335 long err; 336 int sp, nkeys, kix; 337 338 keyring = key_ref_to_ptr(keyring_ref); 339 possessed = is_key_possessed(keyring_ref); 340 key_check(keyring); 341 342 /* top keyring must have search permission to begin the search */ 343 err = key_task_permission(keyring_ref, cred, KEY_SEARCH); 344 if (err < 0) { 345 key_ref = ERR_PTR(err); 346 goto error; 347 } 348 349 key_ref = ERR_PTR(-ENOTDIR); 350 if (keyring->type != &key_type_keyring) 351 goto error; 352 353 rcu_read_lock(); 354 355 now = current_kernel_time(); 356 err = -EAGAIN; 357 sp = 0; 358 359 /* firstly we should check to see if this top-level keyring is what we 360 * are looking for */ 361 key_ref = ERR_PTR(-EAGAIN); 362 kflags = keyring->flags; 363 if (keyring->type == type && match(keyring, description)) { 364 key = keyring; 365 if (no_state_check) 366 goto found; 367 368 /* check it isn't negative and hasn't expired or been 369 * revoked */ 370 if (kflags & (1 << KEY_FLAG_REVOKED)) 371 goto error_2; 372 if (key->expiry && now.tv_sec >= key->expiry) 373 goto error_2; 374 key_ref = ERR_PTR(key->type_data.reject_error); 375 if (kflags & (1 << KEY_FLAG_NEGATIVE)) 376 goto error_2; 377 goto found; 378 } 379 380 /* otherwise, the top keyring must not be revoked, expired, or 381 * negatively instantiated if we are to search it */ 382 key_ref = ERR_PTR(-EAGAIN); 383 if (kflags & ((1 << KEY_FLAG_INVALIDATED) | 384 (1 << KEY_FLAG_REVOKED) | 385 (1 << KEY_FLAG_NEGATIVE)) || 386 (keyring->expiry && now.tv_sec >= keyring->expiry)) 387 goto error_2; 388 389 /* start processing a new keyring */ 390 descend: 391 kflags = keyring->flags; 392 if (kflags & ((1 << KEY_FLAG_INVALIDATED) | 393 (1 << KEY_FLAG_REVOKED))) 394 goto not_this_keyring; 395 396 keylist = rcu_dereference(keyring->payload.subscriptions); 397 if (!keylist) 398 goto not_this_keyring; 399 400 /* iterate through the keys in this keyring first */ 401 nkeys = keylist->nkeys; 402 smp_rmb(); 403 for (kix = 0; kix < nkeys; kix++) { 404 key = rcu_dereference(keylist->keys[kix]); 405 kflags = key->flags; 406 407 /* ignore keys not of this type */ 408 if (key->type != type) 409 continue; 410 411 /* skip invalidated, revoked and expired keys */ 412 if (!no_state_check) { 413 if (kflags & ((1 << KEY_FLAG_INVALIDATED) | 414 (1 << KEY_FLAG_REVOKED))) 415 continue; 416 417 if (key->expiry && now.tv_sec >= key->expiry) 418 continue; 419 } 420 421 /* keys that don't match */ 422 if (!match(key, description)) 423 continue; 424 425 /* key must have search permissions */ 426 if (key_task_permission(make_key_ref(key, possessed), 427 cred, KEY_SEARCH) < 0) 428 continue; 429 430 if (no_state_check) 431 goto found; 432 433 /* we set a different error code if we pass a negative key */ 434 if (kflags & (1 << KEY_FLAG_NEGATIVE)) { 435 err = key->type_data.reject_error; 436 continue; 437 } 438 439 goto found; 440 } 441 442 /* search through the keyrings nested in this one */ 443 kix = 0; 444 ascend: 445 nkeys = keylist->nkeys; 446 smp_rmb(); 447 for (; kix < nkeys; kix++) { 448 key = rcu_dereference(keylist->keys[kix]); 449 if (key->type != &key_type_keyring) 450 continue; 451 452 /* recursively search nested keyrings 453 * - only search keyrings for which we have search permission 454 */ 455 if (sp >= KEYRING_SEARCH_MAX_DEPTH) 456 continue; 457 458 if (key_task_permission(make_key_ref(key, possessed), 459 cred, KEY_SEARCH) < 0) 460 continue; 461 462 /* stack the current position */ 463 stack[sp].keyring = keyring; 464 stack[sp].keylist = keylist; 465 stack[sp].kix = kix; 466 sp++; 467 468 /* begin again with the new keyring */ 469 keyring = key; 470 goto descend; 471 } 472 473 /* the keyring we're looking at was disqualified or didn't contain a 474 * matching key */ 475 not_this_keyring: 476 if (sp > 0) { 477 /* resume the processing of a keyring higher up in the tree */ 478 sp--; 479 keyring = stack[sp].keyring; 480 keylist = stack[sp].keylist; 481 kix = stack[sp].kix + 1; 482 goto ascend; 483 } 484 485 key_ref = ERR_PTR(err); 486 goto error_2; 487 488 /* we found a viable match */ 489 found: 490 atomic_inc(&key->usage); 491 key->last_used_at = now.tv_sec; 492 keyring->last_used_at = now.tv_sec; 493 while (sp > 0) 494 stack[--sp].keyring->last_used_at = now.tv_sec; 495 key_check(key); 496 key_ref = make_key_ref(key, possessed); 497 error_2: 498 rcu_read_unlock(); 499 error: 500 return key_ref; 501 } 502 503 /** 504 * keyring_search - Search the supplied keyring tree for a matching key 505 * @keyring: The root of the keyring tree to be searched. 506 * @type: The type of keyring we want to find. 507 * @description: The name of the keyring we want to find. 508 * 509 * As keyring_search_aux() above, but using the current task's credentials and 510 * type's default matching function. 511 */ 512 key_ref_t keyring_search(key_ref_t keyring, 513 struct key_type *type, 514 const char *description) 515 { 516 if (!type->match) 517 return ERR_PTR(-ENOKEY); 518 519 return keyring_search_aux(keyring, current->cred, 520 type, description, type->match, false); 521 } 522 EXPORT_SYMBOL(keyring_search); 523 524 /* 525 * Search the given keyring only (no recursion). 526 * 527 * The caller must guarantee that the keyring is a keyring and that the 528 * permission is granted to search the keyring as no check is made here. 529 * 530 * RCU is used to make it unnecessary to lock the keyring key list here. 531 * 532 * Returns a pointer to the found key with usage count incremented if 533 * successful and returns -ENOKEY if not found. Revoked keys and keys not 534 * providing the requested permission are skipped over. 535 * 536 * If successful, the possession indicator is propagated from the keyring ref 537 * to the returned key reference. 538 */ 539 key_ref_t __keyring_search_one(key_ref_t keyring_ref, 540 const struct key_type *ktype, 541 const char *description, 542 key_perm_t perm) 543 { 544 struct keyring_list *klist; 545 unsigned long possessed; 546 struct key *keyring, *key; 547 int nkeys, loop; 548 549 keyring = key_ref_to_ptr(keyring_ref); 550 possessed = is_key_possessed(keyring_ref); 551 552 rcu_read_lock(); 553 554 klist = rcu_dereference(keyring->payload.subscriptions); 555 if (klist) { 556 nkeys = klist->nkeys; 557 smp_rmb(); 558 for (loop = 0; loop < nkeys ; loop++) { 559 key = rcu_dereference(klist->keys[loop]); 560 if (key->type == ktype && 561 (!key->type->match || 562 key->type->match(key, description)) && 563 key_permission(make_key_ref(key, possessed), 564 perm) == 0 && 565 !(key->flags & ((1 << KEY_FLAG_INVALIDATED) | 566 (1 << KEY_FLAG_REVOKED))) 567 ) 568 goto found; 569 } 570 } 571 572 rcu_read_unlock(); 573 return ERR_PTR(-ENOKEY); 574 575 found: 576 atomic_inc(&key->usage); 577 keyring->last_used_at = key->last_used_at = 578 current_kernel_time().tv_sec; 579 rcu_read_unlock(); 580 return make_key_ref(key, possessed); 581 } 582 583 /* 584 * Find a keyring with the specified name. 585 * 586 * All named keyrings in the current user namespace are searched, provided they 587 * grant Search permission directly to the caller (unless this check is 588 * skipped). Keyrings whose usage points have reached zero or who have been 589 * revoked are skipped. 590 * 591 * Returns a pointer to the keyring with the keyring's refcount having being 592 * incremented on success. -ENOKEY is returned if a key could not be found. 593 */ 594 struct key *find_keyring_by_name(const char *name, bool skip_perm_check) 595 { 596 struct key *keyring; 597 int bucket; 598 599 if (!name) 600 return ERR_PTR(-EINVAL); 601 602 bucket = keyring_hash(name); 603 604 read_lock(&keyring_name_lock); 605 606 if (keyring_name_hash[bucket].next) { 607 /* search this hash bucket for a keyring with a matching name 608 * that's readable and that hasn't been revoked */ 609 list_for_each_entry(keyring, 610 &keyring_name_hash[bucket], 611 type_data.link 612 ) { 613 if (!kuid_has_mapping(current_user_ns(), keyring->user->uid)) 614 continue; 615 616 if (test_bit(KEY_FLAG_REVOKED, &keyring->flags)) 617 continue; 618 619 if (strcmp(keyring->description, name) != 0) 620 continue; 621 622 if (!skip_perm_check && 623 key_permission(make_key_ref(keyring, 0), 624 KEY_SEARCH) < 0) 625 continue; 626 627 /* we've got a match but we might end up racing with 628 * key_cleanup() if the keyring is currently 'dead' 629 * (ie. it has a zero usage count) */ 630 if (!atomic_inc_not_zero(&keyring->usage)) 631 continue; 632 keyring->last_used_at = current_kernel_time().tv_sec; 633 goto out; 634 } 635 } 636 637 keyring = ERR_PTR(-ENOKEY); 638 out: 639 read_unlock(&keyring_name_lock); 640 return keyring; 641 } 642 643 /* 644 * See if a cycle will will be created by inserting acyclic tree B in acyclic 645 * tree A at the topmost level (ie: as a direct child of A). 646 * 647 * Since we are adding B to A at the top level, checking for cycles should just 648 * be a matter of seeing if node A is somewhere in tree B. 649 */ 650 static int keyring_detect_cycle(struct key *A, struct key *B) 651 { 652 struct { 653 struct keyring_list *keylist; 654 int kix; 655 } stack[KEYRING_SEARCH_MAX_DEPTH]; 656 657 struct keyring_list *keylist; 658 struct key *subtree, *key; 659 int sp, nkeys, kix, ret; 660 661 rcu_read_lock(); 662 663 ret = -EDEADLK; 664 if (A == B) 665 goto cycle_detected; 666 667 subtree = B; 668 sp = 0; 669 670 /* start processing a new keyring */ 671 descend: 672 if (test_bit(KEY_FLAG_REVOKED, &subtree->flags)) 673 goto not_this_keyring; 674 675 keylist = rcu_dereference(subtree->payload.subscriptions); 676 if (!keylist) 677 goto not_this_keyring; 678 kix = 0; 679 680 ascend: 681 /* iterate through the remaining keys in this keyring */ 682 nkeys = keylist->nkeys; 683 smp_rmb(); 684 for (; kix < nkeys; kix++) { 685 key = rcu_dereference(keylist->keys[kix]); 686 687 if (key == A) 688 goto cycle_detected; 689 690 /* recursively check nested keyrings */ 691 if (key->type == &key_type_keyring) { 692 if (sp >= KEYRING_SEARCH_MAX_DEPTH) 693 goto too_deep; 694 695 /* stack the current position */ 696 stack[sp].keylist = keylist; 697 stack[sp].kix = kix; 698 sp++; 699 700 /* begin again with the new keyring */ 701 subtree = key; 702 goto descend; 703 } 704 } 705 706 /* the keyring we're looking at was disqualified or didn't contain a 707 * matching key */ 708 not_this_keyring: 709 if (sp > 0) { 710 /* resume the checking of a keyring higher up in the tree */ 711 sp--; 712 keylist = stack[sp].keylist; 713 kix = stack[sp].kix + 1; 714 goto ascend; 715 } 716 717 ret = 0; /* no cycles detected */ 718 719 error: 720 rcu_read_unlock(); 721 return ret; 722 723 too_deep: 724 ret = -ELOOP; 725 goto error; 726 727 cycle_detected: 728 ret = -EDEADLK; 729 goto error; 730 } 731 732 /* 733 * Dispose of a keyring list after the RCU grace period, freeing the unlinked 734 * key 735 */ 736 static void keyring_unlink_rcu_disposal(struct rcu_head *rcu) 737 { 738 struct keyring_list *klist = 739 container_of(rcu, struct keyring_list, rcu); 740 741 if (klist->delkey != USHRT_MAX) 742 key_put(rcu_access_pointer(klist->keys[klist->delkey])); 743 kfree(klist); 744 } 745 746 /* 747 * Preallocate memory so that a key can be linked into to a keyring. 748 */ 749 int __key_link_begin(struct key *keyring, const struct key_type *type, 750 const char *description, unsigned long *_prealloc) 751 __acquires(&keyring->sem) 752 __acquires(&keyring_serialise_link_sem) 753 { 754 struct keyring_list *klist, *nklist; 755 unsigned long prealloc; 756 unsigned max; 757 time_t lowest_lru; 758 size_t size; 759 int loop, lru, ret; 760 761 kenter("%d,%s,%s,", key_serial(keyring), type->name, description); 762 763 if (keyring->type != &key_type_keyring) 764 return -ENOTDIR; 765 766 down_write(&keyring->sem); 767 768 ret = -EKEYREVOKED; 769 if (test_bit(KEY_FLAG_REVOKED, &keyring->flags)) 770 goto error_krsem; 771 772 /* serialise link/link calls to prevent parallel calls causing a cycle 773 * when linking two keyring in opposite orders */ 774 if (type == &key_type_keyring) 775 down_write(&keyring_serialise_link_sem); 776 777 klist = rcu_dereference_locked_keyring(keyring); 778 779 /* see if there's a matching key we can displace */ 780 lru = -1; 781 if (klist && klist->nkeys > 0) { 782 lowest_lru = TIME_T_MAX; 783 for (loop = klist->nkeys - 1; loop >= 0; loop--) { 784 struct key *key = rcu_deref_link_locked(klist, loop, 785 keyring); 786 if (key->type == type && 787 strcmp(key->description, description) == 0) { 788 /* Found a match - we'll replace the link with 789 * one to the new key. We record the slot 790 * position. 791 */ 792 klist->delkey = loop; 793 prealloc = 0; 794 goto done; 795 } 796 if (key->last_used_at < lowest_lru) { 797 lowest_lru = key->last_used_at; 798 lru = loop; 799 } 800 } 801 } 802 803 /* If the keyring is full then do an LRU discard */ 804 if (klist && 805 klist->nkeys == klist->maxkeys && 806 klist->maxkeys >= MAX_KEYRING_LINKS) { 807 kdebug("LRU discard %d\n", lru); 808 klist->delkey = lru; 809 prealloc = 0; 810 goto done; 811 } 812 813 /* check that we aren't going to overrun the user's quota */ 814 ret = key_payload_reserve(keyring, 815 keyring->datalen + KEYQUOTA_LINK_BYTES); 816 if (ret < 0) 817 goto error_sem; 818 819 if (klist && klist->nkeys < klist->maxkeys) { 820 /* there's sufficient slack space to append directly */ 821 klist->delkey = klist->nkeys; 822 prealloc = KEY_LINK_FIXQUOTA; 823 } else { 824 /* grow the key list */ 825 max = 4; 826 if (klist) { 827 max += klist->maxkeys; 828 if (max > MAX_KEYRING_LINKS) 829 max = MAX_KEYRING_LINKS; 830 BUG_ON(max <= klist->maxkeys); 831 } 832 833 size = sizeof(*klist) + sizeof(struct key *) * max; 834 835 ret = -ENOMEM; 836 nklist = kmalloc(size, GFP_KERNEL); 837 if (!nklist) 838 goto error_quota; 839 840 nklist->maxkeys = max; 841 if (klist) { 842 memcpy(nklist->keys, klist->keys, 843 sizeof(struct key *) * klist->nkeys); 844 nklist->delkey = klist->nkeys; 845 nklist->nkeys = klist->nkeys + 1; 846 klist->delkey = USHRT_MAX; 847 } else { 848 nklist->nkeys = 1; 849 nklist->delkey = 0; 850 } 851 852 /* add the key into the new space */ 853 RCU_INIT_POINTER(nklist->keys[nklist->delkey], NULL); 854 prealloc = (unsigned long)nklist | KEY_LINK_FIXQUOTA; 855 } 856 857 done: 858 *_prealloc = prealloc; 859 kleave(" = 0"); 860 return 0; 861 862 error_quota: 863 /* undo the quota changes */ 864 key_payload_reserve(keyring, 865 keyring->datalen - KEYQUOTA_LINK_BYTES); 866 error_sem: 867 if (type == &key_type_keyring) 868 up_write(&keyring_serialise_link_sem); 869 error_krsem: 870 up_write(&keyring->sem); 871 kleave(" = %d", ret); 872 return ret; 873 } 874 875 /* 876 * Check already instantiated keys aren't going to be a problem. 877 * 878 * The caller must have called __key_link_begin(). Don't need to call this for 879 * keys that were created since __key_link_begin() was called. 880 */ 881 int __key_link_check_live_key(struct key *keyring, struct key *key) 882 { 883 if (key->type == &key_type_keyring) 884 /* check that we aren't going to create a cycle by linking one 885 * keyring to another */ 886 return keyring_detect_cycle(keyring, key); 887 return 0; 888 } 889 890 /* 891 * Link a key into to a keyring. 892 * 893 * Must be called with __key_link_begin() having being called. Discards any 894 * already extant link to matching key if there is one, so that each keyring 895 * holds at most one link to any given key of a particular type+description 896 * combination. 897 */ 898 void __key_link(struct key *keyring, struct key *key, 899 unsigned long *_prealloc) 900 { 901 struct keyring_list *klist, *nklist; 902 struct key *discard; 903 904 nklist = (struct keyring_list *)(*_prealloc & ~KEY_LINK_FIXQUOTA); 905 *_prealloc = 0; 906 907 kenter("%d,%d,%p", keyring->serial, key->serial, nklist); 908 909 klist = rcu_dereference_locked_keyring(keyring); 910 911 atomic_inc(&key->usage); 912 keyring->last_used_at = key->last_used_at = 913 current_kernel_time().tv_sec; 914 915 /* there's a matching key we can displace or an empty slot in a newly 916 * allocated list we can fill */ 917 if (nklist) { 918 kdebug("reissue %hu/%hu/%hu", 919 nklist->delkey, nklist->nkeys, nklist->maxkeys); 920 921 RCU_INIT_POINTER(nklist->keys[nklist->delkey], key); 922 923 rcu_assign_pointer(keyring->payload.subscriptions, nklist); 924 925 /* dispose of the old keyring list and, if there was one, the 926 * displaced key */ 927 if (klist) { 928 kdebug("dispose %hu/%hu/%hu", 929 klist->delkey, klist->nkeys, klist->maxkeys); 930 call_rcu(&klist->rcu, keyring_unlink_rcu_disposal); 931 } 932 } else if (klist->delkey < klist->nkeys) { 933 kdebug("replace %hu/%hu/%hu", 934 klist->delkey, klist->nkeys, klist->maxkeys); 935 936 discard = rcu_dereference_protected( 937 klist->keys[klist->delkey], 938 rwsem_is_locked(&keyring->sem)); 939 rcu_assign_pointer(klist->keys[klist->delkey], key); 940 /* The garbage collector will take care of RCU 941 * synchronisation */ 942 key_put(discard); 943 } else { 944 /* there's sufficient slack space to append directly */ 945 kdebug("append %hu/%hu/%hu", 946 klist->delkey, klist->nkeys, klist->maxkeys); 947 948 RCU_INIT_POINTER(klist->keys[klist->delkey], key); 949 smp_wmb(); 950 klist->nkeys++; 951 } 952 } 953 954 /* 955 * Finish linking a key into to a keyring. 956 * 957 * Must be called with __key_link_begin() having being called. 958 */ 959 void __key_link_end(struct key *keyring, struct key_type *type, 960 unsigned long prealloc) 961 __releases(&keyring->sem) 962 __releases(&keyring_serialise_link_sem) 963 { 964 BUG_ON(type == NULL); 965 BUG_ON(type->name == NULL); 966 kenter("%d,%s,%lx", keyring->serial, type->name, prealloc); 967 968 if (type == &key_type_keyring) 969 up_write(&keyring_serialise_link_sem); 970 971 if (prealloc) { 972 if (prealloc & KEY_LINK_FIXQUOTA) 973 key_payload_reserve(keyring, 974 keyring->datalen - 975 KEYQUOTA_LINK_BYTES); 976 kfree((struct keyring_list *)(prealloc & ~KEY_LINK_FIXQUOTA)); 977 } 978 up_write(&keyring->sem); 979 } 980 981 /** 982 * key_link - Link a key to a keyring 983 * @keyring: The keyring to make the link in. 984 * @key: The key to link to. 985 * 986 * Make a link in a keyring to a key, such that the keyring holds a reference 987 * on that key and the key can potentially be found by searching that keyring. 988 * 989 * This function will write-lock the keyring's semaphore and will consume some 990 * of the user's key data quota to hold the link. 991 * 992 * Returns 0 if successful, -ENOTDIR if the keyring isn't a keyring, 993 * -EKEYREVOKED if the keyring has been revoked, -ENFILE if the keyring is 994 * full, -EDQUOT if there is insufficient key data quota remaining to add 995 * another link or -ENOMEM if there's insufficient memory. 996 * 997 * It is assumed that the caller has checked that it is permitted for a link to 998 * be made (the keyring should have Write permission and the key Link 999 * permission). 1000 */ 1001 int key_link(struct key *keyring, struct key *key) 1002 { 1003 unsigned long prealloc; 1004 int ret; 1005 1006 key_check(keyring); 1007 key_check(key); 1008 1009 ret = __key_link_begin(keyring, key->type, key->description, &prealloc); 1010 if (ret == 0) { 1011 ret = __key_link_check_live_key(keyring, key); 1012 if (ret == 0) 1013 __key_link(keyring, key, &prealloc); 1014 __key_link_end(keyring, key->type, prealloc); 1015 } 1016 1017 return ret; 1018 } 1019 EXPORT_SYMBOL(key_link); 1020 1021 /** 1022 * key_unlink - Unlink the first link to a key from a keyring. 1023 * @keyring: The keyring to remove the link from. 1024 * @key: The key the link is to. 1025 * 1026 * Remove a link from a keyring to a key. 1027 * 1028 * This function will write-lock the keyring's semaphore. 1029 * 1030 * Returns 0 if successful, -ENOTDIR if the keyring isn't a keyring, -ENOENT if 1031 * the key isn't linked to by the keyring or -ENOMEM if there's insufficient 1032 * memory. 1033 * 1034 * It is assumed that the caller has checked that it is permitted for a link to 1035 * be removed (the keyring should have Write permission; no permissions are 1036 * required on the key). 1037 */ 1038 int key_unlink(struct key *keyring, struct key *key) 1039 { 1040 struct keyring_list *klist, *nklist; 1041 int loop, ret; 1042 1043 key_check(keyring); 1044 key_check(key); 1045 1046 ret = -ENOTDIR; 1047 if (keyring->type != &key_type_keyring) 1048 goto error; 1049 1050 down_write(&keyring->sem); 1051 1052 klist = rcu_dereference_locked_keyring(keyring); 1053 if (klist) { 1054 /* search the keyring for the key */ 1055 for (loop = 0; loop < klist->nkeys; loop++) 1056 if (rcu_access_pointer(klist->keys[loop]) == key) 1057 goto key_is_present; 1058 } 1059 1060 up_write(&keyring->sem); 1061 ret = -ENOENT; 1062 goto error; 1063 1064 key_is_present: 1065 /* we need to copy the key list for RCU purposes */ 1066 nklist = kmalloc(sizeof(*klist) + 1067 sizeof(struct key *) * klist->maxkeys, 1068 GFP_KERNEL); 1069 if (!nklist) 1070 goto nomem; 1071 nklist->maxkeys = klist->maxkeys; 1072 nklist->nkeys = klist->nkeys - 1; 1073 1074 if (loop > 0) 1075 memcpy(&nklist->keys[0], 1076 &klist->keys[0], 1077 loop * sizeof(struct key *)); 1078 1079 if (loop < nklist->nkeys) 1080 memcpy(&nklist->keys[loop], 1081 &klist->keys[loop + 1], 1082 (nklist->nkeys - loop) * sizeof(struct key *)); 1083 1084 /* adjust the user's quota */ 1085 key_payload_reserve(keyring, 1086 keyring->datalen - KEYQUOTA_LINK_BYTES); 1087 1088 rcu_assign_pointer(keyring->payload.subscriptions, nklist); 1089 1090 up_write(&keyring->sem); 1091 1092 /* schedule for later cleanup */ 1093 klist->delkey = loop; 1094 call_rcu(&klist->rcu, keyring_unlink_rcu_disposal); 1095 1096 ret = 0; 1097 1098 error: 1099 return ret; 1100 nomem: 1101 ret = -ENOMEM; 1102 up_write(&keyring->sem); 1103 goto error; 1104 } 1105 EXPORT_SYMBOL(key_unlink); 1106 1107 /* 1108 * Dispose of a keyring list after the RCU grace period, releasing the keys it 1109 * links to. 1110 */ 1111 static void keyring_clear_rcu_disposal(struct rcu_head *rcu) 1112 { 1113 struct keyring_list *klist; 1114 int loop; 1115 1116 klist = container_of(rcu, struct keyring_list, rcu); 1117 1118 for (loop = klist->nkeys - 1; loop >= 0; loop--) 1119 key_put(rcu_access_pointer(klist->keys[loop])); 1120 1121 kfree(klist); 1122 } 1123 1124 /** 1125 * keyring_clear - Clear a keyring 1126 * @keyring: The keyring to clear. 1127 * 1128 * Clear the contents of the specified keyring. 1129 * 1130 * Returns 0 if successful or -ENOTDIR if the keyring isn't a keyring. 1131 */ 1132 int keyring_clear(struct key *keyring) 1133 { 1134 struct keyring_list *klist; 1135 int ret; 1136 1137 ret = -ENOTDIR; 1138 if (keyring->type == &key_type_keyring) { 1139 /* detach the pointer block with the locks held */ 1140 down_write(&keyring->sem); 1141 1142 klist = rcu_dereference_locked_keyring(keyring); 1143 if (klist) { 1144 /* adjust the quota */ 1145 key_payload_reserve(keyring, 1146 sizeof(struct keyring_list)); 1147 1148 rcu_assign_pointer(keyring->payload.subscriptions, 1149 NULL); 1150 } 1151 1152 up_write(&keyring->sem); 1153 1154 /* free the keys after the locks have been dropped */ 1155 if (klist) 1156 call_rcu(&klist->rcu, keyring_clear_rcu_disposal); 1157 1158 ret = 0; 1159 } 1160 1161 return ret; 1162 } 1163 EXPORT_SYMBOL(keyring_clear); 1164 1165 /* 1166 * Dispose of the links from a revoked keyring. 1167 * 1168 * This is called with the key sem write-locked. 1169 */ 1170 static void keyring_revoke(struct key *keyring) 1171 { 1172 struct keyring_list *klist; 1173 1174 klist = rcu_dereference_locked_keyring(keyring); 1175 1176 /* adjust the quota */ 1177 key_payload_reserve(keyring, 0); 1178 1179 if (klist) { 1180 rcu_assign_pointer(keyring->payload.subscriptions, NULL); 1181 call_rcu(&klist->rcu, keyring_clear_rcu_disposal); 1182 } 1183 } 1184 1185 /* 1186 * Collect garbage from the contents of a keyring, replacing the old list with 1187 * a new one with the pointers all shuffled down. 1188 * 1189 * Dead keys are classed as oned that are flagged as being dead or are revoked, 1190 * expired or negative keys that were revoked or expired before the specified 1191 * limit. 1192 */ 1193 void keyring_gc(struct key *keyring, time_t limit) 1194 { 1195 struct keyring_list *klist, *new; 1196 struct key *key; 1197 int loop, keep, max; 1198 1199 kenter("{%x,%s}", key_serial(keyring), keyring->description); 1200 1201 down_write(&keyring->sem); 1202 1203 klist = rcu_dereference_locked_keyring(keyring); 1204 if (!klist) 1205 goto no_klist; 1206 1207 /* work out how many subscriptions we're keeping */ 1208 keep = 0; 1209 for (loop = klist->nkeys - 1; loop >= 0; loop--) 1210 if (!key_is_dead(rcu_deref_link_locked(klist, loop, keyring), 1211 limit)) 1212 keep++; 1213 1214 if (keep == klist->nkeys) 1215 goto just_return; 1216 1217 /* allocate a new keyring payload */ 1218 max = roundup(keep, 4); 1219 new = kmalloc(sizeof(struct keyring_list) + max * sizeof(struct key *), 1220 GFP_KERNEL); 1221 if (!new) 1222 goto nomem; 1223 new->maxkeys = max; 1224 new->nkeys = 0; 1225 new->delkey = 0; 1226 1227 /* install the live keys 1228 * - must take care as expired keys may be updated back to life 1229 */ 1230 keep = 0; 1231 for (loop = klist->nkeys - 1; loop >= 0; loop--) { 1232 key = rcu_deref_link_locked(klist, loop, keyring); 1233 if (!key_is_dead(key, limit)) { 1234 if (keep >= max) 1235 goto discard_new; 1236 RCU_INIT_POINTER(new->keys[keep++], key_get(key)); 1237 } 1238 } 1239 new->nkeys = keep; 1240 1241 /* adjust the quota */ 1242 key_payload_reserve(keyring, 1243 sizeof(struct keyring_list) + 1244 KEYQUOTA_LINK_BYTES * keep); 1245 1246 if (keep == 0) { 1247 rcu_assign_pointer(keyring->payload.subscriptions, NULL); 1248 kfree(new); 1249 } else { 1250 rcu_assign_pointer(keyring->payload.subscriptions, new); 1251 } 1252 1253 up_write(&keyring->sem); 1254 1255 call_rcu(&klist->rcu, keyring_clear_rcu_disposal); 1256 kleave(" [yes]"); 1257 return; 1258 1259 discard_new: 1260 new->nkeys = keep; 1261 keyring_clear_rcu_disposal(&new->rcu); 1262 up_write(&keyring->sem); 1263 kleave(" [discard]"); 1264 return; 1265 1266 just_return: 1267 up_write(&keyring->sem); 1268 kleave(" [no dead]"); 1269 return; 1270 1271 no_klist: 1272 up_write(&keyring->sem); 1273 kleave(" [no_klist]"); 1274 return; 1275 1276 nomem: 1277 up_write(&keyring->sem); 1278 kleave(" [oom]"); 1279 } 1280