For dumps with large task count, ps spends most its time in the
following stack:
  task_to_context
  task_to_pid
  show_ps_data
  show_ps
  cmd_ps
  exec_command
  main_loop
  captured_command_loop
  catch_errors
  captured_main
  catch_errors
  gdb_main_entry
  gdb_main_loop
  main
The above shows use of task_to_pid on each process.  task_to_context is
O(N), thus ps is O(N^2).

Reduce task_to_context to O(N*log(N)) by using a binary search.

On a 1M task dump, this reduces ps time 45m => 17s.

Signed-off-by: Greg Thelen <gthe...@google.com>
---
 defs.h |  2 ++
 task.c | 64 ++++++++++++++++++++++++++++++++++++++++++++++++++++------
 2 files changed, 60 insertions(+), 6 deletions(-)

diff --git a/defs.h b/defs.h
index 3a3b6f66573c..15346f01fd4e 100644
--- a/defs.h
+++ b/defs.h
@@ -811,6 +811,7 @@ struct tgid_context {               /* tgid and task stored 
for each task */
 struct task_table {                      /* kernel/local task table data */
        struct task_context *current;
        struct task_context *context_array;
+       struct task_context **context_by_task; /* task_context sorted by task 
addr */
        void (*refresh_task_table)(void);
        ulong flags;
         ulong task_start;
@@ -871,6 +872,7 @@ struct task_table {                      /* kernel/local 
task table data */
 #define START_TIME_NSECS  (0x8000)
 #define THREAD_INFO_IN_TASK (0x10000)
 #define PID_RADIX_TREE   (0x20000)
+#define INDEXED_CONTEXTS (0x40000)
 
 #define TASK_SLUSH (20)
 
diff --git a/task.c b/task.c
index cddc1f5b651a..5ad77408530d 100644
--- a/task.c
+++ b/task.c
@@ -783,6 +783,10 @@ allocate_task_space(int cnt)
                     malloc(cnt * sizeof(struct task_context))))
                         error(FATAL, "cannot malloc context array (%d tasks)",
                                 cnt);
+               if (!(tt->context_by_task = (struct task_context **)
+                    malloc(cnt * sizeof(struct task_context*))))
+                        error(FATAL, "cannot malloc context_by_task array (%d 
tasks)",
+                                cnt);
                if (!(tt->tgid_array = (struct tgid_context *)
                     malloc(cnt * sizeof(struct tgid_context))))
                         error(FATAL, "cannot malloc tgid array (%d tasks)",
@@ -802,6 +806,13 @@ allocate_task_space(int cnt)
                             "%scannot realloc context array (%d tasks)",
                                (pc->flags & RUNTIME) ? "" : "\n", cnt);
 
+                if (!(tt->context_by_task = (struct task_context **)
+                    realloc(tt->context_by_task,
+                   cnt * sizeof(struct task_context*))))
+                        error(FATAL,
+                            "%scannot realloc context_by_task array (%d 
tasks)",
+                               (pc->flags & RUNTIME) ? "" : "\n", cnt);
+
                 if (!(tt->tgid_array = (struct tgid_context *)
                     realloc(tt->tgid_array, 
                    cnt * sizeof(struct tgid_context)))) 
@@ -2700,6 +2711,7 @@ add_context(ulong task, char *tp)
         if (has_cpu && (tt->flags & POPULATE_PANIC))
                 tt->panic_threads[tc->processor] = tc->task;
 
+       tt->flags &= ~INDEXED_CONTEXTS;
        tt->running_tasks++;
        return tc;
 }
@@ -2747,6 +2759,33 @@ refresh_context(ulong curtask, ulong curpid)
         }
 }
 
+static int
+sort_by_task(const void *arg1, const void *arg2)
+{
+       const struct task_context *t1, *t2;
+
+       t1 = *(const struct task_context **)arg1;
+       t2 = *(const struct task_context **)arg2;
+
+       if (t1->task == t2->task)
+               return 0;
+
+       return (t1->task < t2->task) ? -1 : 1;
+}
+
+/* sort context_by_task by task address */
+static void
+sort_context_by_task(void)
+{
+       int i;
+
+       for (i = 0; i < tt->running_tasks; i++)
+               tt->context_by_task[i] = &tt->context_array[i];
+       qsort(tt->context_by_task, tt->running_tasks,
+             sizeof(*tt->context_by_task), sort_by_task);
+       tt->flags |= INDEXED_CONTEXTS;
+}
+
 /*
  *  Sort the task_context array by PID number; for PID 0, sort by processor.
  */
@@ -2759,6 +2798,8 @@ sort_context_array(void)
        qsort((void *)tt->context_array, (size_t)tt->running_tasks,
                sizeof(struct task_context), sort_by_pid);
        set_context(curtask, NO_PID);
+
+       sort_context_by_task();
 }
 
 static int
@@ -2804,6 +2845,8 @@ sort_context_array_by_last_run(void)
        qsort((void *)tt->context_array, (size_t)tt->running_tasks,
                sizeof(struct task_context), sort_by_last_run);
        set_context(curtask, NO_PID);
+
+       sort_context_by_task();
 }
 
 /*
@@ -4640,15 +4683,24 @@ task_exists(ulong task)
 struct task_context *
 task_to_context(ulong task)
 {
-        int i;
-        struct task_context *tc;
+       struct task_context key, *tc, **found;
+       int i;
+
+       /* Binary search the context_by_task array. */
+       if (tt->flags & INDEXED_CONTEXTS) {
+               key.task = task;
+               tc = &key;
+               found = bsearch(&tc, tt->context_by_task, tt->running_tasks,
+                               sizeof(*tt->context_by_task), sort_by_task);
+               return found ? *found : NULL;
+       }
 
         tc = FIRST_CONTEXT();
-        for (i = 0; i < RUNNING_TASKS(); i++, tc++) 
+        for (i = 0; i < RUNNING_TASKS(); i++, tc++)
                 if (tc->task == task)
-                        return tc; 
-        
-        return NULL;
+                        return tc;
+
+       return NULL;
 }
 
 /*
-- 
2.17.0.484.g0c8726318c-goog

--
Crash-utility mailing list
Crash-utility@redhat.com
https://www.redhat.com/mailman/listinfo/crash-utility

Reply via email to