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 <linux/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);
84 * publish the name of a keyring so that it can be found by name (if it has
87 static void keyring_publish_name(struct key *keyring)
91 if (keyring->description) {
92 bucket = keyring_hash(keyring->description);
94 write_lock(&keyring_name_lock);
96 if (!keyring_name_hash[bucket].next)
97 INIT_LIST_HEAD(&keyring_name_hash[bucket]);
99 list_add_tail(&keyring->type_data.link,
100 &keyring_name_hash[bucket]);
102 write_unlock(&keyring_name_lock);
107 * initialise a keyring
108 * - we object if we were given any data
110 static int keyring_instantiate(struct key *keyring,
111 const void *data, size_t datalen)
117 /* make the keyring available by name if it has one */
118 keyring_publish_name(keyring);
126 * match keyrings on their name
128 static int keyring_match(const struct key *keyring, const void *description)
130 return keyring->description &&
131 strcmp(keyring->description, description) == 0;
135 * dispose of the data dangling from the corpse of a keyring
137 static void keyring_destroy(struct key *keyring)
139 struct keyring_list *klist;
142 if (keyring->description) {
143 write_lock(&keyring_name_lock);
145 if (keyring->type_data.link.next != NULL &&
146 !list_empty(&keyring->type_data.link))
147 list_del(&keyring->type_data.link);
149 write_unlock(&keyring_name_lock);
152 klist = rcu_dereference_check(keyring->payload.subscriptions,
153 rcu_read_lock_held() ||
154 atomic_read(&keyring->usage) == 0);
156 for (loop = klist->nkeys - 1; loop >= 0; loop--)
157 key_put(klist->keys[loop]);
163 * describe the keyring
165 static void keyring_describe(const struct key *keyring, struct seq_file *m)
167 struct keyring_list *klist;
169 if (keyring->description)
170 seq_puts(m, keyring->description);
172 seq_puts(m, "[anon]");
175 klist = rcu_dereference(keyring->payload.subscriptions);
177 seq_printf(m, ": %u/%u", klist->nkeys, klist->maxkeys);
179 seq_puts(m, ": empty");
184 * read a list of key IDs from the keyring's contents
185 * - the keyring's semaphore is read-locked
187 static long keyring_read(const struct key *keyring,
188 char __user *buffer, size_t buflen)
190 struct keyring_list *klist;
196 klist = rcu_dereference_locked_keyring(keyring);
198 /* calculate how much data we could return */
199 qty = klist->nkeys * sizeof(key_serial_t);
201 if (buffer && buflen > 0) {
205 /* copy the IDs of the subscribed keys into the
209 for (loop = 0; loop < klist->nkeys; loop++) {
210 key = klist->keys[loop];
212 tmp = sizeof(key_serial_t);
216 if (copy_to_user(buffer,
236 * allocate a keyring and link into the destination keyring
238 struct key *keyring_alloc(const char *description, uid_t uid, gid_t gid,
239 const struct cred *cred, unsigned long flags,
245 keyring = key_alloc(&key_type_keyring, description,
247 (KEY_POS_ALL & ~KEY_POS_SETATTR) | KEY_USR_ALL,
250 if (!IS_ERR(keyring)) {
251 ret = key_instantiate_and_link(keyring, NULL, 0, dest, NULL);
254 keyring = ERR_PTR(ret);
262 * search the supplied keyring tree for a key that matches the criterion
263 * - perform a breadth-then-depth search up to the prescribed limit
264 * - we only find keys on which we have search permission
265 * - we use the supplied match function to see if the description (or other
266 * feature of interest) matches
267 * - we rely on RCU to prevent the keyring lists from disappearing on us
268 * - we return -EAGAIN if we didn't find any matching key
269 * - we return -ENOKEY if we only found negative matching keys
270 * - we propagate the possession attribute from the keyring ref to the key ref
272 key_ref_t keyring_search_aux(key_ref_t keyring_ref,
273 const struct cred *cred,
274 struct key_type *type,
275 const void *description,
276 key_match_func_t match)
279 struct keyring_list *keylist;
281 } stack[KEYRING_SEARCH_MAX_DEPTH];
283 struct keyring_list *keylist;
285 unsigned long possessed, kflags;
286 struct key *keyring, *key;
291 keyring = key_ref_to_ptr(keyring_ref);
292 possessed = is_key_possessed(keyring_ref);
295 /* top keyring must have search permission to begin the search */
296 err = key_task_permission(keyring_ref, cred, KEY_SEARCH);
298 key_ref = ERR_PTR(err);
302 key_ref = ERR_PTR(-ENOTDIR);
303 if (keyring->type != &key_type_keyring)
308 now = current_kernel_time();
312 /* firstly we should check to see if this top-level keyring is what we
314 key_ref = ERR_PTR(-EAGAIN);
315 kflags = keyring->flags;
316 if (keyring->type == type && match(keyring, description)) {
319 /* check it isn't negative and hasn't expired or been
321 if (kflags & (1 << KEY_FLAG_REVOKED))
323 if (key->expiry && now.tv_sec >= key->expiry)
325 key_ref = ERR_PTR(-ENOKEY);
326 if (kflags & (1 << KEY_FLAG_NEGATIVE))
331 /* otherwise, the top keyring must not be revoked, expired, or
332 * negatively instantiated if we are to search it */
333 key_ref = ERR_PTR(-EAGAIN);
334 if (kflags & ((1 << KEY_FLAG_REVOKED) | (1 << KEY_FLAG_NEGATIVE)) ||
335 (keyring->expiry && now.tv_sec >= keyring->expiry))
338 /* start processing a new keyring */
340 if (test_bit(KEY_FLAG_REVOKED, &keyring->flags))
341 goto not_this_keyring;
343 keylist = rcu_dereference(keyring->payload.subscriptions);
345 goto not_this_keyring;
347 /* iterate through the keys in this keyring first */
348 for (kix = 0; kix < keylist->nkeys; kix++) {
349 key = keylist->keys[kix];
352 /* ignore keys not of this type */
353 if (key->type != type)
356 /* skip revoked keys and expired keys */
357 if (kflags & (1 << KEY_FLAG_REVOKED))
360 if (key->expiry && now.tv_sec >= key->expiry)
363 /* keys that don't match */
364 if (!match(key, description))
367 /* key must have search permissions */
368 if (key_task_permission(make_key_ref(key, possessed),
369 cred, KEY_SEARCH) < 0)
372 /* we set a different error code if we pass a negative key */
373 if (kflags & (1 << KEY_FLAG_NEGATIVE)) {
381 /* search through the keyrings nested in this one */
384 for (; kix < keylist->nkeys; kix++) {
385 key = keylist->keys[kix];
386 if (key->type != &key_type_keyring)
389 /* recursively search nested keyrings
390 * - only search keyrings for which we have search permission
392 if (sp >= KEYRING_SEARCH_MAX_DEPTH)
395 if (key_task_permission(make_key_ref(key, possessed),
396 cred, KEY_SEARCH) < 0)
399 /* stack the current position */
400 stack[sp].keylist = keylist;
404 /* begin again with the new keyring */
409 /* the keyring we're looking at was disqualified or didn't contain a
413 /* resume the processing of a keyring higher up in the tree */
415 keylist = stack[sp].keylist;
416 kix = stack[sp].kix + 1;
420 key_ref = ERR_PTR(err);
423 /* we found a viable match */
425 atomic_inc(&key->usage);
427 key_ref = make_key_ref(key, possessed);
435 * search the supplied keyring tree for a key that matches the criterion
436 * - perform a breadth-then-depth search up to the prescribed limit
437 * - we only find keys on which we have search permission
438 * - we readlock the keyrings as we search down the tree
439 * - we return -EAGAIN if we didn't find any matching key
440 * - we return -ENOKEY if we only found negative matching keys
442 key_ref_t keyring_search(key_ref_t keyring,
443 struct key_type *type,
444 const char *description)
447 return ERR_PTR(-ENOKEY);
449 return keyring_search_aux(keyring, current->cred,
450 type, description, type->match);
453 EXPORT_SYMBOL(keyring_search);
456 * search the given keyring only (no recursion)
457 * - keyring must be locked by caller
458 * - caller must guarantee that the keyring is a keyring
460 key_ref_t __keyring_search_one(key_ref_t keyring_ref,
461 const struct key_type *ktype,
462 const char *description,
465 struct keyring_list *klist;
466 unsigned long possessed;
467 struct key *keyring, *key;
470 keyring = key_ref_to_ptr(keyring_ref);
471 possessed = is_key_possessed(keyring_ref);
475 klist = rcu_dereference(keyring->payload.subscriptions);
477 for (loop = 0; loop < klist->nkeys; loop++) {
478 key = klist->keys[loop];
480 if (key->type == ktype &&
481 (!key->type->match ||
482 key->type->match(key, description)) &&
483 key_permission(make_key_ref(key, possessed),
485 !test_bit(KEY_FLAG_REVOKED, &key->flags)
492 return ERR_PTR(-ENOKEY);
495 atomic_inc(&key->usage);
497 return make_key_ref(key, possessed);
501 * find a keyring with the specified name
502 * - all named keyrings are searched
503 * - normally only finds keyrings with search permission for the current process
505 struct key *find_keyring_by_name(const char *name, bool skip_perm_check)
511 return ERR_PTR(-EINVAL);
513 bucket = keyring_hash(name);
515 read_lock(&keyring_name_lock);
517 if (keyring_name_hash[bucket].next) {
518 /* search this hash bucket for a keyring with a matching name
519 * that's readable and that hasn't been revoked */
520 list_for_each_entry(keyring,
521 &keyring_name_hash[bucket],
524 if (keyring->user->user_ns != current_user_ns())
527 if (test_bit(KEY_FLAG_REVOKED, &keyring->flags))
530 if (strcmp(keyring->description, name) != 0)
533 if (!skip_perm_check &&
534 key_permission(make_key_ref(keyring, 0),
538 /* we've got a match but we might end up racing with
539 * key_cleanup() if the keyring is currently 'dead'
540 * (ie. it has a zero usage count) */
541 if (!atomic_inc_not_zero(&keyring->usage))
547 keyring = ERR_PTR(-ENOKEY);
549 read_unlock(&keyring_name_lock);
554 * see if a cycle will will be created by inserting acyclic tree B in acyclic
555 * tree A at the topmost level (ie: as a direct child of A)
556 * - since we are adding B to A at the top level, checking for cycles should
557 * just be a matter of seeing if node A is somewhere in tree B
559 static int keyring_detect_cycle(struct key *A, struct key *B)
562 struct keyring_list *keylist;
564 } stack[KEYRING_SEARCH_MAX_DEPTH];
566 struct keyring_list *keylist;
567 struct key *subtree, *key;
579 /* start processing a new keyring */
581 if (test_bit(KEY_FLAG_REVOKED, &subtree->flags))
582 goto not_this_keyring;
584 keylist = rcu_dereference(subtree->payload.subscriptions);
586 goto not_this_keyring;
590 /* iterate through the remaining keys in this keyring */
591 for (; kix < keylist->nkeys; kix++) {
592 key = keylist->keys[kix];
597 /* recursively check nested keyrings */
598 if (key->type == &key_type_keyring) {
599 if (sp >= KEYRING_SEARCH_MAX_DEPTH)
602 /* stack the current position */
603 stack[sp].keylist = keylist;
607 /* begin again with the new keyring */
613 /* the keyring we're looking at was disqualified or didn't contain a
617 /* resume the checking of a keyring higher up in the tree */
619 keylist = stack[sp].keylist;
620 kix = stack[sp].kix + 1;
624 ret = 0; /* no cycles detected */
640 * dispose of a keyring list after the RCU grace period, freeing the unlinked
643 static void keyring_unlink_rcu_disposal(struct rcu_head *rcu)
645 struct keyring_list *klist =
646 container_of(rcu, struct keyring_list, rcu);
648 if (klist->delkey != USHRT_MAX)
649 key_put(klist->keys[klist->delkey]);
654 * preallocate memory so that a key can be linked into to a keyring
656 int __key_link_begin(struct key *keyring, const struct key_type *type,
657 const char *description,
658 struct keyring_list **_prealloc)
659 __acquires(&keyring->sem)
661 struct keyring_list *klist, *nklist;
666 kenter("%d,%s,%s,", key_serial(keyring), type->name, description);
668 if (keyring->type != &key_type_keyring)
671 down_write(&keyring->sem);
674 if (test_bit(KEY_FLAG_REVOKED, &keyring->flags))
677 /* serialise link/link calls to prevent parallel calls causing a cycle
678 * when linking two keyring in opposite orders */
679 if (type == &key_type_keyring)
680 down_write(&keyring_serialise_link_sem);
682 klist = rcu_dereference_locked_keyring(keyring);
684 /* see if there's a matching key we can displace */
685 if (klist && klist->nkeys > 0) {
686 for (loop = klist->nkeys - 1; loop >= 0; loop--) {
687 if (klist->keys[loop]->type == type &&
688 strcmp(klist->keys[loop]->description,
691 /* found a match - we'll replace this one with
693 size = sizeof(struct key *) * klist->maxkeys;
694 size += sizeof(*klist);
695 BUG_ON(size > PAGE_SIZE);
698 nklist = kmemdup(klist, size, GFP_KERNEL);
702 /* note replacement slot */
703 klist->delkey = nklist->delkey = loop;
709 /* check that we aren't going to overrun the user's quota */
710 ret = key_payload_reserve(keyring,
711 keyring->datalen + KEYQUOTA_LINK_BYTES);
715 if (klist && klist->nkeys < klist->maxkeys) {
716 /* there's sufficient slack space to append directly */
719 /* grow the key list */
722 max += klist->maxkeys;
725 if (max > USHRT_MAX - 1)
727 size = sizeof(*klist) + sizeof(struct key *) * max;
728 if (size > PAGE_SIZE)
732 nklist = kmalloc(size, GFP_KERNEL);
736 nklist->maxkeys = max;
738 memcpy(nklist->keys, klist->keys,
739 sizeof(struct key *) * klist->nkeys);
740 nklist->delkey = klist->nkeys;
741 nklist->nkeys = klist->nkeys + 1;
742 klist->delkey = USHRT_MAX;
748 /* add the key into the new space */
749 nklist->keys[nklist->delkey] = NULL;
758 /* undo the quota changes */
759 key_payload_reserve(keyring,
760 keyring->datalen - KEYQUOTA_LINK_BYTES);
762 if (type == &key_type_keyring)
763 up_write(&keyring_serialise_link_sem);
765 up_write(&keyring->sem);
766 kleave(" = %d", ret);
771 * check already instantiated keys aren't going to be a problem
772 * - the caller must have called __key_link_begin()
773 * - don't need to call this for keys that were created since __key_link_begin()
776 int __key_link_check_live_key(struct key *keyring, struct key *key)
778 if (key->type == &key_type_keyring)
779 /* check that we aren't going to create a cycle by linking one
780 * keyring to another */
781 return keyring_detect_cycle(keyring, key);
786 * link a key into to a keyring
787 * - must be called with __key_link_begin() having being called
788 * - discard already extant link to matching key if there is one
790 void __key_link(struct key *keyring, struct key *key,
791 struct keyring_list **_prealloc)
793 struct keyring_list *klist, *nklist;
798 kenter("%d,%d,%p", keyring->serial, key->serial, nklist);
800 klist = rcu_dereference_protected(keyring->payload.subscriptions,
801 rwsem_is_locked(&keyring->sem));
803 atomic_inc(&key->usage);
805 /* there's a matching key we can displace or an empty slot in a newly
806 * allocated list we can fill */
808 kdebug("replace %hu/%hu/%hu",
809 nklist->delkey, nklist->nkeys, nklist->maxkeys);
811 nklist->keys[nklist->delkey] = key;
813 rcu_assign_pointer(keyring->payload.subscriptions, nklist);
815 /* dispose of the old keyring list and, if there was one, the
818 kdebug("dispose %hu/%hu/%hu",
819 klist->delkey, klist->nkeys, klist->maxkeys);
820 call_rcu(&klist->rcu, keyring_unlink_rcu_disposal);
823 /* there's sufficient slack space to append directly */
824 klist->keys[klist->nkeys] = key;
831 * finish linking a key into to a keyring
832 * - must be called with __key_link_begin() having being called
834 void __key_link_end(struct key *keyring, struct key_type *type,
835 struct keyring_list *prealloc)
836 __releases(&keyring->sem)
838 BUG_ON(type == NULL);
839 BUG_ON(type->name == NULL);
840 kenter("%d,%s,%p", keyring->serial, type->name, prealloc);
842 if (type == &key_type_keyring)
843 up_write(&keyring_serialise_link_sem);
847 key_payload_reserve(keyring,
848 keyring->datalen - KEYQUOTA_LINK_BYTES);
850 up_write(&keyring->sem);
854 * link a key to a keyring
856 int key_link(struct key *keyring, struct key *key)
858 struct keyring_list *prealloc;
864 ret = __key_link_begin(keyring, key->type, key->description, &prealloc);
866 ret = __key_link_check_live_key(keyring, key);
868 __key_link(keyring, key, &prealloc);
869 __key_link_end(keyring, key->type, prealloc);
875 EXPORT_SYMBOL(key_link);
878 * unlink the first link to a key from a keyring
880 int key_unlink(struct key *keyring, struct key *key)
882 struct keyring_list *klist, *nklist;
889 if (keyring->type != &key_type_keyring)
892 down_write(&keyring->sem);
894 klist = rcu_dereference_locked_keyring(keyring);
896 /* search the keyring for the key */
897 for (loop = 0; loop < klist->nkeys; loop++)
898 if (klist->keys[loop] == key)
902 up_write(&keyring->sem);
907 /* we need to copy the key list for RCU purposes */
908 nklist = kmalloc(sizeof(*klist) +
909 sizeof(struct key *) * klist->maxkeys,
913 nklist->maxkeys = klist->maxkeys;
914 nklist->nkeys = klist->nkeys - 1;
917 memcpy(&nklist->keys[0],
919 loop * sizeof(struct key *));
921 if (loop < nklist->nkeys)
922 memcpy(&nklist->keys[loop],
923 &klist->keys[loop + 1],
924 (nklist->nkeys - loop) * sizeof(struct key *));
926 /* adjust the user's quota */
927 key_payload_reserve(keyring,
928 keyring->datalen - KEYQUOTA_LINK_BYTES);
930 rcu_assign_pointer(keyring->payload.subscriptions, nklist);
932 up_write(&keyring->sem);
934 /* schedule for later cleanup */
935 klist->delkey = loop;
936 call_rcu(&klist->rcu, keyring_unlink_rcu_disposal);
944 up_write(&keyring->sem);
948 EXPORT_SYMBOL(key_unlink);
951 * dispose of a keyring list after the RCU grace period, releasing the keys it
954 static void keyring_clear_rcu_disposal(struct rcu_head *rcu)
956 struct keyring_list *klist;
959 klist = container_of(rcu, struct keyring_list, rcu);
961 for (loop = klist->nkeys - 1; loop >= 0; loop--)
962 key_put(klist->keys[loop]);
968 * clear the specified process keyring
969 * - implements keyctl(KEYCTL_CLEAR)
971 int keyring_clear(struct key *keyring)
973 struct keyring_list *klist;
977 if (keyring->type == &key_type_keyring) {
978 /* detach the pointer block with the locks held */
979 down_write(&keyring->sem);
981 klist = rcu_dereference_locked_keyring(keyring);
983 /* adjust the quota */
984 key_payload_reserve(keyring,
985 sizeof(struct keyring_list));
987 rcu_assign_pointer(keyring->payload.subscriptions,
991 up_write(&keyring->sem);
993 /* free the keys after the locks have been dropped */
995 call_rcu(&klist->rcu, keyring_clear_rcu_disposal);
1003 EXPORT_SYMBOL(keyring_clear);
1006 * dispose of the links from a revoked keyring
1007 * - called with the key sem write-locked
1009 static void keyring_revoke(struct key *keyring)
1011 struct keyring_list *klist;
1013 klist = rcu_dereference_locked_keyring(keyring);
1015 /* adjust the quota */
1016 key_payload_reserve(keyring, 0);
1019 rcu_assign_pointer(keyring->payload.subscriptions, NULL);
1020 call_rcu(&klist->rcu, keyring_clear_rcu_disposal);
1025 * Determine whether a key is dead
1027 static bool key_is_dead(struct key *key, time_t limit)
1029 return test_bit(KEY_FLAG_DEAD, &key->flags) ||
1030 (key->expiry > 0 && key->expiry <= limit);
1034 * Collect garbage from the contents of a keyring
1036 void keyring_gc(struct key *keyring, time_t limit)
1038 struct keyring_list *klist, *new;
1040 int loop, keep, max;
1042 kenter("{%x,%s}", key_serial(keyring), keyring->description);
1044 down_write(&keyring->sem);
1046 klist = rcu_dereference_locked_keyring(keyring);
1050 /* work out how many subscriptions we're keeping */
1052 for (loop = klist->nkeys - 1; loop >= 0; loop--)
1053 if (!key_is_dead(klist->keys[loop], limit))
1056 if (keep == klist->nkeys)
1059 /* allocate a new keyring payload */
1060 max = roundup(keep, 4);
1061 new = kmalloc(sizeof(struct keyring_list) + max * sizeof(struct key *),
1069 /* install the live keys
1070 * - must take care as expired keys may be updated back to life
1073 for (loop = klist->nkeys - 1; loop >= 0; loop--) {
1074 key = klist->keys[loop];
1075 if (!key_is_dead(key, limit)) {
1078 new->keys[keep++] = key_get(key);
1083 /* adjust the quota */
1084 key_payload_reserve(keyring,
1085 sizeof(struct keyring_list) +
1086 KEYQUOTA_LINK_BYTES * keep);
1089 rcu_assign_pointer(keyring->payload.subscriptions, NULL);
1092 rcu_assign_pointer(keyring->payload.subscriptions, new);
1095 up_write(&keyring->sem);
1097 call_rcu(&klist->rcu, keyring_clear_rcu_disposal);
1103 keyring_clear_rcu_disposal(&new->rcu);
1104 up_write(&keyring->sem);
1105 kleave(" [discard]");
1109 up_write(&keyring->sem);
1110 kleave(" [no dead]");
1114 up_write(&keyring->sem);
1115 kleave(" [no_klist]");
1119 up_write(&keyring->sem);