[PATCH v4 0/2] perf tool: improves DSO long names search speed with rbtree

[PATCH v4 0/2] perf tool: improves DSO long names search speed with rbtree

[Waiman Long]

v3->v4:
  - As suggested by Arnaldo, keep the DSO linked list for iteration
    purpose and create a new dsos structure to host the dual list
    head and rbtree root for DSOs inside the machine structure.

v2->v3:
  - Move the rbtree linking operation from dso__set_long_name() to
    dsos__add(), where the list_add() operation was done.
  - Add a second patch to remove the linked list and iterates the
    DSO structures by going through them in the rbtree. This requires
    changes in quite a number of files, but it makes for neater code.
  - Rebased to the 3.17-rc5 kernel.

v1->v2:
 - Rename DSO longname RBtree find function to segregate its two
   different uses of searching and linking DSO into RB tree.

This patch set adds a rbtree for linking the DSO structures of the
perf tool sorted by their long names in additional to the linked list
which is of no specific order. The list enables fast iterations of
the DSOs and the rbtree root allows fast lookup by long name. The
latter use can significantly speed up DSO processing when a large
number of DSOs are beining profiled.

Waiman Long (2):
  perf tool: encapsulate dsos list head into struct dsos
  perf tool: improves DSO long names lookup speed with rbtree

 tools/perf/util/dso.c         |   90 ++++++++++++++++++++++++++++++++++++-----
 tools/perf/util/dso.h         |   10 +++-
 tools/perf/util/header.c      |   32 ++++++++------
 tools/perf/util/machine.c     |   24 +++++-----
 tools/perf/util/machine.h     |   13 +++++-
 tools/perf/util/probe-event.c |    3 +-
 tools/perf/util/symbol-elf.c  |    2 +-
 7 files changed, 130 insertions(+), 44 deletions(-)

[PATCH v4 1/2] perf tool: encapsulate dsos list head into struct dsos

[Waiman Long]

This is a precursor patch to enable long name searching of DSOs
using the rbtree. In this patch, a new dsos structure is created
which contains only a list head structure for the moment. The new
dsos structure is used, in turn, in the machine structure for the
user_dsos and kernel_dsos fields. Only the following 3 dsos functions
are modified to accept the new dsos structure parameter instead
of list_head:
 - dsos__add()
 - dsos__find()
 - __dsos__findnew()

Because of the need to find out the corresponding dsos structure to
properly call dsos__add() in dso__load_sym() of util/symbol-elf.c,
a new dsos field is also added to the dso structure.

Signed-off-by: Waiman Long <Waiman.Long@hp.com>
---
 tools/perf/util/dso.c         |   19 +++++++++++--------
 tools/perf/util/dso.h         |    9 ++++++---
 tools/perf/util/header.c      |   32 ++++++++++++++++++--------------
 tools/perf/util/machine.c     |   24 ++++++++++++------------
 tools/perf/util/machine.h     |   11 +++++++++--
 tools/perf/util/probe-event.c |    3 ++-
 tools/perf/util/symbol-elf.c  |    2 +-
 7 files changed, 59 insertions(+), 41 deletions(-)

diff --git a/tools/perf/util/dso.c b/tools/perf/util/dso.c
index 90d02c6..c2c6134 100644
--- a/tools/perf/util/dso.c
+++ b/tools/perf/util/dso.c
@@ -753,6 +753,7 @@ struct dso *dso__new(const char *name)
 		dso->a2l_fails = 1;
 		dso->kernel = DSO_TYPE_USER;
 		dso->needs_swap = DSO_SWAP__UNSET;
+		dso->dsos = NULL;
 		INIT_LIST_HEAD(&dso->node);
 		INIT_LIST_HEAD(&dso->data.open_entry);
 	}
@@ -849,35 +850,37 @@ bool __dsos__read_build_ids(struct list_head *head, bool with_hits)
 	return have_build_id;
 }
 
-void dsos__add(struct list_head *head, struct dso *dso)
+void dsos__add(struct dsos *dsos, struct dso *dso)
 {
-	list_add_tail(&dso->node, head);
+	dso->dsos = dsos;
+	list_add_tail(&dso->node, &dsos->head);
 }
 
-struct dso *dsos__find(const struct list_head *head, const char *name, bool cmp_short)
+struct dso *dsos__find(const struct dsos *dsos, const char *name,
+		       bool cmp_short)
 {
 	struct dso *pos;
 
 	if (cmp_short) {
-		list_for_each_entry(pos, head, node)
+		list_for_each_entry(pos, &dsos->head, node)
 			if (strcmp(pos->short_name, name) == 0)
 				return pos;
 		return NULL;
 	}
-	list_for_each_entry(pos, head, node)
+	list_for_each_entry(pos, &dsos->head, node)
 		if (strcmp(pos->long_name, name) == 0)
 			return pos;
 	return NULL;
 }
 
-struct dso *__dsos__findnew(struct list_head *head, const char *name)
+struct dso *__dsos__findnew(struct dsos *dsos, const char *name)
 {
-	struct dso *dso = dsos__find(head, name, false);
+	struct dso *dso = dsos__find(dsos, name, false);
 
 	if (!dso) {
 		dso = dso__new(name);
 		if (dso != NULL) {
-			dsos__add(head, dso);
+			dsos__add(dsos, dso);
 			dso__set_basename(dso);
 		}
 	}
diff --git a/tools/perf/util/dso.h b/tools/perf/util/dso.h
index 5e463c0..cadfef7 100644
--- a/tools/perf/util/dso.h
+++ b/tools/perf/util/dso.h
@@ -90,8 +90,11 @@ struct dso_cache {
 	char data[0];
 };
 
+struct dsos;
+
 struct dso {
 	struct list_head node;
+	struct dsos      *dsos;
 	struct rb_root	 symbols[MAP__NR_TYPES];
 	struct rb_root	 symbol_names[MAP__NR_TYPES];
 	void		 *a2l;
@@ -224,10 +227,10 @@ struct map *dso__new_map(const char *name);
 struct dso *dso__kernel_findnew(struct machine *machine, const char *name,
 				const char *short_name, int dso_type);
 
-void dsos__add(struct list_head *head, struct dso *dso);
-struct dso *dsos__find(const struct list_head *head, const char *name,
+void dsos__add(struct dsos *dsos, struct dso *dso);
+struct dso *dsos__find(const struct dsos *dsos, const char *name,
 		       bool cmp_short);
-struct dso *__dsos__findnew(struct list_head *head, const char *name);
+struct dso *__dsos__findnew(struct dsos *dsos, const char *name);
 bool __dsos__read_build_ids(struct list_head *head, bool with_hits);
 
 size_t __dsos__fprintf_buildid(struct list_head *head, FILE *fp,
diff --git a/tools/perf/util/header.c b/tools/perf/util/header.c
index 158c787..ce0de00 100644
--- a/tools/perf/util/header.c
+++ b/tools/perf/util/header.c
@@ -214,11 +214,11 @@ static int machine__hit_all_dsos(struct machine *machine)
 {
 	int err;
 
-	err = __dsos__hit_all(&machine->kernel_dsos);
+	err = __dsos__hit_all(&machine->kernel_dsos.head);
 	if (err)
 		return err;
 
-	return __dsos__hit_all(&machine->user_dsos);
+	return __dsos__hit_all(&machine->user_dsos.head);
 }
 
 int dsos__hit_all(struct perf_session *session)
@@ -288,11 +288,12 @@ static int machine__write_buildid_table(struct machine *machine, int fd)
 		umisc = PERF_RECORD_MISC_GUEST_USER;
 	}
 
-	err = __dsos__write_buildid_table(&machine->kernel_dsos, machine,
+	err = __dsos__write_buildid_table(&machine->kernel_dsos.head, machine,
 					  machine->pid, kmisc, fd);
 	if (err == 0)
-		err = __dsos__write_buildid_table(&machine->user_dsos, machine,
-						  machine->pid, umisc, fd);
+		err = __dsos__write_buildid_table(&machine->user_dsos.head,
+						  machine, machine->pid, umisc,
+						  fd);
 	return err;
 }
 
@@ -455,9 +456,10 @@ static int __dsos__cache_build_ids(struct list_head *head,
 
 static int machine__cache_build_ids(struct machine *machine, const char *debugdir)
 {
-	int ret = __dsos__cache_build_ids(&machine->kernel_dsos, machine,
+	int ret = __dsos__cache_build_ids(&machine->kernel_dsos.head, machine,
 					  debugdir);
-	ret |= __dsos__cache_build_ids(&machine->user_dsos, machine, debugdir);
+	ret |= __dsos__cache_build_ids(&machine->user_dsos.head, machine,
+				       debugdir);
 	return ret;
 }
 
@@ -483,8 +485,10 @@ static int perf_session__cache_build_ids(struct perf_session *session)
 
 static bool machine__read_build_ids(struct machine *machine, bool with_hits)
 {
-	bool ret = __dsos__read_build_ids(&machine->kernel_dsos, with_hits);
-	ret |= __dsos__read_build_ids(&machine->user_dsos, with_hits);
+	bool ret;
+
+	ret  = __dsos__read_build_ids(&machine->kernel_dsos.head, with_hits);
+	ret |= __dsos__read_build_ids(&machine->user_dsos.head, with_hits);
 	return ret;
 }
 
@@ -1548,7 +1552,7 @@ static int __event_process_build_id(struct build_id_event *bev,
 				    struct perf_session *session)
 {
 	int err = -1;
-	struct list_head *head;
+	struct dsos *dsos;
 	struct machine *machine;
 	u16 misc;
 	struct dso *dso;
@@ -1563,22 +1567,22 @@ static int __event_process_build_id(struct build_id_event *bev,
 	switch (misc) {
 	case PERF_RECORD_MISC_KERNEL:
 		dso_type = DSO_TYPE_KERNEL;
-		head = &machine->kernel_dsos;
+		dsos = &machine->kernel_dsos;
 		break;
 	case PERF_RECORD_MISC_GUEST_KERNEL:
 		dso_type = DSO_TYPE_GUEST_KERNEL;
-		head = &machine->kernel_dsos;
+		dsos = &machine->kernel_dsos;
 		break;
 	case PERF_RECORD_MISC_USER:
 	case PERF_RECORD_MISC_GUEST_USER:
 		dso_type = DSO_TYPE_USER;
-		head = &machine->user_dsos;
+		dsos = &machine->user_dsos;
 		break;
 	default:
 		goto out;
 	}
 
-	dso = __dsos__findnew(head, filename);
+	dso = __dsos__findnew(dsos, filename);
 	if (dso != NULL) {
 		char sbuild_id[BUILD_ID_SIZE * 2 + 1];
 
diff --git a/tools/perf/util/machine.c b/tools/perf/util/machine.c
index 16bba9f..214b6f7 100644
--- a/tools/perf/util/machine.c
+++ b/tools/perf/util/machine.c
@@ -17,8 +17,8 @@ int machine__init(struct machine *machine, const char *root_dir, pid_t pid)
 {
 	map_groups__init(&machine->kmaps);
 	RB_CLEAR_NODE(&machine->rb_node);
-	INIT_LIST_HEAD(&machine->user_dsos);
-	INIT_LIST_HEAD(&machine->kernel_dsos);
+	INIT_LIST_HEAD(&machine->user_dsos.head);
+	INIT_LIST_HEAD(&machine->kernel_dsos.head);
 
 	machine->threads = RB_ROOT;
 	INIT_LIST_HEAD(&machine->dead_threads);
@@ -70,11 +70,11 @@ out_delete:
 	return NULL;
 }
 
-static void dsos__delete(struct list_head *dsos)
+static void dsos__delete(struct dsos *dsos)
 {
 	struct dso *pos, *n;
 
-	list_for_each_entry_safe(pos, n, dsos, node) {
+	list_for_each_entry_safe(pos, n, &dsos->head, node) {
 		list_del(&pos->node);
 		dso__delete(pos);
 	}
@@ -448,23 +448,23 @@ struct map *machine__new_module(struct machine *machine, u64 start,
 size_t machines__fprintf_dsos(struct machines *machines, FILE *fp)
 {
 	struct rb_node *nd;
-	size_t ret = __dsos__fprintf(&machines->host.kernel_dsos, fp) +
-		     __dsos__fprintf(&machines->host.user_dsos, fp);
+	size_t ret = __dsos__fprintf(&machines->host.kernel_dsos.head, fp) +
+		     __dsos__fprintf(&machines->host.user_dsos.head, fp);
 
 	for (nd = rb_first(&machines->guests); nd; nd = rb_next(nd)) {
 		struct machine *pos = rb_entry(nd, struct machine, rb_node);
-		ret += __dsos__fprintf(&pos->kernel_dsos, fp);
-		ret += __dsos__fprintf(&pos->user_dsos, fp);
+		ret += __dsos__fprintf(&pos->kernel_dsos.head, fp);
+		ret += __dsos__fprintf(&pos->user_dsos.head, fp);
 	}
 
 	return ret;
 }
 
-size_t machine__fprintf_dsos_buildid(struct machine *machine, FILE *fp,
+size_t machine__fprintf_dsos_buildid(struct machine *m, FILE *fp,
 				     bool (skip)(struct dso *dso, int parm), int parm)
 {
-	return __dsos__fprintf_buildid(&machine->kernel_dsos, fp, skip, parm) +
-	       __dsos__fprintf_buildid(&machine->user_dsos, fp, skip, parm);
+	return __dsos__fprintf_buildid(&m->kernel_dsos.head, fp, skip, parm) +
+	       __dsos__fprintf_buildid(&m->user_dsos.head, fp, skip, parm);
 }
 
 size_t machines__fprintf_dsos_buildid(struct machines *machines, FILE *fp,
@@ -965,7 +965,7 @@ static bool machine__uses_kcore(struct machine *machine)
 {
 	struct dso *dso;
 
-	list_for_each_entry(dso, &machine->kernel_dsos, node) {
+	list_for_each_entry(dso, &machine->kernel_dsos.head, node) {
 		if (dso__is_kcore(dso))
 			return true;
 	}
diff --git a/tools/perf/util/machine.h b/tools/perf/util/machine.h
index b972824..d8abb6c 100644
--- a/tools/perf/util/machine.h
+++ b/tools/perf/util/machine.h
@@ -22,6 +22,13 @@ extern const char *ref_reloc_sym_names[];
 
 struct vdso_info;
 
+/*
+ * DSOs are put into a list for fast iteration.
+ */
+struct dsos {
+	struct list_head head;
+};
+
 struct machine {
 	struct rb_node	  rb_node;
 	pid_t		  pid;
@@ -31,8 +38,8 @@ struct machine {
 	struct list_head  dead_threads;
 	struct thread	  *last_match;
 	struct vdso_info  *vdso_info;
-	struct list_head  user_dsos;
-	struct list_head  kernel_dsos;
+	struct dsos	  user_dsos;
+	struct dsos	  kernel_dsos;
 	struct map_groups kmaps;
 	struct map	  *vmlinux_maps[MAP__NR_TYPES];
 	symbol_filter_t	  symbol_filter;
diff --git a/tools/perf/util/probe-event.c b/tools/perf/util/probe-event.c
index 9a0a183..b153636 100644
--- a/tools/perf/util/probe-event.c
+++ b/tools/perf/util/probe-event.c
@@ -184,7 +184,8 @@ static struct dso *kernel_get_module_dso(const char *module)
 	const char *vmlinux_name;
 
 	if (module) {
-		list_for_each_entry(dso, &host_machine->kernel_dsos, node) {
+		list_for_each_entry(dso, &host_machine->kernel_dsos.head,
+				    node) {
 			if (strncmp(dso->short_name + 1, module,
 				    dso->short_name_len - 2) == 0)
 				goto found;
diff --git a/tools/perf/util/symbol-elf.c b/tools/perf/util/symbol-elf.c
index d753499..cbecc3d 100644
--- a/tools/perf/util/symbol-elf.c
+++ b/tools/perf/util/symbol-elf.c
@@ -916,7 +916,7 @@ int dso__load_sym(struct dso *dso, struct map *map,
 				}
 				curr_dso->symtab_type = dso->symtab_type;
 				map_groups__insert(kmap->kmaps, curr_map);
-				dsos__add(&dso->node, curr_dso);
+				dsos__add(dso->dsos, curr_dso);
 				dso__set_loaded(curr_dso, map->type);
 			} else
 				curr_dso = curr_map->dso;
-- 
1.7.1

Re: [PATCH v4 1/2] perf tool: encapsulate dsos list head into struct dsos

[Arnaldo Carvalho de Melo]

Em Wed, Sep 24, 2014 at 11:45:39AM -0400, Waiman Long escreveu:
> This is a precursor patch to enable long name searching of DSOs
> using the rbtree. In this patch, a new dsos structure is created
> which contains only a list head structure for the moment. The new
> dsos structure is used, in turn, in the machine structure for the
> user_dsos and kernel_dsos fields. Only the following 3 dsos functions
> are modified to accept the new dsos structure parameter instead
> of list_head:
>  - dsos__add()
>  - dsos__find()
>  - __dsos__findnew()
> 
> Because of the need to find out the corresponding dsos structure to
> properly call dsos__add() in dso__load_sym() of util/symbol-elf.c,
> a new dsos field is also added to the dso structure.

Argh, yeah, that is unfortunate that we need to add entries that deep
inside dso__load_syms() :-\

At some point I need to go over that symbols layer, in this case, doing
multiple passes could probably limit dso__load_sym() to act _just_ on
one dso, as it should not be creating any other dso :-\

Anyway, continuing to review, enough ranting :-)

- Arnaldo
 
> Signed-off-by: Waiman Long <Waiman.Long@hp.com>
> ---
>  tools/perf/util/dso.c         |   19 +++++++++++--------
>  tools/perf/util/dso.h         |    9 ++++++---
>  tools/perf/util/header.c      |   32 ++++++++++++++++++--------------
>  tools/perf/util/machine.c     |   24 ++++++++++++------------
>  tools/perf/util/machine.h     |   11 +++++++++--
>  tools/perf/util/probe-event.c |    3 ++-
>  tools/perf/util/symbol-elf.c  |    2 +-
>  7 files changed, 59 insertions(+), 41 deletions(-)
> 
> diff --git a/tools/perf/util/dso.c b/tools/perf/util/dso.c
> index 90d02c6..c2c6134 100644
> --- a/tools/perf/util/dso.c
> +++ b/tools/perf/util/dso.c
> @@ -753,6 +753,7 @@ struct dso *dso__new(const char *name)
>  		dso->a2l_fails = 1;
>  		dso->kernel = DSO_TYPE_USER;
>  		dso->needs_swap = DSO_SWAP__UNSET;
> +		dso->dsos = NULL;
>  		INIT_LIST_HEAD(&dso->node);
>  		INIT_LIST_HEAD(&dso->data.open_entry);
>  	}
> @@ -849,35 +850,37 @@ bool __dsos__read_build_ids(struct list_head *head, bool with_hits)
>  	return have_build_id;
>  }
>  
> -void dsos__add(struct list_head *head, struct dso *dso)
> +void dsos__add(struct dsos *dsos, struct dso *dso)
>  {
> -	list_add_tail(&dso->node, head);
> +	dso->dsos = dsos;
> +	list_add_tail(&dso->node, &dsos->head);
>  }
>  
> -struct dso *dsos__find(const struct list_head *head, const char *name, bool cmp_short)
> +struct dso *dsos__find(const struct dsos *dsos, const char *name,
> +		       bool cmp_short)
>  {
>  	struct dso *pos;
>  
>  	if (cmp_short) {
> -		list_for_each_entry(pos, head, node)
> +		list_for_each_entry(pos, &dsos->head, node)
>  			if (strcmp(pos->short_name, name) == 0)
>  				return pos;
>  		return NULL;
>  	}
> -	list_for_each_entry(pos, head, node)
> +	list_for_each_entry(pos, &dsos->head, node)
>  		if (strcmp(pos->long_name, name) == 0)
>  			return pos;
>  	return NULL;
>  }
>  
> -struct dso *__dsos__findnew(struct list_head *head, const char *name)
> +struct dso *__dsos__findnew(struct dsos *dsos, const char *name)
>  {
> -	struct dso *dso = dsos__find(head, name, false);
> +	struct dso *dso = dsos__find(dsos, name, false);
>  
>  	if (!dso) {
>  		dso = dso__new(name);
>  		if (dso != NULL) {
> -			dsos__add(head, dso);
> +			dsos__add(dsos, dso);
>  			dso__set_basename(dso);
>  		}
>  	}
> diff --git a/tools/perf/util/dso.h b/tools/perf/util/dso.h
> index 5e463c0..cadfef7 100644
> --- a/tools/perf/util/dso.h
> +++ b/tools/perf/util/dso.h
> @@ -90,8 +90,11 @@ struct dso_cache {
>  	char data[0];
>  };
>  
> +struct dsos;
> +
>  struct dso {
>  	struct list_head node;
> +	struct dsos      *dsos;
>  	struct rb_root	 symbols[MAP__NR_TYPES];
>  	struct rb_root	 symbol_names[MAP__NR_TYPES];
>  	void		 *a2l;
> @@ -224,10 +227,10 @@ struct map *dso__new_map(const char *name);
>  struct dso *dso__kernel_findnew(struct machine *machine, const char *name,
>  				const char *short_name, int dso_type);
>  
> -void dsos__add(struct list_head *head, struct dso *dso);
> -struct dso *dsos__find(const struct list_head *head, const char *name,
> +void dsos__add(struct dsos *dsos, struct dso *dso);
> +struct dso *dsos__find(const struct dsos *dsos, const char *name,
>  		       bool cmp_short);
> -struct dso *__dsos__findnew(struct list_head *head, const char *name);
> +struct dso *__dsos__findnew(struct dsos *dsos, const char *name);
>  bool __dsos__read_build_ids(struct list_head *head, bool with_hits);
>  
>  size_t __dsos__fprintf_buildid(struct list_head *head, FILE *fp,
> diff --git a/tools/perf/util/header.c b/tools/perf/util/header.c
> index 158c787..ce0de00 100644
> --- a/tools/perf/util/header.c
> +++ b/tools/perf/util/header.c
> @@ -214,11 +214,11 @@ static int machine__hit_all_dsos(struct machine *machine)
>  {
>  	int err;
>  
> -	err = __dsos__hit_all(&machine->kernel_dsos);
> +	err = __dsos__hit_all(&machine->kernel_dsos.head);
>  	if (err)
>  		return err;
>  
> -	return __dsos__hit_all(&machine->user_dsos);
> +	return __dsos__hit_all(&machine->user_dsos.head);
>  }
>  
>  int dsos__hit_all(struct perf_session *session)
> @@ -288,11 +288,12 @@ static int machine__write_buildid_table(struct machine *machine, int fd)
>  		umisc = PERF_RECORD_MISC_GUEST_USER;
>  	}
>  
> -	err = __dsos__write_buildid_table(&machine->kernel_dsos, machine,
> +	err = __dsos__write_buildid_table(&machine->kernel_dsos.head, machine,
>  					  machine->pid, kmisc, fd);
>  	if (err == 0)
> -		err = __dsos__write_buildid_table(&machine->user_dsos, machine,
> -						  machine->pid, umisc, fd);
> +		err = __dsos__write_buildid_table(&machine->user_dsos.head,
> +						  machine, machine->pid, umisc,
> +						  fd);
>  	return err;
>  }
>  
> @@ -455,9 +456,10 @@ static int __dsos__cache_build_ids(struct list_head *head,
>  
>  static int machine__cache_build_ids(struct machine *machine, const char *debugdir)
>  {
> -	int ret = __dsos__cache_build_ids(&machine->kernel_dsos, machine,
> +	int ret = __dsos__cache_build_ids(&machine->kernel_dsos.head, machine,
>  					  debugdir);
> -	ret |= __dsos__cache_build_ids(&machine->user_dsos, machine, debugdir);
> +	ret |= __dsos__cache_build_ids(&machine->user_dsos.head, machine,
> +				       debugdir);
>  	return ret;
>  }
>  
> @@ -483,8 +485,10 @@ static int perf_session__cache_build_ids(struct perf_session *session)
>  
>  static bool machine__read_build_ids(struct machine *machine, bool with_hits)
>  {
> -	bool ret = __dsos__read_build_ids(&machine->kernel_dsos, with_hits);
> -	ret |= __dsos__read_build_ids(&machine->user_dsos, with_hits);
> +	bool ret;
> +
> +	ret  = __dsos__read_build_ids(&machine->kernel_dsos.head, with_hits);
> +	ret |= __dsos__read_build_ids(&machine->user_dsos.head, with_hits);
>  	return ret;
>  }
>  
> @@ -1548,7 +1552,7 @@ static int __event_process_build_id(struct build_id_event *bev,
>  				    struct perf_session *session)
>  {
>  	int err = -1;
> -	struct list_head *head;
> +	struct dsos *dsos;
>  	struct machine *machine;
>  	u16 misc;
>  	struct dso *dso;
> @@ -1563,22 +1567,22 @@ static int __event_process_build_id(struct build_id_event *bev,
>  	switch (misc) {
>  	case PERF_RECORD_MISC_KERNEL:
>  		dso_type = DSO_TYPE_KERNEL;
> -		head = &machine->kernel_dsos;
> +		dsos = &machine->kernel_dsos;
>  		break;
>  	case PERF_RECORD_MISC_GUEST_KERNEL:
>  		dso_type = DSO_TYPE_GUEST_KERNEL;
> -		head = &machine->kernel_dsos;
> +		dsos = &machine->kernel_dsos;
>  		break;
>  	case PERF_RECORD_MISC_USER:
>  	case PERF_RECORD_MISC_GUEST_USER:
>  		dso_type = DSO_TYPE_USER;
> -		head = &machine->user_dsos;
> +		dsos = &machine->user_dsos;
>  		break;
>  	default:
>  		goto out;
>  	}
>  
> -	dso = __dsos__findnew(head, filename);
> +	dso = __dsos__findnew(dsos, filename);
>  	if (dso != NULL) {
>  		char sbuild_id[BUILD_ID_SIZE * 2 + 1];
>  
> diff --git a/tools/perf/util/machine.c b/tools/perf/util/machine.c
> index 16bba9f..214b6f7 100644
> --- a/tools/perf/util/machine.c
> +++ b/tools/perf/util/machine.c
> @@ -17,8 +17,8 @@ int machine__init(struct machine *machine, const char *root_dir, pid_t pid)
>  {
>  	map_groups__init(&machine->kmaps);
>  	RB_CLEAR_NODE(&machine->rb_node);
> -	INIT_LIST_HEAD(&machine->user_dsos);
> -	INIT_LIST_HEAD(&machine->kernel_dsos);
> +	INIT_LIST_HEAD(&machine->user_dsos.head);
> +	INIT_LIST_HEAD(&machine->kernel_dsos.head);
>  
>  	machine->threads = RB_ROOT;
>  	INIT_LIST_HEAD(&machine->dead_threads);
> @@ -70,11 +70,11 @@ out_delete:
>  	return NULL;
>  }
>  
> -static void dsos__delete(struct list_head *dsos)
> +static void dsos__delete(struct dsos *dsos)
>  {
>  	struct dso *pos, *n;
>  
> -	list_for_each_entry_safe(pos, n, dsos, node) {
> +	list_for_each_entry_safe(pos, n, &dsos->head, node) {
>  		list_del(&pos->node);
>  		dso__delete(pos);
>  	}
> @@ -448,23 +448,23 @@ struct map *machine__new_module(struct machine *machine, u64 start,
>  size_t machines__fprintf_dsos(struct machines *machines, FILE *fp)
>  {
>  	struct rb_node *nd;
> -	size_t ret = __dsos__fprintf(&machines->host.kernel_dsos, fp) +
> -		     __dsos__fprintf(&machines->host.user_dsos, fp);
> +	size_t ret = __dsos__fprintf(&machines->host.kernel_dsos.head, fp) +
> +		     __dsos__fprintf(&machines->host.user_dsos.head, fp);
>  
>  	for (nd = rb_first(&machines->guests); nd; nd = rb_next(nd)) {
>  		struct machine *pos = rb_entry(nd, struct machine, rb_node);
> -		ret += __dsos__fprintf(&pos->kernel_dsos, fp);
> -		ret += __dsos__fprintf(&pos->user_dsos, fp);
> +		ret += __dsos__fprintf(&pos->kernel_dsos.head, fp);
> +		ret += __dsos__fprintf(&pos->user_dsos.head, fp);
>  	}
>  
>  	return ret;
>  }
>  
> -size_t machine__fprintf_dsos_buildid(struct machine *machine, FILE *fp,
> +size_t machine__fprintf_dsos_buildid(struct machine *m, FILE *fp,
>  				     bool (skip)(struct dso *dso, int parm), int parm)
>  {
> -	return __dsos__fprintf_buildid(&machine->kernel_dsos, fp, skip, parm) +
> -	       __dsos__fprintf_buildid(&machine->user_dsos, fp, skip, parm);
> +	return __dsos__fprintf_buildid(&m->kernel_dsos.head, fp, skip, parm) +
> +	       __dsos__fprintf_buildid(&m->user_dsos.head, fp, skip, parm);
>  }
>  
>  size_t machines__fprintf_dsos_buildid(struct machines *machines, FILE *fp,
> @@ -965,7 +965,7 @@ static bool machine__uses_kcore(struct machine *machine)
>  {
>  	struct dso *dso;
>  
> -	list_for_each_entry(dso, &machine->kernel_dsos, node) {
> +	list_for_each_entry(dso, &machine->kernel_dsos.head, node) {
>  		if (dso__is_kcore(dso))
>  			return true;
>  	}
> diff --git a/tools/perf/util/machine.h b/tools/perf/util/machine.h
> index b972824..d8abb6c 100644
> --- a/tools/perf/util/machine.h
> +++ b/tools/perf/util/machine.h
> @@ -22,6 +22,13 @@ extern const char *ref_reloc_sym_names[];
>  
>  struct vdso_info;
>  
> +/*
> + * DSOs are put into a list for fast iteration.
> + */
> +struct dsos {
> +	struct list_head head;
> +};
> +
>  struct machine {
>  	struct rb_node	  rb_node;
>  	pid_t		  pid;
> @@ -31,8 +38,8 @@ struct machine {
>  	struct list_head  dead_threads;
>  	struct thread	  *last_match;
>  	struct vdso_info  *vdso_info;
> -	struct list_head  user_dsos;
> -	struct list_head  kernel_dsos;
> +	struct dsos	  user_dsos;
> +	struct dsos	  kernel_dsos;
>  	struct map_groups kmaps;
>  	struct map	  *vmlinux_maps[MAP__NR_TYPES];
>  	symbol_filter_t	  symbol_filter;
> diff --git a/tools/perf/util/probe-event.c b/tools/perf/util/probe-event.c
> index 9a0a183..b153636 100644
> --- a/tools/perf/util/probe-event.c
> +++ b/tools/perf/util/probe-event.c
> @@ -184,7 +184,8 @@ static struct dso *kernel_get_module_dso(const char *module)
>  	const char *vmlinux_name;
>  
>  	if (module) {
> -		list_for_each_entry(dso, &host_machine->kernel_dsos, node) {
> +		list_for_each_entry(dso, &host_machine->kernel_dsos.head,
> +				    node) {
>  			if (strncmp(dso->short_name + 1, module,
>  				    dso->short_name_len - 2) == 0)
>  				goto found;
> diff --git a/tools/perf/util/symbol-elf.c b/tools/perf/util/symbol-elf.c
> index d753499..cbecc3d 100644
> --- a/tools/perf/util/symbol-elf.c
> +++ b/tools/perf/util/symbol-elf.c
> @@ -916,7 +916,7 @@ int dso__load_sym(struct dso *dso, struct map *map,
>  				}
>  				curr_dso->symtab_type = dso->symtab_type;
>  				map_groups__insert(kmap->kmaps, curr_map);
> -				dsos__add(&dso->node, curr_dso);
> +				dsos__add(dso->dsos, curr_dso);
>  				dso__set_loaded(curr_dso, map->type);
>  			} else
>  				curr_dso = curr_map->dso;
> -- 
> 1.7.1

Re: [PATCH v4 1/2] perf tool: encapsulate dsos list head into struct dsos

[Namhyung Kim]

Hi Arnaldo and Waiman,

On Fri, 26 Sep 2014 11:06:25 -0300, Arnaldo Carvalho de Melo wrote:
> Em Wed, Sep 24, 2014 at 11:45:39AM -0400, Waiman Long escreveu:
>> This is a precursor patch to enable long name searching of DSOs
>> using the rbtree. In this patch, a new dsos structure is created
>> which contains only a list head structure for the moment. The new
>> dsos structure is used, in turn, in the machine structure for the
>> user_dsos and kernel_dsos fields. Only the following 3 dsos functions
>> are modified to accept the new dsos structure parameter instead
>> of list_head:
>>  - dsos__add()
>>  - dsos__find()
>>  - __dsos__findnew()
>> 
>> Because of the need to find out the corresponding dsos structure to
>> properly call dsos__add() in dso__load_sym() of util/symbol-elf.c,
>> a new dsos field is also added to the dso structure.
>
> Argh, yeah, that is unfortunate that we need to add entries that deep
> inside dso__load_syms() :-\

But it seems we can use map->groups->machine to find out the head/root
of the dsos..

Thanks,
Namhyung

Re: [PATCH v4 1/2] perf tool: encapsulate dsos list head into struct dsos

[Waiman Long]

On 09/28/2014 11:54 PM, Namhyung Kim wrote:
> Hi Arnaldo and Waiman,
>
> On Fri, 26 Sep 2014 11:06:25 -0300, Arnaldo Carvalho de Melo wrote:
>> Em Wed, Sep 24, 2014 at 11:45:39AM -0400, Waiman Long escreveu:
>>> This is a precursor patch to enable long name searching of DSOs
>>> using the rbtree. In this patch, a new dsos structure is created
>>> which contains only a list head structure for the moment. The new
>>> dsos structure is used, in turn, in the machine structure for the
>>> user_dsos and kernel_dsos fields. Only the following 3 dsos functions
>>> are modified to accept the new dsos structure parameter instead
>>> of list_head:
>>>   - dsos__add()
>>>   - dsos__find()
>>>   - __dsos__findnew()
>>>
>>> Because of the need to find out the corresponding dsos structure to
>>> properly call dsos__add() in dso__load_sym() of util/symbol-elf.c,
>>> a new dsos field is also added to the dso structure.
>> Argh, yeah, that is unfortunate that we need to add entries that deep
>> inside dso__load_syms() :-\
> But it seems we can use map->groups->machine to find out the head/root
> of the dsos..
>
> Thanks,
> Namhyung
>

There are 2 dsos at the machine structure level - user_dsos and 
kernel_dsos. In this particular case, it should be kernel_dsos. I can 
remove the dsos pointer and hardcode it to use the kernel_dsos if you 
guys think it is acceptable.

-Longman

Re: [PATCH v4 1/2] perf tool: encapsulate dsos list head into struct dsos

[Arnaldo Carvalho de Melo]

Em Mon, Sep 29, 2014 at 01:30:07PM -0400, Waiman Long escreveu:
> On 09/28/2014 11:54 PM, Namhyung Kim wrote:
> >On Fri, 26 Sep 2014 11:06:25 -0300, Arnaldo Carvalho de Melo wrote:
> >>Em Wed, Sep 24, 2014 at 11:45:39AM -0400, Waiman Long escreveu:
> >>>This is a precursor patch to enable long name searching of DSOs
> >>>using the rbtree. In this patch, a new dsos structure is created
> >>>which contains only a list head structure for the moment. The new
> >>>dsos structure is used, in turn, in the machine structure for the
> >>>user_dsos and kernel_dsos fields. Only the following 3 dsos functions
> >>>are modified to accept the new dsos structure parameter instead
> >>>of list_head:
> >>>  - dsos__add()
> >>>  - dsos__find()
> >>>  - __dsos__findnew()
> >>>
> >>>Because of the need to find out the corresponding dsos structure to
> >>>properly call dsos__add() in dso__load_sym() of util/symbol-elf.c,
> >>>a new dsos field is also added to the dso structure.
> >>Argh, yeah, that is unfortunate that we need to add entries that deep
> >>inside dso__load_syms() :-\
> >But it seems we can use map->groups->machine to find out the head/root
> >of the dsos..

> There are 2 dsos at the machine structure level - user_dsos and kernel_dsos.
> In this particular case, it should be kernel_dsos. I can remove the dsos
> pointer and hardcode it to use the kernel_dsos if you guys think it is
> acceptable.

Yes, I think that if we have already how to obtain the head/root where
we want to insert things from structures present at that point in the
code, no need to add it to the per-dso data structure.

Thanks to Namhyung for finding an existing way of getting to the needed
data structures.

- Arnaldo

Re: [PATCH v4 1/2] perf tool: encapsulate dsos list head into struct dsos

[Waiman Long]

On 09/29/2014 02:09 PM, Arnaldo Carvalho de Melo wrote:
> Em Mon, Sep 29, 2014 at 01:30:07PM -0400, Waiman Long escreveu:
>> On 09/28/2014 11:54 PM, Namhyung Kim wrote:
>>> On Fri, 26 Sep 2014 11:06:25 -0300, Arnaldo Carvalho de Melo wrote:
>>>> Em Wed, Sep 24, 2014 at 11:45:39AM -0400, Waiman Long escreveu:
>>>>> This is a precursor patch to enable long name searching of DSOs
>>>>> using the rbtree. In this patch, a new dsos structure is created
>>>>> which contains only a list head structure for the moment. The new
>>>>> dsos structure is used, in turn, in the machine structure for the
>>>>> user_dsos and kernel_dsos fields. Only the following 3 dsos functions
>>>>> are modified to accept the new dsos structure parameter instead
>>>>> of list_head:
>>>>>   - dsos__add()
>>>>>   - dsos__find()
>>>>>   - __dsos__findnew()
>>>>>
>>>>> Because of the need to find out the corresponding dsos structure to
>>>>> properly call dsos__add() in dso__load_sym() of util/symbol-elf.c,
>>>>> a new dsos field is also added to the dso structure.
>>>> Argh, yeah, that is unfortunate that we need to add entries that deep
>>>> inside dso__load_syms() :-\
>>> But it seems we can use map->groups->machine to find out the head/root
>>> of the dsos..
>> There are 2 dsos at the machine structure level - user_dsos and kernel_dsos.
>> In this particular case, it should be kernel_dsos. I can remove the dsos
>> pointer and hardcode it to use the kernel_dsos if you guys think it is
>> acceptable.
> Yes, I think that if we have already how to obtain the head/root where
> we want to insert things from structures present at that point in the
> code, no need to add it to the per-dso data structure.
>
> Thanks to Namhyung for finding an existing way of getting to the needed
> data structures.
>
> - Arnaldo

Sure, I will send out a new patch which includes the suggested change.

Thanks for the review.

-Longman

Re: [PATCH v4 1/2] perf tool: encapsulate dsos list head into struct dsos

[Arnaldo Carvalho de Melo]

Em Wed, Sep 24, 2014 at 11:45:39AM -0400, Waiman Long escreveu:
> This is a precursor patch to enable long name searching of DSOs
> using the rbtree. In this patch, a new dsos structure is created
> which contains only a list head structure for the moment. The new
> dsos structure is used, in turn, in the machine structure for the
> user_dsos and kernel_dsos fields. Only the following 3 dsos functions
> are modified to accept the new dsos structure parameter instead
> of list_head:
>  - dsos__add()
>  - dsos__find()
>  - __dsos__findnew()
> 
> Because of the need to find out the corresponding dsos structure to
> properly call dsos__add() in dso__load_sym() of util/symbol-elf.c,
> a new dsos field is also added to the dso structure.

What tree did you use to produce these patches? I just tried on my
perf/core branch and I get some fuzzes:

[acme@zoo linux]$ patch -p1 < /wb/1.patch 
patching file tools/perf/util/dso.c
Hunk #1 succeeded at 755 (offset 2 lines).
Hunk #2 succeeded at 852 (offset 2 lines).
patching file tools/perf/util/dso.h
patching file tools/perf/util/header.c
patching file tools/perf/util/machine.c
Hunk #2 succeeded at 72 (offset 2 lines).
Hunk #3 succeeded at 477 (offset 29 lines).
Hunk #4 succeeded at 994 (offset 29 lines).
patching file tools/perf/util/machine.h
Hunk #2 succeeded at 39 with fuzz 1 (offset 1 line).
patching file tools/perf/util/probe-event.c
patching file tools/perf/util/symbol-elf.c
Hunk #1 succeeded at 929 (offset 13 lines).
[acme@zoo linux]$

I'll fix this up, probably harmless, just a heads up.

- Arnaldo

Re: [PATCH v4 1/2] perf tool: encapsulate dsos list head into struct dsos

[Waiman Long]

On 09/26/2014 10:12 AM, Arnaldo Carvalho de Melo wrote:
> Em Wed, Sep 24, 2014 at 11:45:39AM -0400, Waiman Long escreveu:
>> This is a precursor patch to enable long name searching of DSOs
>> using the rbtree. In this patch, a new dsos structure is created
>> which contains only a list head structure for the moment. The new
>> dsos structure is used, in turn, in the machine structure for the
>> user_dsos and kernel_dsos fields. Only the following 3 dsos functions
>> are modified to accept the new dsos structure parameter instead
>> of list_head:
>>   - dsos__add()
>>   - dsos__find()
>>   - __dsos__findnew()
>>
>> Because of the need to find out the corresponding dsos structure to
>> properly call dsos__add() in dso__load_sym() of util/symbol-elf.c,
>> a new dsos field is also added to the dso structure.
> What tree did you use to produce these patches? I just tried on my
> perf/core branch and I get some fuzzes:
>
> [acme@zoo linux]$ patch -p1<  /wb/1.patch
> patching file tools/perf/util/dso.c
> Hunk #1 succeeded at 755 (offset 2 lines).
> Hunk #2 succeeded at 852 (offset 2 lines).
> patching file tools/perf/util/dso.h
> patching file tools/perf/util/header.c
> patching file tools/perf/util/machine.c
> Hunk #2 succeeded at 72 (offset 2 lines).
> Hunk #3 succeeded at 477 (offset 29 lines).
> Hunk #4 succeeded at 994 (offset 29 lines).
> patching file tools/perf/util/machine.h
> Hunk #2 succeeded at 39 with fuzz 1 (offset 1 line).
> patching file tools/perf/util/probe-event.c
> patching file tools/perf/util/symbol-elf.c
> Hunk #1 succeeded at 929 (offset 13 lines).
> [acme@zoo linux]$
>
> I'll fix this up, probably harmless, just a heads up.
>
> - Arnaldo

I was using the latest linux 3.17 tree. I should have used the tip tree 
instead. I will use that if I need to sent out a new patch.

-Longman

Re: [PATCH v4 1/2] perf tool: encapsulate dsos list head into struct dsos

[Arnaldo Carvalho de Melo]

Em Mon, Sep 29, 2014 at 01:26:55PM -0400, Waiman Long escreveu:
> On 09/26/2014 10:12 AM, Arnaldo Carvalho de Melo wrote:
> >Em Wed, Sep 24, 2014 at 11:45:39AM -0400, Waiman Long escreveu:
> >>This is a precursor patch to enable long name searching of DSOs
> >>using the rbtree. In this patch, a new dsos structure is created
> >>which contains only a list head structure for the moment. The new
> >>dsos structure is used, in turn, in the machine structure for the
> >>user_dsos and kernel_dsos fields. Only the following 3 dsos functions
> >>are modified to accept the new dsos structure parameter instead
> >>of list_head:
> >>  - dsos__add()
> >>  - dsos__find()
> >>  - __dsos__findnew()
> >>
> >>Because of the need to find out the corresponding dsos structure to
> >>properly call dsos__add() in dso__load_sym() of util/symbol-elf.c,
> >>a new dsos field is also added to the dso structure.
> >What tree did you use to produce these patches? I just tried on my
> >perf/core branch and I get some fuzzes:
> >
> >[acme@zoo linux]$ patch -p1<  /wb/1.patch
> >patching file tools/perf/util/dso.c
> >Hunk #1 succeeded at 755 (offset 2 lines).
> >Hunk #2 succeeded at 852 (offset 2 lines).
> >patching file tools/perf/util/dso.h
> >patching file tools/perf/util/header.c
> >patching file tools/perf/util/machine.c
> >Hunk #2 succeeded at 72 (offset 2 lines).
> >Hunk #3 succeeded at 477 (offset 29 lines).
> >Hunk #4 succeeded at 994 (offset 29 lines).
> >patching file tools/perf/util/machine.h
> >Hunk #2 succeeded at 39 with fuzz 1 (offset 1 line).
> >patching file tools/perf/util/probe-event.c
> >patching file tools/perf/util/symbol-elf.c
> >Hunk #1 succeeded at 929 (offset 13 lines).
> >[acme@zoo linux]$
> >
> >I'll fix this up, probably harmless, just a heads up.
> >
> >- Arnaldo
> 
> I was using the latest linux 3.17 tree. I should have used the tip tree
> instead. I will use that if I need to sent out a new patch.

Please do, tip/perf/urgent strictly for bug fixes, tip/perf/core for new
features or bug fixes for things that are only in tip/perf/core.

- Arnaldo

[PATCH v4 2/2] perf tool: improves DSO long names lookup speed with rbtree

[Waiman Long]

With workload that spawns and destroys many threads and processes,
it was found that perf-mem could took a long time to post-process
the perf data after the target workload had completed its operation.
The performance bottleneck was found to be the lookup and insertion
of the new DSO structures (thousands of them in this case).

In a dual-socket Ivy-Bridge E7-4890 v2 machine (30-core, 60-thread),
the perf profile below shows what perf was doing after the profiled
AIM7 shared workload completed:

-     83.94%  perf  libc-2.11.3.so     [.] __strcmp_sse42
   - __strcmp_sse42
      - 99.82% map__new
           machine__process_mmap_event
           perf_session_deliver_event
           perf_session__process_event
           __perf_session__process_events
           cmd_record
           cmd_mem
           run_builtin
           main
           __libc_start_main
-     13.17%  perf  perf               [.] __dsos__findnew
     __dsos__findnew
     map__new
     machine__process_mmap_event
     perf_session_deliver_event
     perf_session__process_event
     __perf_session__process_events
     cmd_record
     cmd_mem
     run_builtin
     main
     __libc_start_main

So about 97% of CPU times were spent in the map__new() function
trying to insert new DSO entry into the DSO linked list. The whole
post-processing step took about 9 minutes.

The DSO structures are currently searched linearly. So the total
processing time will be proportional to n^2.

To overcome this performance problem, the DSO code is modified to
also put the DSO structures in a RB tree sorted by its long name
in additional to being in a simple linked list. With this change,
the processing time will become proportional to n*log(n) which will
be much quicker for large n. However, the short name will still be
searched using the old linear searching method.  With that patch
in place, the same perf-mem post-processing step took less than 30
seconds to complete.

Signed-off-by: Waiman Long <Waiman.Long@hp.com>
---
 tools/perf/util/dso.c     |   73 ++++++++++++++++++++++++++++++++++++++++++--
 tools/perf/util/dso.h     |    1 +
 tools/perf/util/machine.h |    4 ++-
 3 files changed, 73 insertions(+), 5 deletions(-)

diff --git a/tools/perf/util/dso.c b/tools/perf/util/dso.c
index c2c6134..810a4b5 100644
--- a/tools/perf/util/dso.c
+++ b/tools/perf/util/dso.c
@@ -651,6 +651,67 @@ 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;
+	int warned = false;
+
+	if (!name)
+		name = dso->long_name;
+	/*
+	 * Find node with the matching name
+	 */
+	while (*p) {
+		struct dso *this = rb_entry(*p, struct dso, rb_node);
+		long rc = (long)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 & sort the entry
+			 * by its DSO address.
+			 */
+			if (!dso || (dso == this))
+				return this;	/* Find matching dso */
+			/*
+			 * The kernel DSOs may have duplicated long name,
+			 * so don't print warning for them.
+			 */
+			if (!warned && !strstr(name, "kernel.kallsyms")
+				    && !strstr(name, "/vmlinux")) {
+				pr_warning("Duplicated dso long name: %s\n",
+					   name);
+				warned = true;
+			}
+			rc = (long)dso - (long)this;
+		}
+		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(struct rb_root *root, const char *name)
+{
+	return dso__findlink_by_longname(root, NULL, name);
+}
+
 void dso__set_long_name(struct dso *dso, const char *name, bool name_allocated)
 {
 	if (name == NULL)
@@ -754,6 +815,7 @@ struct dso *dso__new(const char *name)
 		dso->kernel = DSO_TYPE_USER;
 		dso->needs_swap = DSO_SWAP__UNSET;
 		dso->dsos = NULL;
+		RB_CLEAR_NODE(&dso->rb_node);
 		INIT_LIST_HEAD(&dso->node);
 		INIT_LIST_HEAD(&dso->data.open_entry);
 	}
@@ -776,6 +838,11 @@ void dso__delete(struct dso *dso)
 		zfree((char **)&dso->long_name);
 		dso->long_name_allocated = false;
 	}
+	if (dso->dsos) {
+		/* Remove entry from rbtree */
+		rb_erase(&dso->rb_node, &dso->dsos->root);
+		dso->dsos = NULL;
+	}
 
 	dso__data_close(dso);
 	dso_cache__free(&dso->data.cache);
@@ -854,6 +921,7 @@ void dsos__add(struct dsos *dsos, struct dso *dso)
 {
 	dso->dsos = dsos;
 	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 +935,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((struct rb_root *)&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 cadfef7..bae7042 100644
--- a/tools/perf/util/dso.h
+++ b/tools/perf/util/dso.h
@@ -94,6 +94,7 @@ struct dsos;
 
 struct dso {
 	struct list_head node;
+	struct rb_node	 rb_node;	/* rbtree node sorted by long name */
 	struct dsos      *dsos;
 	struct rb_root	 symbols[MAP__NR_TYPES];
 	struct rb_root	 symbol_names[MAP__NR_TYPES];
diff --git a/tools/perf/util/machine.h b/tools/perf/util/machine.h
index d8abb6c..f7546f3 100644
--- a/tools/perf/util/machine.h
+++ b/tools/perf/util/machine.h
@@ -23,10 +23,12 @@ extern const char *ref_reloc_sym_names[];
 struct vdso_info;
 
 /*
- * 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 machine {
-- 
1.7.1

Re: [PATCH v4 2/2] perf tool: improves DSO long names lookup speed with rbtree

[Arnaldo Carvalho de Melo]

Em Wed, Sep 24, 2014 at 11:45:40AM -0400, Waiman Long escreveu:
> With workload that spawns and destroys many threads and processes,
> it was found that perf-mem could took a long time to post-process
> the perf data after the target workload had completed its operation.
> The performance bottleneck was found to be the lookup and insertion
> of the new DSO structures (thousands of them in this case).
> 
> In a dual-socket Ivy-Bridge E7-4890 v2 machine (30-core, 60-thread),
> the perf profile below shows what perf was doing after the profiled
> AIM7 shared workload completed:
> 
> -     83.94%  perf  libc-2.11.3.so     [.] __strcmp_sse42
>    - __strcmp_sse42
>       - 99.82% map__new
>            machine__process_mmap_event
>            perf_session_deliver_event
>            perf_session__process_event
>            __perf_session__process_events
>            cmd_record
>            cmd_mem
>            run_builtin
>            main
>            __libc_start_main
> -     13.17%  perf  perf               [.] __dsos__findnew
>      __dsos__findnew
>      map__new
>      machine__process_mmap_event
>      perf_session_deliver_event
>      perf_session__process_event
>      __perf_session__process_events
>      cmd_record
>      cmd_mem
>      run_builtin
>      main
>      __libc_start_main
> 
> So about 97% of CPU times were spent in the map__new() function
> trying to insert new DSO entry into the DSO linked list. The whole
> post-processing step took about 9 minutes.
> 
> The DSO structures are currently searched linearly. So the total
> processing time will be proportional to n^2.
> 
> To overcome this performance problem, the DSO code is modified to
> also put the DSO structures in a RB tree sorted by its long name
> in additional to being in a simple linked list. With this change,
> the processing time will become proportional to n*log(n) which will
> be much quicker for large n. However, the short name will still be
> searched using the old linear searching method.  With that patch
> in place, the same perf-mem post-processing step took less than 30
> seconds to complete.
> 
> Signed-off-by: Waiman Long <Waiman.Long@hp.com>
> ---
>  tools/perf/util/dso.c     |   73 ++++++++++++++++++++++++++++++++++++++++++--
>  tools/perf/util/dso.h     |    1 +
>  tools/perf/util/machine.h |    4 ++-
>  3 files changed, 73 insertions(+), 5 deletions(-)
> 
> diff --git a/tools/perf/util/dso.c b/tools/perf/util/dso.c
> index c2c6134..810a4b5 100644
> --- a/tools/perf/util/dso.c
> +++ b/tools/perf/util/dso.c
> @@ -651,6 +651,67 @@ 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;
> +	int warned = false;
> +
> +	if (!name)
> +		name = dso->long_name;
> +	/*
> +	 * Find node with the matching name
> +	 */
> +	while (*p) {
> +		struct dso *this = rb_entry(*p, struct dso, rb_node);
> +		long rc = (long)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 & sort the entry
> +			 * by its DSO address.
> +			 */
> +			if (!dso || (dso == this))
> +				return this;	/* Find matching dso */
> +			/*
> +			 * The kernel DSOs may have duplicated long name,
> +			 * so don't print warning for them.
> +			 */
> +			if (!warned && !strstr(name, "kernel.kallsyms")
> +				    && !strstr(name, "/vmlinux")) {
> +				pr_warning("Duplicated dso long name: %s\n",
> +					   name);

Huh? Can you elaborate on this? Ho can we add multiple DSOs with the
exact same name into this tree? Have you actually seen this in practice?
I guess so, judging by the comment above ("may have").

I'll try the patch to see if I get these warnings...

But initial reaction to these long casts and fallbacking to pointer
arithmetic for tree searching/inserting looked ugly :-\

- Arnaldo

> +				warned = true;
> +			}
> +			rc = (long)dso - (long)this;
> +		}
> +		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(struct rb_root *root, const char *name)
> +{
> +	return dso__findlink_by_longname(root, NULL, name);
> +}
> +
>  void dso__set_long_name(struct dso *dso, const char *name, bool name_allocated)
>  {
>  	if (name == NULL)
> @@ -754,6 +815,7 @@ struct dso *dso__new(const char *name)
>  		dso->kernel = DSO_TYPE_USER;
>  		dso->needs_swap = DSO_SWAP__UNSET;
>  		dso->dsos = NULL;
> +		RB_CLEAR_NODE(&dso->rb_node);
>  		INIT_LIST_HEAD(&dso->node);
>  		INIT_LIST_HEAD(&dso->data.open_entry);
>  	}
> @@ -776,6 +838,11 @@ void dso__delete(struct dso *dso)
>  		zfree((char **)&dso->long_name);
>  		dso->long_name_allocated = false;
>  	}
> +	if (dso->dsos) {
> +		/* Remove entry from rbtree */
> +		rb_erase(&dso->rb_node, &dso->dsos->root);
> +		dso->dsos = NULL;
> +	}
>  
>  	dso__data_close(dso);
>  	dso_cache__free(&dso->data.cache);
> @@ -854,6 +921,7 @@ void dsos__add(struct dsos *dsos, struct dso *dso)
>  {
>  	dso->dsos = dsos;
>  	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 +935,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((struct rb_root *)&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 cadfef7..bae7042 100644
> --- a/tools/perf/util/dso.h
> +++ b/tools/perf/util/dso.h
> @@ -94,6 +94,7 @@ struct dsos;
>  
>  struct dso {
>  	struct list_head node;
> +	struct rb_node	 rb_node;	/* rbtree node sorted by long name */
>  	struct dsos      *dsos;
>  	struct rb_root	 symbols[MAP__NR_TYPES];
>  	struct rb_root	 symbol_names[MAP__NR_TYPES];
> diff --git a/tools/perf/util/machine.h b/tools/perf/util/machine.h
> index d8abb6c..f7546f3 100644
> --- a/tools/perf/util/machine.h
> +++ b/tools/perf/util/machine.h
> @@ -23,10 +23,12 @@ extern const char *ref_reloc_sym_names[];
>  struct vdso_info;
>  
>  /*
> - * 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 machine {
> -- 
> 1.7.1

Re: [PATCH v4 2/2] perf tool: improves DSO long names lookup speed with rbtree

[Namhyung Kim]

On Fri, 26 Sep 2014 11:22:34 -0300, Arnaldo Carvalho de Melo wrote:
> Em Wed, Sep 24, 2014 at 11:45:40AM -0400, Waiman Long escreveu:
>> +	/*
>> +	 * Find node with the matching name
>> +	 */
>> +	while (*p) {
>> +		struct dso *this = rb_entry(*p, struct dso, rb_node);
>> +		long rc = (long)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 & sort the entry
>> +			 * by its DSO address.
>> +			 */
>> +			if (!dso || (dso == this))
>> +				return this;	/* Find matching dso */
>> +			/*
>> +			 * The kernel DSOs may have duplicated long name,
>> +			 * so don't print warning for them.
>> +			 */
>> +			if (!warned && !strstr(name, "kernel.kallsyms")
>> +				    && !strstr(name, "/vmlinux")) {
>> +				pr_warning("Duplicated dso long name: %s\n",
>> +					   name);
>
> Huh? Can you elaborate on this? Ho can we add multiple DSOs with the
> exact same name into this tree? Have you actually seen this in practice?
> I guess so, judging by the comment above ("may have").

I guess it's because we split maps and dsos by section name (for kernel
only).  Please look at dso__load_sym() - If map_groups__find_by_name()
with short name + section name fails, it creates a new dso and map, and
then curr_dso->long_name will be set as dso->long_name.

Thanks,
Namhyung


>
> I'll try the patch to see if I get these warnings...
>
> But initial reaction to these long casts and fallbacking to pointer
> arithmetic for tree searching/inserting looked ugly :-\

Re: [PATCH v4 2/2] perf tool: improves DSO long names lookup speed with rbtree

[Waiman Long]

On 09/29/2014 12:02 AM, Namhyung Kim wrote:
> On Fri, 26 Sep 2014 11:22:34 -0300, Arnaldo Carvalho de Melo wrote:
>> Em Wed, Sep 24, 2014 at 11:45:40AM -0400, Waiman Long escreveu:
>>> +	/*
>>> +	 * Find node with the matching name
>>> +	 */
>>> +	while (*p) {
>>> +		struct dso *this = rb_entry(*p, struct dso, rb_node);
>>> +		long rc = (long)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&  sort the entry
>>> +			 * by its DSO address.
>>> +			 */
>>> +			if (!dso || (dso == this))
>>> +				return this;	/* Find matching dso */
>>> +			/*
>>> +			 * The kernel DSOs may have duplicated long name,
>>> +			 * so don't print warning for them.
>>> +			 */
>>> +			if (!warned&&  !strstr(name, "kernel.kallsyms")
>>> +				&&  !strstr(name, "/vmlinux")) {
>>> +				pr_warning("Duplicated dso long name: %s\n",
>>> +					   name);
>> Huh? Can you elaborate on this? Ho can we add multiple DSOs with the
>> exact same name into this tree? Have you actually seen this in practice?
>> I guess so, judging by the comment above ("may have").
> I guess it's because we split maps and dsos by section name (for kernel
> only).  Please look at dso__load_sym() - If map_groups__find_by_name()
> with short name + section name fails, it creates a new dso and map, and
> then curr_dso->long_name will be set as dso->long_name.
>
> Thanks,
> Namhyung
>

Yes, it is where I found that the different DSOs may have the same long 
name.

-Longman