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