3 * Copyright (C) 2004-2005, 2008 Red Hat, Inc. All Rights Reserved.
4 * Written by David Howells (dhowells@redhat.com)
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.
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 <asm/uaccess.h>
23 #define rcu_dereference_locked_keyring(keyring) \
24 (rcu_dereference_protected( \
25 (keyring)->payload.subscriptions, \
26 rwsem_is_locked((struct rw_semaphore *)&(keyring)->sem)))
29 * when plumbing the depths of the key tree, this sets a hard limit set on how
30 * deep we're willing to go
32 #define KEYRING_SEARCH_MAX_DEPTH 6
35 * we keep all named keyrings in a hash to speed looking them up
37 #define KEYRING_NAME_HASH_SIZE (1 << 5)
39 static struct list_head keyring_name_hash[KEYRING_NAME_HASH_SIZE];
40 static DEFINE_RWLOCK(keyring_name_lock);
42 static inline unsigned keyring_hash(const char *desc)
47 bucket += (unsigned char) *desc;
49 return bucket & (KEYRING_NAME_HASH_SIZE - 1);
53 * the keyring type definition
55 static int keyring_instantiate(struct key *keyring,
56 const void *data, size_t datalen);
57 static int keyring_match(const struct key *keyring, const void *criterion);
58 static void keyring_revoke(struct key *keyring);
59 static void keyring_destroy(struct key *keyring);
60 static void keyring_describe(const struct key *keyring, struct seq_file *m);
61 static long keyring_read(const struct key *keyring,
62 char __user *buffer, size_t buflen);
64 struct key_type key_type_keyring = {
66 .def_datalen = sizeof(struct keyring_list),
67 .instantiate = keyring_instantiate,
68 .match = keyring_match,
69 .revoke = keyring_revoke,
70 .destroy = keyring_destroy,
71 .describe = keyring_describe,
75 EXPORT_SYMBOL(key_type_keyring);
78 * semaphore to serialise link/link calls to prevent two link calls in parallel
81 static DECLARE_RWSEM(keyring_serialise_link_sem);
83 /*****************************************************************************/
85 * publish the name of a keyring so that it can be found by name (if it has
88 static void keyring_publish_name(struct key *keyring)
92 if (keyring->description) {
93 bucket = keyring_hash(keyring->description);
95 write_lock(&keyring_name_lock);
97 if (!keyring_name_hash[bucket].next)
98 INIT_LIST_HEAD(&keyring_name_hash[bucket]);
100 list_add_tail(&keyring->type_data.link,
101 &keyring_name_hash[bucket]);
103 write_unlock(&keyring_name_lock);
106 } /* end keyring_publish_name() */
108 /*****************************************************************************/
110 * initialise a keyring
111 * - we object if we were given any data
113 static int keyring_instantiate(struct key *keyring,
114 const void *data, size_t datalen)
120 /* make the keyring available by name if it has one */
121 keyring_publish_name(keyring);
127 } /* end keyring_instantiate() */
129 /*****************************************************************************/
131 * match keyrings on their name
133 static int keyring_match(const struct key *keyring, const void *description)
135 return keyring->description &&
136 strcmp(keyring->description, description) == 0;
138 } /* end keyring_match() */
140 /*****************************************************************************/
142 * dispose of the data dangling from the corpse of a keyring
144 static void keyring_destroy(struct key *keyring)
146 struct keyring_list *klist;
149 if (keyring->description) {
150 write_lock(&keyring_name_lock);
152 if (keyring->type_data.link.next != NULL &&
153 !list_empty(&keyring->type_data.link))
154 list_del(&keyring->type_data.link);
156 write_unlock(&keyring_name_lock);
159 klist = rcu_dereference_check(keyring->payload.subscriptions,
160 rcu_read_lock_held() ||
161 atomic_read(&keyring->usage) == 0);
163 for (loop = klist->nkeys - 1; loop >= 0; loop--)
164 key_put(klist->keys[loop]);
168 } /* end keyring_destroy() */
170 /*****************************************************************************/
172 * describe the keyring
174 static void keyring_describe(const struct key *keyring, struct seq_file *m)
176 struct keyring_list *klist;
178 if (keyring->description) {
179 seq_puts(m, keyring->description);
182 seq_puts(m, "[anon]");
186 klist = rcu_dereference(keyring->payload.subscriptions);
188 seq_printf(m, ": %u/%u", klist->nkeys, klist->maxkeys);
190 seq_puts(m, ": empty");
193 } /* end keyring_describe() */
195 /*****************************************************************************/
197 * read a list of key IDs from the keyring's contents
198 * - the keyring's semaphore is read-locked
200 static long keyring_read(const struct key *keyring,
201 char __user *buffer, size_t buflen)
203 struct keyring_list *klist;
209 klist = rcu_dereference_locked_keyring(keyring);
211 /* calculate how much data we could return */
212 qty = klist->nkeys * sizeof(key_serial_t);
214 if (buffer && buflen > 0) {
218 /* copy the IDs of the subscribed keys into the
222 for (loop = 0; loop < klist->nkeys; loop++) {
223 key = klist->keys[loop];
225 tmp = sizeof(key_serial_t);
229 if (copy_to_user(buffer,
247 } /* end keyring_read() */
249 /*****************************************************************************/
251 * allocate a keyring and link into the destination keyring
253 struct key *keyring_alloc(const char *description, uid_t uid, gid_t gid,
254 const struct cred *cred, unsigned long flags,
260 keyring = key_alloc(&key_type_keyring, description,
262 (KEY_POS_ALL & ~KEY_POS_SETATTR) | KEY_USR_ALL,
265 if (!IS_ERR(keyring)) {
266 ret = key_instantiate_and_link(keyring, NULL, 0, dest, NULL);
269 keyring = ERR_PTR(ret);
275 } /* end keyring_alloc() */
277 /*****************************************************************************/
279 * search the supplied keyring tree for a key that matches the criterion
280 * - perform a breadth-then-depth search up to the prescribed limit
281 * - we only find keys on which we have search permission
282 * - we use the supplied match function to see if the description (or other
283 * feature of interest) matches
284 * - we rely on RCU to prevent the keyring lists from disappearing on us
285 * - we return -EAGAIN if we didn't find any matching key
286 * - we return -ENOKEY if we only found negative matching keys
287 * - we propagate the possession attribute from the keyring ref to the key ref
289 key_ref_t keyring_search_aux(key_ref_t keyring_ref,
290 const struct cred *cred,
291 struct key_type *type,
292 const void *description,
293 key_match_func_t match)
296 struct keyring_list *keylist;
298 } stack[KEYRING_SEARCH_MAX_DEPTH];
300 struct keyring_list *keylist;
302 unsigned long possessed, kflags;
303 struct key *keyring, *key;
308 keyring = key_ref_to_ptr(keyring_ref);
309 possessed = is_key_possessed(keyring_ref);
312 /* top keyring must have search permission to begin the search */
313 err = key_task_permission(keyring_ref, cred, KEY_SEARCH);
315 key_ref = ERR_PTR(err);
319 key_ref = ERR_PTR(-ENOTDIR);
320 if (keyring->type != &key_type_keyring)
325 now = current_kernel_time();
329 /* firstly we should check to see if this top-level keyring is what we
331 key_ref = ERR_PTR(-EAGAIN);
332 kflags = keyring->flags;
333 if (keyring->type == type && match(keyring, description)) {
336 /* check it isn't negative and hasn't expired or been
338 if (kflags & (1 << KEY_FLAG_REVOKED))
340 if (key->expiry && now.tv_sec >= key->expiry)
342 key_ref = ERR_PTR(-ENOKEY);
343 if (kflags & (1 << KEY_FLAG_NEGATIVE))
348 /* otherwise, the top keyring must not be revoked, expired, or
349 * negatively instantiated if we are to search it */
350 key_ref = ERR_PTR(-EAGAIN);
351 if (kflags & ((1 << KEY_FLAG_REVOKED) | (1 << KEY_FLAG_NEGATIVE)) ||
352 (keyring->expiry && now.tv_sec >= keyring->expiry))
355 /* start processing a new keyring */
357 if (test_bit(KEY_FLAG_REVOKED, &keyring->flags))
358 goto not_this_keyring;
360 keylist = rcu_dereference(keyring->payload.subscriptions);
362 goto not_this_keyring;
364 /* iterate through the keys in this keyring first */
365 for (kix = 0; kix < keylist->nkeys; kix++) {
366 key = keylist->keys[kix];
369 /* ignore keys not of this type */
370 if (key->type != type)
373 /* skip revoked keys and expired keys */
374 if (kflags & (1 << KEY_FLAG_REVOKED))
377 if (key->expiry && now.tv_sec >= key->expiry)
380 /* keys that don't match */
381 if (!match(key, description))
384 /* key must have search permissions */
385 if (key_task_permission(make_key_ref(key, possessed),
386 cred, KEY_SEARCH) < 0)
389 /* we set a different error code if we pass a negative key */
390 if (kflags & (1 << KEY_FLAG_NEGATIVE)) {
398 /* search through the keyrings nested in this one */
401 for (; kix < keylist->nkeys; kix++) {
402 key = keylist->keys[kix];
403 if (key->type != &key_type_keyring)
406 /* recursively search nested keyrings
407 * - only search keyrings for which we have search permission
409 if (sp >= KEYRING_SEARCH_MAX_DEPTH)
412 if (key_task_permission(make_key_ref(key, possessed),
413 cred, KEY_SEARCH) < 0)
416 /* stack the current position */
417 stack[sp].keylist = keylist;
421 /* begin again with the new keyring */
426 /* the keyring we're looking at was disqualified or didn't contain a
430 /* resume the processing of a keyring higher up in the tree */
432 keylist = stack[sp].keylist;
433 kix = stack[sp].kix + 1;
437 key_ref = ERR_PTR(err);
440 /* we found a viable match */
442 atomic_inc(&key->usage);
444 key_ref = make_key_ref(key, possessed);
450 } /* end keyring_search_aux() */
452 /*****************************************************************************/
454 * search the supplied keyring tree for a key that matches the criterion
455 * - perform a breadth-then-depth search up to the prescribed limit
456 * - we only find keys on which we have search permission
457 * - we readlock the keyrings as we search down the tree
458 * - we return -EAGAIN if we didn't find any matching key
459 * - we return -ENOKEY if we only found negative matching keys
461 key_ref_t keyring_search(key_ref_t keyring,
462 struct key_type *type,
463 const char *description)
466 return ERR_PTR(-ENOKEY);
468 return keyring_search_aux(keyring, current->cred,
469 type, description, type->match);
471 } /* end keyring_search() */
473 EXPORT_SYMBOL(keyring_search);
475 /*****************************************************************************/
477 * search the given keyring only (no recursion)
478 * - keyring must be locked by caller
479 * - caller must guarantee that the keyring is a keyring
481 key_ref_t __keyring_search_one(key_ref_t keyring_ref,
482 const struct key_type *ktype,
483 const char *description,
486 struct keyring_list *klist;
487 unsigned long possessed;
488 struct key *keyring, *key;
491 keyring = key_ref_to_ptr(keyring_ref);
492 possessed = is_key_possessed(keyring_ref);
496 klist = rcu_dereference(keyring->payload.subscriptions);
498 for (loop = 0; loop < klist->nkeys; loop++) {
499 key = klist->keys[loop];
501 if (key->type == ktype &&
502 (!key->type->match ||
503 key->type->match(key, description)) &&
504 key_permission(make_key_ref(key, possessed),
506 !test_bit(KEY_FLAG_REVOKED, &key->flags)
513 return ERR_PTR(-ENOKEY);
516 atomic_inc(&key->usage);
518 return make_key_ref(key, possessed);
520 } /* end __keyring_search_one() */
522 /*****************************************************************************/
524 * find a keyring with the specified name
525 * - all named keyrings are searched
526 * - normally only finds keyrings with search permission for the current process
528 struct key *find_keyring_by_name(const char *name, bool skip_perm_check)
534 return ERR_PTR(-EINVAL);
536 bucket = keyring_hash(name);
538 read_lock(&keyring_name_lock);
540 if (keyring_name_hash[bucket].next) {
541 /* search this hash bucket for a keyring with a matching name
542 * that's readable and that hasn't been revoked */
543 list_for_each_entry(keyring,
544 &keyring_name_hash[bucket],
547 if (keyring->user->user_ns != current_user_ns())
550 if (test_bit(KEY_FLAG_REVOKED, &keyring->flags))
553 if (strcmp(keyring->description, name) != 0)
556 if (!skip_perm_check &&
557 key_permission(make_key_ref(keyring, 0),
561 /* we've got a match but we might end up racing with
562 * key_cleanup() if the keyring is currently 'dead'
563 * (ie. it has a zero usage count) */
564 if (!atomic_inc_not_zero(&keyring->usage))
570 keyring = ERR_PTR(-ENOKEY);
572 read_unlock(&keyring_name_lock);
575 } /* end find_keyring_by_name() */
577 /*****************************************************************************/
579 * see if a cycle will will be created by inserting acyclic tree B in acyclic
580 * tree A at the topmost level (ie: as a direct child of A)
581 * - since we are adding B to A at the top level, checking for cycles should
582 * just be a matter of seeing if node A is somewhere in tree B
584 static int keyring_detect_cycle(struct key *A, struct key *B)
587 struct keyring_list *keylist;
589 } stack[KEYRING_SEARCH_MAX_DEPTH];
591 struct keyring_list *keylist;
592 struct key *subtree, *key;
604 /* start processing a new keyring */
606 if (test_bit(KEY_FLAG_REVOKED, &subtree->flags))
607 goto not_this_keyring;
609 keylist = rcu_dereference(subtree->payload.subscriptions);
611 goto not_this_keyring;
615 /* iterate through the remaining keys in this keyring */
616 for (; kix < keylist->nkeys; kix++) {
617 key = keylist->keys[kix];
622 /* recursively check nested keyrings */
623 if (key->type == &key_type_keyring) {
624 if (sp >= KEYRING_SEARCH_MAX_DEPTH)
627 /* stack the current position */
628 stack[sp].keylist = keylist;
632 /* begin again with the new keyring */
638 /* the keyring we're looking at was disqualified or didn't contain a
642 /* resume the checking of a keyring higher up in the tree */
644 keylist = stack[sp].keylist;
645 kix = stack[sp].kix + 1;
649 ret = 0; /* no cycles detected */
663 } /* end keyring_detect_cycle() */
665 /*****************************************************************************/
667 * dispose of a keyring list after the RCU grace period
669 static void keyring_link_rcu_disposal(struct rcu_head *rcu)
671 struct keyring_list *klist =
672 container_of(rcu, struct keyring_list, rcu);
676 } /* end keyring_link_rcu_disposal() */
678 /*****************************************************************************/
680 * dispose of a keyring list after the RCU grace period, freeing the unlinked
683 static void keyring_unlink_rcu_disposal(struct rcu_head *rcu)
685 struct keyring_list *klist =
686 container_of(rcu, struct keyring_list, rcu);
688 key_put(klist->keys[klist->delkey]);
691 } /* end keyring_unlink_rcu_disposal() */
693 /*****************************************************************************/
695 * link a key into to a keyring
696 * - must be called with the keyring's semaphore write-locked
697 * - discard already extant link to matching key if there is one
699 int __key_link(struct key *keyring, struct key *key)
701 struct keyring_list *klist, *nklist;
707 if (test_bit(KEY_FLAG_REVOKED, &keyring->flags))
711 if (keyring->type != &key_type_keyring)
714 /* serialise link/link calls to prevent parallel calls causing a
715 * cycle when applied to two keyring in opposite orders */
716 down_write(&keyring_serialise_link_sem);
718 /* check that we aren't going to create a cycle adding one keyring to
720 if (key->type == &key_type_keyring) {
721 ret = keyring_detect_cycle(keyring, key);
726 /* see if there's a matching key we can displace */
727 klist = rcu_dereference_locked_keyring(keyring);
728 if (klist && klist->nkeys > 0) {
729 struct key_type *type = key->type;
731 for (loop = klist->nkeys - 1; loop >= 0; loop--) {
732 if (klist->keys[loop]->type == type &&
733 strcmp(klist->keys[loop]->description,
734 key->description) == 0
736 /* found a match - replace with new key */
737 size = sizeof(struct key *) * klist->maxkeys;
738 size += sizeof(*klist);
739 BUG_ON(size > PAGE_SIZE);
742 nklist = kmemdup(klist, size, GFP_KERNEL);
746 /* replace matched key */
747 atomic_inc(&key->usage);
748 nklist->keys[loop] = key;
751 keyring->payload.subscriptions,
754 /* dispose of the old keyring list and the
756 klist->delkey = loop;
757 call_rcu(&klist->rcu,
758 keyring_unlink_rcu_disposal);
765 /* check that we aren't going to overrun the user's quota */
766 ret = key_payload_reserve(keyring,
767 keyring->datalen + KEYQUOTA_LINK_BYTES);
771 if (klist && klist->nkeys < klist->maxkeys) {
772 /* there's sufficient slack space to add directly */
773 atomic_inc(&key->usage);
775 klist->keys[klist->nkeys] = key;
781 /* grow the key list */
784 max += klist->maxkeys;
789 size = sizeof(*klist) + sizeof(struct key *) * max;
790 if (size > PAGE_SIZE)
794 nklist = kmalloc(size, GFP_KERNEL);
797 nklist->maxkeys = max;
801 nklist->nkeys = klist->nkeys;
804 sizeof(struct key *) * klist->nkeys);
807 /* add the key into the new space */
808 atomic_inc(&key->usage);
809 nklist->keys[nklist->nkeys++] = key;
811 rcu_assign_pointer(keyring->payload.subscriptions, nklist);
813 /* dispose of the old keyring list */
815 call_rcu(&klist->rcu, keyring_link_rcu_disposal);
821 up_write(&keyring_serialise_link_sem);
826 /* undo the quota changes */
827 key_payload_reserve(keyring,
828 keyring->datalen - KEYQUOTA_LINK_BYTES);
831 } /* end __key_link() */
833 /*****************************************************************************/
835 * link a key to a keyring
837 int key_link(struct key *keyring, struct key *key)
844 down_write(&keyring->sem);
845 ret = __key_link(keyring, key);
846 up_write(&keyring->sem);
850 } /* end key_link() */
852 EXPORT_SYMBOL(key_link);
854 /*****************************************************************************/
856 * unlink the first link to a key from a keyring
858 int key_unlink(struct key *keyring, struct key *key)
860 struct keyring_list *klist, *nklist;
867 if (keyring->type != &key_type_keyring)
870 down_write(&keyring->sem);
872 klist = rcu_dereference_locked_keyring(keyring);
874 /* search the keyring for the key */
875 for (loop = 0; loop < klist->nkeys; loop++)
876 if (klist->keys[loop] == key)
880 up_write(&keyring->sem);
885 /* we need to copy the key list for RCU purposes */
886 nklist = kmalloc(sizeof(*klist) +
887 sizeof(struct key *) * klist->maxkeys,
891 nklist->maxkeys = klist->maxkeys;
892 nklist->nkeys = klist->nkeys - 1;
895 memcpy(&nklist->keys[0],
897 loop * sizeof(struct key *));
899 if (loop < nklist->nkeys)
900 memcpy(&nklist->keys[loop],
901 &klist->keys[loop + 1],
902 (nklist->nkeys - loop) * sizeof(struct key *));
904 /* adjust the user's quota */
905 key_payload_reserve(keyring,
906 keyring->datalen - KEYQUOTA_LINK_BYTES);
908 rcu_assign_pointer(keyring->payload.subscriptions, nklist);
910 up_write(&keyring->sem);
912 /* schedule for later cleanup */
913 klist->delkey = loop;
914 call_rcu(&klist->rcu, keyring_unlink_rcu_disposal);
922 up_write(&keyring->sem);
925 } /* end key_unlink() */
927 EXPORT_SYMBOL(key_unlink);
929 /*****************************************************************************/
931 * dispose of a keyring list after the RCU grace period, releasing the keys it
934 static void keyring_clear_rcu_disposal(struct rcu_head *rcu)
936 struct keyring_list *klist;
939 klist = container_of(rcu, struct keyring_list, rcu);
941 for (loop = klist->nkeys - 1; loop >= 0; loop--)
942 key_put(klist->keys[loop]);
946 } /* end keyring_clear_rcu_disposal() */
948 /*****************************************************************************/
950 * clear the specified process keyring
951 * - implements keyctl(KEYCTL_CLEAR)
953 int keyring_clear(struct key *keyring)
955 struct keyring_list *klist;
959 if (keyring->type == &key_type_keyring) {
960 /* detach the pointer block with the locks held */
961 down_write(&keyring->sem);
963 klist = rcu_dereference_locked_keyring(keyring);
965 /* adjust the quota */
966 key_payload_reserve(keyring,
967 sizeof(struct keyring_list));
969 rcu_assign_pointer(keyring->payload.subscriptions,
973 up_write(&keyring->sem);
975 /* free the keys after the locks have been dropped */
977 call_rcu(&klist->rcu, keyring_clear_rcu_disposal);
984 } /* end keyring_clear() */
986 EXPORT_SYMBOL(keyring_clear);
988 /*****************************************************************************/
990 * dispose of the links from a revoked keyring
991 * - called with the key sem write-locked
993 static void keyring_revoke(struct key *keyring)
995 struct keyring_list *klist;
997 klist = rcu_dereference_locked_keyring(keyring);
999 /* adjust the quota */
1000 key_payload_reserve(keyring, 0);
1003 rcu_assign_pointer(keyring->payload.subscriptions, NULL);
1004 call_rcu(&klist->rcu, keyring_clear_rcu_disposal);
1007 } /* end keyring_revoke() */
1010 * Determine whether a key is dead
1012 static bool key_is_dead(struct key *key, time_t limit)
1014 return test_bit(KEY_FLAG_DEAD, &key->flags) ||
1015 (key->expiry > 0 && key->expiry <= limit);
1019 * Collect garbage from the contents of a keyring
1021 void keyring_gc(struct key *keyring, time_t limit)
1023 struct keyring_list *klist, *new;
1025 int loop, keep, max;
1027 kenter("{%x,%s}", key_serial(keyring), keyring->description);
1029 down_write(&keyring->sem);
1031 klist = rcu_dereference_locked_keyring(keyring);
1035 /* work out how many subscriptions we're keeping */
1037 for (loop = klist->nkeys - 1; loop >= 0; loop--)
1038 if (!key_is_dead(klist->keys[loop], limit))
1041 if (keep == klist->nkeys)
1044 /* allocate a new keyring payload */
1045 max = roundup(keep, 4);
1046 new = kmalloc(sizeof(struct keyring_list) + max * sizeof(struct key *),
1054 /* install the live keys
1055 * - must take care as expired keys may be updated back to life
1058 for (loop = klist->nkeys - 1; loop >= 0; loop--) {
1059 key = klist->keys[loop];
1060 if (!key_is_dead(key, limit)) {
1063 new->keys[keep++] = key_get(key);
1068 /* adjust the quota */
1069 key_payload_reserve(keyring,
1070 sizeof(struct keyring_list) +
1071 KEYQUOTA_LINK_BYTES * keep);
1074 rcu_assign_pointer(keyring->payload.subscriptions, NULL);
1077 rcu_assign_pointer(keyring->payload.subscriptions, new);
1080 up_write(&keyring->sem);
1082 call_rcu(&klist->rcu, keyring_clear_rcu_disposal);
1088 keyring_clear_rcu_disposal(&new->rcu);
1089 up_write(&keyring->sem);
1090 kleave(" [discard]");
1094 up_write(&keyring->sem);
1095 kleave(" [no dead]");
1099 up_write(&keyring->sem);
1100 kleave(" [no_klist]");
1104 up_write(&keyring->sem);