Gitweb:     
http://git.kernel.org/git/?p=linux/kernel/git/torvalds/linux-2.6.git;a=commit;h=9ad0830f307bcd8dc285cfae58998d43b21727f4
Commit:     9ad0830f307bcd8dc285cfae58998d43b21727f4
Parent:     768c242b30d9ec5581dd245e8289acb6b77815d1
Author:     David Howells <[EMAIL PROTECTED]>
AuthorDate: Tue Feb 6 13:45:51 2007 +0000
Committer:  Linus Torvalds <[EMAIL PROTECTED]>
CommitDate: Tue Feb 6 14:45:00 2007 -0800

    [PATCH] Keys: Fix key serial number collision handling
    
    Fix the key serial number collision avoidance code in key_alloc_serial().
    
    This didn't use to be so much of a problem as the key serial numbers were
    allocated from a simple incremental counter, and it would have to go through
    two billion keys before it could possibly encounter a collision.  However, 
now
    that random numbers are used instead, collisions are much more likely.
    
    This is fixed by finding a hole in the rbtree where the next unused serial
    number ought to be and using that by going almost back to the top of the
    insertion routine and redoing the insertion with the new serial number 
rather
    than trying to be clever and attempting to work out the insertion point
    pointer directly.
    
    This fixes kernel BZ #7727.
    
    Signed-off-by: David Howells <[EMAIL PROTECTED]>
    Signed-off-by: Linus Torvalds <[EMAIL PROTECTED]>
---
 security/keys/key.c |   33 ++++++++++++++-------------------
 1 files changed, 14 insertions(+), 19 deletions(-)

diff --git a/security/keys/key.c b/security/keys/key.c
index ac9326c..700400d 100644
--- a/security/keys/key.c
+++ b/security/keys/key.c
@@ -188,6 +188,7 @@ static inline void key_alloc_serial(struct key *key)
 
        spin_lock(&key_serial_lock);
 
+attempt_insertion:
        parent = NULL;
        p = &key_serial_tree.rb_node;
 
@@ -202,39 +203,33 @@ static inline void key_alloc_serial(struct key *key)
                else
                        goto serial_exists;
        }
-       goto insert_here;
+
+       /* we've found a suitable hole - arrange for this key to occupy it */
+       rb_link_node(&key->serial_node, parent, p);
+       rb_insert_color(&key->serial_node, &key_serial_tree);
+
+       spin_unlock(&key_serial_lock);
+       return;
 
        /* 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))
-                       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);
+               if (key->serial < 3) {
+                       key->serial = 3;
+                       goto attempt_insertion;
+               }
 
                parent = rb_next(parent);
                if (!parent)
-                       break;
+                       goto attempt_insertion;
 
                xkey = rb_entry(parent, struct key, serial_node);
                if (key->serial < xkey->serial)
-                       goto insert_here;
+                       goto attempt_insertion;
        }
 
-       /* 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);
-
-       spin_unlock(&key_serial_lock);
-
 } /* end key_alloc_serial() */
 
 /*****************************************************************************/
-
To unsubscribe from this list: send the line "unsubscribe git-commits-head" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Reply via email to