aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/keys/keyring-type.h17
-rw-r--r--include/linux/key.h13
-rw-r--r--lib/assoc_array.c1
-rw-r--r--security/keys/Kconfig1
-rw-r--r--security/keys/gc.c33
-rw-r--r--security/keys/internal.h17
-rw-r--r--security/keys/key.c35
-rw-r--r--security/keys/keyring.c1436
-rw-r--r--security/keys/request_key.c12
9 files changed, 803 insertions, 762 deletions
diff --git a/include/keys/keyring-type.h b/include/keys/keyring-type.h
index cf49159b0e3a..fca5c62340a4 100644
--- a/include/keys/keyring-type.h
+++ b/include/keys/keyring-type.h
@@ -1,6 +1,6 @@
1/* Keyring key type 1/* Keyring key type
2 * 2 *
3 * Copyright (C) 2008 Red Hat, Inc. All Rights Reserved. 3 * Copyright (C) 2008, 2013 Red Hat, Inc. All Rights Reserved.
4 * Written by David Howells (dhowells@redhat.com) 4 * Written by David Howells (dhowells@redhat.com)
5 * 5 *
6 * This program is free software; you can redistribute it and/or 6 * This program is free software; you can redistribute it and/or
@@ -13,19 +13,6 @@
13#define _KEYS_KEYRING_TYPE_H 13#define _KEYS_KEYRING_TYPE_H
14 14
15#include <linux/key.h> 15#include <linux/key.h>
16#include <linux/rcupdate.h> 16#include <linux/assoc_array.h>
17
18/*
19 * the keyring payload contains a list of the keys to which the keyring is
20 * subscribed
21 */
22struct keyring_list {
23 struct rcu_head rcu; /* RCU deletion hook */
24 unsigned short maxkeys; /* max keys this list can hold */
25 unsigned short nkeys; /* number of keys currently held */
26 unsigned short delkey; /* key to be unlinked by RCU */
27 struct key __rcu *keys[0];
28};
29
30 17
31#endif /* _KEYS_KEYRING_TYPE_H */ 18#endif /* _KEYS_KEYRING_TYPE_H */
diff --git a/include/linux/key.h b/include/linux/key.h
index ef596c7af585..2417f789d29b 100644
--- a/include/linux/key.h
+++ b/include/linux/key.h
@@ -22,6 +22,7 @@
22#include <linux/sysctl.h> 22#include <linux/sysctl.h>
23#include <linux/rwsem.h> 23#include <linux/rwsem.h>
24#include <linux/atomic.h> 24#include <linux/atomic.h>
25#include <linux/assoc_array.h>
25 26
26#ifdef __KERNEL__ 27#ifdef __KERNEL__
27#include <linux/uidgid.h> 28#include <linux/uidgid.h>
@@ -196,11 +197,13 @@ struct key {
196 * whatever 197 * whatever
197 */ 198 */
198 union { 199 union {
199 unsigned long value; 200 union {
200 void __rcu *rcudata; 201 unsigned long value;
201 void *data; 202 void __rcu *rcudata;
202 struct keyring_list __rcu *subscriptions; 203 void *data;
203 } payload; 204 } payload;
205 struct assoc_array keys;
206 };
204}; 207};
205 208
206extern struct key *key_alloc(struct key_type *type, 209extern struct key *key_alloc(struct key_type *type,
diff --git a/lib/assoc_array.c b/lib/assoc_array.c
index a0952818f938..17edeaf19180 100644
--- a/lib/assoc_array.c
+++ b/lib/assoc_array.c
@@ -12,6 +12,7 @@
12 */ 12 */
13//#define DEBUG 13//#define DEBUG
14#include <linux/slab.h> 14#include <linux/slab.h>
15#include <linux/err.h>
15#include <linux/assoc_array_priv.h> 16#include <linux/assoc_array_priv.h>
16 17
17/* 18/*
diff --git a/security/keys/Kconfig b/security/keys/Kconfig
index a90d6d300dbd..15e0dfe8c80f 100644
--- a/security/keys/Kconfig
+++ b/security/keys/Kconfig
@@ -4,6 +4,7 @@
4 4
5config KEYS 5config KEYS
6 bool "Enable access key retention support" 6 bool "Enable access key retention support"
7 select ASSOCIATIVE_ARRAY
7 help 8 help
8 This option provides support for retaining authentication tokens and 9 This option provides support for retaining authentication tokens and
9 access keys in the kernel. 10 access keys in the kernel.
diff --git a/security/keys/gc.c b/security/keys/gc.c
index d67c97bb1025..cce621c33dce 100644
--- a/security/keys/gc.c
+++ b/security/keys/gc.c
@@ -130,6 +130,13 @@ void key_gc_keytype(struct key_type *ktype)
130 kleave(""); 130 kleave("");
131} 131}
132 132
133static int key_gc_keyring_func(const void *object, void *iterator_data)
134{
135 const struct key *key = object;
136 time_t *limit = iterator_data;
137 return key_is_dead(key, *limit);
138}
139
133/* 140/*
134 * Garbage collect pointers from a keyring. 141 * Garbage collect pointers from a keyring.
135 * 142 *
@@ -138,10 +145,9 @@ void key_gc_keytype(struct key_type *ktype)
138 */ 145 */
139static void key_gc_keyring(struct key *keyring, time_t limit) 146static void key_gc_keyring(struct key *keyring, time_t limit)
140{ 147{
141 struct keyring_list *klist; 148 int result;
142 int loop;
143 149
144 kenter("%x", key_serial(keyring)); 150 kenter("%x{%s}", keyring->serial, keyring->description ?: "");
145 151
146 if (keyring->flags & ((1 << KEY_FLAG_INVALIDATED) | 152 if (keyring->flags & ((1 << KEY_FLAG_INVALIDATED) |
147 (1 << KEY_FLAG_REVOKED))) 153 (1 << KEY_FLAG_REVOKED)))
@@ -149,27 +155,17 @@ static void key_gc_keyring(struct key *keyring, time_t limit)
149 155
150 /* scan the keyring looking for dead keys */ 156 /* scan the keyring looking for dead keys */
151 rcu_read_lock(); 157 rcu_read_lock();
152 klist = rcu_dereference(keyring->payload.subscriptions); 158 result = assoc_array_iterate(&keyring->keys,
153 if (!klist) 159 key_gc_keyring_func, &limit);
154 goto unlock_dont_gc;
155
156 loop = klist->nkeys;
157 smp_rmb();
158 for (loop--; loop >= 0; loop--) {
159 struct key *key = rcu_dereference(klist->keys[loop]);
160 if (key_is_dead(key, limit))
161 goto do_gc;
162 }
163
164unlock_dont_gc:
165 rcu_read_unlock(); 160 rcu_read_unlock();
161 if (result == true)
162 goto do_gc;
163
166dont_gc: 164dont_gc:
167 kleave(" [no gc]"); 165 kleave(" [no gc]");
168 return; 166 return;
169 167
170do_gc: 168do_gc:
171 rcu_read_unlock();
172
173 keyring_gc(keyring, limit); 169 keyring_gc(keyring, limit);
174 kleave(" [gc]"); 170 kleave(" [gc]");
175} 171}
@@ -392,7 +388,6 @@ found_unreferenced_key:
392 */ 388 */
393found_keyring: 389found_keyring:
394 spin_unlock(&key_serial_lock); 390 spin_unlock(&key_serial_lock);
395 kdebug("scan keyring %d", key->serial);
396 key_gc_keyring(key, limit); 391 key_gc_keyring(key, limit);
397 goto maybe_resched; 392 goto maybe_resched;
398 393
diff --git a/security/keys/internal.h b/security/keys/internal.h
index 73950bf8f875..581c6f688352 100644
--- a/security/keys/internal.h
+++ b/security/keys/internal.h
@@ -90,20 +90,23 @@ extern void key_type_put(struct key_type *ktype);
90 90
91extern int __key_link_begin(struct key *keyring, 91extern int __key_link_begin(struct key *keyring,
92 const struct keyring_index_key *index_key, 92 const struct keyring_index_key *index_key,
93 unsigned long *_prealloc); 93 struct assoc_array_edit **_edit);
94extern int __key_link_check_live_key(struct key *keyring, struct key *key); 94extern int __key_link_check_live_key(struct key *keyring, struct key *key);
95extern void __key_link(struct key *keyring, struct key *key, 95extern void __key_link(struct key *key, struct assoc_array_edit **_edit);
96 unsigned long *_prealloc);
97extern void __key_link_end(struct key *keyring, 96extern void __key_link_end(struct key *keyring,
98 const struct keyring_index_key *index_key, 97 const struct keyring_index_key *index_key,
99 unsigned long prealloc); 98 struct assoc_array_edit *edit);
100 99
101extern key_ref_t __keyring_search_one(key_ref_t keyring_ref, 100extern key_ref_t find_key_to_update(key_ref_t keyring_ref,
102 const struct keyring_index_key *index_key); 101 const struct keyring_index_key *index_key);
103 102
104extern struct key *keyring_search_instkey(struct key *keyring, 103extern struct key *keyring_search_instkey(struct key *keyring,
105 key_serial_t target_id); 104 key_serial_t target_id);
106 105
106extern int iterate_over_keyring(const struct key *keyring,
107 int (*func)(const struct key *key, void *data),
108 void *data);
109
107typedef int (*key_match_func_t)(const struct key *, const void *); 110typedef int (*key_match_func_t)(const struct key *, const void *);
108 111
109struct keyring_search_context { 112struct keyring_search_context {
@@ -119,6 +122,8 @@ struct keyring_search_context {
119#define KEYRING_SEARCH_NO_CHECK_PERM 0x0010 /* Don't check permissions */ 122#define KEYRING_SEARCH_NO_CHECK_PERM 0x0010 /* Don't check permissions */
120#define KEYRING_SEARCH_DETECT_TOO_DEEP 0x0020 /* Give an error on excessive depth */ 123#define KEYRING_SEARCH_DETECT_TOO_DEEP 0x0020 /* Give an error on excessive depth */
121 124
125 int (*iterator)(const void *object, void *iterator_data);
126
122 /* Internal stuff */ 127 /* Internal stuff */
123 int skipped_ret; 128 int skipped_ret;
124 bool possessed; 129 bool possessed;
diff --git a/security/keys/key.c b/security/keys/key.c
index 7d716b82a61e..a819b5c7d4ec 100644
--- a/security/keys/key.c
+++ b/security/keys/key.c
@@ -409,7 +409,7 @@ static int __key_instantiate_and_link(struct key *key,
409 struct key_preparsed_payload *prep, 409 struct key_preparsed_payload *prep,
410 struct key *keyring, 410 struct key *keyring,
411 struct key *authkey, 411 struct key *authkey,
412 unsigned long *_prealloc) 412 struct assoc_array_edit **_edit)
413{ 413{
414 int ret, awaken; 414 int ret, awaken;
415 415
@@ -436,7 +436,7 @@ static int __key_instantiate_and_link(struct key *key,
436 436
437 /* and link it into the destination keyring */ 437 /* and link it into the destination keyring */
438 if (keyring) 438 if (keyring)
439 __key_link(keyring, key, _prealloc); 439 __key_link(key, _edit);
440 440
441 /* disable the authorisation key */ 441 /* disable the authorisation key */
442 if (authkey) 442 if (authkey)
@@ -476,7 +476,7 @@ int key_instantiate_and_link(struct key *key,
476 struct key *authkey) 476 struct key *authkey)
477{ 477{
478 struct key_preparsed_payload prep; 478 struct key_preparsed_payload prep;
479 unsigned long prealloc; 479 struct assoc_array_edit *edit;
480 int ret; 480 int ret;
481 481
482 memset(&prep, 0, sizeof(prep)); 482 memset(&prep, 0, sizeof(prep));
@@ -490,16 +490,15 @@ int key_instantiate_and_link(struct key *key,
490 } 490 }
491 491
492 if (keyring) { 492 if (keyring) {
493 ret = __key_link_begin(keyring, &key->index_key, &prealloc); 493 ret = __key_link_begin(keyring, &key->index_key, &edit);
494 if (ret < 0) 494 if (ret < 0)
495 goto error_free_preparse; 495 goto error_free_preparse;
496 } 496 }
497 497
498 ret = __key_instantiate_and_link(key, &prep, keyring, authkey, 498 ret = __key_instantiate_and_link(key, &prep, keyring, authkey, &edit);
499 &prealloc);
500 499
501 if (keyring) 500 if (keyring)
502 __key_link_end(keyring, &key->index_key, prealloc); 501 __key_link_end(keyring, &key->index_key, edit);
503 502
504error_free_preparse: 503error_free_preparse:
505 if (key->type->preparse) 504 if (key->type->preparse)
@@ -537,7 +536,7 @@ int key_reject_and_link(struct key *key,
537 struct key *keyring, 536 struct key *keyring,
538 struct key *authkey) 537 struct key *authkey)
539{ 538{
540 unsigned long prealloc; 539 struct assoc_array_edit *edit;
541 struct timespec now; 540 struct timespec now;
542 int ret, awaken, link_ret = 0; 541 int ret, awaken, link_ret = 0;
543 542
@@ -548,7 +547,7 @@ int key_reject_and_link(struct key *key,
548 ret = -EBUSY; 547 ret = -EBUSY;
549 548
550 if (keyring) 549 if (keyring)
551 link_ret = __key_link_begin(keyring, &key->index_key, &prealloc); 550 link_ret = __key_link_begin(keyring, &key->index_key, &edit);
552 551
553 mutex_lock(&key_construction_mutex); 552 mutex_lock(&key_construction_mutex);
554 553
@@ -570,7 +569,7 @@ int key_reject_and_link(struct key *key,
570 569
571 /* and link it into the destination keyring */ 570 /* and link it into the destination keyring */
572 if (keyring && link_ret == 0) 571 if (keyring && link_ret == 0)
573 __key_link(keyring, key, &prealloc); 572 __key_link(key, &edit);
574 573
575 /* disable the authorisation key */ 574 /* disable the authorisation key */
576 if (authkey) 575 if (authkey)
@@ -580,7 +579,7 @@ int key_reject_and_link(struct key *key,
580 mutex_unlock(&key_construction_mutex); 579 mutex_unlock(&key_construction_mutex);
581 580
582 if (keyring) 581 if (keyring)
583 __key_link_end(keyring, &key->index_key, prealloc); 582 __key_link_end(keyring, &key->index_key, edit);
584 583
585 /* wake up anyone waiting for a key to be constructed */ 584 /* wake up anyone waiting for a key to be constructed */
586 if (awaken) 585 if (awaken)
@@ -783,8 +782,8 @@ key_ref_t key_create_or_update(key_ref_t keyring_ref,
783 .description = description, 782 .description = description,
784 }; 783 };
785 struct key_preparsed_payload prep; 784 struct key_preparsed_payload prep;
785 struct assoc_array_edit *edit;
786 const struct cred *cred = current_cred(); 786 const struct cred *cred = current_cred();
787 unsigned long prealloc;
788 struct key *keyring, *key = NULL; 787 struct key *keyring, *key = NULL;
789 key_ref_t key_ref; 788 key_ref_t key_ref;
790 int ret; 789 int ret;
@@ -828,7 +827,7 @@ key_ref_t key_create_or_update(key_ref_t keyring_ref,
828 } 827 }
829 index_key.desc_len = strlen(index_key.description); 828 index_key.desc_len = strlen(index_key.description);
830 829
831 ret = __key_link_begin(keyring, &index_key, &prealloc); 830 ret = __key_link_begin(keyring, &index_key, &edit);
832 if (ret < 0) { 831 if (ret < 0) {
833 key_ref = ERR_PTR(ret); 832 key_ref = ERR_PTR(ret);
834 goto error_free_prep; 833 goto error_free_prep;
@@ -847,8 +846,8 @@ key_ref_t key_create_or_update(key_ref_t keyring_ref,
847 * update that instead if possible 846 * update that instead if possible
848 */ 847 */
849 if (index_key.type->update) { 848 if (index_key.type->update) {
850 key_ref = __keyring_search_one(keyring_ref, &index_key); 849 key_ref = find_key_to_update(keyring_ref, &index_key);
851 if (!IS_ERR(key_ref)) 850 if (key_ref)
852 goto found_matching_key; 851 goto found_matching_key;
853 } 852 }
854 853
@@ -874,7 +873,7 @@ key_ref_t key_create_or_update(key_ref_t keyring_ref,
874 } 873 }
875 874
876 /* instantiate it and link it into the target keyring */ 875 /* instantiate it and link it into the target keyring */
877 ret = __key_instantiate_and_link(key, &prep, keyring, NULL, &prealloc); 876 ret = __key_instantiate_and_link(key, &prep, keyring, NULL, &edit);
878 if (ret < 0) { 877 if (ret < 0) {
879 key_put(key); 878 key_put(key);
880 key_ref = ERR_PTR(ret); 879 key_ref = ERR_PTR(ret);
@@ -884,7 +883,7 @@ key_ref_t key_create_or_update(key_ref_t keyring_ref,
884 key_ref = make_key_ref(key, is_key_possessed(keyring_ref)); 883 key_ref = make_key_ref(key, is_key_possessed(keyring_ref));
885 884
886error_link_end: 885error_link_end:
887 __key_link_end(keyring, &index_key, prealloc); 886 __key_link_end(keyring, &index_key, edit);
888error_free_prep: 887error_free_prep:
889 if (index_key.type->preparse) 888 if (index_key.type->preparse)
890 index_key.type->free_preparse(&prep); 889 index_key.type->free_preparse(&prep);
@@ -897,7 +896,7 @@ error:
897 /* we found a matching key, so we're going to try to update it 896 /* we found a matching key, so we're going to try to update it
898 * - we can drop the locks first as we have the key pinned 897 * - we can drop the locks first as we have the key pinned
899 */ 898 */
900 __key_link_end(keyring, &index_key, prealloc); 899 __key_link_end(keyring, &index_key, edit);
901 900
902 key_ref = __key_update(key_ref, &prep); 901 key_ref = __key_update(key_ref, &prep);
903 goto error_free_prep; 902 goto error_free_prep;
diff --git a/security/keys/keyring.c b/security/keys/keyring.c
index eeef1a073db4..f7cdea22214f 100644
--- a/security/keys/keyring.c
+++ b/security/keys/keyring.c
@@ -1,6 +1,6 @@
1/* Keyring handling 1/* Keyring handling
2 * 2 *
3 * Copyright (C) 2004-2005, 2008 Red Hat, Inc. All Rights Reserved. 3 * Copyright (C) 2004-2005, 2008, 2013 Red Hat, Inc. All Rights Reserved.
4 * Written by David Howells (dhowells@redhat.com) 4 * Written by David Howells (dhowells@redhat.com)
5 * 5 *
6 * This program is free software; you can redistribute it and/or 6 * This program is free software; you can redistribute it and/or
@@ -17,25 +17,11 @@
17#include <linux/seq_file.h> 17#include <linux/seq_file.h>
18#include <linux/err.h> 18#include <linux/err.h>
19#include <keys/keyring-type.h> 19#include <keys/keyring-type.h>
20#include <keys/user-type.h>
21#include <linux/assoc_array_priv.h>
20#include <linux/uaccess.h> 22#include <linux/uaccess.h>
21#include "internal.h" 23#include "internal.h"
22 24
23#define rcu_dereference_locked_keyring(keyring) \
24 (rcu_dereference_protected( \
25 (keyring)->payload.subscriptions, \
26 rwsem_is_locked((struct rw_semaphore *)&(keyring)->sem)))
27
28#define rcu_deref_link_locked(klist, index, keyring) \
29 (rcu_dereference_protected( \
30 (klist)->keys[index], \
31 rwsem_is_locked((struct rw_semaphore *)&(keyring)->sem)))
32
33#define MAX_KEYRING_LINKS \
34 min_t(size_t, USHRT_MAX - 1, \
35 ((PAGE_SIZE - sizeof(struct keyring_list)) / sizeof(struct key *)))
36
37#define KEY_LINK_FIXQUOTA 1UL
38
39/* 25/*
40 * When plumbing the depths of the key tree, this sets a hard limit 26 * When plumbing the depths of the key tree, this sets a hard limit
41 * set on how deep we're willing to go. 27 * set on how deep we're willing to go.
@@ -47,6 +33,28 @@
47 */ 33 */
48#define KEYRING_NAME_HASH_SIZE (1 << 5) 34#define KEYRING_NAME_HASH_SIZE (1 << 5)
49 35
36/*
37 * We mark pointers we pass to the associative array with bit 1 set if
38 * they're keyrings and clear otherwise.
39 */
40#define KEYRING_PTR_SUBTYPE 0x2UL
41
42static inline bool keyring_ptr_is_keyring(const struct assoc_array_ptr *x)
43{
44 return (unsigned long)x & KEYRING_PTR_SUBTYPE;
45}
46static inline struct key *keyring_ptr_to_key(const struct assoc_array_ptr *x)
47{
48 void *object = assoc_array_ptr_to_leaf(x);
49 return (struct key *)((unsigned long)object & ~KEYRING_PTR_SUBTYPE);
50}
51static inline void *keyring_key_to_ptr(struct key *key)
52{
53 if (key->type == &key_type_keyring)
54 return (void *)((unsigned long)key | KEYRING_PTR_SUBTYPE);
55 return key;
56}
57
50static struct list_head keyring_name_hash[KEYRING_NAME_HASH_SIZE]; 58static struct list_head keyring_name_hash[KEYRING_NAME_HASH_SIZE];
51static DEFINE_RWLOCK(keyring_name_lock); 59static DEFINE_RWLOCK(keyring_name_lock);
52 60
@@ -67,7 +75,6 @@ static inline unsigned keyring_hash(const char *desc)
67 */ 75 */
68static int keyring_instantiate(struct key *keyring, 76static int keyring_instantiate(struct key *keyring,
69 struct key_preparsed_payload *prep); 77 struct key_preparsed_payload *prep);
70static int keyring_match(const struct key *keyring, const void *criterion);
71static void keyring_revoke(struct key *keyring); 78static void keyring_revoke(struct key *keyring);
72static void keyring_destroy(struct key *keyring); 79static void keyring_destroy(struct key *keyring);
73static void keyring_describe(const struct key *keyring, struct seq_file *m); 80static void keyring_describe(const struct key *keyring, struct seq_file *m);
@@ -76,9 +83,9 @@ static long keyring_read(const struct key *keyring,
76 83
77struct key_type key_type_keyring = { 84struct key_type key_type_keyring = {
78 .name = "keyring", 85 .name = "keyring",
79 .def_datalen = sizeof(struct keyring_list), 86 .def_datalen = 0,
80 .instantiate = keyring_instantiate, 87 .instantiate = keyring_instantiate,
81 .match = keyring_match, 88 .match = user_match,
82 .revoke = keyring_revoke, 89 .revoke = keyring_revoke,
83 .destroy = keyring_destroy, 90 .destroy = keyring_destroy,
84 .describe = keyring_describe, 91 .describe = keyring_describe,
@@ -127,6 +134,7 @@ static int keyring_instantiate(struct key *keyring,
127 134
128 ret = -EINVAL; 135 ret = -EINVAL;
129 if (prep->datalen == 0) { 136 if (prep->datalen == 0) {
137 assoc_array_init(&keyring->keys);
130 /* make the keyring available by name if it has one */ 138 /* make the keyring available by name if it has one */
131 keyring_publish_name(keyring); 139 keyring_publish_name(keyring);
132 ret = 0; 140 ret = 0;
@@ -136,15 +144,226 @@ static int keyring_instantiate(struct key *keyring,
136} 144}
137 145
138/* 146/*
139 * Match keyrings on their name 147 * Multiply 64-bits by 32-bits to 96-bits and fold back to 64-bit. Ideally we'd
148 * fold the carry back too, but that requires inline asm.
149 */
150static u64 mult_64x32_and_fold(u64 x, u32 y)
151{
152 u64 hi = (u64)(u32)(x >> 32) * y;
153 u64 lo = (u64)(u32)(x) * y;
154 return lo + ((u64)(u32)hi << 32) + (u32)(hi >> 32);
155}
156
157/*
158 * Hash a key type and description.
159 */
160static unsigned long hash_key_type_and_desc(const struct keyring_index_key *index_key)
161{
162 const unsigned level_shift = ASSOC_ARRAY_LEVEL_STEP;
163 const unsigned long level_mask = ASSOC_ARRAY_LEVEL_STEP_MASK;
164 const char *description = index_key->description;
165 unsigned long hash, type;
166 u32 piece;
167 u64 acc;
168 int n, desc_len = index_key->desc_len;
169
170 type = (unsigned long)index_key->type;
171
172 acc = mult_64x32_and_fold(type, desc_len + 13);
173 acc = mult_64x32_and_fold(acc, 9207);
174 for (;;) {
175 n = desc_len;
176 if (n <= 0)
177 break;
178 if (n > 4)
179 n = 4;
180 piece = 0;
181 memcpy(&piece, description, n);
182 description += n;
183 desc_len -= n;
184 acc = mult_64x32_and_fold(acc, piece);
185 acc = mult_64x32_and_fold(acc, 9207);
186 }
187
188 /* Fold the hash down to 32 bits if need be. */
189 hash = acc;
190 if (ASSOC_ARRAY_KEY_CHUNK_SIZE == 32)
191 hash ^= acc >> 32;
192
193 /* Squidge all the keyrings into a separate part of the tree to
194 * ordinary keys by making sure the lowest level segment in the hash is
195 * zero for keyrings and non-zero otherwise.
196 */
197 if (index_key->type != &key_type_keyring && (hash & level_mask) == 0)
198 return hash | (hash >> (ASSOC_ARRAY_KEY_CHUNK_SIZE - level_shift)) | 1;
199 if (index_key->type == &key_type_keyring && (hash & level_mask) != 0)
200 return (hash + (hash << level_shift)) & ~level_mask;
201 return hash;
202}
203
204/*
205 * Build the next index key chunk.
206 *
207 * On 32-bit systems the index key is laid out as:
208 *
209 * 0 4 5 9...
210 * hash desclen typeptr desc[]
211 *
212 * On 64-bit systems:
213 *
214 * 0 8 9 17...
215 * hash desclen typeptr desc[]
216 *
217 * We return it one word-sized chunk at a time.
140 */ 218 */
141static int keyring_match(const struct key *keyring, const void *description) 219static unsigned long keyring_get_key_chunk(const void *data, int level)
220{
221 const struct keyring_index_key *index_key = data;
222 unsigned long chunk = 0;
223 long offset = 0;
224 int desc_len = index_key->desc_len, n = sizeof(chunk);
225
226 level /= ASSOC_ARRAY_KEY_CHUNK_SIZE;
227 switch (level) {
228 case 0:
229 return hash_key_type_and_desc(index_key);
230 case 1:
231 return ((unsigned long)index_key->type << 8) | desc_len;
232 case 2:
233 if (desc_len == 0)
234 return (u8)((unsigned long)index_key->type >>
235 (ASSOC_ARRAY_KEY_CHUNK_SIZE - 8));
236 n--;
237 offset = 1;
238 default:
239 offset += sizeof(chunk) - 1;
240 offset += (level - 3) * sizeof(chunk);
241 if (offset >= desc_len)
242 return 0;
243 desc_len -= offset;
244 if (desc_len > n)
245 desc_len = n;
246 offset += desc_len;
247 do {
248 chunk <<= 8;
249 chunk |= ((u8*)index_key->description)[--offset];
250 } while (--desc_len > 0);
251
252 if (level == 2) {
253 chunk <<= 8;
254 chunk |= (u8)((unsigned long)index_key->type >>
255 (ASSOC_ARRAY_KEY_CHUNK_SIZE - 8));
256 }
257 return chunk;
258 }
259}
260
261static unsigned long keyring_get_object_key_chunk(const void *object, int level)
262{
263 const struct key *key = keyring_ptr_to_key(object);
264 return keyring_get_key_chunk(&key->index_key, level);
265}
266
267static bool keyring_compare_object(const void *object, const void *data)
142{ 268{
143 return keyring->description && 269 const struct keyring_index_key *index_key = data;
144 strcmp(keyring->description, description) == 0; 270 const struct key *key = keyring_ptr_to_key(object);
271
272 return key->index_key.type == index_key->type &&
273 key->index_key.desc_len == index_key->desc_len &&
274 memcmp(key->index_key.description, index_key->description,
275 index_key->desc_len) == 0;
145} 276}
146 277
147/* 278/*
279 * Compare the index keys of a pair of objects and determine the bit position
280 * at which they differ - if they differ.
281 */
282static int keyring_diff_objects(const void *_a, const void *_b)
283{
284 const struct key *key_a = keyring_ptr_to_key(_a);
285 const struct key *key_b = keyring_ptr_to_key(_b);
286 const struct keyring_index_key *a = &key_a->index_key;
287 const struct keyring_index_key *b = &key_b->index_key;
288 unsigned long seg_a, seg_b;
289 int level, i;
290
291 level = 0;
292 seg_a = hash_key_type_and_desc(a);
293 seg_b = hash_key_type_and_desc(b);
294 if ((seg_a ^ seg_b) != 0)
295 goto differ;
296
297 /* The number of bits contributed by the hash is controlled by a
298 * constant in the assoc_array headers. Everything else thereafter we
299 * can deal with as being machine word-size dependent.
300 */
301 level += ASSOC_ARRAY_KEY_CHUNK_SIZE / 8;
302 seg_a = a->desc_len;
303 seg_b = b->desc_len;
304 if ((seg_a ^ seg_b) != 0)
305 goto differ;
306
307 /* The next bit may not work on big endian */
308 level++;
309 seg_a = (unsigned long)a->type;
310 seg_b = (unsigned long)b->type;
311 if ((seg_a ^ seg_b) != 0)
312 goto differ;
313
314 level += sizeof(unsigned long);
315 if (a->desc_len == 0)
316 goto same;
317
318 i = 0;
319 if (((unsigned long)a->description | (unsigned long)b->description) &
320 (sizeof(unsigned long) - 1)) {
321 do {
322 seg_a = *(unsigned long *)(a->description + i);
323 seg_b = *(unsigned long *)(b->description + i);
324 if ((seg_a ^ seg_b) != 0)
325 goto differ_plus_i;
326 i += sizeof(unsigned long);
327 } while (i < (a->desc_len & (sizeof(unsigned long) - 1)));
328 }
329
330 for (; i < a->desc_len; i++) {
331 seg_a = *(unsigned char *)(a->description + i);
332 seg_b = *(unsigned char *)(b->description + i);
333 if ((seg_a ^ seg_b) != 0)
334 goto differ_plus_i;
335 }
336
337same:
338 return -1;
339
340differ_plus_i:
341 level += i;
342differ:
343 i = level * 8 + __ffs(seg_a ^ seg_b);
344 return i;
345}
346
347/*
348 * Free an object after stripping the keyring flag off of the pointer.
349 */
350static void keyring_free_object(void *object)
351{
352 key_put(keyring_ptr_to_key(object));
353}
354
355/*
356 * Operations for keyring management by the index-tree routines.
357 */
358static const struct assoc_array_ops keyring_assoc_array_ops = {
359 .get_key_chunk = keyring_get_key_chunk,
360 .get_object_key_chunk = keyring_get_object_key_chunk,
361 .compare_object = keyring_compare_object,
362 .diff_objects = keyring_diff_objects,
363 .free_object = keyring_free_object,
364};
365
366/*
148 * Clean up a keyring when it is destroyed. Unpublish its name if it had one 367 * Clean up a keyring when it is destroyed. Unpublish its name if it had one
149 * and dispose of its data. 368 * and dispose of its data.
150 * 369 *
@@ -155,9 +374,6 @@ static int keyring_match(const struct key *keyring, const void *description)
155 */ 374 */
156static void keyring_destroy(struct key *keyring) 375static void keyring_destroy(struct key *keyring)
157{ 376{
158 struct keyring_list *klist;
159 int loop;
160
161 if (keyring->description) { 377 if (keyring->description) {
162 write_lock(&keyring_name_lock); 378 write_lock(&keyring_name_lock);
163 379
@@ -168,12 +384,7 @@ static void keyring_destroy(struct key *keyring)
168 write_unlock(&keyring_name_lock); 384 write_unlock(&keyring_name_lock);
169 } 385 }
170 386
171 klist = rcu_access_pointer(keyring->payload.subscriptions); 387 assoc_array_destroy(&keyring->keys, &keyring_assoc_array_ops);
172 if (klist) {
173 for (loop = klist->nkeys - 1; loop >= 0; loop--)
174 key_put(rcu_access_pointer(klist->keys[loop]));
175 kfree(klist);
176 }
177} 388}
178 389
179/* 390/*
@@ -181,76 +392,88 @@ static void keyring_destroy(struct key *keyring)
181 */ 392 */
182static void keyring_describe(const struct key *keyring, struct seq_file *m) 393static void keyring_describe(const struct key *keyring, struct seq_file *m)
183{ 394{
184 struct keyring_list *klist;
185
186 if (keyring->description) 395 if (keyring->description)
187 seq_puts(m, keyring->description); 396 seq_puts(m, keyring->description);
188 else 397 else
189 seq_puts(m, "[anon]"); 398 seq_puts(m, "[anon]");
190 399
191 if (key_is_instantiated(keyring)) { 400 if (key_is_instantiated(keyring)) {
192 rcu_read_lock(); 401 if (keyring->keys.nr_leaves_on_tree != 0)
193 klist = rcu_dereference(keyring->payload.subscriptions); 402 seq_printf(m, ": %lu", keyring->keys.nr_leaves_on_tree);
194 if (klist)
195 seq_printf(m, ": %u/%u", klist->nkeys, klist->maxkeys);
196 else 403 else
197 seq_puts(m, ": empty"); 404 seq_puts(m, ": empty");
198 rcu_read_unlock();
199 } 405 }
200} 406}
201 407
408struct keyring_read_iterator_context {
409 size_t qty;
410 size_t count;
411 key_serial_t __user *buffer;
412};
413
414static int keyring_read_iterator(const void *object, void *data)
415{
416 struct keyring_read_iterator_context *ctx = data;
417 const struct key *key = keyring_ptr_to_key(object);
418 int ret;
419
420 kenter("{%s,%d},,{%zu/%zu}",
421 key->type->name, key->serial, ctx->count, ctx->qty);
422
423 if (ctx->count >= ctx->qty)
424 return 1;
425
426 ret = put_user(key->serial, ctx->buffer);
427 if (ret < 0)
428 return ret;
429 ctx->buffer++;
430 ctx->count += sizeof(key->serial);
431 return 0;
432}
433
202/* 434/*
203 * Read a list of key IDs from the keyring's contents in binary form 435 * Read a list of key IDs from the keyring's contents in binary form
204 * 436 *
205 * The keyring's semaphore is read-locked by the caller. 437 * The keyring's semaphore is read-locked by the caller. This prevents someone
438 * from modifying it under us - which could cause us to read key IDs multiple
439 * times.
206 */ 440 */
207static long keyring_read(const struct key *keyring, 441static long keyring_read(const struct key *keyring,
208 char __user *buffer, size_t buflen) 442 char __user *buffer, size_t buflen)
209{ 443{
210 struct keyring_list *klist; 444 struct keyring_read_iterator_context ctx;
211 struct key *key; 445 unsigned long nr_keys;
212 size_t qty, tmp; 446 int ret;
213 int loop, ret;
214 447
215 ret = 0; 448 kenter("{%d},,%zu", key_serial(keyring), buflen);
216 klist = rcu_dereference_locked_keyring(keyring); 449
217 if (klist) { 450 if (buflen & (sizeof(key_serial_t) - 1))
218 /* calculate how much data we could return */ 451 return -EINVAL;
219 qty = klist->nkeys * sizeof(key_serial_t); 452
220 453 nr_keys = keyring->keys.nr_leaves_on_tree;
221 if (buffer && buflen > 0) { 454 if (nr_keys == 0)
222 if (buflen > qty) 455 return 0;
223 buflen = qty;
224
225 /* copy the IDs of the subscribed keys into the
226 * buffer */
227 ret = -EFAULT;
228
229 for (loop = 0; loop < klist->nkeys; loop++) {
230 key = rcu_deref_link_locked(klist, loop,
231 keyring);
232
233 tmp = sizeof(key_serial_t);
234 if (tmp > buflen)
235 tmp = buflen;
236
237 if (copy_to_user(buffer,
238 &key->serial,
239 tmp) != 0)
240 goto error;
241
242 buflen -= tmp;
243 if (buflen == 0)
244 break;
245 buffer += tmp;
246 }
247 }
248 456
249 ret = qty; 457 /* Calculate how much data we could return */
458 ctx.qty = nr_keys * sizeof(key_serial_t);
459
460 if (!buffer || !buflen)
461 return ctx.qty;
462
463 if (buflen > ctx.qty)
464 ctx.qty = buflen;
465
466 /* Copy the IDs of the subscribed keys into the buffer */
467 ctx.buffer = (key_serial_t __user *)buffer;
468 ctx.count = 0;
469 ret = assoc_array_iterate(&keyring->keys, keyring_read_iterator, &ctx);
470 if (ret < 0) {
471 kleave(" = %d [iterate]", ret);
472 return ret;
250 } 473 }
251 474
252error: 475 kleave(" = %zu [ok]", ctx.count);
253 return ret; 476 return ctx.count;
254} 477}
255 478
256/* 479/*
@@ -277,219 +500,360 @@ struct key *keyring_alloc(const char *description, kuid_t uid, kgid_t gid,
277} 500}
278EXPORT_SYMBOL(keyring_alloc); 501EXPORT_SYMBOL(keyring_alloc);
279 502
280/** 503/*
281 * keyring_search_aux - Search a keyring tree for a key matching some criteria 504 * Iteration function to consider each key found.
282 * @keyring_ref: A pointer to the keyring with possession indicator.
283 * @ctx: The keyring search context.
284 *
285 * Search the supplied keyring tree for a key that matches the criteria given.
286 * The root keyring and any linked keyrings must grant Search permission to the
287 * caller to be searchable and keys can only be found if they too grant Search
288 * to the caller. The possession flag on the root keyring pointer controls use
289 * of the possessor bits in permissions checking of the entire tree. In
290 * addition, the LSM gets to forbid keyring searches and key matches.
291 *
292 * The search is performed as a breadth-then-depth search up to the prescribed
293 * limit (KEYRING_SEARCH_MAX_DEPTH).
294 *
295 * Keys are matched to the type provided and are then filtered by the match
296 * function, which is given the description to use in any way it sees fit. The
297 * match function may use any attributes of a key that it wishes to to
298 * determine the match. Normally the match function from the key type would be
299 * used.
300 *
301 * RCU is used to prevent the keyring key lists from disappearing without the
302 * need to take lots of locks.
303 *
304 * Returns a pointer to the found key and increments the key usage count if
305 * successful; -EAGAIN if no matching keys were found, or if expired or revoked
306 * keys were found; -ENOKEY if only negative keys were found; -ENOTDIR if the
307 * specified keyring wasn't a keyring.
308 *
309 * In the case of a successful return, the possession attribute from
310 * @keyring_ref is propagated to the returned key reference.
311 */ 505 */
312key_ref_t keyring_search_aux(key_ref_t keyring_ref, 506static int keyring_search_iterator(const void *object, void *iterator_data)
313 struct keyring_search_context *ctx)
314{ 507{
315 struct { 508 struct keyring_search_context *ctx = iterator_data;
316 /* Need a separate keylist pointer for RCU purposes */ 509 const struct key *key = keyring_ptr_to_key(object);
317 struct key *keyring; 510 unsigned long kflags = key->flags;
318 struct keyring_list *keylist;
319 int kix;
320 } stack[KEYRING_SEARCH_MAX_DEPTH];
321
322 struct keyring_list *keylist;
323 unsigned long kflags;
324 struct key *keyring, *key;
325 key_ref_t key_ref;
326 long err;
327 int sp, nkeys, kix;
328 511
329 keyring = key_ref_to_ptr(keyring_ref); 512 kenter("{%d}", key->serial);
330 ctx->possessed = is_key_possessed(keyring_ref);
331 key_check(keyring);
332 513
333 /* top keyring must have search permission to begin the search */ 514 /* ignore keys not of this type */
334 err = key_task_permission(keyring_ref, ctx->cred, KEY_SEARCH); 515 if (key->type != ctx->index_key.type) {
335 if (err < 0) { 516 kleave(" = 0 [!type]");
336 key_ref = ERR_PTR(err); 517 return 0;
337 goto error;
338 } 518 }
339 519
340 key_ref = ERR_PTR(-ENOTDIR); 520 /* skip invalidated, revoked and expired keys */
341 if (keyring->type != &key_type_keyring) 521 if (ctx->flags & KEYRING_SEARCH_DO_STATE_CHECK) {
342 goto error; 522 if (kflags & ((1 << KEY_FLAG_INVALIDATED) |
523 (1 << KEY_FLAG_REVOKED))) {
524 ctx->result = ERR_PTR(-EKEYREVOKED);
525 kleave(" = %d [invrev]", ctx->skipped_ret);
526 goto skipped;
527 }
343 528
344 rcu_read_lock(); 529 if (key->expiry && ctx->now.tv_sec >= key->expiry) {
530 ctx->result = ERR_PTR(-EKEYEXPIRED);
531 kleave(" = %d [expire]", ctx->skipped_ret);
532 goto skipped;
533 }
534 }
345 535
346 ctx->now = current_kernel_time(); 536 /* keys that don't match */
347 err = -EAGAIN; 537 if (!ctx->match(key, ctx->match_data)) {
348 sp = 0; 538 kleave(" = 0 [!match]");
349 539 return 0;
350 /* firstly we should check to see if this top-level keyring is what we 540 }
351 * are looking for */
352 key_ref = ERR_PTR(-EAGAIN);
353 kflags = keyring->flags;
354 if (keyring->type == ctx->index_key.type &&
355 ctx->match(keyring, ctx->match_data)) {
356 key = keyring;
357 if (ctx->flags & KEYRING_SEARCH_NO_STATE_CHECK)
358 goto found;
359 541
360 /* check it isn't negative and hasn't expired or been 542 /* key must have search permissions */
361 * revoked */ 543 if (!(ctx->flags & KEYRING_SEARCH_NO_CHECK_PERM) &&
362 if (kflags & (1 << KEY_FLAG_REVOKED)) 544 key_task_permission(make_key_ref(key, ctx->possessed),
363 goto error_2; 545 ctx->cred, KEY_SEARCH) < 0) {
364 if (key->expiry && ctx->now.tv_sec >= key->expiry) 546 ctx->result = ERR_PTR(-EACCES);
365 goto error_2; 547 kleave(" = %d [!perm]", ctx->skipped_ret);
366 key_ref = ERR_PTR(key->type_data.reject_error); 548 goto skipped;
367 if (kflags & (1 << KEY_FLAG_NEGATIVE))
368 goto error_2;
369 goto found;
370 } 549 }
371 550
372 /* otherwise, the top keyring must not be revoked, expired, or 551 if (ctx->flags & KEYRING_SEARCH_DO_STATE_CHECK) {
373 * negatively instantiated if we are to search it */ 552 /* we set a different error code if we pass a negative key */
374 key_ref = ERR_PTR(-EAGAIN); 553 if (kflags & (1 << KEY_FLAG_NEGATIVE)) {
375 if (kflags & ((1 << KEY_FLAG_INVALIDATED) | 554 ctx->result = ERR_PTR(key->type_data.reject_error);
376 (1 << KEY_FLAG_REVOKED) | 555 kleave(" = %d [neg]", ctx->skipped_ret);
377 (1 << KEY_FLAG_NEGATIVE)) || 556 goto skipped;
378 (keyring->expiry && ctx->now.tv_sec >= keyring->expiry)) 557 }
379 goto error_2; 558 }
380
381 /* start processing a new keyring */
382descend:
383 kflags = keyring->flags;
384 if (kflags & ((1 << KEY_FLAG_INVALIDATED) |
385 (1 << KEY_FLAG_REVOKED)))
386 goto not_this_keyring;
387 559
388 keylist = rcu_dereference(keyring->payload.subscriptions); 560 /* Found */
389 if (!keylist) 561 ctx->result = make_key_ref(key, ctx->possessed);
390 goto not_this_keyring; 562 kleave(" = 1 [found]");
563 return 1;
391 564
392 /* iterate through the keys in this keyring first */ 565skipped:
393 nkeys = keylist->nkeys; 566 return ctx->skipped_ret;
394 smp_rmb(); 567}
395 for (kix = 0; kix < nkeys; kix++) {
396 key = rcu_dereference(keylist->keys[kix]);
397 kflags = key->flags;
398 568
399 /* ignore keys not of this type */ 569/*
400 if (key->type != ctx->index_key.type) 570 * Search inside a keyring for a key. We can search by walking to it
401 continue; 571 * directly based on its index-key or we can iterate over the entire
572 * tree looking for it, based on the match function.
573 */
574static int search_keyring(struct key *keyring, struct keyring_search_context *ctx)
575{
576 if ((ctx->flags & KEYRING_SEARCH_LOOKUP_TYPE) ==
577 KEYRING_SEARCH_LOOKUP_DIRECT) {
578 const void *object;
579
580 object = assoc_array_find(&keyring->keys,
581 &keyring_assoc_array_ops,
582 &ctx->index_key);
583 return object ? ctx->iterator(object, ctx) : 0;
584 }
585 return assoc_array_iterate(&keyring->keys, ctx->iterator, ctx);
586}
402 587
403 /* skip invalidated, revoked and expired keys */ 588/*
404 if (!(ctx->flags & KEYRING_SEARCH_NO_STATE_CHECK)) { 589 * Search a tree of keyrings that point to other keyrings up to the maximum
405 if (kflags & ((1 << KEY_FLAG_INVALIDATED) | 590 * depth.
406 (1 << KEY_FLAG_REVOKED))) 591 */
407 continue; 592static bool search_nested_keyrings(struct key *keyring,
593 struct keyring_search_context *ctx)
594{
595 struct {
596 struct key *keyring;
597 struct assoc_array_node *node;
598 int slot;
599 } stack[KEYRING_SEARCH_MAX_DEPTH];
408 600
409 if (key->expiry && ctx->now.tv_sec >= key->expiry) 601 struct assoc_array_shortcut *shortcut;
410 continue; 602 struct assoc_array_node *node;
411 } 603 struct assoc_array_ptr *ptr;
604 struct key *key;
605 int sp = 0, slot;
412 606
413 /* keys that don't match */ 607 kenter("{%d},{%s,%s}",
414 if (!ctx->match(key, ctx->match_data)) 608 keyring->serial,
415 continue; 609 ctx->index_key.type->name,
610 ctx->index_key.description);
416 611
417 /* key must have search permissions */ 612 if (ctx->index_key.description)
418 if (key_task_permission(make_key_ref(key, ctx->possessed), 613 ctx->index_key.desc_len = strlen(ctx->index_key.description);
419 ctx->cred, KEY_SEARCH) < 0)
420 continue;
421 614
422 if (ctx->flags & KEYRING_SEARCH_NO_STATE_CHECK) 615 /* Check to see if this top-level keyring is what we are looking for
616 * and whether it is valid or not.
617 */
618 if (ctx->flags & KEYRING_SEARCH_LOOKUP_ITERATE ||
619 keyring_compare_object(keyring, &ctx->index_key)) {
620 ctx->skipped_ret = 2;
621 ctx->flags |= KEYRING_SEARCH_DO_STATE_CHECK;
622 switch (ctx->iterator(keyring_key_to_ptr(keyring), ctx)) {
623 case 1:
423 goto found; 624 goto found;
424 625 case 2:
425 /* we set a different error code if we pass a negative key */ 626 return false;
426 if (kflags & (1 << KEY_FLAG_NEGATIVE)) { 627 default:
427 err = key->type_data.reject_error; 628 break;
428 continue;
429 } 629 }
630 }
430 631
632 ctx->skipped_ret = 0;
633 if (ctx->flags & KEYRING_SEARCH_NO_STATE_CHECK)
634 ctx->flags &= ~KEYRING_SEARCH_DO_STATE_CHECK;
635
636 /* Start processing a new keyring */
637descend_to_keyring:
638 kdebug("descend to %d", keyring->serial);
639 if (keyring->flags & ((1 << KEY_FLAG_INVALIDATED) |
640 (1 << KEY_FLAG_REVOKED)))
641 goto not_this_keyring;
642
643 /* Search through the keys in this keyring before its searching its
644 * subtrees.
645 */
646 if (search_keyring(keyring, ctx))
431 goto found; 647 goto found;
432 }
433 648
434 /* search through the keyrings nested in this one */ 649 /* Then manually iterate through the keyrings nested in this one.
435 kix = 0; 650 *
436ascend: 651 * Start from the root node of the index tree. Because of the way the
437 nkeys = keylist->nkeys; 652 * hash function has been set up, keyrings cluster on the leftmost
438 smp_rmb(); 653 * branch of the root node (root slot 0) or in the root node itself.
439 for (; kix < nkeys; kix++) { 654 * Non-keyrings avoid the leftmost branch of the root entirely (root
440 key = rcu_dereference(keylist->keys[kix]); 655 * slots 1-15).
441 if (key->type != &key_type_keyring) 656 */
442 continue; 657 ptr = ACCESS_ONCE(keyring->keys.root);
658 if (!ptr)
659 goto not_this_keyring;
443 660
444 /* recursively search nested keyrings 661 if (assoc_array_ptr_is_shortcut(ptr)) {
445 * - only search keyrings for which we have search permission 662 /* If the root is a shortcut, either the keyring only contains
663 * keyring pointers (everything clusters behind root slot 0) or
664 * doesn't contain any keyring pointers.
446 */ 665 */
447 if (sp >= KEYRING_SEARCH_MAX_DEPTH) 666 shortcut = assoc_array_ptr_to_shortcut(ptr);
667 smp_read_barrier_depends();
668 if ((shortcut->index_key[0] & ASSOC_ARRAY_FAN_MASK) != 0)
669 goto not_this_keyring;
670
671 ptr = ACCESS_ONCE(shortcut->next_node);
672 node = assoc_array_ptr_to_node(ptr);
673 goto begin_node;
674 }
675
676 node = assoc_array_ptr_to_node(ptr);
677 smp_read_barrier_depends();
678
679 ptr = node->slots[0];
680 if (!assoc_array_ptr_is_meta(ptr))
681 goto begin_node;
682
683descend_to_node:
684 /* Descend to a more distal node in this keyring's content tree and go
685 * through that.
686 */
687 kdebug("descend");
688 if (assoc_array_ptr_is_shortcut(ptr)) {
689 shortcut = assoc_array_ptr_to_shortcut(ptr);
690 smp_read_barrier_depends();
691 ptr = ACCESS_ONCE(shortcut->next_node);
692 BUG_ON(!assoc_array_ptr_is_node(ptr));
693 node = assoc_array_ptr_to_node(ptr);
694 }
695
696begin_node:
697 kdebug("begin_node");
698 smp_read_barrier_depends();
699 slot = 0;
700ascend_to_node:
701 /* Go through the slots in a node */
702 for (; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
703 ptr = ACCESS_ONCE(node->slots[slot]);
704
705 if (assoc_array_ptr_is_meta(ptr) && node->back_pointer)
706 goto descend_to_node;
707
708 if (!keyring_ptr_is_keyring(ptr))
448 continue; 709 continue;
449 710
450 if (key_task_permission(make_key_ref(key, ctx->possessed), 711 key = keyring_ptr_to_key(ptr);
712
713 if (sp >= KEYRING_SEARCH_MAX_DEPTH) {
714 if (ctx->flags & KEYRING_SEARCH_DETECT_TOO_DEEP) {
715 ctx->result = ERR_PTR(-ELOOP);
716 return false;
717 }
718 goto not_this_keyring;
719 }
720
721 /* Search a nested keyring */
722 if (!(ctx->flags & KEYRING_SEARCH_NO_CHECK_PERM) &&
723 key_task_permission(make_key_ref(key, ctx->possessed),
451 ctx->cred, KEY_SEARCH) < 0) 724 ctx->cred, KEY_SEARCH) < 0)
452 continue; 725 continue;
453 726
454 /* stack the current position */ 727 /* stack the current position */
455 stack[sp].keyring = keyring; 728 stack[sp].keyring = keyring;
456 stack[sp].keylist = keylist; 729 stack[sp].node = node;
457 stack[sp].kix = kix; 730 stack[sp].slot = slot;
458 sp++; 731 sp++;
459 732
460 /* begin again with the new keyring */ 733 /* begin again with the new keyring */
461 keyring = key; 734 keyring = key;
462 goto descend; 735 goto descend_to_keyring;
736 }
737
738 /* We've dealt with all the slots in the current node, so now we need
739 * to ascend to the parent and continue processing there.
740 */
741 ptr = ACCESS_ONCE(node->back_pointer);
742 slot = node->parent_slot;
743
744 if (ptr && assoc_array_ptr_is_shortcut(ptr)) {
745 shortcut = assoc_array_ptr_to_shortcut(ptr);
746 smp_read_barrier_depends();
747 ptr = ACCESS_ONCE(shortcut->back_pointer);
748 slot = shortcut->parent_slot;
749 }
750 if (!ptr)
751 goto not_this_keyring;
752 node = assoc_array_ptr_to_node(ptr);
753 smp_read_barrier_depends();
754 slot++;
755
756 /* If we've ascended to the root (zero backpointer), we must have just
757 * finished processing the leftmost branch rather than the root slots -
758 * so there can't be any more keyrings for us to find.
759 */
760 if (node->back_pointer) {
761 kdebug("ascend %d", slot);
762 goto ascend_to_node;
463 } 763 }
464 764
465 /* the keyring we're looking at was disqualified or didn't contain a 765 /* The keyring we're looking at was disqualified or didn't contain a
466 * matching key */ 766 * matching key.
767 */
467not_this_keyring: 768not_this_keyring:
468 if (sp > 0) { 769 kdebug("not_this_keyring %d", sp);
469 /* resume the processing of a keyring higher up in the tree */ 770 if (sp <= 0) {
470 sp--; 771 kleave(" = false");
471 keyring = stack[sp].keyring; 772 return false;
472 keylist = stack[sp].keylist;
473 kix = stack[sp].kix + 1;
474 goto ascend;
475 } 773 }
476 774
477 key_ref = ERR_PTR(err); 775 /* Resume the processing of a keyring higher up in the tree */
478 goto error_2; 776 sp--;
777 keyring = stack[sp].keyring;
778 node = stack[sp].node;
779 slot = stack[sp].slot + 1;
780 kdebug("ascend to %d [%d]", keyring->serial, slot);
781 goto ascend_to_node;
479 782
480 /* we found a viable match */ 783 /* We found a viable match */
481found: 784found:
482 __key_get(key); 785 key = key_ref_to_ptr(ctx->result);
483 key->last_used_at = ctx->now.tv_sec;
484 keyring->last_used_at = ctx->now.tv_sec;
485 while (sp > 0)
486 stack[--sp].keyring->last_used_at = ctx->now.tv_sec;
487 key_check(key); 786 key_check(key);
488 key_ref = make_key_ref(key, ctx->possessed); 787 if (!(ctx->flags & KEYRING_SEARCH_NO_UPDATE_TIME)) {
489error_2: 788 key->last_used_at = ctx->now.tv_sec;
789 keyring->last_used_at = ctx->now.tv_sec;
790 while (sp > 0)
791 stack[--sp].keyring->last_used_at = ctx->now.tv_sec;
792 }
793 kleave(" = true");
794 return true;
795}
796
797/**
798 * keyring_search_aux - Search a keyring tree for a key matching some criteria
799 * @keyring_ref: A pointer to the keyring with possession indicator.
800 * @ctx: The keyring search context.
801 *
802 * Search the supplied keyring tree for a key that matches the criteria given.
803 * The root keyring and any linked keyrings must grant Search permission to the
804 * caller to be searchable and keys can only be found if they too grant Search
805 * to the caller. The possession flag on the root keyring pointer controls use
806 * of the possessor bits in permissions checking of the entire tree. In
807 * addition, the LSM gets to forbid keyring searches and key matches.
808 *
809 * The search is performed as a breadth-then-depth search up to the prescribed
810 * limit (KEYRING_SEARCH_MAX_DEPTH).
811 *
812 * Keys are matched to the type provided and are then filtered by the match
813 * function, which is given the description to use in any way it sees fit. The
814 * match function may use any attributes of a key that it wishes to to
815 * determine the match. Normally the match function from the key type would be
816 * used.
817 *
818 * RCU can be used to prevent the keyring key lists from disappearing without
819 * the need to take lots of locks.
820 *
821 * Returns a pointer to the found key and increments the key usage count if
822 * successful; -EAGAIN if no matching keys were found, or if expired or revoked
823 * keys were found; -ENOKEY if only negative keys were found; -ENOTDIR if the
824 * specified keyring wasn't a keyring.
825 *
826 * In the case of a successful return, the possession attribute from
827 * @keyring_ref is propagated to the returned key reference.
828 */
829key_ref_t keyring_search_aux(key_ref_t keyring_ref,
830 struct keyring_search_context *ctx)
831{
832 struct key *keyring;
833 long err;
834
835 ctx->iterator = keyring_search_iterator;
836 ctx->possessed = is_key_possessed(keyring_ref);
837 ctx->result = ERR_PTR(-EAGAIN);
838
839 keyring = key_ref_to_ptr(keyring_ref);
840 key_check(keyring);
841
842 if (keyring->type != &key_type_keyring)
843 return ERR_PTR(-ENOTDIR);
844
845 if (!(ctx->flags & KEYRING_SEARCH_NO_CHECK_PERM)) {
846 err = key_task_permission(keyring_ref, ctx->cred, KEY_SEARCH);
847 if (err < 0)
848 return ERR_PTR(err);
849 }
850
851 rcu_read_lock();
852 ctx->now = current_kernel_time();
853 if (search_nested_keyrings(keyring, ctx))
854 __key_get(key_ref_to_ptr(ctx->result));
490 rcu_read_unlock(); 855 rcu_read_unlock();
491error: 856 return ctx->result;
492 return key_ref;
493} 857}
494 858
495/** 859/**
@@ -499,7 +863,7 @@ error:
499 * @description: The name of the keyring we want to find. 863 * @description: The name of the keyring we want to find.
500 * 864 *
501 * As keyring_search_aux() above, but using the current task's credentials and 865 * As keyring_search_aux() above, but using the current task's credentials and
502 * type's default matching function. 866 * type's default matching function and preferred search method.
503 */ 867 */
504key_ref_t keyring_search(key_ref_t keyring, 868key_ref_t keyring_search(key_ref_t keyring,
505 struct key_type *type, 869 struct key_type *type,
@@ -523,58 +887,49 @@ key_ref_t keyring_search(key_ref_t keyring,
523EXPORT_SYMBOL(keyring_search); 887EXPORT_SYMBOL(keyring_search);
524 888
525/* 889/*
526 * Search the given keyring only (no recursion). 890 * Search the given keyring for a key that might be updated.
527 * 891 *
528 * The caller must guarantee that the keyring is a keyring and that the 892 * The caller must guarantee that the keyring is a keyring and that the
529 * permission is granted to search the keyring as no check is made here. 893 * permission is granted to modify the keyring as no check is made here. The
530 * 894 * caller must also hold a lock on the keyring semaphore.
531 * RCU is used to make it unnecessary to lock the keyring key list here.
532 * 895 *
533 * Returns a pointer to the found key with usage count incremented if 896 * Returns a pointer to the found key with usage count incremented if
534 * successful and returns -ENOKEY if not found. Revoked and invalidated keys 897 * successful and returns NULL if not found. Revoked and invalidated keys are
535 * are skipped over. 898 * skipped over.
536 * 899 *
537 * If successful, the possession indicator is propagated from the keyring ref 900 * If successful, the possession indicator is propagated from the keyring ref
538 * to the returned key reference. 901 * to the returned key reference.
539 */ 902 */
540key_ref_t __keyring_search_one(key_ref_t keyring_ref, 903key_ref_t find_key_to_update(key_ref_t keyring_ref,
541 const struct keyring_index_key *index_key) 904 const struct keyring_index_key *index_key)
542{ 905{
543 struct keyring_list *klist;
544 struct key *keyring, *key; 906 struct key *keyring, *key;
545 bool possessed; 907 const void *object;
546 int nkeys, loop;
547 908
548 keyring = key_ref_to_ptr(keyring_ref); 909 keyring = key_ref_to_ptr(keyring_ref);
549 possessed = is_key_possessed(keyring_ref);
550 910
551 rcu_read_lock(); 911 kenter("{%d},{%s,%s}",
912 keyring->serial, index_key->type->name, index_key->description);
552 913
553 klist = rcu_dereference(keyring->payload.subscriptions); 914 object = assoc_array_find(&keyring->keys, &keyring_assoc_array_ops,
554 if (klist) { 915 index_key);
555 nkeys = klist->nkeys;
556 smp_rmb();
557 for (loop = 0; loop < nkeys ; loop++) {
558 key = rcu_dereference(klist->keys[loop]);
559 if (key->type == index_key->type &&
560 (!key->type->match ||
561 key->type->match(key, index_key->description)) &&
562 !(key->flags & ((1 << KEY_FLAG_INVALIDATED) |
563 (1 << KEY_FLAG_REVOKED)))
564 )
565 goto found;
566 }
567 }
568 916
569 rcu_read_unlock(); 917 if (object)
570 return ERR_PTR(-ENOKEY); 918 goto found;
919
920 kleave(" = NULL");
921 return NULL;
571 922
572found: 923found:
924 key = keyring_ptr_to_key(object);
925 if (key->flags & ((1 << KEY_FLAG_INVALIDATED) |
926 (1 << KEY_FLAG_REVOKED))) {
927 kleave(" = NULL [x]");
928 return NULL;
929 }
573 __key_get(key); 930 __key_get(key);
574 keyring->last_used_at = key->last_used_at = 931 kleave(" = {%d}", key->serial);
575 current_kernel_time().tv_sec; 932 return make_key_ref(key, is_key_possessed(keyring_ref));
576 rcu_read_unlock();
577 return make_key_ref(key, possessed);
578} 933}
579 934
580/* 935/*
@@ -637,6 +992,19 @@ out:
637 return keyring; 992 return keyring;
638} 993}
639 994
995static int keyring_detect_cycle_iterator(const void *object,
996 void *iterator_data)
997{
998 struct keyring_search_context *ctx = iterator_data;
999 const struct key *key = keyring_ptr_to_key(object);
1000
1001 kenter("{%d}", key->serial);
1002
1003 BUG_ON(key != ctx->match_data);
1004 ctx->result = ERR_PTR(-EDEADLK);
1005 return 1;
1006}
1007
640/* 1008/*
641 * See if a cycle will will be created by inserting acyclic tree B in acyclic 1009 * See if a cycle will will be created by inserting acyclic tree B in acyclic
642 * tree A at the topmost level (ie: as a direct child of A). 1010 * tree A at the topmost level (ie: as a direct child of A).
@@ -646,117 +1014,39 @@ out:
646 */ 1014 */
647static int keyring_detect_cycle(struct key *A, struct key *B) 1015static int keyring_detect_cycle(struct key *A, struct key *B)
648{ 1016{
649 struct { 1017 struct keyring_search_context ctx = {
650 struct keyring_list *keylist; 1018 .index_key = A->index_key,
651 int kix; 1019 .match_data = A,
652 } stack[KEYRING_SEARCH_MAX_DEPTH]; 1020 .iterator = keyring_detect_cycle_iterator,
653 1021 .flags = (KEYRING_SEARCH_LOOKUP_DIRECT |
654 struct keyring_list *keylist; 1022 KEYRING_SEARCH_NO_STATE_CHECK |
655 struct key *subtree, *key; 1023 KEYRING_SEARCH_NO_UPDATE_TIME |
656 int sp, nkeys, kix, ret; 1024 KEYRING_SEARCH_NO_CHECK_PERM |
1025 KEYRING_SEARCH_DETECT_TOO_DEEP),
1026 };
657 1027
658 rcu_read_lock(); 1028 rcu_read_lock();
659 1029 search_nested_keyrings(B, &ctx);
660 ret = -EDEADLK;
661 if (A == B)
662 goto cycle_detected;
663
664 subtree = B;
665 sp = 0;
666
667 /* start processing a new keyring */
668descend:
669 if (test_bit(KEY_FLAG_REVOKED, &subtree->flags))
670 goto not_this_keyring;
671
672 keylist = rcu_dereference(subtree->payload.subscriptions);
673 if (!keylist)
674 goto not_this_keyring;
675 kix = 0;
676
677ascend:
678 /* iterate through the remaining keys in this keyring */
679 nkeys = keylist->nkeys;
680 smp_rmb();
681 for (; kix < nkeys; kix++) {
682 key = rcu_dereference(keylist->keys[kix]);
683
684 if (key == A)
685 goto cycle_detected;
686
687 /* recursively check nested keyrings */
688 if (key->type == &key_type_keyring) {
689 if (sp >= KEYRING_SEARCH_MAX_DEPTH)
690 goto too_deep;
691
692 /* stack the current position */
693 stack[sp].keylist = keylist;
694 stack[sp].kix = kix;
695 sp++;
696
697 /* begin again with the new keyring */
698 subtree = key;
699 goto descend;
700 }
701 }
702
703 /* the keyring we're looking at was disqualified or didn't contain a
704 * matching key */
705not_this_keyring:
706 if (sp > 0) {
707 /* resume the checking of a keyring higher up in the tree */
708 sp--;
709 keylist = stack[sp].keylist;
710 kix = stack[sp].kix + 1;
711 goto ascend;
712 }
713
714 ret = 0; /* no cycles detected */
715
716error:
717 rcu_read_unlock(); 1030 rcu_read_unlock();
718 return ret; 1031 return PTR_ERR(ctx.result) == -EAGAIN ? 0 : PTR_ERR(ctx.result);
719
720too_deep:
721 ret = -ELOOP;
722 goto error;
723
724cycle_detected:
725 ret = -EDEADLK;
726 goto error;
727}
728
729/*
730 * Dispose of a keyring list after the RCU grace period, freeing the unlinked
731 * key
732 */
733static void keyring_unlink_rcu_disposal(struct rcu_head *rcu)
734{
735 struct keyring_list *klist =
736 container_of(rcu, struct keyring_list, rcu);
737
738 if (klist->delkey != USHRT_MAX)
739 key_put(rcu_access_pointer(klist->keys[klist->delkey]));
740 kfree(klist);
741} 1032}
742 1033
743/* 1034/*
744 * Preallocate memory so that a key can be linked into to a keyring. 1035 * Preallocate memory so that a key can be linked into to a keyring.
745 */ 1036 */
746int __key_link_begin(struct key *keyring, const struct keyring_index_key *index_key, 1037int __key_link_begin(struct key *keyring,
747 unsigned long *_prealloc) 1038 const struct keyring_index_key *index_key,
1039 struct assoc_array_edit **_edit)
748 __acquires(&keyring->sem) 1040 __acquires(&keyring->sem)
749 __acquires(&keyring_serialise_link_sem) 1041 __acquires(&keyring_serialise_link_sem)
750{ 1042{
751 struct keyring_list *klist, *nklist; 1043 struct assoc_array_edit *edit;
752 unsigned long prealloc; 1044 int ret;
753 unsigned max;
754 time_t lowest_lru;
755 size_t size;
756 int loop, lru, ret;
757 1045
758 kenter("%d,%s,%s,", 1046 kenter("%d,%s,%s,",
759 key_serial(keyring), index_key->type->name, index_key->description); 1047 keyring->serial, index_key->type->name, index_key->description);
1048
1049 BUG_ON(index_key->desc_len == 0);
760 1050
761 if (keyring->type != &key_type_keyring) 1051 if (keyring->type != &key_type_keyring)
762 return -ENOTDIR; 1052 return -ENOTDIR;
@@ -772,88 +1062,25 @@ int __key_link_begin(struct key *keyring, const struct keyring_index_key *index_
772 if (index_key->type == &key_type_keyring) 1062 if (index_key->type == &key_type_keyring)
773 down_write(&keyring_serialise_link_sem); 1063 down_write(&keyring_serialise_link_sem);
774 1064
775 klist = rcu_dereference_locked_keyring(keyring);
776
777 /* see if there's a matching key we can displace */
778 lru = -1;
779 if (klist && klist->nkeys > 0) {
780 lowest_lru = TIME_T_MAX;
781 for (loop = klist->nkeys - 1; loop >= 0; loop--) {
782 struct key *key = rcu_deref_link_locked(klist, loop,
783 keyring);
784 if (key->type == index_key->type &&
785 strcmp(key->description, index_key->description) == 0) {
786 /* Found a match - we'll replace the link with
787 * one to the new key. We record the slot
788 * position.
789 */
790 klist->delkey = loop;
791 prealloc = 0;
792 goto done;
793 }
794 if (key->last_used_at < lowest_lru) {
795 lowest_lru = key->last_used_at;
796 lru = loop;
797 }
798 }
799 }
800
801 /* If the keyring is full then do an LRU discard */
802 if (klist &&
803 klist->nkeys == klist->maxkeys &&
804 klist->maxkeys >= MAX_KEYRING_LINKS) {
805 kdebug("LRU discard %d\n", lru);
806 klist->delkey = lru;
807 prealloc = 0;
808 goto done;
809 }
810
811 /* check that we aren't going to overrun the user's quota */ 1065 /* check that we aren't going to overrun the user's quota */
812 ret = key_payload_reserve(keyring, 1066 ret = key_payload_reserve(keyring,
813 keyring->datalen + KEYQUOTA_LINK_BYTES); 1067 keyring->datalen + KEYQUOTA_LINK_BYTES);
814 if (ret < 0) 1068 if (ret < 0)
815 goto error_sem; 1069 goto error_sem;
816 1070
817 if (klist && klist->nkeys < klist->maxkeys) { 1071 /* Create an edit script that will insert/replace the key in the
818 /* there's sufficient slack space to append directly */ 1072 * keyring tree.
819 klist->delkey = klist->nkeys; 1073 */
820 prealloc = KEY_LINK_FIXQUOTA; 1074 edit = assoc_array_insert(&keyring->keys,
821 } else { 1075 &keyring_assoc_array_ops,
822 /* grow the key list */ 1076 index_key,
823 max = 4; 1077 NULL);
824 if (klist) { 1078 if (IS_ERR(edit)) {
825 max += klist->maxkeys; 1079 ret = PTR_ERR(edit);
826 if (max > MAX_KEYRING_LINKS) 1080 goto error_quota;
827 max = MAX_KEYRING_LINKS;
828 BUG_ON(max <= klist->maxkeys);
829 }
830
831 size = sizeof(*klist) + sizeof(struct key *) * max;
832
833 ret = -ENOMEM;
834 nklist = kmalloc(size, GFP_KERNEL);
835 if (!nklist)
836 goto error_quota;
837
838 nklist->maxkeys = max;
839 if (klist) {
840 memcpy(nklist->keys, klist->keys,
841 sizeof(struct key *) * klist->nkeys);
842 nklist->delkey = klist->nkeys;
843 nklist->nkeys = klist->nkeys + 1;
844 klist->delkey = USHRT_MAX;
845 } else {
846 nklist->nkeys = 1;
847 nklist->delkey = 0;
848 }
849
850 /* add the key into the new space */
851 RCU_INIT_POINTER(nklist->keys[nklist->delkey], NULL);
852 prealloc = (unsigned long)nklist | KEY_LINK_FIXQUOTA;
853 } 1081 }
854 1082
855done: 1083 *_edit = edit;
856 *_prealloc = prealloc;
857 kleave(" = 0"); 1084 kleave(" = 0");
858 return 0; 1085 return 0;
859 1086
@@ -893,60 +1120,12 @@ int __key_link_check_live_key(struct key *keyring, struct key *key)
893 * holds at most one link to any given key of a particular type+description 1120 * holds at most one link to any given key of a particular type+description
894 * combination. 1121 * combination.
895 */ 1122 */
896void __key_link(struct key *keyring, struct key *key, 1123void __key_link(struct key *key, struct assoc_array_edit **_edit)
897 unsigned long *_prealloc)
898{ 1124{
899 struct keyring_list *klist, *nklist;
900 struct key *discard;
901
902 nklist = (struct keyring_list *)(*_prealloc & ~KEY_LINK_FIXQUOTA);
903 *_prealloc = 0;
904
905 kenter("%d,%d,%p", keyring->serial, key->serial, nklist);
906
907 klist = rcu_dereference_locked_keyring(keyring);
908
909 __key_get(key); 1125 __key_get(key);
910 keyring->last_used_at = key->last_used_at = 1126 assoc_array_insert_set_object(*_edit, keyring_key_to_ptr(key));
911 current_kernel_time().tv_sec; 1127 assoc_array_apply_edit(*_edit);
912 1128 *_edit = NULL;
913 /* there's a matching key we can displace or an empty slot in a newly
914 * allocated list we can fill */
915 if (nklist) {
916 kdebug("reissue %hu/%hu/%hu",
917 nklist->delkey, nklist->nkeys, nklist->maxkeys);
918
919 RCU_INIT_POINTER(nklist->keys[nklist->delkey], key);
920
921 rcu_assign_pointer(keyring->payload.subscriptions, nklist);
922
923 /* dispose of the old keyring list and, if there was one, the
924 * displaced key */
925 if (klist) {
926 kdebug("dispose %hu/%hu/%hu",
927 klist->delkey, klist->nkeys, klist->maxkeys);
928 call_rcu(&klist->rcu, keyring_unlink_rcu_disposal);
929 }
930 } else if (klist->delkey < klist->nkeys) {
931 kdebug("replace %hu/%hu/%hu",
932 klist->delkey, klist->nkeys, klist->maxkeys);
933
934 discard = rcu_dereference_protected(
935 klist->keys[klist->delkey],
936 rwsem_is_locked(&keyring->sem));
937 rcu_assign_pointer(klist->keys[klist->delkey], key);
938 /* The garbage collector will take care of RCU
939 * synchronisation */
940 key_put(discard);
941 } else {
942 /* there's sufficient slack space to append directly */
943 kdebug("append %hu/%hu/%hu",
944 klist->delkey, klist->nkeys, klist->maxkeys);
945
946 RCU_INIT_POINTER(klist->keys[klist->delkey], key);
947 smp_wmb();
948 klist->nkeys++;
949 }
950} 1129}
951 1130
952/* 1131/*
@@ -956,23 +1135,20 @@ void __key_link(struct key *keyring, struct key *key,
956 */ 1135 */
957void __key_link_end(struct key *keyring, 1136void __key_link_end(struct key *keyring,
958 const struct keyring_index_key *index_key, 1137 const struct keyring_index_key *index_key,
959 unsigned long prealloc) 1138 struct assoc_array_edit *edit)
960 __releases(&keyring->sem) 1139 __releases(&keyring->sem)
961 __releases(&keyring_serialise_link_sem) 1140 __releases(&keyring_serialise_link_sem)
962{ 1141{
963 BUG_ON(index_key->type == NULL); 1142 BUG_ON(index_key->type == NULL);
964 BUG_ON(index_key->type->name == NULL); 1143 kenter("%d,%s,", keyring->serial, index_key->type->name);
965 kenter("%d,%s,%lx", keyring->serial, index_key->type->name, prealloc);
966 1144
967 if (index_key->type == &key_type_keyring) 1145 if (index_key->type == &key_type_keyring)
968 up_write(&keyring_serialise_link_sem); 1146 up_write(&keyring_serialise_link_sem);
969 1147
970 if (prealloc) { 1148 if (edit) {
971 if (prealloc & KEY_LINK_FIXQUOTA) 1149 key_payload_reserve(keyring,
972 key_payload_reserve(keyring, 1150 keyring->datalen - KEYQUOTA_LINK_BYTES);
973 keyring->datalen - 1151 assoc_array_cancel_edit(edit);
974 KEYQUOTA_LINK_BYTES);
975 kfree((struct keyring_list *)(prealloc & ~KEY_LINK_FIXQUOTA));
976 } 1152 }
977 up_write(&keyring->sem); 1153 up_write(&keyring->sem);
978} 1154}
@@ -999,20 +1175,24 @@ void __key_link_end(struct key *keyring,
999 */ 1175 */
1000int key_link(struct key *keyring, struct key *key) 1176int key_link(struct key *keyring, struct key *key)
1001{ 1177{
1002 unsigned long prealloc; 1178 struct assoc_array_edit *edit;
1003 int ret; 1179 int ret;
1004 1180
1181 kenter("{%d,%d}", keyring->serial, atomic_read(&keyring->usage));
1182
1005 key_check(keyring); 1183 key_check(keyring);
1006 key_check(key); 1184 key_check(key);
1007 1185
1008 ret = __key_link_begin(keyring, &key->index_key, &prealloc); 1186 ret = __key_link_begin(keyring, &key->index_key, &edit);
1009 if (ret == 0) { 1187 if (ret == 0) {
1188 kdebug("begun {%d,%d}", keyring->serial, atomic_read(&keyring->usage));
1010 ret = __key_link_check_live_key(keyring, key); 1189 ret = __key_link_check_live_key(keyring, key);
1011 if (ret == 0) 1190 if (ret == 0)
1012 __key_link(keyring, key, &prealloc); 1191 __key_link(key, &edit);
1013 __key_link_end(keyring, &key->index_key, prealloc); 1192 __key_link_end(keyring, &key->index_key, edit);
1014 } 1193 }
1015 1194
1195 kleave(" = %d {%d,%d}", ret, keyring->serial, atomic_read(&keyring->usage));
1016 return ret; 1196 return ret;
1017} 1197}
1018EXPORT_SYMBOL(key_link); 1198EXPORT_SYMBOL(key_link);
@@ -1036,90 +1216,36 @@ EXPORT_SYMBOL(key_link);
1036 */ 1216 */
1037int key_unlink(struct key *keyring, struct key *key) 1217int key_unlink(struct key *keyring, struct key *key)
1038{ 1218{
1039 struct keyring_list *klist, *nklist; 1219 struct assoc_array_edit *edit;
1040 int loop, ret; 1220 int ret;
1041 1221
1042 key_check(keyring); 1222 key_check(keyring);
1043 key_check(key); 1223 key_check(key);
1044 1224
1045 ret = -ENOTDIR;
1046 if (keyring->type != &key_type_keyring) 1225 if (keyring->type != &key_type_keyring)
1047 goto error; 1226 return -ENOTDIR;
1048 1227
1049 down_write(&keyring->sem); 1228 down_write(&keyring->sem);
1050 1229
1051 klist = rcu_dereference_locked_keyring(keyring); 1230 edit = assoc_array_delete(&keyring->keys, &keyring_assoc_array_ops,
1052 if (klist) { 1231 &key->index_key);
1053 /* search the keyring for the key */ 1232 if (IS_ERR(edit)) {
1054 for (loop = 0; loop < klist->nkeys; loop++) 1233 ret = PTR_ERR(edit);
1055 if (rcu_access_pointer(klist->keys[loop]) == key) 1234 goto error;
1056 goto key_is_present;
1057 } 1235 }
1058
1059 up_write(&keyring->sem);
1060 ret = -ENOENT; 1236 ret = -ENOENT;
1061 goto error; 1237 if (edit == NULL)
1062 1238 goto error;
1063key_is_present:
1064 /* we need to copy the key list for RCU purposes */
1065 nklist = kmalloc(sizeof(*klist) +
1066 sizeof(struct key *) * klist->maxkeys,
1067 GFP_KERNEL);
1068 if (!nklist)
1069 goto nomem;
1070 nklist->maxkeys = klist->maxkeys;
1071 nklist->nkeys = klist->nkeys - 1;
1072
1073 if (loop > 0)
1074 memcpy(&nklist->keys[0],
1075 &klist->keys[0],
1076 loop * sizeof(struct key *));
1077
1078 if (loop < nklist->nkeys)
1079 memcpy(&nklist->keys[loop],
1080 &klist->keys[loop + 1],
1081 (nklist->nkeys - loop) * sizeof(struct key *));
1082
1083 /* adjust the user's quota */
1084 key_payload_reserve(keyring,
1085 keyring->datalen - KEYQUOTA_LINK_BYTES);
1086
1087 rcu_assign_pointer(keyring->payload.subscriptions, nklist);
1088
1089 up_write(&keyring->sem);
1090
1091 /* schedule for later cleanup */
1092 klist->delkey = loop;
1093 call_rcu(&klist->rcu, keyring_unlink_rcu_disposal);
1094 1239
1240 assoc_array_apply_edit(edit);
1095 ret = 0; 1241 ret = 0;
1096 1242
1097error: 1243error:
1098 return ret;
1099nomem:
1100 ret = -ENOMEM;
1101 up_write(&keyring->sem); 1244 up_write(&keyring->sem);
1102 goto error; 1245 return ret;
1103} 1246}
1104EXPORT_SYMBOL(key_unlink); 1247EXPORT_SYMBOL(key_unlink);
1105 1248
1106/*
1107 * Dispose of a keyring list after the RCU grace period, releasing the keys it
1108 * links to.
1109 */
1110static void keyring_clear_rcu_disposal(struct rcu_head *rcu)
1111{
1112 struct keyring_list *klist;
1113 int loop;
1114
1115 klist = container_of(rcu, struct keyring_list, rcu);
1116
1117 for (loop = klist->nkeys - 1; loop >= 0; loop--)
1118 key_put(rcu_access_pointer(klist->keys[loop]));
1119
1120 kfree(klist);
1121}
1122
1123/** 1249/**
1124 * keyring_clear - Clear a keyring 1250 * keyring_clear - Clear a keyring
1125 * @keyring: The keyring to clear. 1251 * @keyring: The keyring to clear.
@@ -1130,33 +1256,25 @@ static void keyring_clear_rcu_disposal(struct rcu_head *rcu)
1130 */ 1256 */
1131int keyring_clear(struct key *keyring) 1257int keyring_clear(struct key *keyring)
1132{ 1258{
1133 struct keyring_list *klist; 1259 struct assoc_array_edit *edit;
1134 int ret; 1260 int ret;
1135 1261
1136 ret = -ENOTDIR; 1262 if (keyring->type != &key_type_keyring)
1137 if (keyring->type == &key_type_keyring) { 1263 return -ENOTDIR;
1138 /* detach the pointer block with the locks held */
1139 down_write(&keyring->sem);
1140
1141 klist = rcu_dereference_locked_keyring(keyring);
1142 if (klist) {
1143 /* adjust the quota */
1144 key_payload_reserve(keyring,
1145 sizeof(struct keyring_list));
1146
1147 rcu_assign_pointer(keyring->payload.subscriptions,
1148 NULL);
1149 }
1150
1151 up_write(&keyring->sem);
1152 1264
1153 /* free the keys after the locks have been dropped */ 1265 down_write(&keyring->sem);
1154 if (klist)
1155 call_rcu(&klist->rcu, keyring_clear_rcu_disposal);
1156 1266
1267 edit = assoc_array_clear(&keyring->keys, &keyring_assoc_array_ops);
1268 if (IS_ERR(edit)) {
1269 ret = PTR_ERR(edit);
1270 } else {
1271 if (edit)
1272 assoc_array_apply_edit(edit);
1273 key_payload_reserve(keyring, 0);
1157 ret = 0; 1274 ret = 0;
1158 } 1275 }
1159 1276
1277 up_write(&keyring->sem);
1160 return ret; 1278 return ret;
1161} 1279}
1162EXPORT_SYMBOL(keyring_clear); 1280EXPORT_SYMBOL(keyring_clear);
@@ -1168,17 +1286,25 @@ EXPORT_SYMBOL(keyring_clear);
1168 */ 1286 */
1169static void keyring_revoke(struct key *keyring) 1287static void keyring_revoke(struct key *keyring)
1170{ 1288{
1171 struct keyring_list *klist; 1289 struct assoc_array_edit *edit;
1172 1290
1173 klist = rcu_dereference_locked_keyring(keyring); 1291 edit = assoc_array_clear(&keyring->keys, &keyring_assoc_array_ops);
1292 if (!IS_ERR(edit)) {
1293 if (edit)
1294 assoc_array_apply_edit(edit);
1295 key_payload_reserve(keyring, 0);
1296 }
1297}
1174 1298
1175 /* adjust the quota */ 1299static bool gc_iterator(void *object, void *iterator_data)
1176 key_payload_reserve(keyring, 0); 1300{
1301 struct key *key = keyring_ptr_to_key(object);
1302 time_t *limit = iterator_data;
1177 1303
1178 if (klist) { 1304 if (key_is_dead(key, *limit))
1179 rcu_assign_pointer(keyring->payload.subscriptions, NULL); 1305 return false;
1180 call_rcu(&klist->rcu, keyring_clear_rcu_disposal); 1306 key_get(key);
1181 } 1307 return true;
1182} 1308}
1183 1309
1184/* 1310/*
@@ -1191,88 +1317,12 @@ static void keyring_revoke(struct key *keyring)
1191 */ 1317 */
1192void keyring_gc(struct key *keyring, time_t limit) 1318void keyring_gc(struct key *keyring, time_t limit)
1193{ 1319{
1194 struct keyring_list *klist, *new;
1195 struct key *key;
1196 int loop, keep, max;
1197
1198 kenter("{%x,%s}", key_serial(keyring), keyring->description); 1320 kenter("{%x,%s}", key_serial(keyring), keyring->description);
1199 1321
1200 down_write(&keyring->sem); 1322 down_write(&keyring->sem);
1201 1323 assoc_array_gc(&keyring->keys, &keyring_assoc_array_ops,
1202 klist = rcu_dereference_locked_keyring(keyring); 1324 gc_iterator, &limit);
1203 if (!klist)
1204 goto no_klist;
1205
1206 /* work out how many subscriptions we're keeping */
1207 keep = 0;
1208 for (loop = klist->nkeys - 1; loop >= 0; loop--)
1209 if (!key_is_dead(rcu_deref_link_locked(klist, loop, keyring),
1210 limit))
1211 keep++;
1212
1213 if (keep == klist->nkeys)
1214 goto just_return;
1215
1216 /* allocate a new keyring payload */
1217 max = roundup(keep, 4);
1218 new = kmalloc(sizeof(struct keyring_list) + max * sizeof(struct key *),
1219 GFP_KERNEL);
1220 if (!new)
1221 goto nomem;
1222 new->maxkeys = max;
1223 new->nkeys = 0;
1224 new->delkey = 0;
1225
1226 /* install the live keys
1227 * - must take care as expired keys may be updated back to life
1228 */
1229 keep = 0;
1230 for (loop = klist->nkeys - 1; loop >= 0; loop--) {
1231 key = rcu_deref_link_locked(klist, loop, keyring);
1232 if (!key_is_dead(key, limit)) {
1233 if (keep >= max)
1234 goto discard_new;
1235 RCU_INIT_POINTER(new->keys[keep++], key_get(key));
1236 }
1237 }
1238 new->nkeys = keep;
1239
1240 /* adjust the quota */
1241 key_payload_reserve(keyring,
1242 sizeof(struct keyring_list) +
1243 KEYQUOTA_LINK_BYTES * keep);
1244
1245 if (keep == 0) {
1246 rcu_assign_pointer(keyring->payload.subscriptions, NULL);
1247 kfree(new);
1248 } else {
1249 rcu_assign_pointer(keyring->payload.subscriptions, new);
1250 }
1251
1252 up_write(&keyring->sem);
1253
1254 call_rcu(&klist->rcu, keyring_clear_rcu_disposal);
1255 kleave(" [yes]");
1256 return;
1257
1258discard_new:
1259 new->nkeys = keep;
1260 keyring_clear_rcu_disposal(&new->rcu);
1261 up_write(&keyring->sem); 1325 up_write(&keyring->sem);
1262 kleave(" [discard]");
1263 return;
1264 1326
1265just_return: 1327 kleave("");
1266 up_write(&keyring->sem);
1267 kleave(" [no dead]");
1268 return;
1269
1270no_klist:
1271 up_write(&keyring->sem);
1272 kleave(" [no_klist]");
1273 return;
1274
1275nomem:
1276 up_write(&keyring->sem);
1277 kleave(" [oom]");
1278} 1328}
diff --git a/security/keys/request_key.c b/security/keys/request_key.c
index ab75df4745af..df94827103d0 100644
--- a/security/keys/request_key.c
+++ b/security/keys/request_key.c
@@ -351,7 +351,7 @@ static int construct_alloc_key(struct keyring_search_context *ctx,
351 struct key_user *user, 351 struct key_user *user,
352 struct key **_key) 352 struct key **_key)
353{ 353{
354 unsigned long prealloc; 354 struct assoc_array_edit *edit;
355 struct key *key; 355 struct key *key;
356 key_perm_t perm; 356 key_perm_t perm;
357 key_ref_t key_ref; 357 key_ref_t key_ref;
@@ -380,7 +380,7 @@ static int construct_alloc_key(struct keyring_search_context *ctx,
380 set_bit(KEY_FLAG_USER_CONSTRUCT, &key->flags); 380 set_bit(KEY_FLAG_USER_CONSTRUCT, &key->flags);
381 381
382 if (dest_keyring) { 382 if (dest_keyring) {
383 ret = __key_link_begin(dest_keyring, &ctx->index_key, &prealloc); 383 ret = __key_link_begin(dest_keyring, &ctx->index_key, &edit);
384 if (ret < 0) 384 if (ret < 0)
385 goto link_prealloc_failed; 385 goto link_prealloc_failed;
386 } 386 }
@@ -395,11 +395,11 @@ static int construct_alloc_key(struct keyring_search_context *ctx,
395 goto key_already_present; 395 goto key_already_present;
396 396
397 if (dest_keyring) 397 if (dest_keyring)
398 __key_link(dest_keyring, key, &prealloc); 398 __key_link(key, &edit);
399 399
400 mutex_unlock(&key_construction_mutex); 400 mutex_unlock(&key_construction_mutex);
401 if (dest_keyring) 401 if (dest_keyring)
402 __key_link_end(dest_keyring, &ctx->index_key, prealloc); 402 __key_link_end(dest_keyring, &ctx->index_key, edit);
403 mutex_unlock(&user->cons_lock); 403 mutex_unlock(&user->cons_lock);
404 *_key = key; 404 *_key = key;
405 kleave(" = 0 [%d]", key_serial(key)); 405 kleave(" = 0 [%d]", key_serial(key));
@@ -414,8 +414,8 @@ key_already_present:
414 if (dest_keyring) { 414 if (dest_keyring) {
415 ret = __key_link_check_live_key(dest_keyring, key); 415 ret = __key_link_check_live_key(dest_keyring, key);
416 if (ret == 0) 416 if (ret == 0)
417 __key_link(dest_keyring, key, &prealloc); 417 __key_link(key, &edit);
418 __key_link_end(dest_keyring, &ctx->index_key, prealloc); 418 __key_link_end(dest_keyring, &ctx->index_key, edit);
419 if (ret < 0) 419 if (ret < 0)
420 goto link_check_failed; 420 goto link_check_failed;
421 } 421 }
generated by cgit v1.2.2 (git 2.25.0) at 2026-04-18 02:45:10 -0400