Merge branch 'next' into for-linus
[linux-3.10.git] / security / keys / keyring.c
1 /* Keyring handling
2  *
3  * Copyright (C) 2004-2005, 2008 Red Hat, Inc. All Rights Reserved.
4  * Written by David Howells (dhowells@redhat.com)
5  *
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.
10  */
11
12 #include <linux/module.h>
13 #include <linux/init.h>
14 #include <linux/sched.h>
15 #include <linux/slab.h>
16 #include <linux/security.h>
17 #include <linux/seq_file.h>
18 #include <linux/err.h>
19 #include <keys/keyring-type.h>
20 #include <linux/uaccess.h>
21 #include "internal.h"
22
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 KEY_LINK_FIXQUOTA 1UL
29
30 /*
31  * When plumbing the depths of the key tree, this sets a hard limit
32  * set on how deep we're willing to go.
33  */
34 #define KEYRING_SEARCH_MAX_DEPTH 6
35
36 /*
37  * We keep all named keyrings in a hash to speed looking them up.
38  */
39 #define KEYRING_NAME_HASH_SIZE  (1 << 5)
40
41 static struct list_head keyring_name_hash[KEYRING_NAME_HASH_SIZE];
42 static DEFINE_RWLOCK(keyring_name_lock);
43
44 static inline unsigned keyring_hash(const char *desc)
45 {
46         unsigned bucket = 0;
47
48         for (; *desc; desc++)
49                 bucket += (unsigned char)*desc;
50
51         return bucket & (KEYRING_NAME_HASH_SIZE - 1);
52 }
53
54 /*
55  * The keyring key type definition.  Keyrings are simply keys of this type and
56  * can be treated as ordinary keys in addition to having their own special
57  * operations.
58  */
59 static int keyring_instantiate(struct key *keyring,
60                                const void *data, size_t datalen);
61 static int keyring_match(const struct key *keyring, const void *criterion);
62 static void keyring_revoke(struct key *keyring);
63 static void keyring_destroy(struct key *keyring);
64 static void keyring_describe(const struct key *keyring, struct seq_file *m);
65 static long keyring_read(const struct key *keyring,
66                          char __user *buffer, size_t buflen);
67
68 struct key_type key_type_keyring = {
69         .name           = "keyring",
70         .def_datalen    = sizeof(struct keyring_list),
71         .instantiate    = keyring_instantiate,
72         .match          = keyring_match,
73         .revoke         = keyring_revoke,
74         .destroy        = keyring_destroy,
75         .describe       = keyring_describe,
76         .read           = keyring_read,
77 };
78 EXPORT_SYMBOL(key_type_keyring);
79
80 /*
81  * Semaphore to serialise link/link calls to prevent two link calls in parallel
82  * introducing a cycle.
83  */
84 static DECLARE_RWSEM(keyring_serialise_link_sem);
85
86 /*
87  * Publish the name of a keyring so that it can be found by name (if it has
88  * one).
89  */
90 static void keyring_publish_name(struct key *keyring)
91 {
92         int bucket;
93
94         if (keyring->description) {
95                 bucket = keyring_hash(keyring->description);
96
97                 write_lock(&keyring_name_lock);
98
99                 if (!keyring_name_hash[bucket].next)
100                         INIT_LIST_HEAD(&keyring_name_hash[bucket]);
101
102                 list_add_tail(&keyring->type_data.link,
103                               &keyring_name_hash[bucket]);
104
105                 write_unlock(&keyring_name_lock);
106         }
107 }
108
109 /*
110  * Initialise a keyring.
111  *
112  * Returns 0 on success, -EINVAL if given any data.
113  */
114 static int keyring_instantiate(struct key *keyring,
115                                const void *data, size_t datalen)
116 {
117         int ret;
118
119         ret = -EINVAL;
120         if (datalen == 0) {
121                 /* make the keyring available by name if it has one */
122                 keyring_publish_name(keyring);
123                 ret = 0;
124         }
125
126         return ret;
127 }
128
129 /*
130  * Match keyrings on their name
131  */
132 static int keyring_match(const struct key *keyring, const void *description)
133 {
134         return keyring->description &&
135                 strcmp(keyring->description, description) == 0;
136 }
137
138 /*
139  * Clean up a keyring when it is destroyed.  Unpublish its name if it had one
140  * and dispose of its data.
141  */
142 static void keyring_destroy(struct key *keyring)
143 {
144         struct keyring_list *klist;
145         int loop;
146
147         if (keyring->description) {
148                 write_lock(&keyring_name_lock);
149
150                 if (keyring->type_data.link.next != NULL &&
151                     !list_empty(&keyring->type_data.link))
152                         list_del(&keyring->type_data.link);
153
154                 write_unlock(&keyring_name_lock);
155         }
156
157         klist = rcu_dereference_check(keyring->payload.subscriptions,
158                                       rcu_read_lock_held() ||
159                                       atomic_read(&keyring->usage) == 0);
160         if (klist) {
161                 for (loop = klist->nkeys - 1; loop >= 0; loop--)
162                         key_put(klist->keys[loop]);
163                 kfree(klist);
164         }
165 }
166
167 /*
168  * Describe a keyring for /proc.
169  */
170 static void keyring_describe(const struct key *keyring, struct seq_file *m)
171 {
172         struct keyring_list *klist;
173
174         if (keyring->description)
175                 seq_puts(m, keyring->description);
176         else
177                 seq_puts(m, "[anon]");
178
179         if (key_is_instantiated(keyring)) {
180                 rcu_read_lock();
181                 klist = rcu_dereference(keyring->payload.subscriptions);
182                 if (klist)
183                         seq_printf(m, ": %u/%u", klist->nkeys, klist->maxkeys);
184                 else
185                         seq_puts(m, ": empty");
186                 rcu_read_unlock();
187         }
188 }
189
190 /*
191  * Read a list of key IDs from the keyring's contents in binary form
192  *
193  * The keyring's semaphore is read-locked by the caller.
194  */
195 static long keyring_read(const struct key *keyring,
196                          char __user *buffer, size_t buflen)
197 {
198         struct keyring_list *klist;
199         struct key *key;
200         size_t qty, tmp;
201         int loop, ret;
202
203         ret = 0;
204         klist = rcu_dereference_locked_keyring(keyring);
205         if (klist) {
206                 /* calculate how much data we could return */
207                 qty = klist->nkeys * sizeof(key_serial_t);
208
209                 if (buffer && buflen > 0) {
210                         if (buflen > qty)
211                                 buflen = qty;
212
213                         /* copy the IDs of the subscribed keys into the
214                          * buffer */
215                         ret = -EFAULT;
216
217                         for (loop = 0; loop < klist->nkeys; loop++) {
218                                 key = klist->keys[loop];
219
220                                 tmp = sizeof(key_serial_t);
221                                 if (tmp > buflen)
222                                         tmp = buflen;
223
224                                 if (copy_to_user(buffer,
225                                                  &key->serial,
226                                                  tmp) != 0)
227                                         goto error;
228
229                                 buflen -= tmp;
230                                 if (buflen == 0)
231                                         break;
232                                 buffer += tmp;
233                         }
234                 }
235
236                 ret = qty;
237         }
238
239 error:
240         return ret;
241 }
242
243 /*
244  * Allocate a keyring and link into the destination keyring.
245  */
246 struct key *keyring_alloc(const char *description, uid_t uid, gid_t gid,
247                           const struct cred *cred, unsigned long flags,
248                           struct key *dest)
249 {
250         struct key *keyring;
251         int ret;
252
253         keyring = key_alloc(&key_type_keyring, description,
254                             uid, gid, cred,
255                             (KEY_POS_ALL & ~KEY_POS_SETATTR) | KEY_USR_ALL,
256                             flags);
257
258         if (!IS_ERR(keyring)) {
259                 ret = key_instantiate_and_link(keyring, NULL, 0, dest, NULL);
260                 if (ret < 0) {
261                         key_put(keyring);
262                         keyring = ERR_PTR(ret);
263                 }
264         }
265
266         return keyring;
267 }
268
269 /**
270  * keyring_search_aux - Search a keyring tree for a key matching some criteria
271  * @keyring_ref: A pointer to the keyring with possession indicator.
272  * @cred: The credentials to use for permissions checks.
273  * @type: The type of key to search for.
274  * @description: Parameter for @match.
275  * @match: Function to rule on whether or not a key is the one required.
276  * @no_state_check: Don't check if a matching key is bad
277  *
278  * Search the supplied keyring tree for a key that matches the criteria given.
279  * The root keyring and any linked keyrings must grant Search permission to the
280  * caller to be searchable and keys can only be found if they too grant Search
281  * to the caller. The possession flag on the root keyring pointer controls use
282  * of the possessor bits in permissions checking of the entire tree.  In
283  * addition, the LSM gets to forbid keyring searches and key matches.
284  *
285  * The search is performed as a breadth-then-depth search up to the prescribed
286  * limit (KEYRING_SEARCH_MAX_DEPTH).
287  *
288  * Keys are matched to the type provided and are then filtered by the match
289  * function, which is given the description to use in any way it sees fit.  The
290  * match function may use any attributes of a key that it wishes to to
291  * determine the match.  Normally the match function from the key type would be
292  * used.
293  *
294  * RCU is used to prevent the keyring key lists from disappearing without the
295  * need to take lots of locks.
296  *
297  * Returns a pointer to the found key and increments the key usage count if
298  * successful; -EAGAIN if no matching keys were found, or if expired or revoked
299  * keys were found; -ENOKEY if only negative keys were found; -ENOTDIR if the
300  * specified keyring wasn't a keyring.
301  *
302  * In the case of a successful return, the possession attribute from
303  * @keyring_ref is propagated to the returned key reference.
304  */
305 key_ref_t keyring_search_aux(key_ref_t keyring_ref,
306                              const struct cred *cred,
307                              struct key_type *type,
308                              const void *description,
309                              key_match_func_t match,
310                              bool no_state_check)
311 {
312         struct {
313                 struct keyring_list *keylist;
314                 int kix;
315         } stack[KEYRING_SEARCH_MAX_DEPTH];
316
317         struct keyring_list *keylist;
318         struct timespec now;
319         unsigned long possessed, kflags;
320         struct key *keyring, *key;
321         key_ref_t key_ref;
322         long err;
323         int sp, kix;
324
325         keyring = key_ref_to_ptr(keyring_ref);
326         possessed = is_key_possessed(keyring_ref);
327         key_check(keyring);
328
329         /* top keyring must have search permission to begin the search */
330         err = key_task_permission(keyring_ref, cred, KEY_SEARCH);
331         if (err < 0) {
332                 key_ref = ERR_PTR(err);
333                 goto error;
334         }
335
336         key_ref = ERR_PTR(-ENOTDIR);
337         if (keyring->type != &key_type_keyring)
338                 goto error;
339
340         rcu_read_lock();
341
342         now = current_kernel_time();
343         err = -EAGAIN;
344         sp = 0;
345
346         /* firstly we should check to see if this top-level keyring is what we
347          * are looking for */
348         key_ref = ERR_PTR(-EAGAIN);
349         kflags = keyring->flags;
350         if (keyring->type == type && match(keyring, description)) {
351                 key = keyring;
352                 if (no_state_check)
353                         goto found;
354
355                 /* check it isn't negative and hasn't expired or been
356                  * revoked */
357                 if (kflags & (1 << KEY_FLAG_REVOKED))
358                         goto error_2;
359                 if (key->expiry && now.tv_sec >= key->expiry)
360                         goto error_2;
361                 key_ref = ERR_PTR(key->type_data.reject_error);
362                 if (kflags & (1 << KEY_FLAG_NEGATIVE))
363                         goto error_2;
364                 goto found;
365         }
366
367         /* otherwise, the top keyring must not be revoked, expired, or
368          * negatively instantiated if we are to search it */
369         key_ref = ERR_PTR(-EAGAIN);
370         if (kflags & ((1 << KEY_FLAG_REVOKED) | (1 << KEY_FLAG_NEGATIVE)) ||
371             (keyring->expiry && now.tv_sec >= keyring->expiry))
372                 goto error_2;
373
374         /* start processing a new keyring */
375 descend:
376         if (test_bit(KEY_FLAG_REVOKED, &keyring->flags))
377                 goto not_this_keyring;
378
379         keylist = rcu_dereference(keyring->payload.subscriptions);
380         if (!keylist)
381                 goto not_this_keyring;
382
383         /* iterate through the keys in this keyring first */
384         for (kix = 0; kix < keylist->nkeys; kix++) {
385                 key = keylist->keys[kix];
386                 kflags = key->flags;
387
388                 /* ignore keys not of this type */
389                 if (key->type != type)
390                         continue;
391
392                 /* skip revoked keys and expired keys */
393                 if (!no_state_check) {
394                         if (kflags & (1 << KEY_FLAG_REVOKED))
395                                 continue;
396
397                         if (key->expiry && now.tv_sec >= key->expiry)
398                                 continue;
399                 }
400
401                 /* keys that don't match */
402                 if (!match(key, description))
403                         continue;
404
405                 /* key must have search permissions */
406                 if (key_task_permission(make_key_ref(key, possessed),
407                                         cred, KEY_SEARCH) < 0)
408                         continue;
409
410                 if (no_state_check)
411                         goto found;
412
413                 /* we set a different error code if we pass a negative key */
414                 if (kflags & (1 << KEY_FLAG_NEGATIVE)) {
415                         err = key->type_data.reject_error;
416                         continue;
417                 }
418
419                 goto found;
420         }
421
422         /* search through the keyrings nested in this one */
423         kix = 0;
424 ascend:
425         for (; kix < keylist->nkeys; kix++) {
426                 key = keylist->keys[kix];
427                 if (key->type != &key_type_keyring)
428                         continue;
429
430                 /* recursively search nested keyrings
431                  * - only search keyrings for which we have search permission
432                  */
433                 if (sp >= KEYRING_SEARCH_MAX_DEPTH)
434                         continue;
435
436                 if (key_task_permission(make_key_ref(key, possessed),
437                                         cred, KEY_SEARCH) < 0)
438                         continue;
439
440                 /* stack the current position */
441                 stack[sp].keylist = keylist;
442                 stack[sp].kix = kix;
443                 sp++;
444
445                 /* begin again with the new keyring */
446                 keyring = key;
447                 goto descend;
448         }
449
450         /* the keyring we're looking at was disqualified or didn't contain a
451          * matching key */
452 not_this_keyring:
453         if (sp > 0) {
454                 /* resume the processing of a keyring higher up in the tree */
455                 sp--;
456                 keylist = stack[sp].keylist;
457                 kix = stack[sp].kix + 1;
458                 goto ascend;
459         }
460
461         key_ref = ERR_PTR(err);
462         goto error_2;
463
464         /* we found a viable match */
465 found:
466         atomic_inc(&key->usage);
467         key_check(key);
468         key_ref = make_key_ref(key, possessed);
469 error_2:
470         rcu_read_unlock();
471 error:
472         return key_ref;
473 }
474
475 /**
476  * keyring_search - Search the supplied keyring tree for a matching key
477  * @keyring: The root of the keyring tree to be searched.
478  * @type: The type of keyring we want to find.
479  * @description: The name of the keyring we want to find.
480  *
481  * As keyring_search_aux() above, but using the current task's credentials and
482  * type's default matching function.
483  */
484 key_ref_t keyring_search(key_ref_t keyring,
485                          struct key_type *type,
486                          const char *description)
487 {
488         if (!type->match)
489                 return ERR_PTR(-ENOKEY);
490
491         return keyring_search_aux(keyring, current->cred,
492                                   type, description, type->match, false);
493 }
494 EXPORT_SYMBOL(keyring_search);
495
496 /*
497  * Search the given keyring only (no recursion).
498  *
499  * The caller must guarantee that the keyring is a keyring and that the
500  * permission is granted to search the keyring as no check is made here.
501  *
502  * RCU is used to make it unnecessary to lock the keyring key list here.
503  *
504  * Returns a pointer to the found key with usage count incremented if
505  * successful and returns -ENOKEY if not found.  Revoked keys and keys not
506  * providing the requested permission are skipped over.
507  *
508  * If successful, the possession indicator is propagated from the keyring ref
509  * to the returned key reference.
510  */
511 key_ref_t __keyring_search_one(key_ref_t keyring_ref,
512                                const struct key_type *ktype,
513                                const char *description,
514                                key_perm_t perm)
515 {
516         struct keyring_list *klist;
517         unsigned long possessed;
518         struct key *keyring, *key;
519         int loop;
520
521         keyring = key_ref_to_ptr(keyring_ref);
522         possessed = is_key_possessed(keyring_ref);
523
524         rcu_read_lock();
525
526         klist = rcu_dereference(keyring->payload.subscriptions);
527         if (klist) {
528                 for (loop = 0; loop < klist->nkeys; loop++) {
529                         key = klist->keys[loop];
530
531                         if (key->type == ktype &&
532                             (!key->type->match ||
533                              key->type->match(key, description)) &&
534                             key_permission(make_key_ref(key, possessed),
535                                            perm) == 0 &&
536                             !test_bit(KEY_FLAG_REVOKED, &key->flags)
537                             )
538                                 goto found;
539                 }
540         }
541
542         rcu_read_unlock();
543         return ERR_PTR(-ENOKEY);
544
545 found:
546         atomic_inc(&key->usage);
547         rcu_read_unlock();
548         return make_key_ref(key, possessed);
549 }
550
551 /*
552  * Find a keyring with the specified name.
553  *
554  * All named keyrings in the current user namespace are searched, provided they
555  * grant Search permission directly to the caller (unless this check is
556  * skipped).  Keyrings whose usage points have reached zero or who have been
557  * revoked are skipped.
558  *
559  * Returns a pointer to the keyring with the keyring's refcount having being
560  * incremented on success.  -ENOKEY is returned if a key could not be found.
561  */
562 struct key *find_keyring_by_name(const char *name, bool skip_perm_check)
563 {
564         struct key *keyring;
565         int bucket;
566
567         if (!name)
568                 return ERR_PTR(-EINVAL);
569
570         bucket = keyring_hash(name);
571
572         read_lock(&keyring_name_lock);
573
574         if (keyring_name_hash[bucket].next) {
575                 /* search this hash bucket for a keyring with a matching name
576                  * that's readable and that hasn't been revoked */
577                 list_for_each_entry(keyring,
578                                     &keyring_name_hash[bucket],
579                                     type_data.link
580                                     ) {
581                         if (keyring->user->user_ns != current_user_ns())
582                                 continue;
583
584                         if (test_bit(KEY_FLAG_REVOKED, &keyring->flags))
585                                 continue;
586
587                         if (strcmp(keyring->description, name) != 0)
588                                 continue;
589
590                         if (!skip_perm_check &&
591                             key_permission(make_key_ref(keyring, 0),
592                                            KEY_SEARCH) < 0)
593                                 continue;
594
595                         /* we've got a match but we might end up racing with
596                          * key_cleanup() if the keyring is currently 'dead'
597                          * (ie. it has a zero usage count) */
598                         if (!atomic_inc_not_zero(&keyring->usage))
599                                 continue;
600                         goto out;
601                 }
602         }
603
604         keyring = ERR_PTR(-ENOKEY);
605 out:
606         read_unlock(&keyring_name_lock);
607         return keyring;
608 }
609
610 /*
611  * See if a cycle will will be created by inserting acyclic tree B in acyclic
612  * tree A at the topmost level (ie: as a direct child of A).
613  *
614  * Since we are adding B to A at the top level, checking for cycles should just
615  * be a matter of seeing if node A is somewhere in tree B.
616  */
617 static int keyring_detect_cycle(struct key *A, struct key *B)
618 {
619         struct {
620                 struct keyring_list *keylist;
621                 int kix;
622         } stack[KEYRING_SEARCH_MAX_DEPTH];
623
624         struct keyring_list *keylist;
625         struct key *subtree, *key;
626         int sp, kix, ret;
627
628         rcu_read_lock();
629
630         ret = -EDEADLK;
631         if (A == B)
632                 goto cycle_detected;
633
634         subtree = B;
635         sp = 0;
636
637         /* start processing a new keyring */
638 descend:
639         if (test_bit(KEY_FLAG_REVOKED, &subtree->flags))
640                 goto not_this_keyring;
641
642         keylist = rcu_dereference(subtree->payload.subscriptions);
643         if (!keylist)
644                 goto not_this_keyring;
645         kix = 0;
646
647 ascend:
648         /* iterate through the remaining keys in this keyring */
649         for (; kix < keylist->nkeys; kix++) {
650                 key = keylist->keys[kix];
651
652                 if (key == A)
653                         goto cycle_detected;
654
655                 /* recursively check nested keyrings */
656                 if (key->type == &key_type_keyring) {
657                         if (sp >= KEYRING_SEARCH_MAX_DEPTH)
658                                 goto too_deep;
659
660                         /* stack the current position */
661                         stack[sp].keylist = keylist;
662                         stack[sp].kix = kix;
663                         sp++;
664
665                         /* begin again with the new keyring */
666                         subtree = key;
667                         goto descend;
668                 }
669         }
670
671         /* the keyring we're looking at was disqualified or didn't contain a
672          * matching key */
673 not_this_keyring:
674         if (sp > 0) {
675                 /* resume the checking of a keyring higher up in the tree */
676                 sp--;
677                 keylist = stack[sp].keylist;
678                 kix = stack[sp].kix + 1;
679                 goto ascend;
680         }
681
682         ret = 0; /* no cycles detected */
683
684 error:
685         rcu_read_unlock();
686         return ret;
687
688 too_deep:
689         ret = -ELOOP;
690         goto error;
691
692 cycle_detected:
693         ret = -EDEADLK;
694         goto error;
695 }
696
697 /*
698  * Dispose of a keyring list after the RCU grace period, freeing the unlinked
699  * key
700  */
701 static void keyring_unlink_rcu_disposal(struct rcu_head *rcu)
702 {
703         struct keyring_list *klist =
704                 container_of(rcu, struct keyring_list, rcu);
705
706         if (klist->delkey != USHRT_MAX)
707                 key_put(klist->keys[klist->delkey]);
708         kfree(klist);
709 }
710
711 /*
712  * Preallocate memory so that a key can be linked into to a keyring.
713  */
714 int __key_link_begin(struct key *keyring, const struct key_type *type,
715                      const char *description, unsigned long *_prealloc)
716         __acquires(&keyring->sem)
717 {
718         struct keyring_list *klist, *nklist;
719         unsigned long prealloc;
720         unsigned max;
721         size_t size;
722         int loop, ret;
723
724         kenter("%d,%s,%s,", key_serial(keyring), type->name, description);
725
726         if (keyring->type != &key_type_keyring)
727                 return -ENOTDIR;
728
729         down_write(&keyring->sem);
730
731         ret = -EKEYREVOKED;
732         if (test_bit(KEY_FLAG_REVOKED, &keyring->flags))
733                 goto error_krsem;
734
735         /* serialise link/link calls to prevent parallel calls causing a cycle
736          * when linking two keyring in opposite orders */
737         if (type == &key_type_keyring)
738                 down_write(&keyring_serialise_link_sem);
739
740         klist = rcu_dereference_locked_keyring(keyring);
741
742         /* see if there's a matching key we can displace */
743         if (klist && klist->nkeys > 0) {
744                 for (loop = klist->nkeys - 1; loop >= 0; loop--) {
745                         if (klist->keys[loop]->type == type &&
746                             strcmp(klist->keys[loop]->description,
747                                    description) == 0
748                             ) {
749                                 /* found a match - we'll replace this one with
750                                  * the new key */
751                                 size = sizeof(struct key *) * klist->maxkeys;
752                                 size += sizeof(*klist);
753                                 BUG_ON(size > PAGE_SIZE);
754
755                                 ret = -ENOMEM;
756                                 nklist = kmemdup(klist, size, GFP_KERNEL);
757                                 if (!nklist)
758                                         goto error_sem;
759
760                                 /* note replacement slot */
761                                 klist->delkey = nklist->delkey = loop;
762                                 prealloc = (unsigned long)nklist;
763                                 goto done;
764                         }
765                 }
766         }
767
768         /* check that we aren't going to overrun the user's quota */
769         ret = key_payload_reserve(keyring,
770                                   keyring->datalen + KEYQUOTA_LINK_BYTES);
771         if (ret < 0)
772                 goto error_sem;
773
774         if (klist && klist->nkeys < klist->maxkeys) {
775                 /* there's sufficient slack space to append directly */
776                 nklist = NULL;
777                 prealloc = KEY_LINK_FIXQUOTA;
778         } else {
779                 /* grow the key list */
780                 max = 4;
781                 if (klist)
782                         max += klist->maxkeys;
783
784                 ret = -ENFILE;
785                 if (max > USHRT_MAX - 1)
786                         goto error_quota;
787                 size = sizeof(*klist) + sizeof(struct key *) * max;
788                 if (size > PAGE_SIZE)
789                         goto error_quota;
790
791                 ret = -ENOMEM;
792                 nklist = kmalloc(size, GFP_KERNEL);
793                 if (!nklist)
794                         goto error_quota;
795
796                 nklist->maxkeys = max;
797                 if (klist) {
798                         memcpy(nklist->keys, klist->keys,
799                                sizeof(struct key *) * klist->nkeys);
800                         nklist->delkey = klist->nkeys;
801                         nklist->nkeys = klist->nkeys + 1;
802                         klist->delkey = USHRT_MAX;
803                 } else {
804                         nklist->nkeys = 1;
805                         nklist->delkey = 0;
806                 }
807
808                 /* add the key into the new space */
809                 nklist->keys[nklist->delkey] = NULL;
810         }
811
812         prealloc = (unsigned long)nklist | KEY_LINK_FIXQUOTA;
813 done:
814         *_prealloc = prealloc;
815         kleave(" = 0");
816         return 0;
817
818 error_quota:
819         /* undo the quota changes */
820         key_payload_reserve(keyring,
821                             keyring->datalen - KEYQUOTA_LINK_BYTES);
822 error_sem:
823         if (type == &key_type_keyring)
824                 up_write(&keyring_serialise_link_sem);
825 error_krsem:
826         up_write(&keyring->sem);
827         kleave(" = %d", ret);
828         return ret;
829 }
830
831 /*
832  * Check already instantiated keys aren't going to be a problem.
833  *
834  * The caller must have called __key_link_begin(). Don't need to call this for
835  * keys that were created since __key_link_begin() was called.
836  */
837 int __key_link_check_live_key(struct key *keyring, struct key *key)
838 {
839         if (key->type == &key_type_keyring)
840                 /* check that we aren't going to create a cycle by linking one
841                  * keyring to another */
842                 return keyring_detect_cycle(keyring, key);
843         return 0;
844 }
845
846 /*
847  * Link a key into to a keyring.
848  *
849  * Must be called with __key_link_begin() having being called.  Discards any
850  * already extant link to matching key if there is one, so that each keyring
851  * holds at most one link to any given key of a particular type+description
852  * combination.
853  */
854 void __key_link(struct key *keyring, struct key *key,
855                 unsigned long *_prealloc)
856 {
857         struct keyring_list *klist, *nklist;
858
859         nklist = (struct keyring_list *)(*_prealloc & ~KEY_LINK_FIXQUOTA);
860         *_prealloc = 0;
861
862         kenter("%d,%d,%p", keyring->serial, key->serial, nklist);
863
864         klist = rcu_dereference_protected(keyring->payload.subscriptions,
865                                           rwsem_is_locked(&keyring->sem));
866
867         atomic_inc(&key->usage);
868
869         /* there's a matching key we can displace or an empty slot in a newly
870          * allocated list we can fill */
871         if (nklist) {
872                 kdebug("replace %hu/%hu/%hu",
873                        nklist->delkey, nklist->nkeys, nklist->maxkeys);
874
875                 nklist->keys[nklist->delkey] = key;
876
877                 rcu_assign_pointer(keyring->payload.subscriptions, nklist);
878
879                 /* dispose of the old keyring list and, if there was one, the
880                  * displaced key */
881                 if (klist) {
882                         kdebug("dispose %hu/%hu/%hu",
883                                klist->delkey, klist->nkeys, klist->maxkeys);
884                         call_rcu(&klist->rcu, keyring_unlink_rcu_disposal);
885                 }
886         } else {
887                 /* there's sufficient slack space to append directly */
888                 klist->keys[klist->nkeys] = key;
889                 smp_wmb();
890                 klist->nkeys++;
891         }
892 }
893
894 /*
895  * Finish linking a key into to a keyring.
896  *
897  * Must be called with __key_link_begin() having being called.
898  */
899 void __key_link_end(struct key *keyring, struct key_type *type,
900                     unsigned long prealloc)
901         __releases(&keyring->sem)
902 {
903         BUG_ON(type == NULL);
904         BUG_ON(type->name == NULL);
905         kenter("%d,%s,%lx", keyring->serial, type->name, prealloc);
906
907         if (type == &key_type_keyring)
908                 up_write(&keyring_serialise_link_sem);
909
910         if (prealloc) {
911                 if (prealloc & KEY_LINK_FIXQUOTA)
912                         key_payload_reserve(keyring,
913                                             keyring->datalen -
914                                             KEYQUOTA_LINK_BYTES);
915                 kfree((struct keyring_list *)(prealloc & ~KEY_LINK_FIXQUOTA));
916         }
917         up_write(&keyring->sem);
918 }
919
920 /**
921  * key_link - Link a key to a keyring
922  * @keyring: The keyring to make the link in.
923  * @key: The key to link to.
924  *
925  * Make a link in a keyring to a key, such that the keyring holds a reference
926  * on that key and the key can potentially be found by searching that keyring.
927  *
928  * This function will write-lock the keyring's semaphore and will consume some
929  * of the user's key data quota to hold the link.
930  *
931  * Returns 0 if successful, -ENOTDIR if the keyring isn't a keyring,
932  * -EKEYREVOKED if the keyring has been revoked, -ENFILE if the keyring is
933  * full, -EDQUOT if there is insufficient key data quota remaining to add
934  * another link or -ENOMEM if there's insufficient memory.
935  *
936  * It is assumed that the caller has checked that it is permitted for a link to
937  * be made (the keyring should have Write permission and the key Link
938  * permission).
939  */
940 int key_link(struct key *keyring, struct key *key)
941 {
942         unsigned long prealloc;
943         int ret;
944
945         key_check(keyring);
946         key_check(key);
947
948         ret = __key_link_begin(keyring, key->type, key->description, &prealloc);
949         if (ret == 0) {
950                 ret = __key_link_check_live_key(keyring, key);
951                 if (ret == 0)
952                         __key_link(keyring, key, &prealloc);
953                 __key_link_end(keyring, key->type, prealloc);
954         }
955
956         return ret;
957 }
958 EXPORT_SYMBOL(key_link);
959
960 /**
961  * key_unlink - Unlink the first link to a key from a keyring.
962  * @keyring: The keyring to remove the link from.
963  * @key: The key the link is to.
964  *
965  * Remove a link from a keyring to a key.
966  *
967  * This function will write-lock the keyring's semaphore.
968  *
969  * Returns 0 if successful, -ENOTDIR if the keyring isn't a keyring, -ENOENT if
970  * the key isn't linked to by the keyring or -ENOMEM if there's insufficient
971  * memory.
972  *
973  * It is assumed that the caller has checked that it is permitted for a link to
974  * be removed (the keyring should have Write permission; no permissions are
975  * required on the key).
976  */
977 int key_unlink(struct key *keyring, struct key *key)
978 {
979         struct keyring_list *klist, *nklist;
980         int loop, ret;
981
982         key_check(keyring);
983         key_check(key);
984
985         ret = -ENOTDIR;
986         if (keyring->type != &key_type_keyring)
987                 goto error;
988
989         down_write(&keyring->sem);
990
991         klist = rcu_dereference_locked_keyring(keyring);
992         if (klist) {
993                 /* search the keyring for the key */
994                 for (loop = 0; loop < klist->nkeys; loop++)
995                         if (klist->keys[loop] == key)
996                                 goto key_is_present;
997         }
998
999         up_write(&keyring->sem);
1000         ret = -ENOENT;
1001         goto error;
1002
1003 key_is_present:
1004         /* we need to copy the key list for RCU purposes */
1005         nklist = kmalloc(sizeof(*klist) +
1006                          sizeof(struct key *) * klist->maxkeys,
1007                          GFP_KERNEL);
1008         if (!nklist)
1009                 goto nomem;
1010         nklist->maxkeys = klist->maxkeys;
1011         nklist->nkeys = klist->nkeys - 1;
1012
1013         if (loop > 0)
1014                 memcpy(&nklist->keys[0],
1015                        &klist->keys[0],
1016                        loop * sizeof(struct key *));
1017
1018         if (loop < nklist->nkeys)
1019                 memcpy(&nklist->keys[loop],
1020                        &klist->keys[loop + 1],
1021                        (nklist->nkeys - loop) * sizeof(struct key *));
1022
1023         /* adjust the user's quota */
1024         key_payload_reserve(keyring,
1025                             keyring->datalen - KEYQUOTA_LINK_BYTES);
1026
1027         rcu_assign_pointer(keyring->payload.subscriptions, nklist);
1028
1029         up_write(&keyring->sem);
1030
1031         /* schedule for later cleanup */
1032         klist->delkey = loop;
1033         call_rcu(&klist->rcu, keyring_unlink_rcu_disposal);
1034
1035         ret = 0;
1036
1037 error:
1038         return ret;
1039 nomem:
1040         ret = -ENOMEM;
1041         up_write(&keyring->sem);
1042         goto error;
1043 }
1044 EXPORT_SYMBOL(key_unlink);
1045
1046 /*
1047  * Dispose of a keyring list after the RCU grace period, releasing the keys it
1048  * links to.
1049  */
1050 static void keyring_clear_rcu_disposal(struct rcu_head *rcu)
1051 {
1052         struct keyring_list *klist;
1053         int loop;
1054
1055         klist = container_of(rcu, struct keyring_list, rcu);
1056
1057         for (loop = klist->nkeys - 1; loop >= 0; loop--)
1058                 key_put(klist->keys[loop]);
1059
1060         kfree(klist);
1061 }
1062
1063 /**
1064  * keyring_clear - Clear a keyring
1065  * @keyring: The keyring to clear.
1066  *
1067  * Clear the contents of the specified keyring.
1068  *
1069  * Returns 0 if successful or -ENOTDIR if the keyring isn't a keyring.
1070  */
1071 int keyring_clear(struct key *keyring)
1072 {
1073         struct keyring_list *klist;
1074         int ret;
1075
1076         ret = -ENOTDIR;
1077         if (keyring->type == &key_type_keyring) {
1078                 /* detach the pointer block with the locks held */
1079                 down_write(&keyring->sem);
1080
1081                 klist = rcu_dereference_locked_keyring(keyring);
1082                 if (klist) {
1083                         /* adjust the quota */
1084                         key_payload_reserve(keyring,
1085                                             sizeof(struct keyring_list));
1086
1087                         rcu_assign_pointer(keyring->payload.subscriptions,
1088                                            NULL);
1089                 }
1090
1091                 up_write(&keyring->sem);
1092
1093                 /* free the keys after the locks have been dropped */
1094                 if (klist)
1095                         call_rcu(&klist->rcu, keyring_clear_rcu_disposal);
1096
1097                 ret = 0;
1098         }
1099
1100         return ret;
1101 }
1102 EXPORT_SYMBOL(keyring_clear);
1103
1104 /*
1105  * Dispose of the links from a revoked keyring.
1106  *
1107  * This is called with the key sem write-locked.
1108  */
1109 static void keyring_revoke(struct key *keyring)
1110 {
1111         struct keyring_list *klist;
1112
1113         klist = rcu_dereference_locked_keyring(keyring);
1114
1115         /* adjust the quota */
1116         key_payload_reserve(keyring, 0);
1117
1118         if (klist) {
1119                 rcu_assign_pointer(keyring->payload.subscriptions, NULL);
1120                 call_rcu(&klist->rcu, keyring_clear_rcu_disposal);
1121         }
1122 }
1123
1124 /*
1125  * Determine whether a key is dead.
1126  */
1127 static bool key_is_dead(struct key *key, time_t limit)
1128 {
1129         return test_bit(KEY_FLAG_DEAD, &key->flags) ||
1130                 (key->expiry > 0 && key->expiry <= limit);
1131 }
1132
1133 /*
1134  * Collect garbage from the contents of a keyring, replacing the old list with
1135  * a new one with the pointers all shuffled down.
1136  *
1137  * Dead keys are classed as oned that are flagged as being dead or are revoked,
1138  * expired or negative keys that were revoked or expired before the specified
1139  * limit.
1140  */
1141 void keyring_gc(struct key *keyring, time_t limit)
1142 {
1143         struct keyring_list *klist, *new;
1144         struct key *key;
1145         int loop, keep, max;
1146
1147         kenter("{%x,%s}", key_serial(keyring), keyring->description);
1148
1149         down_write(&keyring->sem);
1150
1151         klist = rcu_dereference_locked_keyring(keyring);
1152         if (!klist)
1153                 goto no_klist;
1154
1155         /* work out how many subscriptions we're keeping */
1156         keep = 0;
1157         for (loop = klist->nkeys - 1; loop >= 0; loop--)
1158                 if (!key_is_dead(klist->keys[loop], limit))
1159                         keep++;
1160
1161         if (keep == klist->nkeys)
1162                 goto just_return;
1163
1164         /* allocate a new keyring payload */
1165         max = roundup(keep, 4);
1166         new = kmalloc(sizeof(struct keyring_list) + max * sizeof(struct key *),
1167                       GFP_KERNEL);
1168         if (!new)
1169                 goto nomem;
1170         new->maxkeys = max;
1171         new->nkeys = 0;
1172         new->delkey = 0;
1173
1174         /* install the live keys
1175          * - must take care as expired keys may be updated back to life
1176          */
1177         keep = 0;
1178         for (loop = klist->nkeys - 1; loop >= 0; loop--) {
1179                 key = klist->keys[loop];
1180                 if (!key_is_dead(key, limit)) {
1181                         if (keep >= max)
1182                                 goto discard_new;
1183                         new->keys[keep++] = key_get(key);
1184                 }
1185         }
1186         new->nkeys = keep;
1187
1188         /* adjust the quota */
1189         key_payload_reserve(keyring,
1190                             sizeof(struct keyring_list) +
1191                             KEYQUOTA_LINK_BYTES * keep);
1192
1193         if (keep == 0) {
1194                 rcu_assign_pointer(keyring->payload.subscriptions, NULL);
1195                 kfree(new);
1196         } else {
1197                 rcu_assign_pointer(keyring->payload.subscriptions, new);
1198         }
1199
1200         up_write(&keyring->sem);
1201
1202         call_rcu(&klist->rcu, keyring_clear_rcu_disposal);
1203         kleave(" [yes]");
1204         return;
1205
1206 discard_new:
1207         new->nkeys = keep;
1208         keyring_clear_rcu_disposal(&new->rcu);
1209         up_write(&keyring->sem);
1210         kleave(" [discard]");
1211         return;
1212
1213 just_return:
1214         up_write(&keyring->sem);
1215         kleave(" [no dead]");
1216         return;
1217
1218 no_klist:
1219         up_write(&keyring->sem);
1220         kleave(" [no_klist]");
1221         return;
1222
1223 nomem:
1224         up_write(&keyring->sem);
1225         kleave(" [oom]");
1226 }