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>
24 * when plumbing the depths of the key tree, this sets a hard limit set on how
25 * deep we're willing to go
27 #define KEYRING_SEARCH_MAX_DEPTH 6
30 * we keep all named keyrings in a hash to speed looking them up
32 #define KEYRING_NAME_HASH_SIZE (1 << 5)
34 static struct list_head keyring_name_hash[KEYRING_NAME_HASH_SIZE];
35 static DEFINE_RWLOCK(keyring_name_lock);
37 static inline unsigned keyring_hash(const char *desc)
42 bucket += (unsigned char) *desc;
44 return bucket & (KEYRING_NAME_HASH_SIZE - 1);
48 * the keyring type definition
50 static int keyring_instantiate(struct key *keyring,
51 const void *data, size_t datalen);
52 static int keyring_match(const struct key *keyring, const void *criterion);
53 static void keyring_revoke(struct key *keyring);
54 static void keyring_destroy(struct key *keyring);
55 static void keyring_describe(const struct key *keyring, struct seq_file *m);
56 static long keyring_read(const struct key *keyring,
57 char __user *buffer, size_t buflen);
59 struct key_type key_type_keyring = {
61 .def_datalen = sizeof(struct keyring_list),
62 .instantiate = keyring_instantiate,
63 .match = keyring_match,
64 .revoke = keyring_revoke,
65 .destroy = keyring_destroy,
66 .describe = keyring_describe,
70 EXPORT_SYMBOL(key_type_keyring);
73 * semaphore to serialise link/link calls to prevent two link calls in parallel
76 static DECLARE_RWSEM(keyring_serialise_link_sem);
78 /*****************************************************************************/
80 * publish the name of a keyring so that it can be found by name (if it has
83 static void keyring_publish_name(struct key *keyring)
87 if (keyring->description) {
88 bucket = keyring_hash(keyring->description);
90 write_lock(&keyring_name_lock);
92 if (!keyring_name_hash[bucket].next)
93 INIT_LIST_HEAD(&keyring_name_hash[bucket]);
95 list_add_tail(&keyring->type_data.link,
96 &keyring_name_hash[bucket]);
98 write_unlock(&keyring_name_lock);
101 } /* end keyring_publish_name() */
103 /*****************************************************************************/
105 * initialise a keyring
106 * - we object if we were given any data
108 static int keyring_instantiate(struct key *keyring,
109 const void *data, size_t datalen)
115 /* make the keyring available by name if it has one */
116 keyring_publish_name(keyring);
122 } /* end keyring_instantiate() */
124 /*****************************************************************************/
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;
133 } /* end keyring_match() */
135 /*****************************************************************************/
137 * dispose of the data dangling from the corpse of a keyring
139 static void keyring_destroy(struct key *keyring)
141 struct keyring_list *klist;
144 if (keyring->description) {
145 write_lock(&keyring_name_lock);
147 if (keyring->type_data.link.next != NULL &&
148 !list_empty(&keyring->type_data.link))
149 list_del(&keyring->type_data.link);
151 write_unlock(&keyring_name_lock);
154 klist = rcu_dereference_check(keyring->payload.subscriptions,
155 rcu_read_lock_held() ||
156 atomic_read(&keyring->usage) == 0);
158 for (loop = klist->nkeys - 1; loop >= 0; loop--)
159 key_put(klist->keys[loop]);
163 } /* end keyring_destroy() */
165 /*****************************************************************************/
167 * describe the keyring
169 static void keyring_describe(const struct key *keyring, struct seq_file *m)
171 struct keyring_list *klist;
173 if (keyring->description) {
174 seq_puts(m, keyring->description);
177 seq_puts(m, "[anon]");
181 klist = rcu_dereference(keyring->payload.subscriptions);
183 seq_printf(m, ": %u/%u", klist->nkeys, klist->maxkeys);
185 seq_puts(m, ": empty");
188 } /* end keyring_describe() */
190 /*****************************************************************************/
192 * read a list of key IDs from the keyring's contents
193 * - the keyring's semaphore is read-locked
195 static long keyring_read(const struct key *keyring,
196 char __user *buffer, size_t buflen)
198 struct keyring_list *klist;
204 klist = rcu_dereference(keyring->payload.subscriptions);
207 /* calculate how much data we could return */
208 qty = klist->nkeys * sizeof(key_serial_t);
210 if (buffer && buflen > 0) {
214 /* copy the IDs of the subscribed keys into the
218 for (loop = 0; loop < klist->nkeys; loop++) {
219 key = klist->keys[loop];
221 tmp = sizeof(key_serial_t);
225 if (copy_to_user(buffer,
243 } /* end keyring_read() */
245 /*****************************************************************************/
247 * allocate a keyring and link into the destination keyring
249 struct key *keyring_alloc(const char *description, uid_t uid, gid_t gid,
250 const struct cred *cred, unsigned long flags,
256 keyring = key_alloc(&key_type_keyring, description,
258 (KEY_POS_ALL & ~KEY_POS_SETATTR) | KEY_USR_ALL,
261 if (!IS_ERR(keyring)) {
262 ret = key_instantiate_and_link(keyring, NULL, 0, dest, NULL);
265 keyring = ERR_PTR(ret);
271 } /* end keyring_alloc() */
273 /*****************************************************************************/
275 * search the supplied keyring tree for a key that matches the criterion
276 * - perform a breadth-then-depth search up to the prescribed limit
277 * - we only find keys on which we have search permission
278 * - we use the supplied match function to see if the description (or other
279 * feature of interest) matches
280 * - we rely on RCU to prevent the keyring lists from disappearing on us
281 * - we return -EAGAIN if we didn't find any matching key
282 * - we return -ENOKEY if we only found negative matching keys
283 * - we propagate the possession attribute from the keyring ref to the key ref
285 key_ref_t keyring_search_aux(key_ref_t keyring_ref,
286 const struct cred *cred,
287 struct key_type *type,
288 const void *description,
289 key_match_func_t match)
292 struct keyring_list *keylist;
294 } stack[KEYRING_SEARCH_MAX_DEPTH];
296 struct keyring_list *keylist;
298 unsigned long possessed, kflags;
299 struct key *keyring, *key;
304 keyring = key_ref_to_ptr(keyring_ref);
305 possessed = is_key_possessed(keyring_ref);
308 /* top keyring must have search permission to begin the search */
309 err = key_task_permission(keyring_ref, cred, KEY_SEARCH);
311 key_ref = ERR_PTR(err);
315 key_ref = ERR_PTR(-ENOTDIR);
316 if (keyring->type != &key_type_keyring)
321 now = current_kernel_time();
325 /* firstly we should check to see if this top-level keyring is what we
327 key_ref = ERR_PTR(-EAGAIN);
328 kflags = keyring->flags;
329 if (keyring->type == type && match(keyring, description)) {
332 /* check it isn't negative and hasn't expired or been
334 if (kflags & (1 << KEY_FLAG_REVOKED))
336 if (key->expiry && now.tv_sec >= key->expiry)
338 key_ref = ERR_PTR(-ENOKEY);
339 if (kflags & (1 << KEY_FLAG_NEGATIVE))
344 /* otherwise, the top keyring must not be revoked, expired, or
345 * negatively instantiated if we are to search it */
346 key_ref = ERR_PTR(-EAGAIN);
347 if (kflags & ((1 << KEY_FLAG_REVOKED) | (1 << KEY_FLAG_NEGATIVE)) ||
348 (keyring->expiry && now.tv_sec >= keyring->expiry))
351 /* start processing a new keyring */
353 if (test_bit(KEY_FLAG_REVOKED, &keyring->flags))
354 goto not_this_keyring;
356 keylist = rcu_dereference(keyring->payload.subscriptions);
358 goto not_this_keyring;
360 /* iterate through the keys in this keyring first */
361 for (kix = 0; kix < keylist->nkeys; kix++) {
362 key = keylist->keys[kix];
365 /* ignore keys not of this type */
366 if (key->type != type)
369 /* skip revoked keys and expired keys */
370 if (kflags & (1 << KEY_FLAG_REVOKED))
373 if (key->expiry && now.tv_sec >= key->expiry)
376 /* keys that don't match */
377 if (!match(key, description))
380 /* key must have search permissions */
381 if (key_task_permission(make_key_ref(key, possessed),
382 cred, KEY_SEARCH) < 0)
385 /* we set a different error code if we pass a negative key */
386 if (kflags & (1 << KEY_FLAG_NEGATIVE)) {
394 /* search through the keyrings nested in this one */
397 for (; kix < keylist->nkeys; kix++) {
398 key = keylist->keys[kix];
399 if (key->type != &key_type_keyring)
402 /* recursively search nested keyrings
403 * - only search keyrings for which we have search permission
405 if (sp >= KEYRING_SEARCH_MAX_DEPTH)
408 if (key_task_permission(make_key_ref(key, possessed),
409 cred, KEY_SEARCH) < 0)
412 /* stack the current position */
413 stack[sp].keylist = keylist;
417 /* begin again with the new keyring */
422 /* the keyring we're looking at was disqualified or didn't contain a
426 /* resume the processing of a keyring higher up in the tree */
428 keylist = stack[sp].keylist;
429 kix = stack[sp].kix + 1;
433 key_ref = ERR_PTR(err);
436 /* we found a viable match */
438 atomic_inc(&key->usage);
440 key_ref = make_key_ref(key, possessed);
446 } /* end keyring_search_aux() */
448 /*****************************************************************************/
450 * search the supplied keyring tree for a key that matches the criterion
451 * - perform a breadth-then-depth search up to the prescribed limit
452 * - we only find keys on which we have search permission
453 * - we readlock the keyrings as we search down the tree
454 * - we return -EAGAIN if we didn't find any matching key
455 * - we return -ENOKEY if we only found negative matching keys
457 key_ref_t keyring_search(key_ref_t keyring,
458 struct key_type *type,
459 const char *description)
462 return ERR_PTR(-ENOKEY);
464 return keyring_search_aux(keyring, current->cred,
465 type, description, type->match);
467 } /* end keyring_search() */
469 EXPORT_SYMBOL(keyring_search);
471 /*****************************************************************************/
473 * search the given keyring only (no recursion)
474 * - keyring must be locked by caller
475 * - caller must guarantee that the keyring is a keyring
477 key_ref_t __keyring_search_one(key_ref_t keyring_ref,
478 const struct key_type *ktype,
479 const char *description,
482 struct keyring_list *klist;
483 unsigned long possessed;
484 struct key *keyring, *key;
487 keyring = key_ref_to_ptr(keyring_ref);
488 possessed = is_key_possessed(keyring_ref);
492 klist = rcu_dereference(keyring->payload.subscriptions);
494 for (loop = 0; loop < klist->nkeys; loop++) {
495 key = klist->keys[loop];
497 if (key->type == ktype &&
498 (!key->type->match ||
499 key->type->match(key, description)) &&
500 key_permission(make_key_ref(key, possessed),
502 !test_bit(KEY_FLAG_REVOKED, &key->flags)
509 return ERR_PTR(-ENOKEY);
512 atomic_inc(&key->usage);
514 return make_key_ref(key, possessed);
516 } /* end __keyring_search_one() */
518 /*****************************************************************************/
520 * find a keyring with the specified name
521 * - all named keyrings are searched
522 * - normally only finds keyrings with search permission for the current process
524 struct key *find_keyring_by_name(const char *name, bool skip_perm_check)
529 keyring = ERR_PTR(-EINVAL);
533 bucket = keyring_hash(name);
535 read_lock(&keyring_name_lock);
537 if (keyring_name_hash[bucket].next) {
538 /* search this hash bucket for a keyring with a matching name
539 * that's readable and that hasn't been revoked */
540 list_for_each_entry(keyring,
541 &keyring_name_hash[bucket],
544 if (keyring->user->user_ns != current_user_ns())
547 if (test_bit(KEY_FLAG_REVOKED, &keyring->flags))
550 if (strcmp(keyring->description, name) != 0)
553 if (!skip_perm_check &&
554 key_permission(make_key_ref(keyring, 0),
558 /* we've got a match */
559 atomic_inc(&keyring->usage);
560 read_unlock(&keyring_name_lock);
565 read_unlock(&keyring_name_lock);
566 keyring = ERR_PTR(-ENOKEY);
571 } /* end find_keyring_by_name() */
573 /*****************************************************************************/
575 * see if a cycle will will be created by inserting acyclic tree B in acyclic
576 * tree A at the topmost level (ie: as a direct child of A)
577 * - since we are adding B to A at the top level, checking for cycles should
578 * just be a matter of seeing if node A is somewhere in tree B
580 static int keyring_detect_cycle(struct key *A, struct key *B)
583 struct keyring_list *keylist;
585 } stack[KEYRING_SEARCH_MAX_DEPTH];
587 struct keyring_list *keylist;
588 struct key *subtree, *key;
600 /* start processing a new keyring */
602 if (test_bit(KEY_FLAG_REVOKED, &subtree->flags))
603 goto not_this_keyring;
605 keylist = rcu_dereference(subtree->payload.subscriptions);
607 goto not_this_keyring;
611 /* iterate through the remaining keys in this keyring */
612 for (; kix < keylist->nkeys; kix++) {
613 key = keylist->keys[kix];
618 /* recursively check nested keyrings */
619 if (key->type == &key_type_keyring) {
620 if (sp >= KEYRING_SEARCH_MAX_DEPTH)
623 /* stack the current position */
624 stack[sp].keylist = keylist;
628 /* begin again with the new keyring */
634 /* the keyring we're looking at was disqualified or didn't contain a
638 /* resume the checking of a keyring higher up in the tree */
640 keylist = stack[sp].keylist;
641 kix = stack[sp].kix + 1;
645 ret = 0; /* no cycles detected */
659 } /* end keyring_detect_cycle() */
661 /*****************************************************************************/
663 * dispose of a keyring list after the RCU grace period
665 static void keyring_link_rcu_disposal(struct rcu_head *rcu)
667 struct keyring_list *klist =
668 container_of(rcu, struct keyring_list, rcu);
672 } /* end keyring_link_rcu_disposal() */
674 /*****************************************************************************/
676 * dispose of a keyring list after the RCU grace period, freeing the unlinked
679 static void keyring_unlink_rcu_disposal(struct rcu_head *rcu)
681 struct keyring_list *klist =
682 container_of(rcu, struct keyring_list, rcu);
684 key_put(klist->keys[klist->delkey]);
687 } /* end keyring_unlink_rcu_disposal() */
689 /*****************************************************************************/
691 * link a key into to a keyring
692 * - must be called with the keyring's semaphore write-locked
693 * - discard already extant link to matching key if there is one
695 int __key_link(struct key *keyring, struct key *key)
697 struct keyring_list *klist, *nklist;
703 if (test_bit(KEY_FLAG_REVOKED, &keyring->flags))
707 if (keyring->type != &key_type_keyring)
710 /* serialise link/link calls to prevent parallel calls causing a
711 * cycle when applied to two keyring in opposite orders */
712 down_write(&keyring_serialise_link_sem);
714 /* check that we aren't going to create a cycle adding one keyring to
716 if (key->type == &key_type_keyring) {
717 ret = keyring_detect_cycle(keyring, key);
722 /* see if there's a matching key we can displace */
723 klist = keyring->payload.subscriptions;
725 if (klist && klist->nkeys > 0) {
726 struct key_type *type = key->type;
728 for (loop = klist->nkeys - 1; loop >= 0; loop--) {
729 if (klist->keys[loop]->type == type &&
730 strcmp(klist->keys[loop]->description,
731 key->description) == 0
733 /* found a match - replace with new key */
734 size = sizeof(struct key *) * klist->maxkeys;
735 size += sizeof(*klist);
736 BUG_ON(size > PAGE_SIZE);
739 nklist = kmemdup(klist, size, GFP_KERNEL);
743 /* replace matched key */
744 atomic_inc(&key->usage);
745 nklist->keys[loop] = key;
748 keyring->payload.subscriptions,
751 /* dispose of the old keyring list and the
753 klist->delkey = loop;
754 call_rcu(&klist->rcu,
755 keyring_unlink_rcu_disposal);
762 /* check that we aren't going to overrun the user's quota */
763 ret = key_payload_reserve(keyring,
764 keyring->datalen + KEYQUOTA_LINK_BYTES);
768 klist = keyring->payload.subscriptions;
770 if (klist && klist->nkeys < klist->maxkeys) {
771 /* there's sufficient slack space to add directly */
772 atomic_inc(&key->usage);
774 klist->keys[klist->nkeys] = key;
780 /* grow the key list */
783 max += klist->maxkeys;
788 size = sizeof(*klist) + sizeof(struct key *) * max;
789 if (size > PAGE_SIZE)
793 nklist = kmalloc(size, GFP_KERNEL);
796 nklist->maxkeys = max;
800 nklist->nkeys = klist->nkeys;
803 sizeof(struct key *) * klist->nkeys);
806 /* add the key into the new space */
807 atomic_inc(&key->usage);
808 nklist->keys[nklist->nkeys++] = key;
810 rcu_assign_pointer(keyring->payload.subscriptions, nklist);
812 /* dispose of the old keyring list */
814 call_rcu(&klist->rcu, keyring_link_rcu_disposal);
820 up_write(&keyring_serialise_link_sem);
825 /* undo the quota changes */
826 key_payload_reserve(keyring,
827 keyring->datalen - KEYQUOTA_LINK_BYTES);
830 } /* end __key_link() */
832 /*****************************************************************************/
834 * link a key to a keyring
836 int key_link(struct key *keyring, struct key *key)
843 down_write(&keyring->sem);
844 ret = __key_link(keyring, key);
845 up_write(&keyring->sem);
849 } /* end key_link() */
851 EXPORT_SYMBOL(key_link);
853 /*****************************************************************************/
855 * unlink the first link to a key from a keyring
857 int key_unlink(struct key *keyring, struct key *key)
859 struct keyring_list *klist, *nklist;
866 if (keyring->type != &key_type_keyring)
869 down_write(&keyring->sem);
871 klist = keyring->payload.subscriptions;
873 /* search the keyring for the key */
874 for (loop = 0; loop < klist->nkeys; loop++)
875 if (klist->keys[loop] == key)
879 up_write(&keyring->sem);
884 /* we need to copy the key list for RCU purposes */
885 nklist = kmalloc(sizeof(*klist) +
886 sizeof(struct key *) * klist->maxkeys,
890 nklist->maxkeys = klist->maxkeys;
891 nklist->nkeys = klist->nkeys - 1;
894 memcpy(&nklist->keys[0],
896 loop * sizeof(struct key *));
898 if (loop < nklist->nkeys)
899 memcpy(&nklist->keys[loop],
900 &klist->keys[loop + 1],
901 (nklist->nkeys - loop) * sizeof(struct key *));
903 /* adjust the user's quota */
904 key_payload_reserve(keyring,
905 keyring->datalen - KEYQUOTA_LINK_BYTES);
907 rcu_assign_pointer(keyring->payload.subscriptions, nklist);
909 up_write(&keyring->sem);
911 /* schedule for later cleanup */
912 klist->delkey = loop;
913 call_rcu(&klist->rcu, keyring_unlink_rcu_disposal);
921 up_write(&keyring->sem);
924 } /* end key_unlink() */
926 EXPORT_SYMBOL(key_unlink);
928 /*****************************************************************************/
930 * dispose of a keyring list after the RCU grace period, releasing the keys it
933 static void keyring_clear_rcu_disposal(struct rcu_head *rcu)
935 struct keyring_list *klist;
938 klist = container_of(rcu, struct keyring_list, rcu);
940 for (loop = klist->nkeys - 1; loop >= 0; loop--)
941 key_put(klist->keys[loop]);
945 } /* end keyring_clear_rcu_disposal() */
947 /*****************************************************************************/
949 * clear the specified process keyring
950 * - implements keyctl(KEYCTL_CLEAR)
952 int keyring_clear(struct key *keyring)
954 struct keyring_list *klist;
958 if (keyring->type == &key_type_keyring) {
959 /* detach the pointer block with the locks held */
960 down_write(&keyring->sem);
962 klist = keyring->payload.subscriptions;
964 /* adjust the quota */
965 key_payload_reserve(keyring,
966 sizeof(struct keyring_list));
968 rcu_assign_pointer(keyring->payload.subscriptions,
972 up_write(&keyring->sem);
974 /* free the keys after the locks have been dropped */
976 call_rcu(&klist->rcu, keyring_clear_rcu_disposal);
983 } /* end keyring_clear() */
985 EXPORT_SYMBOL(keyring_clear);
987 /*****************************************************************************/
989 * dispose of the links from a revoked keyring
990 * - called with the key sem write-locked
992 static void keyring_revoke(struct key *keyring)
994 struct keyring_list *klist = keyring->payload.subscriptions;
996 /* adjust the quota */
997 key_payload_reserve(keyring, 0);
1000 rcu_assign_pointer(keyring->payload.subscriptions, NULL);
1001 call_rcu(&klist->rcu, keyring_clear_rcu_disposal);
1004 } /* end keyring_revoke() */
1007 * Determine whether a key is dead
1009 static bool key_is_dead(struct key *key, time_t limit)
1011 return test_bit(KEY_FLAG_DEAD, &key->flags) ||
1012 (key->expiry > 0 && key->expiry <= limit);
1016 * Collect garbage from the contents of a keyring
1018 void keyring_gc(struct key *keyring, time_t limit)
1020 struct keyring_list *klist, *new;
1022 int loop, keep, max;
1024 kenter("{%x,%s}", key_serial(keyring), keyring->description);
1026 down_write(&keyring->sem);
1028 klist = keyring->payload.subscriptions;
1032 /* work out how many subscriptions we're keeping */
1034 for (loop = klist->nkeys - 1; loop >= 0; loop--)
1035 if (!key_is_dead(klist->keys[loop], limit))
1038 if (keep == klist->nkeys)
1041 /* allocate a new keyring payload */
1042 max = roundup(keep, 4);
1043 new = kmalloc(sizeof(struct keyring_list) + max * sizeof(struct key *),
1051 /* install the live keys
1052 * - must take care as expired keys may be updated back to life
1055 for (loop = klist->nkeys - 1; loop >= 0; loop--) {
1056 key = klist->keys[loop];
1057 if (!key_is_dead(key, limit)) {
1060 new->keys[keep++] = key_get(key);
1065 /* adjust the quota */
1066 key_payload_reserve(keyring,
1067 sizeof(struct keyring_list) +
1068 KEYQUOTA_LINK_BYTES * keep);
1071 rcu_assign_pointer(keyring->payload.subscriptions, NULL);
1074 rcu_assign_pointer(keyring->payload.subscriptions, new);
1077 up_write(&keyring->sem);
1079 call_rcu(&klist->rcu, keyring_clear_rcu_disposal);
1085 keyring_clear_rcu_disposal(&new->rcu);
1086 up_write(&keyring->sem);
1087 kleave(" [discard]");
1091 up_write(&keyring->sem);
1092 kleave(" [no dead]");
1096 up_write(&keyring->sem);
1097 kleave(" [no_klist]");
1101 up_write(&keyring->sem);