linux-kernel - Re: [PATCH RFC v1] random: implement getrandom() in vDSO

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <87a68r4qpy.fsf@oldenburg.str.redhat.com>
Date:   Fri, 29 Jul 2022 22:19:05 +0200
From:   Florian Weimer <fweimer@...hat.com>
To:     "Jason A. Donenfeld" <Jason@...c4.com>
Cc:     linux-kernel@...r.kernel.org, linux-crypto@...r.kernel.org,
        x86@...nel.org, Nadia Heninger <nadiah@...ucsd.edu>,
        Thomas Ristenpart <ristenpart@...nell.edu>,
        Theodore Ts'o <tytso@....edu>,
        Vincenzo Frascino <vincenzo.frascino@....com>,
        Adhemerval Zanella Netto <adhemerval.zanella@...aro.org>
Subject: Re: [PATCH RFC v1] random: implement getrandom() in vDSO

* Jason A. Donenfeld:

> diff --git a/lib/vdso/getrandom.c b/lib/vdso/getrandom.c
> new file mode 100644
> index 000000000000..3ffc900f31ff
> --- /dev/null
> +++ b/lib/vdso/getrandom.c

> +static struct getrandom_state *find_free_bucket(struct getrandom_state *buckets)
> +{
> +	unsigned int start = 0, i;
> +
> +	if (getcpu(&start, NULL, NULL) == 0)
> +		start %= NUM_BUCKETS;

getcpu is not available everywhere.  Userspace/libc should probably
provide a CPU number hint as an additional argument during the vDSO
call.  We can load that easily enough from rseq.  That's going to be
faster on x86, too (the LSL instruction is quite slow).  The only
advantage of using getcpu like this is that it's compatible with a libc
that isn't rseq-enabled.

> +	for (i = start;;) {
> +		struct getrandom_state *state = &buckets[i];
> +
> +		if (cmpxchg(&state->in_use, false, true) == false)
> +			return state;
> +
> +		i = i == NUM_BUCKETS - 1 ? 0 : i + 1;
> +		if (i == start)
> +			break;
> +	}

Surely this scales very badly once the number of buckets is smaller than
the system processor count?

> +static ssize_t __always_inline
> +__cvdso_getrandom(void **state, void *buffer, size_t len, unsigned long flags)

> +more_batch:
> +	batch_len = min_t(size_t, sizeof(s->batch) - s->pos, len);
> +	if (batch_len) {
> +		memcpy_and_zero(buffer, s->batch, batch_len);
> +		s->pos += batch_len;
> +		buffer += batch_len;
> +		len -= batch_len;
> +		if (!len) {
> +			WRITE_ONCE(s->in_use, false);
> +			return ret;
> +		}
> +	}

I expect the main performance benefit comes from not doing any ChaCha20
work except on batch boundaries, not the vDSO acceleration as such.
Maybe that's something that should be tried first within the system call
implementation.  (Even for getrandom with a small buffer, it's not the
system call overhead that dominates, but something related to ChaCha20.)

Thanks,
Florian