Bug#398470: fix for oops caused by key serial collisions
The oops is being caused by collisions in the key serial allocation code
and subsequent corruption being introduced into the key serial rbtree.
The following patch against 2.6.18 will fix it. Bug also exists in
2.6.19 and 2.6.20; it is patched in 2.6.21 going forward.
---
Fix rbtree corruption causing oops in key serial allocation.
Premature optimization in key_alloc_serial contained bugs which were
exposed by the change to random serial selection in 2.6.18. This patch
fixes that by properly traversing the rbtree when dealing with collisions.
It also returns -ENOMEM when there are no more serials left to allocate
(which would be hard to do, but still).
---
commit 74dde47f248cceb6f7964543a84d5d48cbd0118f
tree 49a18110c7b1c24f8b9ce0353a6bfd026e535cf5
parent e478bec0ba0a83a48a0f6982934b6de079e7e6b3
author Matt Mitchell <mm@fairfax-deb.localdomain> Fri, 09 Feb 2007
12:37:02 -0600
committer Matt Mitchell <mm@fairfax-deb.localdomain> Fri, 09 Feb 2007
12:37:02 -0600
security/keys/key.c | 58
++++++++++++++++++++++++++-------------------------
1 files changed, 30 insertions(+), 28 deletions(-)
diff --git a/security/keys/key.c b/security/keys/key.c
index 80de8c3..d8f5cc2 100644
--- a/security/keys/key.c
+++ b/security/keys/key.c
@@ -178,12 +178,17 @@ static inline void key_alloc_serial(struct key *key)
struct rb_node *parent, **p;
struct key *xkey;
+ key_serial_t orig;
+ int keyspace_loop;
+
/* propose a random serial number and look for a hole for it in the
* serial number tree */
do {
get_random_bytes(&key->serial, sizeof(key->serial));
key->serial >>= 1; /* negative numbers are not permitted */
+ orig = key->serial;
+ keyspace_loop = 0;
} while (key->serial < 3);
spin_lock(&key_serial_lock);
@@ -199,37 +204,29 @@ static inline void key_alloc_serial(struct key *key)
p = &(*p)->rb_left;
else if (key->serial > xkey->serial)
p = &(*p)->rb_right;
- else
- goto serial_exists;
- }
- goto insert_here;
-
- /* we found a key with the proposed serial number - walk the tree from
- * that point looking for the next unused serial number */
-serial_exists:
- for (;;) {
- key->serial++;
- if (key->serial < 2)
- key->serial = 2;
-
- if (!rb_parent(parent))
+ else {
+ /* if we have already looped, check for exhausted
+ * keyspace */
+ if ((keyspace_loop == 1) && (key->serial >= orig)) {
+ /* this is just a dummy */
+ key->serial = -1;
+ spin_unlock(&key_serial_lock);
+ printk(KERN_WARNING "key_alloc_serial: "
+ "keyspace exhausted\n");
+ return;
+ }
+
+ key->serial++;
+ if (key->serial < 2) {
+ keyspace_loop = 1;
+ key->serial = 2;
+ }
+ parent = NULL;
p = &key_serial_tree.rb_node;
- else if (rb_parent(parent)->rb_left == parent)
- p = &(rb_parent(parent)->rb_left);
- else
- p = &(rb_parent(parent)->rb_right);
-
- parent = rb_next(parent);
- if (!parent)
- break;
-
- xkey = rb_entry(parent, struct key, serial_node);
- if (key->serial < xkey->serial)
- goto insert_here;
+ }
}
/* we've found a suitable hole - arrange for this key to occupy it */
-insert_here:
rb_link_node(&key->serial_node, parent, p);
rb_insert_color(&key->serial_node, &key_serial_tree);
@@ -326,9 +323,14 @@ struct key *key_alloc(struct key_type *type, const
char *desc,
goto security_error;
/* publish the key by giving it a serial number */
- atomic_inc(&user->nkeys);
key_alloc_serial(key);
+ /* check for success */
+ if (key->serial == -1)
+ goto no_memory_3;
+ else
+ atomic_inc(&user->nkeys);
+
error:
return key;
Reply to: