re: mm: reorganize SLAB freelist randomization

re: mm: reorganize SLAB freelist randomization

[Dan Carpenter]

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>

Re: mm: reorganize SLAB freelist randomization

[Thomas Garnier]

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>

Re: mm: reorganize SLAB freelist randomization

[Dan Carpenter]

On Mon, Jun 06, 2016 at 01:01:45PM -0700, Thomas Garnier wrote:
> 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 na??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

Thanks for looking at this.  :)

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>

Re: mm: reorganize SLAB freelist randomization

[Thomas Garnier]

Thanks a lot for running static checkers on the code.

On Mon, Jun 6, 2016 at 1:11 PM, Dan Carpenter <dan.carpenter@oracle.com> wrote:
> On Mon, Jun 06, 2016 at 01:01:45PM -0700, Thomas Garnier wrote:
>> 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
>
> Thanks for looking at this.  :)
>
> 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>