3 files changed, 71 insertions, 5 deletions

diff --git a/tools/perf/util/dso.c b/tools/perf/util/dso.c
index 901a58fa3f22..0247acfdfaca 100644
--- a/tools/perf/util/dso.c
+++ b/tools/perf/util/dso.c
@@ -653,6 +653,65 @@ struct dso *dso__kernel_findnew(struct machine *machine, const char *name,
         return dso;
 }
 
+/*
+ * Find a matching entry and/or link current entry to RB tree.
+ * Either one of the dso or name parameter must be non-NULL or the
+ * function will not work.
+ */
+static struct dso *dso__findlink_by_longname(struct rb_root *root,
+                                             struct dso *dso, const char *name)
+{
+        struct rb_node **p = &root->rb_node;
+        struct rb_node  *parent = NULL;
+
+        if (!name)
+                name = dso->long_name;
+        /*
+         * Find node with the matching name
+         */
+        while (*p) {
+                struct dso *this = rb_entry(*p, struct dso, rb_node);
+                int rc = strcmp(name, this->long_name);
+
+                parent = *p;
+                if (rc == 0) {
+                        /*
+                         * In case the new DSO is a duplicate of an existing
+                         * one, print an one-time warning & put the new entry
+                         * at the end of the list of duplicates.
+                         */
+                        if (!dso || (dso == this))
+                                return this;    /* Find matching dso */
+                        /*
+                         * The core kernel DSOs may have duplicated long name.
+                         * In this case, the short name should be different.
+                         * Comparing the short names to differentiate the DSOs.
+                         */
+                        rc = strcmp(dso->short_name, this->short_name);
+                        if (rc == 0) {
+                                pr_err("Duplicated dso name: %s\n", name);
+                                return NULL;
+                        }
+                }
+                if (rc < 0)
+                        p = &parent->rb_left;
+                else
+                        p = &parent->rb_right;
+        }
+        if (dso) {
+                /* Add new node and rebalance tree */
+                rb_link_node(&dso->rb_node, parent, p);
+                rb_insert_color(&dso->rb_node, root);
+        }
+        return NULL;
+}
+
+static inline struct dso *
+dso__find_by_longname(const struct rb_root *root, const char *name)
+{
+        return dso__findlink_by_longname((struct rb_root *)root, NULL, name);
+}
+
 void dso__set_long_name(struct dso *dso, const char *name, bool name_allocated)
 {
         if (name == NULL)
@@ -755,6 +814,7 @@ struct dso *dso__new(const char *name)
                 dso->a2l_fails = 1;
                 dso->kernel = DSO_TYPE_USER;
                 dso->needs_swap = DSO_SWAP__UNSET;
+                RB_CLEAR_NODE(&dso->rb_node);
                 INIT_LIST_HEAD(&dso->node);
                 INIT_LIST_HEAD(&dso->data.open_entry);
         }
@@ -765,6 +825,10 @@ struct dso *dso__new(const char *name)
 void dso__delete(struct dso *dso)
 {
         int i;
+
+        if (!RB_EMPTY_NODE(&dso->rb_node))
+                pr_err("DSO %s is still in rbtree when being deleted!\n",
+                       dso->long_name);
         for (i = 0; i < MAP__NR_TYPES; ++i)
                 symbols__delete(&dso->symbols[i]);
 
@@ -854,6 +918,7 @@ bool __dsos__read_build_ids(struct list_head *head, bool with_hits)
 void dsos__add(struct dsos *dsos, struct dso *dso)
 {
         list_add_tail(&dso->node, &dsos->head);
+        dso__findlink_by_longname(&dsos->root, dso, NULL);
 }
 
 struct dso *dsos__find(const struct dsos *dsos, const char *name,
@@ -867,10 +932,7 @@ struct dso *dsos__find(const struct dsos *dsos, const char *name,
                                 return pos;
                 return NULL;
         }
-        list_for_each_entry(pos, &dsos->head, node)
-                if (strcmp(pos->long_name, name) == 0)
-                        return pos;
-        return NULL;
+        return dso__find_by_longname(&dsos->root, name);
 }
 
 struct dso *__dsos__findnew(struct dsos *dsos, const char *name)
diff --git a/tools/perf/util/dso.h b/tools/perf/util/dso.h
index b63dc98ad71d..acb651acc7fd 100644
--- a/tools/perf/util/dso.h
+++ b/tools/perf/util/dso.h
@@ -91,14 +91,17 @@ struct dso_cache {
 };
 
 /*
- * DSOs are put into a list for fast iteration.
+ * DSOs are put into both a list for fast iteration and rbtree for fast
+ * long name lookup.
  */
 struct dsos {
         struct list_head head;
+        struct rb_root   root;  /* rbtree root sorted by long name */
 };
 
 struct dso {
         struct list_head node;
+        struct rb_node   rb_node;       /* rbtree node sorted by long name */
         struct rb_root   symbols[MAP__NR_TYPES];
         struct rb_root   symbol_names[MAP__NR_TYPES];
         void             *a2l;
diff --git a/tools/perf/util/machine.c b/tools/perf/util/machine.c
index 49a75ec4c47b..b7d477fbda02 100644
--- a/tools/perf/util/machine.c
+++ b/tools/perf/util/machine.c
@@ -77,6 +77,7 @@ static void dsos__delete(struct dsos *dsos)
         struct dso *pos, *n;
 
         list_for_each_entry_safe(pos, n, &dsos->head, node) {
+                RB_CLEAR_NODE(&pos->rb_node);
                 list_del(&pos->node);
                 dso__delete(pos);
         }