On Fri, Jan 28, 2022 at 01:18:45PM +0100, Anton Khirnov wrote:
> Quoting Michael Niedermayer (2022-01-25 11:21:08)
> > This decreases the quality of the seeds during the test, it does not affect
> > the seeds outside the test.
> > There is a small chance that this causes test failures, if that happens
> > the threshold needs adjusting
> >
> > Testing on an idle x86_64 system shows that this passes even with the test
> > strength
> > increased to 32768 from 256 with 0 retries
> > So test failures are not anticipated
> > Lowering the threshold from 3 to 2 causes failure at test strength of 32768
> >
> > Signed-off-by: Michael Niedermayer
> > ---
> > libavutil/random_seed.c | 2 +-
> > 1 file changed, 1 insertion(+), 1 deletion(-)
> >
> > diff --git a/libavutil/random_seed.c b/libavutil/random_seed.c
> > index 70dc509d2f..509b74936c 100644
> > --- a/libavutil/random_seed.c
> > +++ b/libavutil/random_seed.c
> > @@ -95,7 +95,7 @@ static uint32_t get_generic_seed(void)
> > last_td = t - last_t;
> > 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)
> > +if (last_i && i - last_i > 4 || i - last_i > 64 || TEST &&
> > i - last_i > 3)
>
> On my Ryzen 5950x, this brings the test runtime from > 60s to ~30s,
> which is a good improvement, but still quite a lot (the entire FATE run
> with -j32 and without the random-seed test is ~40s).
>
> How about something like this instead (takes about 8s on my machines, observed
> no test failures):
this works, though it may be better to estimate the collected entropy
and stop once enough is collected
i played around with the code a bit and got the test to pass with 32768 in 5min
down from i think 17min
and the unmodified 256 test from 8 sec to 3 sec
the 8 is with my 2 and your patch applied
but the resulting threshold in the code doesnt feel correct
also a completely different approuch would be to predict/compress the
timestamp deltas to estimate the entropy
i need to do something else now or i loose my sanity, maybe ill look at
it again in a few days, but feel free to continue working on the WIP below
if you like (if something makes no sense in it it likely doesnt)
thx
diff --git a/libavutil/random_seed.c b/libavutil/random_seed.c
index b1bbbd1b69..0255de7302 100644
--- a/libavutil/random_seed.c
+++ b/libavutil/random_seed.c
@@ -62,18 +62,21 @@ static int read_random(uint32_t *dst, const char *file)
#endif
}
+#define N_COUNTS 5
+
static uint32_t get_generic_seed(void)
{
uint64_t tmp[120/8];
struct AVSHA *sha = (void*)tmp;
clock_t last_t = 0;
clock_t last_td = 0;
-clock_t init_t = 0;
+clock_t last_td2 = 0;
static uint64_t i = 0;
static uint32_t buffer[512] = { 0 };
unsigned char digest[20];
uint64_t last_i = i;
-uint64_t cnt = 0;
+uint32_t last_td_count[N_COUNTS] = {0};
+int entropy = 0;
av_assert0(sizeof(tmp) >= av_sha_size);
@@ -89,21 +92,33 @@ static uint32_t get_generic_seed(void)
for (;;) {
clock_t t = clock();
-if (last_t + 2*last_td + (CLOCKS_PER_SEC > 1000) >= t &&
-!(TEST && cnt > (1 << 15))) {
-last_td = t - last_t;
-buffer[i & 511] = 1664525*buffer[i & 511] + 1013904223 + (last_td
% 3294638521U);
-cnt++;
+clock_t tmp = t - last_t;
+if (last_td == tmp || last_td2 == tmp) {
+buffer[i & 511] = 1664525*buffer[i & 511] + 1013904223 + (tmp %
3294638521U);
+if (last_td == tmp) {
+last_td_count[0] ++;
+} else {
+int add_entropy = INT_MAX;
+for (int j = N_COUNTS-1; j; j--) {
+add_entropy = FFMIN(add_entropy, abs(last_td_count[j] -
last_td_count[0]));
+last_td_count[j] = last_td_count[j-1];
+}
+last_td_count[0] = 0;
+if (last_td2 != last_td)
+entropy += av_log2(add_entropy);
+last_td2 = last_td;
+}
} else {
-last_td = t - last_t;
-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 > 3)
-break;
+if (last_td2 != last_td)
+entropy += av_log2(FFMIN(abs(last_td - tmp), abs(last_td2 -
tmp)) + 1) + av_log2(last_td_count[0]);
+buffer[++i & 511] += tmp % 3294638521U;
+last_td2 = last_td;
+last_td_count[0] = 0;
}
+if (last_i && entropy > 32 || entropy > 128 || TEST && entropy > 8)
+break;
+last_td = tmp;
last_t = t;
-if (!init_t)
-init_t = t;
}
if(TEST) {
[...]
--
Michael Gn
