linux-kernel - Re: [PATCH 6/7] perf hist: Use cached rbtrees

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20190122135901.GE14973@kernel.org>
Date:   Tue, 22 Jan 2019 11:59:01 -0200
From:   Arnaldo Carvalho de Melo <acme@...nel.org>
To:     Davidlohr Bueso <dave@...olabs.net>
Cc:     mingo@...nel.org, linux-kernel@...r.kernel.org,
        Davidlohr Bueso <dbueso@...e.de>
Subject: Re: [PATCH 6/7] perf hist: Use cached rbtrees

Em Thu, Dec 06, 2018 at 11:18:18AM -0800, Davidlohr Bueso escreveu:
> At the cost of an extra pointer, we can avoid the O(logN) cost
> of finding the first element in the tree (smallest node), which
> is something heavily required for histograms. Specifically, the
> following are converted to rb_root_cached, and users accordingly:
> 
> hist::entries_in_array
> hist::entries_in
> hist::entries
> hist::entries_collapsed
> hist_entry::hroot_in
> hist_entry::hroot_out

  CC       /tmp/build/perf/util/hist.o
ui/browsers/hists.c: In function ‘hierarchy_set_folding’:
ui/browsers/hists.c:511:21: error: passing argument 1 of ‘rb_first’ from incompatible pointer type [-Werror=incompatible-pointer-types]
  for (nd = rb_first(&he->hroot_out); nd; nd = rb_next(nd)) {
                     ^~~~~~~~~~~~~~
In file included from ui/browsers/hists.c:8:
/home/acme/git/perf/tools/include/linux/rbtree.h:83:24: note: expected ‘const struct rb_root *’ but argument is of type ‘struct rb_root_cached *’
 extern struct rb_node *rb_first(const struct rb_root *);
                        ^~~~~~~~
ui/browsers/hists.c: In function ‘__hist_browser__set_folding’:
ui/browsers/hists.c:569:16: error: passing argument 1 of ‘rb_first’ from incompatible pointer type [-Werror=incompatible-pointer-types]
  nd = rb_first(&browser->hists->entries);
                ^~~~~~~~~~~~~~~~~~~~~~~~

So I added this on top, please check:


diff --git a/tools/perf/ui/browsers/hists.c b/tools/perf/ui/browsers/hists.c
index f8913723a99a..85790a4d1842 100644
--- a/tools/perf/ui/browsers/hists.c
+++ b/tools/perf/ui/browsers/hists.c
@@ -508,7 +508,7 @@ static int hierarchy_set_folding(struct hist_browser *hb, struct hist_entry *he,
 	struct hist_entry *child;
 	int n = 0;
 
-	for (nd = rb_first(&he->hroot_out); nd; nd = rb_next(nd)) {
+	for (nd = rb_first_cached(&he->hroot_out); nd; nd = rb_next(nd)) {
 		child = rb_entry(nd, struct hist_entry, rb_node);
 		percent = hist_entry__get_percent_limit(child);
 		if (!child->filtered && percent >= hb->min_pcnt)
@@ -566,7 +566,7 @@ __hist_browser__set_folding(struct hist_browser *browser, bool unfold)
 	struct rb_node *nd;
 	struct hist_entry *he;
 
-	nd = rb_first(&browser->hists->entries);
+	nd = rb_first_cached(&browser->hists->entries);
 	while (nd) {
 		he = rb_entry(nd, struct hist_entry, rb_node);
 
@@ -1738,7 +1738,7 @@ static void ui_browser__hists_init_top(struct ui_browser *browser)
 		struct hist_browser *hb;
 
 		hb = container_of(browser, struct hist_browser, b);
-		browser->top = rb_first(&hb->hists->entries);
+		browser->top = rb_first_cached(&hb->hists->entries);
 	}
 }
 
@@ -2649,7 +2649,7 @@ add_socket_opt(struct hist_browser *browser, struct popup_action *act,
 static void hist_browser__update_nr_entries(struct hist_browser *hb)
 {
 	u64 nr_entries = 0;
-	struct rb_node *nd = rb_first(&hb->hists->entries);
+	struct rb_node *nd = rb_first_cached(&hb->hists->entries);
 
 	if (hb->min_pcnt == 0 && !symbol_conf.report_hierarchy) {
 		hb->nr_non_filtered_entries = hb->hists->nr_non_filtered_entries;
@@ -2669,7 +2669,7 @@ static void hist_browser__update_percent_limit(struct hist_browser *hb,
 					       double percent)
 {
 	struct hist_entry *he;
-	struct rb_node *nd = rb_first(&hb->hists->entries);
+	struct rb_node *nd = rb_first_cached(&hb->hists->entries);
 	u64 total = hists__total_period(hb->hists);
 	u64 min_callchain_hits = total * (percent / 100);
 
diff --git a/tools/perf/ui/gtk/hists.c b/tools/perf/ui/gtk/hists.c
index dfab3deef028..74414ccd8c84 100644
--- a/tools/perf/ui/gtk/hists.c
+++ b/tools/perf/ui/gtk/hists.c
@@ -401,7 +401,7 @@ static void perf_gtk__show_hists(GtkWidget *window, struct hists *hists,
 }
 
 static void perf_gtk__add_hierarchy_entries(struct hists *hists,
-					    struct rb_root *root,
+					    struct rb_root_cached *root,
 					    GtkTreeStore *store,
 					    GtkTreeIter *parent,
 					    struct perf_hpp *hpp,
@@ -415,7 +415,7 @@ static void perf_gtk__add_hierarchy_entries(struct hists *hists,
 	u64 total = hists__total_period(hists);
 	int size;
 
-	for (node = rb_first(root); node; node = rb_next(node)) {
+	for (node = rb_first_cached(root); node; node = rb_next(node)) {
 		GtkTreeIter iter;
 		float percent;
 		char *bf;
@@ -578,7 +578,7 @@ static void perf_gtk__show_hierarchy(GtkWidget *window, struct hists *hists,
 	gtk_tree_view_set_model(GTK_TREE_VIEW(view), GTK_TREE_MODEL(store));
 	g_object_unref(GTK_TREE_MODEL(store));
 
-	perf_gtk__add_hierarchy_entries(hists, &hists->entries.rb_root, store,
+	perf_gtk__add_hierarchy_entries(hists, &hists->entries, store,
 					NULL, &hpp, min_pcnt);
 
 	gtk_tree_view_set_rules_hint(GTK_TREE_VIEW(view), TRUE);