security/keys/keyring.c

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