[FFmpeg-devel] [PATCH] random_seed: Limit the time taken by get_generic_seed

[FFmpeg-devel] [PATCH] random_seed: Limit the time taken by get_generic_seed

[Martin Storsjö]

On a Zen 5, on Ubuntu 24.04 (with CLOCKS_PER_SEC 1000000), the
value of clock() in this loop increments by 0 most of the time,
and when it does increment, it usually increments by 1 compared
to the previous round.

Due to the "last_t + 2*last_td + (CLOCKS_PER_SEC > 1000) >= t"
expression, we only manage to take one step forward in this loop
(incrementing i) if clock() increments by 2, while it incremented
by 0 in the previous iteration (last_td).

As we do mutate the buffer state even on loop iterations where we
don't increment i, limit the number of times we consecutively can
do this.

This is similar to the change done in
c4152fc42e480c41efb7f761b1bbe5f0bc43d5bc, to speed it up on
systems with very small CLOCKS_PER_SEC. However in this case,
CLOCKS_PER_SEC is still very large, but the machine is fast enough
to hit every clock increment repeatedly.

This makes sure that fate-random-seed actually terminates within a
reasonable time on such a system (where it previously could hang,
running for many minutes).
---
 libavutil/random_seed.c | 5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)

diff --git a/libavutil/random_seed.c b/libavutil/random_seed.c
index 8a4e4f1fc0..8f969060a0 100644
--- a/libavutil/random_seed.c
+++ b/libavutil/random_seed.c
@@ -83,6 +83,7 @@ static uint32_t get_generic_seed(void)
     static uint32_t buffer[512] = { 0 };
     unsigned char digest[20];
     uint64_t last_i = i;
+    int cur_iters = 0;
 
     av_assert0(sizeof(tmp) >= av_sha_size);
 
@@ -98,11 +99,13 @@ static uint32_t get_generic_seed(void)
 
     for (;;) {
         clock_t t = clock();
-        if (last_t + 2*last_td + (CLOCKS_PER_SEC > 1000) >= t) {
+        if (last_t + 2*last_td + (CLOCKS_PER_SEC > 1000) >= t && cur_iters < 128) {
             last_td = t - last_t;
             buffer[i & 511] = 1664525*buffer[i & 511] + 1013904223 + (last_td % 3294638521U);
+            cur_iters++;
         } else {
             last_td = t - last_t;
+            cur_iters = 0;
             buffer[++i & 511] += last_td % 3294638521U;
             if ((t - init_t) >= CLOCKS_PER_SEC>>5)
                 if (last_i && i - last_i > 4 || i - last_i > 64 || TEST && i - last_i > 8)
-- 
2.43.0

_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel

To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".

Re: [FFmpeg-devel] [PATCH] random_seed: Limit the time taken by get_generic_seed

[Michael Niedermayer]

[-- Attachment #1.1: Type: text/plain, Size: 2968 bytes --]

Hi Martin

On Wed, Jan 29, 2025 at 11:53:53AM +0200, Martin Storsjö wrote:
> On a Zen 5, on Ubuntu 24.04 (with CLOCKS_PER_SEC 1000000), the
> value of clock() in this loop increments by 0 most of the time,
> and when it does increment, it usually increments by 1 compared
> to the previous round.
> 
> Due to the "last_t + 2*last_td + (CLOCKS_PER_SEC > 1000) >= t"
> expression, we only manage to take one step forward in this loop
> (incrementing i) if clock() increments by 2, while it incremented
> by 0 in the previous iteration (last_td).
> 
> As we do mutate the buffer state even on loop iterations where we
> don't increment i, limit the number of times we consecutively can
> do this.
> 
> This is similar to the change done in
> c4152fc42e480c41efb7f761b1bbe5f0bc43d5bc, to speed it up on
> systems with very small CLOCKS_PER_SEC. However in this case,
> CLOCKS_PER_SEC is still very large, but the machine is fast enough
> to hit every clock increment repeatedly.
> 
> This makes sure that fate-random-seed actually terminates within a
> reasonable time on such a system (where it previously could hang,
> running for many minutes).
> ---
>  libavutil/random_seed.c | 5 ++++-
>  1 file changed, 4 insertions(+), 1 deletion(-)
> 
> diff --git a/libavutil/random_seed.c b/libavutil/random_seed.c
> index 8a4e4f1fc0..8f969060a0 100644
> --- a/libavutil/random_seed.c
> +++ b/libavutil/random_seed.c
> @@ -83,6 +83,7 @@ static uint32_t get_generic_seed(void)
>      static uint32_t buffer[512] = { 0 };
>      unsigned char digest[20];
>      uint64_t last_i = i;
> +    int cur_iters = 0;
>  
>      av_assert0(sizeof(tmp) >= av_sha_size);
>  
> @@ -98,11 +99,13 @@ static uint32_t get_generic_seed(void)
>  
>      for (;;) {
>          clock_t t = clock();
> -        if (last_t + 2*last_td + (CLOCKS_PER_SEC > 1000) >= t) {
> +        if (last_t + 2*last_td + (CLOCKS_PER_SEC > 1000) >= t && cur_iters < 128) {
>              last_td = t - last_t;
>              buffer[i & 511] = 1664525*buffer[i & 511] + 1013904223 + (last_td % 3294638521U);
> +            cur_iters++;
>          } else {
>              last_td = t - last_t;
> +            cur_iters = 0;

Iam concerned this could negatively impact entropy
The "else" should be run when a interrupt/task switch occured.
If that doesnt occur in 128 iterations that doesnt gurantee the entropy
has increased.

If there are only 0 and 1, ideally we should look at the distribution and
go to the else when the pattern differs from the past / has some signs of
randomness

thx

[...]
-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

Awnsering whenever a program halts or runs forever is
On a turing machine, in general impossible (turings halting problem).
On any real computer, always possible as a real computer has a finite number
of states N, and will either halt in less than N cycles or never halt.

[-- Attachment #1.2: signature.asc --]
[-- Type: application/pgp-signature, Size: 195 bytes --]

[-- Attachment #2: Type: text/plain, Size: 251 bytes --]

_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel

To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".

Re: [FFmpeg-devel] [PATCH] random_seed: Limit the time taken by get_generic_seed

[Martin Storsjö]

On Fri, 31 Jan 2025, Michael Niedermayer wrote:

>> diff --git a/libavutil/random_seed.c b/libavutil/random_seed.c
>> index 8a4e4f1fc0..8f969060a0 100644
>> --- a/libavutil/random_seed.c
>> +++ b/libavutil/random_seed.c
>> @@ -83,6 +83,7 @@ static uint32_t get_generic_seed(void)
>>      static uint32_t buffer[512] = { 0 };
>>      unsigned char digest[20];
>>      uint64_t last_i = i;
>> +    int cur_iters = 0;
>>
>>      av_assert0(sizeof(tmp) >= av_sha_size);
>>
>> @@ -98,11 +99,13 @@ static uint32_t get_generic_seed(void)
>>
>>      for (;;) {
>>          clock_t t = clock();
>> -        if (last_t + 2*last_td + (CLOCKS_PER_SEC > 1000) >= t) {
>> +        if (last_t + 2*last_td + (CLOCKS_PER_SEC > 1000) >= t && cur_iters < 128) {
>>              last_td = t - last_t;
>>              buffer[i & 511] = 1664525*buffer[i & 511] + 1013904223 + (last_td % 3294638521U);
>> +            cur_iters++;
>>          } else {
>>              last_td = t - last_t;
>> +            cur_iters = 0;
>
> Iam concerned this could negatively impact entropy
> The "else" should be run when a interrupt/task switch occured.
> If that doesnt occur in 128 iterations that doesnt gurantee the entropy
> has increased.
>
> If there are only 0 and 1, ideally we should look at the distribution and
> go to the else when the pattern differs from the past / has some signs of
> randomness

Ok, I've somewhat tried to implement this, please take a look.

// Martin

_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel

To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".