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