Re: mm: reorganize SLAB freelist randomization

[Thomas Garnier <thgarnie@google.com>]

No, the for loop is correct. Fisher-Yates shuffles algorithm is as follow:

-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 downto 1 do
     j random integer such that 0 <= j <= i
     exchange a[j] and a[i]

https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

On Mon, Jun 6, 2016 at 12:52 PM, Dan Carpenter <dan.carpenter@oracle.com> wrote:
> Hello Thomas Garnier,
>
> The patch aded650eb82e: "mm: reorganize SLAB freelist randomization"
> from Jun 5, 2016, leads to the following static checker warning:
>
>         mm/slab_common.c:1160 freelist_randomize()
>         warn: why is zero skipped 'i'
>
> mm/slab_common.c
>   1146  /* Randomize a generic freelist */
>   1147  static void freelist_randomize(struct rnd_state *state, unsigned int *list,
>   1148                          size_t count)
>   1149  {
>   1150          size_t i;
>   1151          unsigned int rand;
>   1152
>   1153          for (i = 0; i < count; i++)
>   1154                  list[i] = i;
>   1155
>   1156          /* Fisher-Yates shuffle */
>   1157          for (i = count - 1; i > 0; i--) {
>
> This looks like it should be i >= 0.
>
>   1158                  rand = prandom_u32_state(state);
>   1159                  rand %= (i + 1);
>   1160                  swap(list[i], list[rand]);
>   1161          }
>   1162  }
>
> regards,
> dan carpenter

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>