[RFC PATCH v1 29/50] fs/ocfs2/journal: Use prandom_u32() and not /dev/random for timeout

[RFC PATCH v1 29/50] fs/ocfs2/journal: Use prandom_u32() and not /dev/random for timeout

[George Spelvin]

get_random_bytes() is expensive crypto-quality random numbers.
If we're just doing random backoff, prandom_u32() is plenty.

(Not to mention fetching 8 bytes of seed material only to
reduce it modulo 5000 is a huge waste.)

Also, convert timeouts to jiffies at compile time; convert
milliseconds to jiffies before picking a random number in the
range to take advantage of compile-time constant folding.

Signed-off-by: George Spelvin <lkml@sdf.org>
Cc: Mark Fasheh <mark@fasheh.com>
Cc: Joel Becker <jlbec@evilplan.org>
Cc: Joseph Qi <joseph.qi@linux.alibaba.com>
Cc: ocfs2-devel@oss.oracle.com
---
 fs/ocfs2/journal.c | 7 ++-----
 1 file changed, 2 insertions(+), 5 deletions(-)

diff --git a/fs/ocfs2/journal.c b/fs/ocfs2/journal.c
index 68ba354cf3610..939a12e57fa8b 100644
--- a/fs/ocfs2/journal.c
+++ b/fs/ocfs2/journal.c
@@ -1884,11 +1884,8 @@ int ocfs2_mark_dead_nodes(struct ocfs2_super *osb)
  */
 static inline unsigned long ocfs2_orphan_scan_timeout(void)
 {
-	unsigned long time;
-
-	get_random_bytes(&time, sizeof(time));
-	time = ORPHAN_SCAN_SCHEDULE_TIMEOUT + (time % 5000);
-	return msecs_to_jiffies(time);
+	return msecs_to_jiffies(ORPHAN_SCAN_SCHEDULE_TIMEOUT) +
+		prandom_u32_max(5 * HZ);
 }
 
 /*
-- 
2.26.0

[Ocfs2-devel] [RFC PATCH v1 29/50] fs/ocfs2/journal: Use prandom_u32() and not /dev/random for timeout

[George Spelvin]

get_random_bytes() is expensive crypto-quality random numbers.
If we're just doing random backoff, prandom_u32() is plenty.

(Not to mention fetching 8 bytes of seed material only to
reduce it modulo 5000 is a huge waste.)

Also, convert timeouts to jiffies at compile time; convert
milliseconds to jiffies before picking a random number in the
range to take advantage of compile-time constant folding.

Signed-off-by: George Spelvin <lkml@sdf.org>
Cc: Mark Fasheh <mark@fasheh.com>
Cc: Joel Becker <jlbec@evilplan.org>
Cc: Joseph Qi <joseph.qi@linux.alibaba.com>
Cc: ocfs2-devel at oss.oracle.com
---
 fs/ocfs2/journal.c | 7 ++-----
 1 file changed, 2 insertions(+), 5 deletions(-)

diff --git a/fs/ocfs2/journal.c b/fs/ocfs2/journal.c
index 68ba354cf3610..939a12e57fa8b 100644
--- a/fs/ocfs2/journal.c
+++ b/fs/ocfs2/journal.c
@@ -1884,11 +1884,8 @@ int ocfs2_mark_dead_nodes(struct ocfs2_super *osb)
  */
 static inline unsigned long ocfs2_orphan_scan_timeout(void)
 {
-	unsigned long time;
-
-	get_random_bytes(&time, sizeof(time));
-	time = ORPHAN_SCAN_SCHEDULE_TIMEOUT + (time % 5000);
-	return msecs_to_jiffies(time);
+	return msecs_to_jiffies(ORPHAN_SCAN_SCHEDULE_TIMEOUT) +
+		prandom_u32_max(5 * HZ);
 }
 
 /*
-- 
2.26.0

Re: [RFC PATCH v1 29/50] fs/ocfs2/journal: Use prandom_u32() and not /dev/random for timeout

[Joseph Qi]

Sorry for the late reply since I might miss this mail.

On 2019/3/21 11:07, George Spelvin wrote:
> get_random_bytes() is expensive crypto-quality random numbers.
> If we're just doing random backoff, prandom_u32() is plenty.
> 
> (Not to mention fetching 8 bytes of seed material only to
> reduce it modulo 5000 is a huge waste.)
> 
> Also, convert timeouts to jiffies at compile time; convert
> milliseconds to jiffies before picking a random number in the
> range to take advantage of compile-time constant folding.
> 
> Signed-off-by: George Spelvin <lkml@sdf.org>
> Cc: Mark Fasheh <mark@fasheh.com>
> Cc: Joel Becker <jlbec@evilplan.org>
> Cc: Joseph Qi <joseph.qi@linux.alibaba.com>
> Cc: ocfs2-devel@oss.oracle.com
> ---
>  fs/ocfs2/journal.c | 7 ++-----
>  1 file changed, 2 insertions(+), 5 deletions(-)
> 
> diff --git a/fs/ocfs2/journal.c b/fs/ocfs2/journal.c
> index 68ba354cf3610..939a12e57fa8b 100644
> --- a/fs/ocfs2/journal.c
> +++ b/fs/ocfs2/journal.c
> @@ -1884,11 +1884,8 @@ int ocfs2_mark_dead_nodes(struct ocfs2_super *osb)
>   */
>  static inline unsigned long ocfs2_orphan_scan_timeout(void)
>  {
> -	unsigned long time;
> -
> -	get_random_bytes(&time, sizeof(time));
> -	time = ORPHAN_SCAN_SCHEDULE_TIMEOUT + (time % 5000);
> -	return msecs_to_jiffies(time);
> +	return msecs_to_jiffies(ORPHAN_SCAN_SCHEDULE_TIMEOUT) +
> +		prandom_u32_max(5 * HZ);

Seems better include the prandom_u32_max() into msecs_to_jiffies()?

Thanks,
Joseph
>  }
>  
>  /*
> 

[Ocfs2-devel] [RFC PATCH v1 29/50] fs/ocfs2/journal: Use prandom_u32() and not /dev/random for timeout

[Joseph Qi]

Sorry for the late reply since I might miss this mail.

On 2019/3/21 11:07, George Spelvin wrote:
> get_random_bytes() is expensive crypto-quality random numbers.
> If we're just doing random backoff, prandom_u32() is plenty.
> 
> (Not to mention fetching 8 bytes of seed material only to
> reduce it modulo 5000 is a huge waste.)
> 
> Also, convert timeouts to jiffies at compile time; convert
> milliseconds to jiffies before picking a random number in the
> range to take advantage of compile-time constant folding.
> 
> Signed-off-by: George Spelvin <lkml@sdf.org>
> Cc: Mark Fasheh <mark@fasheh.com>
> Cc: Joel Becker <jlbec@evilplan.org>
> Cc: Joseph Qi <joseph.qi@linux.alibaba.com>
> Cc: ocfs2-devel at oss.oracle.com
> ---
>  fs/ocfs2/journal.c | 7 ++-----
>  1 file changed, 2 insertions(+), 5 deletions(-)
> 
> diff --git a/fs/ocfs2/journal.c b/fs/ocfs2/journal.c
> index 68ba354cf3610..939a12e57fa8b 100644
> --- a/fs/ocfs2/journal.c
> +++ b/fs/ocfs2/journal.c
> @@ -1884,11 +1884,8 @@ int ocfs2_mark_dead_nodes(struct ocfs2_super *osb)
>   */
>  static inline unsigned long ocfs2_orphan_scan_timeout(void)
>  {
> -	unsigned long time;
> -
> -	get_random_bytes(&time, sizeof(time));
> -	time = ORPHAN_SCAN_SCHEDULE_TIMEOUT + (time % 5000);
> -	return msecs_to_jiffies(time);
> +	return msecs_to_jiffies(ORPHAN_SCAN_SCHEDULE_TIMEOUT) +
> +		prandom_u32_max(5 * HZ);

Seems better include the prandom_u32_max() into msecs_to_jiffies()?

Thanks,
Joseph
>  }
>  
>  /*
> 

Re: [RFC PATCH v1 29/50] fs/ocfs2/journal: Use prandom_u32() and not /dev/random for timeout

[George Spelvin]

On Mon, Mar 30, 2020 at 08:09:33PM +0800, Joseph Qi wrote:
> Sorry for the late reply since I might miss this mail.

You're hardly late; I expect replies to dribble in for a week.

> On 2019/3/21 11:07, George Spelvin wrote:
>> diff --git a/fs/ocfs2/journal.c b/fs/ocfs2/journal.c
>> index 68ba354cf3610..939a12e57fa8b 100644
>> --- a/fs/ocfs2/journal.c
>> +++ b/fs/ocfs2/journal.c
>> @@ -1884,11 +1884,8 @@ int ocfs2_mark_dead_nodes(struct ocfs2_super *osb)
>>   */
>>  static inline unsigned long ocfs2_orphan_scan_timeout(void)
>>  {
>> -	unsigned long time;
>> -
>> -	get_random_bytes(&time, sizeof(time));
>> -	time = ORPHAN_SCAN_SCHEDULE_TIMEOUT + (time % 5000);
>> -	return msecs_to_jiffies(time);
>> +	return msecs_to_jiffies(ORPHAN_SCAN_SCHEDULE_TIMEOUT) +
>> +		prandom_u32_max(5 * HZ);
> 
> Seems better include the prandom_u32_max() into msecs_to_jiffies()?

What I'm trying to take advantage of here is constant propagation.

msecs_to_jiffies is zero cost (it's evaluated entirely at compile 
time) if its argument is a compile-time constant.  It's a function call
and a few instructions if its argument is variable.

msecs_to_jiffies(ORPHAN_SCAN_SCHEDULE_TIMEOUT + prandom_u32_max(5000))
would be forced to use the expensive version.

The compiler does't know, but *I* know, that msecs_to_jiffies() is a 
linear function, and prandom_u32_max() is a sort-of linear function.

(It's a linear function for a given PRNG starting state, so each 
individual call is linear, but multiple calls mess things up.)

Modulo a bit of rounding, we have:

msecs_to_jiffies(a + b) = msecs_to_jiffies(a) + msecs_to_jiffies(b)
msecs_to_jiffies(a) * b = msecs_to_jiffies(a * b)
prandom_u32_max(a) * b = prandom_u32_max(a * b)
prandom_u32_max(msecs_to_jiffies(a)) = msecs_to_jiffies(prandom_u32_max(a))

By doing the addition in jiffies rather than milliseconds, we get the 
cheap code.  It's not a huge big deal, but it's definitely smaller and 
faster.

Admittedly, I happen to be using HZ = 300, which requires a multiply to 
convert, and makes the resultant random numbers slightly non-uniform.  
The default HZ = 250 makes it just a divide by 4, which is pretty simple.

(When HZ = 300, you get 1..3 ms -> 1 jiffy, 4..6 ms -> 2 jiffies, and
7..10 ms -> 3 jiffies.  Multiples of 3 are 33% more likely to be chosen.)

It just seems silly and wasteful to pick a random number between 0 and 
4999 (plus 30000), only to convert it to a random number between 0 and 
1249 (plus 7500).

And if HZ = 2000 ever happens, the timeout won't be artificially limited
to integer milliseconds.

[Ocfs2-devel] [RFC PATCH v1 29/50] fs/ocfs2/journal: Use prandom_u32() and not /dev/random for timeout

[George Spelvin]

On Mon, Mar 30, 2020 at 08:09:33PM +0800, Joseph Qi wrote:
> Sorry for the late reply since I might miss this mail.

You're hardly late; I expect replies to dribble in for a week.

> On 2019/3/21 11:07, George Spelvin wrote:
>> diff --git a/fs/ocfs2/journal.c b/fs/ocfs2/journal.c
>> index 68ba354cf3610..939a12e57fa8b 100644
>> --- a/fs/ocfs2/journal.c
>> +++ b/fs/ocfs2/journal.c
>> @@ -1884,11 +1884,8 @@ int ocfs2_mark_dead_nodes(struct ocfs2_super *osb)
>>   */
>>  static inline unsigned long ocfs2_orphan_scan_timeout(void)
>>  {
>> -	unsigned long time;
>> -
>> -	get_random_bytes(&time, sizeof(time));
>> -	time = ORPHAN_SCAN_SCHEDULE_TIMEOUT + (time % 5000);
>> -	return msecs_to_jiffies(time);
>> +	return msecs_to_jiffies(ORPHAN_SCAN_SCHEDULE_TIMEOUT) +
>> +		prandom_u32_max(5 * HZ);
> 
> Seems better include the prandom_u32_max() into msecs_to_jiffies()?

What I'm trying to take advantage of here is constant propagation.

msecs_to_jiffies is zero cost (it's evaluated entirely at compile 
time) if its argument is a compile-time constant.  It's a function call
and a few instructions if its argument is variable.

msecs_to_jiffies(ORPHAN_SCAN_SCHEDULE_TIMEOUT + prandom_u32_max(5000))
would be forced to use the expensive version.

The compiler does't know, but *I* know, that msecs_to_jiffies() is a 
linear function, and prandom_u32_max() is a sort-of linear function.

(It's a linear function for a given PRNG starting state, so each 
individual call is linear, but multiple calls mess things up.)

Modulo a bit of rounding, we have:

msecs_to_jiffies(a + b) = msecs_to_jiffies(a) + msecs_to_jiffies(b)
msecs_to_jiffies(a) * b = msecs_to_jiffies(a * b)
prandom_u32_max(a) * b = prandom_u32_max(a * b)
prandom_u32_max(msecs_to_jiffies(a)) = msecs_to_jiffies(prandom_u32_max(a))

By doing the addition in jiffies rather than milliseconds, we get the 
cheap code.  It's not a huge big deal, but it's definitely smaller and 
faster.

Admittedly, I happen to be using HZ = 300, which requires a multiply to 
convert, and makes the resultant random numbers slightly non-uniform.  
The default HZ = 250 makes it just a divide by 4, which is pretty simple.

(When HZ = 300, you get 1..3 ms -> 1 jiffy, 4..6 ms -> 2 jiffies, and
7..10 ms -> 3 jiffies.  Multiples of 3 are 33% more likely to be chosen.)

It just seems silly and wasteful to pick a random number between 0 and 
4999 (plus 30000), only to convert it to a random number between 0 and 
1249 (plus 7500).

And if HZ = 2000 ever happens, the timeout won't be artificially limited
to integer milliseconds.

Re: [RFC PATCH v1 29/50] fs/ocfs2/journal: Use prandom_u32() and not /dev/random for timeout

[Joseph Qi]

On 2020/3/31 00:34, George Spelvin wrote:
> On Mon, Mar 30, 2020 at 08:09:33PM +0800, Joseph Qi wrote:
>> Sorry for the late reply since I might miss this mail.
> 
> You're hardly late; I expect replies to dribble in for a week.
> 
>> On 2019/3/21 11:07, George Spelvin wrote:
>>> diff --git a/fs/ocfs2/journal.c b/fs/ocfs2/journal.c
>>> index 68ba354cf3610..939a12e57fa8b 100644
>>> --- a/fs/ocfs2/journal.c
>>> +++ b/fs/ocfs2/journal.c
>>> @@ -1884,11 +1884,8 @@ int ocfs2_mark_dead_nodes(struct ocfs2_super *osb)
>>>   */
>>>  static inline unsigned long ocfs2_orphan_scan_timeout(void)
>>>  {
>>> -	unsigned long time;
>>> -
>>> -	get_random_bytes(&time, sizeof(time));
>>> -	time = ORPHAN_SCAN_SCHEDULE_TIMEOUT + (time % 5000);
>>> -	return msecs_to_jiffies(time);
>>> +	return msecs_to_jiffies(ORPHAN_SCAN_SCHEDULE_TIMEOUT) +
>>> +		prandom_u32_max(5 * HZ);
>>
>> Seems better include the prandom_u32_max() into msecs_to_jiffies()?
> 
> What I'm trying to take advantage of here is constant propagation.
> 
> msecs_to_jiffies is zero cost (it's evaluated entirely at compile 
> time) if its argument is a compile-time constant.  It's a function call
> and a few instructions if its argument is variable.
> 
> msecs_to_jiffies(ORPHAN_SCAN_SCHEDULE_TIMEOUT + prandom_u32_max(5000))
> would be forced to use the expensive version.
> 
> The compiler does't know, but *I* know, that msecs_to_jiffies() is a 
> linear function, and prandom_u32_max() is a sort-of linear function.
> 
> (It's a linear function for a given PRNG starting state, so each 
> individual call is linear, but multiple calls mess things up.)
> 
> Modulo a bit of rounding, we have:
> 
> msecs_to_jiffies(a + b) = msecs_to_jiffies(a) + msecs_to_jiffies(b)
> msecs_to_jiffies(a) * b = msecs_to_jiffies(a * b)
> prandom_u32_max(a) * b = prandom_u32_max(a * b)
> prandom_u32_max(msecs_to_jiffies(a)) = msecs_to_jiffies(prandom_u32_max(a))
> 
> By doing the addition in jiffies rather than milliseconds, we get the 
> cheap code.  It's not a huge big deal, but it's definitely smaller and 
> faster.
> 
> Admittedly, I happen to be using HZ = 300, which requires a multiply to 
> convert, and makes the resultant random numbers slightly non-uniform.  
> The default HZ = 250 makes it just a divide by 4, which is pretty simple.
> 
> (When HZ = 300, you get 1..3 ms -> 1 jiffy, 4..6 ms -> 2 jiffies, and
> 7..10 ms -> 3 jiffies.  Multiples of 3 are 33% more likely to be chosen.)
> 
> It just seems silly and wasteful to pick a random number between 0 and 
> 4999 (plus 30000), only to convert it to a random number between 0 and 
> 1249 (plus 7500).
> 
> And if HZ = 2000 ever happens, the timeout won't be artificially limited
> to integer milliseconds.
> 

Thanks for the detail explanation.
Acked-by: Joseph Qi <joseph.qi@linux.alibaba.com>

[Ocfs2-devel] [RFC PATCH v1 29/50] fs/ocfs2/journal: Use prandom_u32() and not /dev/random for timeout

[Joseph Qi]

On 2020/3/31 00:34, George Spelvin wrote:
> On Mon, Mar 30, 2020 at 08:09:33PM +0800, Joseph Qi wrote:
>> Sorry for the late reply since I might miss this mail.
> 
> You're hardly late; I expect replies to dribble in for a week.
> 
>> On 2019/3/21 11:07, George Spelvin wrote:
>>> diff --git a/fs/ocfs2/journal.c b/fs/ocfs2/journal.c
>>> index 68ba354cf3610..939a12e57fa8b 100644
>>> --- a/fs/ocfs2/journal.c
>>> +++ b/fs/ocfs2/journal.c
>>> @@ -1884,11 +1884,8 @@ int ocfs2_mark_dead_nodes(struct ocfs2_super *osb)
>>>   */
>>>  static inline unsigned long ocfs2_orphan_scan_timeout(void)
>>>  {
>>> -	unsigned long time;
>>> -
>>> -	get_random_bytes(&time, sizeof(time));
>>> -	time = ORPHAN_SCAN_SCHEDULE_TIMEOUT + (time % 5000);
>>> -	return msecs_to_jiffies(time);
>>> +	return msecs_to_jiffies(ORPHAN_SCAN_SCHEDULE_TIMEOUT) +
>>> +		prandom_u32_max(5 * HZ);
>>
>> Seems better include the prandom_u32_max() into msecs_to_jiffies()?
> 
> What I'm trying to take advantage of here is constant propagation.
> 
> msecs_to_jiffies is zero cost (it's evaluated entirely at compile 
> time) if its argument is a compile-time constant.  It's a function call
> and a few instructions if its argument is variable.
> 
> msecs_to_jiffies(ORPHAN_SCAN_SCHEDULE_TIMEOUT + prandom_u32_max(5000))
> would be forced to use the expensive version.
> 
> The compiler does't know, but *I* know, that msecs_to_jiffies() is a 
> linear function, and prandom_u32_max() is a sort-of linear function.
> 
> (It's a linear function for a given PRNG starting state, so each 
> individual call is linear, but multiple calls mess things up.)
> 
> Modulo a bit of rounding, we have:
> 
> msecs_to_jiffies(a + b) = msecs_to_jiffies(a) + msecs_to_jiffies(b)
> msecs_to_jiffies(a) * b = msecs_to_jiffies(a * b)
> prandom_u32_max(a) * b = prandom_u32_max(a * b)
> prandom_u32_max(msecs_to_jiffies(a)) = msecs_to_jiffies(prandom_u32_max(a))
> 
> By doing the addition in jiffies rather than milliseconds, we get the 
> cheap code.  It's not a huge big deal, but it's definitely smaller and 
> faster.
> 
> Admittedly, I happen to be using HZ = 300, which requires a multiply to 
> convert, and makes the resultant random numbers slightly non-uniform.  
> The default HZ = 250 makes it just a divide by 4, which is pretty simple.
> 
> (When HZ = 300, you get 1..3 ms -> 1 jiffy, 4..6 ms -> 2 jiffies, and
> 7..10 ms -> 3 jiffies.  Multiples of 3 are 33% more likely to be chosen.)
> 
> It just seems silly and wasteful to pick a random number between 0 and 
> 4999 (plus 30000), only to convert it to a random number between 0 and 
> 1249 (plus 7500).
> 
> And if HZ = 2000 ever happens, the timeout won't be artificially limited
> to integer milliseconds.
> 

Thanks for the detail explanation.
Acked-by: Joseph Qi <joseph.qi@linux.alibaba.com>