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

[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_head        node;
        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/