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

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

When lookahead mask does not have its last bit set, we can infer that we've lost
our run. However, currently, we set ignore mask to ignore first `need` bits,
which is incorrect for two reasons: first, using `need` bits as ignore bit count
means we might miss opportunities to start a new run within those bits, and more
improtantly when doing lookbehind, we start looking from the top, so we should
be ignoring *last* N bits, not *first* N bits of the mask.

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 from the top (+1 to skip one we
stopped on). Also, add unit tests to reproduce the problem.

Fixes: e1ca5dc86226 ("fbarray: add reverse finding of chunk")
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             | 27 +++++++++++++++++++++++++++
 lib/eal/common/eal_common_fbarray.c |  9 +++++++--
 2 files changed, 34 insertions(+), 2 deletions(-)

diff --git a/app/test/test_fbarray.c b/app/test/test_fbarray.c
index 4b17ef6be3..13c6691e50 100644
--- a/app/test/test_fbarray.c
+++ b/app/test/test_fbarray.c
@@ -781,6 +781,32 @@ static int test_lookahead_mask(void)
 	return TEST_SUCCESS;
 }
 
+static int test_lookbehind_mask(void)
+{
+	/*
+	 * There is a certain type of lookbehind behavior we want to test here,
+	 * namely masking of bits that were scanned with lookbehind but that we
+	 * know do not match our criteria. This is achieved in two steps:
+	 *
+	 *   0. Look for a big enough chunk of free space (say, 62 elements)
+	 *   1. Trigger lookbehind by breaking a run somewhere inside mask 2
+	 *      (indices 128-191)
+	 *   2. Fail lookbehind 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 mask 2 */
+	rte_fbarray_set_used(&param.arr, 130);
+	/* break run on mask 1 */
+	rte_fbarray_set_used(&param.arr, 70);
+
+	/* start from 190, we expect to find free space at 8 */
+	TEST_ASSERT_EQUAL(rte_fbarray_find_prev_n_free(&param.arr, 190, 62),
+			8, "Free chunk index is wrong\n");
+	return TEST_SUCCESS;
+}
+
 static struct unit_test_suite fbarray_test_suite = {
 	.suite_name = "fbarray autotest",
 	.setup = autotest_setup,
@@ -798,6 +824,7 @@ static struct unit_test_suite fbarray_test_suite = {
 		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_CASE_ST(NULL, reset_array, test_lookbehind_mask),
 		TEST_CASES_END()
 	}
 };
diff --git a/lib/eal/common/eal_common_fbarray.c b/lib/eal/common/eal_common_fbarray.c
index 195f8394be..63d8b731f5 100644
--- a/lib/eal/common/eal_common_fbarray.c
+++ b/lib/eal/common/eal_common_fbarray.c
@@ -508,8 +508,13 @@ find_prev_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++) {
 				lookbehind_msk &= lookbehind_msk << 1ULL;
+				/* did we lose the run yet? */
+				if ((lookbehind_msk & last_bit) == 0)
+					break;
+			}
 
 			/* if last bit is not set, we've lost the run */
 			if ((lookbehind_msk & last_bit) == 0) {
@@ -518,7 +523,7 @@ find_prev_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n,
 				 * no runs in the space we've lookbehind-scanned
 				 * as well, so skip that on next iteration.
 				 */
-				ignore_msk = UINT64_MAX << need;
+				ignore_msk = ~(UINT64_MAX << (MASK_ALIGN - s_idx - 1));
 				/* outer loop will decrement msk_idx so add 1 */
 				msk_idx = lookbehind_idx + 1;
 				break;
-- 
2.43.0