btt: Fix overlapping IO stats.

Keep scanning the tree for overlapping IO otherwise Q2G and process
traces will be incorrect.

Let assume we have 2 IOs:

A                                      A+a
       B                B+b

In the red/black tree we have:

                    o -> [A,A+a]
                   / \
                left right
                 /    \
           [...]o      o -> [B, B+b]

In the current code, if we would not be able to find [B+b] in the tree:
B is greater than A, so we won't go left
B+b is smaller than A+a, so we are not going right either.

When we have a [X, X+x] IO to look for:
We need to check for right when either:
 X+x >= A+a (for merged IO)
 X > A (for overlapping IO)

TEST=Check with a trace with overlapping IO: Q2C and Q2G are expected.

Signed-off-by: Gwendal Grignou <>
Signed-off-by: Jens Axboe <>
diff --git a/btt/dip_rb.c b/btt/dip_rb.c
index 2aa7ffc..6efef6c 100644
--- a/btt/dip_rb.c
+++ b/btt/dip_rb.c
@@ -57,7 +57,7 @@
 		__iop = rb_entry(n, struct io, rb_node);
 		if (sec < BIT_START(__iop))
 			n = n->rb_left;
-		else if (sec >= BIT_END(__iop))
+		else if (sec > BIT_START(__iop))
 			n = n->rb_right;
 			return __iop;
@@ -82,7 +82,7 @@
 		if (iop_s < this_s)
 			rb_foreach(n->rb_left, iop, fnc, head);
-		if (this_e < iop_e)
+		if ((this_e < iop_e) || (this_s < iop_s))
 			rb_foreach(n->rb_right, iop, fnc, head);