[PATCH 2/2] Memory Allocation: Alternative fix for ignore_msk during find_next_n() in fb_array library

[Vipin P R]

Ignore mask ignores essential bits WHICH could have been contiguous.
This commit aims to rectify that

Cc: stable at dpdk.org

Signed-off-by: Vipin P R <vipinp at vmware.com>
Acked-by: Kumara Parameshwaran <kparameshwar at vmware.com>
---
Depends-on: 0001-Memory-Allocation-Fixes-ms_idx-jump-lookahead-during.patch
Depends-on: 0002-Memory-Allocation-Fixes-ms_idx-jump-lookbehind-durin.patch
---
 lib/eal/common/eal_common_fbarray.c | 21 ++++++++++++++++++---
 1 file changed, 18 insertions(+), 3 deletions(-)

diff --git a/lib/eal/common/eal_common_fbarray.c b/lib/eal/common/eal_common_fbarray.c
index 313681a..29fffb6 100644
--- a/lib/eal/common/eal_common_fbarray.c
+++ b/lib/eal/common/eal_common_fbarray.c
@@ -138,7 +138,7 @@ find_next_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n,
 	last_msk = ~(UINT64_MAX << last_mod);
 
 	for (msk_idx = first; msk_idx < msk->n_masks; msk_idx++) {
-		uint64_t cur_msk, lookahead_msk;
+		uint64_t cur_msk, lookahead_msk, lookahead_msk_;
 		unsigned int run_start, clz, left;
 		bool found = false;
 		/*
@@ -215,12 +215,14 @@ 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;
+			unsigned int s_idx, need, fsb_idx, fcb_idx, ignore_bits;
 			lookahead_msk = msk->data[lookahead_idx];
 
 			/* if we're looking for free space, invert the mask */
 			if (!used)
 				lookahead_msk = ~lookahead_msk;
+			
+			lookahead_msk_ = lookahead_msk;
 
 			/* figure out how many consecutive bits we need here */
 			need = RTE_MIN(left, MASK_ALIGN);
@@ -236,10 +238,23 @@ find_next_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n,
 				 * as well, so skip that on next iteration.
 				 */
 				if (!lookahead_msk) {
-					/* There aren't "need" number of contiguous bits anywhere in the mask. 
+					/* There aren't "need" number of contiguous bits anywhere in the mask.
 					 * Ignore these many number of bits from LSB for the next iteration. 
 					 */
 					ignore_msk = ~((1ULL << need) - 1);
+				} else {
+					/* Find the first clear bit */
+					fcb_idx = __builtin_ffsll((~lookahead_msk_));
+					/* clear all bits upto the first clear bit in lookahead_msk_. */
+					lookahead_msk_ = lookahead_msk_ & ((~0ULL) << fcb_idx);
+					/* find the first set bit in the modified mask */
+					fsb_idx = __builtin_ffsll(lookahead_msk_);
+					/* number of bits to ignore from the next iteration */
+					ignore_bits = fsb_idx - 1;
+					/* ignore all bits preceding the first set bit after the first clear bit
+					 * starting from LSB of lookahead_msk_. 
+					 */
+					ignore_msk = ~((1ULL << ignore_bits) - 1);
 				}
 				msk_idx = lookahead_idx - 1;
 				break;
-- 
2.7.4