Greeting,

FYI, we noticed the following commit (built with clang-14):

commit: 1e1724f9ddd1649555105fd31a8973e7a2e5466c ("[PATCH] random: remove batched entropy locking")
url: https://github.com/0day-ci/linux/commits/Jason-A-Donenfeld/random-remove-batched-entropy-locking/20220128-233457
base: https://git.kernel.org/cgit/linux/kernel/git/gregkh/char-misc.git 710f8af199ee9d72dd87083edd55c5ee250ee6f4
patch link: https://lore.kernel.org/lkml/[email protected]

in testcase: boot

on test machine: qemu-system-x86_64 -enable-kvm -cpu SandyBridge -smp 2 -m 16G

caused below changes (please refer to attached dmesg/kmsg for entire log/backtrace):

+----------------------------------------------------------+------------+------------+
| | 710f8af199 | 1e1724f9dd |
+----------------------------------------------------------+------------+------------+
| UBSAN:array-index-out-of-bounds_in_drivers/char/random.c | 0 | 13 |
| BUG:KASAN:global-out-of-bounds_in_get_random_u32 | 0 | 13 |
+----------------------------------------------------------+------------+------------+

If you fix the issue, kindly add following tag
Reported-by: kernel test robot <[email protected]>

[ 29.921782][ T1] UBSAN: array-index-out-of-bounds in drivers/char/random.c:2141:8
[ 29.923207][ T1] index 8 is out of range for type 'u64[8]' (aka 'unsigned long long[8]')
[ 29.923634][ T1] CPU: 0 PID: 1 Comm: swapper Not tainted 5.17.0-rc1-00010-g1e1724f9ddd1 #2 51d507a9ab4d92cb438b1c02ba5a02d8ac52cd1d
[ 29.923634][ T1] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.12.0-1 04/01/2014
[ 29.923634][ T1] Call Trace:
[ 29.923634][ T1] <TASK>
[ 29.923634][ T1] dump_stack_lvl (??:?)
[ 29.923634][ T1] dump_stack (??:?)
[ 29.923634][ T1] __ubsan_handle_out_of_bounds (??:?)
[ 29.923634][ T1] get_random_u32 (??:?)
[ 29.923634][ T1] bucket_table_alloc (rhashtable.c:?)
[ 29.923634][ T1] rhashtable_init (??:?)
[ 29.923634][ T1] ? rcu_read_lock_sched_held (??:?)
[ 29.923634][ T1] ? bpf_iter_netlink (af_netlink.c:?)
[ 29.923634][ T1] netlink_proto_init (af_netlink.c:?)
[ 29.923634][ T1] do_one_initcall (??:?)
[ 29.923634][ T1] ? bpf_iter_netlink (af_netlink.c:?)
[ 29.923634][ T1] do_initcall_level (main.c:?)
[ 29.923634][ T1] do_initcalls (main.c:?)
[ 29.923634][ T1] do_basic_setup (main.c:?)
[ 29.923634][ T1] kernel_init_freeable (main.c:?)
[ 29.923634][ T1] ? rest_init (main.c:?)
[ 29.923634][ T1] kernel_init (main.c:?)
[ 29.923634][ T1] ? rest_init (main.c:?)
[ 29.923634][ T1] ret_from_fork (??:?)
[ 29.923634][ T1] </TASK>
[ 29.923634][ T1] ================================================================================
[ 29.923718][ T1] ==================================================================
[ 29.924895][ T1] BUG: KASAN: global-out-of-bounds in get_random_u32 (??:?)
[ 29.926024][ T1] Read of size 8 at addr ffffffffb4fe94c0 by task swapper/1
[ 29.926967][ T1]
[ 29.926967][ T1] CPU: 0 PID: 1 Comm: swapper Not tainted 5.17.0-rc1-00010-g1e1724f9ddd1 #2 51d507a9ab4d92cb438b1c02ba5a02d8ac52cd1d
[ 29.926967][ T1] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.12.0-1 04/01/2014
[ 29.926967][ T1] Call Trace:
[ 29.926967][ T1] <TASK>
[ 29.926967][ T1] dump_stack_lvl (??:?)
[ 29.926967][ T1] print_address_description (report.c:?)
[ 29.926967][ T1] __kasan_report (report.c:?)
[ 29.926967][ T1] ? get_random_u32 (??:?)
[ 29.926967][ T1] kasan_report (??:?)
[ 29.926967][ T1] __asan_report_load8_noabort (??:?)
[ 29.926967][ T1] get_random_u32 (??:?)
[ 29.926967][ T1] bucket_table_alloc (rhashtable.c:?)
[ 29.926967][ T1] rhashtable_init (??:?)
[ 29.926967][ T1] ? rcu_read_lock_sched_held (??:?)
[ 29.926967][ T1] ? bpf_iter_netlink (af_netlink.c:?)
[ 29.926967][ T1] netlink_proto_init (af_netlink.c:?)
[ 29.926967][ T1] do_one_initcall (??:?)
[ 29.926967][ T1] ? bpf_iter_netlink (af_netlink.c:?)
[ 29.926967][ T1] do_initcall_level (main.c:?)
[ 29.926967][ T1] do_initcalls (main.c:?)
[ 29.926967][ T1] do_basic_setup (main.c:?)
[ 29.926967][ T1] kernel_init_freeable (main.c:?)
[ 29.926967][ T1] ? rest_init (main.c:?)
[ 29.926967][ T1] kernel_init (main.c:?)
[ 29.926967][ T1] ? rest_init (main.c:?)
[ 29.926967][ T1] ret_from_fork (??:?)
[ 29.926967][ T1] </TASK>
[ 29.926967][ T1]
[ 29.926967][ T1] The buggy address belongs to the variable:
[ 29.926967][ T1] random_write_wakeup_bits+0x0/0x20
[ 29.926967][ T1]
[ 29.926967][ T1] Memory state around the buggy address:
[ 29.926967][ T1] ffffffffb4fe9380: 00 00 00 00 00 00 00 00 00 00 00 00 f9 f9 f9 f9
[ 29.926967][ T1] ffffffffb4fe9400: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
[ 29.926967][ T1] >ffffffffb4fe9480: 00 00 00 00 00 00 00 00 04 f9 f9 f9 00 00 00 00
[ 29.926967][ T1] ^
[ 29.926967][ T1] ffffffffb4fe9500: 00 00 00 00 00 00 f9 f9 f9 f9 f9 f9 01 f9 f9 f9
[ 29.926967][ T1] ffffffffb4fe9580: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
[ 29.926967][ T1] ==================================================================
[ 29.926967][ T1] Disabling lock debugging due to kernel taint
[ 29.927133][ T1] NET: Registered PF_NETLINK/PF_ROUTE protocol family
[ 29.930966][ T1] thermal_sys: Registered thermal governor 'fair_share'
[ 29.930971][ T1] thermal_sys: Registered thermal governor 'bang_bang'
[ 29.932004][ T1] thermal_sys: Registered thermal governor 'step_wise'
[ 29.933055][ T1] thermal_sys: Registered thermal governor 'user_space'
[ 29.933708][ T1] cpuidle: using governor ladder
[ 29.935795][ T1] acpiphp: ACPI Hot Plug PCI Controller Driver version: 0.5
[ 29.937434][ T1] PCI: Using configuration type 1 for base access
[ 29.958988][ T1] kprobes: kprobe jump-optimization is enabled. All kprobes are optimized if possible.
[ 29.960327][ T7] Callback from call_rcu_tasks() invoked.
[ 29.961915][ T1] HugeTLB: can free 6 vmemmap pages for hugepages-2048kB
[ 29.962897][ T1] HugeTLB registered 2.00 MiB page size, pre-allocated 0 pages
[ 29.965886][ T1] cryptd: max_cpu_qlen set to 1000
[ 29.967924][ T1] raid6: skipped pq benchmark and selected sse2x4
[ 29.968825][ T1] raid6: using ssse3x2 recovery algorithm
[ 29.969891][ T1] ACPI: Added _OSI(Module Device)
[ 29.970307][ T1] ACPI: Added _OSI(Processor Device)
[ 29.971058][ T1] ACPI: Added _OSI(3.0 _SCP Extensions)
[ 29.971841][ T1] ACPI: Added _OSI(Processor Aggregator Device)
[ 29.972747][ T1] ACPI: Added _OSI(Linux-Dell-Video)
[ 29.973549][ T1] ACPI: Added _OSI(Linux-Lenovo-NV-HDMI-Audio)
[ 29.973648][ T1] ACPI: Added _OSI(Linux-HPI-Hybrid-Graphics)
[ 29.994328][ T1] ACPI: 1 ACPI AML tables successfully acquired and loaded
[ 30.006626][ T1] ACPI: Interpreter enabled
[ 30.007071][ T1] ACPI: PM: (supports S0 S3 S5)
[ 30.007783][ T1] ACPI: Using IOAPIC for interrupt routing
[ 30.008714][ T1] PCI: Using host bridge windows from ACPI; if necessary, use "pci=nocrs" and report a bug
[ 30.011387][ T1] ACPI: Enabled 2 GPEs in block 00 to 0F
[ 30.053305][ T1] ACPI: PCI Root Bridge [PCI0] (domain 0000 [bus 00-ff])
[ 30.053667][ T1] acpi PNP0A03:00: _OSC: OS supports [ASPM ClockPM Segments MSI HPX-Type3]
[ 30.054872][ T1] acpi PNP0A03:00: PCIe port services disabled; not requesting _OSC control
[ 30.056154][ T1] acpi PNP0A03:00: fail to add MMCONFIG information, can't access extended PCI configuration space under this bridge.
[ 30.057970][ T1] acpiphp: Slot [3] registered
[ 30.058877][ T1] acpiphp: Slot [4] registered
[ 30.059769][ T1] acpiphp: Slot [5] registered
[ 30.060516][ T1] acpiphp: Slot [6] registered
[ 30.061393][ T1] acpiphp: Slot [7] registered
[ 30.062306][ T1] acpiphp: Slot [8] registered
[ 30.063187][ T1] acpiphp: Slot [9] registered
[ 30.063877][ T1] acpiphp: Slot [10] registered
[ 30.064814][ T1] acpiphp: Slot [11] registered
[ 30.065712][ T1] acpiphp: Slot [12] registered
[ 30.066613][ T1] acpiphp: Slot [13] registered
[ 30.067181][ T1] acpiphp: Slot [14] registered
[ 30.068082][ T1] acpiphp: Slot [15] registered
[ 30.068992][ T1] acpiphp: Slot [16] registered
[ 30.069889][ T1] acpiphp: Slot [17] registered
[ 30.070506][ T1] acpiphp: Slot [18] registered
[ 30.071401][ T1] acpiphp: Slot [19] registered
[ 30.072314][ T1] acpiphp: Slot [20] registered
[ 30.073206][ T1] acpiphp: Slot [21] registered
[ 30.073840][ T1] acpiphp: Slot [22] registered
[ 30.074765][ T1] acpiphp: Slot [23] registered
[ 30.075669][ T1] acpiphp: Slot [24] registered
[ 30.076557][ T1] acpiphp: Slot [25] registered
[ 30.077176][ T1] acpiphp: Slot [26] registered
[ 30.078073][ T1] acpiphp: Slot [27] registered
[ 30.078982][ T1] acpiphp: Slot [28] registered

To reproduce:

# build kernel
cd linux
cp config-5.17.0-rc1-00010-g1e1724f9ddd1 .config
make HOSTCC=clang-14 CC=clang-14 ARCH=x86_64 olddefconfig prepare modules_prepare bzImage modules
make HOSTCC=clang-14 CC=clang-14 ARCH=x86_64 INSTALL_MOD_PATH=<mod-install-dir> modules_install
cd <mod-install-dir>
find lib/ | cpio -o -H newc --quiet | gzip > modules.cgz

git clone https://github.com/intel/lkp-tests.git
cd lkp-tests
bin/lkp qemu -k <bzImage> -m modules.cgz job-script # job-script is attached in this email

# if come across any failure that blocks the test,
# please remove ~/.lkp and /lkp dir to run from a clean state.

---
0DAY/LKP+ Test Infrastructure Open Source Technology Center
https://lists.01.org/hyperkitty/list/[email protected] Intel Corporation

Thanks,
Oliver Sang

Attachments:

(No filename) (9.92 kB)
config-5.17.0-rc1-00010-g1e1724f9ddd1 (146.35 kB)
job-script (4.84 kB)
dmesg.xz (13.63 kB)
Download all attachments

2022-02-01 07:52:04

by Jason A. Donenfeld

[permalink] [raw]

Subject: Re: [PATCH] random: remove batched entropy locking

Hey Jonathan,

On Fri, Jan 28, 2022 at 7:05 PM Jonathan Neuschäfer
<[email protected]> wrote:
> FWIW, this does fix the splat on my machine.
>
> Tested-by: Jonathan Neuschäfer <[email protected]>

Thanks for testing. If it's not too much trouble, would you verify v2
as well? It's substantially different from v1 that it doesn't seem
right to carry through your Tested-by, and from talking a bit with
Andy, I think we're more likely to go with a v2-like approach than a
v1-like one.

Jason

2022-02-01 08:47:11

Rather than use spinlocks to protect batched entropy, we can instead
disable interrupts locally, since we're dealing with per-cpu data, and
manage resets with a basic generation counter. At the same time, we
can't quite do this on PREEMPT_RT, where we still want spinlocks-as-
mutexes semantics. So we use a local_lock_t, which provides the right
behavior for each. Because this is a per-cpu lock, that generation
counter is still doing the necessary CPU-to-CPU communication.

This should improve performance a bit. It will also fix the linked splat
that Jonathan received with a PROVE_RAW_LOCK_NESTING=y.

Note that Sebastian has pointed out a few other areas where
using spinlock_t in an IRQ context is potentially problematic for
PREEMPT_RT. This patch handles one of those cases, and we'll hopefully
have additional patches for other cases.

Suggested-by: Andy Lutomirski <[email protected]>
Reported-by: Jonathan Neuschäfer <[email protected]>
Tested-by: Jonathan Neuschäfer <[email protected]>
Link: https://lore.kernel.org/lkml/YfMa0QgsjCVdRAvJ@latitude/
Cc: Sebastian Andrzej Siewior <[email protected]>
Signed-off-by: Jason A. Donenfeld <[email protected]>
---
drivers/char/random.c | 55 ++++++++++++++++++++++---------------------
1 file changed, 28 insertions(+), 27 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 455615ac169a..3e54b90a3ff8 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -1732,13 +1732,16 @@ struct ctl_table random_table[] = {
};
#endif /* CONFIG_SYSCTL */

+static atomic_t batch_generation = ATOMIC_INIT(0);
+
struct batched_entropy {
union {
u64 entropy_u64[CHACHA_BLOCK_SIZE / sizeof(u64)];
u32 entropy_u32[CHACHA_BLOCK_SIZE / sizeof(u32)];
};
+ local_lock_t lock;
unsigned int position;
- spinlock_t batch_lock;
+ int generation;
};

/*
@@ -1750,7 +1753,7 @@ struct batched_entropy {
* point prior.
*/
static DEFINE_PER_CPU(struct batched_entropy, batched_entropy_u64) = {
- .batch_lock = __SPIN_LOCK_UNLOCKED(batched_entropy_u64.lock),
+ .lock = INIT_LOCAL_LOCK(batched_entropy_u64.lock)
};

u64 get_random_u64(void)
@@ -1759,41 +1762,54 @@ u64 get_random_u64(void)
unsigned long flags;
struct batched_entropy *batch;
static void *previous;
+ int next_gen;

warn_unseeded_randomness(&previous);

- batch = raw_cpu_ptr(&batched_entropy_u64);
- spin_lock_irqsave(&batch->batch_lock, flags);
- if (batch->position % ARRAY_SIZE(batch->entropy_u64) == 0) {
+ batch = this_cpu_ptr(&batched_entropy_u64);
+ local_lock_irqsave(&batch->lock, flags);
+
+ next_gen = atomic_read(&batch_generation);
+ if (batch->position % ARRAY_SIZE(batch->entropy_u64) == 0 ||
+ next_gen != batch->generation) {
extract_crng((u8 *)batch->entropy_u64);
batch->position = 0;
+ batch->generation = next_gen;
}
+
ret = batch->entropy_u64[batch->position++];
- spin_unlock_irqrestore(&batch->batch_lock, flags);
+ local_unlock_irqrestore(&batch->lock, flags);
return ret;
}
EXPORT_SYMBOL(get_random_u64);

static DEFINE_PER_CPU(struct batched_entropy, batched_entropy_u32) = {
- .batch_lock = __SPIN_LOCK_UNLOCKED(batched_entropy_u32.lock),
+ .lock = INIT_LOCAL_LOCK(batched_entropy_u32.lock)
};
+
u32 get_random_u32(void)
{
u32 ret;
unsigned long flags;
struct batched_entropy *batch;
static void *previous;
+ int next_gen;

warn_unseeded_randomness(&previous);

- batch = raw_cpu_ptr(&batched_entropy_u32);
- spin_lock_irqsave(&batch->batch_lock, flags);
- if (batch->position % ARRAY_SIZE(batch->entropy_u32) == 0) {
+ batch = this_cpu_ptr(&batched_entropy_u32);
+ local_lock_irqsave(&batch->lock, flags);
+
+ next_gen = atomic_read(&batch_generation);
+ if (batch->position % ARRAY_SIZE(batch->entropy_u32) == 0 ||
+ next_gen != batch->generation) {
extract_crng((u8 *)batch->entropy_u32);
batch->position = 0;
+ batch->generation = next_gen;
}
+
ret = batch->entropy_u32[batch->position++];
- spin_unlock_irqrestore(&batch->batch_lock, flags);
+ local_unlock_irqrestore(&batch->lock, flags);
return ret;
}
EXPORT_SYMBOL(get_random_u32);
@@ -1804,22 +1820,7 @@ EXPORT_SYMBOL(get_random_u32);
* next usage. */
static void invalidate_batched_entropy(void)
{
- int cpu;
- unsigned long flags;
-
- for_each_possible_cpu(cpu) {
- struct batched_entropy *batched_entropy;
-
- batched_entropy = per_cpu_ptr(&batched_entropy_u32, cpu);
- spin_lock_irqsave(&batched_entropy->batch_lock, flags);
- batched_entropy->position = 0;
- spin_unlock(&batched_entropy->batch_lock);
-
- batched_entropy = per_cpu_ptr(&batched_entropy_u64, cpu);
- spin_lock(&batched_entropy->batch_lock);
- batched_entropy->position = 0;
- spin_unlock_irqrestore(&batched_entropy->batch_lock, flags);
- }
+ atomic_inc(&batch_generation);
}

/**
--
2.35.0