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  * dispose of a keyring list after the RCU grace period, freeing the unlinked
 665  * key
 666  */
 667 static void keyring_unlink_rcu_disposal(struct rcu_head *rcu)
 668 {
 669         struct keyring_list *klist =
 670                 container_of(rcu, struct keyring_list, rcu);
 671
 672         if (klist->delkey != USHRT_MAX)
 673                 key_put(klist->keys[klist->delkey]);
 674         kfree(klist);
 675 }
 676
 677 /*
 678  * preallocate memory so that a key can be linked into to a keyring
 679  */
 680 int __key_link_begin(struct key *keyring, const struct key_type *type,
 681                      const char *description,
 682                      struct keyring_list **_prealloc)
 683         __acquires(&keyring->sem)
 684 {
 685         struct keyring_list *klist, *nklist;
 686         unsigned max;
 687         size_t size;
 688         int loop, ret;
 689
 690         kenter("%d,%s,%s,", key_serial(keyring), type->name, description);
 691
 692         if (keyring->type != &key_type_keyring)
 693                 return -ENOTDIR;
 694
 695         down_write(&keyring->sem);
 696
 697         ret = -EKEYREVOKED;
 698         if (test_bit(KEY_FLAG_REVOKED, &keyring->flags))
 699                 goto error_krsem;
 700
 701         /* serialise link/link calls to prevent parallel calls causing a cycle
 702          * when linking two keyring in opposite orders */
 703         if (type == &key_type_keyring)
 704                 down_write(&keyring_serialise_link_sem);
 705
 706         klist = rcu_dereference_locked_keyring(keyring);
 707
 708         /* see if there's a matching key we can displace */
 709         if (klist && klist->nkeys > 0) {
 710                 for (loop = klist->nkeys - 1; loop >= 0; loop--) {
 711                         if (klist->keys[loop]->type == type &&
 712                             strcmp(klist->keys[loop]->description,
 713                                    description) == 0
 714                             ) {
 715                                 /* found a match - we'll replace this one with
 716                                  * the new key */
 717                                 size = sizeof(struct key *) * klist->maxkeys;
 718                                 size += sizeof(*klist);
 719                                 BUG_ON(size > PAGE_SIZE);
 720
 721                                 ret = -ENOMEM;
 722                                 nklist = kmemdup(klist, size, GFP_KERNEL);
 723                                 if (!nklist)
 724                                         goto error_sem;
 725
 726                                 /* note replacement slot */
 727                                 klist->delkey = nklist->delkey = loop;
 728                                 goto done;
 729                         }
 730                 }
 731         }
 732
 733         /* check that we aren't going to overrun the user's quota */
 734         ret = key_payload_reserve(keyring,
 735                                   keyring->datalen + KEYQUOTA_LINK_BYTES);
 736         if (ret < 0)
 737                 goto error_sem;
 738
 739         if (klist && klist->nkeys < klist->maxkeys) {
 740                 /* there's sufficient slack space to append directly */
 741                 nklist = NULL;
 742         } else {
 743                 /* grow the key list */
 744                 max = 4;
 745                 if (klist)
 746                         max += klist->maxkeys;
 747
 748                 ret = -ENFILE;
 749                 if (max > USHRT_MAX - 1)
 750                         goto error_quota;
 751                 size = sizeof(*klist) + sizeof(struct key *) * max;
 752                 if (size > PAGE_SIZE)
 753                         goto error_quota;
 754
 755                 ret = -ENOMEM;
 756                 nklist = kmalloc(size, GFP_KERNEL);
 757                 if (!nklist)
 758                         goto error_quota;
 759
 760                 nklist->maxkeys = max;
 761                 if (klist) {
 762                         memcpy(nklist->keys, klist->keys,
 763                                sizeof(struct key *) * klist->nkeys);
 764                         nklist->delkey = klist->nkeys;
 765                         nklist->nkeys = klist->nkeys + 1;
 766                         klist->delkey = USHRT_MAX;
 767                 } else {
 768                         nklist->nkeys = 1;
 769                         nklist->delkey = 0;
 770                 }
 771
 772                 /* add the key into the new space */
 773                 nklist->keys[nklist->delkey] = NULL;
 774         }
 775
 776 done:
 777         *_prealloc = nklist;
 778         kleave(" = 0");
 779         return 0;
 780
 781 error_quota:
 782         /* undo the quota changes */
 783         key_payload_reserve(keyring,
 784                             keyring->datalen - KEYQUOTA_LINK_BYTES);
 785 error_sem:
 786         if (type == &key_type_keyring)
 787                 up_write(&keyring_serialise_link_sem);
 788 error_krsem:
 789         up_write(&keyring->sem);
 790         kleave(" = %d", ret);
 791         return ret;
 792 }
 793
 794 /*
 795  * check already instantiated keys aren't going to be a problem
 796  * - the caller must have called __key_link_begin()
 797  * - don't need to call this for keys that were created since __key_link_begin()
 798  *   was called
 799  */
 800 int __key_link_check_live_key(struct key *keyring, struct key *key)
 801 {
 802         if (key->type == &key_type_keyring)
 803                 /* check that we aren't going to create a cycle by linking one
 804                  * keyring to another */
 805                 return keyring_detect_cycle(keyring, key);
 806         return 0;
 807 }
 808
 809 /*
 810  * link a key into to a keyring
 811  * - must be called with __key_link_begin() having being called
 812  * - discard already extant link to matching key if there is one
 813  */
 814 void __key_link(struct key *keyring, struct key *key,
 815                 struct keyring_list **_prealloc)
 816 {
 817         struct keyring_list *klist, *nklist;
 818
 819         nklist = *_prealloc;
 820         *_prealloc = NULL;
 821
 822         kenter("%d,%d,%p", keyring->serial, key->serial, nklist);
 823
 824         klist = rcu_dereference_protected(keyring->payload.subscriptions,
 825                                           rwsem_is_locked(&keyring->sem));
 826
 827         atomic_inc(&key->usage);
 828
 829         /* there's a matching key we can displace or an empty slot in a newly
 830          * allocated list we can fill */
 831         if (nklist) {
 832                 kdebug("replace %hu/%hu/%hu",
 833                        nklist->delkey, nklist->nkeys, nklist->maxkeys);
 834
 835                 nklist->keys[nklist->delkey] = key;
 836
 837                 rcu_assign_pointer(keyring->payload.subscriptions, nklist);
 838
 839                 /* dispose of the old keyring list and, if there was one, the
 840                  * displaced key */
 841                 if (klist) {
 842                         kdebug("dispose %hu/%hu/%hu",
 843                                klist->delkey, klist->nkeys, klist->maxkeys);
 844                         call_rcu(&klist->rcu, keyring_unlink_rcu_disposal);
 845                 }
 846         } else {
 847                 /* there's sufficient slack space to append directly */
 848                 klist->keys[klist->nkeys] = key;
 849                 smp_wmb();
 850                 klist->nkeys++;
 851         }
 852 }
 853
 854 /*
 855  * finish linking a key into to a keyring
 856  * - must be called with __key_link_begin() having being called
 857  */
 858 void __key_link_end(struct key *keyring, struct key_type *type,
 859                     struct keyring_list *prealloc)
 860         __releases(&keyring->sem)
 861 {
 862         BUG_ON(type == NULL);
 863         BUG_ON(type->name == NULL);
 864         kenter("%d,%s,%p", keyring->serial, type->name, prealloc);
 865
 866         if (type == &key_type_keyring)
 867                 up_write(&keyring_serialise_link_sem);
 868
 869         if (prealloc) {
 870                 kfree(prealloc);
 871                 key_payload_reserve(keyring,
 872                                     keyring->datalen - KEYQUOTA_LINK_BYTES);
 873         }
 874         up_write(&keyring->sem);
 875 }
 876
 877 /*
 878  * link a key to a keyring
 879  */
 880 int key_link(struct key *keyring, struct key *key)
 881 {
 882         struct keyring_list *prealloc;
 883         int ret;
 884
 885         key_check(keyring);
 886         key_check(key);
 887
 888         ret = __key_link_begin(keyring, key->type, key->description, &prealloc);
 889         if (ret == 0) {
 890                 ret = __key_link_check_live_key(keyring, key);
 891                 if (ret == 0)
 892                         __key_link(keyring, key, &prealloc);
 893                 __key_link_end(keyring, key->type, prealloc);
 894         }
 895
 896         return ret;
 897 }
 898
 899 EXPORT_SYMBOL(key_link);
 900
 901 /*****************************************************************************/
 902 /*
 903  * unlink the first link to a key from a keyring
 904  */
 905 int key_unlink(struct key *keyring, struct key *key)
 906 {
 907         struct keyring_list *klist, *nklist;
 908         int loop, ret;
 909
 910         key_check(keyring);
 911         key_check(key);
 912
 913         ret = -ENOTDIR;
 914         if (keyring->type != &key_type_keyring)
 915                 goto error;
 916
 917         down_write(&keyring->sem);
 918
 919         klist = rcu_dereference_locked_keyring(keyring);
 920         if (klist) {
 921                 /* search the keyring for the key */
 922                 for (loop = 0; loop < klist->nkeys; loop++)
 923                         if (klist->keys[loop] == key)
 924                                 goto key_is_present;
 925         }
 926
 927         up_write(&keyring->sem);
 928         ret = -ENOENT;
 929         goto error;
 930
 931 key_is_present:
 932         /* we need to copy the key list for RCU purposes */
 933         nklist = kmalloc(sizeof(*klist) +
 934                          sizeof(struct key *) * klist->maxkeys,
 935                          GFP_KERNEL);
 936         if (!nklist)
 937                 goto nomem;
 938         nklist->maxkeys = klist->maxkeys;
 939         nklist->nkeys = klist->nkeys - 1;
 940
 941         if (loop > 0)
 942                 memcpy(&nklist->keys[0],
 943                        &klist->keys[0],
 944                        loop * sizeof(struct key *));
 945
 946         if (loop < nklist->nkeys)
 947                 memcpy(&nklist->keys[loop],
 948                        &klist->keys[loop + 1],
 949                        (nklist->nkeys - loop) * sizeof(struct key *));
 950
 951         /* adjust the user's quota */
 952         key_payload_reserve(keyring,
 953                             keyring->datalen - KEYQUOTA_LINK_BYTES);
 954
 955         rcu_assign_pointer(keyring->payload.subscriptions, nklist);
 956
 957         up_write(&keyring->sem);
 958
 959         /* schedule for later cleanup */
 960         klist->delkey = loop;
 961         call_rcu(&klist->rcu, keyring_unlink_rcu_disposal);
 962
 963         ret = 0;
 964
 965 error:
 966         return ret;
 967 nomem:
 968         ret = -ENOMEM;
 969         up_write(&keyring->sem);
 970         goto error;
 971
 972 } /* end key_unlink() */
 973
 974 EXPORT_SYMBOL(key_unlink);
 975
 976 /*****************************************************************************/
 977 /*
 978  * dispose of a keyring list after the RCU grace period, releasing the keys it
 979  * links to
 980  */
 981 static void keyring_clear_rcu_disposal(struct rcu_head *rcu)
 982 {
 983         struct keyring_list *klist;
 984         int loop;
 985
 986         klist = container_of(rcu, struct keyring_list, rcu);
 987
 988         for (loop = klist->nkeys - 1; loop >= 0; loop--)
 989                 key_put(klist->keys[loop]);
 990
 991         kfree(klist);
 992
 993 } /* end keyring_clear_rcu_disposal() */
 994
 995 /*****************************************************************************/
 996 /*
 997  * clear the specified process keyring
 998  * - implements keyctl(KEYCTL_CLEAR)
 999  */
1000 int keyring_clear(struct key *keyring)
1001 {
1002         struct keyring_list *klist;
1003         int ret;
1004
1005         ret = -ENOTDIR;
1006         if (keyring->type == &key_type_keyring) {
1007                 /* detach the pointer block with the locks held */
1008                 down_write(&keyring->sem);
1009
1010                 klist = rcu_dereference_locked_keyring(keyring);
1011                 if (klist) {
1012                         /* adjust the quota */
1013                         key_payload_reserve(keyring,
1014                                             sizeof(struct keyring_list));
1015
1016                         rcu_assign_pointer(keyring->payload.subscriptions,
1017                                            NULL);
1018                 }
1019
1020                 up_write(&keyring->sem);
1021
1022                 /* free the keys after the locks have been dropped */
1023                 if (klist)
1024                         call_rcu(&klist->rcu, keyring_clear_rcu_disposal);
1025
1026                 ret = 0;
1027         }
1028
1029         return ret;
1030
1031 } /* end keyring_clear() */
1032
1033 EXPORT_SYMBOL(keyring_clear);
1034
1035 /*****************************************************************************/
1036 /*
1037  * dispose of the links from a revoked keyring
1038  * - called with the key sem write-locked
1039  */
1040 static void keyring_revoke(struct key *keyring)
1041 {
1042         struct keyring_list *klist;
1043
1044         klist = rcu_dereference_locked_keyring(keyring);
1045
1046         /* adjust the quota */
1047         key_payload_reserve(keyring, 0);
1048
1049         if (klist) {
1050                 rcu_assign_pointer(keyring->payload.subscriptions, NULL);
1051                 call_rcu(&klist->rcu, keyring_clear_rcu_disposal);
1052         }
1053
1054 } /* end keyring_revoke() */
1055
1056 /*
1057  * Determine whether a key is dead
1058  */
1059 static bool key_is_dead(struct key *key, time_t limit)
1060 {
1061         return test_bit(KEY_FLAG_DEAD, &key->flags) ||
1062                 (key->expiry > 0 && key->expiry <= limit);
1063 }
1064
1065 /*
1066  * Collect garbage from the contents of a keyring
1067  */
1068 void keyring_gc(struct key *keyring, time_t limit)
1069 {
1070         struct keyring_list *klist, *new;
1071         struct key *key;
1072         int loop, keep, max;
1073
1074         kenter("{%x,%s}", key_serial(keyring), keyring->description);
1075
1076         down_write(&keyring->sem);
1077
1078         klist = rcu_dereference_locked_keyring(keyring);
1079         if (!klist)
1080                 goto no_klist;
1081
1082         /* work out how many subscriptions we're keeping */
1083         keep = 0;
1084         for (loop = klist->nkeys - 1; loop >= 0; loop--)
1085                 if (!key_is_dead(klist->keys[loop], limit))
1086                         keep++;
1087
1088         if (keep == klist->nkeys)
1089                 goto just_return;
1090
1091         /* allocate a new keyring payload */
1092         max = roundup(keep, 4);
1093         new = kmalloc(sizeof(struct keyring_list) + max * sizeof(struct key *),
1094                       GFP_KERNEL);
1095         if (!new)
1096                 goto nomem;
1097         new->maxkeys = max;
1098         new->nkeys = 0;
1099         new->delkey = 0;
1100
1101         /* install the live keys
1102          * - must take care as expired keys may be updated back to life
1103          */
1104         keep = 0;
1105         for (loop = klist->nkeys - 1; loop >= 0; loop--) {
1106                 key = klist->keys[loop];
1107                 if (!key_is_dead(key, limit)) {
1108                         if (keep >= max)
1109                                 goto discard_new;
1110                         new->keys[keep++] = key_get(key);
1111                 }
1112         }
1113         new->nkeys = keep;
1114
1115         /* adjust the quota */
1116         key_payload_reserve(keyring,
1117                             sizeof(struct keyring_list) +
1118                             KEYQUOTA_LINK_BYTES * keep);
1119
1120         if (keep == 0) {
1121                 rcu_assign_pointer(keyring->payload.subscriptions, NULL);
1122                 kfree(new);
1123         } else {
1124                 rcu_assign_pointer(keyring->payload.subscriptions, new);
1125         }
1126
1127         up_write(&keyring->sem);
1128
1129         call_rcu(&klist->rcu, keyring_clear_rcu_disposal);
1130         kleave(" [yes]");
1131         return;
1132
1133 discard_new:
1134         new->nkeys = keep;
1135         keyring_clear_rcu_disposal(&new->rcu);
1136         up_write(&keyring->sem);
1137         kleave(" [discard]");
1138         return;
1139
1140 just_return:
1141         up_write(&keyring->sem);
1142         kleave(" [no dead]");
1143         return;
1144
1145 no_klist:
1146         up_write(&keyring->sem);
1147         kleave(" [no_klist]");
1148         return;
1149
1150 nomem:
1151         up_write(&keyring->sem);
1152         kleave(" [oom]");
1153 }