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