[PATCH 02/17] rbtree: optimize root-check during rebalancing loop

[Davidlohr Bueso]

The only times the nil-parent (root node) condition is true is
when the node is the first in the tree, or after fixing rbtree
rule #4 and the case 1 rebalancing made the node the root. Such
conditions do not apply most of the time:

(i) The common case in an rbtree is to have more than a single
node, so this is only true for the first rb_insert().

(ii) While there is a chance only one first rotation is needed,
cases where the node's uncle is black (cases 2,3) are more
common as we can have the following scenarios during the rotation
looping:

    case1 only, case1+1, case2+3, case1+2+3, case3 only, etc.

This patch, therefore, adds an unlikely() optimization to this
conditional. When profiling with CONFIG_PROFILE_ANNOTATED_BRANCHES,
a kernel build shows that the incorrect rate is less than 15%, and
for workloads that involve insert mostly trees overtime tend to
have less than 2% incorrect rate.

Signed-off-by: Davidlohr Bueso <dbueso@xxxxxxx>
---
 lib/rbtree.c | 23 ++++++++++++++++-------
 1 file changed, 16 insertions(+), 7 deletions(-)

diff --git a/lib/rbtree.c b/lib/rbtree.c
index d102d9d2ffaa..e7cce12f404f 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -105,16 +105,25 @@ __rb_insert(struct rb_node *node, struct rb_root *root,
 
 	while (true) {
 		/*
-		 * Loop invariant: node is red
-		 *
-		 * If there is a black parent, we are done.
-		 * Otherwise, take some corrective action as we don't
-		 * want a red root or two consecutive red nodes.
+		 * Loop invariant: node is red.
 		 */
-		if (!parent) {
+		if (unlikely(!parent)) {
+			/*
+			 * The inserted node is root. Either this is the
+			 * first node, or we recursed at Case 1 below and
+			 * are no longer violating 4).
+			 */
 			rb_set_parent_color(node, NULL, RB_BLACK);
 			break;
-		} else if (rb_is_black(parent))
+		}
+
+		/*
+		 * If there is a black parent, we are done.
+		 * Otherwise, take some corrective action as,
+		 * per 4), we don't want a red root or two
+		 * consecutive red nodes.
+		 */
+		if(rb_is_black(parent))
 			break;
 
 		gparent = rb_red_parent(parent);
-- 
2.12.0