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