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 * Schedule a dead links collection run.
  76 */
  77void key_schedule_gc_links(void)
  78{
  79        set_bit(KEY_GC_KEY_EXPIRED, &key_gc_flags);
  80        queue_work(system_nrt_wq, &key_gc_work);
  81}
  82
  83/*
  84 * Some key's cleanup time was met after it expired, so we need to get the
  85 * reaper to go through a cycle finding expired keys.
  86 */
  87static void key_gc_timer_func(unsigned long data)
  88{
  89        kenter("");
  90        key_gc_next_run = LONG_MAX;
  91        key_schedule_gc_links();
  92}
  93
  94/*
  95 * wait_on_bit() sleep function for uninterruptible waiting
  96 */
  97static int key_gc_wait_bit(void *flags)
  98{
  99        schedule();
 100        return 0;
 101}
 102
 103/*
 104 * Reap keys of dead type.
 105 *
 106 * We use three flags to make sure we see three complete cycles of the garbage
 107 * collector: the first to mark keys of that type as being dead, the second to
 108 * collect dead links and the third to clean up the dead keys.  We have to be
 109 * careful as there may already be a cycle in progress.
 110 *
 111 * The caller must be holding key_types_sem.
 112 */
 113void key_gc_keytype(struct key_type *ktype)
 114{
 115        kenter("%s", ktype->name);
 116
 117        key_gc_dead_keytype = ktype;
 118        set_bit(KEY_GC_REAPING_KEYTYPE, &key_gc_flags);
 119        smp_mb();
 120        set_bit(KEY_GC_REAP_KEYTYPE, &key_gc_flags);
 121
 122        kdebug("schedule");
 123        queue_work(system_nrt_wq, &key_gc_work);
 124
 125        kdebug("sleep");
 126        wait_on_bit(&key_gc_flags, KEY_GC_REAPING_KEYTYPE, key_gc_wait_bit,
 127                    TASK_UNINTERRUPTIBLE);
 128
 129        key_gc_dead_keytype = NULL;
 130        kleave("");
 131}
 132
 133/*
 134 * Garbage collect pointers from a keyring.
 135 *
 136 * Not called with any locks held.  The keyring's key struct will not be
 137 * deallocated under us as only our caller may deallocate it.
 138 */
 139static void key_gc_keyring(struct key *keyring, time_t limit)
 140{
 141        struct keyring_list *klist;
 142        int loop;
 143
 144        kenter("%x", key_serial(keyring));
 145
 146        if (keyring->flags & ((1 << KEY_FLAG_INVALIDATED) |
 147                              (1 << KEY_FLAG_REVOKED)))
 148                goto dont_gc;
 149
 150        /* scan the keyring looking for dead keys */
 151        rcu_read_lock();
 152        klist = rcu_dereference(keyring->payload.subscriptions);
 153        if (!klist)
 154                goto unlock_dont_gc;
 155
 156        loop = klist->nkeys;
 157        smp_rmb();
 158        for (loop--; loop >= 0; loop--) {
 159                struct key *key = rcu_dereference(klist->keys[loop]);
 160                if (key_is_dead(key, limit))
 161                        goto do_gc;
 162        }
 163
 164unlock_dont_gc:
 165        rcu_read_unlock();
 166dont_gc:
 167        kleave(" [no gc]");
 168        return;
 169
 170do_gc:
 171        rcu_read_unlock();
 172
 173        keyring_gc(keyring, limit);
 174        kleave(" [gc]");
 175}
 176
 177/*
 178 * Garbage collect a list of unreferenced, detached keys
 179 */
 180static noinline void key_gc_unused_keys(struct list_head *keys)
 181{
 182        while (!list_empty(keys)) {
 183                struct key *key =
 184                        list_entry(keys->next, struct key, graveyard_link);
 185                list_del(&key->graveyard_link);
 186
 187                kdebug("- %u", key->serial);
 188                key_check(key);
 189
 190                security_key_free(key);
 191
 192                /* deal with the user's key tracking and quota */
 193                if (test_bit(KEY_FLAG_IN_QUOTA, &key->flags)) {
 194                        spin_lock(&key->user->lock);
 195                        key->user->qnkeys--;
 196                        key->user->qnbytes -= key->quotalen;
 197                        spin_unlock(&key->user->lock);
 198                }
 199
 200                atomic_dec(&key->user->nkeys);
 201                if (test_bit(KEY_FLAG_INSTANTIATED, &key->flags))
 202                        atomic_dec(&key->user->nikeys);
 203
 204                key_user_put(key->user);
 205
 206                /* now throw away the key memory */
 207                if (key->type->destroy)
 208                        key->type->destroy(key);
 209
 210                kfree(key->description);
 211
 212#ifdef KEY_DEBUGGING
 213                key->magic = KEY_DEBUG_MAGIC_X;
 214#endif
 215                kmem_cache_free(key_jar, key);
 216        }
 217}
 218
 219/*
 220 * Garbage collector for unused keys.
 221 *
 222 * This is done in process context so that we don't have to disable interrupts
 223 * all over the place.  key_put() schedules this rather than trying to do the
 224 * cleanup itself, which means key_put() doesn't have to sleep.
 225 */
 226static void key_garbage_collector(struct work_struct *work)
 227{
 228        static LIST_HEAD(graveyard);
 229        static u8 gc_state;             /* Internal persistent state */
 230#define KEY_GC_REAP_AGAIN       0x01    /* - Need another cycle */
 231#define KEY_GC_REAPING_LINKS    0x02    /* - We need to reap links */
 232#define KEY_GC_SET_TIMER        0x04    /* - We need to restart the timer */
 233#define KEY_GC_REAPING_DEAD_1   0x10    /* - We need to mark dead keys */
 234#define KEY_GC_REAPING_DEAD_2   0x20    /* - We need to reap dead key links */
 235#define KEY_GC_REAPING_DEAD_3   0x40    /* - We need to reap dead keys */
 236#define KEY_GC_FOUND_DEAD_KEY   0x80    /* - We found at least one dead key */
 237
 238        struct rb_node *cursor;
 239        struct key *key;
 240        time_t new_timer, limit;
 241
 242        kenter("[%lx,%x]", key_gc_flags, gc_state);
 243
 244        limit = current_kernel_time().tv_sec;
 245        if (limit > key_gc_delay)
 246                limit -= key_gc_delay;
 247        else
 248                limit = key_gc_delay;
 249
 250        /* Work out what we're going to be doing in this pass */
 251        gc_state &= KEY_GC_REAPING_DEAD_1 | KEY_GC_REAPING_DEAD_2;
 252        gc_state <<= 1;
 253        if (test_and_clear_bit(KEY_GC_KEY_EXPIRED, &key_gc_flags))
 254                gc_state |= KEY_GC_REAPING_LINKS | KEY_GC_SET_TIMER;
 255
 256        if (test_and_clear_bit(KEY_GC_REAP_KEYTYPE, &key_gc_flags))
 257                gc_state |= KEY_GC_REAPING_DEAD_1;
 258        kdebug("new pass %x", gc_state);
 259
 260        new_timer = LONG_MAX;
 261
 262        /* As only this function is permitted to remove things from the key
 263         * serial tree, if cursor is non-NULL then it will always point to a
 264         * valid node in the tree - even if lock got dropped.
 265         */
 266        spin_lock(&key_serial_lock);
 267        cursor = rb_first(&key_serial_tree);
 268
 269continue_scanning:
 270        while (cursor) {
 271                key = rb_entry(cursor, struct key, serial_node);
 272                cursor = rb_next(cursor);
 273
 274                if (atomic_read(&key->usage) == 0)
 275                        goto found_unreferenced_key;
 276
 277                if (unlikely(gc_state & KEY_GC_REAPING_DEAD_1)) {
 278                        if (key->type == key_gc_dead_keytype) {
 279                                gc_state |= KEY_GC_FOUND_DEAD_KEY;
 280                                set_bit(KEY_FLAG_DEAD, &key->flags);
 281                                key->perm = 0;
 282                                goto skip_dead_key;
 283                        }
 284                }
 285
 286                if (gc_state & KEY_GC_SET_TIMER) {
 287                        if (key->expiry > limit && key->expiry < new_timer) {
 288                                kdebug("will expire %x in %ld",
 289                                       key_serial(key), key->expiry - limit);
 290                                new_timer = key->expiry;
 291                        }
 292                }
 293
 294                if (unlikely(gc_state & KEY_GC_REAPING_DEAD_2))
 295                        if (key->type == key_gc_dead_keytype)
 296                                gc_state |= KEY_GC_FOUND_DEAD_KEY;
 297
 298                if ((gc_state & KEY_GC_REAPING_LINKS) ||
 299                    unlikely(gc_state & KEY_GC_REAPING_DEAD_2)) {
 300                        if (key->type == &key_type_keyring)
 301                                goto found_keyring;
 302                }
 303
 304                if (unlikely(gc_state & KEY_GC_REAPING_DEAD_3))
 305                        if (key->type == key_gc_dead_keytype)
 306                                goto destroy_dead_key;
 307
 308        skip_dead_key:
 309                if (spin_is_contended(&key_serial_lock) || need_resched())
 310                        goto contended;
 311        }
 312
 313contended:
 314        spin_unlock(&key_serial_lock);
 315
 316maybe_resched:
 317        if (cursor) {
 318                cond_resched();
 319                spin_lock(&key_serial_lock);
 320                goto continue_scanning;
 321        }
 322
 323        /* We've completed the pass.  Set the timer if we need to and queue a
 324         * new cycle if necessary.  We keep executing cycles until we find one
 325         * where we didn't reap any keys.
 326         */
 327        kdebug("pass complete");
 328
 329        if (gc_state & KEY_GC_SET_TIMER && new_timer != (time_t)LONG_MAX) {
 330                new_timer += key_gc_delay;
 331                key_schedule_gc(new_timer);
 332        }
 333
 334        if (unlikely(gc_state & KEY_GC_REAPING_DEAD_2) ||
 335            !list_empty(&graveyard)) {
 336                /* Make sure that all pending keyring payload destructions are
 337                 * fulfilled and that people aren't now looking at dead or
 338                 * dying keys that they don't have a reference upon or a link
 339                 * to.
 340                 */
 341                kdebug("gc sync");
 342                synchronize_rcu();
 343        }
 344
 345        if (!list_empty(&graveyard)) {
 346                kdebug("gc keys");
 347                key_gc_unused_keys(&graveyard);
 348        }
 349
 350        if (unlikely(gc_state & (KEY_GC_REAPING_DEAD_1 |
 351                                 KEY_GC_REAPING_DEAD_2))) {
 352                if (!(gc_state & KEY_GC_FOUND_DEAD_KEY)) {
 353                        /* No remaining dead keys: short circuit the remaining
 354                         * keytype reap cycles.
 355                         */
 356                        kdebug("dead short");
 357                        gc_state &= ~(KEY_GC_REAPING_DEAD_1 | KEY_GC_REAPING_DEAD_2);
 358                        gc_state |= KEY_GC_REAPING_DEAD_3;
 359                } else {
 360                        gc_state |= KEY_GC_REAP_AGAIN;
 361                }
 362        }
 363
 364        if (unlikely(gc_state & KEY_GC_REAPING_DEAD_3)) {
 365                kdebug("dead wake");
 366                smp_mb();
 367                clear_bit(KEY_GC_REAPING_KEYTYPE, &key_gc_flags);
 368                wake_up_bit(&key_gc_flags, KEY_GC_REAPING_KEYTYPE);
 369        }
 370
 371        if (gc_state & KEY_GC_REAP_AGAIN)
 372                queue_work(system_nrt_wq, &key_gc_work);
 373        kleave(" [end %x]", gc_state);
 374        return;
 375
 376        /* We found an unreferenced key - once we've removed it from the tree,
 377         * we can safely drop the lock.
 378         */
 379found_unreferenced_key:
 380        kdebug("unrefd key %d", key->serial);
 381        rb_erase(&key->serial_node, &key_serial_tree);
 382        spin_unlock(&key_serial_lock);
 383
 384        list_add_tail(&key->graveyard_link, &graveyard);
 385        gc_state |= KEY_GC_REAP_AGAIN;
 386        goto maybe_resched;
 387
 388        /* We found a keyring and we need to check the payload for links to
 389         * dead or expired keys.  We don't flag another reap immediately as we
 390         * have to wait for the old payload to be destroyed by RCU before we
 391         * can reap the keys to which it refers.
 392         */
 393found_keyring:
 394        spin_unlock(&key_serial_lock);
 395        kdebug("scan keyring %d", key->serial);
 396        key_gc_keyring(key, limit);
 397        goto maybe_resched;
 398
 399        /* We found a dead key that is still referenced.  Reset its type and
 400         * destroy its payload with its semaphore held.
 401         */
 402destroy_dead_key:
 403        spin_unlock(&key_serial_lock);
 404        kdebug("destroy key %d", key->serial);
 405        down_write(&key->sem);
 406        key->type = &key_type_dead;
 407        if (key_gc_dead_keytype->destroy)
 408                key_gc_dead_keytype->destroy(key);
 409        memset(&key->payload, KEY_DESTROY, sizeof(key->payload));
 410        up_write(&key->sem);
 411        goto maybe_resched;
 412}
 413
lxr.linux.no kindly hosted by Redpill Linpro AS, provider of Linux consulting and operations services since 1995.