| Message ID | YaivhAV8LouB0zGV@light.dominikbrodowski.net |
|---|---|
| State | New |
| Headers | show |
| Series | [v3,resend] random: fix crash on multiple early calls to add_bootloader_randomness() | expand |
Hi Dominik, Thanks for the patch. One trivial nit and one question: On Thu, Dec 2, 2021 at 6:35 AM Dominik Brodowski <linux@dominikbrodowski.net> wrote: > + /* We cannot do much with the input pool until it is set up in > + * rand_initalize(); therefore just mix into the crng state. I think you meant "rand_initialize()" here (missing 'i'). > If the added entropy suffices to increase crng_init to 1, future calls > to add_bootloader_randomness() or add_hwgenerator_randomness() used to > progress to credit_entropy_bits(). However, if the input pool is not yet > properly set up, the cmpxchg call within that function can lead to an > infinite recursion. I see what this patch does with crng_global_init_time, and that seems probably sensible, but I didn't understand this part of the reasoning in the commit message; I might just be a bit slow here. Where's the recursion exactly? Or even an infinite loop? As far as I can tell, that portion of credit_entropy_bits() breaks down as: retry: entropy_count = orig = READ_ONCE(r->entropy_count); [ ... do some arithmetic on entropy_count ... ] if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig) goto retry; Why would this be infinite? Why wouldn't the cmpxchg eventually converge to a stable value? I don't see any call that modifies r->entropy_count or orig from inside that block. Is there some other super-spinny concurrent operation? Thanks, Jason
Hi Dominik, Thanks for your analysis. Some more questions: On Fri, Dec 3, 2021 at 8:59 AM Dominik Brodowski <linux@dominikbrodowski.net> wrote: > On subsequent calls to add_bootloader_randomness() and then to > add_hwgenerator_randomness(), crng_fast_load() will be skipped. Instead, > wait_event_interruptible() (which makes no sense for the init process) > and then credit_entropy_bits() will be called. If the entropy count for > that second seed is large enough, that proceeds to crng_reseed(). > However, crng_reseed() may depend on workqueues being available, which > is not the case early during boot. It sounds like *the* issue you've identified is that crng_reseed() calls into workqueue functions too early in init, right? The bug is about paths into crng_reseed() that might cause that? If so, then specifically, are you referring to crng_reseed()'s call to numa_crng_init()? In other words, the cause of the bug would be 6c1e851c4edc ("random: fix possible sleeping allocation from irq context")? If that's the case, then I wonder if the problem you're seeing goes away if you revert both 6c1e851c4edc ("random: fix possible sleeping allocation from irq context") and its primary predecessor, 8ef35c866f88 ("random: set up the NUMA crng instances after the CRNG is fully initialized"). These fix an actual bug, so I'm not suggesting we actually revert these in the tree, but for the purpose of testing, I'm wondering if this is actually the root cause of the bug you're seeing. Also, if you have a nice way of reproducing this, please do tell - I'd like to give it a spin if possible. Regards, Jason
On 12/3/21 16:39, Jason A. Donenfeld wrote: > Hi Dominik, > > Thanks for your analysis. Some more questions: > > On Fri, Dec 3, 2021 at 8:59 AM Dominik Brodowski > <linux@dominikbrodowski.net> wrote: >> On subsequent calls to add_bootloader_randomness() and then to >> add_hwgenerator_randomness(), crng_fast_load() will be skipped. Instead, >> wait_event_interruptible() (which makes no sense for the init process) >> and then credit_entropy_bits() will be called. If the entropy count for >> that second seed is large enough, that proceeds to crng_reseed(). >> However, crng_reseed() may depend on workqueues being available, which >> is not the case early during boot. > > It sounds like *the* issue you've identified is that crng_reseed() > calls into workqueue functions too early in init, right? The bug is > about paths into crng_reseed() that might cause that? > > If so, then specifically, are you referring to crng_reseed()'s call to > numa_crng_init()? In other words, the cause of the bug would be > 6c1e851c4edc ("random: fix possible sleeping allocation from irq > context")? If that's the case, then I wonder if the problem you're > seeing goes away if you revert both 6c1e851c4edc ("random: fix > possible sleeping allocation from irq context") and its primary > predecessor, 8ef35c866f88 ("random: set up the NUMA crng instances > after the CRNG is fully initialized"). These fix an actual bug, so I'm > not suggesting we actually revert these in the tree, but for the > purpose of testing, I'm wondering if this is actually the root cause > of the bug you're seeing. If the above holds, I wonder if something more basic like the below would do the trick -- deferring the bringup of the secondary pools until later on in rand_initialize. diff --git a/drivers/char/random.c b/drivers/char/random.c index c81485e2f126..e71b34bf9a2a 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -832,7 +832,6 @@ static void __init crng_initialize_primary(struct crng_state *crng) _extract_entropy(&input_pool, &crng->state[4], sizeof(__u32) * 12, 0); if (crng_init_try_arch_early(crng) && trust_cpu) { invalidate_batched_entropy(); - numa_crng_init(); crng_init = 2; pr_notice("crng done (trusting CPU's manufacturer)\n"); } @@ -840,13 +839,13 @@ static void __init crng_initialize_primary(struct crng_state *crng) } #ifdef CONFIG_NUMA -static void do_numa_crng_init(struct work_struct *work) +static void numa_crng_init(void) { int i; struct crng_state *crng; struct crng_state **pool; - pool = kcalloc(nr_node_ids, sizeof(*pool), GFP_KERNEL|__GFP_NOFAIL); + pool = kcalloc(nr_node_ids, sizeof(*pool), GFP_KERNEL | __GFP_NOFAIL); for_each_online_node(i) { crng = kmalloc_node(sizeof(struct crng_state), GFP_KERNEL | __GFP_NOFAIL, i); @@ -861,13 +860,6 @@ static void do_numa_crng_init(struct work_struct *work) kfree(pool); } } - -static DECLARE_WORK(numa_crng_init_work, do_numa_crng_init); - -static void numa_crng_init(void) -{ - schedule_work(&numa_crng_init_work); -} #else static void numa_crng_init(void) {} #endif @@ -977,7 +969,6 @@ static void crng_reseed(struct crng_state *crng, struct entropy_store *r) spin_unlock_irqrestore(&crng->lock, flags); if (crng == &primary_crng && crng_init < 2) { invalidate_batched_entropy(); - numa_crng_init(); crng_init = 2; process_random_ready_list(); wake_up_interruptible(&crng_init_wait); @@ -1787,6 +1778,7 @@ int __init rand_initialize(void) { init_std_data(&input_pool); crng_initialize_primary(&primary_crng); + numa_crng_init(); crng_global_init_time = jiffies; if (ratelimit_disable) { urandom_warning.interval = 0;
Hi Jason, Am Fri, Dec 03, 2021 at 05:47:41PM +0100 schrieb Jason A. Donenfeld: > On 12/3/21 16:39, Jason A. Donenfeld wrote: > > Hi Dominik, > > > > Thanks for your analysis. Some more questions: > > > > On Fri, Dec 3, 2021 at 8:59 AM Dominik Brodowski > > <linux@dominikbrodowski.net> wrote: > > > On subsequent calls to add_bootloader_randomness() and then to > > > add_hwgenerator_randomness(), crng_fast_load() will be skipped. Instead, > > > wait_event_interruptible() (which makes no sense for the init process) > > > and then credit_entropy_bits() will be called. If the entropy count for > > > that second seed is large enough, that proceeds to crng_reseed(). > > > However, crng_reseed() may depend on workqueues being available, which > > > is not the case early during boot. > > > > It sounds like *the* issue you've identified is that crng_reseed() > > calls into workqueue functions too early in init, right? The bug is > > about paths into crng_reseed() that might cause that? > > > > If so, then specifically, are you referring to crng_reseed()'s call to > > numa_crng_init()? In other words, the cause of the bug would be > > 6c1e851c4edc ("random: fix possible sleeping allocation from irq > > context")? If that's the case, then I wonder if the problem you're > > seeing goes away if you revert both 6c1e851c4edc ("random: fix > > possible sleeping allocation from irq context") and its primary > > predecessor, 8ef35c866f88 ("random: set up the NUMA crng instances > > after the CRNG is fully initialized"). These fix an actual bug, so I'm > > not suggesting we actually revert these in the tree, but for the > > purpose of testing, I'm wondering if this is actually the root cause > > of the bug you're seeing. > > If the above holds, I wonder if something more basic like the below would do > the trick -- deferring the bringup of the secondary pools until later on in > rand_initialize. Firstly, wasn't this done before 8ef35c866f88 -- and initializing the NUMA crng even if not enough entropy had been obtained yet? Secondly, this approach seems works for small amounts of entropy submitted to add_bootloader_randomness (e.g. for four calls with 8 bytes), but not for larger quantities (e.g. for four calls with 64 bytes). Don't ask me why, though. Thirdly, this still does not fix the issue that only the second call to add_bootloader_randomness() credits entropy. Thanks, Dominik
On 12-03 16:39, Jason A. Donenfeld wrote: > Date: Fri, 3 Dec 2021 16:39:55 +0100 > From: "Jason A. Donenfeld" <Jason@zx2c4.com> > To: Dominik Brodowski <linux@dominikbrodowski.net> > Cc: Theodore Ts'o <tytso@mit.edu>, "Ivan T. Ivanov" <iivanov@suse.de>, Ard > Biesheuvel <ardb@kernel.org>, linux-efi@vger.kernel.org, LKML > <linux-kernel@vger.kernel.org>, hsinyi@chromium.org > Subject: Re: [PATCH v4] random: fix crash on multiple early calls to > add_bootloader_randomness() > Message-ID: <CAHmME9qGHo4n6QGxnE+O46pagOR0bA+9E8bi8ZLPAzMuMZpPwg@mail.gmail.com> Tags: all linux me ring watch Hi, > > Hi Dominik, > > Thanks for your analysis. Some more questions: > <snip> > Also, if you have a nice way of reproducing this, please do tell - I'd > like to give it a spin if possible. > Initial bug report could be found here [1]. Comments 14 and onward are probably helpful. To reproduce the issue I have downloaded "assets" from [2] and recreated test environment as found in autoinst-log.txt [3]. Search for qemu-img and qemu-system-aarch64 in the log above. Login credentials for the images could be found by searching for "password" in the same file. Regards, Ivan [1] https://bugzilla.suse.com/show_bug.cgi?id=1184924 [2] https://openqa.opensuse.org/tests/latest?arch=aarch64&distri=opensuse&flavor=DVD&machine=aarch64&test=extra_tests_in_textmode&version=15.3 [3] https://openqa.opensuse.org/tests/2052459/logfile?filename=autoinst-log.txt
On 12-30 19:05, Jason A. Donenfeld wrote: > Date: Thu, 30 Dec 2021 19:05:23 +0100 > From: "Jason A. Donenfeld" <Jason@zx2c4.com> > To: "Ivan T. Ivanov" <iivanov@suse.de> > Cc: Dominik Brodowski <linux@dominikbrodowski.net>, Theodore Ts'o > <tytso@mit.edu>, Ard Biesheuvel <ardb@kernel.org>, > linux-efi@vger.kernel.org, LKML <linux-kernel@vger.kernel.org>, Hsin-Yi > Wang <hsinyi@chromium.org> > Subject: Re: [PATCH v4] random: fix crash on multiple early calls to > add_bootloader_randomness() > Message-ID: <CAHmME9q6DnMk=p5kL0c1e4TxJOLpdxJpm3RbbgsNE8x1PWwi9g@mail.gmail.com> > Hi, > Hey Ivan, > > On Mon, Dec 6, 2021 at 9:14 AM Ivan T. Ivanov <iivanov@suse.de> wrote: > > Initial bug report could be found here [1]. Comments 14 and onward are > > probably helpful. To reproduce the issue I have downloaded "assets" > > from [2] and recreated test environment as found in autoinst-log.txt [3]. > > Search for qemu-img and qemu-system-aarch64 in the log above. Login > > credentials for the images could be found by searching for "password" > > in the same file. > > > > Regards, > > Ivan > > > > > > [1] https://bugzilla.suse.com/show_bug.cgi?id=1184924 > > [2] https://openqa.opensuse.org/tests/latest?arch=aarch64&distri=opensuse&flavor=DVD&machine=aarch64&test=extra_tests_in_textmode&version=15.3 > > [3] https://openqa.opensuse.org/tests/2052459/logfile?filename=autoinst-log.txt > > After a few rounds, Dominik and I converged on a set of patches that > are now in the crng/random.git tree. Do you think you could try this > tree out against your various test environments to confirm it fixes > the issue SUSE was seeing? > > Tree is here: https://git.kernel.org/pub/scm/linux/kernel/git/crng/random.git > Sure, once I have result will post back. Thanks! Ivan
diff --git a/drivers/char/random.c b/drivers/char/random.c index 605969ed0f96..18fe804c1bf8 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -1763,8 +1763,8 @@ static void __init init_std_data(struct entropy_store *r) } /* - * Note that setup_arch() may call add_device_randomness() - * long before we get here. This allows seeding of the pools + * add_device_randomness() or add_bootloader_randomness() may be + * called long before we get here. This allows seeding of the pools * with some platform dependent data very early in the boot * process. But it limits our options here. We must use * statically allocated structures that already have all @@ -2274,7 +2274,12 @@ void add_hwgenerator_randomness(const char *buffer, size_t count, { struct entropy_store *poolp = &input_pool; - if (unlikely(crng_init == 0)) { + /* We cannot do much with the input pool until it is set up in + * rand_initalize(); therefore just mix into the crng state. + * As this does not affect the input pool, we cannot credit + * entropy for this. + */ + if (unlikely(crng_init == 0 || crng_global_init_time == 0)) { crng_fast_load(buffer, count); return; }
If add_bootloader_randomness() or add_hwgenerator_randomness() is called for the first time during early boot, crng_init equals 0. Then, crng_fast_load() gets called -- which is safe to do even if the input pool is not yet properly set up. If the added entropy suffices to increase crng_init to 1, future calls to add_bootloader_randomness() or add_hwgenerator_randomness() used to progress to credit_entropy_bits(). However, if the input pool is not yet properly set up, the cmpxchg call within that function can lead to an infinite recursion. This is not only a hypothetical problem, as qemu on arm64 may provide bootloader entropy via EFI and via devicetree. As crng_global_init_time is set to != 0 once the input pool is properly set up, check (also) for this condition to determine which branch to take. Calls to crng_fast_load() do not modify the input pool; therefore, the entropy_count for the input pool must not be modified at that early stage. Reported-by: Ivan T. Ivanov <iivanov@suse.de> Fixes: 18b915ac6b0a ("efi/random: Treat EFI_RNG_PROTOCOL output as bootloader randomness") Tested-by: Ivan T. Ivanov <iivanov@suse.de> Signed-off-by: Dominik Brodowski <linux@dominikbrodowski.net> --- re-send to new co-maintainer of random.c v2->v3: onle one unlikely (Ard Biesheuvel) v1->v2: fix commit message; unmerge Reported-and-tested-by-tag (Ard Biesheuvel) drivers/char/random.c | 11 ++++++++--- 1 file changed, 8 insertions(+), 3 deletions(-)