linux-kernel - [PATCH] lib/rbtree.c: fix typo in comment of ____rb_erase

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [day] [month] [year] [list]

Date:   Sun, 28 Aug 2016 21:31:55 +0800
From:   Jie Chen <fykcee1@...il.com>
To:     linux-kernel@...r.kernel.org
Cc:     weiyang@...ux.vnet.ibm.com, guangrong.xiao@...ux.intel.com,
        cee1 <fykcee1@...il.com>
Subject: [PATCH] lib/rbtree.c: fix typo in comment of ____rb_erase_color

From: cee1 <fykcee1@...il.com>

In Case 3 of `sibling == parent->rb_right':

Right rotation will not change color of sl and S in the diagram
(i.e. should not change "sl" to "Sl", "S" to "s")

In Case 3 of `sibling == parent->rb_left':

     (p)           (p)
     / \           / \
    S   N    -->  sr  N
   / \           /
  Sl  sr        S
               /
              Sl

  This is actually left rotation at "S", not right rotation.

In Case 4 of `sibling == parent->rb_left':

     (p)             (s)
     / \             / \
    S   N     -->   Sl  P
   / \                 / \
  sl (sr)            (sr) N

  This is actually right rotation at "(p)" + color flips, not left
  rotation + color flips.

Signed-off-by: Jie Chen <fykcee1@...il.com>
---
 lib/rbtree.c | 23 +++++++++++++++++++----
 1 file changed, 19 insertions(+), 4 deletions(-)

diff --git a/lib/rbtree.c b/lib/rbtree.c
index eb8a19f..1f8b112 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -296,11 +296,26 @@ ____rb_erase_color(struct rb_node *parent, struct rb_root *root,
 				 *
 				 *   (p)           (p)
 				 *   / \           / \
-				 *  N   S    -->  N   Sl
+				 *  N   S    -->  N   sl
 				 *     / \             \
-				 *    sl  Sr            s
+				 *    sl  Sr            S
 				 *                       \
 				 *                        Sr
+				 *
+				 * Note: p might be red, and then both
+				 * p and sl are red after rotation(which
+				 * breaks property 4). This is fixed in
+				 * Case 4 (in __rb_rotate_set_parents()
+				 *         which set sl the color of p
+				 *         and set p RB_BLACK)
+				 *
+				 *   (p)            (sl)
+				 *   / \            /  \
+				 *  N   sl   -->   P    S
+				 *       \        /      \
+				 *        S      N        Sr
+				 *         \
+				 *          Sr
 				 */
 				tmp1 = tmp2->rb_right;
 				WRITE_ONCE(sibling->rb_left, tmp1);
@@ -365,7 +380,7 @@ ____rb_erase_color(struct rb_node *parent, struct rb_root *root,
 					}
 					break;
 				}
-				/* Case 3 - right rotate at sibling */
+				/* Case 3 - left rotate at sibling */
 				tmp1 = tmp2->rb_left;
 				WRITE_ONCE(sibling->rb_right, tmp1);
 				WRITE_ONCE(tmp2->rb_left, sibling);
@@ -377,7 +392,7 @@ ____rb_erase_color(struct rb_node *parent, struct rb_root *root,
 				tmp1 = sibling;
 				sibling = tmp2;
 			}
-			/* Case 4 - left rotate at parent + color flips */
+			/* Case 4 - right rotate at parent + color flips */
 			tmp2 = sibling->rb_right;
 			WRITE_ONCE(parent->rb_left, tmp2);
 			WRITE_ONCE(sibling->rb_right, parent);
-- 
2.3.2 (Apple Git-55)