1	// SPDX-License-Identifier: GPL-2.0-or-later
2	/* Keyring handling
3	*
4	* Copyright (C) 2004-2005, 2008, 2013 Red Hat, Inc. All Rights Reserved.
5	* Written by David Howells (dhowells@redhat.com)
6	*/
7
8	#include <linux/export.h>
9	#include <linux/init.h>
10	#include <linux/sched.h>
11	#include <linux/slab.h>
12	#include <linux/security.h>
13	#include <linux/seq_file.h>
14	#include <linux/err.h>
15	#include <linux/user_namespace.h>
16	#include <linux/nsproxy.h>
17	#include <keys/keyring-type.h>
18	#include <keys/user-type.h>
19	#include <linux/assoc_array_priv.h>
20	#include <linux/uaccess.h>
21	#include <net/net_namespace.h>
22	#include "internal.h"
23
24	/*
25	* When plumbing the depths of the key tree, this sets a hard limit
26	* set on how deep we're willing to go.
27	*/
28	#define KEYRING_SEARCH_MAX_DEPTH 6
29
30	/*
31	* We mark pointers we pass to the associative array with bit 1 set if
32	* they're keyrings and clear otherwise.
33	*/
34	#define KEYRING_PTR_SUBTYPE 0x2UL
35
36	static inline bool keyring_ptr_is_keyring(const struct assoc_array_ptr *x)
37	{
38	return (unsigned long)x & KEYRING_PTR_SUBTYPE;
39	}
40	static inline struct key *keyring_ptr_to_key(const struct assoc_array_ptr *x)
41	{
42	void *object = assoc_array_ptr_to_leaf(x);
43	return (struct key *)((unsigned long)object & ~KEYRING_PTR_SUBTYPE);
44	}
45	static inline void *keyring_key_to_ptr(struct key *key)
46	{
47	if (key->type == &key_type_keyring)
48	return (void *)((unsigned long)key | KEYRING_PTR_SUBTYPE);
49	return key;
50	}
51
52	static DEFINE_RWLOCK(keyring_name_lock);
53
54	/*
55	* Clean up the bits of user_namespace that belong to us.
56	*/
57	void key_free_user_ns(struct user_namespace *ns)
58	{
59	write_lock(&keyring_name_lock);
60	list_del_init(entry: &ns->keyring_name_list);
61	write_unlock(&keyring_name_lock);
62
63	key_put(key: ns->user_keyring_register);
64	#ifdef CONFIG_PERSISTENT_KEYRINGS
65	key_put(key: ns->persistent_keyring_register);
66	#endif
67	}
68
69	/*
70	* The keyring key type definition. Keyrings are simply keys of this type and
71	* can be treated as ordinary keys in addition to having their own special
72	* operations.
73	*/
74	static int keyring_preparse(struct key_preparsed_payload *prep);
75	static void keyring_free_preparse(struct key_preparsed_payload *prep);
76	static int keyring_instantiate(struct key *keyring,
77	struct key_preparsed_payload *prep);
78	static void keyring_revoke(struct key *keyring);
79	static void keyring_destroy(struct key *keyring);
80	static void keyring_describe(const struct key *keyring, struct seq_file *m);
81	static long keyring_read(const struct key *keyring,
82	char *buffer, size_t buflen);
83
84	struct key_type key_type_keyring = {
85	.name = "keyring",
86	.def_datalen = 0,
87	.preparse = keyring_preparse,
88	.free_preparse = keyring_free_preparse,
89	.instantiate = keyring_instantiate,
90	.revoke = keyring_revoke,
91	.destroy = keyring_destroy,
92	.describe = keyring_describe,
93	.read = keyring_read,
94	};
95	EXPORT_SYMBOL(key_type_keyring);
96
97	/*
98	* Semaphore to serialise link/link calls to prevent two link calls in parallel
99	* introducing a cycle.
100	*/
101	static DEFINE_MUTEX(keyring_serialise_link_lock);
102
103	/*
104	* Publish the name of a keyring so that it can be found by name (if it has
105	* one and it doesn't begin with a dot).
106	*/
107	static void keyring_publish_name(struct key *keyring)
108	{
109	struct user_namespace *ns = current_user_ns();
110
111	if (keyring->description &&
112	keyring->description[0] &&
113	keyring->description[0] != '.') {
114	write_lock(&keyring_name_lock);
115	list_add_tail(new: &keyring->name_link, head: &ns->keyring_name_list);
116	write_unlock(&keyring_name_lock);
117	}
118	}
119
120	/*
121	* Preparse a keyring payload
122	*/
123	static int keyring_preparse(struct key_preparsed_payload *prep)
124	{
125	return prep->datalen != 0 ? -EINVAL : 0;
126	}
127
128	/*
129	* Free a preparse of a user defined key payload
130	*/
131	static void keyring_free_preparse(struct key_preparsed_payload *prep)
132	{
133	}
134
135	/*
136	* Initialise a keyring.
137	*
138	* Returns 0 on success, -EINVAL if given any data.
139	*/
140	static int keyring_instantiate(struct key *keyring,
141	struct key_preparsed_payload *prep)
142	{
143	assoc_array_init(array: &keyring->keys);
144	/* make the keyring available by name if it has one */
145	keyring_publish_name(keyring);
146	return 0;
147	}
148
149	/*
150	* Multiply 64-bits by 32-bits to 96-bits and fold back to 64-bit. Ideally we'd
151	* fold the carry back too, but that requires inline asm.
152	*/
153	static u64 mult_64x32_and_fold(u64 x, u32 y)
154	{
155	u64 hi = (u64)(u32)(x >> 32) * y;
156	u64 lo = (u64)(u32)(x) * y;
157	return lo + ((u64)(u32)hi << 32) + (u32)(hi >> 32);
158	}
159
160	/*
161	* Hash a key type and description.
162	*/
163	static void hash_key_type_and_desc(struct keyring_index_key *index_key)
164	{
165	const unsigned level_shift = ASSOC_ARRAY_LEVEL_STEP;
166	const unsigned long fan_mask = ASSOC_ARRAY_FAN_MASK;
167	const char *description = index_key->description;
168	unsigned long hash, type;
169	u32 piece;
170	u64 acc;
171	int n, desc_len = index_key->desc_len;
172
173	type = (unsigned long)index_key->type;
174	acc = mult_64x32_and_fold(x: type, y: desc_len + 13);
175	acc = mult_64x32_and_fold(x: acc, y: 9207);
176	piece = (unsigned long)index_key->domain_tag;
177	acc = mult_64x32_and_fold(x: acc, y: piece);
178	acc = mult_64x32_and_fold(x: acc, y: 9207);
179
180	for (;;) {
181	n = desc_len;
182	if (n <= 0)
183	break;
184	if (n > 4)
185	n = 4;
186	piece = 0;
187	memcpy(&piece, description, n);
188	description += n;
189	desc_len -= n;
190	acc = mult_64x32_and_fold(x: acc, y: piece);
191	acc = mult_64x32_and_fold(x: acc, y: 9207);
192	}
193
194	/* Fold the hash down to 32 bits if need be. */
195	hash = acc;
196	if (ASSOC_ARRAY_KEY_CHUNK_SIZE == 32)
197	hash ^= acc >> 32;
198
199	/* Squidge all the keyrings into a separate part of the tree to
200	* ordinary keys by making sure the lowest level segment in the hash is
201	* zero for keyrings and non-zero otherwise.
202	*/
203	if (index_key->type != &key_type_keyring && (hash & fan_mask) == 0)
204	hash |= (hash >> (ASSOC_ARRAY_KEY_CHUNK_SIZE - level_shift)) | 1;
205	else if (index_key->type == &key_type_keyring && (hash & fan_mask) != 0)
206	hash = (hash + (hash << level_shift)) & ~fan_mask;
207	index_key->hash = hash;
208	}
209
210	/*
211	* Finalise an index key to include a part of the description actually in the
212	* index key, to set the domain tag and to calculate the hash.
213	*/
214	void key_set_index_key(struct keyring_index_key *index_key)
215	{
216	static struct key_tag default_domain_tag = { .usage = REFCOUNT_INIT(1), };
217	size_t n = min_t(size_t, index_key->desc_len, sizeof(index_key->desc));
218
219	memcpy(index_key->desc, index_key->description, n);
220
221	if (!index_key->domain_tag) {
222	if (index_key->type->flags & KEY_TYPE_NET_DOMAIN)
223	index_key->domain_tag = current->nsproxy->net_ns->key_domain;
224	else
225	index_key->domain_tag = &default_domain_tag;
226	}
227
228	hash_key_type_and_desc(index_key);
229	}
230
231	/**
232	* key_put_tag - Release a ref on a tag.
233	* @tag: The tag to release.
234	*
235	* This releases a reference the given tag and returns true if that ref was the
236	* last one.
237	*/
238	bool key_put_tag(struct key_tag *tag)
239	{
240	if (refcount_dec_and_test(r: &tag->usage)) {
241	kfree_rcu(tag, rcu);
242	return true;
243	}
244
245	return false;
246	}
247
248	/**
249	* key_remove_domain - Kill off a key domain and gc its keys
250	* @domain_tag: The domain tag to release.
251	*
252	* This marks a domain tag as being dead and releases a ref on it. If that
253	* wasn't the last reference, the garbage collector is poked to try and delete
254	* all keys that were in the domain.
255	*/
256	void key_remove_domain(struct key_tag *domain_tag)
257	{
258	domain_tag->removed = true;
259	if (!key_put_tag(tag: domain_tag))
260	key_schedule_gc_links();
261	}
262
263	/*
264	* Build the next index key chunk.
265	*
266	* We return it one word-sized chunk at a time.
267	*/
268	static unsigned long keyring_get_key_chunk(const void *data, int level)
269	{
270	const struct keyring_index_key *index_key = data;
271	unsigned long chunk = 0;
272	const u8 *d;
273	int desc_len = index_key->desc_len, n = sizeof(chunk);
274
275	level /= ASSOC_ARRAY_KEY_CHUNK_SIZE;
276	switch (level) {
277	case 0:
278	return index_key->hash;
279	case 1:
280	return index_key->x;
281	case 2:
282	return (unsigned long)index_key->type;
283	case 3:
284	return (unsigned long)index_key->domain_tag;
285	default:
286	level -= 4;
287	if (desc_len <= sizeof(index_key->desc))
288	return 0;
289
290	d = index_key->description + sizeof(index_key->desc);
291	d += level * sizeof(long);
292	desc_len -= sizeof(index_key->desc);
293	if (desc_len > n)
294	desc_len = n;
295	do {
296	chunk <<= 8;
297	chunk |= *d++;
298	} while (--desc_len > 0);
299	return chunk;
300	}
301	}
302
303	static unsigned long keyring_get_object_key_chunk(const void *object, int level)
304	{
305	const struct key *key = keyring_ptr_to_key(x: object);
306	return keyring_get_key_chunk(data: &key->index_key, level);
307	}
308
309	static bool keyring_compare_object(const void *object, const void *data)
310	{
311	const struct keyring_index_key *index_key = data;
312	const struct key *key = keyring_ptr_to_key(x: object);
313
314	return key->index_key.type == index_key->type &&
315	key->index_key.domain_tag == index_key->domain_tag &&
316	key->index_key.desc_len == index_key->desc_len &&
317	memcmp(p: key->index_key.description, q: index_key->description,
318	size: index_key->desc_len) == 0;
319	}
320
321	/*
322	* Compare the index keys of a pair of objects and determine the bit position
323	* at which they differ - if they differ.
324	*/
325	static int keyring_diff_objects(const void *object, const void *data)
326	{
327	const struct key *key_a = keyring_ptr_to_key(x: object);
328	const struct keyring_index_key *a = &key_a->index_key;
329	const struct keyring_index_key *b = data;
330	unsigned long seg_a, seg_b;
331	int level, i;
332
333	level = 0;
334	seg_a = a->hash;
335	seg_b = b->hash;
336	if ((seg_a ^ seg_b) != 0)
337	goto differ;
338	level += ASSOC_ARRAY_KEY_CHUNK_SIZE / 8;
339
340	/* The number of bits contributed by the hash is controlled by a
341	* constant in the assoc_array headers. Everything else thereafter we
342	* can deal with as being machine word-size dependent.
343	*/
344	seg_a = a->x;
345	seg_b = b->x;
346	if ((seg_a ^ seg_b) != 0)
347	goto differ;
348	level += sizeof(unsigned long);
349
350	/* The next bit may not work on big endian */
351	seg_a = (unsigned long)a->type;
352	seg_b = (unsigned long)b->type;
353	if ((seg_a ^ seg_b) != 0)
354	goto differ;
355	level += sizeof(unsigned long);
356
357	seg_a = (unsigned long)a->domain_tag;
358	seg_b = (unsigned long)b->domain_tag;
359	if ((seg_a ^ seg_b) != 0)
360	goto differ;
361	level += sizeof(unsigned long);
362
363	i = sizeof(a->desc);
364	if (a->desc_len <= i)
365	goto same;
366
367	for (; i < a->desc_len; i++) {
368	seg_a = *(unsigned char *)(a->description + i);
369	seg_b = *(unsigned char *)(b->description + i);
370	if ((seg_a ^ seg_b) != 0)
371	goto differ_plus_i;
372	}
373
374	same:
375	return -1;
376
377	differ_plus_i:
378	level += i;
379	differ:
380	i = level * 8 + __ffs(seg_a ^ seg_b);
381	return i;
382	}
383
384	/*
385	* Free an object after stripping the keyring flag off of the pointer.
386	*/
387	static void keyring_free_object(void *object)
388	{
389	key_put(key: keyring_ptr_to_key(x: object));
390	}
391
392	/*
393	* Operations for keyring management by the index-tree routines.
394	*/
395	static const struct assoc_array_ops keyring_assoc_array_ops = {
396	.get_key_chunk = keyring_get_key_chunk,
397	.get_object_key_chunk = keyring_get_object_key_chunk,
398	.compare_object = keyring_compare_object,
399	.diff_objects = keyring_diff_objects,
400	.free_object = keyring_free_object,
401	};
402
403	/*
404	* Clean up a keyring when it is destroyed. Unpublish its name if it had one
405	* and dispose of its data.
406	*
407	* The garbage collector detects the final key_put(), removes the keyring from
408	* the serial number tree and then does RCU synchronisation before coming here,
409	* so we shouldn't need to worry about code poking around here with the RCU
410	* readlock held by this time.
411	*/
412	static void keyring_destroy(struct key *keyring)
413	{
414	if (keyring->description) {
415	write_lock(&keyring_name_lock);
416
417	if (keyring->name_link.next != NULL &&
418	!list_empty(head: &keyring->name_link))
419	list_del(entry: &keyring->name_link);
420
421	write_unlock(&keyring_name_lock);
422	}
423
424	if (keyring->restrict_link) {
425	struct key_restriction *keyres = keyring->restrict_link;
426
427	key_put(key: keyres->key);
428	kfree(objp: keyres);
429	}
430
431	assoc_array_destroy(array: &keyring->keys, ops: &keyring_assoc_array_ops);
432	}
433
434	/*
435	* Describe a keyring for /proc.
436	*/
437	static void keyring_describe(const struct key *keyring, struct seq_file *m)
438	{
439	if (keyring->description)
440	seq_puts(m, s: keyring->description);
441	else
442	seq_puts(m, s: "[anon]");
443
444	if (key_is_positive(key: keyring)) {
445	if (keyring->keys.nr_leaves_on_tree != 0)
446	seq_printf(m, fmt: ": %lu", keyring->keys.nr_leaves_on_tree);
447	else
448	seq_puts(m, s: ": empty");
449	}
450	}
451
452	struct keyring_read_iterator_context {
453	size_t buflen;
454	size_t count;
455	key_serial_t *buffer;
456	};
457
458	static int keyring_read_iterator(const void *object, void *data)
459	{
460	struct keyring_read_iterator_context *ctx = data;
461	const struct key *key = keyring_ptr_to_key(x: object);
462
463	kenter("{%s,%d},,{%zu/%zu}",
464	key->type->name, key->serial, ctx->count, ctx->buflen);
465
466	if (ctx->count >= ctx->buflen)
467	return 1;
468
469	*ctx->buffer++ = key->serial;
470	ctx->count += sizeof(key->serial);
471	return 0;
472	}
473
474	/*
475	* Read a list of key IDs from the keyring's contents in binary form
476	*
477	* The keyring's semaphore is read-locked by the caller. This prevents someone
478	* from modifying it under us - which could cause us to read key IDs multiple
479	* times.
480	*/
481	static long keyring_read(const struct key *keyring,
482	char *buffer, size_t buflen)
483	{
484	struct keyring_read_iterator_context ctx;
485	long ret;
486
487	kenter("{%d},,%zu", key_serial(keyring), buflen);
488
489	if (buflen & (sizeof(key_serial_t) - 1))
490	return -EINVAL;
491
492	/* Copy as many key IDs as fit into the buffer */
493	if (buffer && buflen) {
494	ctx.buffer = (key_serial_t *)buffer;
495	ctx.buflen = buflen;
496	ctx.count = 0;
497	ret = assoc_array_iterate(array: &keyring->keys,
498	iterator: keyring_read_iterator, iterator_data: &ctx);
499	if (ret < 0) {
500	kleave(" = %ld [iterate]", ret);
501	return ret;
502	}
503	}
504
505	/* Return the size of the buffer needed */
506	ret = keyring->keys.nr_leaves_on_tree * sizeof(key_serial_t);
507	if (ret <= buflen)
508	kleave("= %ld [ok]", ret);
509	else
510	kleave("= %ld [buffer too small]", ret);
511	return ret;
512	}
513
514	/*
515	* Allocate a keyring and link into the destination keyring.
516	*/
517	struct key *keyring_alloc(const char *description, kuid_t uid, kgid_t gid,
518	const struct cred *cred, key_perm_t perm,
519	unsigned long flags,
520	struct key_restriction *restrict_link,
521	struct key *dest)
522	{
523	struct key *keyring;
524	int ret;
525
526	keyring = key_alloc(type: &key_type_keyring, desc: description,
527	uid, gid, cred, perm, flags, restrict_link);
528	if (!IS_ERR(ptr: keyring)) {
529	ret = key_instantiate_and_link(key: keyring, NULL, datalen: 0, keyring: dest, NULL);
530	if (ret < 0) {
531	key_put(key: keyring);
532	keyring = ERR_PTR(error: ret);
533	}
534	}
535
536	return keyring;
537	}
538	EXPORT_SYMBOL(keyring_alloc);
539
540	/**
541	* restrict_link_reject - Give -EPERM to restrict link
542	* @keyring: The keyring being added to.
543	* @type: The type of key being added.
544	* @payload: The payload of the key intended to be added.
545	* @restriction_key: Keys providing additional data for evaluating restriction.
546	*
547	* Reject the addition of any links to a keyring. It can be overridden by
548	* passing KEY_ALLOC_BYPASS_RESTRICTION to key_instantiate_and_link() when
549	* adding a key to a keyring.
550	*
551	* This is meant to be stored in a key_restriction structure which is passed
552	* in the restrict_link parameter to keyring_alloc().
553	*/
554	int restrict_link_reject(struct key *keyring,
555	const struct key_type *type,
556	const union key_payload *payload,
557	struct key *restriction_key)
558	{
559	return -EPERM;
560	}
561
562	/*
563	* By default, we keys found by getting an exact match on their descriptions.
564	*/
565	bool key_default_cmp(const struct key *key,
566	const struct key_match_data *match_data)
567	{
568	return strcmp(key->description, match_data->raw_data) == 0;
569	}
570
571	/*
572	* Iteration function to consider each key found.
573	*/
574	static int keyring_search_iterator(const void *object, void *iterator_data)
575	{
576	struct keyring_search_context *ctx = iterator_data;
577	const struct key *key = keyring_ptr_to_key(x: object);
578	unsigned long kflags = READ_ONCE(key->flags);
579	short state = READ_ONCE(key->state);
580
581	kenter("{%d}", key->serial);
582
583	/* ignore keys not of this type */
584	if (key->type != ctx->index_key.type) {
585	kleave(" = 0 [!type]");
586	return 0;
587	}
588
589	/* skip invalidated, revoked and expired keys */
590	if (ctx->flags & KEYRING_SEARCH_DO_STATE_CHECK) {
591	time64_t expiry = READ_ONCE(key->expiry);
592
593	if (kflags & ((1 << KEY_FLAG_INVALIDATED) |
594	(1 << KEY_FLAG_REVOKED))) {
595	ctx->result = ERR_PTR(error: -EKEYREVOKED);
596	kleave(" = %d [invrev]", ctx->skipped_ret);
597	goto skipped;
598	}
599
600	if (expiry && ctx->now >= expiry) {
601	if (!(ctx->flags & KEYRING_SEARCH_SKIP_EXPIRED))
602	ctx->result = ERR_PTR(error: -EKEYEXPIRED);
603	kleave(" = %d [expire]", ctx->skipped_ret);
604	goto skipped;
605	}
606	}
607
608	/* keys that don't match */
609	if (!ctx->match_data.cmp(key, &ctx->match_data)) {
610	kleave(" = 0 [!match]");
611	return 0;
612	}
613
614	/* key must have search permissions */
615	if (!(ctx->flags & KEYRING_SEARCH_NO_CHECK_PERM) &&
616	key_task_permission(key_ref: make_key_ref(key, possession: ctx->possessed),
617	cred: ctx->cred, need_perm: KEY_NEED_SEARCH) < 0) {
618	ctx->result = ERR_PTR(error: -EACCES);
619	kleave(" = %d [!perm]", ctx->skipped_ret);
620	goto skipped;
621	}
622
623	if (ctx->flags & KEYRING_SEARCH_DO_STATE_CHECK) {
624	/* we set a different error code if we pass a negative key */
625	if (state < 0) {
626	ctx->result = ERR_PTR(error: state);
627	kleave(" = %d [neg]", ctx->skipped_ret);
628	goto skipped;
629	}
630	}
631
632	/* Found */
633	ctx->result = make_key_ref(key, possession: ctx->possessed);
634	kleave(" = 1 [found]");
635	return 1;
636
637	skipped:
638	return ctx->skipped_ret;
639	}
640
641	/*
642	* Search inside a keyring for a key. We can search by walking to it
643	* directly based on its index-key or we can iterate over the entire
644	* tree looking for it, based on the match function.
645	*/
646	static int search_keyring(struct key *keyring, struct keyring_search_context *ctx)
647	{
648	if (ctx->match_data.lookup_type == KEYRING_SEARCH_LOOKUP_DIRECT) {
649	const void *object;
650
651	object = assoc_array_find(array: &keyring->keys,
652	ops: &keyring_assoc_array_ops,
653	index_key: &ctx->index_key);
654	return object ? ctx->iterator(object, ctx) : 0;
655	}
656	return assoc_array_iterate(array: &keyring->keys, iterator: ctx->iterator, iterator_data: ctx);
657	}
658
659	/*
660	* Search a tree of keyrings that point to other keyrings up to the maximum
661	* depth.
662	*/
663	static bool search_nested_keyrings(struct key *keyring,
664	struct keyring_search_context *ctx)
665	{
666	struct {
667	struct key *keyring;
668	struct assoc_array_node *node;
669	int slot;
670	} stack[KEYRING_SEARCH_MAX_DEPTH];
671
672	struct assoc_array_shortcut *shortcut;
673	struct assoc_array_node *node;
674	struct assoc_array_ptr *ptr;
675	struct key *key;
676	int sp = 0, slot;
677
678	kenter("{%d},{%s,%s}",
679	keyring->serial,
680	ctx->index_key.type->name,
681	ctx->index_key.description);
682
683	#define STATE_CHECKS (KEYRING_SEARCH_NO_STATE_CHECK | KEYRING_SEARCH_DO_STATE_CHECK)
684	BUG_ON((ctx->flags & STATE_CHECKS) == 0 ||
685	(ctx->flags & STATE_CHECKS) == STATE_CHECKS);
686
687	if (ctx->index_key.description)
688	key_set_index_key(index_key: &ctx->index_key);
689
690	/* Check to see if this top-level keyring is what we are looking for
691	* and whether it is valid or not.
692	*/
693	if (ctx->match_data.lookup_type == KEYRING_SEARCH_LOOKUP_ITERATE ||
694	keyring_compare_object(object: keyring, data: &ctx->index_key)) {
695	ctx->skipped_ret = 2;
696	switch (ctx->iterator(keyring_key_to_ptr(key: keyring), ctx)) {
697	case 1:
698	goto found;
699	case 2:
700	return false;
701	default:
702	break;
703	}
704	}
705
706	ctx->skipped_ret = 0;
707
708	/* Start processing a new keyring */
709	descend_to_keyring:
710	kdebug("descend to %d", keyring->serial);
711	if (keyring->flags & ((1 << KEY_FLAG_INVALIDATED) |
712	(1 << KEY_FLAG_REVOKED)))
713	goto not_this_keyring;
714
715	/* Search through the keys in this keyring before its searching its
716	* subtrees.
717	*/
718	if (search_keyring(keyring, ctx))
719	goto found;
720
721	/* Then manually iterate through the keyrings nested in this one.
722	*
723	* Start from the root node of the index tree. Because of the way the
724	* hash function has been set up, keyrings cluster on the leftmost
725	* branch of the root node (root slot 0) or in the root node itself.
726	* Non-keyrings avoid the leftmost branch of the root entirely (root
727	* slots 1-15).
728	*/
729	if (!(ctx->flags & KEYRING_SEARCH_RECURSE))
730	goto not_this_keyring;
731
732	ptr = READ_ONCE(keyring->keys.root);
733	if (!ptr)
734	goto not_this_keyring;
735
736	if (assoc_array_ptr_is_shortcut(x: ptr)) {
737	/* If the root is a shortcut, either the keyring only contains
738	* keyring pointers (everything clusters behind root slot 0) or
739	* doesn't contain any keyring pointers.
740	*/
741	shortcut = assoc_array_ptr_to_shortcut(x: ptr);
742	if ((shortcut->index_key[0] & ASSOC_ARRAY_FAN_MASK) != 0)
743	goto not_this_keyring;
744
745	ptr = READ_ONCE(shortcut->next_node);
746	node = assoc_array_ptr_to_node(x: ptr);
747	goto begin_node;
748	}
749
750	node = assoc_array_ptr_to_node(x: ptr);
751	ptr = node->slots[0];
752	if (!assoc_array_ptr_is_meta(x: ptr))
753	goto begin_node;
754
755	descend_to_node:
756	/* Descend to a more distal node in this keyring's content tree and go
757	* through that.
758	*/
759	kdebug("descend");
760	if (assoc_array_ptr_is_shortcut(x: ptr)) {
761	shortcut = assoc_array_ptr_to_shortcut(x: ptr);
762	ptr = READ_ONCE(shortcut->next_node);
763	BUG_ON(!assoc_array_ptr_is_node(ptr));
764	}
765	node = assoc_array_ptr_to_node(x: ptr);
766
767	begin_node:
768	kdebug("begin_node");
769	slot = 0;
770	ascend_to_node:
771	/* Go through the slots in a node */
772	for (; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
773	ptr = READ_ONCE(node->slots[slot]);
774
775	if (assoc_array_ptr_is_meta(x: ptr) && node->back_pointer)
776	goto descend_to_node;
777
778	if (!keyring_ptr_is_keyring(x: ptr))
779	continue;
780
781	key = keyring_ptr_to_key(x: ptr);
782
783	if (sp >= KEYRING_SEARCH_MAX_DEPTH) {
784	if (ctx->flags & KEYRING_SEARCH_DETECT_TOO_DEEP) {
785	ctx->result = ERR_PTR(error: -ELOOP);
786	return false;
787	}
788	goto not_this_keyring;
789	}
790
791	/* Search a nested keyring */
792	if (!(ctx->flags & KEYRING_SEARCH_NO_CHECK_PERM) &&
793	key_task_permission(key_ref: make_key_ref(key, possession: ctx->possessed),
794	cred: ctx->cred, need_perm: KEY_NEED_SEARCH) < 0)
795	continue;
796
797	/* stack the current position */
798	stack[sp].keyring = keyring;
799	stack[sp].node = node;
800	stack[sp].slot = slot;
801	sp++;
802
803	/* begin again with the new keyring */
804	keyring = key;
805	goto descend_to_keyring;
806	}
807
808	/* We've dealt with all the slots in the current node, so now we need
809	* to ascend to the parent and continue processing there.
810	*/
811	ptr = READ_ONCE(node->back_pointer);
812	slot = node->parent_slot;
813
814	if (ptr && assoc_array_ptr_is_shortcut(x: ptr)) {
815	shortcut = assoc_array_ptr_to_shortcut(x: ptr);
816	ptr = READ_ONCE(shortcut->back_pointer);
817	slot = shortcut->parent_slot;
818	}
819	if (!ptr)
820	goto not_this_keyring;
821	node = assoc_array_ptr_to_node(x: ptr);
822	slot++;
823
824	/* If we've ascended to the root (zero backpointer), we must have just
825	* finished processing the leftmost branch rather than the root slots -
826	* so there can't be any more keyrings for us to find.
827	*/
828	if (node->back_pointer) {
829	kdebug("ascend %d", slot);
830	goto ascend_to_node;
831	}
832
833	/* The keyring we're looking at was disqualified or didn't contain a
834	* matching key.
835	*/
836	not_this_keyring:
837	kdebug("not_this_keyring %d", sp);
838	if (sp <= 0) {
839	kleave(" = false");
840	return false;
841	}
842
843	/* Resume the processing of a keyring higher up in the tree */
844	sp--;
845	keyring = stack[sp].keyring;
846	node = stack[sp].node;
847	slot = stack[sp].slot + 1;
848	kdebug("ascend to %d [%d]", keyring->serial, slot);
849	goto ascend_to_node;
850
851	/* We found a viable match */
852	found:
853	key = key_ref_to_ptr(key_ref: ctx->result);
854	key_check(key);
855	if (!(ctx->flags & KEYRING_SEARCH_NO_UPDATE_TIME)) {
856	key->last_used_at = ctx->now;
857	keyring->last_used_at = ctx->now;
858	while (sp > 0)
859	stack[--sp].keyring->last_used_at = ctx->now;
860	}
861	kleave(" = true");
862	return true;
863	}
864
865	/**
866	* keyring_search_rcu - Search a keyring tree for a matching key under RCU
867	* @keyring_ref: A pointer to the keyring with possession indicator.
868	* @ctx: The keyring search context.
869	*
870	* Search the supplied keyring tree for a key that matches the criteria given.
871	* The root keyring and any linked keyrings must grant Search permission to the
872	* caller to be searchable and keys can only be found if they too grant Search
873	* to the caller. The possession flag on the root keyring pointer controls use
874	* of the possessor bits in permissions checking of the entire tree. In
875	* addition, the LSM gets to forbid keyring searches and key matches.
876	*
877	* The search is performed as a breadth-then-depth search up to the prescribed
878	* limit (KEYRING_SEARCH_MAX_DEPTH). The caller must hold the RCU read lock to
879	* prevent keyrings from being destroyed or rearranged whilst they are being
880	* searched.
881	*
882	* Keys are matched to the type provided and are then filtered by the match
883	* function, which is given the description to use in any way it sees fit. The
884	* match function may use any attributes of a key that it wishes to
885	* determine the match. Normally the match function from the key type would be
886	* used.
887	*
888	* RCU can be used to prevent the keyring key lists from disappearing without
889	* the need to take lots of locks.
890	*
891	* Returns a pointer to the found key and increments the key usage count if
892	* successful; -EAGAIN if no matching keys were found, or if expired or revoked
893	* keys were found; -ENOKEY if only negative keys were found; -ENOTDIR if the
894	* specified keyring wasn't a keyring.
895	*
896	* In the case of a successful return, the possession attribute from
897	* @keyring_ref is propagated to the returned key reference.
898	*/
899	key_ref_t keyring_search_rcu(key_ref_t keyring_ref,
900	struct keyring_search_context *ctx)
901	{
902	struct key *keyring;
903	long err;
904
905	ctx->iterator = keyring_search_iterator;
906	ctx->possessed = is_key_possessed(key_ref: keyring_ref);
907	ctx->result = ERR_PTR(error: -EAGAIN);
908
909	keyring = key_ref_to_ptr(key_ref: keyring_ref);
910	key_check(keyring);
911
912	if (keyring->type != &key_type_keyring)
913	return ERR_PTR(error: -ENOTDIR);
914
915	if (!(ctx->flags & KEYRING_SEARCH_NO_CHECK_PERM)) {
916	err = key_task_permission(key_ref: keyring_ref, cred: ctx->cred, need_perm: KEY_NEED_SEARCH);
917	if (err < 0)
918	return ERR_PTR(error: err);
919	}
920
921	ctx->now = ktime_get_real_seconds();
922	if (search_nested_keyrings(keyring, ctx))
923	__key_get(key: key_ref_to_ptr(key_ref: ctx->result));
924	return ctx->result;
925	}
926
927	/**
928	* keyring_search - Search the supplied keyring tree for a matching key
929	* @keyring: The root of the keyring tree to be searched.
930	* @type: The type of keyring we want to find.
931	* @description: The name of the keyring we want to find.
932	* @recurse: True to search the children of @keyring also
933	*
934	* As keyring_search_rcu() above, but using the current task's credentials and
935	* type's default matching function and preferred search method.
936	*/
937	key_ref_t keyring_search(key_ref_t keyring,
938	struct key_type *type,
939	const char *description,
940	bool recurse)
941	{
942	struct keyring_search_context ctx = {
943	.index_key.type = type,
944	.index_key.description = description,
945	.index_key.desc_len = strlen(description),
946	.cred = current_cred(),
947	.match_data.cmp = key_default_cmp,
948	.match_data.raw_data = description,
949	.match_data.lookup_type = KEYRING_SEARCH_LOOKUP_DIRECT,
950	.flags = KEYRING_SEARCH_DO_STATE_CHECK,
951	};
952	key_ref_t key;
953	int ret;
954
955	if (recurse)
956	ctx.flags |= KEYRING_SEARCH_RECURSE;
957	if (type->match_preparse) {
958	ret = type->match_preparse(&ctx.match_data);
959	if (ret < 0)
960	return ERR_PTR(error: ret);
961	}
962
963	rcu_read_lock();
964	key = keyring_search_rcu(keyring_ref: keyring, ctx: &ctx);
965	rcu_read_unlock();
966
967	if (type->match_free)
968	type->match_free(&ctx.match_data);
969	return key;
970	}
971	EXPORT_SYMBOL(keyring_search);
972
973	static struct key_restriction *keyring_restriction_alloc(
974	key_restrict_link_func_t check)
975	{
976	struct key_restriction *keyres =
977	kzalloc(size: sizeof(struct key_restriction), GFP_KERNEL);
978
979	if (!keyres)
980	return ERR_PTR(error: -ENOMEM);
981
982	keyres->check = check;
983
984	return keyres;
985	}
986
987	/*
988	* Semaphore to serialise restriction setup to prevent reference count
989	* cycles through restriction key pointers.
990	*/
991	static DECLARE_RWSEM(keyring_serialise_restrict_sem);
992
993	/*
994	* Check for restriction cycles that would prevent keyring garbage collection.
995	* keyring_serialise_restrict_sem must be held.
996	*/
997	static bool keyring_detect_restriction_cycle(const struct key *dest_keyring,
998	struct key_restriction *keyres)
999	{
1000	while (keyres && keyres->key &&
1001	keyres->key->type == &key_type_keyring) {
1002	if (keyres->key == dest_keyring)
1003	return true;
1004
1005	keyres = keyres->key->restrict_link;
1006	}
1007
1008	return false;
1009	}
1010
1011	/**
1012	* keyring_restrict - Look up and apply a restriction to a keyring
1013	* @keyring_ref: The keyring to be restricted
1014	* @type: The key type that will provide the restriction checker.
1015	* @restriction: The restriction options to apply to the keyring
1016	*
1017	* Look up a keyring and apply a restriction to it. The restriction is managed
1018	* by the specific key type, but can be configured by the options specified in
1019	* the restriction string.
1020	*/
1021	int keyring_restrict(key_ref_t keyring_ref, const char *type,
1022	const char *restriction)
1023	{
1024	struct key *keyring;
1025	struct key_type *restrict_type = NULL;
1026	struct key_restriction *restrict_link;
1027	int ret = 0;
1028
1029	keyring = key_ref_to_ptr(key_ref: keyring_ref);
1030	key_check(keyring);
1031
1032	if (keyring->type != &key_type_keyring)
1033	return -ENOTDIR;
1034
1035	if (!type) {
1036	restrict_link = keyring_restriction_alloc(check: restrict_link_reject);
1037	} else {
1038	restrict_type = key_type_lookup(type);
1039
1040	if (IS_ERR(ptr: restrict_type))
1041	return PTR_ERR(ptr: restrict_type);
1042
1043	if (!restrict_type->lookup_restriction) {
1044	ret = -ENOENT;
1045	goto error;
1046	}
1047
1048	restrict_link = restrict_type->lookup_restriction(restriction);
1049	}
1050
1051	if (IS_ERR(ptr: restrict_link)) {
1052	ret = PTR_ERR(ptr: restrict_link);
1053	goto error;
1054	}
1055
1056	down_write(sem: &keyring->sem);
1057	down_write(sem: &keyring_serialise_restrict_sem);
1058
1059	if (keyring->restrict_link) {
1060	ret = -EEXIST;
1061	} else if (keyring_detect_restriction_cycle(dest_keyring: keyring, keyres: restrict_link)) {
1062	ret = -EDEADLK;
1063	} else {
1064	keyring->restrict_link = restrict_link;
1065	notify_key(key: keyring, subtype: NOTIFY_KEY_SETATTR, aux: 0);
1066	}
1067
1068	up_write(sem: &keyring_serialise_restrict_sem);
1069	up_write(sem: &keyring->sem);
1070
1071	if (ret < 0) {
1072	key_put(key: restrict_link->key);
1073	kfree(objp: restrict_link);
1074	}
1075
1076	error:
1077	if (restrict_type)
1078	key_type_put(ktype: restrict_type);
1079
1080	return ret;
1081	}
1082	EXPORT_SYMBOL(keyring_restrict);
1083
1084	/*
1085	* Search the given keyring for a key that might be updated.
1086	*
1087	* The caller must guarantee that the keyring is a keyring and that the
1088	* permission is granted to modify the keyring as no check is made here. The
1089	* caller must also hold a lock on the keyring semaphore.
1090	*
1091	* Returns a pointer to the found key with usage count incremented if
1092	* successful and returns NULL if not found. Revoked and invalidated keys are
1093	* skipped over.
1094	*
1095	* If successful, the possession indicator is propagated from the keyring ref
1096	* to the returned key reference.
1097	*/
1098	key_ref_t find_key_to_update(key_ref_t keyring_ref,
1099	const struct keyring_index_key *index_key)
1100	{
1101	struct key *keyring, *key;
1102	const void *object;
1103
1104	keyring = key_ref_to_ptr(key_ref: keyring_ref);
1105
1106	kenter("{%d},{%s,%s}",
1107	keyring->serial, index_key->type->name, index_key->description);
1108
1109	object = assoc_array_find(array: &keyring->keys, ops: &keyring_assoc_array_ops,
1110	index_key);
1111
1112	if (object)
1113	goto found;
1114
1115	kleave(" = NULL");
1116	return NULL;
1117
1118	found:
1119	key = keyring_ptr_to_key(x: object);
1120	if (key->flags & ((1 << KEY_FLAG_INVALIDATED) |
1121	(1 << KEY_FLAG_REVOKED))) {
1122	kleave(" = NULL [x]");
1123	return NULL;
1124	}
1125	__key_get(key);
1126	kleave(" = {%d}", key->serial);
1127	return make_key_ref(key, possession: is_key_possessed(key_ref: keyring_ref));
1128	}
1129
1130	/*
1131	* Find a keyring with the specified name.
1132	*
1133	* Only keyrings that have nonzero refcount, are not revoked, and are owned by a
1134	* user in the current user namespace are considered. If @uid_keyring is %true,
1135	* the keyring additionally must have been allocated as a user or user session
1136	* keyring; otherwise, it must grant Search permission directly to the caller.
1137	*
1138	* Returns a pointer to the keyring with the keyring's refcount having being
1139	* incremented on success. -ENOKEY is returned if a key could not be found.
1140	*/
1141	struct key *find_keyring_by_name(const char *name, bool uid_keyring)
1142	{
1143	struct user_namespace *ns = current_user_ns();
1144	struct key *keyring;
1145
1146	if (!name)
1147	return ERR_PTR(error: -EINVAL);
1148
1149	read_lock(&keyring_name_lock);
1150
1151	/* Search this hash bucket for a keyring with a matching name that
1152	* grants Search permission and that hasn't been revoked
1153	*/
1154	list_for_each_entry(keyring, &ns->keyring_name_list, name_link) {
1155	if (!kuid_has_mapping(ns, uid: keyring->user->uid))
1156	continue;
1157
1158	if (test_bit(KEY_FLAG_REVOKED, &keyring->flags))
1159	continue;
1160
1161	if (strcmp(keyring->description, name) != 0)
1162	continue;
1163
1164	if (uid_keyring) {
1165	if (!test_bit(KEY_FLAG_UID_KEYRING,
1166	&keyring->flags))
1167	continue;
1168	} else {
1169	if (key_permission(key_ref: make_key_ref(key: keyring, possession: 0),
1170	need_perm: KEY_NEED_SEARCH) < 0)
1171	continue;
1172	}
1173
1174	/* we've got a match but we might end up racing with
1175	* key_cleanup() if the keyring is currently 'dead'
1176	* (ie. it has a zero usage count) */
1177	if (!refcount_inc_not_zero(r: &keyring->usage))
1178	continue;
1179	keyring->last_used_at = ktime_get_real_seconds();
1180	goto out;
1181	}
1182
1183	keyring = ERR_PTR(error: -ENOKEY);
1184	out:
1185	read_unlock(&keyring_name_lock);
1186	return keyring;
1187	}
1188
1189	static int keyring_detect_cycle_iterator(const void *object,
1190	void *iterator_data)
1191	{
1192	struct keyring_search_context *ctx = iterator_data;
1193	const struct key *key = keyring_ptr_to_key(x: object);
1194
1195	kenter("{%d}", key->serial);
1196
1197	/* We might get a keyring with matching index-key that is nonetheless a
1198	* different keyring. */
1199	if (key != ctx->match_data.raw_data)
1200	return 0;
1201
1202	ctx->result = ERR_PTR(error: -EDEADLK);
1203	return 1;
1204	}
1205
1206	/*
1207	* See if a cycle will be created by inserting acyclic tree B in acyclic
1208	* tree A at the topmost level (ie: as a direct child of A).
1209	*
1210	* Since we are adding B to A at the top level, checking for cycles should just
1211	* be a matter of seeing if node A is somewhere in tree B.
1212	*/
1213	static int keyring_detect_cycle(struct key *A, struct key *B)
1214	{
1215	struct keyring_search_context ctx = {
1216	.index_key = A->index_key,
1217	.match_data.raw_data = A,
1218	.match_data.lookup_type = KEYRING_SEARCH_LOOKUP_DIRECT,
1219	.iterator = keyring_detect_cycle_iterator,
1220	.flags = (KEYRING_SEARCH_NO_STATE_CHECK |
1221	KEYRING_SEARCH_NO_UPDATE_TIME |
1222	KEYRING_SEARCH_NO_CHECK_PERM |
1223	KEYRING_SEARCH_DETECT_TOO_DEEP |
1224	KEYRING_SEARCH_RECURSE),
1225	};
1226
1227	rcu_read_lock();
1228	search_nested_keyrings(keyring: B, ctx: &ctx);
1229	rcu_read_unlock();
1230	return PTR_ERR(ptr: ctx.result) == -EAGAIN ? 0 : PTR_ERR(ptr: ctx.result);
1231	}
1232
1233	/*
1234	* Lock keyring for link.
1235	*/
1236	int __key_link_lock(struct key *keyring,
1237	const struct keyring_index_key *index_key)
1238	__acquires(&keyring->sem)
1239	__acquires(&keyring_serialise_link_lock)
1240	{
1241	if (keyring->type != &key_type_keyring)
1242	return -ENOTDIR;
1243
1244	down_write(sem: &keyring->sem);
1245
1246	/* Serialise link/link calls to prevent parallel calls causing a cycle
1247	* when linking two keyring in opposite orders.
1248	*/
1249	if (index_key->type == &key_type_keyring)
1250	mutex_lock(&keyring_serialise_link_lock);
1251
1252	return 0;
1253	}
1254
1255	/*
1256	* Lock keyrings for move (link/unlink combination).
1257	*/
1258	int __key_move_lock(struct key *l_keyring, struct key *u_keyring,
1259	const struct keyring_index_key *index_key)
1260	__acquires(&l_keyring->sem)
1261	__acquires(&u_keyring->sem)
1262	__acquires(&keyring_serialise_link_lock)
1263	{
1264	if (l_keyring->type != &key_type_keyring ||
1265	u_keyring->type != &key_type_keyring)
1266	return -ENOTDIR;
1267
1268	/* We have to be very careful here to take the keyring locks in the
1269	* right order, lest we open ourselves to deadlocking against another
1270	* move operation.
1271	*/
1272	if (l_keyring < u_keyring) {
1273	down_write(sem: &l_keyring->sem);
1274	down_write_nested(sem: &u_keyring->sem, subclass: 1);
1275	} else {
1276	down_write(sem: &u_keyring->sem);
1277	down_write_nested(sem: &l_keyring->sem, subclass: 1);
1278	}
1279
1280	/* Serialise link/link calls to prevent parallel calls causing a cycle
1281	* when linking two keyring in opposite orders.
1282	*/
1283	if (index_key->type == &key_type_keyring)
1284	mutex_lock(&keyring_serialise_link_lock);
1285
1286	return 0;
1287	}
1288
1289	/*
1290	* Preallocate memory so that a key can be linked into to a keyring.
1291	*/
1292	int __key_link_begin(struct key *keyring,
1293	const struct keyring_index_key *index_key,
1294	struct assoc_array_edit **_edit)
1295	{
1296	struct assoc_array_edit *edit;
1297	int ret;
1298
1299	kenter("%d,%s,%s,",
1300	keyring->serial, index_key->type->name, index_key->description);
1301
1302	BUG_ON(index_key->desc_len == 0);
1303	BUG_ON(*_edit != NULL);
1304
1305	*_edit = NULL;
1306
1307	ret = -EKEYREVOKED;
1308	if (test_bit(KEY_FLAG_REVOKED, &keyring->flags))
1309	goto error;
1310
1311	/* Create an edit script that will insert/replace the key in the
1312	* keyring tree.
1313	*/
1314	edit = assoc_array_insert(array: &keyring->keys,
1315	ops: &keyring_assoc_array_ops,
1316	index_key,
1317	NULL);
1318	if (IS_ERR(ptr: edit)) {
1319	ret = PTR_ERR(ptr: edit);
1320	goto error;
1321	}
1322
1323	/* If we're not replacing a link in-place then we're going to need some
1324	* extra quota.
1325	*/
1326	if (!edit->dead_leaf) {
1327	ret = key_payload_reserve(key: keyring,
1328	datalen: keyring->datalen + KEYQUOTA_LINK_BYTES);
1329	if (ret < 0)
1330	goto error_cancel;
1331	}
1332
1333	*_edit = edit;
1334	kleave(" = 0");
1335	return 0;
1336
1337	error_cancel:
1338	assoc_array_cancel_edit(edit);
1339	error:
1340	kleave(" = %d", ret);
1341	return ret;
1342	}
1343
1344	/*
1345	* Check already instantiated keys aren't going to be a problem.
1346	*
1347	* The caller must have called __key_link_begin(). Don't need to call this for
1348	* keys that were created since __key_link_begin() was called.
1349	*/
1350	int __key_link_check_live_key(struct key *keyring, struct key *key)
1351	{
1352	if (key->type == &key_type_keyring)
1353	/* check that we aren't going to create a cycle by linking one
1354	* keyring to another */
1355	return keyring_detect_cycle(A: keyring, B: key);
1356	return 0;
1357	}
1358
1359	/*
1360	* Link a key into to a keyring.
1361	*
1362	* Must be called with __key_link_begin() having being called. Discards any
1363	* already extant link to matching key if there is one, so that each keyring
1364	* holds at most one link to any given key of a particular type+description
1365	* combination.
1366	*/
1367	void __key_link(struct key *keyring, struct key *key,
1368	struct assoc_array_edit **_edit)
1369	{
1370	__key_get(key);
1371	assoc_array_insert_set_object(edit: *_edit, object: keyring_key_to_ptr(key));
1372	assoc_array_apply_edit(edit: *_edit);
1373	*_edit = NULL;
1374	notify_key(key: keyring, subtype: NOTIFY_KEY_LINKED, aux: key_serial(key));
1375	}
1376
1377	/*
1378	* Finish linking a key into to a keyring.
1379	*
1380	* Must be called with __key_link_begin() having being called.
1381	*/
1382	void __key_link_end(struct key *keyring,
1383	const struct keyring_index_key *index_key,
1384	struct assoc_array_edit *edit)
1385	__releases(&keyring->sem)
1386	__releases(&keyring_serialise_link_lock)
1387	{
1388	BUG_ON(index_key->type == NULL);
1389	kenter("%d,%s,", keyring->serial, index_key->type->name);
1390
1391	if (edit) {
1392	if (!edit->dead_leaf) {
1393	key_payload_reserve(key: keyring,
1394	datalen: keyring->datalen - KEYQUOTA_LINK_BYTES);
1395	}
1396	assoc_array_cancel_edit(edit);
1397	}
1398	up_write(sem: &keyring->sem);
1399
1400	if (index_key->type == &key_type_keyring)
1401	mutex_unlock(lock: &keyring_serialise_link_lock);
1402	}
1403
1404	/*
1405	* Check addition of keys to restricted keyrings.
1406	*/
1407	static int __key_link_check_restriction(struct key *keyring, struct key *key)
1408	{
1409	if (!keyring->restrict_link || !keyring->restrict_link->check)
1410	return 0;
1411	return keyring->restrict_link->check(keyring, key->type, &key->payload,
1412	keyring->restrict_link->key);
1413	}
1414
1415	/**
1416	* key_link - Link a key to a keyring
1417	* @keyring: The keyring to make the link in.
1418	* @key: The key to link to.
1419	*
1420	* Make a link in a keyring to a key, such that the keyring holds a reference
1421	* on that key and the key can potentially be found by searching that keyring.
1422	*
1423	* This function will write-lock the keyring's semaphore and will consume some
1424	* of the user's key data quota to hold the link.
1425	*
1426	* Returns 0 if successful, -ENOTDIR if the keyring isn't a keyring,
1427	* -EKEYREVOKED if the keyring has been revoked, -ENFILE if the keyring is
1428	* full, -EDQUOT if there is insufficient key data quota remaining to add
1429	* another link or -ENOMEM if there's insufficient memory.
1430	*
1431	* It is assumed that the caller has checked that it is permitted for a link to
1432	* be made (the keyring should have Write permission and the key Link
1433	* permission).
1434	*/
1435	int key_link(struct key *keyring, struct key *key)
1436	{
1437	struct assoc_array_edit *edit = NULL;
1438	int ret;
1439
1440	kenter("{%d,%d}", keyring->serial, refcount_read(&keyring->usage));
1441
1442	key_check(keyring);
1443	key_check(key);
1444
1445	ret = __key_link_lock(keyring, index_key: &key->index_key);
1446	if (ret < 0)
1447	goto error;
1448
1449	ret = __key_link_begin(keyring, index_key: &key->index_key, edit: &edit);
1450	if (ret < 0)
1451	goto error_end;
1452
1453	kdebug("begun {%d,%d}", keyring->serial, refcount_read(&keyring->usage));
1454	ret = __key_link_check_restriction(keyring, key);
1455	if (ret == 0)
1456	ret = __key_link_check_live_key(keyring, key);
1457	if (ret == 0)
1458	__key_link(keyring, key, edit: &edit);
1459
1460	error_end:
1461	__key_link_end(keyring, index_key: &key->index_key, edit);
1462	error:
1463	kleave(" = %d {%d,%d}", ret, keyring->serial, refcount_read(&keyring->usage));
1464	return ret;
1465	}
1466	EXPORT_SYMBOL(key_link);
1467
1468	/*
1469	* Lock a keyring for unlink.
1470	*/
1471	static int __key_unlink_lock(struct key *keyring)
1472	__acquires(&keyring->sem)
1473	{
1474	if (keyring->type != &key_type_keyring)
1475	return -ENOTDIR;
1476
1477	down_write(sem: &keyring->sem);
1478	return 0;
1479	}
1480
1481	/*
1482	* Begin the process of unlinking a key from a keyring.
1483	*/
1484	static int __key_unlink_begin(struct key *keyring, struct key *key,
1485	struct assoc_array_edit **_edit)
1486	{
1487	struct assoc_array_edit *edit;
1488
1489	BUG_ON(*_edit != NULL);
1490
1491	edit = assoc_array_delete(array: &keyring->keys, ops: &keyring_assoc_array_ops,
1492	index_key: &key->index_key);
1493	if (IS_ERR(ptr: edit))
1494	return PTR_ERR(ptr: edit);
1495
1496	if (!edit)
1497	return -ENOENT;
1498
1499	*_edit = edit;
1500	return 0;
1501	}
1502
1503	/*
1504	* Apply an unlink change.
1505	*/
1506	static void __key_unlink(struct key *keyring, struct key *key,
1507	struct assoc_array_edit **_edit)
1508	{
1509	assoc_array_apply_edit(edit: *_edit);
1510	notify_key(key: keyring, subtype: NOTIFY_KEY_UNLINKED, aux: key_serial(key));
1511	*_edit = NULL;
1512	key_payload_reserve(key: keyring, datalen: keyring->datalen - KEYQUOTA_LINK_BYTES);
1513	}
1514
1515	/*
1516	* Finish unlinking a key from to a keyring.
1517	*/
1518	static void __key_unlink_end(struct key *keyring,
1519	struct key *key,
1520	struct assoc_array_edit *edit)
1521	__releases(&keyring->sem)
1522	{
1523	if (edit)
1524	assoc_array_cancel_edit(edit);
1525	up_write(sem: &keyring->sem);
1526	}
1527
1528	/**
1529	* key_unlink - Unlink the first link to a key from a keyring.
1530	* @keyring: The keyring to remove the link from.
1531	* @key: The key the link is to.
1532	*
1533	* Remove a link from a keyring to a key.
1534	*
1535	* This function will write-lock the keyring's semaphore.
1536	*
1537	* Returns 0 if successful, -ENOTDIR if the keyring isn't a keyring, -ENOENT if
1538	* the key isn't linked to by the keyring or -ENOMEM if there's insufficient
1539	* memory.
1540	*
1541	* It is assumed that the caller has checked that it is permitted for a link to
1542	* be removed (the keyring should have Write permission; no permissions are
1543	* required on the key).
1544	*/
1545	int key_unlink(struct key *keyring, struct key *key)
1546	{
1547	struct assoc_array_edit *edit = NULL;
1548	int ret;
1549
1550	key_check(keyring);
1551	key_check(key);
1552
1553	ret = __key_unlink_lock(keyring);
1554	if (ret < 0)
1555	return ret;
1556
1557	ret = __key_unlink_begin(keyring, key, edit: &edit);
1558	if (ret == 0)
1559	__key_unlink(keyring, key, edit: &edit);
1560	__key_unlink_end(keyring, key, edit);
1561	return ret;
1562	}
1563	EXPORT_SYMBOL(key_unlink);
1564
1565	/**
1566	* key_move - Move a key from one keyring to another
1567	* @key: The key to move
1568	* @from_keyring: The keyring to remove the link from.
1569	* @to_keyring: The keyring to make the link in.
1570	* @flags: Qualifying flags, such as KEYCTL_MOVE_EXCL.
1571	*
1572	* Make a link in @to_keyring to a key, such that the keyring holds a reference
1573	* on that key and the key can potentially be found by searching that keyring
1574	* whilst simultaneously removing a link to the key from @from_keyring.
1575	*
1576	* This function will write-lock both keyring's semaphores and will consume
1577	* some of the user's key data quota to hold the link on @to_keyring.
1578	*
1579	* Returns 0 if successful, -ENOTDIR if either keyring isn't a keyring,
1580	* -EKEYREVOKED if either keyring has been revoked, -ENFILE if the second
1581	* keyring is full, -EDQUOT if there is insufficient key data quota remaining
1582	* to add another link or -ENOMEM if there's insufficient memory. If
1583	* KEYCTL_MOVE_EXCL is set, then -EEXIST will be returned if there's already a
1584	* matching key in @to_keyring.
1585	*
1586	* It is assumed that the caller has checked that it is permitted for a link to
1587	* be made (the keyring should have Write permission and the key Link
1588	* permission).
1589	*/
1590	int key_move(struct key *key,
1591	struct key *from_keyring,
1592	struct key *to_keyring,
1593	unsigned int flags)
1594	{
1595	struct assoc_array_edit *from_edit = NULL, *to_edit = NULL;
1596	int ret;
1597
1598	kenter("%d,%d,%d", key->serial, from_keyring->serial, to_keyring->serial);
1599
1600	if (from_keyring == to_keyring)
1601	return 0;
1602
1603	key_check(key);
1604	key_check(from_keyring);
1605	key_check(to_keyring);
1606
1607	ret = __key_move_lock(l_keyring: from_keyring, u_keyring: to_keyring, index_key: &key->index_key);
1608	if (ret < 0)
1609	goto out;
1610	ret = __key_unlink_begin(keyring: from_keyring, key, edit: &from_edit);
1611	if (ret < 0)
1612	goto error;
1613	ret = __key_link_begin(keyring: to_keyring, index_key: &key->index_key, edit: &to_edit);
1614	if (ret < 0)
1615	goto error;
1616
1617	ret = -EEXIST;
1618	if (to_edit->dead_leaf && (flags & KEYCTL_MOVE_EXCL))
1619	goto error;
1620
1621	ret = __key_link_check_restriction(keyring: to_keyring, key);
1622	if (ret < 0)
1623	goto error;
1624	ret = __key_link_check_live_key(keyring: to_keyring, key);
1625	if (ret < 0)
1626	goto error;
1627
1628	__key_unlink(keyring: from_keyring, key, edit: &from_edit);
1629	__key_link(keyring: to_keyring, key, edit: &to_edit);
1630	error:
1631	__key_link_end(keyring: to_keyring, index_key: &key->index_key, edit: to_edit);
1632	__key_unlink_end(keyring: from_keyring, key, edit: from_edit);
1633	out:
1634	kleave(" = %d", ret);
1635	return ret;
1636	}
1637	EXPORT_SYMBOL(key_move);
1638
1639	/**
1640	* keyring_clear - Clear a keyring
1641	* @keyring: The keyring to clear.
1642	*
1643	* Clear the contents of the specified keyring.
1644	*
1645	* Returns 0 if successful or -ENOTDIR if the keyring isn't a keyring.
1646	*/
1647	int keyring_clear(struct key *keyring)
1648	{
1649	struct assoc_array_edit *edit;
1650	int ret;
1651
1652	if (keyring->type != &key_type_keyring)
1653	return -ENOTDIR;
1654
1655	down_write(sem: &keyring->sem);
1656
1657	edit = assoc_array_clear(array: &keyring->keys, ops: &keyring_assoc_array_ops);
1658	if (IS_ERR(ptr: edit)) {
1659	ret = PTR_ERR(ptr: edit);
1660	} else {
1661	if (edit)
1662	assoc_array_apply_edit(edit);
1663	notify_key(key: keyring, subtype: NOTIFY_KEY_CLEARED, aux: 0);
1664	key_payload_reserve(key: keyring, datalen: 0);
1665	ret = 0;
1666	}
1667
1668	up_write(sem: &keyring->sem);
1669	return ret;
1670	}
1671	EXPORT_SYMBOL(keyring_clear);
1672
1673	/*
1674	* Dispose of the links from a revoked keyring.
1675	*
1676	* This is called with the key sem write-locked.
1677	*/
1678	static void keyring_revoke(struct key *keyring)
1679	{
1680	struct assoc_array_edit *edit;
1681
1682	edit = assoc_array_clear(array: &keyring->keys, ops: &keyring_assoc_array_ops);
1683	if (!IS_ERR(ptr: edit)) {
1684	if (edit)
1685	assoc_array_apply_edit(edit);
1686	key_payload_reserve(key: keyring, datalen: 0);
1687	}
1688	}
1689
1690	static bool keyring_gc_select_iterator(void *object, void *iterator_data)
1691	{
1692	struct key *key = keyring_ptr_to_key(x: object);
1693	time64_t *limit = iterator_data;
1694
1695	if (key_is_dead(key, limit: *limit))
1696	return false;
1697	key_get(key);
1698	return true;
1699	}
1700
1701	static int keyring_gc_check_iterator(const void *object, void *iterator_data)
1702	{
1703	const struct key *key = keyring_ptr_to_key(x: object);
1704	time64_t *limit = iterator_data;
1705
1706	key_check(key);
1707	return key_is_dead(key, limit: *limit);
1708	}
1709
1710	/*
1711	* Garbage collect pointers from a keyring.
1712	*
1713	* Not called with any locks held. The keyring's key struct will not be
1714	* deallocated under us as only our caller may deallocate it.
1715	*/
1716	void keyring_gc(struct key *keyring, time64_t limit)
1717	{
1718	int result;
1719
1720	kenter("%x{%s}", keyring->serial, keyring->description ?: "");
1721
1722	if (keyring->flags & ((1 << KEY_FLAG_INVALIDATED) |
1723	(1 << KEY_FLAG_REVOKED)))
1724	goto dont_gc;
1725
1726	/* scan the keyring looking for dead keys */
1727	rcu_read_lock();
1728	result = assoc_array_iterate(array: &keyring->keys,
1729	iterator: keyring_gc_check_iterator, iterator_data: &limit);
1730	rcu_read_unlock();
1731	if (result == true)
1732	goto do_gc;
1733
1734	dont_gc:
1735	kleave(" [no gc]");
1736	return;
1737
1738	do_gc:
1739	down_write(sem: &keyring->sem);
1740	assoc_array_gc(array: &keyring->keys, ops: &keyring_assoc_array_ops,
1741	iterator: keyring_gc_select_iterator, iterator_data: &limit);
1742	up_write(sem: &keyring->sem);
1743	kleave(" [gc]");
1744	}
1745
1746	/*
1747	* Garbage collect restriction pointers from a keyring.
1748	*
1749	* Keyring restrictions are associated with a key type, and must be cleaned
1750	* up if the key type is unregistered. The restriction is altered to always
1751	* reject additional keys so a keyring cannot be opened up by unregistering
1752	* a key type.
1753	*
1754	* Not called with any keyring locks held. The keyring's key struct will not
1755	* be deallocated under us as only our caller may deallocate it.
1756	*
1757	* The caller is required to hold key_types_sem and dead_type->sem. This is
1758	* fulfilled by key_gc_keytype() holding the locks on behalf of
1759	* key_garbage_collector(), which it invokes on a workqueue.
1760	*/
1761	void keyring_restriction_gc(struct key *keyring, struct key_type *dead_type)
1762	{
1763	struct key_restriction *keyres;
1764
1765	kenter("%x{%s}", keyring->serial, keyring->description ?: "");
1766
1767	/*
1768	* keyring->restrict_link is only assigned at key allocation time
1769	* or with the key type locked, so the only values that could be
1770	* concurrently assigned to keyring->restrict_link are for key
1771	* types other than dead_type. Given this, it's ok to check
1772	* the key type before acquiring keyring->sem.
1773	*/
1774	if (!dead_type || !keyring->restrict_link ||
1775	keyring->restrict_link->keytype != dead_type) {
1776	kleave(" [no restriction gc]");
1777	return;
1778	}
1779
1780	/* Lock the keyring to ensure that a link is not in progress */
1781	down_write(sem: &keyring->sem);
1782
1783	keyres = keyring->restrict_link;
1784
1785	keyres->check = restrict_link_reject;
1786
1787	key_put(key: keyres->key);
1788	keyres->key = NULL;
1789	keyres->keytype = NULL;
1790
1791	up_write(sem: &keyring->sem);
1792
1793	kleave(" [restriction gc]");
1794	}
1795