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