Just some stuff for AEDZL.wip-aedzl-revised

5 files changed, 463 insertions, 7 deletions

diff --git a/SConstruct b/SConstruct
index 377297c..c265d89 100644
--- a/SConstruct
+++ b/SConstruct
@@ -19,9 +19,11 @@ if os != 'Linux':
 # base config
 env = Environment(
     CC = 'gcc',
+        CXX = 'g++',
     CCFLAGS = Split(DEBUG_FLAGS),
     CPPPATH = Split(INCLUDE_DIRS),
     CPPDEFINES = '-DMAX_TASKS=%d' % MAX_TASKS,
+        LIBS = Split('blitz m')
 )
 
 # #####################################################################
@@ -29,3 +31,4 @@ env = Environment(
 common = ['src/load.c', 'src/eheap.c', 'src/util.c']
 env.Program('st_convert', ['src/st2pl.c'] + common)
 env.Program('st_show', ['src/showst.c'] + common)
+env.Program('st_show2', ['src/showst2.cpp'] + common)
diff --git a/include/load.h b/include/load.h
index e4a35c2..6d13d07 100644
--- a/include/load.h
+++ b/include/load.h
@@ -67,7 +67,7 @@ u32 count_tasks(void);
 #define for_each_event_t(t, e, evtype) \
         for_each_event(t, e) if (e->rec->hdr.type == evtype)
 
-#define find(e, evtype) \
+#define _find(e, evtype) \
         while (e && e->rec->hdr.type != evtype) e = e->next; if (!e) break;
 
 
diff --git a/include/sched_trace.h b/include/sched_trace.h
index 8bdd253..6b69827 100644
--- a/include/sched_trace.h
+++ b/include/sched_trace.h
@@ -4,6 +4,7 @@
 #include <stdint.h>
 
 typedef uint8_t  u8;
+typedef int32_t  s32;
 typedef uint32_t u32;
 typedef uint16_t u16;
 typedef uint64_t u64;
@@ -66,6 +67,13 @@ struct st_completion_data {	/* A job completed. */
         u8      __unused[3];
 };
 
+struct st_completion_adaptive_data {
+        u32 actual_exe;
+        u32 estimated_exe;
+        s32 accumulated_err;
+        u8 __unused[4];
+};
+
 struct st_block_data {          /* A task blocks. */
         u64     when;
         u64     __unused;
@@ -95,6 +103,7 @@ typedef enum {
         ST_BLOCK,
         ST_RESUME,
         ST_SYS_RELEASE,
+        ST_COMPLETION_ADAPTIVE
 } st_event_record_type_t;
 
 struct st_event_record {
@@ -112,6 +121,7 @@ struct st_event_record {
                 DATA(block);
                 DATA(resume);
                 DATA(sys_release);
+                DATA(completion_adaptive);
 
         } data;
 };
diff --git a/src/showst2.cpp b/src/showst2.cpp
new file mode 100644
index 0000000..71f324a
--- /dev/null
+++ b/src/showst2.cpp
@@ -0,0 +1,443 @@
+#include <iostream>
+#include <sstream>
+#include <fstream>
+#include <set>
+#include <vector>
+#include <map>
+
+#include <blitz/array.h>
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+
+extern "C"
+{
+#include "load.h"
+#include "sched_trace.h"
+#include "eheap.h"
+}
+
+using namespace std;
+using namespace blitz;
+
+double SCALE = 1000000.0; // ms
+//double SCALE =   1000.0; // us
+
+static void usage(const char *str)
+{
+        fprintf(stderr,
+                "\n  USAGE\n"
+                "\n"
+                "    st_show [opts] <file.st>+\n"
+                "\n"
+                "  OPTIONS\n"
+                "     -r         -- find task system release and exit\n"
+                "     -f         -- use first non-zero event as system release\n"
+                "                   if no system release event is found\n"
+                "     -c         -- display a count of the number of events\n"
+                "\n\n"
+                );
+        fprintf(stderr, "Aborted: %s\n", str);
+        exit(1);
+}
+
+struct Job
+{
+        u32 jid;
+
+        mutable u32 actual_exe;
+        mutable u32 estimated_exe;
+        mutable s32 accum_err;
+
+        mutable u64 release;
+        mutable u64 deadline;
+        mutable u64 completion;
+
+        bool operator<(const Job& rhs) const
+        {
+                return(jid < rhs.jid);
+        }
+};
+
+struct Task
+{
+        u16 pid;
+
+        mutable u32 wcet;
+        mutable u32 period;
+
+        bool operator<(const Task& rhs) const
+        {
+                return(pid < rhs.pid);
+        }
+};
+
+map<Task, set<Job> > traceData;
+
+template <class T>
+double stddev(const T& arr)
+{
+    double stddev;
+
+    if(arr.size() > 1)
+    {
+        double avg = blitz::mean(arr);
+
+        blitz::Array<double, 1> devs(arr.size());
+        devs = arr - avg;
+        devs *= devs;
+        double devsum = blitz::sum(devs);
+        stddev = sqrt(devsum/(devs.size()-1));
+    }
+    else
+    {
+        stddev = 0.0;
+    }
+
+    return(stddev);
+}
+
+#define OPTSTR "rcf"
+
+int main(int argc, char** argv)
+{
+        unsigned int count;
+        struct heap *h;
+        struct heap_node *hn, *first = NULL;
+        u64 time;
+        struct st_event_record *rec;
+        int find_release = 0;
+        int show_count = 0;
+        int use_first_nonzero = 0;
+        int opt;
+
+        while ((opt = getopt(argc, argv, OPTSTR)) != -1) {
+                switch (opt) {
+                case 'r':
+                        find_release = 1;
+                        break;
+                case 'c':
+                        show_count = 1;
+                        break;
+                case 'f':
+                        use_first_nonzero = 1;
+                        break;
+                case ':':
+                        usage("Argument missing.");
+                        break;
+                case '?':
+                default:
+                        usage("Bad argument.");
+                        break;
+                }
+        }
+
+        u64 starttime = 0;
+
+        h = load(argv + optind, argc - optind, &count);
+        if (!h)
+                return 1;
+        if (show_count)
+                printf("Loaded %u events.\n", count);
+        while ((hn = heap_take(earlier_event, h))) {
+
+                rec = (st_event_record*)heap_node_value(hn);
+
+                time =  event_time(rec);
+                if (time != 0 && !first)
+                        first = hn;
+                time /= 1000000; /* convert to milliseconds */
+
+                if(rec->hdr.type == ST_SYS_RELEASE && starttime == 0)
+                {
+                        starttime = rec->data.sys_release.when;
+                }
+                else if(rec->hdr.type == ST_PARAM)
+                {
+                        Task tsk;
+                        tsk.pid = rec->hdr.pid;
+                        tsk.wcet = rec->data.param.wcet;
+                        tsk.period = rec->data.param.period;
+
+                        map<Task, set<Job> >::iterator iter = traceData.find(tsk);
+                        if(iter == traceData.end())
+                        {
+                                traceData[tsk] = set<Job>();
+                        }
+                        else
+                        {
+                                iter->first.wcet = rec->data.param.wcet;
+                                iter->first.period = rec->data.param.period;
+                        }
+                }
+                else if(rec->hdr.type == ST_RELEASE)
+                {
+                        Task srch;
+                        srch.pid = rec->hdr.pid;
+
+                        map<Task, set<Job> >::iterator iter = traceData.find(srch);
+
+                        // force the task to be there.
+                        if(iter == traceData.end())
+                        {
+                                traceData[srch] = set<Job>();
+                                iter = traceData.find(srch);
+                                iter->first.period = rec->data.release.release - rec->data.release.deadline;
+                        }
+
+                        if(iter != traceData.end())
+                        {
+                                Job jsrch;
+                                jsrch.jid = rec->hdr.job;
+
+                                set<Job>::iterator jter = iter->second.find(jsrch);
+                                if(jter == iter->second.end())
+                                {
+                                        jsrch.release = rec->data.release.release;
+                                        jsrch.deadline = rec->data.release.deadline;
+                                        jsrch.completion = 0;
+                                        jsrch.actual_exe = 0;
+                                        jsrch.estimated_exe = 0;
+                                        jsrch.accum_err = 0;
+                                        iter->second.insert(jsrch);
+                                }
+                                else
+                                {
+                                        jter->release = rec->data.release.release;
+                                        jter->deadline = rec->data.release.deadline;
+                                }
+                        }
+                        else
+                        {
+                                cerr<<"Could not match release to task."<<endl;
+                        }
+                }
+                else if(rec->hdr.type == ST_COMPLETION)
+                {
+                        Task srch;
+                        srch.pid = rec->hdr.pid;
+
+            map<Task, set<Job> >::iterator iter = traceData.find(srch);
+
+                        // force the task to be there.
+                        if(iter == traceData.end())
+                        {   
+                                traceData[srch] = set<Job>();
+                                iter = traceData.find(srch);
+                                iter->first.period = 0;
+                        }   
+
+                        if(iter != traceData.end())
+                        {
+                                Job jsrch;
+                                jsrch.jid = rec->hdr.job;
+                                set<Job>::iterator j = iter->second.find(jsrch);
+
+
+                                if(j == iter->second.end())
+                                {
+                                        jsrch.release = 0;
+                                        jsrch.deadline = 0;
+                                        jsrch.actual_exe = 0;
+                                        jsrch.estimated_exe = 0;
+                                        jsrch.accum_err = 0;
+                                        iter->second.insert(jsrch);
+                                        j = iter->second.find(jsrch);
+                                }
+
+                                if(j != iter->second.end())
+                                {
+                                        j->completion = rec->data.completion.when;
+                                }
+                                else
+                                {
+                                        cerr<<"Could not find the job to complete."<<endl;
+                                }
+                        }
+                        else
+                        {
+                                cerr<<"Could not find the task for which has a job to complete."<<endl;
+                        }
+                }
+                else if(rec->hdr.type == ST_COMPLETION_ADAPTIVE)
+                {
+                        Task srch;
+                        srch.pid = rec->hdr.pid;
+
+                        map<Task, set<Job> >::iterator iter = traceData.find(srch);
+
+            // force the task to be there.
+                        if(iter == traceData.end())
+                        {
+                                traceData[srch] = set<Job>();
+                                iter = traceData.find(srch);
+                                iter->first.period = 0;
+                        }
+
+                        if(iter != traceData.end())
+                        {
+                                Job jsrch;
+                                jsrch.jid = rec->hdr.job;
+                                set<Job>::iterator j = iter->second.find(jsrch);
+
+                                if(j == iter->second.end())
+                                {
+                                        jsrch.release = 0;
+                                        jsrch.deadline = 0;
+                                        jsrch.completion = 0;
+                                        iter->second.insert(jsrch);
+                                        j = iter->second.find(jsrch);
+                                }
+
+                                if(j != iter->second.end())
+                                {
+                                        j->actual_exe = rec->data.completion_adaptive.actual_exe;
+                                        j->estimated_exe = rec->data.completion_adaptive.estimated_exe;
+                                        j->accum_err = rec->data.completion_adaptive.accumulated_err;
+                                }
+                                else
+                                {
+                                        cerr<<"Could not find the job to complete."<<endl;
+                                }
+                        }
+                        else
+                        {
+                                cerr<<"Could not find the task for which has a job to complete."<<endl;
+                        }
+                }
+        }
+
+        // data loaded.  discard unfinished jobs. and first and last.
+        for(map<Task, set<Job> >::iterator tsk(traceData.begin()), tskEnd(traceData.end());
+                tsk != tskEnd;
+                ++tsk)
+        {
+                if(!tsk->second.empty())
+                {
+                        tsk->second.erase(tsk->second.begin());
+                }
+                if(!tsk->second.empty())
+                {
+                        set<Job>::iterator last(tsk->second.end());
+                        --last;
+                        tsk->second.erase(last);
+                }
+
+                for(set<Job>::iterator job(tsk->second.begin()), jobEnd(tsk->second.end());
+                        job != jobEnd;
+                        )
+                {
+                        if(job->completion == 0 || job->release == 0 || job->deadline == 0)
+                        {
+                                set<Job>::iterator temp(job);
+                                ++job;
+                                tsk->second.erase(temp);
+                        }
+                        else
+                        {
+                                ++job;
+                        }
+                }
+        }
+
+        
+        ofstream outs;
+        outs.open("summary.csv");
+        outs<<"#period, wcet (us), mean_exe, stdev_exe, min_delta_exe, max_delta_exe, mean_delta_exe, stdev_delta_exe, min_rt, max_rt, mean_rt, stdev_rt, min_tardy, max_tardy, mean_tardy, std_tardy"<<endl;
+
+        // print stats.
+        for(map<Task, set<Job> >::iterator tsk(traceData.begin()), tskEnd(traceData.end());
+                tsk != tskEnd;
+                ++tsk)
+        {
+                size_t sz = tsk->second.size();
+                Array<double, 1> releases(sz);
+                Array<double, 1> completions(sz);
+                Array<double, 1> deadlines(sz);
+
+                Array<double, 1> actual_exes(sz);
+                Array<double, 1> est_exes(sz);
+                Array<double, 1> accum_errs(sz);
+
+                int i = 0;
+                for(set<Job>::iterator job(tsk->second.begin()), jobEnd(tsk->second.end());
+                        job != jobEnd;
+                        ++job, ++i)
+                {
+                        releases(i) = (double)job->release;
+                        completions(i) = (double)job->completion;
+                        deadlines(i) = (double)job->deadline;
+
+                        actual_exes(i) = (double)job->actual_exe;
+                        est_exes(i) = (double)job->estimated_exe;
+                        accum_errs(i) = (double)job->accum_err;
+                }
+
+                Array<double, 1> rt(sz);
+                Array<double, 1> tardy(sz);
+                Array<double, 1> delta_exe(sz);
+
+                rt = completions - releases;
+                tardy = where(completions > deadlines, completions - deadlines, 0.0);
+                delta_exe = actual_exes - est_exes;
+
+                // done computing data.  dump stuff to files.
+
+                // tardiness growth and estimates
+                stringstream filename;
+                double per = ((int)(roundf(tsk->first.period/10000.0)))/100.0;
+                double exe = ((int)(roundf(tsk->first.wcet/10000.0)))/100.0;
+                filename<<"e"<<exe<<"_p"<<per<<"_pid"<<tsk->first.pid;
+                if(stddev(actual_exes)/SCALE > 0.4)
+                {
+                        filename<<"+";
+                }
+                filename<<".csv";
+
+                ofstream tardGrowth;
+                tardGrowth.open(filename.str().c_str());
+                tardGrowth<<"#time, tardiness, actual_exe, est_exe, delta_exe, accum_err"<<endl;
+                for(i = 0; i < (int)sz; ++i)
+                {
+                        tardGrowth<<(completions(i)-starttime)/SCALE<<", "
+                                          <<tardy(i)/SCALE<<", "
+                                          <<actual_exes(i)/SCALE<<", "
+                                          <<est_exes(i)/SCALE<<", "
+                                          <<delta_exe(i)/SCALE<<", "
+                                          <<accum_errs(i)/SCALE<<endl;
+                }
+                tardGrowth.close();
+
+                // task stats
+                outs<<tsk->first.period/SCALE<<", "  // id
+                        <<tsk->first.wcet/SCALE<<", "   // id
+                        <<blitz::mean(actual_exes)/SCALE<<", "  // avg actual exe
+                        <<stddev(actual_exes)/SCALE<<", "
+                        <<blitz::min(delta_exe)/SCALE<<", " // estimation accuracy
+                        <<blitz::max(delta_exe)/SCALE<<", "
+                        <<blitz::mean(delta_exe)/SCALE<<", "
+                        <<stddev(delta_exe)/SCALE<<", "
+                        <<blitz::min(rt)/SCALE<<", "            // response time
+                        <<blitz::max(rt)/SCALE<<", "
+                        <<blitz::mean(rt)/SCALE<<", "
+                        <<stddev(rt)/SCALE<<", "
+                        <<blitz::min(tardy)/SCALE<<", " // tardiness
+                        <<blitz::max(tardy)/SCALE<<", "
+                        <<blitz::mean(tardy)/SCALE<<", "
+                        <<stddev(tardy)/SCALE<<endl;
+        }
+        outs.close();
+
+        return 0;
+}
+
+
+
+
+
+
+
+
+
+
diff --git a/src/st2pl.c b/src/st2pl.c
index 6e86c62..90a67ed 100644
--- a/src/st2pl.c
+++ b/src/st2pl.c
@@ -48,9 +48,9 @@ static void write_prolog_kb(void)
         for_each_task(t) {
                 e = t->events;
                 while (e) {
-                        find(e, ST_SWITCH_TO);
+                        _find(e, ST_SWITCH_TO);
                         e2 = e;
-                        find(e, ST_SWITCH_AWAY);
+                        _find(e, ST_SWITCH_AWAY);
                         printf("scheduled(job(%u, %u), %f, %f).\n",
                                e2->rec->hdr.pid,
                                e2->rec->hdr.job,
@@ -62,9 +62,9 @@ static void write_prolog_kb(void)
         for_each_task(t) {
                 e = t->events;
                 while (e) {
-                        find(e, ST_BLOCK);
+                        _find(e, ST_BLOCK);
                         e2 = e;
-                        find(e, ST_RESUME);
+                        _find(e, ST_RESUME);
                         printf("suspended(job(%u, %u), %f, %f).\n",
                                e2->rec->hdr.pid,
                                e2->rec->hdr.job,
@@ -108,9 +108,9 @@ static void write_asy(double from, double to)
         for_each_task(t) {
                 e = t->events;
                 while (e) {
-                        find(e, ST_SWITCH_TO);
+                        _find(e, ST_SWITCH_TO);
                         e2 = e;
-                        find(e, ST_SWITCH_AWAY);
+                        _find(e, ST_SWITCH_AWAY);
                         t1 = ns2ms_adj(e2->rec->data.switch_to.when);
                         t2 = ns2ms_adj(e->rec->data.switch_away.when);
                         if (intersect(&t1, &t2, from, to))