* [PATCH] perf ordered_events: Optimise event object reuse
@ 2020-05-15 21:01 Matt Fleming
2020-05-18 12:04 ` Jiri Olsa
0 siblings, 1 reply; 5+ messages in thread
From: Matt Fleming @ 2020-05-15 21:01 UTC (permalink / raw)
To: Jiri Olsa, Arnaldo Carvalho de Melo; +Cc: linux-kernel, Matt Fleming
ordered_event objects can be placed on the free object cache list in any
order which means future allocations may not return objects at
sequential locations in memory. Getting non-contiguous objects from the
free cache has bad consequences when later iterating over those objects
in ordered_events__queue().
For example, large perf.data files can contain trillions of events and
since objects that are next to each other in the free cache linked list
can point to pretty much anywhere in the object address space, lots of
cycles in ordered_events__queue() are spent servicing DTLB misses.
Implement the free object cache using the in-kernel implementation of
interval trees so that objects can always be allocated from the free
object cache in sequential order, improving spatial locality and
reducing DTLB misses.
Here are some numbers showing the speed up (reducing in execution time)
when running perf sched latency on sched events data and perf report on
HW_CPU_CYCLES.
$ perf stat --null -r 10 -- bash -c \
"export PAGER=cat ; perf sched latency -i $file --stdio &>/dev/null"
Nr events File Size Before After Speed up
-------------- --------- -------- ------- ----------
123318457470 29MB 0.2149 0.2440 -13.5%
1651500885357 260MB 3.1205 1.9855 +36.4%
3470519751785 506MB 6.1821 3.8941 +37.0%
8213765551679 1100MB 13.4875 8.5079 +36.9%
15900515973759 1946MB 23.4069 15.0960 +35.5%
and HW_CPU_CYCLES events:
$ perf stat --null -r 10 -- bash -c \
"export PAGER=cat ; perf report -i $file --stdio &>/dev/null"
Nr events File Size Before After Speed up
-------------- --------- -------- ------- ----------
328805166262 29MB 1.637 1.587 +3.0%
3280413919096 253MB 13.381 12.349 +7.7%
6475305954370 500MB 25.648 23.753 +7.4%
14218430569416 1000MB 52.800 49.036 +7.1%
26760562279427 2000MB 97.169 90.129 +7.2%
Signed-off-by: Matt Fleming <matt@codeblueprint.co.uk>
---
tools/include/linux/interval_tree.h | 30 +++
tools/include/linux/interval_tree_generic.h | 187 ++++++++++++++++++
tools/lib/interval_tree.c | 12 ++
tools/perf/MANIFEST | 1 +
tools/perf/tests/Build | 1 +
tools/perf/tests/builtin-test.c | 4 +
tools/perf/tests/free-object-cache.c | 200 ++++++++++++++++++++
tools/perf/tests/tests.h | 2 +
tools/perf/util/Build | 6 +
tools/perf/util/ordered-events.c | 130 ++++++++++++-
tools/perf/util/ordered-events.h | 8 +-
11 files changed, 573 insertions(+), 8 deletions(-)
create mode 100644 tools/include/linux/interval_tree.h
create mode 100644 tools/include/linux/interval_tree_generic.h
create mode 100644 tools/lib/interval_tree.c
create mode 100644 tools/perf/tests/free-object-cache.c
diff --git a/tools/include/linux/interval_tree.h b/tools/include/linux/interval_tree.h
new file mode 100644
index 000000000000..288c26f50732
--- /dev/null
+++ b/tools/include/linux/interval_tree.h
@@ -0,0 +1,30 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#ifndef _LINUX_INTERVAL_TREE_H
+#define _LINUX_INTERVAL_TREE_H
+
+#include <linux/rbtree.h>
+
+struct interval_tree_node {
+ struct rb_node rb;
+ unsigned long start; /* Start of interval */
+ unsigned long last; /* Last location _in_ interval */
+ unsigned long __subtree_last;
+};
+
+extern void
+interval_tree_insert(struct interval_tree_node *node,
+ struct rb_root_cached *root);
+
+extern void
+interval_tree_remove(struct interval_tree_node *node,
+ struct rb_root_cached *root);
+
+extern struct interval_tree_node *
+interval_tree_iter_first(struct rb_root_cached *root,
+ unsigned long start, unsigned long last);
+
+extern struct interval_tree_node *
+interval_tree_iter_next(struct interval_tree_node *node,
+ unsigned long start, unsigned long last);
+
+#endif /* _LINUX_INTERVAL_TREE_H */
diff --git a/tools/include/linux/interval_tree_generic.h b/tools/include/linux/interval_tree_generic.h
new file mode 100644
index 000000000000..aaa8a0767aa3
--- /dev/null
+++ b/tools/include/linux/interval_tree_generic.h
@@ -0,0 +1,187 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+/*
+ Interval Trees
+ (C) 2012 Michel Lespinasse <walken@google.com>
+
+
+ include/linux/interval_tree_generic.h
+*/
+
+#include <linux/rbtree_augmented.h>
+
+/*
+ * Template for implementing interval trees
+ *
+ * ITSTRUCT: struct type of the interval tree nodes
+ * ITRB: name of struct rb_node field within ITSTRUCT
+ * ITTYPE: type of the interval endpoints
+ * ITSUBTREE: name of ITTYPE field within ITSTRUCT holding last-in-subtree
+ * ITSTART(n): start endpoint of ITSTRUCT node n
+ * ITLAST(n): last endpoint of ITSTRUCT node n
+ * ITSTATIC: 'static' or empty
+ * ITPREFIX: prefix to use for the inline tree definitions
+ *
+ * Note - before using this, please consider if generic version
+ * (interval_tree.h) would work for you...
+ */
+
+#define INTERVAL_TREE_DEFINE(ITSTRUCT, ITRB, ITTYPE, ITSUBTREE, \
+ ITSTART, ITLAST, ITSTATIC, ITPREFIX) \
+ \
+/* Callbacks for augmented rbtree insert and remove */ \
+ \
+RB_DECLARE_CALLBACKS_MAX(static, ITPREFIX ## _augment, \
+ ITSTRUCT, ITRB, ITTYPE, ITSUBTREE, ITLAST) \
+ \
+/* Insert / remove interval nodes from the tree */ \
+ \
+ITSTATIC void ITPREFIX ## _insert(ITSTRUCT *node, \
+ struct rb_root_cached *root) \
+{ \
+ struct rb_node **link = &root->rb_root.rb_node, *rb_parent = NULL; \
+ ITTYPE start = ITSTART(node), last = ITLAST(node); \
+ ITSTRUCT *parent; \
+ bool leftmost = true; \
+ \
+ while (*link) { \
+ rb_parent = *link; \
+ parent = rb_entry(rb_parent, ITSTRUCT, ITRB); \
+ if (parent->ITSUBTREE < last) \
+ parent->ITSUBTREE = last; \
+ if (start < ITSTART(parent)) \
+ link = &parent->ITRB.rb_left; \
+ else { \
+ link = &parent->ITRB.rb_right; \
+ leftmost = false; \
+ } \
+ } \
+ \
+ node->ITSUBTREE = last; \
+ rb_link_node(&node->ITRB, rb_parent, link); \
+ rb_insert_augmented_cached(&node->ITRB, root, \
+ leftmost, &ITPREFIX ## _augment); \
+} \
+ \
+ITSTATIC void ITPREFIX ## _remove(ITSTRUCT *node, \
+ struct rb_root_cached *root) \
+{ \
+ rb_erase_augmented_cached(&node->ITRB, root, &ITPREFIX ## _augment); \
+} \
+ \
+/* \
+ * Iterate over intervals intersecting [start;last] \
+ * \
+ * Note that a node's interval intersects [start;last] iff: \
+ * Cond1: ITSTART(node) <= last \
+ * and \
+ * Cond2: start <= ITLAST(node) \
+ */ \
+ \
+static ITSTRUCT * \
+ITPREFIX ## _subtree_search(ITSTRUCT *node, ITTYPE start, ITTYPE last) \
+{ \
+ while (true) { \
+ /* \
+ * Loop invariant: start <= node->ITSUBTREE \
+ * (Cond2 is satisfied by one of the subtree nodes) \
+ */ \
+ if (node->ITRB.rb_left) { \
+ ITSTRUCT *left = rb_entry(node->ITRB.rb_left, \
+ ITSTRUCT, ITRB); \
+ if (start <= left->ITSUBTREE) { \
+ /* \
+ * Some nodes in left subtree satisfy Cond2. \
+ * Iterate to find the leftmost such node N. \
+ * If it also satisfies Cond1, that's the \
+ * match we are looking for. Otherwise, there \
+ * is no matching interval as nodes to the \
+ * right of N can't satisfy Cond1 either. \
+ */ \
+ node = left; \
+ continue; \
+ } \
+ } \
+ if (ITSTART(node) <= last) { /* Cond1 */ \
+ if (start <= ITLAST(node)) /* Cond2 */ \
+ return node; /* node is leftmost match */ \
+ if (node->ITRB.rb_right) { \
+ node = rb_entry(node->ITRB.rb_right, \
+ ITSTRUCT, ITRB); \
+ if (start <= node->ITSUBTREE) \
+ continue; \
+ } \
+ } \
+ return NULL; /* No match */ \
+ } \
+} \
+ \
+ITSTATIC ITSTRUCT * \
+ITPREFIX ## _iter_first(struct rb_root_cached *root, \
+ ITTYPE start, ITTYPE last) \
+{ \
+ ITSTRUCT *node, *leftmost; \
+ \
+ if (!root->rb_root.rb_node) \
+ return NULL; \
+ \
+ /* \
+ * Fastpath range intersection/overlap between A: [a0, a1] and \
+ * B: [b0, b1] is given by: \
+ * \
+ * a0 <= b1 && b0 <= a1 \
+ * \
+ * ... where A holds the lock range and B holds the smallest \
+ * 'start' and largest 'last' in the tree. For the later, we \
+ * rely on the root node, which by augmented interval tree \
+ * property, holds the largest value in its last-in-subtree. \
+ * This allows mitigating some of the tree walk overhead for \
+ * for non-intersecting ranges, maintained and consulted in O(1). \
+ */ \
+ node = rb_entry(root->rb_root.rb_node, ITSTRUCT, ITRB); \
+ if (node->ITSUBTREE < start) \
+ return NULL; \
+ \
+ leftmost = rb_entry(root->rb_leftmost, ITSTRUCT, ITRB); \
+ if (ITSTART(leftmost) > last) \
+ return NULL; \
+ \
+ return ITPREFIX ## _subtree_search(node, start, last); \
+} \
+ \
+ITSTATIC ITSTRUCT * \
+ITPREFIX ## _iter_next(ITSTRUCT *node, ITTYPE start, ITTYPE last) \
+{ \
+ struct rb_node *rb = node->ITRB.rb_right, *prev; \
+ \
+ while (true) { \
+ /* \
+ * Loop invariants: \
+ * Cond1: ITSTART(node) <= last \
+ * rb == node->ITRB.rb_right \
+ * \
+ * First, search right subtree if suitable \
+ */ \
+ if (rb) { \
+ ITSTRUCT *right = rb_entry(rb, ITSTRUCT, ITRB); \
+ if (start <= right->ITSUBTREE) \
+ return ITPREFIX ## _subtree_search(right, \
+ start, last); \
+ } \
+ \
+ /* Move up the tree until we come from a node's left child */ \
+ do { \
+ rb = rb_parent(&node->ITRB); \
+ if (!rb) \
+ return NULL; \
+ prev = &node->ITRB; \
+ node = rb_entry(rb, ITSTRUCT, ITRB); \
+ rb = node->ITRB.rb_right; \
+ } while (prev == rb); \
+ \
+ /* Check if the node intersects [start;last] */ \
+ if (last < ITSTART(node)) /* !Cond1 */ \
+ return NULL; \
+ else if (start <= ITLAST(node)) /* Cond2 */ \
+ return node; \
+ } \
+}
diff --git a/tools/lib/interval_tree.c b/tools/lib/interval_tree.c
new file mode 100644
index 000000000000..4775c291edd6
--- /dev/null
+++ b/tools/lib/interval_tree.c
@@ -0,0 +1,12 @@
+// SPDX-License-Identifier: GPL-2.0-only
+#include <linux/interval_tree.h>
+#include <linux/interval_tree_generic.h>
+#include <linux/compiler.h>
+#include <linux/export.h>
+
+#define START(node) ((node)->start)
+#define LAST(node) ((node)->last)
+
+INTERVAL_TREE_DEFINE(struct interval_tree_node, rb,
+ unsigned long, __subtree_last,
+ START, LAST,, interval_tree)
diff --git a/tools/perf/MANIFEST b/tools/perf/MANIFEST
index 5d7b947320fb..01fe06660a77 100644
--- a/tools/perf/MANIFEST
+++ b/tools/perf/MANIFEST
@@ -20,4 +20,5 @@ tools/lib/bitmap.c
tools/lib/str_error_r.c
tools/lib/vsprintf.c
tools/lib/zalloc.c
+tools/lib/interval_tree.c
scripts/bpf_helpers_doc.py
diff --git a/tools/perf/tests/Build b/tools/perf/tests/Build
index b3d1bf13ca07..c4e65ce96e2e 100644
--- a/tools/perf/tests/Build
+++ b/tools/perf/tests/Build
@@ -56,6 +56,7 @@ perf-y += mem2node.o
perf-y += maps.o
perf-y += time-utils-test.o
perf-y += genelf.o
+perf-y += free-object-cache.o
$(OUTPUT)tests/llvm-src-base.c: tests/bpf-script-example.c tests/Build
$(call rule_mkdir)
diff --git a/tools/perf/tests/builtin-test.c b/tools/perf/tests/builtin-test.c
index b6322eb0f423..efb9bf7b9056 100644
--- a/tools/perf/tests/builtin-test.c
+++ b/tools/perf/tests/builtin-test.c
@@ -313,6 +313,10 @@ static struct test generic_tests[] = {
.desc = "maps__merge_in",
.func = test__maps__merge_in,
},
+ {
+ .desc = "Free object cache",
+ .func = test__free_object_cache,
+ },
{
.func = NULL,
},
diff --git a/tools/perf/tests/free-object-cache.c b/tools/perf/tests/free-object-cache.c
new file mode 100644
index 000000000000..e4395ece7d2b
--- /dev/null
+++ b/tools/perf/tests/free-object-cache.c
@@ -0,0 +1,200 @@
+// SPDX-License-Identifier: GPL-2.0
+#include "tests.h"
+#include <linux/kernel.h>
+
+#define ordered_events__flush_time __test_ordered_events__flush_time
+#define ordered_events__first_time __test_ordered_events__first_time
+#define ordered_events__delete __test_ordered_events__delete
+#define ordered_events__init __test_ordered_events__init
+#define ordered_events__free __test_ordered_events__free
+#define ordered_events__queue __test_ordered_events__queue
+#define ordered_events__reinit __test_ordered_events__reinit
+#define ordered_events__flush __test_ordered_events__flush
+
+#include "../util/ordered-events.c"
+
+static void *alloc_cache(unsigned int num_objs)
+{
+ void *ptr = calloc(sizeof(struct ordered_event), num_objs);
+ return ptr;
+}
+
+static inline struct ordered_event *
+cache_obj_entry(void *ptr, unsigned int index)
+{
+ struct ordered_event *objs = ptr;
+ return &objs[index];
+}
+
+static int test_cache_get_put(void)
+{
+ struct ordered_events oe;
+ struct ordered_event *e;
+ int num_objs, i;
+ void *ptr;
+
+ __test_ordered_events__init(&oe, NULL, NULL);
+
+ num_objs = 8;
+ ptr = alloc_cache(num_objs);
+
+ e = free_cache_get(&oe);
+ TEST_ASSERT_VAL("got object from empty cache", e == NULL);
+
+ for (i = 0; i < num_objs; i++) {
+ e = cache_obj_entry(ptr, i);
+ free_cache_put(&oe, e);
+ }
+
+ for (i = 0; i < num_objs; i++) {
+ e = free_cache_get(&oe);
+ TEST_ASSERT_VAL("ran out of objects", e != NULL);
+ }
+
+ e = free_cache_get(&oe);
+ TEST_ASSERT_VAL("got object from empty cache after put", e == NULL);
+
+ free(ptr);
+
+ return 0;
+}
+
+#define CHECK_EVENTS_IN_ORDER(o, addr) \
+ for (i = 0; i < num_objs; i++) { \
+ struct ordered_event *__e = free_cache_get(o); \
+ TEST_ASSERT_VAL("out-of-order event object", __e == cache_obj_entry(addr, i)); \
+ }
+
+/*
+ * The reason that the free object cache switched to using interval
+ * trees is that accessing event objects in-order (with contiguous
+ * addresses) is much faster than accessing them out-of-order when
+ * working with a large numbers of events.
+ *
+ * Check that objects are always allocated in-order no matter which
+ * ordered they're added to the cache.
+ */
+static int test_cache_get_put_in_order(void)
+{
+ struct ordered_events oe;
+ struct ordered_event *e;
+ unsigned long *obj_map;
+ int num_objs, i;
+ void *ptr;
+
+ __test_ordered_events__init(&oe, NULL, NULL);
+
+ num_objs = 8192;
+ ptr = alloc_cache(num_objs);
+
+ for (i = 0; i < num_objs; i++) {
+ e = cache_obj_entry(ptr, i);
+ free_cache_put(&oe, e);
+ }
+ CHECK_EVENTS_IN_ORDER(&oe, ptr);
+
+ /*
+ * Reverse the put order and check we still see ascending
+ * addresses on get.
+ */
+ for (i = num_objs-1; i >= 0; i--) {
+ e = cache_obj_entry(ptr, i);
+ free_cache_put(&oe, e);
+ }
+ CHECK_EVENTS_IN_ORDER(&oe, ptr);
+
+ /*
+ * Insert objects randomly and check we still see ascending
+ * addresses on get.
+ */
+ obj_map = bitmap_alloc(num_objs);
+ srand(0);
+
+ while (!bitmap_full(obj_map, num_objs)) {
+ i = rand() % num_objs;
+
+ /* Not already inserted? */
+ if (!test_and_set_bit(i, obj_map)) {
+ e = cache_obj_entry(ptr, i);
+ free_cache_put(&oe, e);
+ }
+ }
+ CHECK_EVENTS_IN_ORDER(&oe, ptr);
+
+ bitmap_free(obj_map);
+ free(ptr);
+
+ return 0;
+}
+
+/*
+ * Punch holes in the object address space and make sure that we can
+ * later fill them without corrupting objects.
+ */
+static int test_cache_hole_punch(void)
+{
+ struct ordered_events oe;
+ struct ordered_event *e;
+ int num_objs, i;
+ int holes[3] = { 2046, 4097, 7084 };
+ void *ptr;
+
+ __test_ordered_events__init(&oe, NULL, NULL);
+
+ num_objs = 8192;
+ ptr = alloc_cache(num_objs);
+
+ for (i = 0; i < num_objs; i++) {
+ switch (i) {
+ case 2046:
+ case 4097:
+ case 7084:
+ continue;
+ default:
+ break;
+ }
+
+ e = cache_obj_entry(ptr, i);
+ memset(e, i, sizeof(*e));
+ free_cache_put(&oe, e);
+ }
+
+ for (i = 0; i < 3; i++) {
+ e = cache_obj_entry(ptr, holes[i]);
+ memset(e, holes[i], sizeof(*e));
+ free_cache_put(&oe, e);
+ }
+
+ for (i = 0; i < num_objs; i++) {
+ struct ordered_event tmp;
+
+ memset(&tmp, i, sizeof(tmp));
+ e = free_cache_get(&oe);
+
+ TEST_ASSERT_VAL("out-of-order event object", e == cache_obj_entry(ptr, i));
+ TEST_ASSERT_VAL("corrupt event object", !memcmp(e, &tmp, sizeof(*e)));
+ }
+
+ free(ptr);
+
+ return 0;
+}
+
+int test__free_object_cache(struct test *test __maybe_unused, int subtest __maybe_unused)
+{
+ int ret;
+
+ ret = test_cache_get_put();
+ if (ret)
+ return ret;
+
+ ret = test_cache_get_put_in_order();
+ if (ret)
+ return ret;
+
+ ret = test_cache_hole_punch();
+ if (ret)
+ return ret;
+
+ return 0;
+}
diff --git a/tools/perf/tests/tests.h b/tools/perf/tests/tests.h
index 61a1ab032080..f790da4357c9 100644
--- a/tools/perf/tests/tests.h
+++ b/tools/perf/tests/tests.h
@@ -117,6 +117,8 @@ bool test__bp_signal_is_supported(void);
bool test__bp_account_is_supported(void);
bool test__wp_is_supported(void);
+int test__free_object_cache(struct test *test, int subtest);
+
#if defined(__arm__) || defined(__aarch64__)
#ifdef HAVE_DWARF_UNWIND_SUPPORT
struct thread;
diff --git a/tools/perf/util/Build b/tools/perf/util/Build
index c0cf8dff694e..3bfb4ab1bd7f 100644
--- a/tools/perf/util/Build
+++ b/tools/perf/util/Build
@@ -28,6 +28,7 @@ perf-y += print_binary.o
perf-y += rlimit.o
perf-y += argv_split.o
perf-y += rbtree.o
+perf-y += interval_tree.o
perf-y += libstring.o
perf-y += bitmap.o
perf-y += hweight.o
@@ -223,6 +224,7 @@ CFLAGS_find_bit.o += -Wno-unused-parameter -DETC_PERFCONFIG="BUILD_STR($(ET
CFLAGS_rbtree.o += -Wno-unused-parameter -DETC_PERFCONFIG="BUILD_STR($(ETC_PERFCONFIG_SQ))"
CFLAGS_libstring.o += -Wno-unused-parameter -DETC_PERFCONFIG="BUILD_STR($(ETC_PERFCONFIG_SQ))"
CFLAGS_hweight.o += -Wno-unused-parameter -DETC_PERFCONFIG="BUILD_STR($(ETC_PERFCONFIG_SQ))"
+CFLAGS_interval_tree.o += -Wno-unused-parameter -DETC_PERFCONFIG="BUILD_STR($(ETC_PERFCONFIG_SQ))"
CFLAGS_parse-events.o += -Wno-redundant-decls
CFLAGS_expr.o += -Wno-redundant-decls
CFLAGS_header.o += -include $(OUTPUT)PERF-VERSION-FILE
@@ -251,6 +253,10 @@ $(OUTPUT)util/rbtree.o: ../lib/rbtree.c FORCE
$(call rule_mkdir)
$(call if_changed_dep,cc_o_c)
+$(OUTPUT)util/interval_tree.o: ../lib/interval_tree.c FORCE
+ $(call rule_mkdir)
+ $(call if_changed_dep,cc_o_c)
+
$(OUTPUT)util/libstring.o: ../lib/string.c FORCE
$(call rule_mkdir)
$(call if_changed_dep,cc_o_c)
diff --git a/tools/perf/util/ordered-events.c b/tools/perf/util/ordered-events.c
index 359db2b1fcef..809bdeb42cb0 100644
--- a/tools/perf/util/ordered-events.c
+++ b/tools/perf/util/ordered-events.c
@@ -4,6 +4,7 @@
#include <linux/list.h>
#include <linux/compiler.h>
#include <linux/string.h>
+#include <linux/interval_tree.h>
#include "ordered-events.h"
#include "session.h"
#include "asm/bug.h"
@@ -95,11 +96,116 @@ static void free_dup_event(struct ordered_events *oe, union perf_event *event)
__free_dup_event(oe, event);
}
+static inline unsigned long cache_region_size(struct interval_tree_node *it)
+{
+ return it->last - it->start + 1;
+}
+
+/*
+ * Allocate a new event object from the free object cache.
+ *
+ * Find the first address range in the cache and carve out enough bytes
+ * for an ordered_event objects. The object with the lowest address is
+ * always returned so that subsequent allocations benefit from
+ * contiguous memory accesses (spatial locality).
+ */
+static struct ordered_event *free_cache_get(struct ordered_events *oe)
+{
+ struct interval_tree_node *it;
+ struct ordered_event *new;
+ size_t bytes = sizeof(*new);
+
+ it = interval_tree_iter_first(&oe->cache, 0, ULONG_MAX);
+ if (!it)
+ return NULL;
+
+ /* Has the cache memory been exhausted? */
+ assert(cache_region_size(it) >= bytes);
+
+ new = (void *)it->start;
+ interval_tree_remove(it, &oe->cache);
+
+ it->start += bytes;
+ if (cache_region_size(it))
+ interval_tree_insert(it, &oe->cache);
+ else
+ free(it);
+
+ return new;
+}
+
+static int free_cache_put(struct ordered_events *oe, struct ordered_event *event)
+{
+ struct interval_tree_node *it;
+ unsigned long start, end;
+
+ /*
+ * We're inserting a new region of free memory. Check to see if
+ * this region can be merged with an existing one. The three cases
+ * to consider are:
+ *
+ * +----------+-------+
+ * 1) | it->last | event |
+ * +----------+-------+
+ *
+ * +-------+-----------+
+ * 2) | event | it->start |
+ * +-------+-----------+
+ *
+ * +----------+-------+-------------+
+ * 3) | it->last | event | next->start |
+ * +----------+-------+-------------+
+ *
+ * Add a byte to either side of 'event' to see if there's an
+ * existing free region(s) to merge with.
+ */
+ start = (unsigned long)event;
+ end = (unsigned long)event + sizeof(*event) - 1;
+
+ it = interval_tree_iter_first(&oe->cache, start - 1, end + 1);
+ if (it) {
+ struct interval_tree_node *next;
+
+ next = interval_tree_iter_next(it, start - 1, end);
+ interval_tree_remove(it, &oe->cache);
+
+ if (next) {
+ /* Case 3: Merge two regions */
+ assert((next->start - (it->last + 1)) == sizeof(*event));
+
+ interval_tree_remove(next, &oe->cache);
+
+ it->start = start;
+ it->last = next->last;
+ free(next);
+ } else if (it->last < start) {
+ /* Case 1: Extend end of region */
+ it->last = end;
+ } else if (it->start > end) {
+ /* Case 2: Extend start of region */
+ it->start = start;
+ }
+
+ interval_tree_insert(it, &oe->cache);
+ return 0;
+ }
+
+ it = malloc(sizeof(*it));
+ if (!it)
+ return -ENOMEM;
+
+ it->start = start;
+ it->last = end;
+
+ interval_tree_insert(it, &oe->cache);
+
+ return 0;
+}
+
#define MAX_SAMPLE_BUFFER (64 * 1024 / sizeof(struct ordered_event))
static struct ordered_event *alloc_event(struct ordered_events *oe,
union perf_event *event)
{
- struct list_head *cache = &oe->cache;
struct ordered_event *new = NULL;
union perf_event *new_event;
size_t size;
@@ -134,13 +240,21 @@ static struct ordered_event *alloc_event(struct ordered_events *oe,
*
* Removal of ordered event object moves it from events to
* the cache list.
+ *
+ * The order of entries on the cache list is crucial for
+ * performance with large numbers of events. Events can be freed
+ * in essentially any order which means that free entries must
+ * be kept sorted on insertion to the cache so that subsequent
+ * allocation in alloc_event() returns contiguous addresses.
+ * This improves spatial locality.
*/
size = sizeof(*oe->buffer) + MAX_SAMPLE_BUFFER * sizeof(*new);
- if (!list_empty(cache)) {
- new = list_entry(cache->next, struct ordered_event, list);
- list_del_init(&new->list);
- } else if (oe->buffer) {
+ new = free_cache_get(oe);
+ if (new)
+ goto out;
+
+ if (oe->buffer) {
new = &oe->buffer->event[oe->buffer_idx];
if (++oe->buffer_idx == MAX_SAMPLE_BUFFER)
oe->buffer = NULL;
@@ -164,6 +278,7 @@ static struct ordered_event *alloc_event(struct ordered_events *oe,
return NULL;
}
+out:
new->event = new_event;
return new;
}
@@ -185,7 +300,8 @@ ordered_events__new_event(struct ordered_events *oe, u64 timestamp,
void ordered_events__delete(struct ordered_events *oe, struct ordered_event *event)
{
- list_move(&event->list, &oe->cache);
+ list_del_init(&event->list);
+ free_cache_put(oe, event);
oe->nr_events--;
free_dup_event(oe, event->event);
event->event = NULL;
@@ -361,8 +477,8 @@ void ordered_events__init(struct ordered_events *oe, ordered_events__deliver_t d
void *data)
{
INIT_LIST_HEAD(&oe->events);
- INIT_LIST_HEAD(&oe->cache);
INIT_LIST_HEAD(&oe->to_free);
+ oe->cache = RB_ROOT_CACHED;
oe->max_alloc_size = (u64) -1;
oe->cur_alloc_size = 0;
oe->deliver = deliver;
diff --git a/tools/perf/util/ordered-events.h b/tools/perf/util/ordered-events.h
index 0920fb0ec6cc..20d108baa572 100644
--- a/tools/perf/util/ordered-events.h
+++ b/tools/perf/util/ordered-events.h
@@ -3,9 +3,15 @@
#define __ORDERED_EVENTS_H
#include <linux/types.h>
+#include <linux/interval_tree.h>
struct perf_sample;
+struct cache_region {
+ struct interval_tree_node node;
+ size_t len;
+};
+
struct ordered_event {
u64 timestamp;
u64 file_offset;
@@ -39,7 +45,7 @@ struct ordered_events {
u64 max_alloc_size;
u64 cur_alloc_size;
struct list_head events;
- struct list_head cache;
+ struct rb_root_cached cache;
struct list_head to_free;
struct ordered_events_buffer *buffer;
struct ordered_event *last;
--
2.17.1
^ permalink raw reply related [flat|nested] 5+ messages in thread
* Re: [PATCH] perf ordered_events: Optimise event object reuse
2020-05-15 21:01 [PATCH] perf ordered_events: Optimise event object reuse Matt Fleming
@ 2020-05-18 12:04 ` Jiri Olsa
2020-05-20 13:00 ` Matt Fleming
0 siblings, 1 reply; 5+ messages in thread
From: Jiri Olsa @ 2020-05-18 12:04 UTC (permalink / raw)
To: Matt Fleming; +Cc: Jiri Olsa, Arnaldo Carvalho de Melo, linux-kernel
On Fri, May 15, 2020 at 10:01:51PM +0100, Matt Fleming wrote:
> ordered_event objects can be placed on the free object cache list in any
> order which means future allocations may not return objects at
> sequential locations in memory. Getting non-contiguous objects from the
> free cache has bad consequences when later iterating over those objects
> in ordered_events__queue().
>
> For example, large perf.data files can contain trillions of events and
> since objects that are next to each other in the free cache linked list
> can point to pretty much anywhere in the object address space, lots of
> cycles in ordered_events__queue() are spent servicing DTLB misses.
>
> Implement the free object cache using the in-kernel implementation of
> interval trees so that objects can always be allocated from the free
> object cache in sequential order, improving spatial locality and
> reducing DTLB misses.
>
> Here are some numbers showing the speed up (reducing in execution time)
> when running perf sched latency on sched events data and perf report on
> HW_CPU_CYCLES.
really nice, few questions below
>
> $ perf stat --null -r 10 -- bash -c \
> "export PAGER=cat ; perf sched latency -i $file --stdio &>/dev/null"
>
> Nr events File Size Before After Speed up
> -------------- --------- -------- ------- ----------
> 123318457470 29MB 0.2149 0.2440 -13.5%
should we be concerned about small data and the extra processing?
maybe we could add some option that disables this, at leat to be
able to compare times in the future
> 1651500885357 260MB 3.1205 1.9855 +36.4%
> 3470519751785 506MB 6.1821 3.8941 +37.0%
> 8213765551679 1100MB 13.4875 8.5079 +36.9%
> 15900515973759 1946MB 23.4069 15.0960 +35.5%
SNIP
> diff --git a/tools/include/linux/interval_tree_generic.h b/tools/include/linux/interval_tree_generic.h
> new file mode 100644
> index 000000000000..aaa8a0767aa3
> --- /dev/null
> +++ b/tools/include/linux/interval_tree_generic.h
> @@ -0,0 +1,187 @@
> +/* SPDX-License-Identifier: GPL-2.0-or-later */
> +/*
> + Interval Trees
> + (C) 2012 Michel Lespinasse <walken@google.com>
> +
> +
> + include/linux/interval_tree_generic.h
> +*/
> +
> +#include <linux/rbtree_augmented.h>
> +
> +/*
> + * Template for implementing interval trees
> + *
> + * ITSTRUCT: struct type of the interval tree nodes
> + * ITRB: name of struct rb_node field within ITSTRUCT
> + * ITTYPE: type of the interval endpoints
> + * ITSUBTREE: name of ITTYPE field within ITSTRUCT holding last-in-subtree
> + * ITSTART(n): start endpoint of ITSTRUCT node n
> + * ITLAST(n): last endpoint of ITSTRUCT node n
> + * ITSTATIC: 'static' or empty
> + * ITPREFIX: prefix to use for the inline tree definitions
> + *
> + * Note - before using this, please consider if generic version
> + * (interval_tree.h) would work for you...
the interval_tree.h looks like what you have added with the generic
header.. is there some reason to use the _generic header?
please add the header file also to check-headers.sh
> + */
> +
> +#define INTERVAL_TREE_DEFINE(ITSTRUCT, ITRB, ITTYPE, ITSUBTREE, \
> + ITSTART, ITLAST, ITSTATIC, ITPREFIX) \
> + \
> +/* Callbacks for augmented rbtree insert and remove */ \
> + \
> +RB_DECLARE_CALLBACKS_MAX(static, ITPREFIX ## _augment, \
> + ITSTRUCT, ITRB, ITTYPE, ITSUBTREE, ITLAST) \
> + \
> +/* Insert / remove interval nodes from the tree */ \
> + \
> +ITSTATIC void ITPREFIX ## _insert(ITSTRUCT *node, \
SNIP
> diff --git a/tools/perf/tests/free-object-cache.c b/tools/perf/tests/free-object-cache.c
> new file mode 100644
> index 000000000000..e4395ece7d2b
> --- /dev/null
> +++ b/tools/perf/tests/free-object-cache.c
> @@ -0,0 +1,200 @@
> +// SPDX-License-Identifier: GPL-2.0
> +#include "tests.h"
> +#include <linux/kernel.h>
> +
> +#define ordered_events__flush_time __test_ordered_events__flush_time
> +#define ordered_events__first_time __test_ordered_events__first_time
> +#define ordered_events__delete __test_ordered_events__delete
> +#define ordered_events__init __test_ordered_events__init
> +#define ordered_events__free __test_ordered_events__free
> +#define ordered_events__queue __test_ordered_events__queue
> +#define ordered_events__reinit __test_ordered_events__reinit
> +#define ordered_events__flush __test_ordered_events__flush
I'm excited to see these tests, but why is above needed?
can't you use ordered-events interface as it is? you used only
exported functions right?
> +
> +#include "../util/ordered-events.c"
> +
> +static void *alloc_cache(unsigned int num_objs)
> +{
> + void *ptr = calloc(sizeof(struct ordered_event), num_objs);
> + return ptr;
> +}
> +
> +static inline struct ordered_event *
> +cache_obj_entry(void *ptr, unsigned int index)
> +{
SNIP
> +static struct ordered_event *free_cache_get(struct ordered_events *oe)
> +{
> + struct interval_tree_node *it;
> + struct ordered_event *new;
> + size_t bytes = sizeof(*new);
> +
> + it = interval_tree_iter_first(&oe->cache, 0, ULONG_MAX);
> + if (!it)
> + return NULL;
> +
> + /* Has the cache memory been exhausted? */
> + assert(cache_region_size(it) >= bytes);
> +
> + new = (void *)it->start;
> + interval_tree_remove(it, &oe->cache);
> +
> + it->start += bytes;
> + if (cache_region_size(it))
> + interval_tree_insert(it, &oe->cache);
in case we did not use the whole node, do we need to remove
and insert back the node? it should be still the lowest node
in the tree no? we could just fix 'start'
> + else
> + free(it);
> +
> + return new;
> +}
> +
SNIP
> diff --git a/tools/perf/util/ordered-events.h b/tools/perf/util/ordered-events.h
> index 0920fb0ec6cc..20d108baa572 100644
> --- a/tools/perf/util/ordered-events.h
> +++ b/tools/perf/util/ordered-events.h
> @@ -3,9 +3,15 @@
> #define __ORDERED_EVENTS_H
>
> #include <linux/types.h>
> +#include <linux/interval_tree.h>
>
> struct perf_sample;
>
> +struct cache_region {
> + struct interval_tree_node node;
> + size_t len;
> +};
^^^ this looks like some leftover
thanks,
jirka
> +
> struct ordered_event {
> u64 timestamp;
> u64 file_offset;
> @@ -39,7 +45,7 @@ struct ordered_events {
> u64 max_alloc_size;
> u64 cur_alloc_size;
> struct list_head events;
> - struct list_head cache;
> + struct rb_root_cached cache;
> struct list_head to_free;
> struct ordered_events_buffer *buffer;
> struct ordered_event *last;
> --
> 2.17.1
>
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH] perf ordered_events: Optimise event object reuse
2020-05-18 12:04 ` Jiri Olsa
@ 2020-05-20 13:00 ` Matt Fleming
2020-05-20 21:52 ` Jiri Olsa
0 siblings, 1 reply; 5+ messages in thread
From: Matt Fleming @ 2020-05-20 13:00 UTC (permalink / raw)
To: Jiri Olsa; +Cc: Jiri Olsa, Arnaldo Carvalho de Melo, linux-kernel
On Mon, 18 May, at 02:04:08PM, Jiri Olsa wrote:
> On Fri, May 15, 2020 at 10:01:51PM +0100, Matt Fleming wrote:
> > ordered_event objects can be placed on the free object cache list in any
> > order which means future allocations may not return objects at
> > sequential locations in memory. Getting non-contiguous objects from the
> > free cache has bad consequences when later iterating over those objects
> > in ordered_events__queue().
> >
> > For example, large perf.data files can contain trillions of events and
> > since objects that are next to each other in the free cache linked list
> > can point to pretty much anywhere in the object address space, lots of
> > cycles in ordered_events__queue() are spent servicing DTLB misses.
> >
> > Implement the free object cache using the in-kernel implementation of
> > interval trees so that objects can always be allocated from the free
> > object cache in sequential order, improving spatial locality and
> > reducing DTLB misses.
> >
> > Here are some numbers showing the speed up (reducing in execution time)
> > when running perf sched latency on sched events data and perf report on
> > HW_CPU_CYCLES.
>
> really nice, few questions below
>
> >
> > $ perf stat --null -r 10 -- bash -c \
> > "export PAGER=cat ; perf sched latency -i $file --stdio &>/dev/null"
> >
> > Nr events File Size Before After Speed up
> > -------------- --------- -------- ------- ----------
> > 123318457470 29MB 0.2149 0.2440 -13.5%
>
> should we be concerned about small data and the extra processing?
I didn't look into this slowdown originally because it's ~2.9 ms, but
FYI it looks like this is caused by:
- Longer code paths (more instructions)
- More branches
- More branch mispredicts
> maybe we could add some option that disables this, at leat to be
> able to compare times in the future
Sure. Do you mean a command-line option or build-time config?
> > diff --git a/tools/include/linux/interval_tree_generic.h b/tools/include/linux/interval_tree_generic.h
> > new file mode 100644
> > index 000000000000..aaa8a0767aa3
> > --- /dev/null
> > +++ b/tools/include/linux/interval_tree_generic.h
> > @@ -0,0 +1,187 @@
> > +/* SPDX-License-Identifier: GPL-2.0-or-later */
> > +/*
> > + Interval Trees
> > + (C) 2012 Michel Lespinasse <walken@google.com>
> > +
> > +
> > + include/linux/interval_tree_generic.h
> > +*/
> > +
> > +#include <linux/rbtree_augmented.h>
> > +
> > +/*
> > + * Template for implementing interval trees
> > + *
> > + * ITSTRUCT: struct type of the interval tree nodes
> > + * ITRB: name of struct rb_node field within ITSTRUCT
> > + * ITTYPE: type of the interval endpoints
> > + * ITSUBTREE: name of ITTYPE field within ITSTRUCT holding last-in-subtree
> > + * ITSTART(n): start endpoint of ITSTRUCT node n
> > + * ITLAST(n): last endpoint of ITSTRUCT node n
> > + * ITSTATIC: 'static' or empty
> > + * ITPREFIX: prefix to use for the inline tree definitions
> > + *
> > + * Note - before using this, please consider if generic version
> > + * (interval_tree.h) would work for you...
>
> the interval_tree.h looks like what you have added with the generic
> header.. is there some reason to use the _generic header?
Yes, the _generic version contains the actual implementation of
interval trees, so you need both.
> please add the header file also to check-headers.sh
Done!
> > diff --git a/tools/perf/tests/free-object-cache.c b/tools/perf/tests/free-object-cache.c
> > new file mode 100644
> > index 000000000000..e4395ece7d2b
> > --- /dev/null
> > +++ b/tools/perf/tests/free-object-cache.c
> > @@ -0,0 +1,200 @@
> > +// SPDX-License-Identifier: GPL-2.0
> > +#include "tests.h"
> > +#include <linux/kernel.h>
> > +
> > +#define ordered_events__flush_time __test_ordered_events__flush_time
> > +#define ordered_events__first_time __test_ordered_events__first_time
> > +#define ordered_events__delete __test_ordered_events__delete
> > +#define ordered_events__init __test_ordered_events__init
> > +#define ordered_events__free __test_ordered_events__free
> > +#define ordered_events__queue __test_ordered_events__queue
> > +#define ordered_events__reinit __test_ordered_events__reinit
> > +#define ordered_events__flush __test_ordered_events__flush
>
> I'm excited to see these tests, but why is above needed?
>
> can't you use ordered-events interface as it is? you used only
> exported functions right?
Nope, the tests in this file are unit tests so I'm testing
free_cache_{get,put} which are file-local functions by #include'ing
ordered-events.c.
The above define are required to avoid duplicate symbol errors at
link-time, e.g.
util/perf-in.o: In function `ordered_events__flush_time':
/home/matt/src/kernels/linux/tools/perf/util/ordered-events.c:461: multiple definition of `ordered_events__flush_time'
tests/perf-in.o:/home/matt/src/kernels/linux/tools/perf/tests/../util/ordered-events.c:461: first defined here
There are other ways to resolve this (linker flags to change the
symbols) but I couldn't find any precedent with that, so this seemed
like the easiest and most obvious solution. I'm happy to fix this up any
other way if you have suggestions though.
> > +static struct ordered_event *free_cache_get(struct ordered_events *oe)
> > +{
> > + struct interval_tree_node *it;
> > + struct ordered_event *new;
> > + size_t bytes = sizeof(*new);
> > +
> > + it = interval_tree_iter_first(&oe->cache, 0, ULONG_MAX);
> > + if (!it)
> > + return NULL;
> > +
> > + /* Has the cache memory been exhausted? */
> > + assert(cache_region_size(it) >= bytes);
> > +
> > + new = (void *)it->start;
> > + interval_tree_remove(it, &oe->cache);
> > +
> > + it->start += bytes;
> > + if (cache_region_size(it))
> > + interval_tree_insert(it, &oe->cache);
>
> in case we did not use the whole node, do we need to remove
> and insert back the node? it should be still the lowest node
> in the tree no? we could just fix 'start'
Hmm.. I originally did this remove/insert dance to be sure that the
rbtree semantics are maintained. But I think you're right that adjusting
->start cannot cause this rbtree node to move places in the tree and the
->start value isn't stored anywhere other than this interval_tree node
(a copy of ->last, on the other hand, can be stored in the parent node).
> > diff --git a/tools/perf/util/ordered-events.h b/tools/perf/util/ordered-events.h
> > index 0920fb0ec6cc..20d108baa572 100644
> > --- a/tools/perf/util/ordered-events.h
> > +++ b/tools/perf/util/ordered-events.h
> > @@ -3,9 +3,15 @@
> > #define __ORDERED_EVENTS_H
> >
> > #include <linux/types.h>
> > +#include <linux/interval_tree.h>
> >
> > struct perf_sample;
> >
> > +struct cache_region {
> > + struct interval_tree_node node;
> > + size_t len;
> > +};
>
> ^^^ this looks like some leftover
Oops :) Yes, you're right. This should not be here.
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH] perf ordered_events: Optimise event object reuse
2020-05-20 13:00 ` Matt Fleming
@ 2020-05-20 21:52 ` Jiri Olsa
2020-05-21 14:41 ` Matt Fleming
0 siblings, 1 reply; 5+ messages in thread
From: Jiri Olsa @ 2020-05-20 21:52 UTC (permalink / raw)
To: Matt Fleming; +Cc: Jiri Olsa, Arnaldo Carvalho de Melo, linux-kernel
On Wed, May 20, 2020 at 02:00:49PM +0100, Matt Fleming wrote:
> On Mon, 18 May, at 02:04:08PM, Jiri Olsa wrote:
> > On Fri, May 15, 2020 at 10:01:51PM +0100, Matt Fleming wrote:
> > > ordered_event objects can be placed on the free object cache list in any
> > > order which means future allocations may not return objects at
> > > sequential locations in memory. Getting non-contiguous objects from the
> > > free cache has bad consequences when later iterating over those objects
> > > in ordered_events__queue().
> > >
> > > For example, large perf.data files can contain trillions of events and
> > > since objects that are next to each other in the free cache linked list
> > > can point to pretty much anywhere in the object address space, lots of
> > > cycles in ordered_events__queue() are spent servicing DTLB misses.
> > >
> > > Implement the free object cache using the in-kernel implementation of
> > > interval trees so that objects can always be allocated from the free
> > > object cache in sequential order, improving spatial locality and
> > > reducing DTLB misses.
> > >
> > > Here are some numbers showing the speed up (reducing in execution time)
> > > when running perf sched latency on sched events data and perf report on
> > > HW_CPU_CYCLES.
> >
> > really nice, few questions below
> >
> > >
> > > $ perf stat --null -r 10 -- bash -c \
> > > "export PAGER=cat ; perf sched latency -i $file --stdio &>/dev/null"
> > >
> > > Nr events File Size Before After Speed up
> > > -------------- --------- -------- ------- ----------
> > > 123318457470 29MB 0.2149 0.2440 -13.5%
> >
> > should we be concerned about small data and the extra processing?
>
> I didn't look into this slowdown originally because it's ~2.9 ms, but
> FYI it looks like this is caused by:
>
> - Longer code paths (more instructions)
> - More branches
> - More branch mispredicts
>
> > maybe we could add some option that disables this, at leat to be
> > able to compare times in the future
>
> Sure. Do you mean a command-line option or build-time config?
command line option would be great
SNIP
> > > diff --git a/tools/perf/tests/free-object-cache.c b/tools/perf/tests/free-object-cache.c
> > > new file mode 100644
> > > index 000000000000..e4395ece7d2b
> > > --- /dev/null
> > > +++ b/tools/perf/tests/free-object-cache.c
> > > @@ -0,0 +1,200 @@
> > > +// SPDX-License-Identifier: GPL-2.0
> > > +#include "tests.h"
> > > +#include <linux/kernel.h>
> > > +
> > > +#define ordered_events__flush_time __test_ordered_events__flush_time
> > > +#define ordered_events__first_time __test_ordered_events__first_time
> > > +#define ordered_events__delete __test_ordered_events__delete
> > > +#define ordered_events__init __test_ordered_events__init
> > > +#define ordered_events__free __test_ordered_events__free
> > > +#define ordered_events__queue __test_ordered_events__queue
> > > +#define ordered_events__reinit __test_ordered_events__reinit
> > > +#define ordered_events__flush __test_ordered_events__flush
> >
> > I'm excited to see these tests, but why is above needed?
> >
> > can't you use ordered-events interface as it is? you used only
> > exported functions right?
>
> Nope, the tests in this file are unit tests so I'm testing
> free_cache_{get,put} which are file-local functions by #include'ing
> ordered-events.c.
>
> The above define are required to avoid duplicate symbol errors at
> link-time, e.g.
>
> util/perf-in.o: In function `ordered_events__flush_time':
> /home/matt/src/kernels/linux/tools/perf/util/ordered-events.c:461: multiple definition of `ordered_events__flush_time'
> tests/perf-in.o:/home/matt/src/kernels/linux/tools/perf/tests/../util/ordered-events.c:461: first defined here
>
> There are other ways to resolve this (linker flags to change the
> symbols) but I couldn't find any precedent with that, so this seemed
> like the easiest and most obvious solution. I'm happy to fix this up any
> other way if you have suggestions though.
hum, could we just make free_cache_{get,put} public?
thanks,
jirka
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH] perf ordered_events: Optimise event object reuse
2020-05-20 21:52 ` Jiri Olsa
@ 2020-05-21 14:41 ` Matt Fleming
0 siblings, 0 replies; 5+ messages in thread
From: Matt Fleming @ 2020-05-21 14:41 UTC (permalink / raw)
To: Jiri Olsa; +Cc: Jiri Olsa, Arnaldo Carvalho de Melo, linux-kernel
On Wed, 20 May, at 11:52:34PM, Jiri Olsa wrote:
> On Wed, May 20, 2020 at 02:00:49PM +0100, Matt Fleming wrote:
> >
> > Nope, the tests in this file are unit tests so I'm testing
> > free_cache_{get,put} which are file-local functions by #include'ing
> > ordered-events.c.
> >
> > The above define are required to avoid duplicate symbol errors at
> > link-time, e.g.
> >
> > util/perf-in.o: In function `ordered_events__flush_time':
> > /home/matt/src/kernels/linux/tools/perf/util/ordered-events.c:461: multiple definition of `ordered_events__flush_time'
> > tests/perf-in.o:/home/matt/src/kernels/linux/tools/perf/tests/../util/ordered-events.c:461: first defined here
> >
> > There are other ways to resolve this (linker flags to change the
> > symbols) but I couldn't find any precedent with that, so this seemed
> > like the easiest and most obvious solution. I'm happy to fix this up any
> > other way if you have suggestions though.
>
> hum, could we just make free_cache_{get,put} public?
Yeah that's totally doable. I'll send a v2 with all these changes.
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2020-05-21 14:41 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-05-15 21:01 [PATCH] perf ordered_events: Optimise event object reuse Matt Fleming
2020-05-18 12:04 ` Jiri Olsa
2020-05-20 13:00 ` Matt Fleming
2020-05-20 21:52 ` Jiri Olsa
2020-05-21 14:41 ` Matt Fleming
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).