[PATCH 0/2] *** Memory Allocation: Fixes ms_idx jump in fb_array library ***

[PATCH 0/2] *** Memory Allocation: Fixes ms_idx jump in fb_array library ***

[Vipin P R]

*** 
The problem :
In the legacy mem mode, when the fb_array is being populated, if there are holes in between, the ms_idx could go backward and there will be an overlap of the region starting from the ms_idx returned later. i.e. it's being mapped to two different physical regions in PA space to a contiguous region in VA space. this would result in the allocator assuming that the memory is contiguous even though there is a hole in between. In legacy mem, allocator assumes that PA contiguous are VA contiguous as well.

Reason for the ms_idx going back :
In the lookahead logic of find_next_n(), if we fail to find contiguous "need" bits, we ignore all masks till the lookahead when we run out of options i.e. the LSB bit is not set or more accurately there are no "need" bits starting from LSB, therefore breaking contiguity.

The optimisation is to avoid repeating this operation and therefore we start from msk_idx = lookahead_idx in the next iter.. However, in the outer loop, we increment msk_idx further, resulting in msk_idx = lookahead_idx + 1, thereby inducing a jump. This problem becomes apparent when we have partially filled bits in the lookahead_msk. Further iterations might find the necessary contiguity from such a lookahead, potentially resulting in the returned ms_idx value to be lower for subsequent iterations.

The assumption was that ms_idx from rte_fbarray_find_next_n_free() is supposed to be incremental in nature, provided that the value of n is always constant.

For a sample input of {1, 1070, 1, 2, 1, 2, 4, 12, 2, 2, 1, 2, 1},

Without the patch :

6358 EAL: ms_idx:1097
6359 EAL: ms_idx:1098
6360 EAL: ms_idx:1099
6361 EAL: ms_idx:1155
6362 EAL: ms_idx:1156
6363 EAL: ms_idx:1158
6364 EAL: ms_idx:1159
6365 EAL: ms_idx:1154
6366 EAL: ms_idx:1161
6367 EAL: ms_idx:1162
6368 EAL: ms_idx:1164

With the patch :

12730 EAL: ms_idx:1096
12731 EAL: ms_idx:1097
12732 EAL: ms_idx:1098
12733 EAL: ms_idx:1099
12734 EAL: ms_idx:1101
12735 EAL: ms_idx:1102
12736 EAL: ms_idx:1104
12737 EAL: ms_idx:1105
12738 EAL: ms_idx:1107
12739 EAL: ms_idx:1109
12740 EAL: ms_idx:1110
12741 EAL: ms_idx:1112

***

Vipin P R (2):
  Memory Allocation: Fixes ms_idx jump (lookahead) during find_next_n()
    in fb_array library
  Memory Allocation: Fixes ms_idx jump (lookbehind) during find_prev_n()
    in fb_array library

 .mailmap                            | 1 +
 lib/eal/common/eal_common_fbarray.c | 4 ++--
 2 files changed, 3 insertions(+), 2 deletions(-)

-- 
2.7.4

[PATCH 1/2] Memory Allocation: Fixes ms_idx jump (lookahead) during find_next_n() in fb_array library

[Vipin P R]

In the legacy mem mode, when the fb_array is being populated, if there are holes in between, the ms_idx could go backward and there will be an overlap of the region starting from the ms_idx returned later. i.e. it's being mapped to two different physical regions in PA space to a contiguous region in VA space. this would result in the allocator assuming that the memory is contiguous even though there is a hole in between. In legacy mem, allocator assumes that PA contiguous are VA contiguous as well.

Cc: stable@dpdk.org

Signed-off-by: Vipin P R <vipinp@vmware.com>
Acked-by: Kumara Parameshwaran <kparameshwar@vmware.com>
---
 .mailmap                            | 1 +
 lib/eal/common/eal_common_fbarray.c | 2 +-
 2 files changed, 2 insertions(+), 1 deletion(-)

diff --git a/.mailmap b/.mailmap
index 75884b6..3707bf5 100644
--- a/.mailmap
+++ b/.mailmap
@@ -1391,6 +1391,7 @@ Vincent Guo <guopengfei160@163.com>
 Vincent Jardin <vincent.jardin@6wind.com>
 Vincent Li <vincent.mc.li@gmail.com>
 Vincent S. Cojot <vcojot@redhat.com>
+Vipin P R <vipinp@vmware.com> <vipinpadmamramesh@gmail.com>
 Vipin Varghese <vipin.varghese@amd.com> <vipin.varghese@intel.com>
 Vipul Ashri <vipul.ashri@oracle.com>
 Vishal Kulkarni <vishal@chelsio.com>
diff --git a/lib/eal/common/eal_common_fbarray.c b/lib/eal/common/eal_common_fbarray.c
index f11f879..551bd87 100644
--- a/lib/eal/common/eal_common_fbarray.c
+++ b/lib/eal/common/eal_common_fbarray.c
@@ -236,7 +236,7 @@ find_next_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n,
 				 * as well, so skip that on next iteration.
 				 */
 				ignore_msk = ~((1ULL << need) - 1);
-				msk_idx = lookahead_idx;
+				msk_idx = lookahead_idx - 1;
 				break;
 			}
 
-- 
2.7.4

[PATCH 2/2] Memory Allocation: Fixes ms_idx jump (lookbehind) during find_prev_n() in fb_array library

[Vipin P R]

Cc: stable@dpdk.org

Signed-off-by: Vipin P R <vipinp@vmware.com>
Acked-by: Kumara Parameshwaran <kparameshwar@vmware.com>
---
 lib/eal/common/eal_common_fbarray.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/lib/eal/common/eal_common_fbarray.c b/lib/eal/common/eal_common_fbarray.c
index 551bd87..90240e8 100644
--- a/lib/eal/common/eal_common_fbarray.c
+++ b/lib/eal/common/eal_common_fbarray.c
@@ -511,7 +511,7 @@ find_prev_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n,
 				 * as well, so skip that on next iteration.
 				 */
 				ignore_msk = UINT64_MAX << need;
-				msk_idx = lookbehind_idx;
+				msk_idx = lookbehind_idx + 1;
 				break;
 			}
 
-- 
2.7.4

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

[Burakov, Anatoly]

Hi Vipin,

Fix looks good, took a while to understand what's going on, but it's a 
great find!

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

Couple of comments below:

On 1/13/2023 1:08 PM, Vipin P R wrote:
> In the legacy mem mode, when the fb_array is being populated, if there are holes in between, the ms_idx could go backward and there will be an overlap of the region starting from the ms_idx returned later. i.e. it's being mapped to two different physical regions in PA space to a contiguous region in VA space. this would result in the allocator assuming that the memory is contiguous even though there is a hole in between. In legacy mem, allocator assumes that PA contiguous are VA contiguous as well.

Technically, while this bug is indeed triggered in legacy mode, it does 
not in any way depend on it, so I would suggest avoid mentioning it 
explicitly.

Suggested commit message rewording:

fbarray: fix incorrect lookahead behavior

Currently, whenever last bit of current index mask is set (meaning, 
there is potentially a run starting at the end of the mask), lookahead 
loop is entered. In that loop, if the first bit of lookahead index is 
not set, the lookahead is stopped, and the current lookahead mask index 
is assigned to current index mask. However, because at that point we are 
inside a for-loop that increments current index mask after each 
iteration, this results in additional mask index increment.

Fix it to leave current index mask at `lookahead - 1`.

Fixes: c44d09811b40 ("eal: add shared indexed file-backed array")
Cc: anatoly.burakov@intel.com

> 
> Cc: stable@dpdk.org
> 
> Signed-off-by: Vipin P R <vipinp@vmware.com>
> Acked-by: Kumara Parameshwaran <kparameshwar@vmware.com>
> ---
>   .mailmap                            | 1 +
>   lib/eal/common/eal_common_fbarray.c | 2 +-
>   2 files changed, 2 insertions(+), 1 deletion(-)
> 
> diff --git a/.mailmap b/.mailmap
> index 75884b6..3707bf5 100644
> --- a/.mailmap
> +++ b/.mailmap
> @@ -1391,6 +1391,7 @@ Vincent Guo <guopengfei160@163.com>
>   Vincent Jardin <vincent.jardin@6wind.com>
>   Vincent Li <vincent.mc.li@gmail.com>
>   Vincent S. Cojot <vcojot@redhat.com>
> +Vipin P R <vipinp@vmware.com> <vipinpadmamramesh@gmail.com>
>   Vipin Varghese <vipin.varghese@amd.com> <vipin.varghese@intel.com>
>   Vipul Ashri <vipul.ashri@oracle.com>
>   Vishal Kulkarni <vishal@chelsio.com>
> diff --git a/lib/eal/common/eal_common_fbarray.c b/lib/eal/common/eal_common_fbarray.c
> index f11f879..551bd87 100644
> --- a/lib/eal/common/eal_common_fbarray.c
> +++ b/lib/eal/common/eal_common_fbarray.c
> @@ -236,7 +236,7 @@ find_next_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n,
>   				 * as well, so skip that on next iteration.
>   				 */
>   				ignore_msk = ~((1ULL << need) - 1);
> -				msk_idx = lookahead_idx;
> +				msk_idx = lookahead_idx - 1;
>   				break;
>   			}
>   

-- 
Thanks,
Anatoly

Re: [PATCH 2/2] Memory Allocation: Fixes ms_idx jump (lookbehind) during find_prev_n() in fb_array library

[Burakov, Anatoly]

Hi Vipin,

This commit should include a more detailed commit message, akin to one I 
suggested for the first patch.

For the patch itself:

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


On 1/13/2023 1:08 PM, Vipin P R wrote:
> Cc: stable@dpdk.org
> 
> Signed-off-by: Vipin P R <vipinp@vmware.com>
> Acked-by: Kumara Parameshwaran <kparameshwar@vmware.com>
> ---
>   lib/eal/common/eal_common_fbarray.c | 2 +-
>   1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/lib/eal/common/eal_common_fbarray.c b/lib/eal/common/eal_common_fbarray.c
> index 551bd87..90240e8 100644
> --- a/lib/eal/common/eal_common_fbarray.c
> +++ b/lib/eal/common/eal_common_fbarray.c
> @@ -511,7 +511,7 @@ find_prev_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n,
>   				 * as well, so skip that on next iteration.
>   				 */
>   				ignore_msk = UINT64_MAX << need;
> -				msk_idx = lookbehind_idx;
> +				msk_idx = lookbehind_idx + 1;
>   				break;
>   			}
>   

The unit test code you suggested does not cover this case. I've reduced 
this bug to a minimal test case:

1. Allocate fbarray with 256 entries
2. Set idx 63 as used
3. Call rte_fbarray_find_prev_n_free() starting with index 64 and length 
of 2

Returned value should be 61, but without the fix it returns -1.

-- 
Thanks,
Anatoly