btt: Fix overlapping IO stats.
authorGwendal Grignou <gwendal@chromium.org>
Fri, 18 Aug 2017 22:00:22 +0000 (15:00 -0700)
committerJens Axboe <axboe@kernel.dk>
Tue, 7 Nov 2017 18:25:38 +0000 (11:25 -0700)
commit8fc451c6b0b9a7db7c376ea6865c35321e561f00
treeecbc1551e497e0b60e3ddf88b106e2fc9df4815c
parent07d76e12aa46fa0bad4b736d581ec5aca62264f7
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)
and
 X > A (for overlapping IO)

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

Signed-off-by: Gwendal Grignou <gwendal@chromium.org>
Signed-off-by: Jens Axboe <axboe@kernel.dk>
btt/dip_rb.c