1 /* keyring.c: keyring handling
3 * Copyright (C) 2004 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/seq_file.h>
17 #include <linux/err.h>
18 #include <asm/uaccess.h>
22 * when plumbing the depths of the key tree, this sets a hard limit set on how
23 * deep we're willing to go
25 #define KEYRING_SEARCH_MAX_DEPTH 6
28 * we keep all named keyrings in a hash to speed looking them up
30 #define KEYRING_NAME_HASH_SIZE (1 << 5)
32 static struct list_head keyring_name_hash[KEYRING_NAME_HASH_SIZE];
33 static DEFINE_RWLOCK(keyring_name_lock);
35 static inline unsigned keyring_hash(const char *desc)
40 bucket += (unsigned char) *desc;
42 return bucket & (KEYRING_NAME_HASH_SIZE - 1);
46 * the keyring type definition
48 static int keyring_instantiate(struct key *keyring,
49 const void *data, size_t datalen);
50 static int keyring_duplicate(struct key *keyring, const struct key *source);
51 static int keyring_match(const struct key *keyring, const void *criterion);
52 static void keyring_destroy(struct key *keyring);
53 static void keyring_describe(const struct key *keyring, struct seq_file *m);
54 static long keyring_read(const struct key *keyring,
55 char __user *buffer, size_t buflen);
57 struct key_type key_type_keyring = {
59 .def_datalen = sizeof(struct keyring_list),
60 .instantiate = keyring_instantiate,
61 .duplicate = keyring_duplicate,
62 .match = keyring_match,
63 .destroy = keyring_destroy,
64 .describe = keyring_describe,
69 * semaphore to serialise link/link calls to prevent two link calls in parallel
72 DECLARE_RWSEM(keyring_serialise_link_sem);
74 /*****************************************************************************/
76 * publish the name of a keyring so that it can be found by name (if it has
79 void keyring_publish_name(struct key *keyring)
83 if (keyring->description) {
84 bucket = keyring_hash(keyring->description);
86 write_lock(&keyring_name_lock);
88 if (!keyring_name_hash[bucket].next)
89 INIT_LIST_HEAD(&keyring_name_hash[bucket]);
91 list_add_tail(&keyring->type_data.link,
92 &keyring_name_hash[bucket]);
94 write_unlock(&keyring_name_lock);
97 } /* end keyring_publish_name() */
99 /*****************************************************************************/
101 * initialise a keyring
102 * - we object if we were given any data
104 static int keyring_instantiate(struct key *keyring,
105 const void *data, size_t datalen)
111 /* make the keyring available by name if it has one */
112 keyring_publish_name(keyring);
118 } /* end keyring_instantiate() */
120 /*****************************************************************************/
122 * duplicate the list of subscribed keys from a source keyring into this one
124 static int keyring_duplicate(struct key *keyring, const struct key *source)
126 struct keyring_list *sklist, *klist;
131 const unsigned limit =
132 (PAGE_SIZE - sizeof(*klist)) / sizeof(struct key);
136 /* find out how many keys are currently linked */
138 sklist = rcu_dereference(source->payload.subscriptions);
144 /* allocate a new payload and stuff load with key links */
148 max = (max + 3) & ~3;
153 size = sizeof(*klist) + sizeof(struct key) * max;
154 klist = kmalloc(size, GFP_KERNEL);
160 sklist = rcu_dereference(source->payload.subscriptions);
162 klist->maxkeys = max;
163 klist->nkeys = sklist->nkeys;
166 sklist->nkeys * sizeof(struct key));
168 for (loop = klist->nkeys - 1; loop >= 0; loop--)
169 atomic_inc(&klist->keys[loop]->usage);
173 rcu_assign_pointer(keyring->payload.subscriptions, klist);
180 } /* end keyring_duplicate() */
182 /*****************************************************************************/
184 * match keyrings on their name
186 static int keyring_match(const struct key *keyring, const void *description)
188 return keyring->description &&
189 strcmp(keyring->description, description) == 0;
191 } /* end keyring_match() */
193 /*****************************************************************************/
195 * dispose of the data dangling from the corpse of a keyring
197 static void keyring_destroy(struct key *keyring)
199 struct keyring_list *klist;
202 if (keyring->description) {
203 write_lock(&keyring_name_lock);
204 list_del(&keyring->type_data.link);
205 write_unlock(&keyring_name_lock);
208 klist = rcu_dereference(keyring->payload.subscriptions);
210 for (loop = klist->nkeys - 1; loop >= 0; loop--)
211 key_put(klist->keys[loop]);
215 } /* end keyring_destroy() */
217 /*****************************************************************************/
219 * describe the keyring
221 static void keyring_describe(const struct key *keyring, struct seq_file *m)
223 struct keyring_list *klist;
225 if (keyring->description) {
226 seq_puts(m, keyring->description);
229 seq_puts(m, "[anon]");
233 klist = rcu_dereference(keyring->payload.subscriptions);
235 seq_printf(m, ": %u/%u", klist->nkeys, klist->maxkeys);
237 seq_puts(m, ": empty");
240 } /* end keyring_describe() */
242 /*****************************************************************************/
244 * read a list of key IDs from the keyring's contents
245 * - the keyring's semaphore is read-locked
247 static long keyring_read(const struct key *keyring,
248 char __user *buffer, size_t buflen)
250 struct keyring_list *klist;
256 klist = rcu_dereference(keyring->payload.subscriptions);
259 /* calculate how much data we could return */
260 qty = klist->nkeys * sizeof(key_serial_t);
262 if (buffer && buflen > 0) {
266 /* copy the IDs of the subscribed keys into the
270 for (loop = 0; loop < klist->nkeys; loop++) {
271 key = klist->keys[loop];
273 tmp = sizeof(key_serial_t);
277 if (copy_to_user(buffer,
295 } /* end keyring_read() */
297 /*****************************************************************************/
299 * allocate a keyring and link into the destination keyring
301 struct key *keyring_alloc(const char *description, uid_t uid, gid_t gid,
302 int not_in_quota, struct key *dest)
307 keyring = key_alloc(&key_type_keyring, description,
308 uid, gid, KEY_USR_ALL, not_in_quota);
310 if (!IS_ERR(keyring)) {
311 ret = key_instantiate_and_link(keyring, NULL, 0, dest);
314 keyring = ERR_PTR(ret);
320 } /* end keyring_alloc() */
322 /*****************************************************************************/
324 * search the supplied keyring tree for a key that matches the criterion
325 * - perform a breadth-then-depth search up to the prescribed limit
326 * - we only find keys on which we have search permission
327 * - we use the supplied match function to see if the description (or other
328 * feature of interest) matches
329 * - we readlock the keyrings as we search down the tree
330 * - we return -EAGAIN if we didn't find any matching key
331 * - we return -ENOKEY if we only found negative matching keys
333 struct key *keyring_search_aux(struct key *keyring,
334 struct key_type *type,
335 const void *description,
336 key_match_func_t match)
339 struct keyring_list *keylist;
341 } stack[KEYRING_SEARCH_MAX_DEPTH];
343 struct keyring_list *keylist;
353 /* top keyring must have search permission to begin the search */
354 key = ERR_PTR(-EACCES);
355 if (!key_permission(keyring, KEY_SEARCH))
358 key = ERR_PTR(-ENOTDIR);
359 if (keyring->type != &key_type_keyring)
362 now = current_kernel_time();
366 /* start processing a new keyring */
368 if (test_bit(KEY_FLAG_REVOKED, &keyring->flags))
369 goto not_this_keyring;
371 keylist = rcu_dereference(keyring->payload.subscriptions);
373 goto not_this_keyring;
375 /* iterate through the keys in this keyring first */
376 for (kix = 0; kix < keylist->nkeys; kix++) {
377 key = keylist->keys[kix];
379 /* ignore keys not of this type */
380 if (key->type != type)
383 /* skip revoked keys and expired keys */
384 if (test_bit(KEY_FLAG_REVOKED, &key->flags))
387 if (key->expiry && now.tv_sec >= key->expiry)
390 /* keys that don't match */
391 if (!match(key, description))
394 /* key must have search permissions */
395 if (!key_permission(key, KEY_SEARCH))
398 /* we set a different error code if we find a negative key */
399 if (test_bit(KEY_FLAG_NEGATIVE, &key->flags)) {
407 /* search through the keyrings nested in this one */
410 for (; kix < keylist->nkeys; kix++) {
411 key = keylist->keys[kix];
412 if (key->type != &key_type_keyring)
415 /* recursively search nested keyrings
416 * - only search keyrings for which we have search permission
418 if (sp >= KEYRING_SEARCH_MAX_DEPTH)
421 if (!key_permission(key, KEY_SEARCH))
424 /* stack the current position */
425 stack[sp].keylist = keylist;
429 /* begin again with the new keyring */
434 /* the keyring we're looking at was disqualified or didn't contain a
438 /* resume the processing of a keyring higher up in the tree */
440 keylist = stack[sp].keylist;
441 kix = stack[sp].kix + 1;
448 /* we found a viable match */
450 atomic_inc(&key->usage);
456 } /* end keyring_search_aux() */
458 /*****************************************************************************/
460 * search the supplied keyring tree for a key that matches the criterion
461 * - perform a breadth-then-depth search up to the prescribed limit
462 * - we only find keys on which we have search permission
463 * - we readlock the keyrings as we search down the tree
464 * - we return -EAGAIN if we didn't find any matching key
465 * - we return -ENOKEY if we only found negative matching keys
467 struct key *keyring_search(struct key *keyring,
468 struct key_type *type,
469 const char *description)
471 return keyring_search_aux(keyring, type, description, type->match);
473 } /* end keyring_search() */
475 EXPORT_SYMBOL(keyring_search);
477 /*****************************************************************************/
479 * search the given keyring only (no recursion)
480 * - keyring must be locked by caller
482 struct key *__keyring_search_one(struct key *keyring,
483 const struct key_type *ktype,
484 const char *description,
487 struct keyring_list *klist;
493 klist = rcu_dereference(keyring->payload.subscriptions);
495 for (loop = 0; loop < klist->nkeys; loop++) {
496 key = klist->keys[loop];
498 if (key->type == ktype &&
499 key->type->match(key, description) &&
500 key_permission(key, perm) &&
501 !test_bit(KEY_FLAG_REVOKED, &key->flags)
507 key = ERR_PTR(-ENOKEY);
511 atomic_inc(&key->usage);
516 } /* end __keyring_search_one() */
518 /*****************************************************************************/
520 * find a keyring with the specified name
521 * - all named keyrings are searched
522 * - only find keyrings with search permission for the process
523 * - only find keyrings with a serial number greater than the one specified
525 struct key *find_keyring_by_name(const char *name, key_serial_t bound)
530 keyring = ERR_PTR(-EINVAL);
534 bucket = keyring_hash(name);
536 read_lock(&keyring_name_lock);
538 if (keyring_name_hash[bucket].next) {
539 /* search this hash bucket for a keyring with a matching name
540 * that's readable and that hasn't been revoked */
541 list_for_each_entry(keyring,
542 &keyring_name_hash[bucket],
545 if (test_bit(KEY_FLAG_REVOKED, &keyring->flags))
548 if (strcmp(keyring->description, name) != 0)
551 if (!key_permission(keyring, KEY_SEARCH))
554 /* found a potential candidate, but we still need to
555 * check the serial number */
556 if (keyring->serial <= bound)
559 /* we've got a match */
560 atomic_inc(&keyring->usage);
561 read_unlock(&keyring_name_lock);
566 read_unlock(&keyring_name_lock);
567 keyring = ERR_PTR(-ENOKEY);
572 } /* end find_keyring_by_name() */
574 /*****************************************************************************/
576 * see if a cycle will will be created by inserting acyclic tree B in acyclic
577 * tree A at the topmost level (ie: as a direct child of A)
578 * - since we are adding B to A at the top level, checking for cycles should
579 * just be a matter of seeing if node A is somewhere in tree B
581 static int keyring_detect_cycle(struct key *A, struct key *B)
584 struct keyring_list *keylist;
586 } stack[KEYRING_SEARCH_MAX_DEPTH];
588 struct keyring_list *keylist;
589 struct key *subtree, *key;
601 /* start processing a new keyring */
603 if (test_bit(KEY_FLAG_REVOKED, &subtree->flags))
604 goto not_this_keyring;
606 keylist = rcu_dereference(subtree->payload.subscriptions);
608 goto not_this_keyring;
612 /* iterate through the remaining keys in this keyring */
613 for (; kix < keylist->nkeys; kix++) {
614 key = keylist->keys[kix];
619 /* recursively check nested keyrings */
620 if (key->type == &key_type_keyring) {
621 if (sp >= KEYRING_SEARCH_MAX_DEPTH)
624 /* stack the current position */
625 stack[sp].keylist = keylist;
629 /* begin again with the new keyring */
635 /* the keyring we're looking at was disqualified or didn't contain a
639 /* resume the checking of a keyring higher up in the tree */
641 keylist = stack[sp].keylist;
642 kix = stack[sp].kix + 1;
646 ret = 0; /* no cycles detected */
660 } /* end keyring_detect_cycle() */
662 /*****************************************************************************/
664 * dispose of a keyring list after the RCU grace period
666 static void keyring_link_rcu_disposal(struct rcu_head *rcu)
668 struct keyring_list *klist =
669 container_of(rcu, struct keyring_list, rcu);
673 } /* end keyring_link_rcu_disposal() */
675 /*****************************************************************************/
677 * link a key into to a keyring
678 * - must be called with the keyring's semaphore write-locked
680 int __key_link(struct key *keyring, struct key *key)
682 struct keyring_list *klist, *nklist;
688 if (test_bit(KEY_FLAG_REVOKED, &keyring->flags))
692 if (keyring->type != &key_type_keyring)
695 /* serialise link/link calls to prevent parallel calls causing a
696 * cycle when applied to two keyring in opposite orders */
697 down_write(&keyring_serialise_link_sem);
699 /* check that we aren't going to create a cycle adding one keyring to
701 if (key->type == &key_type_keyring) {
702 ret = keyring_detect_cycle(keyring, key);
707 /* check that we aren't going to overrun the user's quota */
708 ret = key_payload_reserve(keyring,
709 keyring->datalen + KEYQUOTA_LINK_BYTES);
713 klist = keyring->payload.subscriptions;
715 if (klist && klist->nkeys < klist->maxkeys) {
716 /* there's sufficient slack space to add directly */
717 atomic_inc(&key->usage);
719 klist->keys[klist->nkeys] = key;
727 /* grow the key list */
730 max += klist->maxkeys;
735 size = sizeof(*klist) + sizeof(*key) * max;
736 if (size > PAGE_SIZE)
740 nklist = kmalloc(size, GFP_KERNEL);
743 nklist->maxkeys = max;
747 nklist->nkeys = klist->nkeys;
750 sizeof(struct key *) * klist->nkeys);
753 /* add the key into the new space */
754 atomic_inc(&key->usage);
755 nklist->keys[nklist->nkeys++] = key;
757 rcu_assign_pointer(keyring->payload.subscriptions, nklist);
759 /* dispose of the old keyring list */
761 call_rcu(&klist->rcu, keyring_link_rcu_disposal);
767 up_write(&keyring_serialise_link_sem);
772 /* undo the quota changes */
773 key_payload_reserve(keyring,
774 keyring->datalen - KEYQUOTA_LINK_BYTES);
777 } /* end __key_link() */
779 /*****************************************************************************/
781 * link a key to a keyring
783 int key_link(struct key *keyring, struct key *key)
790 down_write(&keyring->sem);
791 ret = __key_link(keyring, key);
792 up_write(&keyring->sem);
796 } /* end key_link() */
798 EXPORT_SYMBOL(key_link);
800 /*****************************************************************************/
802 * dispose of a keyring list after the RCU grace period, freeing the unlinked
805 static void keyring_unlink_rcu_disposal(struct rcu_head *rcu)
807 struct keyring_list *klist =
808 container_of(rcu, struct keyring_list, rcu);
810 key_put(klist->keys[klist->delkey]);
813 } /* end keyring_unlink_rcu_disposal() */
815 /*****************************************************************************/
817 * unlink the first link to a key from a keyring
819 int key_unlink(struct key *keyring, struct key *key)
821 struct keyring_list *klist, *nklist;
828 if (keyring->type != &key_type_keyring)
831 down_write(&keyring->sem);
833 klist = keyring->payload.subscriptions;
835 /* search the keyring for the key */
836 for (loop = 0; loop < klist->nkeys; loop++)
837 if (klist->keys[loop] == key)
841 up_write(&keyring->sem);
846 /* we need to copy the key list for RCU purposes */
847 nklist = kmalloc(sizeof(*klist) + sizeof(*key) * klist->maxkeys,
851 nklist->maxkeys = klist->maxkeys;
852 nklist->nkeys = klist->nkeys - 1;
855 memcpy(&nklist->keys[0],
857 loop * sizeof(klist->keys[0]));
859 if (loop < nklist->nkeys)
860 memcpy(&nklist->keys[loop],
861 &klist->keys[loop + 1],
862 (nklist->nkeys - loop) * sizeof(klist->keys[0]));
864 /* adjust the user's quota */
865 key_payload_reserve(keyring,
866 keyring->datalen - KEYQUOTA_LINK_BYTES);
868 rcu_assign_pointer(keyring->payload.subscriptions, nklist);
870 up_write(&keyring->sem);
872 /* schedule for later cleanup */
873 klist->delkey = loop;
874 call_rcu(&klist->rcu, keyring_unlink_rcu_disposal);
882 up_write(&keyring->sem);
885 } /* end key_unlink() */
887 EXPORT_SYMBOL(key_unlink);
889 /*****************************************************************************/
891 * dispose of a keyring list after the RCU grace period, releasing the keys it
894 static void keyring_clear_rcu_disposal(struct rcu_head *rcu)
896 struct keyring_list *klist;
899 klist = container_of(rcu, struct keyring_list, rcu);
901 for (loop = klist->nkeys - 1; loop >= 0; loop--)
902 key_put(klist->keys[loop]);
906 } /* end keyring_clear_rcu_disposal() */
908 /*****************************************************************************/
910 * clear the specified process keyring
911 * - implements keyctl(KEYCTL_CLEAR)
913 int keyring_clear(struct key *keyring)
915 struct keyring_list *klist;
919 if (keyring->type == &key_type_keyring) {
920 /* detach the pointer block with the locks held */
921 down_write(&keyring->sem);
923 klist = keyring->payload.subscriptions;
925 /* adjust the quota */
926 key_payload_reserve(keyring,
927 sizeof(struct keyring_list));
929 rcu_assign_pointer(keyring->payload.subscriptions,
933 up_write(&keyring->sem);
935 /* free the keys after the locks have been dropped */
937 call_rcu(&klist->rcu, keyring_clear_rcu_disposal);
944 } /* end keyring_clear() */
946 EXPORT_SYMBOL(keyring_clear);