Evaluate whether to use semaphores or waitqueues for blocking ops #14

dberliner · 2020-01-14T20:20:06Z

Blocks have the following considerations

We can't wake up too many threads at once
Creating too many blockable objects may be difficult to manage
Reads do not lend themselves to waitqueues if we need to block internally (Investigate kernel blocking for sock calls #13).
Many threads may call blocking ops and make semaphore blocking a bad idea.

This should be done after #13 when it is clear what blocking the SCM drivers have to do and what can be offloaded to the kernel.

dberliner · 2020-01-15T04:58:52Z

With respect to 13, all sock related blocks should be handled like I wrote about in the comments. Internally, however, we still need our own mechanics. IO ops can probably be written to use these constructs with nearly no visibility into internal blocking mechanisms. Wait queues can probably take care of the rest, while semaphores provided some nice looking functionality I think they insufficient moving forward.

This reverts commit 3df85a1. The reverted commit says "It's possible to release the node ID immediately when fwnode_remove_software_node() is called, no need to wait for software_node_release() with that." However, releasing the node ID before waiting for software_node_release() to be called causes the node ID to be released before the kobject and the underlying sysfs entry; this means there is a period of time where a sysfs entry exists that is associated with an unallocated node ID. Once consequence of this is that there is a race condition where it is possible to call fwnode_create_software_node() with no parent node specified (NULL) and have it fail with -EEXIST because the node ID that was assigned is still associated with a stale sysfs entry that hasn't been cleaned up yet. Although it is difficult to reproduce this race condition under normal conditions, it can be deterministically reproduced with the following minconfig on UML: CONFIG_KUNIT_DRIVER_PE_TEST=y CONFIG_DEBUG_KERNEL=y CONFIG_DEBUG_OBJECTS=y CONFIG_DEBUG_OBJECTS_TIMERS=y CONFIG_DEBUG_KOBJECT_RELEASE=y CONFIG_KUNIT=y Running the tests with this configuration causes the following failure: <snip> kobject: 'node0' ((____ptrval____)): kobject_release, parent (____ptrval____) (delayed 400) ok 1 - pe_test_uints sysfs: cannot create duplicate filename '/kernel/software_nodes/node0' CPU: 0 PID: 28 Comm: kunit_try_catch Not tainted 5.6.0-rc3-next-20200227 #14 <snip> kobject_add_internal failed for node0 with -EEXIST, don't try to register things with the same name in the same directory. kobject: 'node0' ((____ptrval____)): kobject_release, parent (____ptrval____) (delayed 100) # pe_test_uint_arrays: ASSERTION FAILED at drivers/base/test/property-entry-test.c:123 Expected node is not error, but is: -17 not ok 2 - pe_test_uint_arrays <snip> Reported-by: Heidi Fahim <[email protected]> Signed-off-by: Brendan Higgins <[email protected]> Reviewed-by: Heikki Krogerus <[email protected]> Cc: 5.3+ <[email protected]> # 5.3+ Signed-off-by: Rafael J. Wysocki <[email protected]>

When experimenting with bpf_send_signal() helper in our production environment (5.2 based), we experienced a deadlock in NMI mode: #5 [ffffc9002219f770] queued_spin_lock_slowpath at ffffffff8110be24 #6 [ffffc9002219f770] _raw_spin_lock_irqsave at ffffffff81a43012 #7 [ffffc9002219f780] try_to_wake_up at ffffffff810e7ecd #8 [ffffc9002219f7e0] signal_wake_up_state at ffffffff810c7b55 #9 [ffffc9002219f7f0] __send_signal at ffffffff810c8602 #10 [ffffc9002219f830] do_send_sig_info at ffffffff810ca31a #11 [ffffc9002219f868] bpf_send_signal at ffffffff8119d227 #12 [ffffc9002219f988] bpf_overflow_handler at ffffffff811d4140 #13 [ffffc9002219f9e0] __perf_event_overflow at ffffffff811d68cf #14 [ffffc9002219fa10] perf_swevent_overflow at ffffffff811d6a09 #15 [ffffc9002219fa38] ___perf_sw_event at ffffffff811e0f47 #16 [ffffc9002219fc30] __schedule at ffffffff81a3e04d #17 [ffffc9002219fc90] schedule at ffffffff81a3e219 #18 [ffffc9002219fca0] futex_wait_queue_me at ffffffff8113d1b9 #19 [ffffc9002219fcd8] futex_wait at ffffffff8113e529 #20 [ffffc9002219fdf0] do_futex at ffffffff8113ffbc #21 [ffffc9002219fec0] __x64_sys_futex at ffffffff81140d1c #22 [ffffc9002219ff38] do_syscall_64 at ffffffff81002602 torvalds#23 [ffffc9002219ff50] entry_SYSCALL_64_after_hwframe at ffffffff81c00068 The above call stack is actually very similar to an issue reported by Commit eac9153 ("bpf/stackmap: Fix deadlock with rq_lock in bpf_get_stack()") by Song Liu. The only difference is bpf_send_signal() helper instead of bpf_get_stack() helper. The above deadlock is triggered with a perf_sw_event. Similar to Commit eac9153, the below almost identical reproducer used tracepoint point sched/sched_switch so the issue can be easily caught. /* stress_test.c */ #include <stdio.h> #include <stdlib.h> #include <sys/mman.h> #include <pthread.h> #include <sys/types.h> #include <sys/stat.h> #include <fcntl.h> #define THREAD_COUNT 1000 char *filename; void *worker(void *p) { void *ptr; int fd; char *pptr; fd = open(filename, O_RDONLY); if (fd < 0) return NULL; while (1) { struct timespec ts = {0, 1000 + rand() % 2000}; ptr = mmap(NULL, 4096 * 64, PROT_READ, MAP_PRIVATE, fd, 0); usleep(1); if (ptr == MAP_FAILED) { printf("failed to mmap\n"); break; } munmap(ptr, 4096 * 64); usleep(1); pptr = malloc(1); usleep(1); pptr[0] = 1; usleep(1); free(pptr); usleep(1); nanosleep(&ts, NULL); } close(fd); return NULL; } int main(int argc, char *argv[]) { void *ptr; int i; pthread_t threads[THREAD_COUNT]; if (argc < 2) return 0; filename = argv[1]; for (i = 0; i < THREAD_COUNT; i++) { if (pthread_create(threads + i, NULL, worker, NULL)) { fprintf(stderr, "Error creating thread\n"); return 0; } } for (i = 0; i < THREAD_COUNT; i++) pthread_join(threads[i], NULL); return 0; } and the following command: 1. run `stress_test /bin/ls` in one windown 2. hack bcc trace.py with the following change: --- a/tools/trace.py +++ b/tools/trace.py @@ -513,6 +513,7 @@ BPF_PERF_OUTPUT(%s); __data.tgid = __tgid; __data.pid = __pid; bpf_get_current_comm(&__data.comm, sizeof(__data.comm)); + bpf_send_signal(10); %s %s %s.perf_submit(%s, &__data, sizeof(__data)); 3. in a different window run ./trace.py -p $(pidof stress_test) t:sched:sched_switch The deadlock can be reproduced in our production system. Similar to Song's fix, the fix is to delay sending signal if irqs is disabled to avoid deadlocks involving with rq_lock. With this change, my above stress-test in our production system won't cause deadlock any more. I also implemented a scale-down version of reproducer in the selftest (a subsequent commit). With latest bpf-next, it complains for the following potential deadlock. [ 32.832450] -> #1 (&p->pi_lock){-.-.}: [ 32.833100] _raw_spin_lock_irqsave+0x44/0x80 [ 32.833696] task_rq_lock+0x2c/0xa0 [ 32.834182] task_sched_runtime+0x59/0xd0 [ 32.834721] thread_group_cputime+0x250/0x270 [ 32.835304] thread_group_cputime_adjusted+0x2e/0x70 [ 32.835959] do_task_stat+0x8a7/0xb80 [ 32.836461] proc_single_show+0x51/0xb0 ... [ 32.839512] -> #0 (&(&sighand->siglock)->rlock){....}: [ 32.840275] __lock_acquire+0x1358/0x1a20 [ 32.840826] lock_acquire+0xc7/0x1d0 [ 32.841309] _raw_spin_lock_irqsave+0x44/0x80 [ 32.841916] __lock_task_sighand+0x79/0x160 [ 32.842465] do_send_sig_info+0x35/0x90 [ 32.842977] bpf_send_signal+0xa/0x10 [ 32.843464] bpf_prog_bc13ed9e4d3163e3_send_signal_tp_sched+0x465/0x1000 [ 32.844301] trace_call_bpf+0x115/0x270 [ 32.844809] perf_trace_run_bpf_submit+0x4a/0xc0 [ 32.845411] perf_trace_sched_switch+0x10f/0x180 [ 32.846014] __schedule+0x45d/0x880 [ 32.846483] schedule+0x5f/0xd0 ... [ 32.853148] Chain exists of: [ 32.853148] &(&sighand->siglock)->rlock --> &p->pi_lock --> &rq->lock [ 32.853148] [ 32.854451] Possible unsafe locking scenario: [ 32.854451] [ 32.855173] CPU0 CPU1 [ 32.855745] ---- ---- [ 32.856278] lock(&rq->lock); [ 32.856671] lock(&p->pi_lock); [ 32.857332] lock(&rq->lock); [ 32.857999] lock(&(&sighand->siglock)->rlock); Deadlock happens on CPU0 when it tries to acquire &sighand->siglock but it has been held by CPU1 and CPU1 tries to grab &rq->lock and cannot get it. This is not exactly the callstack in our production environment, but sympotom is similar and both locks are using spin_lock_irqsave() to acquire the lock, and both involves rq_lock. The fix to delay sending signal when irq is disabled also fixed this issue. Signed-off-by: Yonghong Song <[email protected]> Signed-off-by: Alexei Starovoitov <[email protected]> Cc: Song Liu <[email protected]> Link: https://lore.kernel.org/bpf/[email protected]

dberliner self-assigned this Jan 14, 2020

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Evaluate whether to use semaphores or waitqueues for blocking ops #14

Evaluate whether to use semaphores or waitqueues for blocking ops #14

dberliner commented Jan 14, 2020

dberliner commented Jan 15, 2020

Evaluate whether to use semaphores or waitqueues for blocking ops #14

Evaluate whether to use semaphores or waitqueues for blocking ops #14

Comments

dberliner commented Jan 14, 2020

dberliner commented Jan 15, 2020