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