[PATCH v1 3/4] fbarray: fix lookahead ignore mask handling

[Anatoly Burakov <anatoly.burakov@intel.com>]

When lookahead mask does not have its first bit set, we can infer that we've
lost our run. However, currently, we set ignore mask to ignore `need` number of
bits, which is incorrect because while there is no *current* run within those
bits, we might still be able to start a new run within those ignored bits later.

This issue is fixed by counting how many shifts it took to lose the run, and
this is the number of bits we should ignore (+1 to skip one we stopped on).
Also, add unit tests to reproduce the problem.

Fixes: c44d09811b40 ("eal: add shared indexed file-backed array")
Cc: stable@dpdk.org

Signed-off-by: Vipin P R <vipinp@vmware.com>
Signed-off-by: Anatoly Burakov <anatoly.burakov@intel.com>
---
 app/test/test_fbarray.c             | 28 ++++++++++++++++++++++++++++
 lib/eal/common/eal_common_fbarray.c | 13 ++++++++++---
 2 files changed, 38 insertions(+), 3 deletions(-)

diff --git a/app/test/test_fbarray.c b/app/test/test_fbarray.c
index 147d6e2a07..4b17ef6be3 100644
--- a/app/test/test_fbarray.c
+++ b/app/test/test_fbarray.c
@@ -755,6 +755,32 @@ static int test_lookbehind(void)
 	return TEST_SUCCESS;
 }
 
+static int test_lookahead_mask(void)
+{
+	/*
+	 * There is a certain type of lookahead behavior we want to test here,
+	 * namely masking of bits that were scanned with lookahead but that we
+	 * know do not match our criteria. This is achieved in following steps:
+	 *
+	 *   0. Look for a big enough chunk of free space (say, 62 elements)
+	 *   1. Trigger lookahead by breaking a run somewhere inside mask 0
+	 *      (indices 0-63)
+	 *   2. Fail lookahead by breaking the run somewhere inside mask 1
+	 *      (indices 64-127)
+	 *   3. Ensure that we can still find free space in mask 1 afterwards
+	 */
+
+	/* break run on first mask */
+	rte_fbarray_set_used(&param.arr, 61);
+	/* break run on second mask */
+	rte_fbarray_set_used(&param.arr, 70);
+
+	/* we expect to find free space at 71 */
+	TEST_ASSERT_EQUAL(rte_fbarray_find_next_n_free(&param.arr, 0, 62),
+			71, "Free chunk index is wrong\n");
+	return TEST_SUCCESS;
+}
+
 static struct unit_test_suite fbarray_test_suite = {
 	.suite_name = "fbarray autotest",
 	.setup = autotest_setup,
@@ -770,6 +796,8 @@ static struct unit_test_suite fbarray_test_suite = {
 		TEST_CASE_ST(empty_msk_test_setup, reset_array, test_empty),
 		TEST_CASE_ST(lookahead_test_setup, reset_array, test_lookahead),
 		TEST_CASE_ST(lookbehind_test_setup, reset_array, test_lookbehind),
+		/* setup for these tests is more complex so do it in test func */
+		TEST_CASE_ST(NULL, reset_array, test_lookahead_mask),
 		TEST_CASES_END()
 	}
 };
diff --git a/lib/eal/common/eal_common_fbarray.c b/lib/eal/common/eal_common_fbarray.c
index b4f0b0b0c3..195f8394be 100644
--- a/lib/eal/common/eal_common_fbarray.c
+++ b/lib/eal/common/eal_common_fbarray.c
@@ -216,6 +216,8 @@ find_next_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n,
 		for (lookahead_idx = msk_idx + 1; lookahead_idx < msk->n_masks;
 				lookahead_idx++) {
 			unsigned int s_idx, need;
+			uint64_t first_bit = 1;
+
 			lookahead_msk = msk->data[lookahead_idx];
 
 			/* if we're looking for free space, invert the mask */
@@ -225,17 +227,22 @@ find_next_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n,
 			/* figure out how many consecutive bits we need here */
 			need = RTE_MIN(left, MASK_ALIGN);
 
-			for (s_idx = 0; s_idx < need - 1; s_idx++)
+			/* count number of shifts we performed */
+			for (s_idx = 0; s_idx < need - 1; s_idx++) {
 				lookahead_msk &= lookahead_msk >> 1ULL;
+				/* did we lose the run yet? */
+				if ((lookahead_msk & first_bit) == 0)
+					break;
+			}
 
 			/* if first bit is not set, we've lost the run */
-			if ((lookahead_msk & 1) == 0) {
+			if ((lookahead_msk & first_bit) == 0) {
 				/*
 				 * we've scanned this far, so we know there are
 				 * no runs in the space we've lookahead-scanned
 				 * as well, so skip that on next iteration.
 				 */
-				ignore_msk = ~((1ULL << need) - 1);
+				ignore_msk = ~((1ULL << (s_idx + 1)) - 1);
 				/* outer loop will increment msk_idx so add 1 */
 				msk_idx = lookahead_idx - 1;
 				break;
-- 
2.43.0