Re: [PATCH 14/37] perf tools: Convert dead thread list into rbtree

2014-12-28 Thread Namhyung Kim 
Hi David,

On Sun, Dec 28, 2014 at 12:31 AM, David Ahern  wrote:
> On 12/24/14 12:15 AM, Namhyung Kim wrote:
>>
>> @@ -106,8 +117,8 @@ void machine__delete_threads(struct machine *machine)
>> while (nd) {
>> struct thread *t = rb_entry(nd, struct thread, rb_node);
>>
>> -   rb_erase(&t->rb_node, &machine->threads);
>> nd = rb_next(nd);
>> +   rb_erase(&t->rb_node, &machine->threads);
>> thread__delete(t);
>> }
>>   }
>
>
> unrelated to dead threads. Bug fix? separate patch?

Yes, I'll make it a separate bug-fix patch.


>
>
>> @@ -1236,13 +1247,36 @@ int machine__process_mmap_event(struct machine
>> *machine, union perf_event *event
>>
>>   static void machine__remove_thread(struct machine *machine, struct
>> thread *th)
>>   {
>> +   struct rb_node **p = &machine->dead_threads.rb_node;
>> +   struct rb_node *parent = NULL;
>> +   struct thread *pos;
>> +
>> machine->last_match = NULL;
>> rb_erase(&th->rb_node, &machine->threads);
>> +
>> +   th->dead = true;
>> +
>> /*
>>  * We may have references to this thread, for instance in some
>> hist_entry
>> -* instances, so just move them to a separate list.
>> +* instances, so just move them to a separate list in rbtree.
>>  */
>> -   list_add_tail(&th->node, &machine->dead_threads);
>> +   while (*p != NULL) {
>> +   parent = *p;
>> +   pos = rb_entry(parent, struct thread, rb_node);
>> +
>> +   if (pos->tid == th->tid) {
>> +   list_add_tail(&th->node, &pos->node);
>> +   return;
>> +   }
>
>
> So you have a linked list for tid collisions (not mentioned in the git log).

Right, will add a description.


>
>> +
>> +   if (th->tid < pos->tid)
>> +   p = &(*p)->rb_left;
>> +   else
>> +   p = &(*p)->rb_right;
>> +   }
>> +
>> +   rb_link_node(&th->rb_node, parent, p);
>> +   rb_insert_color(&th->rb_node, &machine->dead_threads);
>>   }
>>
>>   int machine__process_fork_event(struct machine *machine, union
>> perf_event *event,
>> @@ -1649,7 +1683,7 @@ int machine__for_each_thread(struct machine
>> *machine,
>
>
> ---8<---
>
>> diff --git a/tools/perf/util/thread.h b/tools/perf/util/thread.h
>> index 0b6dcd70bc8b..413f28cf689b 100644
>> --- a/tools/perf/util/thread.h
>> +++ b/tools/perf/util/thread.h
>> @@ -11,10 +11,8 @@
>>   struct thread_stack;
>>
>>   struct thread {
>> -   union {
>> -   struct rb_node   rb_node;
>> -   struct list_head node;
>> -   };
>> +   struct rb_node  rb_node;
>> +   struct list_headnode;
>> struct map_groups   *mg;
>> pid_t   pid_; /* Not all tools update this */
>> pid_t   tid;
>
>
> could use better names for rb_node and node. rb_node is the entry in the
> dead_threads tree - dead_node?; node is the linked list for tid collisions -
> tid_node?

But the rb_node is used for 3 different purpose depends on its state -
a thread can be in a (normal) threads tree, dead threads tree or
missing threads tree (will be introduced later).

Thanks,
Namhyung
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH 14/37] perf tools: Convert dead thread list into rbtree

2014-12-27 Thread David Ahern 

On 12/24/14 12:15 AM, Namhyung Kim wrote:

@@ -106,8 +117,8 @@ void machine__delete_threads(struct machine *machine)
while (nd) {
struct thread *t = rb_entry(nd, struct thread, rb_node);

-   rb_erase(&t->rb_node, &machine->threads);
nd = rb_next(nd);
+   rb_erase(&t->rb_node, &machine->threads);
thread__delete(t);
}
  }


unrelated to dead threads. Bug fix? separate patch?



@@ -1236,13 +1247,36 @@ int machine__process_mmap_event(struct machine 
*machine, union perf_event *event

  static void machine__remove_thread(struct machine *machine, struct thread *th)
  {
+   struct rb_node **p = &machine->dead_threads.rb_node;
+   struct rb_node *parent = NULL;
+   struct thread *pos;
+
machine->last_match = NULL;
rb_erase(&th->rb_node, &machine->threads);
+
+   th->dead = true;
+
/*
 * We may have references to this thread, for instance in some 
hist_entry
-* instances, so just move them to a separate list.
+* instances, so just move them to a separate list in rbtree.
 */
-   list_add_tail(&th->node, &machine->dead_threads);
+   while (*p != NULL) {
+   parent = *p;
+   pos = rb_entry(parent, struct thread, rb_node);
+
+   if (pos->tid == th->tid) {
+   list_add_tail(&th->node, &pos->node);
+   return;
+   }


So you have a linked list for tid collisions (not mentioned in the git log).


+
+   if (th->tid < pos->tid)
+   p = &(*p)->rb_left;
+   else
+   p = &(*p)->rb_right;
+   }
+
+   rb_link_node(&th->rb_node, parent, p);
+   rb_insert_color(&th->rb_node, &machine->dead_threads);
  }

  int machine__process_fork_event(struct machine *machine, union perf_event 
*event,
@@ -1649,7 +1683,7 @@ int machine__for_each_thread(struct machine *machine,


---8<---


diff --git a/tools/perf/util/thread.h b/tools/perf/util/thread.h
index 0b6dcd70bc8b..413f28cf689b 100644
--- a/tools/perf/util/thread.h
+++ b/tools/perf/util/thread.h
@@ -11,10 +11,8 @@
  struct thread_stack;

  struct thread {
-   union {
-   struct rb_node   rb_node;
-   struct list_head node;
-   };
+   struct rb_node  rb_node;
+   struct list_headnode;
struct map_groups   *mg;
pid_t   pid_; /* Not all tools update this */
pid_t   tid;


could use better names for rb_node and node. rb_node is the entry in the 
dead_threads tree - dead_node?; node is the linked list for tid 
collisions - tid_node?


David
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH 14/37] perf tools: Convert dead thread list into rbtree

2014-12-26 Thread Namhyung Kim 
On Sat, Dec 27, 2014 at 2:14 AM, David Ahern  wrote:
> On 12/25/14 7:26 PM, Namhyung Kim wrote:

 diff --git a/tools/perf/util/thread.h b/tools/perf/util/thread.h
 index 0b6dcd70bc8b..413f28cf689b 100644
 --- a/tools/perf/util/thread.h
 +++ b/tools/perf/util/thread.h
 @@ -11,10 +11,8 @@
   struct thread_stack;

   struct thread {
 - union {
 - struct rb_node   rb_node;
 - struct list_head node;
 - };
 + struct rb_node  rb_node;
 + struct list_headnode;
struct map_groups   *mg;
pid_t   pid_; /* Not all tools update this */
pid_t   tid;
 @@ -22,7 +20,8 @@ struct thread {
int cpu;
charshortname[3];
boolcomm_set;
 - booldead; /* if set thread has exited */
 + boolexited; /* if set thread has exited */
 + booldead; /* thread is in dead_threads list */
>>>
>>>
>>> looks like this also changes the logic (new exited flag),
>>> not just the dead threads storage wheel
>>
>>
>> AFAICS the 'dead' flag is not used other than thread__exited().  And
>> it confused me a dead thread might not be in a dead_threads tree (or
>> list).  So I changed the name and no logical change intended.
>
>
> git show 236a3bbd5cb51

Thanks for the pointer.  I understand the need of delaying the move to
dead_threads list, but anyway it still makes me confused.  So I
renamed the flag to keep the current behavior and match the name
'dead' to the list/tree management to reduce further confusion.

Thanks,
Namhyung
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH 14/37] perf tools: Convert dead thread list into rbtree

2014-12-26 Thread David Ahern 

On 12/25/14 7:26 PM, Namhyung Kim wrote:

diff --git a/tools/perf/util/thread.h b/tools/perf/util/thread.h
index 0b6dcd70bc8b..413f28cf689b 100644
--- a/tools/perf/util/thread.h
+++ b/tools/perf/util/thread.h
@@ -11,10 +11,8 @@
  struct thread_stack;

  struct thread {
- union {
- struct rb_node   rb_node;
- struct list_head node;
- };
+ struct rb_node  rb_node;
+ struct list_headnode;
   struct map_groups   *mg;
   pid_t   pid_; /* Not all tools update this */
   pid_t   tid;
@@ -22,7 +20,8 @@ struct thread {
   int cpu;
   charshortname[3];
   boolcomm_set;
- booldead; /* if set thread has exited */
+ boolexited; /* if set thread has exited */
+ booldead; /* thread is in dead_threads list */


looks like this also changes the logic (new exited flag),
not just the dead threads storage wheel


AFAICS the 'dead' flag is not used other than thread__exited().  And
it confused me a dead thread might not be in a dead_threads tree (or
list).  So I changed the name and no logical change intended.


git show 236a3bbd5cb51

David

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH 14/37] perf tools: Convert dead thread list into rbtree

2014-12-25 Thread Namhyung Kim 
On Fri, Dec 26, 2014 at 8:05 AM, Jiri Olsa  wrote:
> On Wed, Dec 24, 2014 at 04:15:10PM +0900, Namhyung Kim wrote:
>
> SNIP
>
>>
>>  static void machine__remove_thread(struct machine *machine, struct thread 
>> *th)
>>  {
>> + struct rb_node **p = &machine->dead_threads.rb_node;
>> + struct rb_node *parent = NULL;
>> + struct thread *pos;
>> +
>>   machine->last_match = NULL;
>>   rb_erase(&th->rb_node, &machine->threads);
>> +
>> + th->dead = true;
>> +
>>   /*
>>* We may have references to this thread, for instance in some 
>> hist_entry
>> -  * instances, so just move them to a separate list.
>> +  * instances, so just move them to a separate list in rbtree.
>>*/
>> - list_add_tail(&th->node, &machine->dead_threads);
>> + while (*p != NULL) {
>> + parent = *p;
>> + pos = rb_entry(parent, struct thread, rb_node);
>> +
>> + if (pos->tid == th->tid) {
>> + list_add_tail(&th->node, &pos->node);
>> + return;
>> + }
>
> hum, why is this 'new list' in thread object necessary? why not
> to store all in the tree?

No absolute reason, but I just wanted to keep them in a single place
and to see how many of them exist easily.  We could compare pid and
then timestamp so that it can be in a single rbtree.

>
>
>> +
>> + if (th->tid < pos->tid)
>> + p = &(*p)->rb_left;
>> + else
>> + p = &(*p)->rb_right;
>> + }
>> +
>
> SNIP
>
>> diff --git a/tools/perf/util/thread.h b/tools/perf/util/thread.h
>> index 0b6dcd70bc8b..413f28cf689b 100644
>> --- a/tools/perf/util/thread.h
>> +++ b/tools/perf/util/thread.h
>> @@ -11,10 +11,8 @@
>>  struct thread_stack;
>>
>>  struct thread {
>> - union {
>> - struct rb_node   rb_node;
>> - struct list_head node;
>> - };
>> + struct rb_node  rb_node;
>> + struct list_headnode;
>>   struct map_groups   *mg;
>>   pid_t   pid_; /* Not all tools update this */
>>   pid_t   tid;
>> @@ -22,7 +20,8 @@ struct thread {
>>   int cpu;
>>   charshortname[3];
>>   boolcomm_set;
>> - booldead; /* if set thread has exited */
>> + boolexited; /* if set thread has exited */
>> + booldead; /* thread is in dead_threads list */
>
> looks like this also changes the logic (new exited flag),
> not just the dead threads storage wheel

AFAICS the 'dead' flag is not used other than thread__exited().  And
it confused me a dead thread might not be in a dead_threads tree (or
list).  So I changed the name and no logical change intended.

Thanks,
Namhyung
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH 14/37] perf tools: Convert dead thread list into rbtree

2014-12-25 Thread Jiri Olsa 
On Wed, Dec 24, 2014 at 04:15:10PM +0900, Namhyung Kim wrote:

SNIP

>  
>  static void machine__remove_thread(struct machine *machine, struct thread 
> *th)
>  {
> + struct rb_node **p = &machine->dead_threads.rb_node;
> + struct rb_node *parent = NULL;
> + struct thread *pos;
> +
>   machine->last_match = NULL;
>   rb_erase(&th->rb_node, &machine->threads);
> +
> + th->dead = true;
> +
>   /*
>* We may have references to this thread, for instance in some 
> hist_entry
> -  * instances, so just move them to a separate list.
> +  * instances, so just move them to a separate list in rbtree.
>*/
> - list_add_tail(&th->node, &machine->dead_threads);
> + while (*p != NULL) {
> + parent = *p;
> + pos = rb_entry(parent, struct thread, rb_node);
> +
> + if (pos->tid == th->tid) {
> + list_add_tail(&th->node, &pos->node);
> + return;
> + }

hum, why is this 'new list' in thread object necessary? why not
to store all in the tree?


> +
> + if (th->tid < pos->tid)
> + p = &(*p)->rb_left;
> + else
> + p = &(*p)->rb_right;
> + }
> +

SNIP

> diff --git a/tools/perf/util/thread.h b/tools/perf/util/thread.h
> index 0b6dcd70bc8b..413f28cf689b 100644
> --- a/tools/perf/util/thread.h
> +++ b/tools/perf/util/thread.h
> @@ -11,10 +11,8 @@
>  struct thread_stack;
>  
>  struct thread {
> - union {
> - struct rb_node   rb_node;
> - struct list_head node;
> - };
> + struct rb_node  rb_node;
> + struct list_headnode;
>   struct map_groups   *mg;
>   pid_t   pid_; /* Not all tools update this */
>   pid_t   tid;
> @@ -22,7 +20,8 @@ struct thread {
>   int cpu;
>   charshortname[3];
>   boolcomm_set;
> - booldead; /* if set thread has exited */
> + boolexited; /* if set thread has exited */
> + booldead; /* thread is in dead_threads list */

looks like this also changes the logic (new exited flag),
not just the dead threads storage wheel

jirka
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[PATCH 14/37] perf tools: Convert dead thread list into rbtree

2014-12-23 Thread Namhyung Kim 
Currently perf maintains dead threads in a linked list but this can be
a problem if someone needs to search from it.  Convert it to a rbtree
like normal threads and it'll be used later with multi-file changes.

Cc: Frederic Weisbecker 
Signed-off-by: Namhyung Kim 
---
 tools/perf/util/machine.c | 59 +++
 tools/perf/util/machine.h |  2 +-
 tools/perf/util/thread.c  |  1 +
 tools/perf/util/thread.h  | 11 -
 4 files changed, 57 insertions(+), 16 deletions(-)

diff --git a/tools/perf/util/machine.c b/tools/perf/util/machine.c
index 15dd0a9691ce..582e011adc92 100644
--- a/tools/perf/util/machine.c
+++ b/tools/perf/util/machine.c
@@ -28,7 +28,7 @@ int machine__init(struct machine *machine, const char 
*root_dir, pid_t pid)
dsos__init(&machine->kernel_dsos);
 
machine->threads = RB_ROOT;
-   INIT_LIST_HEAD(&machine->dead_threads);
+   machine->dead_threads = RB_ROOT;
machine->last_match = NULL;
 
machine->vdso_info = NULL;
@@ -91,10 +91,21 @@ static void dsos__delete(struct dsos *dsos)
 
 void machine__delete_dead_threads(struct machine *machine)
 {
-   struct thread *n, *t;
+   struct rb_node *nd = rb_first(&machine->dead_threads);
+
+   while (nd) {
+   struct thread *t = rb_entry(nd, struct thread, rb_node);
+   struct thread *pos;
+
+   nd = rb_next(nd);
+   rb_erase(&t->rb_node, &machine->dead_threads);
+
+   while (!list_empty(&t->node)) {
+   pos = list_first_entry(&t->node, struct thread, node);
+   list_del(&pos->node);
+   thread__delete(pos);
+   }
 
-   list_for_each_entry_safe(t, n, &machine->dead_threads, node) {
-   list_del(&t->node);
thread__delete(t);
}
 }
@@ -106,8 +117,8 @@ void machine__delete_threads(struct machine *machine)
while (nd) {
struct thread *t = rb_entry(nd, struct thread, rb_node);
 
-   rb_erase(&t->rb_node, &machine->threads);
nd = rb_next(nd);
+   rb_erase(&t->rb_node, &machine->threads);
thread__delete(t);
}
 }
@@ -1236,13 +1247,36 @@ int machine__process_mmap_event(struct machine 
*machine, union perf_event *event
 
 static void machine__remove_thread(struct machine *machine, struct thread *th)
 {
+   struct rb_node **p = &machine->dead_threads.rb_node;
+   struct rb_node *parent = NULL;
+   struct thread *pos;
+
machine->last_match = NULL;
rb_erase(&th->rb_node, &machine->threads);
+
+   th->dead = true;
+
/*
 * We may have references to this thread, for instance in some 
hist_entry
-* instances, so just move them to a separate list.
+* instances, so just move them to a separate list in rbtree.
 */
-   list_add_tail(&th->node, &machine->dead_threads);
+   while (*p != NULL) {
+   parent = *p;
+   pos = rb_entry(parent, struct thread, rb_node);
+
+   if (pos->tid == th->tid) {
+   list_add_tail(&th->node, &pos->node);
+   return;
+   }
+
+   if (th->tid < pos->tid)
+   p = &(*p)->rb_left;
+   else
+   p = &(*p)->rb_right;
+   }
+
+   rb_link_node(&th->rb_node, parent, p);
+   rb_insert_color(&th->rb_node, &machine->dead_threads);
 }
 
 int machine__process_fork_event(struct machine *machine, union perf_event 
*event,
@@ -1649,7 +1683,7 @@ int machine__for_each_thread(struct machine *machine,
 void *priv)
 {
struct rb_node *nd;
-   struct thread *thread;
+   struct thread *thread, *pos;
int rc = 0;
 
for (nd = rb_first(&machine->threads); nd; nd = rb_next(nd)) {
@@ -1659,10 +1693,17 @@ int machine__for_each_thread(struct machine *machine,
return rc;
}
 
-   list_for_each_entry(thread, &machine->dead_threads, node) {
+   for (nd = rb_first(&machine->dead_threads); nd; nd = rb_next(nd)) {
+   thread = rb_entry(nd, struct thread, rb_node);
rc = fn(thread, priv);
if (rc != 0)
return rc;
+
+   list_for_each_entry(pos, &thread->node, node) {
+   rc = fn(pos, priv);
+   if (rc != 0)
+   return rc;
+   }
}
return rc;
 }
diff --git a/tools/perf/util/machine.h b/tools/perf/util/machine.h
index e8b7779a0a3f..4349946a38ff 100644
--- a/tools/perf/util/machine.h
+++ b/tools/perf/util/machine.h
@@ -30,7 +30,7 @@ struct machine {
bool  comm_exec;
char  *root_dir;
struct rb_rootthreads;
-   struct list_head  dead_threads;
+   struct rb_rootdead_threads;
s