KEYS: Make /proc/keys use keyid not numread as file position [try #6]

Make the file position maintained by /proc/keys represent the ID of the key
just read rather than the number of keys read.  This should make it faster to
perform a lookup as we don't have to scan the key ID tree from the beginning to
find the current position.

Signed-off-by: Serge E. Hallyn <serue@us.ibm.com>
Signed-off-by: David Howells <dhowells@redhat.com>
Signed-off-by: James Morris <jmorris@namei.org>

1 files changed, 55 insertions, 22 deletions

diff --git a/security/keys/proc.c b/security/keys/proc.c
index 39793c774f33..624c650c2efd 100644
--- a/security/keys/proc.c
+++ b/security/keys/proc.c
@@ -91,57 +91,90 @@ __initcall(key_proc_init);
  */
 #ifdef CONFIG_KEYS_DEBUG_PROC_KEYS
 
-static struct rb_node *__key_serial_next(struct rb_node *n)
+static struct rb_node *key_serial_next(struct rb_node *n)
 {
+        struct user_namespace *user_ns = current_user_ns();
+
+        n = rb_next(n);
         while (n) {
                 struct key *key = rb_entry(n, struct key, serial_node);
-                if (key->user->user_ns == current_user_ns())
+                if (key->user->user_ns == user_ns)
                         break;
                 n = rb_next(n);
         }
         return n;
 }
 
-static struct rb_node *key_serial_next(struct rb_node *n)
+static int proc_keys_open(struct inode *inode, struct file *file)
 {
-        return __key_serial_next(rb_next(n));
+        return seq_open(file, &proc_keys_ops);
 }
 
-static struct rb_node *key_serial_first(struct rb_root *r)
+static struct key *find_ge_key(key_serial_t id)
 {
-        struct rb_node *n = rb_first(r);
-        return __key_serial_next(n);
-}
+        struct user_namespace *user_ns = current_user_ns();
+        struct rb_node *n = key_serial_tree.rb_node;
+        struct key *minkey = NULL;
 
-static int proc_keys_open(struct inode *inode, struct file *file)
-{
-        return seq_open(file, &proc_keys_ops);
+        while (n) {
+                struct key *key = rb_entry(n, struct key, serial_node);
+                if (id < key->serial) {
+                        if (!minkey || minkey->serial > key->serial)
+                                minkey = key;
+                        n = n->rb_left;
+                } else if (id > key->serial) {
+                        n = n->rb_right;
+                } else {
+                        minkey = key;
+                        break;
+                }
+                key = NULL;
+        }
 
+        if (!minkey)
+                return NULL;
+
+        for (;;) {
+                if (minkey->user->user_ns == user_ns)
+                        return minkey;
+                n = rb_next(&minkey->serial_node);
+                if (!n)
+                        return NULL;
+                minkey = rb_entry(n, struct key, serial_node);
+        }
 }
 
 static void *proc_keys_start(struct seq_file *p, loff_t *_pos)
         __acquires(key_serial_lock)
 {
-        struct rb_node *_p;
-        loff_t pos = *_pos;
+        key_serial_t pos = *_pos;
+        struct key *key;
 
         spin_lock(&key_serial_lock);
 
-        _p = key_serial_first(&key_serial_tree);
-        while (pos > 0 && _p) {
-                pos--;
-                _p = key_serial_next(_p);
-        }
-
-        return _p;
+        if (*_pos > INT_MAX)
+                return NULL;
+        key = find_ge_key(pos);
+        if (!key)
+                return NULL;
+        *_pos = key->serial;
+        return &key->serial_node;
+}
 
+static inline key_serial_t key_node_serial(struct rb_node *n)
+{
+        struct key *key = rb_entry(n, struct key, serial_node);
+        return key->serial;
 }
 
 static void *proc_keys_next(struct seq_file *p, void *v, loff_t *_pos)
 {
-        (*_pos)++;
-        return key_serial_next((struct rb_node *) v);
+        struct rb_node *n;
 
+        n = key_serial_next(v);
+        if (n)
+                *_pos = key_node_serial(n);
+        return n;
 }
 
 static void proc_keys_stop(struct seq_file *p, void *v)