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         if (!match)
 340                 return ERR_PTR(-ENOKEY);
 341
 342         rcu_read_lock();
 343
 344         now = current_kernel_time();
 345         err = -EAGAIN;
 346         sp = 0;
 347
 348         /* firstly we should check to see if this top-level keyring is what we
 349          * are looking for */
 350         key_ref = ERR_PTR(-EAGAIN);
 351         kflags = keyring->flags;
 352         if (keyring->type == type && match(keyring, description)) {
 353                 key = keyring;
 354                 if (no_state_check)
 355                         goto found;
 356
 357                 /* check it isn't negative and hasn't expired or been
 358                  * revoked */
 359                 if (kflags & (1 << KEY_FLAG_REVOKED))
 360                         goto error_2;
 361                 if (key->expiry && now.tv_sec >= key->expiry)
 362                         goto error_2;
 363                 key_ref = ERR_PTR(key->type_data.reject_error);
 364                 if (kflags & (1 << KEY_FLAG_NEGATIVE))
 365                         goto error_2;
 366                 goto found;
 367         }
 368
 369         /* otherwise, the top keyring must not be revoked, expired, or
 370          * negatively instantiated if we are to search it */
 371         key_ref = ERR_PTR(-EAGAIN);
 372         if (kflags & ((1 << KEY_FLAG_REVOKED) | (1 << KEY_FLAG_NEGATIVE)) ||
 373             (keyring->expiry && now.tv_sec >= keyring->expiry))
 374                 goto error_2;
 375
 376         /* start processing a new keyring */
 377 descend:
 378         if (test_bit(KEY_FLAG_REVOKED, &keyring->flags))
 379                 goto not_this_keyring;
 380
 381         keylist = rcu_dereference(keyring->payload.subscriptions);
 382         if (!keylist)
 383                 goto not_this_keyring;
 384
 385         /* iterate through the keys in this keyring first */
 386         for (kix = 0; kix < keylist->nkeys; kix++) {
 387                 key = keylist->keys[kix];
 388                 kflags = key->flags;
 389
 390                 /* ignore keys not of this type */
 391                 if (key->type != type)
 392                         continue;
 393
 394                 /* skip revoked keys and expired keys */
 395                 if (!no_state_check) {
 396                         if (kflags & (1 << KEY_FLAG_REVOKED))
 397                                 continue;
 398
 399                         if (key->expiry && now.tv_sec >= key->expiry)
 400                                 continue;
 401                 }
 402
 403                 /* keys that don't match */
 404                 if (!match(key, description))
 405                         continue;
 406
 407                 /* key must have search permissions */
 408                 if (key_task_permission(make_key_ref(key, possessed),
 409                                         cred, KEY_SEARCH) < 0)
 410                         continue;
 411
 412                 if (no_state_check)
 413                         goto found;
 414
 415                 /* we set a different error code if we pass a negative key */
 416                 if (kflags & (1 << KEY_FLAG_NEGATIVE)) {
 417                         err = key->type_data.reject_error;
 418                         continue;
 419                 }
 420
 421                 goto found;
 422         }
 423
 424         /* search through the keyrings nested in this one */
 425         kix = 0;
 426 ascend:
 427         for (; kix < keylist->nkeys; kix++) {
 428                 key = keylist->keys[kix];
 429                 if (key->type != &key_type_keyring)
 430                         continue;
 431
 432                 /* recursively search nested keyrings
 433                  * - only search keyrings for which we have search permission
 434                  */
 435                 if (sp >= KEYRING_SEARCH_MAX_DEPTH)
 436                         continue;
 437
 438                 if (key_task_permission(make_key_ref(key, possessed),
 439                                         cred, KEY_SEARCH) < 0)
 440                         continue;
 441
 442                 /* stack the current position */
 443                 stack[sp].keylist = keylist;
 444                 stack[sp].kix = kix;
 445                 sp++;
 446
 447                 /* begin again with the new keyring */
 448                 keyring = key;
 449                 goto descend;
 450         }
 451
 452         /* the keyring we're looking at was disqualified or didn't contain a
 453          * matching key */
 454 not_this_keyring:
 455         if (sp > 0) {
 456                 /* resume the processing of a keyring higher up in the tree */
 457                 sp--;
 458                 keylist = stack[sp].keylist;
 459                 kix = stack[sp].kix + 1;
 460                 goto ascend;
 461         }
 462
 463         key_ref = ERR_PTR(err);
 464         goto error_2;
 465
 466         /* we found a viable match */
 467 found:
 468         atomic_inc(&key->usage);
 469         key_check(key);
 470         key_ref = make_key_ref(key, possessed);
 471 error_2:
 472         rcu_read_unlock();
 473 error:
 474         return key_ref;
 475 }
 476
 477 /**
 478  * keyring_search - Search the supplied keyring tree for a matching key
 479  * @keyring: The root of the keyring tree to be searched.
 480  * @type: The type of keyring we want to find.
 481  * @description: The name of the keyring we want to find.
 482  *
 483  * As keyring_search_aux() above, but using the current task's credentials and
 484  * type's default matching function.
 485  */
 486 key_ref_t keyring_search(key_ref_t keyring,
 487                          struct key_type *type,
 488                          const char *description)
 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  * Only keyrings that have nonzero refcount, are not revoked, and are owned by a
 554  * user in the current user namespace are considered.  If @uid_keyring is %true,
 555  * the keyring additionally must have been allocated as a user or user session
 556  * keyring; otherwise, it must grant Search permission directly to the caller.
 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 uid_keyring)
 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 (uid_keyring) {
 590                                 if (!test_bit(KEY_FLAG_UID_KEYRING,
 591                                               &keyring->flags))
 592                                         continue;
 593                         } else {
 594                                 if (key_permission(make_key_ref(keyring, 0),
 595                                                    KEY_SEARCH) < 0)
 596                                         continue;
 597                         }
 598
 599                         /* we've got a match but we might end up racing with
 600                          * key_cleanup() if the keyring is currently 'dead'
 601                          * (ie. it has a zero usage count) */
 602                         if (!atomic_inc_not_zero(&keyring->usage))
 603                                 continue;
 604                         goto out;
 605                 }
 606         }
 607
 608         keyring = ERR_PTR(-ENOKEY);
 609 out:
 610         read_unlock(&keyring_name_lock);
 611         return keyring;
 612 }
 613
 614 /*
 615  * See if a cycle will will be created by inserting acyclic tree B in acyclic
 616  * tree A at the topmost level (ie: as a direct child of A).
 617  *
 618  * Since we are adding B to A at the top level, checking for cycles should just
 619  * be a matter of seeing if node A is somewhere in tree B.
 620  */
 621 static int keyring_detect_cycle(struct key *A, struct key *B)
 622 {
 623         struct {
 624                 struct keyring_list *keylist;
 625                 int kix;
 626         } stack[KEYRING_SEARCH_MAX_DEPTH];
 627
 628         struct keyring_list *keylist;
 629         struct key *subtree, *key;
 630         int sp, kix, ret;
 631
 632         rcu_read_lock();
 633
 634         ret = -EDEADLK;
 635         if (A == B)
 636                 goto cycle_detected;
 637
 638         subtree = B;
 639         sp = 0;
 640
 641         /* start processing a new keyring */
 642 descend:
 643         if (test_bit(KEY_FLAG_REVOKED, &subtree->flags))
 644                 goto not_this_keyring;
 645
 646         keylist = rcu_dereference(subtree->payload.subscriptions);
 647         if (!keylist)
 648                 goto not_this_keyring;
 649         kix = 0;
 650
 651 ascend:
 652         /* iterate through the remaining keys in this keyring */
 653         for (; kix < keylist->nkeys; kix++) {
 654                 key = keylist->keys[kix];
 655
 656                 if (key == A)
 657                         goto cycle_detected;
 658
 659                 /* recursively check nested keyrings */
 660                 if (key->type == &key_type_keyring) {
 661                         if (sp >= KEYRING_SEARCH_MAX_DEPTH)
 662                                 goto too_deep;
 663
 664                         /* stack the current position */
 665                         stack[sp].keylist = keylist;
 666                         stack[sp].kix = kix;
 667                         sp++;
 668
 669                         /* begin again with the new keyring */
 670                         subtree = key;
 671                         goto descend;
 672                 }
 673         }
 674
 675         /* the keyring we're looking at was disqualified or didn't contain a
 676          * matching key */
 677 not_this_keyring:
 678         if (sp > 0) {
 679                 /* resume the checking of a keyring higher up in the tree */
 680                 sp--;
 681                 keylist = stack[sp].keylist;
 682                 kix = stack[sp].kix + 1;
 683                 goto ascend;
 684         }
 685
 686         ret = 0; /* no cycles detected */
 687
 688 error:
 689         rcu_read_unlock();
 690         return ret;
 691
 692 too_deep:
 693         ret = -ELOOP;
 694         goto error;
 695
 696 cycle_detected:
 697         ret = -EDEADLK;
 698         goto error;
 699 }
 700
 701 /*
 702  * Dispose of a keyring list after the RCU grace period, freeing the unlinked
 703  * key
 704  */
 705 static void keyring_unlink_rcu_disposal(struct rcu_head *rcu)
 706 {
 707         struct keyring_list *klist =
 708                 container_of(rcu, struct keyring_list, rcu);
 709
 710         if (klist->delkey != USHRT_MAX)
 711                 key_put(klist->keys[klist->delkey]);
 712         kfree(klist);
 713 }
 714
 715 /*
 716  * Preallocate memory so that a key can be linked into to a keyring.
 717  */
 718 int __key_link_begin(struct key *keyring, const struct key_type *type,
 719                      const char *description, unsigned long *_prealloc)
 720         __acquires(&keyring->sem)
 721 {
 722         struct keyring_list *klist, *nklist;
 723         unsigned long prealloc;
 724         unsigned max;
 725         size_t size;
 726         int loop, ret;
 727
 728         kenter("%d,%s,%s,", key_serial(keyring), type->name, description);
 729
 730         if (keyring->type != &key_type_keyring)
 731                 return -ENOTDIR;
 732
 733         down_write(&keyring->sem);
 734
 735         ret = -EKEYREVOKED;
 736         if (test_bit(KEY_FLAG_REVOKED, &keyring->flags))
 737                 goto error_krsem;
 738
 739         /* serialise link/link calls to prevent parallel calls causing a cycle
 740          * when linking two keyring in opposite orders */
 741         if (type == &key_type_keyring)
 742                 down_write(&keyring_serialise_link_sem);
 743
 744         klist = rcu_dereference_locked_keyring(keyring);
 745
 746         /* see if there's a matching key we can displace */
 747         if (klist && klist->nkeys > 0) {
 748                 for (loop = klist->nkeys - 1; loop >= 0; loop--) {
 749                         if (klist->keys[loop]->type == type &&
 750                             strcmp(klist->keys[loop]->description,
 751                                    description) == 0
 752                             ) {
 753                                 /* found a match - we'll replace this one with
 754                                  * the new key */
 755                                 size = sizeof(struct key *) * klist->maxkeys;
 756                                 size += sizeof(*klist);
 757                                 BUG_ON(size > PAGE_SIZE);
 758
 759                                 ret = -ENOMEM;
 760                                 nklist = kmemdup(klist, size, GFP_KERNEL);
 761                                 if (!nklist)
 762                                         goto error_sem;
 763
 764                                 /* note replacement slot */
 765                                 klist->delkey = nklist->delkey = loop;
 766                                 prealloc = (unsigned long)nklist;
 767                                 goto done;
 768                         }
 769                 }
 770         }
 771
 772         /* check that we aren't going to overrun the user's quota */
 773         ret = key_payload_reserve(keyring,
 774                                   keyring->datalen + KEYQUOTA_LINK_BYTES);
 775         if (ret < 0)
 776                 goto error_sem;
 777
 778         if (klist && klist->nkeys < klist->maxkeys) {
 779                 /* there's sufficient slack space to append directly */
 780                 nklist = NULL;
 781                 prealloc = KEY_LINK_FIXQUOTA;
 782         } else {
 783                 /* grow the key list */
 784                 max = 4;
 785                 if (klist)
 786                         max += klist->maxkeys;
 787
 788                 ret = -ENFILE;
 789                 if (max > USHRT_MAX - 1)
 790                         goto error_quota;
 791                 size = sizeof(*klist) + sizeof(struct key *) * max;
 792                 if (size > PAGE_SIZE)
 793                         goto error_quota;
 794
 795                 ret = -ENOMEM;
 796                 nklist = kmalloc(size, GFP_KERNEL);
 797                 if (!nklist)
 798                         goto error_quota;
 799
 800                 nklist->maxkeys = max;
 801                 if (klist) {
 802                         memcpy(nklist->keys, klist->keys,
 803                                sizeof(struct key *) * klist->nkeys);
 804                         nklist->delkey = klist->nkeys;
 805                         nklist->nkeys = klist->nkeys + 1;
 806                         klist->delkey = USHRT_MAX;
 807                 } else {
 808                         nklist->nkeys = 1;
 809                         nklist->delkey = 0;
 810                 }
 811
 812                 /* add the key into the new space */
 813                 nklist->keys[nklist->delkey] = NULL;
 814         }
 815
 816         prealloc = (unsigned long)nklist | KEY_LINK_FIXQUOTA;
 817 done:
 818         *_prealloc = prealloc;
 819         kleave(" = 0");
 820         return 0;
 821
 822 error_quota:
 823         /* undo the quota changes */
 824         key_payload_reserve(keyring,
 825                             keyring->datalen - KEYQUOTA_LINK_BYTES);
 826 error_sem:
 827         if (type == &key_type_keyring)
 828                 up_write(&keyring_serialise_link_sem);
 829 error_krsem:
 830         up_write(&keyring->sem);
 831         kleave(" = %d", ret);
 832         return ret;
 833 }
 834
 835 /*
 836  * Check already instantiated keys aren't going to be a problem.
 837  *
 838  * The caller must have called __key_link_begin(). Don't need to call this for
 839  * keys that were created since __key_link_begin() was called.
 840  */
 841 int __key_link_check_live_key(struct key *keyring, struct key *key)
 842 {
 843         if (key->type == &key_type_keyring)
 844                 /* check that we aren't going to create a cycle by linking one
 845                  * keyring to another */
 846                 return keyring_detect_cycle(keyring, key);
 847         return 0;
 848 }
 849
 850 /*
 851  * Link a key into to a keyring.
 852  *
 853  * Must be called with __key_link_begin() having being called.  Discards any
 854  * already extant link to matching key if there is one, so that each keyring
 855  * holds at most one link to any given key of a particular type+description
 856  * combination.
 857  */
 858 void __key_link(struct key *keyring, struct key *key,
 859                 unsigned long *_prealloc)
 860 {
 861         struct keyring_list *klist, *nklist;
 862
 863         nklist = (struct keyring_list *)(*_prealloc & ~KEY_LINK_FIXQUOTA);
 864         *_prealloc = 0;
 865
 866         kenter("%d,%d,%p", keyring->serial, key->serial, nklist);
 867
 868         klist = rcu_dereference_locked_keyring(keyring);
 869
 870         atomic_inc(&key->usage);
 871
 872         /* there's a matching key we can displace or an empty slot in a newly
 873          * allocated list we can fill */
 874         if (nklist) {
 875                 kdebug("replace %hu/%hu/%hu",
 876                        nklist->delkey, nklist->nkeys, nklist->maxkeys);
 877
 878                 nklist->keys[nklist->delkey] = key;
 879
 880                 rcu_assign_pointer(keyring->payload.subscriptions, nklist);
 881
 882                 /* dispose of the old keyring list and, if there was one, the
 883                  * displaced key */
 884                 if (klist) {
 885                         kdebug("dispose %hu/%hu/%hu",
 886                                klist->delkey, klist->nkeys, klist->maxkeys);
 887                         call_rcu(&klist->rcu, keyring_unlink_rcu_disposal);
 888                 }
 889         } else {
 890                 /* there's sufficient slack space to append directly */
 891                 klist->keys[klist->nkeys] = key;
 892                 smp_wmb();
 893                 klist->nkeys++;
 894         }
 895 }
 896
 897 /*
 898  * Finish linking a key into to a keyring.
 899  *
 900  * Must be called with __key_link_begin() having being called.
 901  */
 902 void __key_link_end(struct key *keyring, struct key_type *type,
 903                     unsigned long prealloc)
 904         __releases(&keyring->sem)
 905 {
 906         BUG_ON(type == NULL);
 907         BUG_ON(type->name == NULL);
 908         kenter("%d,%s,%lx", keyring->serial, type->name, prealloc);
 909
 910         if (type == &key_type_keyring)
 911                 up_write(&keyring_serialise_link_sem);
 912
 913         if (prealloc) {
 914                 if (prealloc & KEY_LINK_FIXQUOTA)
 915                         key_payload_reserve(keyring,
 916                                             keyring->datalen -
 917                                             KEYQUOTA_LINK_BYTES);
 918                 kfree((struct keyring_list *)(prealloc & ~KEY_LINK_FIXQUOTA));
 919         }
 920         up_write(&keyring->sem);
 921 }
 922
 923 /**
 924  * key_link - Link a key to a keyring
 925  * @keyring: The keyring to make the link in.
 926  * @key: The key to link to.
 927  *
 928  * Make a link in a keyring to a key, such that the keyring holds a reference
 929  * on that key and the key can potentially be found by searching that keyring.
 930  *
 931  * This function will write-lock the keyring's semaphore and will consume some
 932  * of the user's key data quota to hold the link.
 933  *
 934  * Returns 0 if successful, -ENOTDIR if the keyring isn't a keyring,
 935  * -EKEYREVOKED if the keyring has been revoked, -ENFILE if the keyring is
 936  * full, -EDQUOT if there is insufficient key data quota remaining to add
 937  * another link or -ENOMEM if there's insufficient memory.
 938  *
 939  * It is assumed that the caller has checked that it is permitted for a link to
 940  * be made (the keyring should have Write permission and the key Link
 941  * permission).
 942  */
 943 int key_link(struct key *keyring, struct key *key)
 944 {
 945         unsigned long prealloc;
 946         int ret;
 947
 948         key_check(keyring);
 949         key_check(key);
 950
 951         ret = __key_link_begin(keyring, key->type, key->description, &prealloc);
 952         if (ret == 0) {
 953                 ret = __key_link_check_live_key(keyring, key);
 954                 if (ret == 0)
 955                         __key_link(keyring, key, &prealloc);
 956                 __key_link_end(keyring, key->type, prealloc);
 957         }
 958
 959         return ret;
 960 }
 961 EXPORT_SYMBOL(key_link);
 962
 963 /**
 964  * key_unlink - Unlink the first link to a key from a keyring.
 965  * @keyring: The keyring to remove the link from.
 966  * @key: The key the link is to.
 967  *
 968  * Remove a link from a keyring to a key.
 969  *
 970  * This function will write-lock the keyring's semaphore.
 971  *
 972  * Returns 0 if successful, -ENOTDIR if the keyring isn't a keyring, -ENOENT if
 973  * the key isn't linked to by the keyring or -ENOMEM if there's insufficient
 974  * memory.
 975  *
 976  * It is assumed that the caller has checked that it is permitted for a link to
 977  * be removed (the keyring should have Write permission; no permissions are
 978  * required on the key).
 979  */
 980 int key_unlink(struct key *keyring, struct key *key)
 981 {
 982         struct keyring_list *klist, *nklist;
 983         int loop, ret;
 984
 985         key_check(keyring);
 986         key_check(key);
 987
 988         ret = -ENOTDIR;
 989         if (keyring->type != &key_type_keyring)
 990                 goto error;
 991
 992         down_write(&keyring->sem);
 993
 994         klist = rcu_dereference_locked_keyring(keyring);
 995         if (klist) {
 996                 /* search the keyring for the key */
 997                 for (loop = 0; loop < klist->nkeys; loop++)
 998                         if (klist->keys[loop] == key)
 999                                 goto key_is_present;
1000         }
1001
1002         up_write(&keyring->sem);
1003         ret = -ENOENT;
1004         goto error;
1005
1006 key_is_present:
1007         /* we need to copy the key list for RCU purposes */
1008         nklist = kmalloc(sizeof(*klist) +
1009                          sizeof(struct key *) * klist->maxkeys,
1010                          GFP_KERNEL);
1011         if (!nklist)
1012                 goto nomem;
1013         nklist->maxkeys = klist->maxkeys;
1014         nklist->nkeys = klist->nkeys - 1;
1015
1016         if (loop > 0)
1017                 memcpy(&nklist->keys[0],
1018                        &klist->keys[0],
1019                        loop * sizeof(struct key *));
1020
1021         if (loop < nklist->nkeys)
1022                 memcpy(&nklist->keys[loop],
1023                        &klist->keys[loop + 1],
1024                        (nklist->nkeys - loop) * sizeof(struct key *));
1025
1026         /* adjust the user's quota */
1027         key_payload_reserve(keyring,
1028                             keyring->datalen - KEYQUOTA_LINK_BYTES);
1029
1030         rcu_assign_pointer(keyring->payload.subscriptions, nklist);
1031
1032         up_write(&keyring->sem);
1033
1034         /* schedule for later cleanup */
1035         klist->delkey = loop;
1036         call_rcu(&klist->rcu, keyring_unlink_rcu_disposal);
1037
1038         ret = 0;
1039
1040 error:
1041         return ret;
1042 nomem:
1043         ret = -ENOMEM;
1044         up_write(&keyring->sem);
1045         goto error;
1046 }
1047 EXPORT_SYMBOL(key_unlink);
1048
1049 /*
1050  * Dispose of a keyring list after the RCU grace period, releasing the keys it
1051  * links to.
1052  */
1053 static void keyring_clear_rcu_disposal(struct rcu_head *rcu)
1054 {
1055         struct keyring_list *klist;
1056         int loop;
1057
1058         klist = container_of(rcu, struct keyring_list, rcu);
1059
1060         for (loop = klist->nkeys - 1; loop >= 0; loop--)
1061                 key_put(klist->keys[loop]);
1062
1063         kfree(klist);
1064 }
1065
1066 /**
1067  * keyring_clear - Clear a keyring
1068  * @keyring: The keyring to clear.
1069  *
1070  * Clear the contents of the specified keyring.
1071  *
1072  * Returns 0 if successful or -ENOTDIR if the keyring isn't a keyring.
1073  */
1074 int keyring_clear(struct key *keyring)
1075 {
1076         struct keyring_list *klist;
1077         int ret;
1078
1079         ret = -ENOTDIR;
1080         if (keyring->type == &key_type_keyring) {
1081                 /* detach the pointer block with the locks held */
1082                 down_write(&keyring->sem);
1083
1084                 klist = rcu_dereference_locked_keyring(keyring);
1085                 if (klist) {
1086                         /* adjust the quota */
1087                         key_payload_reserve(keyring,
1088                                             sizeof(struct keyring_list));
1089
1090                         rcu_assign_pointer(keyring->payload.subscriptions,
1091                                            NULL);
1092                 }
1093
1094                 up_write(&keyring->sem);
1095
1096                 /* free the keys after the locks have been dropped */
1097                 if (klist)
1098                         call_rcu(&klist->rcu, keyring_clear_rcu_disposal);
1099
1100                 ret = 0;
1101         }
1102
1103         return ret;
1104 }
1105 EXPORT_SYMBOL(keyring_clear);
1106
1107 /*
1108  * Dispose of the links from a revoked keyring.
1109  *
1110  * This is called with the key sem write-locked.
1111  */
1112 static void keyring_revoke(struct key *keyring)
1113 {
1114         struct keyring_list *klist;
1115
1116         klist = rcu_dereference_locked_keyring(keyring);
1117
1118         /* adjust the quota */
1119         key_payload_reserve(keyring, 0);
1120
1121         if (klist) {
1122                 rcu_assign_pointer(keyring->payload.subscriptions, NULL);
1123                 call_rcu(&klist->rcu, keyring_clear_rcu_disposal);
1124         }
1125 }
1126
1127 /*
1128  * Determine whether a key is dead.
1129  */
1130 static bool key_is_dead(struct key *key, time_t limit)
1131 {
1132         return test_bit(KEY_FLAG_DEAD, &key->flags) ||
1133                 (key->expiry > 0 && key->expiry <= limit);
1134 }
1135
1136 /*
1137  * Collect garbage from the contents of a keyring, replacing the old list with
1138  * a new one with the pointers all shuffled down.
1139  *
1140  * Dead keys are classed as oned that are flagged as being dead or are revoked,
1141  * expired or negative keys that were revoked or expired before the specified
1142  * limit.
1143  */
1144 void keyring_gc(struct key *keyring, time_t limit)
1145 {
1146         struct keyring_list *klist, *new;
1147         struct key *key;
1148         int loop, keep, max;
1149
1150         kenter("{%x,%s}", key_serial(keyring), keyring->description);
1151
1152         down_write(&keyring->sem);
1153
1154         klist = rcu_dereference_locked_keyring(keyring);
1155         if (!klist)
1156                 goto no_klist;
1157
1158         /* work out how many subscriptions we're keeping */
1159         keep = 0;
1160         for (loop = klist->nkeys - 1; loop >= 0; loop--)
1161                 if (!key_is_dead(klist->keys[loop], limit))
1162                         keep++;
1163
1164         if (keep == klist->nkeys)
1165                 goto just_return;
1166
1167         /* allocate a new keyring payload */
1168         max = roundup(keep, 4);
1169         new = kmalloc(sizeof(struct keyring_list) + max * sizeof(struct key *),
1170                       GFP_KERNEL);
1171         if (!new)
1172                 goto nomem;
1173         new->maxkeys = max;
1174         new->nkeys = 0;
1175         new->delkey = 0;
1176
1177         /* install the live keys
1178          * - must take care as expired keys may be updated back to life
1179          */
1180         keep = 0;
1181         for (loop = klist->nkeys - 1; loop >= 0; loop--) {
1182                 key = klist->keys[loop];
1183                 if (!key_is_dead(key, limit)) {
1184                         if (keep >= max)
1185                                 goto discard_new;
1186                         new->keys[keep++] = key_get(key);
1187                 }
1188         }
1189         new->nkeys = keep;
1190
1191         /* adjust the quota */
1192         key_payload_reserve(keyring,
1193                             sizeof(struct keyring_list) +
1194                             KEYQUOTA_LINK_BYTES * keep);
1195
1196         if (keep == 0) {
1197                 rcu_assign_pointer(keyring->payload.subscriptions, NULL);
1198                 kfree(new);
1199         } else {
1200                 rcu_assign_pointer(keyring->payload.subscriptions, new);
1201         }
1202
1203         up_write(&keyring->sem);
1204
1205         call_rcu(&klist->rcu, keyring_clear_rcu_disposal);
1206         kleave(" [yes]");
1207         return;
1208
1209 discard_new:
1210         new->nkeys = keep;
1211         keyring_clear_rcu_disposal(&new->rcu);
1212         up_write(&keyring->sem);
1213         kleave(" [discard]");
1214         return;
1215
1216 just_return:
1217         up_write(&keyring->sem);
1218         kleave(" [no dead]");
1219         return;
1220
1221 no_klist:
1222         up_write(&keyring->sem);
1223         kleave(" [no_klist]");
1224         return;
1225
1226 nomem:
1227         up_write(&keyring->sem);
1228         kleave(" [oom]");
1229 }