perf machine: Use hashtable for machine threads

To process any events, it needs to find the thread in the machine first.
The machine maintains a rb tree to store all threads. The rb tree is
protected by a rw lock.

It is not a problem for current perf which serially processing events.
However, it will have scalability performance issue to process events in
parallel, especially on a heavy load system which have many threads.

Introduce a hashtable to divide the big rb tree into many samll rb tree
for threads. The index is thread id % hashtable size. It can reduce the
lock contention.

Committer notes:

Renamed some variables and function names to reduce semantic confusion:

  'struct threads' pointers: thread -> threads
  threads hastable index: tid -> hash_bucket
  struct threads *machine__thread() -> machine__threads()
  Cast tid to (unsigned int) to handle -1 in machine__threads() (Kan Liang)

Signed-off-by: Kan Liang <kan.liang@intel.com>
Tested-by: Arnaldo Carvalho de Melo <acme@redhat.com>
Cc: Adrian Hunter <adrian.hunter@intel.com>
Cc: Andi Kleen <ak@linux.intel.com>
Cc: Jiri Olsa <jolsa@kernel.org>
Cc: Lukasz Odzioba <lukasz.odzioba@intel.com>
Cc: Namhyung Kim <namhyung@kernel.org>
Cc: Peter Zijlstra <peterz@infradead.org>
Link: http://lkml.kernel.org/r/1505096603-215017-2-git-send-email-kan.liang@intel.com
Signed-off-by: Arnaldo Carvalho de Melo <acme@redhat.com>

1 files changed, 85 insertions, 51 deletions

diff --git a/tools/perf/util/machine.c b/tools/perf/util/machine.c
index df709363ef69..f4f926753209 100644
--- a/tools/perf/util/machine.c
+++ b/tools/perf/util/machine.c
@@ -33,6 +33,20 @@ static void dsos__init(struct dsos *dsos)
         pthread_rwlock_init(&dsos->lock, NULL);
 }
 
+static void machine__threads_init(struct machine *machine)
+{
+        int i;
+
+        for (i = 0; i < THREADS__TABLE_SIZE; i++) {
+                struct threads *threads = &machine->threads[i];
+                threads->entries = RB_ROOT;
+                pthread_rwlock_init(&threads->lock, NULL);
+                threads->nr = 0;
+                INIT_LIST_HEAD(&threads->dead);
+                threads->last_match = NULL;
+        }
+}
+
 int machine__init(struct machine *machine, const char *root_dir, pid_t pid)
 {
         memset(machine, 0, sizeof(*machine));
@@ -40,11 +54,7 @@ int machine__init(struct machine *machine, const char *root_dir, pid_t pid)
         RB_CLEAR_NODE(&machine->rb_node);
         dsos__init(&machine->dsos);
 
-        machine->threads = RB_ROOT;
-        pthread_rwlock_init(&machine->threads_lock, NULL);
-        machine->nr_threads = 0;
-        INIT_LIST_HEAD(&machine->dead_threads);
-        machine->last_match = NULL;
+        machine__threads_init(machine);
 
         machine->vdso_info = NULL;
         machine->env = NULL;
@@ -141,27 +151,37 @@ static void dsos__exit(struct dsos *dsos)
 void machine__delete_threads(struct machine *machine)
 {
         struct rb_node *nd;
+        int i;
 
-        pthread_rwlock_wrlock(&machine->threads_lock);
-        nd = rb_first(&machine->threads);
-        while (nd) {
-                struct thread *t = rb_entry(nd, struct thread, rb_node);
+        for (i = 0; i < THREADS__TABLE_SIZE; i++) {
+                struct threads *threads = &machine->threads[i];
+                pthread_rwlock_wrlock(&threads->lock);
+                nd = rb_first(&threads->entries);
+                while (nd) {
+                        struct thread *t = rb_entry(nd, struct thread, rb_node);
 
-                nd = rb_next(nd);
-                __machine__remove_thread(machine, t, false);
+                        nd = rb_next(nd);
+                        __machine__remove_thread(machine, t, false);
+                }
+                pthread_rwlock_unlock(&threads->lock);
         }
-        pthread_rwlock_unlock(&machine->threads_lock);
 }
 
 void machine__exit(struct machine *machine)
 {
+        int i;
+
         machine__destroy_kernel_maps(machine);
         map_groups__exit(&machine->kmaps);
         dsos__exit(&machine->dsos);
         machine__exit_vdso(machine);
         zfree(&machine->root_dir);
         zfree(&machine->current_tid);
-        pthread_rwlock_destroy(&machine->threads_lock);
+
+        for (i = 0; i < THREADS__TABLE_SIZE; i++) {
+                struct threads *threads = &machine->threads[i];
+                pthread_rwlock_destroy(&threads->lock);
+        }
 }
 
 void machine__delete(struct machine *machine)
@@ -382,7 +402,8 @@ static struct thread *____machine__findnew_thread(struct machine *machine,
                                                   pid_t pid, pid_t tid,
                                                   bool create)
 {
-        struct rb_node **p = &machine->threads.rb_node;
+        struct threads *threads = machine__threads(machine, tid);
+        struct rb_node **p = &threads->entries.rb_node;
         struct rb_node *parent = NULL;
         struct thread *th;
 
@@ -391,14 +412,14 @@ static struct thread *____machine__findnew_thread(struct machine *machine,
          * so most of the time we dont have to look up
          * the full rbtree:
          */
-        th = machine->last_match;
+        th = threads->last_match;
         if (th != NULL) {
                 if (th->tid == tid) {
                         machine__update_thread_pid(machine, th, pid);
                         return thread__get(th);
                 }
 
-                machine->last_match = NULL;
+                threads->last_match = NULL;
         }
 
         while (*p != NULL) {
@@ -406,7 +427,7 @@ static struct thread *____machine__findnew_thread(struct machine *machine,
                 th = rb_entry(parent, struct thread, rb_node);
 
                 if (th->tid == tid) {
-                        machine->last_match = th;
+                        threads->last_match = th;
                         machine__update_thread_pid(machine, th, pid);
                         return thread__get(th);
                 }
@@ -423,7 +444,7 @@ static struct thread *____machine__findnew_thread(struct machine *machine,
         th = thread__new(pid, tid);
         if (th != NULL) {
                 rb_link_node(&th->rb_node, parent, p);
-                rb_insert_color(&th->rb_node, &machine->threads);
+                rb_insert_color(&th->rb_node, &threads->entries);
 
                 /*
                  * We have to initialize map_groups separately
@@ -434,7 +455,7 @@ static struct thread *____machine__findnew_thread(struct machine *machine,
                  * leader and that would screwed the rb tree.
                  */
                 if (thread__init_map_groups(th, machine)) {
-                        rb_erase_init(&th->rb_node, &machine->threads);
+                        rb_erase_init(&th->rb_node, &threads->entries);
                         RB_CLEAR_NODE(&th->rb_node);
                         thread__put(th);
                         return NULL;
@@ -443,8 +464,8 @@ static struct thread *____machine__findnew_thread(struct machine *machine,
                  * It is now in the rbtree, get a ref
                  */
                 thread__get(th);
-                machine->last_match = th;
-                ++machine->nr_threads;
+                threads->last_match = th;
+                ++threads->nr;
         }
 
         return th;
@@ -458,21 +479,24 @@ struct thread *__machine__findnew_thread(struct machine *machine, pid_t pid, pid
 struct thread *machine__findnew_thread(struct machine *machine, pid_t pid,
                                        pid_t tid)
 {
+        struct threads *threads = machine__threads(machine, tid);
         struct thread *th;
 
-        pthread_rwlock_wrlock(&machine->threads_lock);
+        pthread_rwlock_wrlock(&threads->lock);
         th = __machine__findnew_thread(machine, pid, tid);
-        pthread_rwlock_unlock(&machine->threads_lock);
+        pthread_rwlock_unlock(&threads->lock);
         return th;
 }
 
 struct thread *machine__find_thread(struct machine *machine, pid_t pid,
                                     pid_t tid)
 {
+        struct threads *threads = machine__threads(machine, tid);
         struct thread *th;
-        pthread_rwlock_rdlock(&machine->threads_lock);
+
+        pthread_rwlock_rdlock(&threads->lock);
         th =  ____machine__findnew_thread(machine, pid, tid, false);
-        pthread_rwlock_unlock(&machine->threads_lock);
+        pthread_rwlock_unlock(&threads->lock);
         return th;
 }
 
@@ -719,21 +743,24 @@ size_t machine__fprintf_vmlinux_path(struct machine *machine, FILE *fp)
 
 size_t machine__fprintf(struct machine *machine, FILE *fp)
 {
-        size_t ret;
         struct rb_node *nd;
+        size_t ret;
+        int i;
 
-        pthread_rwlock_rdlock(&machine->threads_lock);
-
-        ret = fprintf(fp, "Threads: %u\n", machine->nr_threads);
+        for (i = 0; i < THREADS__TABLE_SIZE; i++) {
+                struct threads *threads = &machine->threads[i];
+                pthread_rwlock_rdlock(&threads->lock);
 
-        for (nd = rb_first(&machine->threads); nd; nd = rb_next(nd)) {
-                struct thread *pos = rb_entry(nd, struct thread, rb_node);
+                ret = fprintf(fp, "Threads: %u\n", threads->nr);
 
-                ret += thread__fprintf(pos, fp);
-        }
+                for (nd = rb_first(&threads->entries); nd; nd = rb_next(nd)) {
+                        struct thread *pos = rb_entry(nd, struct thread, rb_node);
 
-        pthread_rwlock_unlock(&machine->threads_lock);
+                        ret += thread__fprintf(pos, fp);
+                }
 
+                pthread_rwlock_unlock(&threads->lock);
+        }
         return ret;
 }
 
@@ -1479,23 +1506,25 @@ out_problem:
 
 static void __machine__remove_thread(struct machine *machine, struct thread *th, bool lock)
 {
-        if (machine->last_match == th)
-                machine->last_match = NULL;
+        struct threads *threads = machine__threads(machine, th->tid);
+
+        if (threads->last_match == th)
+                threads->last_match = NULL;
 
         BUG_ON(refcount_read(&th->refcnt) == 0);
         if (lock)
-                pthread_rwlock_wrlock(&machine->threads_lock);
-        rb_erase_init(&th->rb_node, &machine->threads);
+                pthread_rwlock_wrlock(&threads->lock);
+        rb_erase_init(&th->rb_node, &threads->entries);
         RB_CLEAR_NODE(&th->rb_node);
-        --machine->nr_threads;
+        --threads->nr;
         /*
          * Move it first to the dead_threads list, then drop the reference,
          * if this is the last reference, then the thread__delete destructor
          * will be called and we will remove it from the dead_threads list.
          */
-        list_add_tail(&th->node, &machine->dead_threads);
+        list_add_tail(&th->node, &threads->dead);
         if (lock)
-                pthread_rwlock_unlock(&machine->threads_lock);
+                pthread_rwlock_unlock(&threads->lock);
         thread__put(th);
 }
 
@@ -2140,21 +2169,26 @@ int machine__for_each_thread(struct machine *machine,
                              int (*fn)(struct thread *thread, void *p),
                              void *priv)
 {
+        struct threads *threads;
         struct rb_node *nd;
         struct thread *thread;
         int rc = 0;
+        int i;
 
-        for (nd = rb_first(&machine->threads); nd; nd = rb_next(nd)) {
-                thread = rb_entry(nd, struct thread, rb_node);
-                rc = fn(thread, priv);
-                if (rc != 0)
-                        return rc;
-        }
+        for (i = 0; i < THREADS__TABLE_SIZE; i++) {
+                threads = &machine->threads[i];
+                for (nd = rb_first(&threads->entries); 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(thread, &machine->dead_threads, node) {
-                rc = fn(thread, priv);
-                if (rc != 0)
-                        return rc;
+                list_for_each_entry(thread, &threads->dead, node) {
+                        rc = fn(thread, priv);
+                        if (rc != 0)
+                                return rc;
+                }
         }
         return rc;
 }