Skip to contentSkip to conversation

*** Memory Allocation: Fixes ignore_msk during find_next_n() in fb_array library***

PATCH In review Vipin P R 3 participants 7 messages Jan 15, 2023 – May 22, 2023

lore
Share & tools
lore

Vipin P R

author
#0 lore raw

cover *** Memory Allocation: Fixes ignore_msk during find_next_n() in fb_array library***

***
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(-)
Signature · 1 line
2.7.4
author
#1 lore raw

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

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

---
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(-)
lib/eal/common/eal_common_fbarray.c +6 -1
index 90240e8..313681a 100644
@@ -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;
 			}
Signature · 1 line
2.7.4
Reviewed-by on v1 1/2
#2 lore raw

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

Hi Vipin,

Quoted 2 lines · Vipin P R

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")
Quoted 17 lines

---
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(-)
lib/eal/common/eal_common_fbarray.c +0 -0
index 90240e8..313681a 100644

lib/eal/common/eal_common_fbarray.c find_next_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n, · line 243

Quoted 10 lines
lib/eal/common/eal_common_fbarray.c +6 -1
@@ -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,

Signature · 2 lines
Thanks,
Anatoly
author
#3 lore raw

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

In reply to Vipin P R

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

---
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(-)
lib/eal/common/eal_common_fbarray.c +18 -3
index 313681a..29fffb6 100644
@@ -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;
Signature · 1 line
2.7.4
#4 lore raw

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

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.

Quoted 3 lines · Vipin P R

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.

Quoted 16 lines

---
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(-)
lib/eal/common/eal_common_fbarray.c +0 -0
index 313681a..29fffb6 100644

lib/eal/common/eal_common_fbarray.c find_next_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n, · line 141

Quoted 5 lines
lib/eal/common/eal_common_fbarray.c +1 -1
@@ -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?

Quoted 32 lines
lib/eal/common/eal_common_fbarray.c +8 -2
  		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_. */

lib/eal/common/eal_common_fbarray.c find_next_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n, · line 258

Quoted 10 lines
lib/eal/common/eal_common_fbarray.c +9 -0
+					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?

Quoted 2 lines
lib/eal/common/eal_common_fbarray.c +0 -0
  				msk_idx = lookahead_idx - 1;
  				break;
Signature · 2 lines
Thanks,
Anatoly
author
#5 lore raw

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

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 <[email protected]>
Sent: 19 May 2023 22:15
To: Vipin P R <[email protected]>
Cc: [email protected] <[email protected]>; [email protected] <[email protected]>
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.

Quoted 3 lines · Vipin P R

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.

Quoted 16 lines

---
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(-)
lib/eal/common/eal_common_fbarray.c +0 -0
index 313681a..29fffb6 100644

lib/eal/common/eal_common_fbarray.c find_next_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n, · line 141

Quoted 5 lines
lib/eal/common/eal_common_fbarray.c +1 -1
@@ -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?

Quoted 32 lines
lib/eal/common/eal_common_fbarray.c +8 -2
              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_. */

lib/eal/common/eal_common_fbarray.c find_next_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n, · line 258

Quoted 10 lines
lib/eal/common/eal_common_fbarray.c +9 -0
+                                     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?

lib/eal/common/eal_common_fbarray.c find_next_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n, · line 260

Quoted 2 lines
lib/eal/common/eal_common_fbarray.c +0 -0
                              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.

#6 lore raw
In reply to Vipin P R

Anatoly, please could you look at this?

13/01/2023 14:14, Vipin P R:

Quoted 47 lines

***
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(-)