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