[Xen-devel] [PATCH 11 of 12] xenalyze: Optimize pcpu_string

[George Dunlap <george.dunlap@xxxxxxxxxxxxx>]

pcpu_string() is called on every line of the dump output,
and the basic loop is O(N) with the number of pcpus.  There
was an optimization that would be O(1), but it had a bug so that
it never actually went into effect.

Put the optimization into effect, so that only the bits that need
to change are changed.

This means, however, that when other things change, like power
states or lost records, that other parts of the string need to
be redrawn.  Put in hooks to redraw when these kinds of things
change.

Signed-off-by: George Dunlap <george.dunlap@xxxxxxxxxxxxx>

diff -r dab5ba28630a -r b7d88a8858b7 xenalyze.c
--- a/xenalyze.c        Mon Nov 28 16:16:23 2011 +0000
+++ b/xenalyze.c        Mon Nov 28 16:16:23 2011 +0000
@@ -1942,6 +1942,7 @@ struct {
 
 /* Function prototypes */
 char * pcpu_string(int pcpu);
+void pcpu_string_draw(struct pcpu_info *p);
 void process_generic(struct record_info *ri);
 void dump_generic(FILE *f, struct record_info *ri);
 ssize_t __read_record(int fd, struct trace_record *rec, loff_t offset);
@@ -6970,6 +6971,7 @@ void vcpu_prev_update(struct pcpu_info *
 set:
     pcpu_runstate_update(p, tsc);
     p->current = NULL;
+    pcpu_string_draw(p);
     runstate_update(prev, new_runstate, tsc);
 }
 
@@ -7051,6 +7053,7 @@ void vcpu_next_update(struct pcpu_info *
 
     next->p = p;
     p->current = next;
+    pcpu_string_draw(p);
     p->time.tsc = tsc;
     p->lost_record.seen_valid_schedule = 1;
 }
@@ -7089,6 +7092,7 @@ void vcpu_start(struct pcpu_info *p, str
     runstate_update(v, RUNSTATE_RUNNING, p->first_tsc);
     p->time.tsc = p->first_tsc;
     p->current = v;
+    pcpu_string_draw(p);
     v->p = p;
 }
 
@@ -7524,6 +7528,7 @@ void sched_default_vcpu_activate(struct 
     v->runstate.state = RUNSTATE_RUNNING;
 
     p->current = v;
+    pcpu_string_draw(p);
 }
 
 void sched_default_domain_init(void)
@@ -7825,7 +7830,10 @@ void pm_process(struct pcpu_info *p) {
                    ri->dump_header,
                    ri->d[0]);
         if ( ri->d[0] <= CSTATE_MAX )
+        {
             p->power_state=ri->d[0];
+            pcpu_string_draw(p);
+        }
         break;
     case TRC_PM_IDLE_EXIT:
         if (opt.dump_all )
@@ -7837,6 +7845,7 @@ void pm_process(struct pcpu_info *p) {
             printf("Strange, pm_idle_end %d, power_state %d!\n",
                    ri->d[0], p->power_state);
         p->power_state = 0;
+        pcpu_string_draw(p);
         break;
     default:
         if(opt.dump_all || opt.dump_cooked) {
@@ -8437,6 +8446,7 @@ void process_lost_records(struct pcpu_in
 
     p->lost_record.active = 1;
     p->lost_record.tsc = first_tsc;
+    pcpu_string_draw(p);
     
     {
         /* Any vcpu which is not actively running may be scheduled on the
@@ -8520,6 +8530,7 @@ void process_lost_records_end(struct pcp
         
         
         p->lost_record.active = 0;
+        pcpu_string_draw(p);
         P.lost_cpus--;
         if(P.lost_cpus < 0) {
             fprintf(warn, "ERROR: lost_cpus fell below 0 for pcpu %d!\n",
@@ -9230,38 +9241,59 @@ ssize_t read_record(int fd, struct pcpu_
     return ri->size;
 }
 
-/* WARNING not thread-safe */
+/*
+ * This funciton gets called for every record when doing dump.  Try to
+ * make it efficient by changing the minimum amount from the last
+ * call.  Do this by:
+ * - Keeping track of the last pcpu called, so we can just set that to -
+ * - Keeping track of how many pcpus we've "drawn", and only "drawing" new ones
+ * - Updating the current one
+ *
+ * FIXME: Need to deal with pcpu states changing...
+ * 
+ * WARNING not thread-safe
+ */
+
+char __pcpu_string[MAX_CPUS+1] = { 0 };
+void pcpu_string_draw(struct pcpu_info *p)
+{
+    char *s = __pcpu_string;
+    int i=p->pid;
+
+    if(p->lost_record.active)
+        s[i]='l';
+    else if (!p->current)
+        s[i]=' ';
+    else if (p->current->d->did == DEFAULT_DOMAIN)
+        s[i]='.';
+    else if (p->current->d->did == IDLE_DOMAIN)
+    {
+        if ( opt.dump_show_power_states )
+            s[i]=p->power_state+'0';
+        else
+            s[i]='-';
+    }
+    else
+        s[i]='|';
+}
+
 char * pcpu_string(int pcpu)
 {
-    static char s[MAX_CPUS+1] = { 0 };
+    char *s = __pcpu_string;
     static int max_active_pcpu=-1, last_pcpu=-1;
     
     assert(P.max_active_pcpu < MAX_CPUS);
     assert(pcpu <= P.max_active_pcpu);
 
     if(last_pcpu >= 0)
-        s[last_pcpu]='-';
+        pcpu_string_draw(P.pcpu+last_pcpu);
 
     if(P.max_active_pcpu > max_active_pcpu)
     {
         int i;
-        for(i=max_active_pcpu + 1; i<= P.max_active_pcpu; i++) {
-            if(P.pcpu[i].lost_record.active)
-                s[i]='l';
-            else if (!P.pcpu[i].current)
-                s[i]=' ';
-            else if (P.pcpu[i].current->d->did == DEFAULT_DOMAIN)
-                s[i]='.';
-            else if (P.pcpu[i].current->d->did == IDLE_DOMAIN)
-            {
-                if ( opt.dump_show_power_states )
-                    s[i]=P.pcpu[i].power_state+'0';
-                else
-                    s[i]='-';
-            }
-            else
-                s[i]='|';
-        }
+        for(i=max_active_pcpu + 1; i<= P.max_active_pcpu; i++) 
+            pcpu_string_draw(P.pcpu+i);
+        max_active_pcpu=P.max_active_pcpu;
     }
 
     s[pcpu]='x';

_______________________________________________
Xen-devel mailing list
Xen-devel@xxxxxxxxxxxxxxxxxxx
http://lists.xensource.com/xen-devel