BUG/MEDIUM: ebtree: Invalid read when looking for dup entry

The first item inserted into an ebtree will be inserted directly below
the root, which is a simple struct eb_root which only holds two branch
pointers (left and right).
If we try to find a duplicated entry to this first leaf through a
ebmb_next_dup, our leaf_p pointer will point to the eb_root instead of a
complete eb_node so we cannot look for the bit part of our leaf_p since
it would try to cast our eb_root into an eb_node and perform an out of
bounds access when reading "eb_root_to_node(eb_untag(t,EB_LEFT)))->bit".
This bug was found by address sanitizer running on a CRL hot update VTC
test.

Note that the bug has been there since the import of the eb_next_dup()
and eb_prev_dup() function in 1.5-dev19 by commit 2b5702030 ("MINOR:
ebtree: add new eb_next_dup/eb_prev_dup() functions to visit duplicates").

It can be backported to all stable branches.

(cherry picked from commit 2608e348bec8a533225424fad06760ce6e19f167)
Signed-off-by: Christopher Faulet <cfaulet@haproxy.com>
(cherry picked from commit 0179e1d7aa4a15b5325e8e3744ef302a488893d6)
Signed-off-by: Christopher Faulet <cfaulet@haproxy.com>
(cherry picked from commit 42f9c53a8f1560845304b42a999c74453f15514b)
Signed-off-by: Christopher Faulet <cfaulet@haproxy.com>
(cherry picked from commit 3455079481bc6d53a320f62054922e5dbca27f94)
Signed-off-by: Christopher Faulet <cfaulet@haproxy.com>
diff --git a/ebtree/ebtree.h b/ebtree/ebtree.h
index cfb7851..bc8012d 100644
--- a/ebtree/ebtree.h
+++ b/ebtree/ebtree.h
@@ -615,12 +615,16 @@
 		t = (eb_root_to_node(eb_untag(t, EB_RGHT)))->node_p;
 	}
 
-	/* Note that <t> cannot be NULL at this stage */
+	/* Note that <t> cannot be NULL at this stage. If our leaf is directly
+	 * under the root, we must not try to cast the leaf_p into a eb_node*
+	 * since it is a pointer to an eb_root.
+	 */
+	if (eb_clrtag((eb_untag(t, EB_LEFT))->b[EB_RGHT]) == NULL)
+		return NULL;
+
 	if ((eb_root_to_node(eb_untag(t, EB_LEFT)))->bit >= 0)
 		return NULL;
 	t = (eb_untag(t, EB_LEFT))->b[EB_RGHT];
-	if (eb_clrtag(t) == NULL)
-		return NULL;
 	return eb_walk_down(t, EB_LEFT);
 }