* Re: [PATCH 1/2] Memory Allocation: Fixes ignore_msk during find_next_n() in fb_array library [not found] ` <1673615669-21011-2-git-send-email-vipinp@vmware.com> @ 2023-05-19 16:23 ` Burakov, Anatoly 0 siblings, 0 replies; 3+ messages in thread From: Burakov, Anatoly @ 2023-05-19 16:23 UTC (permalink / raw) To: Vipin P R; +Cc: dev, stable 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 ^ permalink raw reply [flat|nested] 3+ messages in thread
[parent not found: <1673615669-21011-3-git-send-email-vipinp@vmware.com>]
* Re: [PATCH 2/2] Memory Allocation: Alternative fix for ignore_msk during find_next_n() in fb_array library [not found] ` <1673615669-21011-3-git-send-email-vipinp@vmware.com> @ 2023-05-19 16:45 ` Burakov, Anatoly 2023-05-22 5:12 ` Vipin P R 0 siblings, 1 reply; 3+ messages in thread From: Burakov, Anatoly @ 2023-05-19 16:45 UTC (permalink / raw) To: Vipin P R; +Cc: dev, stable 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 ^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH 2/2] Memory Allocation: Alternative fix for ignore_msk during find_next_n() in fb_array library 2023-05-19 16:45 ` [PATCH 2/2] Memory Allocation: Alternative fix for " Burakov, Anatoly @ 2023-05-22 5:12 ` Vipin P R 0 siblings, 0 replies; 3+ messages in thread From: Vipin P R @ 2023-05-22 5:12 UTC (permalink / raw) To: Burakov, Anatoly; +Cc: dev, stable [-- 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 --] ^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2023-05-22 8:14 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
[not found] <1673615669-21011-1-git-send-email-vipinp@vmware.com>
[not found] ` <1673615669-21011-2-git-send-email-vipinp@vmware.com>
2023-05-19 16:23 ` [PATCH 1/2] Memory Allocation: Fixes ignore_msk during find_next_n() in fb_array library Burakov, Anatoly
[not found] ` <1673615669-21011-3-git-send-email-vipinp@vmware.com>
2023-05-19 16:45 ` [PATCH 2/2] Memory Allocation: Alternative fix for " Burakov, Anatoly
2023-05-22 5:12 ` Vipin P R
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).