Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > linux.kernel > #1395535
| From | Arnaldo Carvalho de Melo <acme@kernel.org> |
|---|---|
| Newsgroups | linux.kernel |
| Subject | [PATCH 02/17] perf tools: Add template for generating rbtree resort class |
| Date | 2016-05-06 02:40 +0200 |
| Message-ID | <rvBYf-2li-39@gated-at.bofh.it> (permalink) |
| References | <rvBYe-2li-13@gated-at.bofh.it> |
| Organization | linux.* mail to news gateway |
From: Arnaldo Carvalho de Melo <acme@redhat.com>
Sometimes we want to sort an existing rbtree by a different key,
introduce a template for that, that needs only to be provided the
rbtree root and the number of entries in it.
To do that a new rbtree will be created with extra space for each entry,
where possibly pre-calculated keys will be stored to be used in the
resort process and also later, when using the newly sorted rbtree.
Please check the following two changesets to see it in use for resorting
stats for threads and its syscalls in 'perf trace --summary'.
Cc: Adrian Hunter <adrian.hunter@intel.com>
Cc: David Ahern <dsahern@gmail.com>
Cc: Jiri Olsa <jolsa@kernel.org>
Cc: Milian Wolff <milian.wolff@kdab.com>
Cc: Namhyung Kim <namhyung@kernel.org>
Cc: Wang Nan <wangnan0@huawei.com>
Link: http://lkml.kernel.org/n/tip-9l6e1q34lmf3wwdeewstyakg@git.kernel.org
Signed-off-by: Arnaldo Carvalho de Melo <acme@redhat.com>
---
tools/perf/util/rb_resort.h | 149 ++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 149 insertions(+)
create mode 100644 tools/perf/util/rb_resort.h
diff --git a/tools/perf/util/rb_resort.h b/tools/perf/util/rb_resort.h
new file mode 100644
index 000000000000..abc76e3d3098
--- /dev/null
+++ b/tools/perf/util/rb_resort.h
@@ -0,0 +1,149 @@
+#ifndef _PERF_RESORT_RB_H_
+#define _PERF_RESORT_RB_H_
+/*
+ * Template for creating a class to resort an existing rb_tree according to
+ * a new sort criteria, that must be present in the entries of the source
+ * rb_tree.
+ *
+ * (c) 2016 Arnaldo Carvalho de Melo <acme@redhat.com>
+ *
+ * Quick example, resorting threads by its shortname:
+ *
+ * First define the prefix (threads) to be used for the functions and data
+ * structures created, and provide an expression for the sorting, then the
+ * fields to be present in each of the entries in the new, sorted, rb_tree.
+ *
+ * The body of the init function should collect the fields, maybe
+ * pre-calculating them from multiple entries in the original 'entry' from
+ * the rb_tree used as a source for the entries to be sorted:
+
+DEFINE_RB_RESORT_RB(threads, strcmp(a->thread->shortname,
+ b->thread->shortname) < 0,
+ struct thread *thread;
+)
+{
+ entry->thread = rb_entry(nd, struct thread, rb_node);
+}
+
+ * After this it is just a matter of instantiating it and iterating it,
+ * for a few data structures with existing rb_trees, such as 'struct machine',
+ * helpers are available to get the rb_root and the nr_entries:
+
+ DECLARE_RESORT_RB_MACHINE_THREADS(threads, machine_ptr);
+
+ * This will instantiate the new rb_tree and a cursor for it, that can be used as:
+
+ struct rb_node *nd;
+
+ resort_rb__for_each(nd, threads) {
+ struct thread *t = threads_entry;
+ printf("%s: %d\n", t->shortname, t->tid);
+ }
+
+ * Then delete it:
+
+ resort_rb__delete(threads);
+
+ * The name of the data structures and functions will have a _sorted suffix
+ * right before the method names, i.e. will look like:
+ *
+ * struct threads_sorted_entry {}
+ * threads_sorted__insert()
+ */
+
+#define DEFINE_RESORT_RB(__name, __comp, ...) \
+struct __name##_sorted_entry { \
+ struct rb_node rb_node; \
+ __VA_ARGS__ \
+}; \
+static void __name##_sorted__init_entry(struct rb_node *nd, \
+ struct __name##_sorted_entry *entry); \
+ \
+static int __name##_sorted__cmp(struct rb_node *nda, struct rb_node *ndb) \
+{ \
+ struct __name##_sorted_entry *a, *b; \
+ a = rb_entry(nda, struct __name##_sorted_entry, rb_node); \
+ b = rb_entry(ndb, struct __name##_sorted_entry, rb_node); \
+ return __comp; \
+} \
+ \
+struct __name##_sorted { \
+ struct rb_root entries; \
+ struct __name##_sorted_entry nd[0]; \
+}; \
+ \
+static void __name##_sorted__insert(struct __name##_sorted *sorted, \
+ struct rb_node *sorted_nd) \
+{ \
+ struct rb_node **p = &sorted->entries.rb_node, *parent = NULL; \
+ while (*p != NULL) { \
+ parent = *p; \
+ if (__name##_sorted__cmp(sorted_nd, parent)) \
+ p = &(*p)->rb_left; \
+ else \
+ p = &(*p)->rb_right; \
+ } \
+ rb_link_node(sorted_nd, parent, p); \
+ rb_insert_color(sorted_nd, &sorted->entries); \
+} \
+ \
+static void __name##_sorted__sort(struct __name##_sorted *sorted, \
+ struct rb_root *entries) \
+{ \
+ struct rb_node *nd; \
+ unsigned int i = 0; \
+ for (nd = rb_first(entries); nd; nd = rb_next(nd)) { \
+ struct __name##_sorted_entry *snd = &sorted->nd[i++]; \
+ __name##_sorted__init_entry(nd, snd); \
+ __name##_sorted__insert(sorted, &snd->rb_node); \
+ } \
+} \
+ \
+static struct __name##_sorted *__name##_sorted__new(struct rb_root *entries, \
+ int nr_entries) \
+{ \
+ struct __name##_sorted *sorted; \
+ sorted = malloc(sizeof(*sorted) + sizeof(sorted->nd[0]) * nr_entries); \
+ if (sorted) { \
+ sorted->entries = RB_ROOT; \
+ __name##_sorted__sort(sorted, entries); \
+ } \
+ return sorted; \
+} \
+ \
+static void __name##_sorted__delete(struct __name##_sorted *sorted) \
+{ \
+ free(sorted); \
+} \
+ \
+static void __name##_sorted__init_entry(struct rb_node *nd, \
+ struct __name##_sorted_entry *entry)
+
+#define DECLARE_RESORT_RB(__name) \
+struct __name##_sorted_entry *__name##_entry; \
+struct __name##_sorted *__name = __name##_sorted__new
+
+#define resort_rb__for_each(__nd, __name) \
+ for (__nd = rb_first(&__name->entries); \
+ __name##_entry = rb_entry(__nd, struct __name##_sorted_entry, \
+ rb_node), __nd; \
+ __nd = rb_next(__nd))
+
+#define resort_rb__delete(__name) \
+ __name##_sorted__delete(__name), __name = NULL
+
+/*
+ * Helpers for other classes that contains both an rbtree and the
+ * number of entries in it:
+ */
+
+/* For 'struct intlist' */
+#define DECLARE_RESORT_RB_INTLIST(__name, __ilist) \
+ DECLARE_RESORT_RB(__name)(&__ilist->rblist.entries, \
+ __ilist->rblist.nr_entries)
+
+/* For 'struct machine->threads' */
+#define DECLARE_RESORT_RB_MACHINE_THREADS(__name, __machine) \
+ DECLARE_RESORT_RB(__name)(&__machine->threads, __machine->nr_threads)
+
+#endif /* _PERF_RESORT_RB_H_ */
--
2.5.5
Back to linux.kernel | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
[GIT PULL 00/17] perf/core improvements and fixes Arnaldo Carvalho de Melo <acme@kernel.org> - 2016-05-06 02:40 +0200 [PATCH 11/17] perf hists: Move sort__has_socket into struct perf_hpp_list Arnaldo Carvalho de Melo <acme@kernel.org> - 2016-05-06 02:40 +0200 [PATCH 02/17] perf tools: Add template for generating rbtree resort class Arnaldo Carvalho de Melo <acme@kernel.org> - 2016-05-06 02:40 +0200 [PATCH 13/17] perf hists: Move sort__has_comm into struct perf_hpp_list Arnaldo Carvalho de Melo <acme@kernel.org> - 2016-05-06 02:40 +0200 [PATCH 14/17] perf powerpc: Fix kprobe and kretprobe handling with kallsyms on ppc64le Arnaldo Carvalho de Melo <acme@kernel.org> - 2016-05-06 02:40 +0200 [PATCH 04/17] perf trace: Sort syscalls stats by msecs in --summary Arnaldo Carvalho de Melo <acme@kernel.org> - 2016-05-06 02:40 +0200 [PATCH 05/17] perf trace: Do not show the runtime_ms for a thread when not collecting it Arnaldo Carvalho de Melo <acme@kernel.org> - 2016-05-06 02:40 +0200 [PATCH 01/17] perf machine: Introduce number of threads member Arnaldo Carvalho de Melo <acme@kernel.org> - 2016-05-06 02:40 +0200 [PATCH 17/17] perf evlist: Rename variable in perf_mmap__read() Arnaldo Carvalho de Melo <acme@kernel.org> - 2016-05-06 02:40 +0200 [PATCH 10/17] perf hists: Move sort__has_dso into struct perf_hpp_list Arnaldo Carvalho de Melo <acme@kernel.org> - 2016-05-06 02:40 +0200 [PATCH 03/17] perf trace: Sort summary output by number of events Arnaldo Carvalho de Melo <acme@kernel.org> - 2016-05-06 02:40 +0200 [PATCH 09/17] perf hists: Move sort__has_sym into struct perf_hpp_list Arnaldo Carvalho de Melo <acme@kernel.org> - 2016-05-06 02:40 +0200 [PATCH 15/17] perf symbols: Fix kallsyms perf test on ppc64le Arnaldo Carvalho de Melo <acme@kernel.org> - 2016-05-06 02:40 +0200 Re: [GIT PULL 00/17] perf/core improvements and fixes Ingo Molnar <mingo@kernel.org> - 2016-05-06 08:40 +0200
csiph-web