Received-SPF: pass (google.com: domain of linux-crypto-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
From:   Florian Weimer <fweimer@redhat.com>
To:     "Jason A. Donenfeld" <Jason@zx2c4.com>
Cc:     linux-kernel@vger.kernel.org, linux-crypto@vger.kernel.org,
        x86@kernel.org, Nadia Heninger <nadiah@cs.ucsd.edu>,
        Thomas Ristenpart <ristenpart@cornell.edu>,
        Theodore Ts'o <tytso@mit.edu>,
        Vincenzo Frascino <vincenzo.frascino@arm.com>,
        Adhemerval Zanella Netto <adhemerval.zanella@linaro.org>
Subject: Re: [PATCH RFC v1] random: implement getrandom() in vDSO
References: <20220729145525.1729066-1-Jason@zx2c4.com>
Date:   Fri, 29 Jul 2022 22:19:05 +0200
In-Reply-To: <20220729145525.1729066-1-Jason@zx2c4.com> (Jason A. Donenfeld's
        message of "Fri, 29 Jul 2022 16:55:25 +0200")
Message-ID: <87a68r4qpy.fsf@oldenburg.str.redhat.com>
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.2 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain
Precedence: bulk

* 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