Branch data     Line data    Source code

       1                 :            : // SPDX-License-Identifier: GPL-2.0-or-later
       2                 :            : /* Key garbage collector
       3                 :            :  *
       4                 :            :  * Copyright (C) 2009-2011 Red Hat, Inc. All Rights Reserved.
       5                 :            :  * Written by David Howells (dhowells@redhat.com)
       6                 :            :  */
       7                 :            : 
       8                 :            : #include <linux/slab.h>
       9                 :            : #include <linux/security.h>
      10                 :            : #include <keys/keyring-type.h>
      11                 :            : #include "internal.h"
      12                 :            : 
      13                 :            : /*
      14                 :            :  * Delay between key revocation/expiry in seconds
      15                 :            :  */
      16                 :            : unsigned key_gc_delay = 5 * 60;
      17                 :            : 
      18                 :            : /*
      19                 :            :  * Reaper for unused keys.
      20                 :            :  */
      21                 :            : static void key_garbage_collector(struct work_struct *work);
      22                 :            : DECLARE_WORK(key_gc_work, key_garbage_collector);
      23                 :            : 
      24                 :            : /*
      25                 :            :  * Reaper for links from keyrings to dead keys.
      26                 :            :  */
      27                 :            : static void key_gc_timer_func(struct timer_list *);
      28                 :            : static DEFINE_TIMER(key_gc_timer, key_gc_timer_func);
      29                 :            : 
      30                 :            : static time64_t key_gc_next_run = TIME64_MAX;
      31                 :            : static struct key_type *key_gc_dead_keytype;
      32                 :            : 
      33                 :            : static unsigned long key_gc_flags;
      34                 :            : #define KEY_GC_KEY_EXPIRED      0       /* A key expired and needs unlinking */
      35                 :            : #define KEY_GC_REAP_KEYTYPE     1       /* A keytype is being unregistered */
      36                 :            : #define KEY_GC_REAPING_KEYTYPE  2       /* Cleared when keytype reaped */
      37                 :            : 
      38                 :            : 
      39                 :            : /*
      40                 :            :  * Any key whose type gets unregistered will be re-typed to this if it can't be
      41                 :            :  * immediately unlinked.
      42                 :            :  */
      43                 :            : struct key_type key_type_dead = {
      44                 :            :         .name = ".dead",
      45                 :            : };
      46                 :            : 
      47                 :            : /*
      48                 :            :  * Schedule a garbage collection run.
      49                 :            :  * - time precision isn't particularly important
      50                 :            :  */
      51                 :          0 : void key_schedule_gc(time64_t gc_at)
      52                 :            : {
      53                 :            :         unsigned long expires;
      54                 :          0 :         time64_t now = ktime_get_real_seconds();
      55                 :            : 
      56                 :            :         kenter("%lld", gc_at - now);
      57                 :            : 
      58                 :          0 :         if (gc_at <= now || test_bit(KEY_GC_REAP_KEYTYPE, &key_gc_flags)) {
      59                 :            :                 kdebug("IMMEDIATE");
      60                 :            :                 schedule_work(&key_gc_work);
      61                 :          0 :         } else if (gc_at < key_gc_next_run) {
      62                 :            :                 kdebug("DEFERRED");
      63                 :          0 :                 key_gc_next_run = gc_at;
      64                 :          0 :                 expires = jiffies + (gc_at - now) * HZ;
      65                 :          0 :                 mod_timer(&key_gc_timer, expires);
      66                 :            :         }
      67                 :          0 : }
      68                 :            : 
      69                 :            : /*
      70                 :            :  * Schedule a dead links collection run.
      71                 :            :  */
      72                 :          0 : void key_schedule_gc_links(void)
      73                 :            : {
      74                 :          0 :         set_bit(KEY_GC_KEY_EXPIRED, &key_gc_flags);
      75                 :            :         schedule_work(&key_gc_work);
      76                 :          0 : }
      77                 :            : 
      78                 :            : /*
      79                 :            :  * Some key's cleanup time was met after it expired, so we need to get the
      80                 :            :  * reaper to go through a cycle finding expired keys.
      81                 :            :  */
      82                 :          0 : static void key_gc_timer_func(struct timer_list *unused)
      83                 :            : {
      84                 :            :         kenter("");
      85                 :          0 :         key_gc_next_run = TIME64_MAX;
      86                 :          0 :         key_schedule_gc_links();
      87                 :          0 : }
      88                 :            : 
      89                 :            : /*
      90                 :            :  * Reap keys of dead type.
      91                 :            :  *
      92                 :            :  * We use three flags to make sure we see three complete cycles of the garbage
      93                 :            :  * collector: the first to mark keys of that type as being dead, the second to
      94                 :            :  * collect dead links and the third to clean up the dead keys.  We have to be
      95                 :            :  * careful as there may already be a cycle in progress.
      96                 :            :  *
      97                 :            :  * The caller must be holding key_types_sem.
      98                 :            :  */
      99                 :          0 : void key_gc_keytype(struct key_type *ktype)
     100                 :            : {
     101                 :            :         kenter("%s", ktype->name);
     102                 :            : 
     103                 :          0 :         key_gc_dead_keytype = ktype;
     104                 :          0 :         set_bit(KEY_GC_REAPING_KEYTYPE, &key_gc_flags);
     105                 :          0 :         smp_mb();
     106                 :          0 :         set_bit(KEY_GC_REAP_KEYTYPE, &key_gc_flags);
     107                 :            : 
     108                 :            :         kdebug("schedule");
     109                 :            :         schedule_work(&key_gc_work);
     110                 :            : 
     111                 :            :         kdebug("sleep");
     112                 :          0 :         wait_on_bit(&key_gc_flags, KEY_GC_REAPING_KEYTYPE,
     113                 :            :                     TASK_UNINTERRUPTIBLE);
     114                 :            : 
     115                 :          0 :         key_gc_dead_keytype = NULL;
     116                 :            :         kleave("");
     117                 :          0 : }
     118                 :            : 
     119                 :            : /*
     120                 :            :  * Garbage collect a list of unreferenced, detached keys
     121                 :            :  */
     122                 :          3 : static noinline void key_gc_unused_keys(struct list_head *keys)
     123                 :            : {
     124                 :          3 :         while (!list_empty(keys)) {
     125                 :            :                 struct key *key =
     126                 :          3 :                         list_entry(keys->next, struct key, graveyard_link);
     127                 :          3 :                 short state = key->state;
     128                 :            : 
     129                 :            :                 list_del(&key->graveyard_link);
     130                 :            : 
     131                 :            :                 kdebug("- %u", key->serial);
     132                 :            :                 key_check(key);
     133                 :            : 
     134                 :            :                 /* Throw away the key data if the key is instantiated */
     135                 :          3 :                 if (state == KEY_IS_POSITIVE && key->type->destroy)
     136                 :          3 :                         key->type->destroy(key);
     137                 :            : 
     138                 :          3 :                 security_key_free(key);
     139                 :            : 
     140                 :            :                 /* deal with the user's key tracking and quota */
     141                 :          3 :                 if (test_bit(KEY_FLAG_IN_QUOTA, &key->flags)) {
     142                 :          3 :                         spin_lock(&key->user->lock);
     143                 :          3 :                         key->user->qnkeys--;
     144                 :          3 :                         key->user->qnbytes -= key->quotalen;
     145                 :          3 :                         spin_unlock(&key->user->lock);
     146                 :            :                 }
     147                 :            : 
     148                 :          3 :                 atomic_dec(&key->user->nkeys);
     149                 :          3 :                 if (state != KEY_IS_UNINSTANTIATED)
     150                 :          3 :                         atomic_dec(&key->user->nikeys);
     151                 :            : 
     152                 :          3 :                 key_user_put(key->user);
     153                 :          3 :                 key_put_tag(key->domain_tag);
     154                 :          3 :                 kfree(key->description);
     155                 :            : 
     156                 :            :                 memzero_explicit(key, sizeof(*key));
     157                 :          3 :                 kmem_cache_free(key_jar, key);
     158                 :            :         }
     159                 :          3 : }
     160                 :            : 
     161                 :            : /*
     162                 :            :  * Garbage collector for unused keys.
     163                 :            :  *
     164                 :            :  * This is done in process context so that we don't have to disable interrupts
     165                 :            :  * all over the place.  key_put() schedules this rather than trying to do the
     166                 :            :  * cleanup itself, which means key_put() doesn't have to sleep.
     167                 :            :  */
     168                 :          3 : static void key_garbage_collector(struct work_struct *work)
     169                 :            : {
     170                 :            :         static LIST_HEAD(graveyard);
     171                 :            :         static u8 gc_state;             /* Internal persistent state */
     172                 :            : #define KEY_GC_REAP_AGAIN       0x01    /* - Need another cycle */
     173                 :            : #define KEY_GC_REAPING_LINKS    0x02    /* - We need to reap links */
     174                 :            : #define KEY_GC_SET_TIMER        0x04    /* - We need to restart the timer */
     175                 :            : #define KEY_GC_REAPING_DEAD_1   0x10    /* - We need to mark dead keys */
     176                 :            : #define KEY_GC_REAPING_DEAD_2   0x20    /* - We need to reap dead key links */
     177                 :            : #define KEY_GC_REAPING_DEAD_3   0x40    /* - We need to reap dead keys */
     178                 :            : #define KEY_GC_FOUND_DEAD_KEY   0x80    /* - We found at least one dead key */
     179                 :            : 
     180                 :            :         struct rb_node *cursor;
     181                 :            :         struct key *key;
     182                 :            :         time64_t new_timer, limit;
     183                 :            : 
     184                 :            :         kenter("[%lx,%x]", key_gc_flags, gc_state);
     185                 :            : 
     186                 :          3 :         limit = ktime_get_real_seconds();
     187                 :          3 :         if (limit > key_gc_delay)
     188                 :          3 :                 limit -= key_gc_delay;
     189                 :            :         else
     190                 :            :                 limit = key_gc_delay;
     191                 :            : 
     192                 :            :         /* Work out what we're going to be doing in this pass */
     193                 :          3 :         gc_state &= KEY_GC_REAPING_DEAD_1 | KEY_GC_REAPING_DEAD_2;
     194                 :          3 :         gc_state <<= 1;
     195                 :          3 :         if (test_and_clear_bit(KEY_GC_KEY_EXPIRED, &key_gc_flags))
     196                 :          0 :                 gc_state |= KEY_GC_REAPING_LINKS | KEY_GC_SET_TIMER;
     197                 :            : 
     198                 :          3 :         if (test_and_clear_bit(KEY_GC_REAP_KEYTYPE, &key_gc_flags))
     199                 :          0 :                 gc_state |= KEY_GC_REAPING_DEAD_1;
     200                 :            :         kdebug("new pass %x", gc_state);
     201                 :            : 
     202                 :            :         new_timer = TIME64_MAX;
     203                 :            : 
     204                 :            :         /* As only this function is permitted to remove things from the key
     205                 :            :          * serial tree, if cursor is non-NULL then it will always point to a
     206                 :            :          * valid node in the tree - even if lock got dropped.
     207                 :            :          */
     208                 :            :         spin_lock(&key_serial_lock);
     209                 :          3 :         cursor = rb_first(&key_serial_tree);
     210                 :            : 
     211                 :            : continue_scanning:
     212                 :          3 :         while (cursor) {
     213                 :          3 :                 key = rb_entry(cursor, struct key, serial_node);
     214                 :          3 :                 cursor = rb_next(cursor);
     215                 :            : 
     216                 :          3 :                 if (refcount_read(&key->usage) == 0)
     217                 :            :                         goto found_unreferenced_key;
     218                 :            : 
     219                 :          3 :                 if (unlikely(gc_state & KEY_GC_REAPING_DEAD_1)) {
     220                 :          0 :                         if (key->type == key_gc_dead_keytype) {
     221                 :          0 :                                 gc_state |= KEY_GC_FOUND_DEAD_KEY;
     222                 :          0 :                                 set_bit(KEY_FLAG_DEAD, &key->flags);
     223                 :          0 :                                 key->perm = 0;
     224                 :          0 :                                 goto skip_dead_key;
     225                 :          0 :                         } else if (key->type == &key_type_keyring &&
     226                 :          0 :                                    key->restrict_link) {
     227                 :            :                                 goto found_restricted_keyring;
     228                 :            :                         }
     229                 :            :                 }
     230                 :            : 
     231                 :          3 :                 if (gc_state & KEY_GC_SET_TIMER) {
     232                 :          0 :                         if (key->expiry > limit && key->expiry < new_timer) {
     233                 :            :                                 kdebug("will expire %x in %lld",
     234                 :            :                                        key_serial(key), key->expiry - limit);
     235                 :            :                                 new_timer = key->expiry;
     236                 :            :                         }
     237                 :            :                 }
     238                 :            : 
     239                 :          3 :                 if (unlikely(gc_state & KEY_GC_REAPING_DEAD_2))
     240                 :          0 :                         if (key->type == key_gc_dead_keytype)
     241                 :          0 :                                 gc_state |= KEY_GC_FOUND_DEAD_KEY;
     242                 :            : 
     243                 :          3 :                 if ((gc_state & KEY_GC_REAPING_LINKS) ||
     244                 :          3 :                     unlikely(gc_state & KEY_GC_REAPING_DEAD_2)) {
     245                 :          0 :                         if (key->type == &key_type_keyring)
     246                 :            :                                 goto found_keyring;
     247                 :            :                 }
     248                 :            : 
     249                 :          3 :                 if (unlikely(gc_state & KEY_GC_REAPING_DEAD_3))
     250                 :          0 :                         if (key->type == key_gc_dead_keytype)
     251                 :            :                                 goto destroy_dead_key;
     252                 :            : 
     253                 :            :         skip_dead_key:
     254                 :          3 :                 if (spin_is_contended(&key_serial_lock) || need_resched())
     255                 :            :                         goto contended;
     256                 :            :         }
     257                 :            : 
     258                 :            : contended:
     259                 :            :         spin_unlock(&key_serial_lock);
     260                 :            : 
     261                 :            : maybe_resched:
     262                 :          3 :         if (cursor) {
     263                 :          3 :                 cond_resched();
     264                 :            :                 spin_lock(&key_serial_lock);
     265                 :            :                 goto continue_scanning;
     266                 :            :         }
     267                 :            : 
     268                 :            :         /* We've completed the pass.  Set the timer if we need to and queue a
     269                 :            :          * new cycle if necessary.  We keep executing cycles until we find one
     270                 :            :          * where we didn't reap any keys.
     271                 :            :          */
     272                 :            :         kdebug("pass complete");
     273                 :            : 
     274                 :          3 :         if (gc_state & KEY_GC_SET_TIMER && new_timer != (time64_t)TIME64_MAX) {
     275                 :          0 :                 new_timer += key_gc_delay;
     276                 :          0 :                 key_schedule_gc(new_timer);
     277                 :            :         }
     278                 :            : 
     279                 :          3 :         if (unlikely(gc_state & KEY_GC_REAPING_DEAD_2) ||
     280                 :            :             !list_empty(&graveyard)) {
     281                 :            :                 /* Make sure that all pending keyring payload destructions are
     282                 :            :                  * fulfilled and that people aren't now looking at dead or
     283                 :            :                  * dying keys that they don't have a reference upon or a link
     284                 :            :                  * to.
     285                 :            :                  */
     286                 :            :                 kdebug("gc sync");
     287                 :          3 :                 synchronize_rcu();
     288                 :            :         }
     289                 :            : 
     290                 :          3 :         if (!list_empty(&graveyard)) {
     291                 :            :                 kdebug("gc keys");
     292                 :          3 :                 key_gc_unused_keys(&graveyard);
     293                 :            :         }
     294                 :            : 
     295                 :          3 :         if (unlikely(gc_state & (KEY_GC_REAPING_DEAD_1 |
     296                 :            :                                  KEY_GC_REAPING_DEAD_2))) {
     297                 :          0 :                 if (!(gc_state & KEY_GC_FOUND_DEAD_KEY)) {
     298                 :            :                         /* No remaining dead keys: short circuit the remaining
     299                 :            :                          * keytype reap cycles.
     300                 :            :                          */
     301                 :            :                         kdebug("dead short");
     302                 :          0 :                         gc_state &= ~(KEY_GC_REAPING_DEAD_1 | KEY_GC_REAPING_DEAD_2);
     303                 :          0 :                         gc_state |= KEY_GC_REAPING_DEAD_3;
     304                 :            :                 } else {
     305                 :          0 :                         gc_state |= KEY_GC_REAP_AGAIN;
     306                 :            :                 }
     307                 :            :         }
     308                 :            : 
     309                 :          3 :         if (unlikely(gc_state & KEY_GC_REAPING_DEAD_3)) {
     310                 :            :                 kdebug("dead wake");
     311                 :          0 :                 smp_mb();
     312                 :          0 :                 clear_bit(KEY_GC_REAPING_KEYTYPE, &key_gc_flags);
     313                 :          0 :                 wake_up_bit(&key_gc_flags, KEY_GC_REAPING_KEYTYPE);
     314                 :            :         }
     315                 :            : 
     316                 :          3 :         if (gc_state & KEY_GC_REAP_AGAIN)
     317                 :            :                 schedule_work(&key_gc_work);
     318                 :            :         kleave(" [end %x]", gc_state);
     319                 :          3 :         return;
     320                 :            : 
     321                 :            :         /* We found an unreferenced key - once we've removed it from the tree,
     322                 :            :          * we can safely drop the lock.
     323                 :            :          */
     324                 :            : found_unreferenced_key:
     325                 :            :         kdebug("unrefd key %d", key->serial);
     326                 :          3 :         rb_erase(&key->serial_node, &key_serial_tree);
     327                 :            :         spin_unlock(&key_serial_lock);
     328                 :            : 
     329                 :          3 :         list_add_tail(&key->graveyard_link, &graveyard);
     330                 :          3 :         gc_state |= KEY_GC_REAP_AGAIN;
     331                 :          3 :         goto maybe_resched;
     332                 :            : 
     333                 :            :         /* We found a restricted keyring and need to update the restriction if
     334                 :            :          * it is associated with the dead key type.
     335                 :            :          */
     336                 :            : found_restricted_keyring:
     337                 :            :         spin_unlock(&key_serial_lock);
     338                 :          0 :         keyring_restriction_gc(key, key_gc_dead_keytype);
     339                 :          0 :         goto maybe_resched;
     340                 :            : 
     341                 :            :         /* We found a keyring and we need to check the payload for links to
     342                 :            :          * dead or expired keys.  We don't flag another reap immediately as we
     343                 :            :          * have to wait for the old payload to be destroyed by RCU before we
     344                 :            :          * can reap the keys to which it refers.
     345                 :            :          */
     346                 :            : found_keyring:
     347                 :            :         spin_unlock(&key_serial_lock);
     348                 :          0 :         keyring_gc(key, limit);
     349                 :          0 :         goto maybe_resched;
     350                 :            : 
     351                 :            :         /* We found a dead key that is still referenced.  Reset its type and
     352                 :            :          * destroy its payload with its semaphore held.
     353                 :            :          */
     354                 :            : destroy_dead_key:
     355                 :            :         spin_unlock(&key_serial_lock);
     356                 :            :         kdebug("destroy key %d", key->serial);
     357                 :          0 :         down_write(&key->sem);
     358                 :          0 :         key->type = &key_type_dead;
     359                 :          0 :         if (key_gc_dead_keytype->destroy)
     360                 :          0 :                 key_gc_dead_keytype->destroy(key);
     361                 :          0 :         memset(&key->payload, KEY_DESTROY, sizeof(key->payload));
     362                 :          0 :         up_write(&key->sem);
     363                 :          0 :         goto maybe_resched;
     364                 :            : }