Dynamically allocate bootchart logs

Instead of storing bootchart sample data in arrays, this patch moves
storage to linked lists so that there is no more limit on samples.

This patch also fixes parsing of /proc/<pid>/smaps in kernels > 3.7.

5 files changed, 437 insertions, 143 deletions

diff --git a/src/bootchart/bootchart.c b/src/bootchart/bootchart.c
index b73319123f..8be5a27afa 100644
--- a/src/bootchart/bootchart.c
+++ b/src/bootchart/bootchart.c
@@ -59,14 +59,11 @@
 #include "store.h"
 #include "svg.h"
 #include "bootchart.h"
+#include "list.h"
 
 double graph_start;
 double log_start;
-double sampletime[MAXSAMPLES];
 struct ps_struct *ps_first;
-struct block_stat_struct blockstat[MAXSAMPLES];
-int entropy_avail[MAXSAMPLES];
-struct cpu_stat_struct cpustat[MAXCPUS];
 int pscount;
 int cpus;
 double interval;
@@ -87,6 +84,8 @@ int arg_samples_len = 500; /* we record len+1 (1 start sample) */
 double arg_hz = 25.0;   /* 20 seconds log time */
 double arg_scale_x = 100.0; /* 100px = 1sec */
 double arg_scale_y = 20.0;  /* 16px = 1 process bar */
+static struct list_sample_data *sampledata;
+struct list_sample_data *head;
 
 char arg_init_path[PATH_MAX] = "/sbin/init";
 char arg_output_path[PATH_MAX] = "/run/log";
@@ -227,11 +226,6 @@ static int parse_args(int argc, char *argv[]) {
                 }
         }
 
-        if (arg_samples_len > MAXSAMPLES) {
-                fprintf(stderr, "Error: samples exceeds maximum\n");
-                return -EINVAL;
-        }
-
         if (arg_hz <= 0.0) {
                 fprintf(stderr, "Error: Frequency needs to be > 0\n");
                 return -EINVAL;
@@ -338,6 +332,8 @@ int main(int argc, char *argv[]) {
 
         log_uptime();
 
+        LIST_HEAD_INIT(struct list_sample_data, head);
+
         /* main program loop */
         for (samples = 0; !exiting && samples < arg_samples_len; samples++) {
                 int res;
@@ -348,7 +344,14 @@ int main(int argc, char *argv[]) {
                 double elapsed;
                 double timeleft;
 
-                sampletime[samples] = gettime_ns();
+                sampledata = new0(struct list_sample_data, 1);
+                if (sampledata == NULL) {
+                        log_error("Failed to allocate memory for a node: %m");
+                        return -1;
+                }
+
+                sampledata->sampletime = gettime_ns();
+                sampledata->counter = samples;
 
                 if (!of && (access(arg_output_path, R_OK|W_OK|X_OK) == 0)) {
                         t = time(NULL);
@@ -369,11 +372,11 @@ int main(int argc, char *argv[]) {
                 if (graph_start <= 0.0)
                         log_uptime();
                 else
-                        log_sample(samples);
+                        log_sample(samples, &sampledata);
 
                 sample_stop = gettime_ns();
 
-                elapsed = (sample_stop - sampletime[samples]) * 1000000000.0;
+                elapsed = (sample_stop - sampledata->sampletime) * 1000000000.0;
                 timeleft = interval - elapsed;
 
                 newint_s = (time_t)(timeleft / 1000000000.0);
@@ -403,6 +406,7 @@ int main(int argc, char *argv[]) {
                         /* calculate how many samples we lost and scrap them */
                         arg_samples_len -= (int)(newint_ns / interval);
                 }
+                LIST_PREPEND(struct list_sample_data, link, head, sampledata);
         }
 
         /* do some cleanup, close fd's */
@@ -443,16 +447,32 @@ int main(int argc, char *argv[]) {
                 close(sysfd);
 
         /* nitpic cleanups */
-        ps = ps_first;
+        ps = ps_first->next_ps;
         while (ps->next_ps) {
-                struct ps_struct *old = ps;
+                struct ps_struct *old;
+
+                old = ps;
+                old->sample = ps->first;
                 ps = ps->next_ps;
+                while (old->sample->next) {
+                        struct ps_sched_struct *oldsample = old->sample;
+
+                        old->sample = old->sample->next;
+                        free(oldsample);
+                }
                 free(old->sample);
                 free(old);
         }
         free(ps->sample);
         free(ps);
 
+        sampledata = head;
+        while (sampledata->link_prev) {
+                struct list_sample_data *old_sampledata = sampledata;
+                sampledata = sampledata->link_prev;
+                free(old_sampledata);
+        }
+        free(sampledata);
         /* don't complain when overrun once, happens most commonly on 1st sample */
         if (overrun > 1)
                 fprintf(stderr, "systemd-boochart: Warning: sample time overrun %i times\n", overrun);
diff --git a/src/bootchart/bootchart.h b/src/bootchart/bootchart.h
index a9541caf4a..ee1e67604d 100644
--- a/src/bootchart/bootchart.h
+++ b/src/bootchart/bootchart.h
@@ -26,6 +26,7 @@
 
 #include <dirent.h>
 #include <stdbool.h>
+#include "list.h"
 
 #define MAXCPUS        16
 #define MAXPIDS     65535
@@ -54,6 +55,22 @@ struct ps_sched_struct {
         double runtime;
         double waittime;
         int pss;
+        struct list_sample_data *sampledata;
+        struct ps_sched_struct *next;
+        struct ps_sched_struct *prev;
+        struct ps_sched_struct *cross; /* cross pointer */
+        struct ps_struct *ps_new;
+};
+
+struct list_sample_data {
+        double runtime[MAXCPUS];
+        double waittime[MAXCPUS];
+        double sampletime;
+        int entropy_avail;
+        struct block_stat_struct blockstat;
+        struct cpu_stat_struct cpustat;
+        LIST_FIELDS(struct list_sample_data, link); /* DLL */
+        int counter;
 };
 
 /* process info */
@@ -73,9 +90,9 @@ struct ps_struct {
         int schedstat;
         FILE *smaps;
 
-        /* index to first/last seen timestamps */
-        int first;
-        int last;
+        /* pointers to first/last seen timestamps */
+        struct ps_sched_struct *first;
+        struct ps_sched_struct *last;
 
         /* records actual start time, may be way before bootchart runs */
         double starttime;
diff --git a/src/bootchart/store.c b/src/bootchart/store.c
index 4de187c8bc..b2afb8d13b 100644..100755
--- a/src/bootchart/store.c
+++ b/src/bootchart/store.c
@@ -44,6 +44,7 @@
  * read() overhead.
  */
 static char smaps_buf[4096];
+static int skip = 0;
 DIR *proc;
 int procfd = -1;
 
@@ -111,7 +112,7 @@ static int pid_cmdline_strscpy(char *buffer, size_t buf_len, int pid) {
         return 0;
 }
 
-void log_sample(int sample) {
+void log_sample(int sample, struct list_sample_data **ptr) {
         static int vmstat;
         static int schedstat;
         char buf[4096];
@@ -128,6 +129,12 @@ void log_sample(int sample) {
         ssize_t n;
         struct dirent *ent;
         int fd;
+        struct list_sample_data *sampledata;
+        struct ps_sched_struct *ps_prev = NULL;
+
+
+
+        sampledata = *ptr;
 
         /* all the per-process stuff goes here */
         if (!proc) {
@@ -161,9 +168,9 @@ void log_sample(int sample) {
                 if (sscanf(m, "%s %s", key, val) < 2)
                         goto vmstat_next;
                 if (streq(key, "pgpgin"))
-                        blockstat[sample].bi = atoi(val);
+                        sampledata->blockstat.bi = atoi(val);
                 if (streq(key, "pgpgout")) {
-                        blockstat[sample].bo = atoi(val);
+                        sampledata->blockstat.bo = atoi(val);
                         break;
                 }
 vmstat_next:
@@ -198,8 +205,8 @@ vmstat_next:
                         if (c > MAXCPUS)
                                 /* Oops, we only have room for MAXCPUS data */
                                 break;
-                        cpustat[c].sample[sample].runtime = atoll(rt);
-                        cpustat[c].sample[sample].waittime = atoll(wt);
+                        sampledata->runtime[c] = atoll(rt);
+                        sampledata->waittime[c] = atoll(wt);
 
                         if (c == cpus)
                                 cpus = c + 1;
@@ -219,7 +226,7 @@ schedstat_next:
                         n = pread(e_fd, buf, sizeof(buf) - 1, 0);
                         if (n > 0) {
                                 buf[n] = '\0';
-                                entropy_avail[sample] = atoi(buf);
+                                sampledata->entropy_avail = atoi(buf);
                         }
                 }
         }
@@ -258,16 +265,19 @@ schedstat_next:
                         ps = ps->next_ps;
                         ps->pid = pid;
 
-                        ps->sample = calloc(arg_samples_len + 1, sizeof(struct ps_sched_struct));
+                        ps->sample = calloc(1, sizeof(struct ps_sched_struct));
                         if (!ps->sample) {
                                 perror("calloc(ps_struct)");
                                 exit (EXIT_FAILURE);
                         }
+                        ps->sample->sampledata = sampledata;
 
                         pscount++;
 
                         /* mark our first sample */
-                        ps->first = sample;
+                        ps->first = ps->sample;
+                        ps->sample->runtime = atoll(rt);
+                        ps->sample->waittime = atoll(wt);
 
                         /* get name, start time */
                         if (!ps->sched) {
@@ -383,16 +393,28 @@ schedstat_next:
                 if (!sscanf(buf, "%s %s %*s", rt, wt))
                         continue;
 
-                ps->last = sample;
-                ps->sample[sample].runtime = atoll(rt);
-                ps->sample[sample].waittime = atoll(wt);
-
-                ps->total = (ps->sample[ps->last].runtime
-                                 - ps->sample[ps->first].runtime)
-                                 / 1000000000.0;
+                ps->sample->next = calloc(1, sizeof(struct ps_sched_struct));
+                if (!ps->sample) {
+                        perror("calloc(ps_struct)");
+                        exit (EXIT_FAILURE);
+                }
+                ps->sample->next->prev = ps->sample;
+                ps->sample = ps->sample->next;
+                ps->last = ps->sample;
+                ps->sample->runtime = atoll(rt);
+                ps->sample->waittime = atoll(wt);
+                ps->sample->sampledata = sampledata;
+                ps->sample->ps_new = ps;
+                if (ps_prev) {
+                        ps_prev->cross = ps->sample;
+                }
+                ps_prev = ps->sample;
+                ps->total = (ps->last->runtime - ps->first->runtime)
+                            / 1000000000.0;
 
                 if (!arg_pss)
                         goto catch_rename;
+
                 /* Pss */
                 if (!ps->smaps) {
                         sprintf(filename, "%d/smaps", pid);
@@ -401,31 +423,53 @@ schedstat_next:
                         if (!ps->smaps)
                                 continue;
                         setvbuf(ps->smaps, smaps_buf, _IOFBF, sizeof(smaps_buf));
-                } else {
+                }
+                else {
+                        rewind(ps->smaps);
+                }
+                /* test to see if we need to skip another field */
+                if (skip == 0) {
+                        if (fgets(buf, sizeof(buf), ps->smaps) == NULL) {
+                                continue;
+                        }
+                        if (fread(buf, 1, 28 * 15, ps->smaps) != (28 * 15)) {
+                                continue;
+                        }
+                        if (buf[392] == 'V') {
+                                skip = 2;
+                        }
+                        else {
+                                skip = 1;
+                        }
                         rewind(ps->smaps);
                 }
-
                 while (1) {
                         int pss_kb;
 
-                        /* skip one line, this contains the object mapped */
-                        if (fgets(buf, sizeof(buf), ps->smaps) == NULL)
+                        /* skip one line, this contains the object mapped. */
+                        if (fgets(buf, sizeof(buf), ps->smaps) == NULL) {
                                 break;
+                        }
                         /* then there's a 28 char 14 line block */
-                        if (fread(buf, 1, 28 * 14, ps->smaps) != 28 * 14)
+                        if (fread(buf, 1, 28 * 14, ps->smaps) != 28 * 14) {
                                 break;
-
+                        }
                         pss_kb = atoi(&buf[61]);
-                        ps->sample[sample].pss += pss_kb;
-                }
+                        ps->sample->pss += pss_kb;
 
-                if (ps->sample[sample].pss > ps->pss_max)
-                        ps->pss_max = ps->sample[sample].pss;
+                        /* skip one more line if this is a newer kernel */
+                        if (skip == 2) {
+                               if (fgets(buf, sizeof(buf), ps->smaps) == NULL)
+                                       break;
+                        }
+                }
+                if (ps->sample->pss > ps->pss_max)
+                        ps->pss_max = ps->sample->pss;
 
 catch_rename:
                 /* catch process rename, try to randomize time */
                 mod = (arg_hz < 4.0) ? 4.0 : (arg_hz / 4.0);
-                if (((samples - ps->first) + pid) % (int)(mod) == 0) {
+                if (((samples - ps->pid) + pid) % (int)(mod) == 0) {
 
                         /* re-fetch name */
                         /* get name, start time */
diff --git a/src/bootchart/store.h b/src/bootchart/store.h
index e8d013cde4..7c8ad284da 100644
--- a/src/bootchart/store.h
+++ b/src/bootchart/store.h
@@ -25,10 +25,11 @@
 ***/
 
 #include <dirent.h>
+#include "bootchart.h"
 
 extern DIR *proc;
 extern int procfd;
 
 double gettime_ns(void);
 void log_uptime(void);
-void log_sample(int sample);
+void log_sample(int sample, struct list_sample_data **ptr);
diff --git a/src/bootchart/svg.c b/src/bootchart/svg.c
index 1e87fb5739..859cf81c22 100644
--- a/src/bootchart/svg.c
+++ b/src/bootchart/svg.c
@@ -38,6 +38,7 @@
 #include "store.h"
 #include "svg.h"
 #include "bootchart.h"
+#include "list.h"
 
 #define time_to_graph(t) ((t) * arg_scale_x)
 #define ps_to_graph(n) ((n) * arg_scale_y)
@@ -70,13 +71,24 @@ static int kcount = 0;
 static float psize = 0;
 static float ksize = 0;
 static float esize = 0;
+static struct list_sample_data *sampledata;
+static struct list_sample_data *prev_sampledata;
+extern struct list_sample_data *head;
 
 static void svg_header(void) {
         float w;
         float h;
+        struct list_sample_data *sampledata_last;
+
+        sampledata = head;
+        LIST_FIND_TAIL(struct list_sample_data, link, sampledata, head);
+        sampledata_last = head;
+        LIST_FOREACH_BEFORE(link, sampledata, head) {
+                sampledata_last = sampledata;
+        }
 
         /* min width is about 1600px due to the label */
-        w = 150.0 + 10.0 + time_to_graph(sampletime[samples-1] - graph_start);
+        w = 150.0 + 10.0 + time_to_graph(sampledata_last->sampletime - graph_start);
         w = ((w < 1600.0) ? 1600.0 : w);
 
         /* height is variable based on pss, psize, ksize */
@@ -223,14 +235,23 @@ static void svg_title(const char *build) {
 static void svg_graph_box(int height) {
         double d = 0.0;
         int i = 0;
+        double finalsample = 0.0;
+        struct list_sample_data *sampledata_last;
+
+        sampledata_last = head;
+        LIST_FOREACH_BEFORE(link, sampledata, head) {
+                sampledata_last = sampledata;
+        }
+
+        finalsample = sampledata_last->sampletime;
 
         /* outside box, fill */
         svg("<rect class=\"box\" x=\"%.03f\" y=\"0\" width=\"%.03f\" height=\"%.03f\" />\n",
             time_to_graph(0.0),
-            time_to_graph(sampletime[samples-1] - graph_start),
+            time_to_graph(finalsample - graph_start),
             ps_to_graph(height));
 
-        for (d = graph_start; d <= sampletime[samples-1];
+        for (d = graph_start; d <= finalsample;
              d += (arg_scale_x < 2.0 ? 60.0 : arg_scale_x < 10.0 ? 1.0 : 0.1)) {
                 /* lines for each second */
                 if (i % 50 == 0)
@@ -278,6 +299,13 @@ static char* xml_comment_encode(const char* name) {
 static void svg_pss_graph(void) {
         struct ps_struct *ps;
         int i;
+        struct list_sample_data *sampledata_last;
+
+        sampledata_last = head;
+        LIST_FOREACH_BEFORE(link, sampledata, head) {
+                sampledata_last = sampledata;
+        }
+
 
         svg("\n\n<!-- Pss memory size graph -->\n");
 
@@ -290,18 +318,21 @@ static void svg_pss_graph(void) {
                 svg("  <line class=\"sec01\" x1=\"%.03f\" y1=\"%.0f\" x2=\"%.03f\" y2=\"%.0f\"/>\n",
                         time_to_graph(.0),
                         kb_to_graph(i),
-                        time_to_graph(sampletime[samples-1] - graph_start),
+                        time_to_graph(sampledata_last->sampletime - graph_start),
                         kb_to_graph(i));
                 svg("  <text class=\"sec\" x=\"%.03f\" y=\"%.0f\">%dM</text>\n",
-                    time_to_graph(sampletime[samples-1] - graph_start) + 5,
+                    time_to_graph(sampledata_last->sampletime - graph_start) + 5,
                     kb_to_graph(i), (1000000 - i) / 1000);
         }
         svg("\n");
 
         /* now plot the graph itself */
-        for (i = 1; i < samples ; i++) {
+        i = 1;
+        prev_sampledata = head;
+        LIST_FOREACH_BEFORE(link, sampledata, head) {
                 int bottom;
                 int top;
+                struct ps_sched_struct *cross_place;
 
                 bottom = 0;
                 top = 0;
@@ -312,16 +343,32 @@ static void svg_pss_graph(void) {
                         ps = ps->next_ps;
                         if (!ps)
                                 continue;
-                        if (ps->sample[i].pss <= (100 * arg_scale_y))
-                                top += ps->sample[i].pss;
-                };
+                        ps->sample = ps->first;
+                        while (ps->sample->next) {
+                                ps->sample = ps->sample->next;
+                                if (ps->sample->sampledata == sampledata)
+                                        break;
+                        }
+                        if (ps->sample->sampledata == sampledata) {
+                                if (ps->sample->pss <= (100 * arg_scale_y))
+                                        top += ps->sample->pss;
+                                break;
+                        }
+                }
+                while (ps->sample->cross) {
+                        cross_place = ps->sample->cross;
+                        ps = ps->sample->cross->ps_new;
+                        ps->sample = cross_place;
+                        if (ps->sample->pss <= (100 * arg_scale_y))
+                                top += ps->sample->pss;
+                }
+
                 svg("    <rect class=\"clrw\" style=\"fill: %s\" x=\"%.03f\" y=\"%.03f\" width=\"%.03f\" height=\"%.03f\" />\n",
                     "rgb(64,64,64)",
-                    time_to_graph(sampletime[i - 1] - graph_start),
+                    time_to_graph(prev_sampledata->sampletime - graph_start),
                     kb_to_graph(1000000.0 - top),
-                    time_to_graph(sampletime[i] - sampletime[i - 1]),
+                    time_to_graph(sampledata->sampletime - prev_sampledata->sampletime),
                     kb_to_graph(top - bottom));
-
                 bottom = top;
 
                 /* now plot the ones that are of significant size */
@@ -330,59 +377,129 @@ static void svg_pss_graph(void) {
                         ps = ps->next_ps;
                         if (!ps)
                                 continue;
+                        ps->sample = ps->first;
+                        while (ps->sample->next) {
+                                ps->sample = ps->sample->next;
+                                if (ps->sample->sampledata == sampledata)
+                                        break;
+                        }
                         /* don't draw anything smaller than 2mb */
-                        if (ps->sample[i].pss > (100 * arg_scale_y)) {
-                                top = bottom + ps->sample[i].pss;
+                        if (ps->sample->sampledata == sampledata) {
+                                if (ps->sample->pss > (100 * arg_scale_y)) {
+                                top = bottom + ps->sample->pss;
                                 svg("    <rect class=\"clrw\" style=\"fill: %s\" x=\"%.03f\" y=\"%.03f\" width=\"%.03f\" height=\"%.03f\" />\n",
-                                    colorwheel[ps->pid % 12],
-                                    time_to_graph(sampletime[i - 1] - graph_start),
-                                    kb_to_graph(1000000.0 - top),
-                                    time_to_graph(sampletime[i] - sampletime[i - 1]),
-                                    kb_to_graph(top - bottom));
+                                  colorwheel[ps->pid % 12],
+                                  time_to_graph(prev_sampledata->sampletime - graph_start),
+                                  kb_to_graph(1000000.0 - top),
+                                  time_to_graph(sampledata->sampletime - prev_sampledata->sampletime),
+                                  kb_to_graph(top - bottom));
+                                bottom = top;
+                                }
+                                break;
+                        }
+                }
+                while ((cross_place = ps->sample->cross)) {
+                        ps = ps->sample->cross->ps_new;
+                        ps->sample = cross_place;
+                        if (ps->sample->pss > (100 * arg_scale_y)) {
+                                top = bottom + ps->sample->pss;
+                                svg("    <rect class=\"clrw\" style=\"fill: %s\" x=\"%.03f\" y=\"%.03f\" width=\"%.03f\" height=\"%.03f\" />\n",
+                                  colorwheel[ps->pid % 12],
+                                  time_to_graph(prev_sampledata->sampletime - graph_start),
+                                  kb_to_graph(1000000.0 - top),
+                                  time_to_graph(sampledata->sampletime - prev_sampledata->sampletime),
+                                  kb_to_graph(top - bottom));
                                 bottom = top;
                         }
                 }
+                prev_sampledata = sampledata;
+                i++;
         }
 
         /* overlay all the text labels */
-        for (i = 1; i < samples ; i++) {
+        i = 1;
+        LIST_FOREACH_BEFORE(link, sampledata, head) {
                 int bottom;
                 int top;
+                struct ps_sched_struct *prev_sample;
+                struct ps_sched_struct *cross_place;
 
                 bottom = 0;
                 top = 0;
 
                 /* put all the small pss blocks into the bottom */
-                ps = ps_first;
+                ps = ps_first->next_ps;
                 while (ps->next_ps) {
                         ps = ps->next_ps;
                         if (!ps)
                                 continue;
-                        if (ps->sample[i].pss <= (100 * arg_scale_y))
-                                top += ps->sample[i].pss;
-                };
-
+                        ps->sample = ps->first;
+                        while (ps->sample->next) {
+                                ps->sample = ps->sample->next;
+                                if (ps->sample->sampledata == sampledata)
+                                        break;
+                        }
+                        if (ps->sample->sampledata == sampledata) {
+                                if (ps->sample->pss <= (100 * arg_scale_y))
+                                        top += ps->sample->pss;
+                                break;
+                        }
+                }
+                while ((cross_place = ps->sample->cross)) {
+                        ps = ps->sample->cross->ps_new;
+                        ps->sample = cross_place;
+                        if (ps->sample->pss <= (100 * arg_scale_y))
+                                top += ps->sample->pss;
+                }
                 bottom = top;
 
                 /* now plot the ones that are of significant size */
                 ps = ps_first;
                 while (ps->next_ps) {
+                        prev_sample = ps->sample;
                         ps = ps->next_ps;
                         if (!ps)
                                 continue;
+                        ps->sample = ps->first;
+                        while (ps->sample->next) {
+                                prev_sample = ps->sample;
+                                ps->sample = ps->sample->next;
+                                if (ps->sample->sampledata == sampledata)
+                                        break;
+                        }
                         /* don't draw anything smaller than 2mb */
-                        if (ps->sample[i].pss > (100 * arg_scale_y)) {
-                                top = bottom + ps->sample[i].pss;
+                        if (ps->sample->sampledata == sampledata) {
+                                if (ps->sample->pss > (100 * arg_scale_y)) {
+                                        top = bottom + ps->sample->pss;
+                                        /* draw a label with the process / PID */
+                                        if ((i == 1) || (prev_sample->pss <= (100 * arg_scale_y)))
+                                                svg("  <text x=\"%.03f\" y=\"%.03f\"><![CDATA[%s]]> [%i]</text>\n",
+                                                    time_to_graph(sampledata->sampletime - graph_start),
+                                                    kb_to_graph(1000000.0 - bottom - ((top -  bottom) / 2)),
+                                                    ps->name,
+                                                    ps->pid);
+                                        bottom = top;
+                                }
+                                break;
+                        }
+                }
+                while ((cross_place = ps->sample->cross)) {
+                        ps = ps->sample->cross->ps_new;
+                        ps->sample = cross_place;
+                        prev_sample = ps->sample->prev;
+                        if (ps->sample->pss > (100 * arg_scale_y)) {
+                                top = bottom + ps->sample->pss;
                                 /* draw a label with the process / PID */
-                                if ((i == 1) || (ps->sample[i - 1].pss <= (100 * arg_scale_y)))
+                                if ((i == 1) || (prev_sample->pss <= (100 * arg_scale_y)))
                                         svg("  <text x=\"%.03f\" y=\"%.03f\"><![CDATA[%s]]> [%i]</text>\n",
-                                            time_to_graph(sampletime[i] - graph_start),
+                                            time_to_graph(sampledata->sampletime - graph_start),
                                             kb_to_graph(1000000.0 - bottom - ((top -  bottom) / 2)),
                                             ps->name,
                                             ps->pid);
                                 bottom = top;
                         }
                 }
+                i++;
         }
 
         /* debug output - full data dump */
@@ -400,8 +517,10 @@ static void svg_pss_graph(void) {
 
                 svg("<!-- %s [%d] pss=", enc_name, ps->pid);
 
-                for (i = 0; i < samples ; i++) {
-                        svg("%d," , ps->sample[i].pss);
+                ps->sample = ps->first;
+                while (ps->sample->next) {
+                        ps->sample = ps->sample->next;
+                        svg("%d," , ps->sample->pss);
                 }
                 svg(" -->\n");
         }
@@ -413,6 +532,9 @@ static void svg_io_bi_bar(void) {
         double range;
         int max_here = 0;
         int i;
+        int k;
+        struct list_sample_data *start_sampledata = sampledata;
+        struct list_sample_data *stop_sampledata = sampledata;
 
         svg("<!-- IO utilization graph - In -->\n");
 
@@ -433,54 +555,89 @@ static void svg_io_bi_bar(void) {
         svg_graph_box(5);
 
         /* find the max IO first */
-        for (i = 1; i < samples; i++) {
+        i = 1;
+        LIST_FOREACH_BEFORE(link, sampledata, head) {
                 int start;
                 int stop;
+                int diff;
                 double tot;
 
                 start = MAX(i - ((range / 2) - 1), 0);
                 stop = MIN(i + (range / 2), samples - 1);
+                diff = (stop - start);
+
+                start_sampledata = sampledata;
+                stop_sampledata = sampledata;
+
+                for (k=0;(k<((range/2)-1))&&(start_sampledata->link_next);k++)
+                        start_sampledata = start_sampledata->link_next;
+                for (k=0;(k<(range/2))&&(stop_sampledata->link_prev);k++)
+                        stop_sampledata = stop_sampledata->link_prev;
+
+                tot = (double)(stop_sampledata->blockstat.bi - start_sampledata->blockstat.bi)
+                        / diff;
 
-                tot = (double)(blockstat[stop].bi - blockstat[start].bi)
-                      / (stop - start);
                 if (tot > max) {
                         max = tot;
                         max_here = i;
                 }
-                tot = (double)(blockstat[stop].bo - blockstat[start].bo)
-                      / (stop - start);
+
+                tot = (double)(stop_sampledata->blockstat.bo - start_sampledata->blockstat.bo)
+                        / diff;
+
                 if (tot > max)
                         max = tot;
+
+                i++;
         }
 
         /* plot bi */
-        for (i = 1; i < samples; i++) {
+        i = 1;
+        prev_sampledata = head;
+        LIST_FOREACH_BEFORE(link, sampledata, head) {
                 int start;
                 int stop;
+                int diff;
                 double tot;
                 double pbi;
 
+                tot = 0;
+                pbi = 0;
+
                 start = MAX(i - ((range / 2) - 1), 0);
                 stop = MIN(i + (range / 2), samples);
+                diff = (stop - start);
+
+                start_sampledata = sampledata;
+                stop_sampledata = sampledata;
+
+                for (k=0;(k<((range/2)-1))&&(start_sampledata->link_next);k++)
+                        start_sampledata = start_sampledata->link_next;
+                for (k=0;(k<(range/2))&&(stop_sampledata->link_prev);k++)
+                        stop_sampledata = stop_sampledata->link_prev;
 
-                tot = (double)(blockstat[stop].bi - blockstat[start].bi)
-                      / (stop - start);
-                pbi = tot / max;
+                tot = (double)(stop_sampledata->blockstat.bi - start_sampledata->blockstat.bi)
+                        / diff;
+
+                if (max > 0)
+                        pbi = tot / max;
 
                 if (pbi > 0.001)
                         svg("<rect class=\"bi\" x=\"%.03f\" y=\"%.03f\" width=\"%.03f\" height=\"%.03f\" />\n",
-                            time_to_graph(sampletime[i - 1] - graph_start),
+                            time_to_graph(prev_sampledata->sampletime - graph_start),
                             (arg_scale_y * 5) - (pbi * (arg_scale_y * 5)),
-                            time_to_graph(sampletime[i] - sampletime[i - 1]),
+                            time_to_graph(sampledata->sampletime - prev_sampledata->sampletime),
                             pbi * (arg_scale_y * 5));
 
                 /* labels around highest value */
                 if (i == max_here) {
                         svg("  <text class=\"sec\" x=\"%.03f\" y=\"%.03f\">%0.2fmb/sec</text>\n",
-                            time_to_graph(sampletime[i] - graph_start) + 5,
+                            time_to_graph(sampledata->sampletime - graph_start) + 5,
                             ((arg_scale_y * 5) - (pbi * (arg_scale_y * 5))) + 15,
                             max / 1024.0 / (interval / 1000000000.0));
                 }
+                i++;
+                prev_sampledata = sampledata;
         }
 }
 
@@ -489,6 +646,9 @@ static void svg_io_bo_bar(void) {
         double range;
         int max_here = 0;
         int i;
+        int k;
+        struct list_sample_data *start_sampledata = sampledata;
+        struct list_sample_data *stop_sampledata = sampledata;
 
         svg("<!-- IO utilization graph - out -->\n");
 
@@ -509,59 +669,89 @@ static void svg_io_bo_bar(void) {
         svg_graph_box(5);
 
         /* find the max IO first */
-        for (i = 1; i < samples; i++) {
+        i = 0;
+        LIST_FOREACH_BEFORE(link, sampledata, head) {
                 int start;
                 int stop;
+                int diff;
                 double tot;
 
                 start = MAX(i - ((range / 2) - 1), 0);
                 stop = MIN(i + (range / 2), samples - 1);
+                diff = (stop - start);
+
+                start_sampledata = sampledata;
+                stop_sampledata = sampledata;
+
+                for (k=0;(k<((range/2)-1))&&(start_sampledata->link_next);k++)
+                        start_sampledata = start_sampledata->link_next;
+                for (k=0;(k<(range/2))&&(stop_sampledata->link_prev);k++)
+                        stop_sampledata = stop_sampledata->link_prev;
 
-                tot = (double)(blockstat[stop].bi - blockstat[start].bi)
-                      / (stop - start);
+                tot = (double)(stop_sampledata->blockstat.bi - start_sampledata->blockstat.bi)
+                        / diff;
                 if (tot > max)
                         max = tot;
-                tot = (double)(blockstat[stop].bo - blockstat[start].bo)
-                      / (stop - start);
+                tot = (double)(stop_sampledata->blockstat.bo - start_sampledata->blockstat.bo)
+                        / diff;
                 if (tot > max) {
                         max = tot;
                         max_here = i;
                 }
+                i++;
         }
 
         /* plot bo */
-        for (i = 1; i < samples; i++) {
+        prev_sampledata = head;
+        i=1;
+        LIST_FOREACH_BEFORE(link, sampledata, head) {
                 int start;
                 int stop;
+                int diff;
                 double tot;
                 double pbo;
 
+                tot = 0;
+                pbo = 0;
+
                 start = MAX(i - ((range / 2) - 1), 0);
                 stop = MIN(i + (range / 2), samples);
+                diff = (stop - start);
+
+                start_sampledata = sampledata;
+                stop_sampledata = sampledata;
+
+                for (k=0;(k<((range/2)-1))&&(start_sampledata->link_next);k++)
+                        start_sampledata = start_sampledata->link_next;
+                for (k=0;(k<(range/2))&&(stop_sampledata->link_prev);k++)
+                        stop_sampledata = stop_sampledata->link_prev;
 
-                tot = (double)(blockstat[stop].bo - blockstat[start].bo)
-                      / (stop - start);
-                pbo = tot / max;
+                tot = (double)(stop_sampledata->blockstat.bo - start_sampledata->blockstat.bo)
+                        / diff;
+
+                if (max > 0)
+                        pbo = tot / max;
 
                 if (pbo > 0.001)
                         svg("<rect class=\"bo\" x=\"%.03f\" y=\"%.03f\" width=\"%.03f\" height=\"%.03f\" />\n",
-                            time_to_graph(sampletime[i - 1] - graph_start),
+                            time_to_graph(prev_sampledata->sampletime - graph_start),
                             (arg_scale_y * 5) - (pbo * (arg_scale_y * 5)),
-                            time_to_graph(sampletime[i] - sampletime[i - 1]),
+                            time_to_graph(sampledata->sampletime - prev_sampledata->sampletime),
                             pbo * (arg_scale_y * 5));
 
                 /* labels around highest bo value */
                 if (i == max_here) {
                         svg("  <text class=\"sec\" x=\"%.03f\" y=\"%.03f\">%0.2fmb/sec</text>\n",
-                            time_to_graph(sampletime[i] - graph_start) + 5,
+                            time_to_graph(sampledata->sampletime - graph_start) + 5,
                             ((arg_scale_y * 5) - (pbo * (arg_scale_y * 5))),
                             max / 1024.0 / (interval / 1000000000.0));
                 }
+                i++;
+                prev_sampledata = sampledata;
         }
 }
 
 static void svg_cpu_bar(void) {
-        int i;
 
         svg("<!-- CPU utilization graph -->\n");
 
@@ -570,7 +760,8 @@ static void svg_cpu_bar(void) {
         svg_graph_box(5);
 
         /* bars for each sample, proportional to the CPU util. */
-        for (i = 1; i < samples; i++) {
+        prev_sampledata = head;
+        LIST_FOREACH_BEFORE(link, sampledata, head) {
                 int c;
                 double trt;
                 double ptrt;
@@ -578,30 +769,30 @@ static void svg_cpu_bar(void) {
                 ptrt = trt = 0.0;
 
                 for (c = 0; c < cpus; c++)
-                        trt += cpustat[c].sample[i].runtime - cpustat[c].sample[i - 1].runtime;
+                        trt += sampledata->runtime[c] - prev_sampledata->runtime[c];
 
                 trt = trt / 1000000000.0;
 
                 trt = trt / (double)cpus;
 
                 if (trt > 0.0)
-                        ptrt = trt / (sampletime[i] - sampletime[i - 1]);
+                        ptrt = trt / (sampledata->sampletime - prev_sampledata->sampletime);
 
                 if (ptrt > 1.0)
                         ptrt = 1.0;
 
                 if (ptrt > 0.001) {
                         svg("<rect class=\"cpu\" x=\"%.03f\" y=\"%.03f\" width=\"%.03f\" height=\"%.03f\" />\n",
-                            time_to_graph(sampletime[i - 1] - graph_start),
+                            time_to_graph(prev_sampledata->sampletime - graph_start),
                             (arg_scale_y * 5) - (ptrt * (arg_scale_y * 5)),
-                            time_to_graph(sampletime[i] - sampletime[i - 1]),
+                            time_to_graph(sampledata->sampletime - prev_sampledata->sampletime),
                             ptrt * (arg_scale_y * 5));
                 }
+                prev_sampledata = sampledata;
         }
 }
 
 static void svg_wait_bar(void) {
-        int i;
 
         svg("<!-- Wait time aggregation box -->\n");
 
@@ -611,7 +802,8 @@ static void svg_wait_bar(void) {
         svg_graph_box(5);
 
         /* bars for each sample, proportional to the CPU util. */
-        for (i = 1; i < samples; i++) {
+        prev_sampledata = head;
+        LIST_FOREACH_BEFORE(link, sampledata, head) {
                 int c;
                 double twt;
                 double ptwt;
@@ -619,31 +811,31 @@ static void svg_wait_bar(void) {
                 ptwt = twt = 0.0;
 
                 for (c = 0; c < cpus; c++)
-                        twt += cpustat[c].sample[i].waittime - cpustat[c].sample[i - 1].waittime;
+                        twt += sampledata->waittime[c] - prev_sampledata->waittime[c];
 
                 twt = twt / 1000000000.0;
 
                 twt = twt / (double)cpus;
 
                 if (twt > 0.0)
-                        ptwt = twt / (sampletime[i] - sampletime[i - 1]);
+                        ptwt = twt / (sampledata->sampletime - prev_sampledata->sampletime);
 
                 if (ptwt > 1.0)
                         ptwt = 1.0;
 
                 if (ptwt > 0.001) {
                         svg("<rect class=\"wait\" x=\"%.03f\" y=\"%.03f\" width=\"%.03f\" height=\"%.03f\" />\n",
-                            time_to_graph(sampletime[i - 1] - graph_start),
+                            time_to_graph(prev_sampledata->sampletime - graph_start),
                             ((arg_scale_y * 5) - (ptwt * (arg_scale_y * 5))),
-                            time_to_graph(sampletime[i] - sampletime[i - 1]),
+                            time_to_graph(sampledata->sampletime - prev_sampledata->sampletime),
                             ptwt * (arg_scale_y * 5));
                 }
+                prev_sampledata = sampledata;
         }
 }
 
 
 static void svg_entropy_bar(void) {
-        int i;
 
         svg("<!-- entropy pool graph -->\n");
 
@@ -652,13 +844,15 @@ static void svg_entropy_bar(void) {
         svg_graph_box(5);
 
         /* bars for each sample, scale 0-4096 */
-        for (i = 1; i < samples; i++) {
+        prev_sampledata = head;
+        LIST_FOREACH_BEFORE(link, sampledata, head) {
                 /* svg("<!-- entropy %.03f %i -->\n", sampletime[i], entropy_avail[i]); */
                 svg("<rect class=\"cpu\" x=\"%.03f\" y=\"%.03f\" width=\"%.03f\" height=\"%.03f\" />\n",
-                    time_to_graph(sampletime[i - 1] - graph_start),
-                    ((arg_scale_y * 5) - ((entropy_avail[i] / 4096.) * (arg_scale_y * 5))),
-                    time_to_graph(sampletime[i] - sampletime[i - 1]),
-                    (entropy_avail[i] / 4096.) * (arg_scale_y * 5));
+                    time_to_graph(prev_sampledata->sampletime - graph_start),
+                    ((arg_scale_y * 5) - ((sampledata->entropy_avail / 4096.) * (arg_scale_y * 5))),
+                    time_to_graph(sampledata->sampletime - prev_sampledata->sampletime),
+                    (sampledata->entropy_avail / 4096.) * (arg_scale_y * 5));
+                prev_sampledata = sampledata;
         }
 }
 
@@ -802,8 +996,8 @@ static void svg_ps_bars(void) {
         struct ps_struct *ps;
         int i = 0;
         int j = 0;
-        int w;
         int pid;
+        double w = 0.0;
 
         svg("<!-- Process graph -->\n");
 
@@ -816,7 +1010,7 @@ static void svg_ps_bars(void) {
         ps = ps_first;
         while ((ps = get_next_ps(ps))) {
                 _cleanup_free_ char *enc_name = NULL;
-
+                double endtime;
                 double starttime;
                 int t;
 
@@ -828,15 +1022,13 @@ static void svg_ps_bars(void) {
                 svg("<!-- %s [%i] ppid=%i runtime=%.03fs -->\n", enc_name, ps->pid,
                     ps->ppid, ps->total);
 
-                /* it would be nice if we could use exec_start from /proc/pid/sched,
-                 * but it's unreliable and gives bogus numbers */
-                starttime = sampletime[ps->first];
+                starttime = ps->first->sampledata->sampletime;
 
                 if (!ps_filter(ps)) {
                         /* remember where _to_ our children need to draw a line */
                         ps->pos_x = time_to_graph(starttime - graph_start);
                         ps->pos_y = ps_to_graph(j+1); /* bottom left corner */
-                } else {
+                } else if (ps->parent){
                         /* hook children to our parent coords instead */
                         ps->pos_x = ps->parent->pos_x;
                         ps->pos_y = ps->parent->pos_y;
@@ -851,23 +1043,30 @@ static void svg_ps_bars(void) {
                         continue;
                 }
 
+                endtime = ps->last->sampledata->sampletime;
                 svg("  <rect class=\"ps\" x=\"%.03f\" y=\"%.03f\" width=\"%.03f\" height=\"%.03f\" />\n",
                     time_to_graph(starttime - graph_start),
                     ps_to_graph(j),
-                    time_to_graph(sampletime[ps->last] - starttime),
+                    time_to_graph(ps->last->sampledata->sampletime - starttime),
                     ps_to_graph(1));
 
                 /* paint cpu load over these */
-                for (t = ps->first + 1; t < ps->last; t++) {
+                ps->sample = ps->first;
+                t = 1;
+                while (ps->sample->next) {
                         double rt, prt;
                         double wt, wrt;
+                        struct ps_sched_struct *prev;
+
+                        prev = ps->sample;
+                        ps->sample = ps->sample->next;
 
                         /* calculate over interval */
-                        rt = ps->sample[t].runtime - ps->sample[t-1].runtime;
-                        wt = ps->sample[t].waittime - ps->sample[t-1].waittime;
+                        rt = ps->sample->runtime - prev->runtime;
+                        wt = ps->sample->waittime - prev->waittime;
 
-                        prt = (rt / 1000000000) / (sampletime[t] - sampletime[t-1]);
-                        wrt = (wt / 1000000000) / (sampletime[t] - sampletime[t-1]);
+                        prt = (rt / 1000000000) / (ps->sample->sampledata->sampletime - prev->sampledata->sampletime);
+                        wrt = (wt / 1000000000) / (ps->sample->sampledata->sampletime - prev->sampledata->sampletime);
 
                         /* this can happen if timekeeping isn't accurate enough */
                         if (prt > 1.0)
@@ -879,33 +1078,34 @@ static void svg_ps_bars(void) {
                                 continue;
 
                         svg("    <rect class=\"wait\" x=\"%.03f\" y=\"%.03f\" width=\"%.03f\" height=\"%.03f\" />\n",
-                            time_to_graph(sampletime[t - 1] - graph_start),
+                            time_to_graph(prev->sampledata->sampletime - graph_start),
                             ps_to_graph(j),
-                            time_to_graph(sampletime[t] - sampletime[t - 1]),
+                            time_to_graph(ps->sample->sampledata->sampletime - prev->sampledata->sampletime),
                             ps_to_graph(wrt));
 
                         /* draw cpu over wait - TODO figure out how/why run + wait > interval */
                         svg("    <rect class=\"cpu\" x=\"%.03f\" y=\"%.03f\" width=\"%.03f\" height=\"%.03f\" />\n",
-                            time_to_graph(sampletime[t - 1] - graph_start),
+                            time_to_graph(prev->sampledata->sampletime - graph_start),
                             ps_to_graph(j + (1.0 - prt)),
-                            time_to_graph(sampletime[t] - sampletime[t - 1]),
+                            time_to_graph(ps->sample->sampledata->sampletime - prev->sampledata->sampletime),
                             ps_to_graph(prt));
+                        t++;
                 }
 
                 /* determine where to display the process name */
-                if (sampletime[ps->last] - sampletime[ps->first] < 1.5)
+                if ((endtime - starttime) < 1.5)
                         /* too small to fit label inside the box */
-                        w = ps->last;
+                        w = endtime;
                 else
-                        w = ps->first;
+                        w = starttime;
 
                 /* text label of process name */
                 svg("  <text x=\"%.03f\" y=\"%.03f\"><![CDATA[%s]]> [%i]<tspan class=\"run\">%.03fs</tspan></text>\n",
-                    time_to_graph(sampletime[w] - graph_start) + 5.0,
+                    time_to_graph(w - graph_start) + 5.0,
                     ps_to_graph(j) + 14.0,
                     ps->name,
                     ps->pid,
-                    (ps->sample[ps->last].runtime - ps->sample[ps->first].runtime) / 1000000000.0);
+                    (ps->last->runtime - ps->first->runtime) / 1000000000.0);
                 /* paint lines to the parent process */
                 if (ps->parent) {
                         /* horizontal part */
@@ -934,6 +1134,7 @@ static void svg_ps_bars(void) {
         /* make sure we start counting from the point where we actually have
          * data: assume that bootchart's first sample is when data started
          */
+
         ps = ps_first;
         while (ps->next_ps) {
                 ps = ps->next_ps;
@@ -941,17 +1142,27 @@ static void svg_ps_bars(void) {
                         break;
         }
 
-        for (i = ps->first; i < samples - (arg_hz / 2); i++) {
+        /* need to know last node first */
+        ps->sample = ps->first;
+        i = ps->sample->next->sampledata->counter;
+
+        while (ps->sample->next && i<(samples-(arg_hz/2))) {
                 double crt;
                 double brt;
                 int c;
+                int ii;
+                struct ps_sched_struct *sample_hz;
+
+                ps->sample = ps->sample->next;
+                sample_hz = ps->sample;
+                for (ii=0;((ii<(int)arg_hz/2)&&(ps->sample->next));ii++)
+                        sample_hz = sample_hz->next;
 
                 /* subtract bootchart cpu utilization from total */
                 crt = 0.0;
                 for (c = 0; c < cpus; c++)
-                        crt += cpustat[c].sample[i + ((int)arg_hz / 2)].runtime - cpustat[c].sample[i].runtime;
-                brt = ps->sample[i + ((int)arg_hz / 2)].runtime - ps->sample[i].runtime;
-
+                        crt += sample_hz->sampledata->runtime[c] - ps->sample->sampledata->runtime[c];
+                brt = sample_hz->runtime - ps->sample->runtime;
                 /*
                  * our definition of "idle":
                  *
@@ -959,7 +1170,7 @@ static void svg_ps_bars(void) {
                  * defaults to 4.0%, which experimentally, is where atom idles
                  */
                 if ((crt - brt) < (interval / 2.0)) {
-                        idletime = sampletime[i] - graph_start;
+                        idletime = ps->sample->sampledata->sampletime - graph_start;
                         svg("\n<!-- idle detected at %.03f seconds -->\n",
                             idletime);
                         svg("<line class=\"idle\" x1=\"%.03f\" y1=\"%.03f\" x2=\"%.03f\" y2=\"%.03f\" />\n",
@@ -973,6 +1184,7 @@ static void svg_ps_bars(void) {
                             idletime);
                         break;
                 }
+                i++;
         }
 }