1 /* key.c: basic authentication token and access key management
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/workqueue.h>
17 #include <linux/err.h>
20 static kmem_cache_t
*key_jar
;
21 static key_serial_t key_serial_next
= 3;
22 struct rb_root key_serial_tree
; /* tree of keys indexed by serial */
23 DEFINE_SPINLOCK(key_serial_lock
);
25 struct rb_root key_user_tree
; /* tree of quota records indexed by UID */
26 DEFINE_SPINLOCK(key_user_lock
);
28 static LIST_HEAD(key_types_list
);
29 static DECLARE_RWSEM(key_types_sem
);
31 static void key_cleanup(void *data
);
32 static DECLARE_WORK(key_cleanup_task
, key_cleanup
, NULL
);
34 /* we serialise key instantiation and link */
35 DECLARE_RWSEM(key_construction_sem
);
37 /* any key who's type gets unegistered will be re-typed to this */
38 struct key_type key_type_dead
= {
43 void __key_check(const struct key
*key
)
45 printk("__key_check: key %p {%08x} should be {%08x}\n",
46 key
, key
->magic
, KEY_DEBUG_MAGIC
);
51 /*****************************************************************************/
53 * get the key quota record for a user, allocating a new record if one doesn't
56 struct key_user
*key_user_lookup(uid_t uid
)
58 struct key_user
*candidate
= NULL
, *user
;
59 struct rb_node
*parent
= NULL
;
63 p
= &key_user_tree
.rb_node
;
64 spin_lock(&key_user_lock
);
66 /* search the tree for a user record with a matching UID */
69 user
= rb_entry(parent
, struct key_user
, node
);
73 else if (uid
> user
->uid
)
79 /* if we get here, we failed to find a match in the tree */
81 /* allocate a candidate user record if we don't already have
83 spin_unlock(&key_user_lock
);
86 candidate
= kmalloc(sizeof(struct key_user
), GFP_KERNEL
);
87 if (unlikely(!candidate
))
90 /* the allocation may have scheduled, so we need to repeat the
91 * search lest someone else added the record whilst we were
96 /* if we get here, then the user record still hadn't appeared on the
97 * second pass - so we use the candidate record */
98 atomic_set(&candidate
->usage
, 1);
99 atomic_set(&candidate
->nkeys
, 0);
100 atomic_set(&candidate
->nikeys
, 0);
101 candidate
->uid
= uid
;
102 candidate
->qnkeys
= 0;
103 candidate
->qnbytes
= 0;
104 spin_lock_init(&candidate
->lock
);
105 INIT_LIST_HEAD(&candidate
->consq
);
107 rb_link_node(&candidate
->node
, parent
, p
);
108 rb_insert_color(&candidate
->node
, &key_user_tree
);
109 spin_unlock(&key_user_lock
);
113 /* okay - we found a user record for this UID */
115 atomic_inc(&user
->usage
);
116 spin_unlock(&key_user_lock
);
122 } /* end key_user_lookup() */
124 /*****************************************************************************/
126 * dispose of a user structure
128 void key_user_put(struct key_user
*user
)
130 if (atomic_dec_and_lock(&user
->usage
, &key_user_lock
)) {
131 rb_erase(&user
->node
, &key_user_tree
);
132 spin_unlock(&key_user_lock
);
137 } /* end key_user_put() */
139 /*****************************************************************************/
141 * insert a key with a fixed serial number
143 static void __init
__key_insert_serial(struct key
*key
)
145 struct rb_node
*parent
, **p
;
149 p
= &key_serial_tree
.rb_node
;
153 xkey
= rb_entry(parent
, struct key
, serial_node
);
155 if (key
->serial
< xkey
->serial
)
157 else if (key
->serial
> xkey
->serial
)
163 /* we've found a suitable hole - arrange for this key to occupy it */
164 rb_link_node(&key
->serial_node
, parent
, p
);
165 rb_insert_color(&key
->serial_node
, &key_serial_tree
);
167 } /* end __key_insert_serial() */
169 /*****************************************************************************/
171 * assign a key the next unique serial number
172 * - we work through all the serial numbers between 2 and 2^31-1 in turn and
175 static inline void key_alloc_serial(struct key
*key
)
177 struct rb_node
*parent
, **p
;
180 spin_lock(&key_serial_lock
);
182 /* propose a likely serial number and look for a hole for it in the
183 * serial number tree */
184 key
->serial
= key_serial_next
;
187 key_serial_next
= key
->serial
+ 1;
190 p
= &key_serial_tree
.rb_node
;
194 xkey
= rb_entry(parent
, struct key
, serial_node
);
196 if (key
->serial
< xkey
->serial
)
198 else if (key
->serial
> xkey
->serial
)
205 /* we found a key with the proposed serial number - walk the tree from
206 * that point looking for the next unused serial number */
209 key
->serial
= key_serial_next
;
212 key_serial_next
= key
->serial
+ 1;
214 if (!parent
->rb_parent
)
215 p
= &key_serial_tree
.rb_node
;
216 else if (parent
->rb_parent
->rb_left
== parent
)
217 p
= &parent
->rb_parent
->rb_left
;
219 p
= &parent
->rb_parent
->rb_right
;
221 parent
= rb_next(parent
);
225 xkey
= rb_entry(parent
, struct key
, serial_node
);
226 if (key
->serial
< xkey
->serial
)
230 /* we've found a suitable hole - arrange for this key to occupy it */
232 rb_link_node(&key
->serial_node
, parent
, p
);
233 rb_insert_color(&key
->serial_node
, &key_serial_tree
);
235 spin_unlock(&key_serial_lock
);
237 } /* end key_alloc_serial() */
239 /*****************************************************************************/
241 * allocate a key of the specified type
242 * - update the user's quota to reflect the existence of the key
243 * - called from a key-type operation with key_types_sem read-locked by either
244 * key_create_or_update() or by key_duplicate(); this prevents unregistration
246 * - upon return the key is as yet uninstantiated; the caller needs to either
247 * instantiate the key or discard it before returning
249 struct key
*key_alloc(struct key_type
*type
, const char *desc
,
250 uid_t uid
, gid_t gid
, key_perm_t perm
,
253 struct key_user
*user
= NULL
;
255 size_t desclen
, quotalen
;
257 key
= ERR_PTR(-EINVAL
);
261 desclen
= strlen(desc
) + 1;
262 quotalen
= desclen
+ type
->def_datalen
;
264 /* get hold of the key tracking for this user */
265 user
= key_user_lookup(uid
);
269 /* check that the user's quota permits allocation of another key and
272 spin_lock(&user
->lock
);
273 if (user
->qnkeys
+ 1 >= KEYQUOTA_MAX_KEYS
&&
274 user
->qnbytes
+ quotalen
>= KEYQUOTA_MAX_BYTES
279 user
->qnbytes
+= quotalen
;
280 spin_unlock(&user
->lock
);
283 /* allocate and initialise the key and its description */
284 key
= kmem_cache_alloc(key_jar
, SLAB_KERNEL
);
289 key
->description
= kmalloc(desclen
, GFP_KERNEL
);
290 if (!key
->description
)
293 memcpy(key
->description
, desc
, desclen
);
296 atomic_set(&key
->usage
, 1);
297 init_rwsem(&key
->sem
);
300 key
->quotalen
= quotalen
;
301 key
->datalen
= type
->def_datalen
;
307 key
->payload
.data
= NULL
;
310 key
->flags
|= 1 << KEY_FLAG_IN_QUOTA
;
312 memset(&key
->type_data
, 0, sizeof(key
->type_data
));
315 key
->magic
= KEY_DEBUG_MAGIC
;
318 /* publish the key by giving it a serial number */
319 atomic_inc(&user
->nkeys
);
320 key_alloc_serial(key
);
326 kmem_cache_free(key_jar
, key
);
329 spin_lock(&user
->lock
);
331 user
->qnbytes
-= quotalen
;
332 spin_unlock(&user
->lock
);
336 key
= ERR_PTR(-ENOMEM
);
340 spin_unlock(&user
->lock
);
342 key
= ERR_PTR(-EDQUOT
);
345 } /* end key_alloc() */
347 EXPORT_SYMBOL(key_alloc
);
349 /*****************************************************************************/
351 * reserve an amount of quota for the key's payload
353 int key_payload_reserve(struct key
*key
, size_t datalen
)
355 int delta
= (int) datalen
- key
->datalen
;
360 /* contemplate the quota adjustment */
361 if (delta
!= 0 && test_bit(KEY_FLAG_IN_QUOTA
, &key
->flags
)) {
362 spin_lock(&key
->user
->lock
);
365 key
->user
->qnbytes
+ delta
> KEYQUOTA_MAX_BYTES
370 key
->user
->qnbytes
+= delta
;
371 key
->quotalen
+= delta
;
373 spin_unlock(&key
->user
->lock
);
376 /* change the recorded data length if that didn't generate an error */
378 key
->datalen
= datalen
;
382 } /* end key_payload_reserve() */
384 EXPORT_SYMBOL(key_payload_reserve
);
386 /*****************************************************************************/
388 * instantiate a key and link it into the target keyring atomically
389 * - called with the target keyring's semaphore writelocked
391 static int __key_instantiate_and_link(struct key
*key
,
404 down_write(&key_construction_sem
);
406 /* can't instantiate twice */
407 if (!test_bit(KEY_FLAG_INSTANTIATED
, &key
->flags
)) {
408 /* instantiate the key */
409 ret
= key
->type
->instantiate(key
, data
, datalen
);
412 /* mark the key as being instantiated */
413 atomic_inc(&key
->user
->nikeys
);
414 set_bit(KEY_FLAG_INSTANTIATED
, &key
->flags
);
416 if (test_and_clear_bit(KEY_FLAG_USER_CONSTRUCT
, &key
->flags
))
419 /* and link it into the destination keyring */
421 ret
= __key_link(keyring
, key
);
425 up_write(&key_construction_sem
);
427 /* wake up anyone waiting for a key to be constructed */
429 wake_up_all(&request_key_conswq
);
433 } /* end __key_instantiate_and_link() */
435 /*****************************************************************************/
437 * instantiate a key and link it into the target keyring atomically
439 int key_instantiate_and_link(struct key
*key
,
447 down_write(&keyring
->sem
);
449 ret
= __key_instantiate_and_link(key
, data
, datalen
, keyring
);
452 up_write(&keyring
->sem
);
455 } /* end key_instantiate_and_link() */
457 EXPORT_SYMBOL(key_instantiate_and_link
);
459 /*****************************************************************************/
461 * negatively instantiate a key and link it into the target keyring atomically
463 int key_negate_and_link(struct key
*key
,
477 down_write(&keyring
->sem
);
479 down_write(&key_construction_sem
);
481 /* can't instantiate twice */
482 if (!test_bit(KEY_FLAG_INSTANTIATED
, &key
->flags
)) {
483 /* mark the key as being negatively instantiated */
484 atomic_inc(&key
->user
->nikeys
);
485 set_bit(KEY_FLAG_NEGATIVE
, &key
->flags
);
486 set_bit(KEY_FLAG_INSTANTIATED
, &key
->flags
);
487 now
= current_kernel_time();
488 key
->expiry
= now
.tv_sec
+ timeout
;
490 if (test_and_clear_bit(KEY_FLAG_USER_CONSTRUCT
, &key
->flags
))
495 /* and link it into the destination keyring */
497 ret
= __key_link(keyring
, key
);
500 up_write(&key_construction_sem
);
503 up_write(&keyring
->sem
);
505 /* wake up anyone waiting for a key to be constructed */
507 wake_up_all(&request_key_conswq
);
511 } /* end key_negate_and_link() */
513 EXPORT_SYMBOL(key_negate_and_link
);
515 /*****************************************************************************/
517 * do cleaning up in process context so that we don't have to disable
518 * interrupts all over the place
520 static void key_cleanup(void *data
)
526 /* look for a dead key in the tree */
527 spin_lock(&key_serial_lock
);
529 for (_n
= rb_first(&key_serial_tree
); _n
; _n
= rb_next(_n
)) {
530 key
= rb_entry(_n
, struct key
, serial_node
);
532 if (atomic_read(&key
->usage
) == 0)
536 spin_unlock(&key_serial_lock
);
540 /* we found a dead key - once we've removed it from the tree, we can
542 rb_erase(&key
->serial_node
, &key_serial_tree
);
543 spin_unlock(&key_serial_lock
);
547 /* deal with the user's key tracking and quota */
548 if (test_bit(KEY_FLAG_IN_QUOTA
, &key
->flags
)) {
549 spin_lock(&key
->user
->lock
);
551 key
->user
->qnbytes
-= key
->quotalen
;
552 spin_unlock(&key
->user
->lock
);
555 atomic_dec(&key
->user
->nkeys
);
556 if (test_bit(KEY_FLAG_INSTANTIATED
, &key
->flags
))
557 atomic_dec(&key
->user
->nikeys
);
559 key_user_put(key
->user
);
561 /* now throw away the key memory */
562 if (key
->type
->destroy
)
563 key
->type
->destroy(key
);
565 kfree(key
->description
);
568 key
->magic
= KEY_DEBUG_MAGIC_X
;
570 kmem_cache_free(key_jar
, key
);
572 /* there may, of course, be more than one key to destroy */
575 } /* end key_cleanup() */
577 /*****************************************************************************/
579 * dispose of a reference to a key
580 * - when all the references are gone, we schedule the cleanup task to come and
581 * pull it out of the tree in definite process context
583 void key_put(struct key
*key
)
588 if (atomic_dec_and_test(&key
->usage
))
589 schedule_work(&key_cleanup_task
);
592 } /* end key_put() */
594 EXPORT_SYMBOL(key_put
);
596 /*****************************************************************************/
598 * find a key by its serial number
600 struct key
*key_lookup(key_serial_t id
)
605 spin_lock(&key_serial_lock
);
607 /* search the tree for the specified key */
608 n
= key_serial_tree
.rb_node
;
610 key
= rb_entry(n
, struct key
, serial_node
);
612 if (id
< key
->serial
)
614 else if (id
> key
->serial
)
621 key
= ERR_PTR(-ENOKEY
);
625 /* pretend it doesn't exist if it's dead */
626 if (atomic_read(&key
->usage
) == 0 ||
627 test_bit(KEY_FLAG_DEAD
, &key
->flags
) ||
628 key
->type
== &key_type_dead
)
631 /* this races with key_put(), but that doesn't matter since key_put()
632 * doesn't actually change the key
634 atomic_inc(&key
->usage
);
637 spin_unlock(&key_serial_lock
);
640 } /* end key_lookup() */
642 /*****************************************************************************/
644 * find and lock the specified key type against removal
645 * - we return with the sem readlocked
647 struct key_type
*key_type_lookup(const char *type
)
649 struct key_type
*ktype
;
651 down_read(&key_types_sem
);
653 /* look up the key type to see if it's one of the registered kernel
655 list_for_each_entry(ktype
, &key_types_list
, link
) {
656 if (strcmp(ktype
->name
, type
) == 0)
657 goto found_kernel_type
;
660 up_read(&key_types_sem
);
661 ktype
= ERR_PTR(-ENOKEY
);
666 } /* end key_type_lookup() */
668 /*****************************************************************************/
672 void key_type_put(struct key_type
*ktype
)
674 up_read(&key_types_sem
);
676 } /* end key_type_put() */
678 /*****************************************************************************/
680 * attempt to update an existing key
681 * - the key has an incremented refcount
682 * - we need to put the key if we get an error
684 static inline struct key
*__key_update(struct key
*key
, const void *payload
,
689 /* need write permission on the key to update it */
691 if (!key_permission(key
, KEY_WRITE
))
695 if (!key
->type
->update
)
698 down_write(&key
->sem
);
700 ret
= key
->type
->update(key
, payload
, plen
);
703 /* updating a negative key instantiates it */
704 clear_bit(KEY_FLAG_NEGATIVE
, &key
->flags
);
718 } /* end __key_update() */
720 /*****************************************************************************/
722 * search the specified keyring for a key of the same description; if one is
723 * found, update it, otherwise add a new one
725 struct key
*key_create_or_update(struct key
*keyring
,
727 const char *description
,
732 struct key_type
*ktype
;
733 struct key
*key
= NULL
;
739 /* look up the key type to see if it's one of the registered kernel
741 ktype
= key_type_lookup(type
);
743 key
= ERR_PTR(-ENODEV
);
748 if (!ktype
->match
|| !ktype
->instantiate
)
751 /* search for an existing key of the same type and description in the
752 * destination keyring
754 down_write(&keyring
->sem
);
756 key
= __keyring_search_one(keyring
, ktype
, description
, 0);
758 goto found_matching_key
;
760 /* if we're going to allocate a new key, we're going to have to modify
763 if (!key_permission(keyring
, KEY_WRITE
))
766 /* decide on the permissions we want */
767 perm
= KEY_USR_VIEW
| KEY_USR_SEARCH
| KEY_USR_LINK
;
770 perm
|= KEY_USR_READ
;
772 if (ktype
== &key_type_keyring
|| ktype
->update
)
773 perm
|= KEY_USR_WRITE
;
775 /* allocate a new key */
776 key
= key_alloc(ktype
, description
, current
->fsuid
, current
->fsgid
,
783 /* instantiate it and link it into the target keyring */
784 ret
= __key_instantiate_and_link(key
, payload
, plen
, keyring
);
791 up_write(&keyring
->sem
);
798 /* we found a matching key, so we're going to try to update it
799 * - we can drop the locks first as we have the key pinned
801 up_write(&keyring
->sem
);
804 key
= __key_update(key
, payload
, plen
);
807 } /* end key_create_or_update() */
809 EXPORT_SYMBOL(key_create_or_update
);
811 /*****************************************************************************/
815 int key_update(struct key
*key
, const void *payload
, size_t plen
)
821 /* the key must be writable */
823 if (!key_permission(key
, KEY_WRITE
))
826 /* attempt to update it if supported */
828 if (key
->type
->update
) {
829 down_write(&key
->sem
);
830 ret
= key
->type
->update(key
, payload
, plen
);
833 /* updating a negative key instantiates it */
834 clear_bit(KEY_FLAG_NEGATIVE
, &key
->flags
);
842 } /* end key_update() */
844 EXPORT_SYMBOL(key_update
);
846 /*****************************************************************************/
848 * duplicate a key, potentially with a revised description
849 * - must be supported by the keytype (keyrings for instance can be duplicated)
851 struct key
*key_duplicate(struct key
*source
, const char *desc
)
859 desc
= source
->description
;
861 down_read(&key_types_sem
);
864 if (!source
->type
->duplicate
)
867 /* allocate and instantiate a key */
868 key
= key_alloc(source
->type
, desc
, current
->fsuid
, current
->fsgid
,
873 down_read(&source
->sem
);
874 ret
= key
->type
->duplicate(key
, source
);
875 up_read(&source
->sem
);
879 atomic_inc(&key
->user
->nikeys
);
880 set_bit(KEY_FLAG_INSTANTIATED
, &key
->flags
);
883 up_read(&key_types_sem
);
890 up_read(&key_types_sem
);
894 } /* end key_duplicate() */
896 /*****************************************************************************/
900 void key_revoke(struct key
*key
)
904 /* make sure no one's trying to change or use the key when we mark
906 down_write(&key
->sem
);
907 set_bit(KEY_FLAG_REVOKED
, &key
->flags
);
910 } /* end key_revoke() */
912 EXPORT_SYMBOL(key_revoke
);
914 /*****************************************************************************/
916 * register a type of key
918 int register_key_type(struct key_type
*ktype
)
924 down_write(&key_types_sem
);
926 /* disallow key types with the same name */
927 list_for_each_entry(p
, &key_types_list
, link
) {
928 if (strcmp(p
->name
, ktype
->name
) == 0)
933 list_add(&ktype
->link
, &key_types_list
);
937 up_write(&key_types_sem
);
940 } /* end register_key_type() */
942 EXPORT_SYMBOL(register_key_type
);
944 /*****************************************************************************/
946 * unregister a type of key
948 void unregister_key_type(struct key_type
*ktype
)
953 down_write(&key_types_sem
);
955 /* withdraw the key type */
956 list_del_init(&ktype
->link
);
958 /* mark all the keys of this type dead */
959 spin_lock(&key_serial_lock
);
961 for (_n
= rb_first(&key_serial_tree
); _n
; _n
= rb_next(_n
)) {
962 key
= rb_entry(_n
, struct key
, serial_node
);
964 if (key
->type
== ktype
)
965 key
->type
= &key_type_dead
;
968 spin_unlock(&key_serial_lock
);
970 /* make sure everyone revalidates their keys */
971 synchronize_kernel();
973 /* we should now be able to destroy the payloads of all the keys of
974 * this type with impunity */
975 spin_lock(&key_serial_lock
);
977 for (_n
= rb_first(&key_serial_tree
); _n
; _n
= rb_next(_n
)) {
978 key
= rb_entry(_n
, struct key
, serial_node
);
980 if (key
->type
== ktype
) {
983 memset(&key
->payload
, 0xbd, sizeof(key
->payload
));
987 spin_unlock(&key_serial_lock
);
988 up_write(&key_types_sem
);
990 } /* end unregister_key_type() */
992 EXPORT_SYMBOL(unregister_key_type
);
994 /*****************************************************************************/
996 * initialise the key management stuff
998 void __init
key_init(void)
1000 /* allocate a slab in which we can store keys */
1001 key_jar
= kmem_cache_create("key_jar", sizeof(struct key
),
1002 0, SLAB_HWCACHE_ALIGN
|SLAB_PANIC
, NULL
, NULL
);
1004 /* add the special key types */
1005 list_add_tail(&key_type_keyring
.link
, &key_types_list
);
1006 list_add_tail(&key_type_dead
.link
, &key_types_list
);
1007 list_add_tail(&key_type_user
.link
, &key_types_list
);
1009 /* record the root user tracking */
1010 rb_link_node(&root_key_user
.node
,
1012 &key_user_tree
.rb_node
);
1014 rb_insert_color(&root_key_user
.node
,
1017 /* record root's user standard keyrings */
1018 key_check(&root_user_keyring
);
1019 key_check(&root_session_keyring
);
1021 __key_insert_serial(&root_user_keyring
);
1022 __key_insert_serial(&root_session_keyring
);
1024 keyring_publish_name(&root_user_keyring
);
1025 keyring_publish_name(&root_session_keyring
);
1027 /* link the two root keyrings together */
1028 key_link(&root_session_keyring
, &root_user_keyring
);
1030 } /* end key_init() */