Hi,
This is technically not a bug fix but an improvement to the lookahead
algorithm, so I don't think this needs a Fixes: tag or a Cc to stable.
On 1/13/2023 1:14 PM, Vipin P R wrote:
Ignore mask ignores essential bits WHICH could have been contiguous.
This commit aims to rectify that
Suggested rewording:
fbarray: improve lookahead ignore mask handling
Currently, when lookahead mask does not have its first bit set but has
other bits set, we do not set any ignore masks to avoid potentially
ignoring useful bits.
We can still ignore some bits, because we can rely on the fact that
we're looking for `need` bits, and lookahead mask does give us
information about whether there are other potential places we can start
looking for runs in the next iteration.
Address this by ignoring least significant clear bits in our lookahead
mask on next iteration.
Cc: sta...@dpdk.org
Signed-off-by: Vipin P R <vip...@vmware.com>
Acked-by: Kumara Parameshwaran <kparamesh...@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_;
`lookahead_msk_` doesn't need to be in the outer loop, IMO it can be
moved inside the lookahead code. Also, `lookahead_msk_` is not a very
informative name. Maybe change it to `lookahead_old` or similar?
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);
}
I don't quite understand what's happening here. Or rather, I kind of do,
but I don't understand why we don't just 1) find first set bit in
lookahead mask, and 2) ignore all preceding bits?
E.g. something like:
/* find first set bit */
fsb_idx = __builtin_ffsll(lookahead_msk);
/* ignore all preceding bits */
ignore_msk = ~((1ULL << fsb_idx) - 1);
would be much simpler and achieve the same result, would it not?
msk_idx = lookahead_idx - 1;
break;
--
Thanks,
Anatoly
