KEYS: Expand the capacity of a keyring

Expand the capacity of a keyring to be able to hold a lot more keys by using
the previously added associative array implementation.  Currently the maximum
capacity is:

	(PAGE_SIZE - sizeof(header)) / sizeof(struct key *)

which, on a 64-bit system, is a little more 500.  However, since this is being
used for the NFS uid mapper, we need more than that.  The new implementation
gives us effectively unlimited capacity.

With some alterations, the keyutils testsuite runs successfully to completion
after this patch is applied.  The alterations are because (a) keyrings that
are simply added to no longer appear ordered and (b) some of the errors have
changed a bit.

Signed-off-by: David Howells <dhowells@redhat.com>

9 files changed, 803 insertions, 762 deletions

diff --git a/include/keys/keyring-type.h b/include/keys/keyring-type.h
index cf49159b0e3a..fca5c62340a4 100644
--- a/include/keys/keyring-type.h
+++ b/include/keys/keyring-type.h
@@ -1,6 +1,6 @@
 /* Keyring key type
  *
- * Copyright (C) 2008 Red Hat, Inc. All Rights Reserved.
+ * Copyright (C) 2008, 2013 Red Hat, Inc. All Rights Reserved.
  * Written by David Howells (dhowells@redhat.com)
  *
  * This program is free software; you can redistribute it and/or
@@ -13,19 +13,6 @@
 #define _KEYS_KEYRING_TYPE_H
 
 #include <linux/key.h>
-#include <linux/rcupdate.h>
-
-/*
- * the keyring payload contains a list of the keys to which the keyring is
- * subscribed
- */
-struct keyring_list {
-        struct rcu_head rcu;            /* RCU deletion hook */
-        unsigned short  maxkeys;        /* max keys this list can hold */
-        unsigned short  nkeys;          /* number of keys currently held */
-        unsigned short  delkey;         /* key to be unlinked by RCU */
-        struct key __rcu *keys[0];
-};
-
+#include <linux/assoc_array.h>
 
 #endif /* _KEYS_KEYRING_TYPE_H */
diff --git a/include/linux/key.h b/include/linux/key.h
index ef596c7af585..2417f789d29b 100644
--- a/include/linux/key.h
+++ b/include/linux/key.h
@@ -22,6 +22,7 @@
 #include <linux/sysctl.h>
 #include <linux/rwsem.h>
 #include <linux/atomic.h>
+#include <linux/assoc_array.h>
 
 #ifdef __KERNEL__
 #include <linux/uidgid.h>
@@ -196,11 +197,13 @@ struct key {
          *   whatever
          */
         union {
-                unsigned long           value;
-                void __rcu              *rcudata;
-                void                    *data;
-                struct keyring_list __rcu *subscriptions;
-        } payload;
+                union {
+                        unsigned long           value;
+                        void __rcu              *rcudata;
+                        void                    *data;
+                } payload;
+                struct assoc_array keys;
+        };
 };
 
 extern struct key *key_alloc(struct key_type *type,
diff --git a/lib/assoc_array.c b/lib/assoc_array.c
index a0952818f938..17edeaf19180 100644
--- a/lib/assoc_array.c
+++ b/lib/assoc_array.c
@@ -12,6 +12,7 @@
  */
 //#define DEBUG
 #include <linux/slab.h>
+#include <linux/err.h>
 #include <linux/assoc_array_priv.h>
 
 /*
diff --git a/security/keys/Kconfig b/security/keys/Kconfig
index a90d6d300dbd..15e0dfe8c80f 100644
--- a/security/keys/Kconfig
+++ b/security/keys/Kconfig
@@ -4,6 +4,7 @@
 
 config KEYS
         bool "Enable access key retention support"
+        select ASSOCIATIVE_ARRAY
         help
           This option provides support for retaining authentication tokens and
           access keys in the kernel.
diff --git a/security/keys/gc.c b/security/keys/gc.c
index d67c97bb1025..cce621c33dce 100644
--- a/security/keys/gc.c
+++ b/security/keys/gc.c
@@ -130,6 +130,13 @@ void key_gc_keytype(struct key_type *ktype)
         kleave("");
 }
 
+static int key_gc_keyring_func(const void *object, void *iterator_data)
+{
+        const struct key *key = object;
+        time_t *limit = iterator_data;
+        return key_is_dead(key, *limit);
+}
+
 /*
  * Garbage collect pointers from a keyring.
  *
@@ -138,10 +145,9 @@ void key_gc_keytype(struct key_type *ktype)
  */
 static void key_gc_keyring(struct key *keyring, time_t limit)
 {
-        struct keyring_list *klist;
-        int loop;
+        int result;
 
-        kenter("%x", key_serial(keyring));
+        kenter("%x{%s}", keyring->serial, keyring->description ?: "");
 
         if (keyring->flags & ((1 << KEY_FLAG_INVALIDATED) |
                               (1 << KEY_FLAG_REVOKED)))
@@ -149,27 +155,17 @@ static void key_gc_keyring(struct key *keyring, time_t limit)
 
         /* scan the keyring looking for dead keys */
         rcu_read_lock();
-        klist = rcu_dereference(keyring->payload.subscriptions);
-        if (!klist)
-                goto unlock_dont_gc;
-
-        loop = klist->nkeys;
-        smp_rmb();
-        for (loop--; loop >= 0; loop--) {
-                struct key *key = rcu_dereference(klist->keys[loop]);
-                if (key_is_dead(key, limit))
-                        goto do_gc;
-        }
-
-unlock_dont_gc:
+        result = assoc_array_iterate(&keyring->keys,
+                                     key_gc_keyring_func, &limit);
         rcu_read_unlock();
+        if (result == true)
+                goto do_gc;
+
 dont_gc:
         kleave(" [no gc]");
         return;
 
 do_gc:
-        rcu_read_unlock();
-
         keyring_gc(keyring, limit);
         kleave(" [gc]");
 }
@@ -392,7 +388,6 @@ found_unreferenced_key:
          */
 found_keyring:
         spin_unlock(&key_serial_lock);
-        kdebug("scan keyring %d", key->serial);
         key_gc_keyring(key, limit);
         goto maybe_resched;
 
diff --git a/security/keys/internal.h b/security/keys/internal.h
index 73950bf8f875..581c6f688352 100644
--- a/security/keys/internal.h
+++ b/security/keys/internal.h
@@ -90,20 +90,23 @@ extern void key_type_put(struct key_type *ktype);
 
 extern int __key_link_begin(struct key *keyring,
                             const struct keyring_index_key *index_key,
-                            unsigned long *_prealloc);
+                            struct assoc_array_edit **_edit);
 extern int __key_link_check_live_key(struct key *keyring, struct key *key);
-extern void __key_link(struct key *keyring, struct key *key,
-                       unsigned long *_prealloc);
+extern void __key_link(struct key *key, struct assoc_array_edit **_edit);
 extern void __key_link_end(struct key *keyring,