perf/hw_breakpoint: Optimize for thousands of tasks

Add KUnit test for hw_breakpoint constraints accounting, with various interesting mixes of breakpoint targets (some care was taken to catch interesting corner cases via bug-injection).

The test cannot be built as a module because it requires access to hw_breakpoint_slots(), which is not inlinable or exported on all architectures.

Signed-off-by Marco Elver <[email protected]>

---
v2:
* New patch.

---
 kernel/events/Makefile             |   1 +
 kernel/events/hw_breakpoint_test.c | 321 +++++++++++++++++++++++++++++
 lib/Kconfig.debug                  |  10 +
 3 files changed, 332 insertions(+)
 create mode 100644 kernel/events/hw_breakpoint_test.c

kernel/events/Makefile +1 -0

index 8591c180b52b..91a62f566743 100644
@@ -2,4 +2,5 @@
 obj-y := core.o ring_buffer.o callchain.o
 
 obj-$(CONFIG_HAVE_HW_BREAKPOINT) += hw_breakpoint.o
+obj-$(CONFIG_HW_BREAKPOINT_KUNIT_TEST) += hw_breakpoint_test.o
 obj-$(CONFIG_UPROBES) += uprobes.o

kernel/events/hw_breakpoint_test.c new file +47 -0

new file mode 100644
index 000000000000..747a0249a606
@@ -0,0 +1,321 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * KUnit test for hw_breakpoint constraints accounting logic.
+ *
+ * Copyright (C) 2022, Google LLC.
+ */
+
+#include <kunit/test.h>
+#include <linux/cpumask.h>
+#include <linux/hw_breakpoint.h>
+#include <linux/kthread.h>
+#include <linux/perf_event.h>
+#include <asm/hw_breakpoint.h>
+
+#define TEST_REQUIRES_BP_SLOTS(test, slots)                                            \
+       do {                                                                            \
+               if ((slots) > get_test_bp_slots()) {                                    \
+                       kunit_skip((test), "Requires breakpoint slots: %d > %d", slots, \
+                                  get_test_bp_slots());                                \
+               }                                                                       \
+       } while (0)
+
+#define TEST_EXPECT_NOSPC(expr) KUNIT_EXPECT_EQ(test, -ENOSPC, PTR_ERR(expr))
+
+#define MAX_TEST_BREAKPOINTS 512
+
+static char break_vars[MAX_TEST_BREAKPOINTS];
+static struct perf_event *test_bps[MAX_TEST_BREAKPOINTS];
+static struct task_struct *__other_task;
+
+static struct perf_event *register_test_bp(int cpu, struct task_struct *tsk, int idx)
+{
+       struct perf_event_attr attr = {};
+
+       if (WARN_ON(idx < 0 || idx >= MAX_TEST_BREAKPOINTS))
+               return NULL;
+
+       hw_breakpoint_init(&attr);
+       attr.bp_addr = (unsigned long)&break_vars[idx];
+       attr.bp_len = HW_BREAKPOINT_LEN_1;
+       attr.bp_type = HW_BREAKPOINT_RW;
+       return perf_event_create_kernel_counter(&attr, cpu, tsk, NULL, NULL);
+}
+
+static void unregister_test_bp(struct perf_event **bp)
+{
+       if (WARN_ON(IS_ERR(*bp)))

kernel/events/hw_breakpoint_test.c new file +44 -0

+
+       if (!slots)
+               slots = hw_breakpoint_slots(TYPE_DATA);
+
+       return slots;
+}
+
+static void fill_one_bp_slot(struct kunit *test, int *id, int cpu, struct task_struct *tsk)
+{
+       struct perf_event *bp = register_test_bp(cpu, tsk, *id);
+
+       KUNIT_ASSERT_NOT_NULL(test, bp);
+       KUNIT_ASSERT_FALSE(test, IS_ERR(bp));
+       KUNIT_ASSERT_NULL(test, test_bps[*id]);
+       test_bps[(*id)++] = bp;
+}
+
+/*
+ * Fills up the given @cpu/@tsk with breakpoints, only leaving @skip slots free.
+ *
+ * Returns true if this can be called again, continuing at @id.
+ */
+static bool fill_bp_slots(struct kunit *test, int *id, int cpu, struct task_struct *tsk, int skip)
+{
+       for (int i = 0; i < get_test_bp_slots() - skip; ++i)
+               fill_one_bp_slot(test, id, cpu, tsk);
+
+       return *id + get_test_bp_slots() <= MAX_TEST_BREAKPOINTS;
+}
+
+static int dummy_kthread(void *arg)
+{
+       return 0;
+}
+
+static struct task_struct *get_other_task(struct kunit *test)
+{
+       struct task_struct *tsk;
+
+       if (__other_task)
+               return __other_task;
+
+       tsk = kthread_create(dummy_kthread, NULL, "hw_breakpoint_dummy_task");
+       KUNIT_ASSERT_FALSE(test, IS_ERR(tsk));

kernel/events/hw_breakpoint_test.c new file +210 -0

+                       break;
+       }
+
+       return cpu;
+}
+
+/* ===== Test cases ===== */
+
+static void test_one_cpu(struct kunit *test)
+{
+       int idx = 0;
+
+       fill_bp_slots(test, &idx, raw_smp_processor_id(), NULL, 0);
+       TEST_EXPECT_NOSPC(register_test_bp(-1, current, idx));
+       TEST_EXPECT_NOSPC(register_test_bp(raw_smp_processor_id(), NULL, idx));
+}
+
+static void test_many_cpus(struct kunit *test)
+{
+       int idx = 0;
+       int cpu;
+
+       /* Test that CPUs are independent. */
+       for_each_online_cpu(cpu) {
+               bool do_continue = fill_bp_slots(test, &idx, cpu, NULL, 0);
+
+               TEST_EXPECT_NOSPC(register_test_bp(cpu, NULL, idx));
+               if (!do_continue)
+                       break;
+       }
+}
+
+static void test_one_task_on_all_cpus(struct kunit *test)
+{
+       int idx = 0;
+
+       fill_bp_slots(test, &idx, -1, current, 0);
+       TEST_EXPECT_NOSPC(register_test_bp(-1, current, idx));
+       TEST_EXPECT_NOSPC(register_test_bp(raw_smp_processor_id(), current, idx));
+       TEST_EXPECT_NOSPC(register_test_bp(raw_smp_processor_id(), NULL, idx));
+       /* Remove one and adding back CPU-target should work. */
+       unregister_test_bp(&test_bps[0]);
+       fill_one_bp_slot(test, &idx, raw_smp_processor_id(), NULL);
+}
+
+static void test_two_tasks_on_all_cpus(struct kunit *test)
+{
+       int idx = 0;
+
+       /* Test that tasks are independent. */
+       fill_bp_slots(test, &idx, -1, current, 0);
+       fill_bp_slots(test, &idx, -1, get_other_task(test), 0);
+
+       TEST_EXPECT_NOSPC(register_test_bp(-1, current, idx));
+       TEST_EXPECT_NOSPC(register_test_bp(-1, get_other_task(test), idx));
+       TEST_EXPECT_NOSPC(register_test_bp(raw_smp_processor_id(), current, idx));
+       TEST_EXPECT_NOSPC(register_test_bp(raw_smp_processor_id(), get_other_task(test), idx));
+       TEST_EXPECT_NOSPC(register_test_bp(raw_smp_processor_id(), NULL, idx));
+       /* Remove one from first task and adding back CPU-target should not work. */
+       unregister_test_bp(&test_bps[0]);
+       TEST_EXPECT_NOSPC(register_test_bp(raw_smp_processor_id(), NULL, idx));
+}
+
+static void test_one_task_on_one_cpu(struct kunit *test)
+{
+       int idx = 0;
+
+       fill_bp_slots(test, &idx, raw_smp_processor_id(), current, 0);
+       TEST_EXPECT_NOSPC(register_test_bp(-1, current, idx));
+       TEST_EXPECT_NOSPC(register_test_bp(raw_smp_processor_id(), current, idx));
+       TEST_EXPECT_NOSPC(register_test_bp(raw_smp_processor_id(), NULL, idx));
+       /*
+        * Remove one and adding back CPU-target should work; this case is
+        * special vs. above because the task's constraints are CPU-dependent.
+        */
+       unregister_test_bp(&test_bps[0]);
+       fill_one_bp_slot(test, &idx, raw_smp_processor_id(), NULL);
+}
+
+static void test_one_task_mixed(struct kunit *test)
+{
+       int idx = 0;
+
+       TEST_REQUIRES_BP_SLOTS(test, 3);
+
+       fill_one_bp_slot(test, &idx, raw_smp_processor_id(), current);
+       fill_bp_slots(test, &idx, -1, current, 1);
+       TEST_EXPECT_NOSPC(register_test_bp(-1, current, idx));
+       TEST_EXPECT_NOSPC(register_test_bp(raw_smp_processor_id(), current, idx));
+       TEST_EXPECT_NOSPC(register_test_bp(raw_smp_processor_id(), NULL, idx));
+
+       /* Transition from CPU-dependent pinned count to CPU-independent. */
+       unregister_test_bp(&test_bps[0]);
+       unregister_test_bp(&test_bps[1]);
+       fill_one_bp_slot(test, &idx, raw_smp_processor_id(), NULL);
+       fill_one_bp_slot(test, &idx, raw_smp_processor_id(), NULL);
+       TEST_EXPECT_NOSPC(register_test_bp(raw_smp_processor_id(), NULL, idx));
+}
+
+static void test_two_tasks_on_one_cpu(struct kunit *test)
+{
+       int idx = 0;
+
+       fill_bp_slots(test, &idx, raw_smp_processor_id(), current, 0);
+       fill_bp_slots(test, &idx, raw_smp_processor_id(), get_other_task(test), 0);
+
+       TEST_EXPECT_NOSPC(register_test_bp(-1, current, idx));
+       TEST_EXPECT_NOSPC(register_test_bp(-1, get_other_task(test), idx));
+       TEST_EXPECT_NOSPC(register_test_bp(raw_smp_processor_id(), current, idx));
+       TEST_EXPECT_NOSPC(register_test_bp(raw_smp_processor_id(), get_other_task(test), idx));
+       TEST_EXPECT_NOSPC(register_test_bp(raw_smp_processor_id(), NULL, idx));
+       /* Can still create breakpoints on some other CPU. */
+       fill_bp_slots(test, &idx, get_other_cpu(), NULL, 0);
+}
+
+static void test_two_tasks_on_one_all_cpus(struct kunit *test)
+{
+       int idx = 0;
+
+       fill_bp_slots(test, &idx, raw_smp_processor_id(), current, 0);
+       fill_bp_slots(test, &idx, -1, get_other_task(test), 0);
+
+       TEST_EXPECT_NOSPC(register_test_bp(-1, current, idx));
+       TEST_EXPECT_NOSPC(register_test_bp(-1, get_other_task(test), idx));
+       TEST_EXPECT_NOSPC(register_test_bp(raw_smp_processor_id(), current, idx));
+       TEST_EXPECT_NOSPC(register_test_bp(raw_smp_processor_id(), get_other_task(test), idx));
+       TEST_EXPECT_NOSPC(register_test_bp(raw_smp_processor_id(), NULL, idx));
+       /* Cannot create breakpoints on some other CPU either. */
+       TEST_EXPECT_NOSPC(register_test_bp(get_other_cpu(), NULL, idx));
+}
+
+static void test_task_on_all_and_one_cpu(struct kunit *test)
+{
+       int tsk_on_cpu_idx, cpu_idx;
+       int idx = 0;
+
+       TEST_REQUIRES_BP_SLOTS(test, 3);
+
+       fill_bp_slots(test, &idx, -1, current, 2);
+       /* Transitioning from only all CPU breakpoints to mixed. */
+       tsk_on_cpu_idx = idx;
+       fill_one_bp_slot(test, &idx, raw_smp_processor_id(), current);
+       fill_one_bp_slot(test, &idx, -1, current);
+
+       TEST_EXPECT_NOSPC(register_test_bp(-1, current, idx));
+       TEST_EXPECT_NOSPC(register_test_bp(raw_smp_processor_id(), current, idx));
+       TEST_EXPECT_NOSPC(register_test_bp(raw_smp_processor_id(), NULL, idx));
+
+       /* We should still be able to use up another CPU's slots. */
+       cpu_idx = idx;
+       fill_one_bp_slot(test, &idx, get_other_cpu(), NULL);
+       TEST_EXPECT_NOSPC(register_test_bp(get_other_cpu(), NULL, idx));
+
+       /* Transitioning back to task target on all CPUs. */
+       unregister_test_bp(&test_bps[tsk_on_cpu_idx]);
+       /* Still have a CPU target breakpoint in get_other_cpu(). */
+       TEST_EXPECT_NOSPC(register_test_bp(-1, current, idx));
+       /* Remove it and try again. */
+       unregister_test_bp(&test_bps[cpu_idx]);
+       fill_one_bp_slot(test, &idx, -1, current);
+
+       TEST_EXPECT_NOSPC(register_test_bp(-1, current, idx));
+       TEST_EXPECT_NOSPC(register_test_bp(raw_smp_processor_id(), current, idx));
+       TEST_EXPECT_NOSPC(register_test_bp(raw_smp_processor_id(), NULL, idx));
+       TEST_EXPECT_NOSPC(register_test_bp(get_other_cpu(), NULL, idx));
+}
+
+static struct kunit_case hw_breakpoint_test_cases[] = {
+       KUNIT_CASE(test_one_cpu),
+       KUNIT_CASE(test_many_cpus),
+       KUNIT_CASE(test_one_task_on_all_cpus),
+       KUNIT_CASE(test_two_tasks_on_all_cpus),
+       KUNIT_CASE(test_one_task_on_one_cpu),
+       KUNIT_CASE(test_one_task_mixed),
+       KUNIT_CASE(test_two_tasks_on_one_cpu),
+       KUNIT_CASE(test_two_tasks_on_one_all_cpus),
+       KUNIT_CASE(test_task_on_all_and_one_cpu),
+       {},
+};
+
+static int test_init(struct kunit *test)
+{
+       /* Most test cases want 2 distinct CPUs. */
+       return num_online_cpus() < 2 ? -EINVAL : 0;
+}
+
+static void test_exit(struct kunit *test)
+{
+       for (int i = 0; i < MAX_TEST_BREAKPOINTS; ++i) {
+               if (test_bps[i])
+                       unregister_test_bp(&test_bps[i]);
+       }
+
+       if (__other_task) {
+               kthread_stop(__other_task);
+               __other_task = NULL;
+       }
+}
+
+static struct kunit_suite hw_breakpoint_test_suite = {
+       .name = "hw_breakpoint",
+       .test_cases = hw_breakpoint_test_cases,
+       .init = test_init,
+       .exit = test_exit,
+};
+
+kunit_test_suites(&hw_breakpoint_test_suite);
+
+MODULE_LICENSE("GPL");
+MODULE_AUTHOR("Marco Elver <[email protected]>");

lib/Kconfig.debug +10 -1

index 2e24db4bff19..4c87a6edf046 100644
@@ -2513,6 +2513,16 @@ config STACKINIT_KUNIT_TEST
          CONFIG_GCC_PLUGIN_STRUCTLEAK, CONFIG_GCC_PLUGIN_STRUCTLEAK_BYREF,
          or CONFIG_GCC_PLUGIN_STRUCTLEAK_BYREF_ALL.
 
+config HW_BREAKPOINT_KUNIT_TEST
+       bool "Test hw_breakpoint constraints accounting" if !KUNIT_ALL_TESTS
+       depends on HAVE_HW_BREAKPOINT
+       depends on KUNIT=y
+       default KUNIT_ALL_TESTS
+       help
+         Tests for hw_breakpoint constraints accounting.
+
+         If unsure, say N.
+
 config TEST_UDELAY
        tristate "udelay test driver"
        help
--

2.37.0.rc0.161.g10f37bed90-goog

Quoted 87 lines · Marco Elver

Add KUnit test for hw_breakpoint constraints accounting, with various interesting mixes of breakpoint targets (some care was taken to catch interesting corner cases via bug-injection).

The test cannot be built as a module because it requires access to hw_breakpoint_slots(), which is not inlinable or exported on all architectures.

Signed-off-by Marco Elver <[email protected]>

---
v2:
* New patch.

---
 kernel/events/Makefile             |   1 +
 kernel/events/hw_breakpoint_test.c | 321 +++++++++++++++++++++++++++++
 lib/Kconfig.debug                  |  10 +
 3 files changed, 332 insertions(+)
 create mode 100644 kernel/events/hw_breakpoint_test.c

kernel/events/Makefile +1 -0

index 8591c180b52b..91a62f566743 100644
@@ -2,4 +2,5 @@
 obj-y := core.o ring_buffer.o callchain.o
 
 obj-$(CONFIG_HAVE_HW_BREAKPOINT) += hw_breakpoint.o
+obj-$(CONFIG_HW_BREAKPOINT_KUNIT_TEST) += hw_breakpoint_test.o
 obj-$(CONFIG_UPROBES) += uprobes.o

kernel/events/hw_breakpoint_test.c new file +51 -0

new file mode 100644
index 000000000000..747a0249a606
@@ -0,0 +1,321 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * KUnit test for hw_breakpoint constraints accounting logic.
+ *
+ * Copyright (C) 2022, Google LLC.
+ */
+
+#include <kunit/test.h>
+#include <linux/cpumask.h>
+#include <linux/hw_breakpoint.h>
+#include <linux/kthread.h>
+#include <linux/perf_event.h>
+#include <asm/hw_breakpoint.h>
+
+#define TEST_REQUIRES_BP_SLOTS(test, slots)                                            \
+       do {                                                                            \
+               if ((slots) > get_test_bp_slots()) {                                    \
+                       kunit_skip((test), "Requires breakpoint slots: %d > %d", slots, \
+                                  get_test_bp_slots());                                \
+               }                                                                       \
+       } while (0)
+
+#define TEST_EXPECT_NOSPC(expr) KUNIT_EXPECT_EQ(test, -ENOSPC, PTR_ERR(expr))
+
+#define MAX_TEST_BREAKPOINTS 512
+
+static char break_vars[MAX_TEST_BREAKPOINTS];
+static struct perf_event *test_bps[MAX_TEST_BREAKPOINTS];
+static struct task_struct *__other_task;
+
+static struct perf_event *register_test_bp(int cpu, struct task_struct *tsk, int idx)
+{
+       struct perf_event_attr attr = {};
+
+       if (WARN_ON(idx < 0 || idx >= MAX_TEST_BREAKPOINTS))
+               return NULL;
+
+       hw_breakpoint_init(&attr);
+       attr.bp_addr = (unsigned long)&break_vars[idx];
+       attr.bp_len = HW_BREAKPOINT_LEN_1;
+       attr.bp_type = HW_BREAKPOINT_RW;
+       return perf_event_create_kernel_counter(&attr, cpu, tsk, NULL, NULL);
+}
+
+static void unregister_test_bp(struct perf_event **bp)
+{
+       if (WARN_ON(IS_ERR(*bp)))
+               return;
+       if (WARN_ON(!*bp))
+               return;
+       unregister_hw_breakpoint(*bp);

kernel/events/hw_breakpoint_test.c line 57

Quoted 6 lines

kernel/events/hw_breakpoint_test.c new file +6 -0

+       *bp = NULL;
+}
+
+static int get_test_bp_slots(void)
+{
+       static int slots;

Why is this function needed? Is hw_breakpoint_slots() very slow?

Quoted 50 lines

kernel/events/hw_breakpoint_test.c new file +50 -0

+
+       if (!slots)
+               slots = hw_breakpoint_slots(TYPE_DATA);
+
+       return slots;
+}
+
+static void fill_one_bp_slot(struct kunit *test, int *id, int cpu, struct task_struct *tsk)
+{
+       struct perf_event *bp = register_test_bp(cpu, tsk, *id);
+
+       KUNIT_ASSERT_NOT_NULL(test, bp);
+       KUNIT_ASSERT_FALSE(test, IS_ERR(bp));
+       KUNIT_ASSERT_NULL(test, test_bps[*id]);
+       test_bps[(*id)++] = bp;
+}
+
+/*
+ * Fills up the given @cpu/@tsk with breakpoints, only leaving @skip slots free.
+ *
+ * Returns true if this can be called again, continuing at @id.
+ */
+static bool fill_bp_slots(struct kunit *test, int *id, int cpu, struct task_struct *tsk, int skip)
+{
+       for (int i = 0; i < get_test_bp_slots() - skip; ++i)
+               fill_one_bp_slot(test, id, cpu, tsk);
+
+       return *id + get_test_bp_slots() <= MAX_TEST_BREAKPOINTS;
+}
+
+static int dummy_kthread(void *arg)
+{
+       return 0;
+}
+
+static struct task_struct *get_other_task(struct kunit *test)
+{
+       struct task_struct *tsk;
+
+       if (__other_task)
+               return __other_task;
+
+       tsk = kthread_create(dummy_kthread, NULL, "hw_breakpoint_dummy_task");
+       KUNIT_ASSERT_FALSE(test, IS_ERR(tsk));
+       __other_task = tsk;
+       return __other_task;
+}
+
+static int get_other_cpu(void)
+{

kernel/events/hw_breakpoint_test.c line 111

Quoted 4 lines

kernel/events/hw_breakpoint_test.c new file +4 -0

+       int cpu;
+
+       for_each_online_cpu(cpu) {
+               if (cpu != raw_smp_processor_id())

Are we guaranteed to not be rescheduled in the middle of a test? If not, can't get_other_cpu() return the same CPU that was returned by raw_smp_processor_id() earlier in the test?

On a machine with 256 CPUs, running the recently added perf breakpoint benchmark results in:

 | $> perf bench -r 30 breakpoint thread -b 4 -p 64 -t 64
 | # Running 'breakpoint/thread' benchmark:
 | # Created/joined 30 threads with 4 breakpoints and 64 parallelism
 |      Total time: 236.418 [sec]
 |
 |   123134.794271 usecs/op
 |  7880626.833333 usecs/op/cpu

The benchmark tests inherited breakpoint perf events across many threads.

Looking at a perf profile, we can see that the majority of the time is spent in various hw_breakpoint.c functions, which execute within the 'nr_bp_mutex' critical sections which then results in contention on that mutex as well:

    37.27%  [kernel]       [k] osq_lock
    34.92%  [kernel]       [k] mutex_spin_on_owner
    12.15%  [kernel]       [k] toggle_bp_slot
    11.90%  [kernel]       [k] __reserve_bp_slot

The culprit here is task_bp_pinned(), which has a runtime complexity of O(#tasks) due to storing all task breakpoints in the same list and iterating through that list looking for a matching task. Clearly, this does not scale to thousands of tasks.

Instead, make use of the "rhashtable" variant "rhltable" which stores multiple items with the same key in a list. This results in average runtime complexity of O(1) for task_bp_pinned().

With the optimization, the benchmark shows:

 | $> perf bench -r 30 breakpoint thread -b 4 -p 64 -t 64
 | # Running 'breakpoint/thread' benchmark:
 | # Created/joined 30 threads with 4 breakpoints and 64 parallelism
 |      Total time: 0.208 [sec]
 |
 |      108.422396 usecs/op
 |     6939.033333 usecs/op/cpu

On this particular setup that's a speedup of ~1135x.

While one option would be to make task_struct a breakpoint list node, this would only further bloat task_struct for infrequently used data. Furthermore, after all optimizations in this series, there's no evidence it would result in better performance: later optimizations make the time spent looking up entries in the hash table negligible (we'll reach the theoretical ideal performance i.e. no constraints).

Signed-off-by Marco Elver <[email protected]>

---
v2:
* Commit message tweaks.

---
 include/linux/perf_event.h    |  3 +-
 kernel/events/hw_breakpoint.c | 56 ++++++++++++++++++++++-------------
 2 files changed, 37 insertions(+), 22 deletions(-)

include/linux/perf_event.h +2 -1

index 01231f1d976c..e27360436dc6 100644
@@ -36,6 +36,7 @@ struct perf_guest_info_callbacks {
 };
 
 #ifdef CONFIG_HAVE_HW_BREAKPOINT
+#include <linux/rhashtable-types.h>
 #include <asm/hw_breakpoint.h>
 #endif
 

@@ -178,7 +179,7 @@ struct hw_perf_event {
                         * creation and event initalization.
                         */
                        struct arch_hw_breakpoint       info;
-                       struct list_head                bp_list;
+                       struct rhlist_head              bp_list;
                };
 #endif
                struct { /* amd_iommu */

kernel/events/hw_breakpoint.c +29 -17

index 1b013968b395..add1b9c59631 100644
@@ -26,10 +26,10 @@
 #include <linux/irqflags.h>
 #include <linux/kdebug.h>
 #include <linux/kernel.h>
-#include <linux/list.h>
 #include <linux/mutex.h>
 #include <linux/notifier.h>
 #include <linux/percpu.h>
+#include <linux/rhashtable.h>
 #include <linux/sched.h>
 #include <linux/slab.h>
 

@@ -54,7 +54,13 @@ static struct bp_cpuinfo *get_bp_info(int cpu, enum bp_type_idx type)
 }
 
 /* Keep track of the breakpoints attached to tasks */
-static LIST_HEAD(bp_task_head);
+static struct rhltable task_bps_ht;
+static const struct rhashtable_params task_bps_ht_params = {
+       .head_offset = offsetof(struct hw_perf_event, bp_list),
+       .key_offset = offsetof(struct hw_perf_event, target),
+       .key_len = sizeof_field(struct hw_perf_event, target),
+       .automatic_shrinking = true,
+};
 
 static int constraints_initialized;
 

@@ -103,17 +109,23 @@ static unsigned int max_task_bp_pinned(int cpu, enum bp_type_idx type)
  */
 static int task_bp_pinned(int cpu, struct perf_event *bp, enum bp_type_idx type)
 {
-       struct task_struct *tsk = bp->hw.target;
+       struct rhlist_head *head, *pos;
        struct perf_event *iter;
        int count = 0;
 
-       list_for_each_entry(iter, &bp_task_head, hw.bp_list) {
-               if (iter->hw.target == tsk &&
-                   find_slot_idx(iter->attr.bp_type) == type &&
+       rcu_read_lock();
+       head = rhltable_lookup(&task_bps_ht, &bp->hw.target, task_bps_ht_params);
+       if (!head)
+               goto out;
+
+       rhl_for_each_entry_rcu(iter, pos, head, hw.bp_list) {
+               if (find_slot_idx(iter->attr.bp_type) == type &&
                    (iter->cpu < 0 || cpu == iter->cpu))
                        count += hw_breakpoint_weight(iter);
        }
 
+out:
+       rcu_read_unlock();
        return count;
 }
 

@@ -186,7 +198,7 @@ static void toggle_bp_task_slot(struct perf_event *bp, int cpu,
 /*
  * Add/remove the given breakpoint in our constraint table
  */
-static void
+static int
 toggle_bp_slot(struct perf_event *bp, bool enable, enum bp_type_idx type,
               int weight)
 {

@@ -199,7 +211,7 @@ toggle_bp_slot(struct perf_event *bp, bool enable, enum bp_type_idx type,
        /* Pinned counter cpu profiling */
        if (!bp->hw.target) {
                get_bp_info(bp->cpu, type)->cpu_pinned += weight;
-               return;
+               return 0;
        }
 
        /* Pinned counter task profiling */

@@ -207,9 +219,9 @@ toggle_bp_slot(struct perf_event *bp, bool enable, enum bp_type_idx type,
                toggle_bp_task_slot(bp, cpu, type, weight);
 
        if (enable)
-               list_add_tail(&bp->hw.bp_list, &bp_task_head);
+               return rhltable_insert(&task_bps_ht, &bp->hw.bp_list, task_bps_ht_params);
        else
-               list_del(&bp->hw.bp_list);
+               return rhltable_remove(&task_bps_ht, &bp->hw.bp_list, task_bps_ht_params);
 }
 
 __weak int arch_reserve_bp_slot(struct perf_event *bp)

@@ -307,9 +319,7 @@ static int __reserve_bp_slot(struct perf_event *bp, u64 bp_type)
        if (ret)
                return ret;
 
-       toggle_bp_slot(bp, true, type, weight);
-
-       return 0;
+       return toggle_bp_slot(bp, true, type, weight);
 }
 
 int reserve_bp_slot(struct perf_event *bp)

@@ -334,7 +344,7 @@ static void __release_bp_slot(struct perf_event *bp, u64 bp_type)
 
        type = find_slot_idx(bp_type);
        weight = hw_breakpoint_weight(bp);
-       toggle_bp_slot(bp, false, type, weight);
+       WARN_ON(toggle_bp_slot(bp, false, type, weight));
 }
 
 void release_bp_slot(struct perf_event *bp)

@@ -678,7 +688,7 @@ static struct pmu perf_breakpoint = {
 int __init init_hw_breakpoint(void)
 {
        int cpu, err_cpu;
-       int i;
+       int i, ret;
 
        for (i = 0; i < TYPE_MAX; i++)
                nr_slots[i] = hw_breakpoint_slots(i);

@@ -689,18 +699,24 @@ int __init init_hw_breakpoint(void)
 
                        info->tsk_pinned = kcalloc(nr_slots[i], sizeof(int),
                                                        GFP_KERNEL);
-                       if (!info->tsk_pinned)
-                               goto err_alloc;
+                       if (!info->tsk_pinned) {
+                               ret = -ENOMEM;
+                               goto err;
+                       }
                }
        }

kernel/events/hw_breakpoint.c +2 -5

- err_alloc:
+err:
        for_each_possible_cpu(err_cpu) {
                for (i = 0; i < TYPE_MAX; i++)
                        kfree(get_bp_info(err_cpu, i)->tsk_pinned);

@@ -708,7 +724,5 @@ int __init init_hw_breakpoint(void)
                        break;
        }
 
-       return -ENOMEM;
+       return ret;
 }
-
-
--

2.37.0.rc0.161.g10f37bed90-goog

Quoted 220 lines · Marco Elver

On a machine with 256 CPUs, running the recently added perf breakpoint benchmark results in:

 | $> perf bench -r 30 breakpoint thread -b 4 -p 64 -t 64
 | # Running 'breakpoint/thread' benchmark:
 | # Created/joined 30 threads with 4 breakpoints and 64 parallelism
 |      Total time: 236.418 [sec]
 |
 |   123134.794271 usecs/op
 |  7880626.833333 usecs/op/cpu

The benchmark tests inherited breakpoint perf events across many threads.

Looking at a perf profile, we can see that the majority of the time is spent in various hw_breakpoint.c functions, which execute within the 'nr_bp_mutex' critical sections which then results in contention on that mutex as well:

    37.27%  [kernel]       [k] osq_lock
    34.92%  [kernel]       [k] mutex_spin_on_owner
    12.15%  [kernel]       [k] toggle_bp_slot
    11.90%  [kernel]       [k] __reserve_bp_slot

The culprit here is task_bp_pinned(), which has a runtime complexity of O(#tasks) due to storing all task breakpoints in the same list and iterating through that list looking for a matching task. Clearly, this does not scale to thousands of tasks.

Instead, make use of the "rhashtable" variant "rhltable" which stores multiple items with the same key in a list. This results in average runtime complexity of O(1) for task_bp_pinned().

With the optimization, the benchmark shows:

 | $> perf bench -r 30 breakpoint thread -b 4 -p 64 -t 64
 | # Running 'breakpoint/thread' benchmark:
 | # Created/joined 30 threads with 4 breakpoints and 64 parallelism
 |      Total time: 0.208 [sec]
 |
 |      108.422396 usecs/op
 |     6939.033333 usecs/op/cpu

On this particular setup that's a speedup of ~1135x.

While one option would be to make task_struct a breakpoint list node, this would only further bloat task_struct for infrequently used data. Furthermore, after all optimizations in this series, there's no evidence it would result in better performance: later optimizations make the time spent looking up entries in the hash table negligible (we'll reach the theoretical ideal performance i.e. no constraints).

Signed-off-by Marco Elver <[email protected]>

---
v2:
* Commit message tweaks.

---
 include/linux/perf_event.h    |  3 +-
 kernel/events/hw_breakpoint.c | 56 ++++++++++++++++++++++-------------
 2 files changed, 37 insertions(+), 22 deletions(-)

include/linux/perf_event.h +2 -1

index 01231f1d976c..e27360436dc6 100644
@@ -36,6 +36,7 @@ struct perf_guest_info_callbacks {
 };
 
 #ifdef CONFIG_HAVE_HW_BREAKPOINT
+#include <linux/rhashtable-types.h>
 #include <asm/hw_breakpoint.h>
 #endif
 

@@ -178,7 +179,7 @@ struct hw_perf_event {
                         * creation and event initalization.
                         */
                        struct arch_hw_breakpoint       info;
-                       struct list_head                bp_list;
+                       struct rhlist_head              bp_list;
                };
 #endif
                struct { /* amd_iommu */

kernel/events/hw_breakpoint.c +33 -17

index 1b013968b395..add1b9c59631 100644
@@ -26,10 +26,10 @@
 #include <linux/irqflags.h>
 #include <linux/kdebug.h>
 #include <linux/kernel.h>
-#include <linux/list.h>
 #include <linux/mutex.h>
 #include <linux/notifier.h>
 #include <linux/percpu.h>
+#include <linux/rhashtable.h>
 #include <linux/sched.h>
 #include <linux/slab.h>
 

@@ -54,7 +54,13 @@ static struct bp_cpuinfo *get_bp_info(int cpu, enum bp_type_idx type)
 }
 
 /* Keep track of the breakpoints attached to tasks */
-static LIST_HEAD(bp_task_head);
+static struct rhltable task_bps_ht;
+static const struct rhashtable_params task_bps_ht_params = {
+       .head_offset = offsetof(struct hw_perf_event, bp_list),
+       .key_offset = offsetof(struct hw_perf_event, target),
+       .key_len = sizeof_field(struct hw_perf_event, target),
+       .automatic_shrinking = true,
+};
 
 static int constraints_initialized;
 

@@ -103,17 +109,23 @@ static unsigned int max_task_bp_pinned(int cpu, enum bp_type_idx type)
  */
 static int task_bp_pinned(int cpu, struct perf_event *bp, enum bp_type_idx type)
 {
-       struct task_struct *tsk = bp->hw.target;
+       struct rhlist_head *head, *pos;
        struct perf_event *iter;
        int count = 0;
 
-       list_for_each_entry(iter, &bp_task_head, hw.bp_list) {
-               if (iter->hw.target == tsk &&
-                   find_slot_idx(iter->attr.bp_type) == type &&
+       rcu_read_lock();
+       head = rhltable_lookup(&task_bps_ht, &bp->hw.target, task_bps_ht_params);
+       if (!head)
+               goto out;
+
+       rhl_for_each_entry_rcu(iter, pos, head, hw.bp_list) {
+               if (find_slot_idx(iter->attr.bp_type) == type &&
                    (iter->cpu < 0 || cpu == iter->cpu))
                        count += hw_breakpoint_weight(iter);
        }
 
+out:
+       rcu_read_unlock();
        return count;
 }
 

@@ -186,7 +198,7 @@ static void toggle_bp_task_slot(struct perf_event *bp, int cpu,
 /*
  * Add/remove the given breakpoint in our constraint table
  */
-static void
+static int
 toggle_bp_slot(struct perf_event *bp, bool enable, enum bp_type_idx type,
               int weight)
 {

@@ -199,7 +211,7 @@ toggle_bp_slot(struct perf_event *bp, bool enable, enum bp_type_idx type,
        /* Pinned counter cpu profiling */
        if (!bp->hw.target) {
                get_bp_info(bp->cpu, type)->cpu_pinned += weight;
-               return;
+               return 0;
        }
 
        /* Pinned counter task profiling */

@@ -207,9 +219,9 @@ toggle_bp_slot(struct perf_event *bp, bool enable, enum bp_type_idx type,
                toggle_bp_task_slot(bp, cpu, type, weight);
 
        if (enable)
-               list_add_tail(&bp->hw.bp_list, &bp_task_head);
+               return rhltable_insert(&task_bps_ht, &bp->hw.bp_list, task_bps_ht_params);
        else
-               list_del(&bp->hw.bp_list);
+               return rhltable_remove(&task_bps_ht, &bp->hw.bp_list, task_bps_ht_params);
 }
 
 __weak int arch_reserve_bp_slot(struct perf_event *bp)

@@ -307,9 +319,7 @@ static int __reserve_bp_slot(struct perf_event *bp, u64 bp_type)
        if (ret)
                return ret;
 
-       toggle_bp_slot(bp, true, type, weight);
-
-       return 0;
+       return toggle_bp_slot(bp, true, type, weight);
 }
 
 int reserve_bp_slot(struct perf_event *bp)

@@ -334,7 +344,7 @@ static void __release_bp_slot(struct perf_event *bp, u64 bp_type)
 
        type = find_slot_idx(bp_type);
        weight = hw_breakpoint_weight(bp);
-       toggle_bp_slot(bp, false, type, weight);
+       WARN_ON(toggle_bp_slot(bp, false, type, weight));
 }
 
 void release_bp_slot(struct perf_event *bp)

@@ -678,7 +688,7 @@ static struct pmu perf_breakpoint = {
 int __init init_hw_breakpoint(void)
 {
        int cpu, err_cpu;
-       int i;
+       int i, ret;
 
        for (i = 0; i < TYPE_MAX; i++)
                nr_slots[i] = hw_breakpoint_slots(i);

@@ -689,18 +699,24 @@ int __init init_hw_breakpoint(void)
 
                        info->tsk_pinned = kcalloc(nr_slots[i], sizeof(int),
                                                        GFP_KERNEL);
-                       if (!info->tsk_pinned)
-                               goto err_alloc;
+                       if (!info->tsk_pinned) {
+                               ret = -ENOMEM;
+                               goto err;
+                       }
                }
        }
 
+       ret = rhltable_init(&task_bps_ht, &task_bps_ht_params);
+       if (ret)
+               goto err;
+
        constraints_initialized = 1;
 

kernel/events/hw_breakpoint.c int __init init_hw_breakpoint(void) · line 717

Quoted 3 lines

kernel/events/hw_breakpoint.c +0 -0

        perf_pmu_register(&perf_breakpoint, "breakpoint", PERF_TYPE_BREAKPOINT);
 
        return register_die_notifier(&hw_breakpoint_exceptions_nb);

It seems there is a latent bug here:
if register_die_notifier() fails we also need to execute the err: label code.

Otherwise the patch looks good.

Reviewed-by Dmitry Vyukov <[email protected]>

Quoted 219 lines

Quoted 219 lines

On a machine with 256 CPUs, running the recently added perf breakpoint benchmark results in:

 | $> perf bench -r 30 breakpoint thread -b 4 -p 64 -t 64
 | # Running 'breakpoint/thread' benchmark:
 | # Created/joined 30 threads with 4 breakpoints and 64 parallelism
 |      Total time: 236.418 [sec]
 |
 |   123134.794271 usecs/op
 |  7880626.833333 usecs/op/cpu

The benchmark tests inherited breakpoint perf events across many threads.

Looking at a perf profile, we can see that the majority of the time is spent in various hw_breakpoint.c functions, which execute within the 'nr_bp_mutex' critical sections which then results in contention on that mutex as well:

    37.27%  [kernel]       [k] osq_lock
    34.92%  [kernel]       [k] mutex_spin_on_owner
    12.15%  [kernel]       [k] toggle_bp_slot
    11.90%  [kernel]       [k] __reserve_bp_slot

The culprit here is task_bp_pinned(), which has a runtime complexity of O(#tasks) due to storing all task breakpoints in the same list and iterating through that list looking for a matching task. Clearly, this does not scale to thousands of tasks.

Instead, make use of the "rhashtable" variant "rhltable" which stores multiple items with the same key in a list. This results in average runtime complexity of O(1) for task_bp_pinned().

With the optimization, the benchmark shows:

 | $> perf bench -r 30 breakpoint thread -b 4 -p 64 -t 64
 | # Running 'breakpoint/thread' benchmark:
 | # Created/joined 30 threads with 4 breakpoints and 64 parallelism
 |      Total time: 0.208 [sec]
 |
 |      108.422396 usecs/op
 |     6939.033333 usecs/op/cpu

On this particular setup that's a speedup of ~1135x.

While one option would be to make task_struct a breakpoint list node, this would only further bloat task_struct for infrequently used data. Furthermore, after all optimizations in this series, there's no evidence it would result in better performance: later optimizations make the time spent looking up entries in the hash table negligible (we'll reach the theoretical ideal performance i.e. no constraints).

Signed-off-by Marco Elver <[email protected]>

---
v2:
* Commit message tweaks.

---
 include/linux/perf_event.h    |  3 +-
 kernel/events/hw_breakpoint.c | 56 ++++++++++++++++++++++-------------
 2 files changed, 37 insertions(+), 22 deletions(-)

include/linux/perf_event.h +2 -1

index 01231f1d976c..e27360436dc6 100644
@@ -36,6 +36,7 @@ struct perf_guest_info_callbacks {
 };
 
 #ifdef CONFIG_HAVE_HW_BREAKPOINT
+#include <linux/rhashtable-types.h>
 #include <asm/hw_breakpoint.h>
 #endif
 

@@ -178,7 +179,7 @@ struct hw_perf_event {
                         * creation and event initalization.
                         */
                        struct arch_hw_breakpoint       info;
-                       struct list_head                bp_list;
+                       struct rhlist_head              bp_list;
                };
 #endif
                struct { /* amd_iommu */

kernel/events/hw_breakpoint.c +33 -17

index 1b013968b395..add1b9c59631 100644
@@ -26,10 +26,10 @@
 #include <linux/irqflags.h>
 #include <linux/kdebug.h>
 #include <linux/kernel.h>
-#include <linux/list.h>
 #include <linux/mutex.h>
 #include <linux/notifier.h>
 #include <linux/percpu.h>
+#include <linux/rhashtable.h>
 #include <linux/sched.h>
 #include <linux/slab.h>
 

@@ -54,7 +54,13 @@ static struct bp_cpuinfo *get_bp_info(int cpu, enum bp_type_idx type)
 }
 
 /* Keep track of the breakpoints attached to tasks */
-static LIST_HEAD(bp_task_head);
+static struct rhltable task_bps_ht;
+static const struct rhashtable_params task_bps_ht_params = {
+       .head_offset = offsetof(struct hw_perf_event, bp_list),
+       .key_offset = offsetof(struct hw_perf_event, target),
+       .key_len = sizeof_field(struct hw_perf_event, target),
+       .automatic_shrinking = true,
+};
 
 static int constraints_initialized;
 

@@ -103,17 +109,23 @@ static unsigned int max_task_bp_pinned(int cpu, enum bp_type_idx type)
  */
 static int task_bp_pinned(int cpu, struct perf_event *bp, enum bp_type_idx type)
 {
-       struct task_struct *tsk = bp->hw.target;
+       struct rhlist_head *head, *pos;
        struct perf_event *iter;
        int count = 0;
 
-       list_for_each_entry(iter, &bp_task_head, hw.bp_list) {
-               if (iter->hw.target == tsk &&
-                   find_slot_idx(iter->attr.bp_type) == type &&
+       rcu_read_lock();
+       head = rhltable_lookup(&task_bps_ht, &bp->hw.target, task_bps_ht_params);
+       if (!head)
+               goto out;
+
+       rhl_for_each_entry_rcu(iter, pos, head, hw.bp_list) {
+               if (find_slot_idx(iter->attr.bp_type) == type &&
                    (iter->cpu < 0 || cpu == iter->cpu))
                        count += hw_breakpoint_weight(iter);
        }
 
+out:
+       rcu_read_unlock();
        return count;
 }
 

@@ -186,7 +198,7 @@ static void toggle_bp_task_slot(struct perf_event *bp, int cpu,
 /*
  * Add/remove the given breakpoint in our constraint table
  */
-static void
+static int
 toggle_bp_slot(struct perf_event *bp, bool enable, enum bp_type_idx type,
               int weight)
 {

@@ -199,7 +211,7 @@ toggle_bp_slot(struct perf_event *bp, bool enable, enum bp_type_idx type,
        /* Pinned counter cpu profiling */
        if (!bp->hw.target) {
                get_bp_info(bp->cpu, type)->cpu_pinned += weight;
-               return;
+               return 0;
        }
 
        /* Pinned counter task profiling */

@@ -207,9 +219,9 @@ toggle_bp_slot(struct perf_event *bp, bool enable, enum bp_type_idx type,
                toggle_bp_task_slot(bp, cpu, type, weight);
 
        if (enable)
-               list_add_tail(&bp->hw.bp_list, &bp_task_head);
+               return rhltable_insert(&task_bps_ht, &bp->hw.bp_list, task_bps_ht_params);
        else
-               list_del(&bp->hw.bp_list);
+               return rhltable_remove(&task_bps_ht, &bp->hw.bp_list, task_bps_ht_params);
 }
 
 __weak int arch_reserve_bp_slot(struct perf_event *bp)

@@ -307,9 +319,7 @@ static int __reserve_bp_slot(struct perf_event *bp, u64 bp_type)
        if (ret)
                return ret;
 
-       toggle_bp_slot(bp, true, type, weight);
-
-       return 0;
+       return toggle_bp_slot(bp, true, type, weight);
 }
 
 int reserve_bp_slot(struct perf_event *bp)

@@ -334,7 +344,7 @@ static void __release_bp_slot(struct perf_event *bp, u64 bp_type)
 
        type = find_slot_idx(bp_type);
        weight = hw_breakpoint_weight(bp);
-       toggle_bp_slot(bp, false, type, weight);
+       WARN_ON(toggle_bp_slot(bp, false, type, weight));
 }
 
 void release_bp_slot(struct perf_event *bp)

@@ -678,7 +688,7 @@ static struct pmu perf_breakpoint = {
 int __init init_hw_breakpoint(void)
 {
        int cpu, err_cpu;
-       int i;
+       int i, ret;
 
        for (i = 0; i < TYPE_MAX; i++)
                nr_slots[i] = hw_breakpoint_slots(i);

@@ -689,18 +699,24 @@ int __init init_hw_breakpoint(void)
 
                        info->tsk_pinned = kcalloc(nr_slots[i], sizeof(int),
                                                        GFP_KERNEL);
-                       if (!info->tsk_pinned)
-                               goto err_alloc;
+                       if (!info->tsk_pinned) {
+                               ret = -ENOMEM;
+                               goto err;
+                       }
                }
        }
 
+       ret = rhltable_init(&task_bps_ht, &task_bps_ht_params);
+       if (ret)
+               goto err;
+
        constraints_initialized = 1;
 

Quoted 6 lines

kernel/events/hw_breakpoint.c int __init init_hw_breakpoint(void) · line 717

Quoted 3 lines

kernel/events/hw_breakpoint.c +0 -0

        perf_pmu_register(&perf_breakpoint, "breakpoint", PERF_TYPE_BREAKPOINT);
 
        return register_die_notifier(&hw_breakpoint_exceptions_nb);

It seems there is a latent bug here:
if register_die_notifier() fails we also need to execute the err: label code.

I think we should ignore it, because it's just a notifier when the kernel dies. I'd rather have working breakpoints (which we have if we made it to this point) when the kernel is live, and sacrifice some bad behaviour when the kernel dies.

Quoted 3 lines

Otherwise the patch looks good.

Reviewed-by Dmitry Vyukov <[email protected]>

Thanks,
-- Marco

Due to being a __weak function, hw_breakpoint_weight() will cause the compiler to always emit a call to it. This generates unnecessarily bad code (register spills etc.) for no good reason; in fact it appears in profiles of perf bench -r 100 breakpoint thread -b 4 -p 128 -t 512:

    ...
    0.70%  [kernel]       [k] hw_breakpoint_weight
    ...

While a small percentage, no architecture defines its own hw_breakpoint_weight() nor are there users outside hw_breakpoint.c, which makes the fact it is currently __weak a poor choice.

Change hw_breakpoint_weight()'s definition to follow a similar protocol to hw_breakpoint_slots(), such that if <asm/hw_breakpoint.h> defines hw_breakpoint_weight(), we'll use it instead.

The result is that it is inlined and no longer shows up in profiles.

Signed-off-by Marco Elver <[email protected]>

---
 include/linux/hw_breakpoint.h | 1 -
 kernel/events/hw_breakpoint.c | 4 +++-
 2 files changed, 3 insertions(+), 2 deletions(-)

include/linux/hw_breakpoint.h +0 -1

index 78dd7035d1e5..9fa3547acd87 100644
@@ -79,7 +79,6 @@ extern int dbg_reserve_bp_slot(struct perf_event *bp);
 extern int dbg_release_bp_slot(struct perf_event *bp);
 extern int reserve_bp_slot(struct perf_event *bp);
 extern void release_bp_slot(struct perf_event *bp);
-int hw_breakpoint_weight(struct perf_event *bp);
 int arch_reserve_bp_slot(struct perf_event *bp);
 void arch_release_bp_slot(struct perf_event *bp);
 void arch_unregister_hw_breakpoint(struct perf_event *bp);

kernel/events/hw_breakpoint.c +3 -2

index a089302ddf59..a124786e3ade 100644
@@ -124,10 +124,12 @@ static __init int init_breakpoint_slots(void)
 }
 #endif
 
-__weak int hw_breakpoint_weight(struct perf_event *bp)
+#ifndef hw_breakpoint_weight
+static inline int hw_breakpoint_weight(struct perf_event *bp)
 {
        return 1;
 }
+#endif
 
 static inline enum bp_type_idx find_slot_idx(u64 bp_type)
 {
--

2.37.0.rc0.161.g10f37bed90-goog

Flexible breakpoints have never been implemented, with bp_cpuinfo::flexible always being 0. Unfortunately, they still occupy 4 bytes in each bp_cpuinfo and bp_busy_slots, as well as computing the max flexible count in fetch_bp_busy_slots().

This again causes suboptimal code generation, when we always know that !!slots.flexible will be 0.

Just get rid of the flexible "placeholder" and remove all real code related to it. Make a note in the comment related to the constraints algorithm but don't remove them from the algorithm, so that if in future flexible breakpoints need supporting, it should be trivial to revive them (along with reverting this change).

Signed-off-by Marco Elver <[email protected]>

---
v2:
* Also remove struct bp_busy_slots, and simplify functions.

---
 kernel/events/hw_breakpoint.c | 57 +++++++++++------------------------
 1 file changed, 17 insertions(+), 40 deletions(-)

kernel/events/hw_breakpoint.c +17 -41

index a124786e3ade..63e39dc836bd 100644
@@ -45,8 +45,6 @@ struct bp_cpuinfo {
 #else
        unsigned int    *tsk_pinned;
 #endif
-       /* Number of non-pinned cpu/task breakpoints in a cpu */
-       unsigned int    flexible; /* XXX: placeholder, see fetch_this_slot() */
 };
 
 static DEFINE_PER_CPU(struct bp_cpuinfo, bp_cpuinfo[TYPE_MAX]);

@@ -67,12 +65,6 @@ static const struct rhashtable_params task_bps_ht_params = {
 
 static bool constraints_initialized __ro_after_init;
 
-/* Gather the number of total pinned and un-pinned bp in a cpuset */
-struct bp_busy_slots {
-       unsigned int pinned;
-       unsigned int flexible;
-};
-
 /* Serialize accesses to the above constraints */
 static DEFINE_MUTEX(nr_bp_mutex);
 

@@ -190,14 +182,14 @@ static const struct cpumask *cpumask_of_bp(struct perf_event *bp)
 }
 
 /*
- * Report the number of pinned/un-pinned breakpoints we have in
- * a given cpu (cpu > -1) or in all of them (cpu = -1).
+ * Returns the max pinned breakpoint slots in a given
+ * CPU (cpu > -1) or across all of them (cpu = -1).
  */
-static void
-fetch_bp_busy_slots(struct bp_busy_slots *slots, struct perf_event *bp,
-                   enum bp_type_idx type)
+static int
+max_bp_pinned_slots(struct perf_event *bp, enum bp_type_idx type)
 {
        const struct cpumask *cpumask = cpumask_of_bp(bp);
+       int pinned_slots = 0;
        int cpu;
 
        for_each_cpu(cpu, cpumask) {

@@ -210,24 +202,10 @@ fetch_bp_busy_slots(struct bp_busy_slots *slots, struct perf_event *bp,
                else
                        nr += task_bp_pinned(cpu, bp, type);
 
-               if (nr > slots->pinned)
-                       slots->pinned = nr;
-
-               nr = info->flexible;
-               if (nr > slots->flexible)
-                       slots->flexible = nr;
+               pinned_slots = max(nr, pinned_slots);
        }
-}
 
-/*
- * For now, continue to consider flexible as pinned, until we can
- * ensure no flexible event can ever be scheduled before a pinned event
- * in a same cpu.
- */
-static void
-fetch_this_slot(struct bp_busy_slots *slots, int weight)
-{
-       slots->pinned += weight;
+       return pinned_slots;
 }
 
 /*

@@ -298,7 +276,12 @@ __weak void arch_unregister_hw_breakpoint(struct perf_event *bp)
 }
 
 /*
- * Constraints to check before allowing this new breakpoint counter:
+ * Constraints to check before allowing this new breakpoint counter.
+ *
+ * Note: Flexible breakpoints are currently unimplemented, but outlined in the
+ * below algorithm for completeness.  The implementation treats flexible as
+ * pinned due to no guarantee that we currently always schedule flexible events
+ * before a pinned event in a same CPU.
  *
  *  == Non-pinned counter == (Considered as pinned for now)
  *

@@ -340,8 +323,8 @@ __weak void arch_unregister_hw_breakpoint(struct perf_event *bp)
  */
 static int __reserve_bp_slot(struct perf_event *bp, u64 bp_type)
 {
-       struct bp_busy_slots slots = {0};
        enum bp_type_idx type;
+       int max_pinned_slots;
        int weight;
        int ret;
 

@@ -357,15 +340,9 @@ static int __reserve_bp_slot(struct perf_event *bp, u64 bp_type)
        type = find_slot_idx(bp_type);
        weight = hw_breakpoint_weight(bp);
 
-       fetch_bp_busy_slots(&slots, bp, type);
-       /*
-        * Simulate the addition of this breakpoint to the constraints
-        * and see the result.
-        */
-       fetch_this_slot(&slots, weight);
-
-       /* Flexible counters need to keep at least one slot */
-       if (slots.pinned + (!!slots.flexible) > hw_breakpoint_slots_cached(type))
+       /* Check if this new breakpoint can be satisfied across all CPUs. */
+       max_pinned_slots = max_bp_pinned_slots(bp, type) + weight;
+       if (max_pinned_slots > hw_breakpoint_slots_cached(type))
                return -ENOSPC;
 
        ret = arch_reserve_bp_slot(bp);
--

2.37.0.rc0.161.g10f37bed90-goog

Internal data structures (cpu_bps, task_bps) of powerpc's hw_breakpoint implementation have relied on nr_bp_mutex serializing access to them.

Before overhauling synchronization of kernel/events/hw_breakpoint.c, introduce 2 spinlocks to synchronize cpu_bps and task_bps respectively, thus avoiding reliance on callers synchronizing powerpc's hw_breakpoint.

Reported-by Dmitry Vyukov <[email protected]>

Signed-off-by Marco Elver <[email protected]>

---
v2:
* New patch.

---
 arch/powerpc/kernel/hw_breakpoint.c | 53 ++++++++++++++++++++++-------
 1 file changed, 40 insertions(+), 13 deletions(-)

arch/powerpc/kernel/hw_breakpoint.c +40 -14

index 2669f80b3a49..8db1a15d7acb 100644
@@ -15,6 +15,7 @@
 #include <linux/kernel.h>
 #include <linux/sched.h>
 #include <linux/smp.h>
+#include <linux/spinlock.h>
 #include <linux/debugfs.h>
 #include <linux/init.h>
 

@@ -129,7 +130,14 @@ struct breakpoint {
        bool ptrace_bp;
 };
 
+/*
+ * While kernel/events/hw_breakpoint.c does its own synchronization, we cannot
+ * rely on it safely synchronizing internals here; however, we can rely on it
+ * not requesting more breakpoints than available.
+ */
+static DEFINE_SPINLOCK(cpu_bps_lock);
 static DEFINE_PER_CPU(struct breakpoint *, cpu_bps[HBP_NUM_MAX]);
+static DEFINE_SPINLOCK(task_bps_lock);
 static LIST_HEAD(task_bps);
 
 static struct breakpoint *alloc_breakpoint(struct perf_event *bp)

@@ -174,7 +182,9 @@ static int task_bps_add(struct perf_event *bp)
        if (IS_ERR(tmp))
                return PTR_ERR(tmp);
 
+       spin_lock(&task_bps_lock);
        list_add(&tmp->list, &task_bps);
+       spin_unlock(&task_bps_lock);
        return 0;
 }
 

@@ -182,6 +192,7 @@ static void task_bps_remove(struct perf_event *bp)
 {
        struct list_head *pos, *q;
 
+       spin_lock(&task_bps_lock);
        list_for_each_safe(pos, q, &task_bps) {
                struct breakpoint *tmp = list_entry(pos, struct breakpoint, list);
 

@@ -191,6 +202,7 @@ static void task_bps_remove(struct perf_event *bp)
                        break;
                }
        }
+       spin_unlock(&task_bps_lock);
 }
 
 /*

@@ -200,12 +212,17 @@ static void task_bps_remove(struct perf_event *bp)
 static bool all_task_bps_check(struct perf_event *bp)
 {
        struct breakpoint *tmp;
+       bool ret = false;
 
+       spin_lock(&task_bps_lock);
        list_for_each_entry(tmp, &task_bps, list) {
-               if (!can_co_exist(tmp, bp))
-                       return true;
+               if (!can_co_exist(tmp, bp)) {
+                       ret = true;
+                       break;
+               }
        }
-       return false;
+       spin_unlock(&task_bps_lock);
+       return ret;
 }
 
 /*

@@ -215,13 +232,18 @@ static bool all_task_bps_check(struct perf_event *bp)
 static bool same_task_bps_check(struct perf_event *bp)
 {
        struct breakpoint *tmp;
+       bool ret = false;
 
+       spin_lock(&task_bps_lock);
        list_for_each_entry(tmp, &task_bps, list) {
                if (tmp->bp->hw.target == bp->hw.target &&
-                   !can_co_exist(tmp, bp))
-                       return true;
+                   !can_co_exist(tmp, bp)) {
+                       ret = true;
+                       break;
+               }
        }
-       return false;
+       spin_unlock(&task_bps_lock);
+       return ret;
 }
 
 static int cpu_bps_add(struct perf_event *bp)

@@ -234,6 +256,7 @@ static int cpu_bps_add(struct perf_event *bp)
        if (IS_ERR(tmp))
                return PTR_ERR(tmp);
 
+       spin_lock(&cpu_bps_lock);
        cpu_bp = per_cpu_ptr(cpu_bps, bp->cpu);
        for (i = 0; i < nr_wp_slots(); i++) {
                if (!cpu_bp[i]) {

@@ -241,6 +264,7 @@ static int cpu_bps_add(struct perf_event *bp)
                        break;
                }
        }
+       spin_unlock(&cpu_bps_lock);
        return 0;
 }
 

@@ -249,6 +273,7 @@ static void cpu_bps_remove(struct perf_event *bp)
        struct breakpoint **cpu_bp;
        int i = 0;
 
+       spin_lock(&cpu_bps_lock);
        cpu_bp = per_cpu_ptr(cpu_bps, bp->cpu);
        for (i = 0; i < nr_wp_slots(); i++) {
                if (!cpu_bp[i])

@@ -260,19 +285,25 @@ static void cpu_bps_remove(struct perf_event *bp)
                        break;
                }
        }
+       spin_unlock(&cpu_bps_lock);
 }
 
 static bool cpu_bps_check(int cpu, struct perf_event *bp)
 {
        struct breakpoint **cpu_bp;
+       bool ret = false;
        int i;
 
+       spin_lock(&cpu_bps_lock);
        cpu_bp = per_cpu_ptr(cpu_bps, cpu);
        for (i = 0; i < nr_wp_slots(); i++) {
-               if (cpu_bp[i] && !can_co_exist(cpu_bp[i], bp))
-                       return true;
+               if (cpu_bp[i] && !can_co_exist(cpu_bp[i], bp)) {
+                       ret = true;
+                       break;
+               }
        }
-       return false;
+       spin_unlock(&cpu_bps_lock);
+       return ret;
 }
 
 static bool all_cpu_bps_check(struct perf_event *bp)

@@ -286,10 +317,6 @@ static bool all_cpu_bps_check(struct perf_event *bp)
        return false;
 }
 
-/*
- * We don't use any locks to serialize accesses to cpu_bps or task_bps
- * because are already inside nr_bp_mutex.
- */
 int arch_reserve_bp_slot(struct perf_event *bp)
 {
        int ret;
--

2.37.0.rc0.161.g10f37bed90-goog

Internal data structures (cpu_bps, task_bps) of powerpc's hw_breakpoint implementation have relied on nr_bp_mutex serializing access to them.

Before overhauling synchronization of kernel/events/hw_breakpoint.c, introduce 2 spinlocks to synchronize cpu_bps and task_bps respectively, thus avoiding reliance on callers synchronizing powerpc's hw_breakpoint.

Reported-by Dmitry Vyukov <[email protected]>

Signed-off-by Marco Elver <[email protected]>

---
v2:
* New patch.

---
  arch/powerpc/kernel/hw_breakpoint.c | 53 ++++++++++++++++++++++-------
  1 file changed, 40 insertions(+), 13 deletions(-)

arch/powerpc/kernel/hw_breakpoint.c +40 -13

index 2669f80b3a49..8db1a15d7acb 100644
@@ -15,6 +15,7 @@
  #include <linux/kernel.h>
  #include <linux/sched.h>
  #include <linux/smp.h>
+#include <linux/spinlock.h>
  #include <linux/debugfs.h>
  #include <linux/init.h>
 

@@ -129,7 +130,14 @@ struct breakpoint {
  	bool ptrace_bp;
  };
 
+/*
+ * While kernel/events/hw_breakpoint.c does its own synchronization, we cannot
+ * rely on it safely synchronizing internals here; however, we can rely on it
+ * not requesting more breakpoints than available.
+ */
+static DEFINE_SPINLOCK(cpu_bps_lock);
  static DEFINE_PER_CPU(struct breakpoint *, cpu_bps[HBP_NUM_MAX]);
+static DEFINE_SPINLOCK(task_bps_lock);
  static LIST_HEAD(task_bps);
 
  static struct breakpoint *alloc_breakpoint(struct perf_event *bp)

@@ -174,7 +182,9 @@ static int task_bps_add(struct perf_event *bp)
  	if (IS_ERR(tmp))
  		return PTR_ERR(tmp);
 
+	spin_lock(&task_bps_lock);
  	list_add(&tmp->list, &task_bps);
+	spin_unlock(&task_bps_lock);
  	return 0;
  }
 

@@ -182,6 +192,7 @@ static void task_bps_remove(struct perf_event *bp)
  {
  	struct list_head *pos, *q;
 
+	spin_lock(&task_bps_lock);
  	list_for_each_safe(pos, q, &task_bps) {
  		struct breakpoint *tmp = list_entry(pos, struct breakpoint, list);
 

@@ -191,6 +202,7 @@ static void task_bps_remove(struct perf_event *bp)
  			break;
  		}
  	}
+	spin_unlock(&task_bps_lock);
  }
 
  /*

@@ -200,12 +212,17 @@ static void task_bps_remove(struct perf_event *bp)
  static bool all_task_bps_check(struct perf_event *bp)
  {
  	struct breakpoint *tmp;
+	bool ret = false;
 
+	spin_lock(&task_bps_lock);
  	list_for_each_entry(tmp, &task_bps, list) {
-		if (!can_co_exist(tmp, bp))
-			return true;
+		if (!can_co_exist(tmp, bp)) {
+			ret = true;
+			break;
+		}
  	}
-	return false;
+	spin_unlock(&task_bps_lock);
+	return ret;
  }
 
  /*

@@ -215,13 +232,18 @@ static bool all_task_bps_check(struct perf_event *bp)
  static bool same_task_bps_check(struct perf_event *bp)
  {
  	struct breakpoint *tmp;
+	bool ret = false;
 
+	spin_lock(&task_bps_lock);
  	list_for_each_entry(tmp, &task_bps, list) {
  		if (tmp->bp->hw.target == bp->hw.target &&
-		    !can_co_exist(tmp, bp))
-			return true;
+		    !can_co_exist(tmp, bp)) {
+			ret = true;
+			break;
+		}
  	}
-	return false;
+	spin_unlock(&task_bps_lock);
+	return ret;
  }
 
  static int cpu_bps_add(struct perf_event *bp)

@@ -234,6 +256,7 @@ static int cpu_bps_add(struct perf_event *bp)
  	if (IS_ERR(tmp))
  		return PTR_ERR(tmp);
 
+	spin_lock(&cpu_bps_lock);
  	cpu_bp = per_cpu_ptr(cpu_bps, bp->cpu);
  	for (i = 0; i < nr_wp_slots(); i++) {
  		if (!cpu_bp[i]) {

@@ -241,6 +264,7 @@ static int cpu_bps_add(struct perf_event *bp)
  			break;
  		}
  	}
+	spin_unlock(&cpu_bps_lock);
  	return 0;
  }
 

@@ -249,6 +273,7 @@ static void cpu_bps_remove(struct perf_event *bp)
  	struct breakpoint **cpu_bp;
  	int i = 0;
 
+	spin_lock(&cpu_bps_lock);
  	cpu_bp = per_cpu_ptr(cpu_bps, bp->cpu);
  	for (i = 0; i < nr_wp_slots(); i++) {
  		if (!cpu_bp[i])

@@ -260,19 +285,25 @@ static void cpu_bps_remove(struct perf_event *bp)
  			break;
  		}
  	}
+	spin_unlock(&cpu_bps_lock);
  }
 
  static bool cpu_bps_check(int cpu, struct perf_event *bp)
  {
  	struct breakpoint **cpu_bp;
+	bool ret = false;
  	int i;
 
+	spin_lock(&cpu_bps_lock);
  	cpu_bp = per_cpu_ptr(cpu_bps, cpu);
  	for (i = 0; i < nr_wp_slots(); i++) {
-		if (cpu_bp[i] && !can_co_exist(cpu_bp[i], bp))
-			return true;
+		if (cpu_bp[i] && !can_co_exist(cpu_bp[i], bp)) {
+			ret = true;
+			break;
+		}
  	}
-	return false;
+	spin_unlock(&cpu_bps_lock);
+	return ret;
  }
 
  static bool all_cpu_bps_check(struct perf_event *bp)

@@ -286,10 +317,6 @@ static bool all_cpu_bps_check(struct perf_event *bp)
  	return false;
  }
 
-/*
- * We don't use any locks to serialize accesses to cpu_bps or task_bps
- * because are already inside nr_bp_mutex.
- */
  int arch_reserve_bp_slot(struct perf_event *bp)
  {
  	int ret;

Hi Marco,

Quoted 6 lines · Marco Elver

Internal data structures (cpu_bps, task_bps) of powerpc's hw_breakpoint implementation have relied on nr_bp_mutex serializing access to them.

Before overhauling synchronization of kernel/events/hw_breakpoint.c, introduce 2 spinlocks to synchronize cpu_bps and task_bps respectively, thus avoiding reliance on callers synchronizing powerpc's hw_breakpoint.

We have an still opened old issue in our database related to hw_breakpoint, I was wondering if it could have any link with the changes you are doing and whether you could handle it at the same time.

https://github.com/linuxppc/issues/issues/38

Maybe it is completely unrelated, but as your series modifies only powerpc and as the issue says that powerpc is the only one to do that, I thought it might be worth a hand up.

Quoted 15 lines · Christophe Leroy

Hi Marco,

Quoted 6 lines · Marco Elver

Internal data structures (cpu_bps, task_bps) of powerpc's hw_breakpoint implementation have relied on nr_bp_mutex serializing access to them.

Before overhauling synchronization of kernel/events/hw_breakpoint.c, introduce 2 spinlocks to synchronize cpu_bps and task_bps respectively, thus avoiding reliance on callers synchronizing powerpc's hw_breakpoint.

We have an still opened old issue in our database related to hw_breakpoint, I was wondering if it could have any link with the changes you are doing and whether you could handle it at the same time.

Quoted 5 lines

https://github.com/linuxppc/issues/issues/38

Maybe it is completely unrelated, but as your series modifies only powerpc and as the issue says that powerpc is the only one to do that, I thought it might be worth a hand up.

I see the powerpc issue unrelated to the optimizations in this series; perhaps by fixing the powerpc issue, it would also become more optimal. But all I saw is that it just so happens that powerpc relied on the nr_bp_mutex which is going away.

This series will become even more complex if I decided to add a powerpc rework on top (notwithstanding the fact I don't have any ppc hardware at my disposal either). A separate series/patch seems much more appropriate.

Implement simple accessors to probe percpu-rwsem's locked state:
percpu_is_write_locked(), percpu_is_read_locked().

Signed-off-by Marco Elver <[email protected]>

---
v2:
* New patch.

---
 include/linux/percpu-rwsem.h  | 6 ++++++
 kernel/locking/percpu-rwsem.c | 6 ++++++
 2 files changed, 12 insertions(+)

include/linux/percpu-rwsem.h +6 -0

index 5fda40f97fe9..36b942b67b7d 100644
@@ -121,9 +121,15 @@ static inline void percpu_up_read(struct percpu_rw_semaphore *sem)
        preempt_enable();
 }
 
+extern bool percpu_is_read_locked(struct percpu_rw_semaphore *);
 extern void percpu_down_write(struct percpu_rw_semaphore *);
 extern void percpu_up_write(struct percpu_rw_semaphore *);
 
+static inline bool percpu_is_write_locked(struct percpu_rw_semaphore *sem)
+{
+       return atomic_read(&sem->block);
+}
+
 extern int __percpu_init_rwsem(struct percpu_rw_semaphore *,
                                const char *, struct lock_class_key *);
 

kernel/locking/percpu-rwsem.c +6 -1

index 5fe4c5495ba3..213d114fb025 100644
@@ -192,6 +192,12 @@ EXPORT_SYMBOL_GPL(__percpu_down_read);
        __sum;                                                          \
 })
 
+bool percpu_is_read_locked(struct percpu_rw_semaphore *sem)
+{
+       return per_cpu_sum(*sem->read_count) != 0;
+}
+EXPORT_SYMBOL_GPL(percpu_is_read_locked);
+
 /*
  * Return true if the modular sum of the sem->read_count per-CPU variable is
  * zero.  If this sum is zero, then it is stable due to the fact that if any
--

2.37.0.rc0.161.g10f37bed90-goog

While optimizing task_bp_pinned()'s runtime complexity to O(1) on average helps reduce time spent in the critical section, we still suffer due to serializing everything via 'nr_bp_mutex'. Indeed, a profile shows that now contention is the biggest issue:

    95.93%  [kernel]       [k] osq_lock
     0.70%  [kernel]       [k] mutex_spin_on_owner
     0.22%  [kernel]       [k] smp_cfm_core_cond
     0.18%  [kernel]       [k] task_bp_pinned
     0.18%  [kernel]       [k] rhashtable_jhash2
     0.15%  [kernel]       [k] queued_spin_lock_slowpath

when running the breakpoint benchmark with (system with 256 CPUs):

 | $> perf bench -r 30 breakpoint thread -b 4 -p 64 -t 64
 | # Running 'breakpoint/thread' benchmark:
 | # Created/joined 30 threads with 4 breakpoints and 64 parallelism
 |      Total time: 0.207 [sec]
 |
 |      108.267188 usecs/op
 |     6929.100000 usecs/op/cpu

The main concern for synchronizing the breakpoint constraints data is that a consistent snapshot of the per-CPU and per-task data is observed.

The access pattern is as follows:

1. If the target is a task: the task's pinned breakpoints are counted, checked for space, and then appended to; only bp_cpuinfo::cpu_pinned is used to check for conflicts with CPU-only breakpoints; bp_cpuinfo::tsk_pinned are incremented/decremented, but otherwise unused.

2. If the target is a CPU: bp_cpuinfo::cpu_pinned are counted, along with bp_cpuinfo::tsk_pinned; after a successful check, cpu_pinned is incremented. No per-task breakpoints are checked.

Since rhltable safely synchronizes insertions/deletions, we can allow concurrency as follows:

1. If the target is a task: independent tasks may update and check the constraints concurrently, but same-task target calls need to be serialized; since bp_cpuinfo::tsk_pinned is only updated, but not checked, these modifications can happen concurrently by switching tsk_pinned to atomic_t.

2. If the target is a CPU: access to the per-CPU constraints needs to be serialized with other CPU-target and task-target callers (to stabilize the bp_cpuinfo::tsk_pinned snapshot).

We can allow the above concurrency by introducing a per-CPU constraints data reader-writer lock (bp_cpuinfo_sem), and per-task mutexes (reuses task_struct::perf_event_mutex):

1. If the target is a task: acquires perf_event_mutex, and acquires bp_cpuinfo_sem as a reader. The choice of percpu-rwsem minimizes contention in the presence of many read-lock but few write-lock
acquisitions: we assume many orders of magnitude more task target breakpoints creations/destructions than CPU target breakpoints.

2. If the target is a CPU: acquires bp_cpuinfo_sem as a writer.

With these changes, contention with thousands of tasks is reduced to the point where waiting on locking no longer dominates the profile:

 | $> perf bench -r 30 breakpoint thread -b 4 -p 64 -t 64
 | # Running 'breakpoint/thread' benchmark:
 | # Created/joined 30 threads with 4 breakpoints and 64 parallelism
 |      Total time: 0.077 [sec]
 |
 |       40.201563 usecs/op
 |     2572.900000 usecs/op/cpu

    21.54%  [kernel]       [k] task_bp_pinned
    20.18%  [kernel]       [k] rhashtable_jhash2
     6.81%  [kernel]       [k] toggle_bp_slot
     5.47%  [kernel]       [k] queued_spin_lock_slowpath
     3.75%  [kernel]       [k] smp_cfm_core_cond
     3.48%  [kernel]       [k] bcmp

On this particular setup that's a speedup of 2.7x.

We're also getting closer to the theoretical ideal performance through optimizations in hw_breakpoint.c -- constraints accounting disabled:

 | perf bench -r 30 breakpoint thread -b 4 -p 64 -t 64
 | # Running 'breakpoint/thread' benchmark:
 | # Created/joined 30 threads with 4 breakpoints and 64 parallelism
 |      Total time: 0.067 [sec]
 |
 |       35.286458 usecs/op
 |     2258.333333 usecs/op/cpu

Which means the current implementation is ~12% slower than the theoretical ideal.

For reference, performance without any breakpoints:

 | $> bench -r 30 breakpoint thread -b 0 -p 64 -t 64
 | # Running 'breakpoint/thread' benchmark:
 | # Created/joined 30 threads with 0 breakpoints and 64 parallelism
 |      Total time: 0.060 [sec]
 |
 |       31.365625 usecs/op
 |     2007.400000 usecs/op/cpu

On a system with 256 CPUs, the theoretical ideal is only ~12% slower than no breakpoints at all; the current implementation is ~28% slower.

Signed-off-by Marco Elver <[email protected]>

---
v2:
* Use percpu-rwsem instead of rwlock.
* Use task_struct::perf_event_mutex. See code comment for reasoning. ==> Speedup of 2.7x (vs 2.5x in v1).

---
 kernel/events/hw_breakpoint.c | 159 ++++++++++++++++++++++++++++------
 1 file changed, 132 insertions(+), 27 deletions(-)

kernel/events/hw_breakpoint.c +132 -28

index 63e39dc836bd..128ba3429223 100644
@@ -19,6 +19,7 @@
 
 #include <linux/hw_breakpoint.h>
 
+#include <linux/atomic.h>
 #include <linux/bug.h>
 #include <linux/cpu.h>
 #include <linux/export.h>

@@ -28,6 +29,7 @@
 #include <linux/kernel.h>
 #include <linux/mutex.h>
 #include <linux/notifier.h>
+#include <linux/percpu-rwsem.h>
 #include <linux/percpu.h>
 #include <linux/rhashtable.h>
 #include <linux/sched.h>

@@ -41,9 +43,9 @@ struct bp_cpuinfo {
        unsigned int    cpu_pinned;
        /* tsk_pinned[n] is the number of tasks having n+1 breakpoints */
 #ifdef hw_breakpoint_slots
-       unsigned int    tsk_pinned[hw_breakpoint_slots(0)];
+       atomic_t        tsk_pinned[hw_breakpoint_slots(0)];
 #else
-       unsigned int    *tsk_pinned;
+       atomic_t        *tsk_pinned;
 #endif
 };
 

@@ -65,8 +67,79 @@ static const struct rhashtable_params task_bps_ht_params = {
 
 static bool constraints_initialized __ro_after_init;
 
-/* Serialize accesses to the above constraints */
-static DEFINE_MUTEX(nr_bp_mutex);
+/*
+ * Synchronizes accesses to the per-CPU constraints; the locking rules are:
+ *
+ *  1. Atomic updates to bp_cpuinfo::tsk_pinned only require a held read-lock
+ *     (due to bp_slots_histogram::count being atomic, no update are lost).
+ *
+ *  2. Holding a write-lock is required for computations that require a
+ *     stable snapshot of all bp_cpuinfo::tsk_pinned.
+ *
+ *  3. In all other cases, non-atomic accesses require the appropriately held
+ *     lock (read-lock for read-only accesses; write-lock for reads/writes).
+ */
+DEFINE_STATIC_PERCPU_RWSEM(bp_cpuinfo_sem);
+
+/*
+ * Return mutex to serialize accesses to per-task lists in task_bps_ht. Since
+ * rhltable synchronizes concurrent insertions/deletions, independent tasks may
+ * insert/delete concurrently; therefore, a mutex per task is sufficient.
+ *
+ * Uses task_struct::perf_event_mutex, to avoid extending task_struct with a
+ * hw_breakpoint-only mutex, which may be infrequently used. The caveat here is
+ * that hw_breakpoint may contend with per-task perf event list management. The
+ * assumption is that perf usecases involving hw_breakpoints are very unlikely
+ * to result in unnecessary contention.
+ */
+static inline struct mutex *get_task_bps_mutex(struct perf_event *bp)
+{
+       struct task_struct *tsk = bp->hw.target;
+
+       return tsk ? &tsk->perf_event_mutex : NULL;
+}
+
+static struct mutex *bp_constraints_lock(struct perf_event *bp)
+{
+       struct mutex *tsk_mtx = get_task_bps_mutex(bp);
+
+       if (tsk_mtx) {
+               mutex_lock(tsk_mtx);
+               percpu_down_read(&bp_cpuinfo_sem);
+       } else {
+               percpu_down_write(&bp_cpuinfo_sem);
+       }
+
+       return tsk_mtx;
+}
+
+static void bp_constraints_unlock(struct mutex *tsk_mtx)
+{
+       if (tsk_mtx) {
+               percpu_up_read(&bp_cpuinfo_sem);
+               mutex_unlock(tsk_mtx);
+       } else {
+               percpu_up_write(&bp_cpuinfo_sem);
+       }
+}
+
+static bool bp_constraints_is_locked(struct perf_event *bp)
+{
+       struct mutex *tsk_mtx = get_task_bps_mutex(bp);
+
+       return percpu_is_write_locked(&bp_cpuinfo_sem) ||
+              (tsk_mtx ? mutex_is_locked(tsk_mtx) :
+                         percpu_is_read_locked(&bp_cpuinfo_sem));
+}
+
+static inline void assert_bp_constraints_lock_held(struct perf_event *bp)
+{
+       struct mutex *tsk_mtx = get_task_bps_mutex(bp);
+
+       if (tsk_mtx)
+               lockdep_assert_held(tsk_mtx);
+       lockdep_assert_held(&bp_cpuinfo_sem);
+}
 
 #ifdef hw_breakpoint_slots
 /*

@@ -97,7 +170,7 @@ static __init int init_breakpoint_slots(void)
                for (i = 0; i < TYPE_MAX; i++) {
                        struct bp_cpuinfo *info = get_bp_info(cpu, i);
 
-                       info->tsk_pinned = kcalloc(__nr_bp_slots[i], sizeof(int), GFP_KERNEL);
+                       info->tsk_pinned = kcalloc(__nr_bp_slots[i], sizeof(atomic_t), GFP_KERNEL);
                        if (!info->tsk_pinned)
                                goto err;
                }

@@ -137,11 +210,19 @@ static inline enum bp_type_idx find_slot_idx(u64 bp_type)
  */
 static unsigned int max_task_bp_pinned(int cpu, enum bp_type_idx type)
 {
-       unsigned int *tsk_pinned = get_bp_info(cpu, type)->tsk_pinned;
+       atomic_t *tsk_pinned = get_bp_info(cpu, type)->tsk_pinned;
        int i;
 
+       /*
+        * At this point we want to have acquired the bp_cpuinfo_sem as a
+        * writer to ensure that there are no concurrent writers in
+        * toggle_bp_task_slot() to tsk_pinned, and we get a stable snapshot.
+        */
+       lockdep_assert_held_write(&bp_cpuinfo_sem);
+
        for (i = hw_breakpoint_slots_cached(type) - 1; i >= 0; i--) {
-               if (tsk_pinned[i] > 0)
+               ASSERT_EXCLUSIVE_WRITER(tsk_pinned[i]); /* Catch unexpected writers. */
+               if (atomic_read(&tsk_pinned[i]) > 0)
                        return i + 1;
        }
 

@@ -158,6 +239,11 @@ static int task_bp_pinned(int cpu, struct perf_event *bp, enum bp_type_idx type)
        struct perf_event *iter;
        int count = 0;
 
+       /*
+        * We need a stable snapshot of the per-task breakpoint list.
+        */
+       assert_bp_constraints_lock_held(bp);
+
        rcu_read_lock();
        head = rhltable_lookup(&task_bps_ht, &bp->hw.target, task_bps_ht_params);
        if (!head)

@@ -214,16 +300,25 @@ max_bp_pinned_slots(struct perf_event *bp, enum bp_type_idx type)
 static void toggle_bp_task_slot(struct perf_event *bp, int cpu,
                                enum bp_type_idx type, int weight)
 {
-       unsigned int *tsk_pinned = get_bp_info(cpu, type)->tsk_pinned;
+       atomic_t *tsk_pinned = get_bp_info(cpu, type)->tsk_pinned;
        int old_idx, new_idx;
 
+       /*
+        * If bp->hw.target, tsk_pinned is only modified, but not used
+        * otherwise. We can permit concurrent updates as long as there are no
+        * other uses: having acquired bp_cpuinfo_sem as a reader allows
+        * concurrent updates here. Uses of tsk_pinned will require acquiring
+        * bp_cpuinfo_sem as a writer to stabilize tsk_pinned's value.
+        */
+       lockdep_assert_held_read(&bp_cpuinfo_sem);
+
        old_idx = task_bp_pinned(cpu, bp, type) - 1;
        new_idx = old_idx + weight;
 
        if (old_idx >= 0)
-               tsk_pinned[old_idx]--;
+               atomic_dec(&tsk_pinned[old_idx]);
        if (new_idx >= 0)
-               tsk_pinned[new_idx]++;
+               atomic_inc(&tsk_pinned[new_idx]);
 }
 
 /*

@@ -241,6 +336,7 @@ toggle_bp_slot(struct perf_event *bp, bool enable, enum bp_type_idx type,
 
        /* Pinned counter cpu profiling */
        if (!bp->hw.target) {
+               lockdep_assert_held_write(&bp_cpuinfo_sem);
                get_bp_info(bp->cpu, type)->cpu_pinned += weight;
                return 0;
        }

@@ -249,6 +345,11 @@ toggle_bp_slot(struct perf_event *bp, bool enable, enum bp_type_idx type,
        for_each_cpu(cpu, cpumask)
                toggle_bp_task_slot(bp, cpu, type, weight);
 
+       /*
+        * Readers want a stable snapshot of the per-task breakpoint list.
+        */
+       assert_bp_constraints_lock_held(bp);
+
        if (enable)
                return rhltable_insert(&task_bps_ht, &bp->hw.bp_list, task_bps_ht_params);
        else

@@ -354,14 +455,10 @@ static int __reserve_bp_slot(struct perf_event *bp, u64 bp_type)
 
 int reserve_bp_slot(struct perf_event *bp)
 {
-       int ret;
-
-       mutex_lock(&nr_bp_mutex);
-
-       ret = __reserve_bp_slot(bp, bp->attr.bp_type);
-
-       mutex_unlock(&nr_bp_mutex);
+       struct mutex *mtx = bp_constraints_lock(bp);
+       int ret = __reserve_bp_slot(bp, bp->attr.bp_type);
 
+       bp_constraints_unlock(mtx);
        return ret;
 }
 

@@ -379,12 +476,11 @@ static void __release_bp_slot(struct perf_event *bp, u64 bp_type)
 
 void release_bp_slot(struct perf_event *bp)
 {
-       mutex_lock(&nr_bp_mutex);
+       struct mutex *mtx = bp_constraints_lock(bp);
 
        arch_unregister_hw_breakpoint(bp);
        __release_bp_slot(bp, bp->attr.bp_type);
-
-       mutex_unlock(&nr_bp_mutex);
+       bp_constraints_unlock(mtx);
 }
 
 static int __modify_bp_slot(struct perf_event *bp, u64 old_type, u64 new_type)

@@ -411,11 +507,10 @@ static int __modify_bp_slot(struct perf_event *bp, u64 old_type, u64 new_type)
 
 static int modify_bp_slot(struct perf_event *bp, u64 old_type, u64 new_type)
 {
-       int ret;
+       struct mutex *mtx = bp_constraints_lock(bp);
+       int ret = __modify_bp_slot(bp, old_type, new_type);
 
-       mutex_lock(&nr_bp_mutex);
-       ret = __modify_bp_slot(bp, old_type, new_type);
-       mutex_unlock(&nr_bp_mutex);
+       bp_constraints_unlock(mtx);
        return ret;
 }
 

@@ -426,18 +521,28 @@ static int modify_bp_slot(struct perf_event *bp, u64 old_type, u64 new_type)
  */
 int dbg_reserve_bp_slot(struct perf_event *bp)
 {
-       if (mutex_is_locked(&nr_bp_mutex))
+       int ret;
+
+       if (bp_constraints_is_locked(bp))
                return -1;
 
-       return __reserve_bp_slot(bp, bp->attr.bp_type);
+       /* Locks aren't held; disable lockdep assert checking. */
+       lockdep_off();
+       ret = __reserve_bp_slot(bp, bp->attr.bp_type);
+       lockdep_on();
+
+       return ret;
 }
 
 int dbg_release_bp_slot(struct perf_event *bp)
 {
-       if (mutex_is_locked(&nr_bp_mutex))
+       if (bp_constraints_is_locked(bp))
                return -1;
 
+       /* Locks aren't held; disable lockdep assert checking. */
+       lockdep_off();
        __release_bp_slot(bp, bp->attr.bp_type);
+       lockdep_on();
 
        return 0;
 }
--

2.37.0.rc0.161.g10f37bed90-goog

Factor out the existing atomic_t count[N] into its own struct called 'bp_slots_histogram', to generalize and make its intent clearer in preparation of reusing elsewhere. The basic idea of bucketing "total uses of N slots" resembles a histogram, so calling it such seems most intuitive.

No functional change.

Signed-off-by Marco Elver <[email protected]>

---
v2:
* New patch.

---
 kernel/events/hw_breakpoint.c | 94 +++++++++++++++++++++++------------
 1 file changed, 62 insertions(+), 32 deletions(-)

kernel/events/hw_breakpoint.c +62 -33

index 128ba3429223..18886f115abc 100644
@@ -36,19 +36,27 @@
 #include <linux/slab.h>
 
 /*
- * Constraints data
+ * Datastructure to track the total uses of N slots across tasks or CPUs;
+ * bp_slots_histogram::count[N] is the number of assigned N+1 breakpoint slots.
  */
-struct bp_cpuinfo {
-       /* Number of pinned cpu breakpoints in a cpu */
-       unsigned int    cpu_pinned;
-       /* tsk_pinned[n] is the number of tasks having n+1 breakpoints */
+struct bp_slots_histogram {
 #ifdef hw_breakpoint_slots
-       atomic_t        tsk_pinned[hw_breakpoint_slots(0)];
+       atomic_t count[hw_breakpoint_slots(0)];
 #else
-       atomic_t        *tsk_pinned;
+       atomic_t *count;
 #endif
 };
 
+/*
+ * Per-CPU constraints data.
+ */
+struct bp_cpuinfo {
+       /* Number of pinned CPU breakpoints in a CPU. */
+       unsigned int                    cpu_pinned;
+       /* Histogram of pinned task breakpoints in a CPU. */
+       struct bp_slots_histogram       tsk_pinned;
+};
+
 static DEFINE_PER_CPU(struct bp_cpuinfo, bp_cpuinfo[TYPE_MAX]);
 
 static struct bp_cpuinfo *get_bp_info(int cpu, enum bp_type_idx type)

@@ -159,6 +167,18 @@ static inline int hw_breakpoint_slots_cached(int type)
        return __nr_bp_slots[type];
 }
 
+static __init bool
+bp_slots_histogram_alloc(struct bp_slots_histogram *hist, enum bp_type_idx type)
+{
+       hist->count = kcalloc(hw_breakpoint_slots_cached(type), sizeof(*hist->count), GFP_KERNEL);
+       return hist->count;
+}
+
+static __init void bp_slots_histogram_free(struct bp_slots_histogram *hist)
+{
+       kfree(hist->count);
+}
+
 static __init int init_breakpoint_slots(void)
 {
        int i, cpu, err_cpu;

@@ -170,8 +190,7 @@ static __init int init_breakpoint_slots(void)
                for (i = 0; i < TYPE_MAX; i++) {
                        struct bp_cpuinfo *info = get_bp_info(cpu, i);
 
-                       info->tsk_pinned = kcalloc(__nr_bp_slots[i], sizeof(atomic_t), GFP_KERNEL);
-                       if (!info->tsk_pinned)
+                       if (!bp_slots_histogram_alloc(&info->tsk_pinned, i))
                                goto err;
                }
        }

@@ -180,7 +199,7 @@ static __init int init_breakpoint_slots(void)
 err:
        for_each_possible_cpu(err_cpu) {
                for (i = 0; i < TYPE_MAX; i++)
-                       kfree(get_bp_info(err_cpu, i)->tsk_pinned);
+                       bp_slots_histogram_free(&get_bp_info(err_cpu, i)->tsk_pinned);
                if (err_cpu == cpu)
                        break;
        }

@@ -189,6 +208,34 @@ static __init int init_breakpoint_slots(void)
 }
 #endif
 
+static inline void
+bp_slots_histogram_add(struct bp_slots_histogram *hist, int old, int val)
+{
+       const int old_idx = old - 1;
+       const int new_idx = old_idx + val;
+
+       if (old_idx >= 0)
+               atomic_dec(&hist->count[old_idx]);
+       if (new_idx >= 0)
+               atomic_inc(&hist->count[new_idx]);
+}
+
+static int
+bp_slots_histogram_max(struct bp_slots_histogram *hist, enum bp_type_idx type)
+{
+       for (int i = hw_breakpoint_slots_cached(type) - 1; i >= 0; i--) {
+               const int count = atomic_read(&hist->count[i]);
+
+               /* Catch unexpected writers; we want a stable snapshot. */
+               ASSERT_EXCLUSIVE_WRITER(hist->count[i]);
+               if (count > 0)
+                       return i + 1;
+               WARN(count < 0, "inconsistent breakpoint slots histogram");
+       }
+
+       return 0;
+}
+
 #ifndef hw_breakpoint_weight
 static inline int hw_breakpoint_weight(struct perf_event *bp)
 {

@@ -205,13 +252,11 @@ static inline enum bp_type_idx find_slot_idx(u64 bp_type)
 }
 
 /*
- * Report the maximum number of pinned breakpoints a task
- * have in this cpu
+ * Return the maximum number of pinned breakpoints a task has in this CPU.
  */
 static unsigned int max_task_bp_pinned(int cpu, enum bp_type_idx type)
 {
-       atomic_t *tsk_pinned = get_bp_info(cpu, type)->tsk_pinned;
-       int i;
+       struct bp_slots_histogram *tsk_pinned = &get_bp_info(cpu, type)->tsk_pinned;
 
        /*
         * At this point we want to have acquired the bp_cpuinfo_sem as a

@@ -219,14 +264,7 @@ static unsigned int max_task_bp_pinned(int cpu, enum bp_type_idx type)
         * toggle_bp_task_slot() to tsk_pinned, and we get a stable snapshot.
         */
        lockdep_assert_held_write(&bp_cpuinfo_sem);
-
-       for (i = hw_breakpoint_slots_cached(type) - 1; i >= 0; i--) {
-               ASSERT_EXCLUSIVE_WRITER(tsk_pinned[i]); /* Catch unexpected writers. */
-               if (atomic_read(&tsk_pinned[i]) > 0)
-                       return i + 1;
-       }
-
-       return 0;
+       return bp_slots_histogram_max(tsk_pinned, type);
 }
 
 /*

@@ -300,8 +338,7 @@ max_bp_pinned_slots(struct perf_event *bp, enum bp_type_idx type)
 static void toggle_bp_task_slot(struct perf_event *bp, int cpu,
                                enum bp_type_idx type, int weight)
 {
-       atomic_t *tsk_pinned = get_bp_info(cpu, type)->tsk_pinned;
-       int old_idx, new_idx;
+       struct bp_slots_histogram *tsk_pinned = &get_bp_info(cpu, type)->tsk_pinned;
 
        /*
         * If bp->hw.target, tsk_pinned is only modified, but not used

@@ -311,14 +348,7 @@ static void toggle_bp_task_slot(struct perf_event *bp, int cpu,
         * bp_cpuinfo_sem as a writer to stabilize tsk_pinned's value.
         */
        lockdep_assert_held_read(&bp_cpuinfo_sem);
-
-       old_idx = task_bp_pinned(cpu, bp, type) - 1;
-       new_idx = old_idx + weight;
-
-       if (old_idx >= 0)
-               atomic_dec(&tsk_pinned[old_idx]);
-       if (new_idx >= 0)
-               atomic_inc(&tsk_pinned[new_idx]);
+       bp_slots_histogram_add(tsk_pinned, task_bp_pinned(cpu, bp, type), weight);
 }
 
 /*
--

2.37.0.rc0.161.g10f37bed90-goog