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

[Vipin P R <vipinp@vmware.com>]

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