[PATCH 0/2] *** Memory Allocation: Fixes ignore_msk during find_next_n() in fb_array library***

[PATCH 0/2] *** Memory Allocation: Fixes ignore_msk during find_next_n() in fb_array library***

[Vipin P R]

*** 
In the lookahead logic, let's say after the Right-Shift-And operation to check for contiguity, we hit case http://code.dpdk.org/dpdk/latest/source/lib/eal/common/eal_common_fbarray.c#L235

            /* if first bit is not set, we've lost the run */
            if ((lookahead_msk & 1) == 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);
                msk_idx = lookahead_idx;
                break;
            }
        lets say for mask size of 64 bits : in msk_idx 4 we need 4 consecutive bits.
        let need = 4. 
        lets say some of the bits starting from LSB are xx11011. 
        Operating on the inverted mask for better clarity. RSA - RightShiftAnd, xx -- don't-care bits before

        This condition could hit if there aren't "need" number of contiguous bits starting from LSB.
        But, that doesn't necessarily mean there aren't "need" number of such bits elsewhere in the same lookahead_idx.
        We seem to be ignoring "need" number of bits starting from the LSB for the next iteration.

        Due to ignore_mask we might end losing some bits.
        /* if we have an ignore mask, ignore once */
        if (ignore_msk) {
            cur_msk &= ignore_msk;
            ignore_msk = 0;
        }
e.g.
lookahead_msk before RSA logic : xx11100 , need = 4, 2 bits lost
lookahead_msk before RSA logic : xx11011, need = 4, 1 bit lost
lookahead_msk before RSA logic : xx11110, need = 4, 3 bits lost

NB : To understand the number of bits lost, look at need; that's the number of bits (starting from LSB) that's cleared to zero before the next iteration.
***

Vipin P R (2):
  Memory Allocation: Fixes ignore_msk during find_next_n() in fb_array
    library
  Memory Allocation: Alternative fix for ignore_msk during find_next_n()
    in fb_array library

 lib/eal/common/eal_common_fbarray.c | 26 +++++++++++++++++++++++---
 1 file changed, 23 insertions(+), 3 deletions(-)

-- 
2.7.4

[PATCH 1/2] Memory Allocation: Fixes 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@dpdk.org

Signed-off-by: Vipin P R <vipinp@vmware.com>
Acked-by: Kumara Parameshwaran <kparameshwar@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 | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)

diff --git a/lib/eal/common/eal_common_fbarray.c b/lib/eal/common/eal_common_fbarray.c
index 90240e8..313681a 100644
--- a/lib/eal/common/eal_common_fbarray.c
+++ b/lib/eal/common/eal_common_fbarray.c
@@ -235,7 +235,12 @@ find_next_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n,
 				 * no runs in the space we've lookahead-scanned
 				 * as well, so skip that on next iteration.
 				 */
-				ignore_msk = ~((1ULL << need) - 1);
+				if (!lookahead_msk) {
+					/* 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);
+				}
 				msk_idx = lookahead_idx - 1;
 				break;
 			}
-- 
2.7.4

Re: [PATCH 1/2] Memory Allocation: Fixes ignore_msk during find_next_n() in fb_array library

[Burakov, Anatoly]

Hi Vipin,

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: fix incorrect lookahead ignore mask

Currently, when lookahead reaches a point where we've lost the run, we 
set ignore mask to ignore N bits we were looking for for lookahead. The 
problem is, because we're only looking at first bit after collapsing 
next N bits into it, we end up ignoring bits that could've potentially 
started a new run not from the first bit.

To reproduce this issue, we need to do the following:

1) Look for N bits where 64 > N > 1 (to enable lookahead behavior)
2) Set last bit of mask M (to trigger lookahead)
3) Leave first bit of mask M+1 unset (to create incorrect ignore mask)
4) Have next N bits of mask M+1 set

For example:

1) Look for 3 bits
2) Set bit 63 (last bit of first mask)
3) Leave bit 64 unset (first bit of second mask)
4) Set bits 65-67

With current code, we will not find a run starting from bit 65, because 
we set ignore mask to ignore first 3 bits of second mask.

Fix this behavior by only setting the ignore mask when we know there 
were no bits in the mask at all, so there's no chance in skipping bits 
that could've been useful to us.

Fixes: c44d09811b40 ("eal: add shared indexed file-backed array")

> 
> Cc: stable@dpdk.org
> 
> Signed-off-by: Vipin P R <vipinp@vmware.com>
> Acked-by: Kumara Parameshwaran <kparameshwar@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 | 7 ++++++-
>   1 file changed, 6 insertions(+), 1 deletion(-)
> 
> diff --git a/lib/eal/common/eal_common_fbarray.c b/lib/eal/common/eal_common_fbarray.c
> index 90240e8..313681a 100644
> --- a/lib/eal/common/eal_common_fbarray.c
> +++ b/lib/eal/common/eal_common_fbarray.c
> @@ -235,7 +235,12 @@ find_next_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n,
>   				 * no runs in the space we've lookahead-scanned
>   				 * as well, so skip that on next iteration.
>   				 */
> -				ignore_msk = ~((1ULL << need) - 1);
> +				if (!lookahead_msk) {
> +					/* 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);
> +				}

Great find! Needs a unit test though. I've described in the commit 
message how to reproduce this behavior, should be trivial to implement 
it as a unit test.

With above changes,

Reviewed-by: Anatoly Burakov <anatoly.burakov@intel.com>

-- 
Thanks,
Anatoly

[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@dpdk.org

Signed-off-by: Vipin P R <vipinp@vmware.com>
Acked-by: Kumara Parameshwaran <kparameshwar@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

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

[Burakov, Anatoly]

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: stable@dpdk.org
> 
> Signed-off-by: Vipin P R <vipinp@vmware.com>
> Acked-by: Kumara Parameshwaran <kparameshwar@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

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

[Vipin P R]

[-- Attachment #1: Type: text/plain, Size: 6044 bytes --]

Hi Burakov,

sure, will amend the changeset. currently I'm travelling, will get back by the end of this week if that's ok.
________________________________
From: Burakov, Anatoly <anatoly.burakov@intel.com>
Sent: 19 May 2023 22:15
To: Vipin P R <vipinp@vmware.com>
Cc: dev@dpdk.org <dev@dpdk.org>; stable@dpdk.org <stable@dpdk.org>
Subject: Re: [PATCH 2/2] Memory Allocation: Alternative fix for ignore_msk during find_next_n() in fb_array library

!! External Email

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: stable@dpdk.org
>
> Signed-off-by: Vipin P R <vipinp@vmware.com>
> Acked-by: Kumara Parameshwaran <kparameshwar@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


!! External Email: This email originated from outside of the organization. Do not click links or open attachments unless you recognize the sender.

[-- Attachment #2: Type: text/html, Size: 13621 bytes --]

Re: [PATCH 0/2] *** Memory Allocation: Fixes ignore_msk during find_next_n() in fb_array library***

[Thomas Monjalon]

Anatoly, please could you look at this?


13/01/2023 14:14, Vipin P R:
> *** 
> In the lookahead logic, let's say after the Right-Shift-And operation to check for contiguity, we hit case http://code.dpdk.org/dpdk/latest/source/lib/eal/common/eal_common_fbarray.c#L235
> 
>             /* if first bit is not set, we've lost the run */
>             if ((lookahead_msk & 1) == 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);
>                 msk_idx = lookahead_idx;
>                 break;
>             }
>         lets say for mask size of 64 bits : in msk_idx 4 we need 4 consecutive bits.
>         let need = 4. 
>         lets say some of the bits starting from LSB are xx11011. 
>         Operating on the inverted mask for better clarity. RSA - RightShiftAnd, xx -- don't-care bits before
> 
>         This condition could hit if there aren't "need" number of contiguous bits starting from LSB.
>         But, that doesn't necessarily mean there aren't "need" number of such bits elsewhere in the same lookahead_idx.
>         We seem to be ignoring "need" number of bits starting from the LSB for the next iteration.
> 
>         Due to ignore_mask we might end losing some bits.
>         /* if we have an ignore mask, ignore once */
>         if (ignore_msk) {
>             cur_msk &= ignore_msk;
>             ignore_msk = 0;
>         }
> e.g.
> lookahead_msk before RSA logic : xx11100 , need = 4, 2 bits lost
> lookahead_msk before RSA logic : xx11011, need = 4, 1 bit lost
> lookahead_msk before RSA logic : xx11110, need = 4, 3 bits lost
> 
> NB : To understand the number of bits lost, look at need; that's the number of bits (starting from LSB) that's cleared to zero before the next iteration.
> ***
> 
> Vipin P R (2):
>   Memory Allocation: Fixes ignore_msk during find_next_n() in fb_array
>     library
>   Memory Allocation: Alternative fix for ignore_msk during find_next_n()
>     in fb_array library
> 
>  lib/eal/common/eal_common_fbarray.c | 26 +++++++++++++++++++++++---
>  1 file changed, 23 insertions(+), 3 deletions(-)
> 
>