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