Merge branch 'wip-edf-wm' into wip-semi-part

Merging library branches for EDF-fm, EDF-WM, and NPS-F scheduling
algorithms.

This version of the library will compile against litmus2010 with all
plugins merged (wip-semi-part).

Conflicts:
	SConstruct
	include/litmus.h
	src/litmus.c

8 files changed, 484 insertions, 5 deletions

diff --git a/SConstruct b/SConstruct
index 657a92f..4e6b4c6 100644
--- a/SConstruct
+++ b/SConstruct
@@ -208,14 +208,18 @@ rt.Program('base_task', 'bin/base_task.c')
 mtrt.Program('base_mt_task', 'bin/base_mt_task.c')
 rt.Program('rt_launch', ['bin/rt_launch.c', 'bin/common.c'])
 rt.Program('rtspin', ['bin/rtspin.c', 'bin/common.c'])
+rt.Program('release_ts', 'bin/release_ts.c')
+rtm.Program('measure_syscall', 'bin/null_call.c')
+
 rt.Program('rtspin_edffm', ['bin/rtspin_edffm.c', 'bin/common.c'])
 rt.Program('rt_launch_edffm', ['bin/rt_launch_edffm.c', 'bin/common.c'])
+
 rt.Program('rtspin_npsf', ['bin/rtspin_npsf.c', 'bin/common.c'])
 rt.Program('npsf_add_server', ['bin/npsf_add_server.c', 'bin/common.c'])
 rt.Program('rt_launch_npsf', ['bin/rt_launch_npsf.c', 'bin/common.c'])
-rt.Program('release_ts', 'bin/release_ts.c')
-rtm.Program('measure_syscall', 'bin/null_call.c')
 
+rt.Program('rtspin_edfwm', ['bin/rtspin_edfwm.c', 'bin/common.c'])
+rt.Program('rt_launch_edfwm', ['bin/rt_launch_edfwm.c', 'bin/common.c'])
 
 # #####################################################################
 # Test suite.
diff --git a/bin/common.c b/bin/common.c
index 452b882..4fd24e1 100644
--- a/bin/common.c
+++ b/bin/common.c
@@ -1,6 +1,7 @@
 #include <stdio.h>
 #include <stdlib.h>
 #include <errno.h>
+#include <string.h>
 
 #include "common.h"
 
@@ -9,3 +10,121 @@ void bail_out(const char* msg)
         perror(msg);
         exit(-1 * errno);
 }
+
+/* EDF-WM helper functions to parse a custom text file format to "easily"
+ * launch tests with rtspin and rt_launch:
+ *
+ * Format for task:
+ *
+ * <task_id execution_cost period phase cpu slices_number> .
+ *
+ * If the task is split on multiple slices, slices_number is non 0
+ * and we scan a list of slice parameters up to slices_number:
+ *
+ * Format for slices:
+ *
+ * <task_id cpu deadline(from job release) budget offset> .
+ *
+ * The offset is the start time for the slice relative to the job release.
+ *
+ * Example:
+ * 14 2.26245771754 10 0 5 2
+ * 14 5 5.000000 1.497306 0.000000
+ * 14 7 10.000000 0.765152 5.000000
+ */
+
+#define fms_to_ns(x)    (lt_t)(((x) * __NS_PER_MS))
+/*
+ * <task_id, cpu, deadline (from job release), budget, offset> .
+ */
+int parse_edfwm_slice(FILE *ts, int slices_no, int task_id,
+                      struct rt_task *rt)
+{
+        int i, tid;
+        unsigned int cpu;
+        double deadline, budget, offset;
+
+        lt_t total_budget = 0;
+
+        struct edf_wm_params* wm = (struct edf_wm_params*) &rt->semi_part;
+
+        for (i = 0; i < slices_no; i++) {
+
+                if (fscanf(ts, "%d %u %lf %lf %lf\n", &tid, &cpu,
+                                &deadline, &budget, &offset) != EOF) {
+
+                        if (task_id != tid) {
+                                fprintf(stderr, "task_id %d != tid %d\n",
+                                                task_id, tid);
+                                return -1;
+                        }
+
+                        wm->slices[i].deadline = fms_to_ns(deadline);
+                        wm->slices[i].budget = fms_to_ns(budget);
+                        wm->slices[i].offset = fms_to_ns(offset);
+                        wm->slices[i].cpu    = cpu;
+
+                        printf("slice(tid, cpu, d, e, ph) = (%d, %u, %llu, %llu, %llu)\n",
+                                        tid, cpu, wm->slices[i].deadline,
+                                        wm->slices[i].budget, wm->slices[i].offset);
+
+                        if (wm->slices[i].budget < MIN_EDF_WM_SLICE_SIZE) {
+
+                                fprintf(stderr, "Slice %llu is too small\n",
+                                                wm->slices[i].budget);
+                                return -1;
+                        }
+
+                        total_budget += wm->slices[i].budget;
+                }
+
+                if (ferror(ts)) {
+                        fprintf(stderr, "Cannot read file\n");
+                        return -1;
+                }
+        }
+        wm->count = slices_no;
+        rt->exec_cost = total_budget;
+        printf("--- total %u slices ---\n", wm->count);
+        return 0;
+}
+
+/*
+ * <task_id, execution_cost, period, phase, cpu, slices_number> .
+ */
+int parse_edfwm_ts_file(FILE *ts, struct rt_task *rt)
+{
+        int task_id, ret = 1;
+        unsigned int cpu, sliceno;
+        double fwcet, fperiod, fphase;
+
+        ret = fscanf(ts, "%d %lf %lf %lf %d %d\n",
+                        &task_id, &fwcet, &fperiod, &fphase, &cpu, &sliceno);
+
+        if (ferror(ts))
+                goto err;
+
+        rt->exec_cost = fms_to_ns(fwcet);
+        rt->period = fms_to_ns(fperiod);
+        rt->phase = fms_to_ns(fphase);
+        rt->cpu = cpu;
+        rt->cls = RT_CLASS_HARD;
+        rt->budget_policy = PRECISE_ENFORCEMENT;
+
+        printf("(tid, wcet, period, ph, cpu, slices) = "
+                        "(%d, %llu, %llu, %llu, %u, %u)\n",
+                        task_id, rt->exec_cost, rt->period, rt->phase, cpu, sliceno);
+        if (sliceno > 0) {
+                memset(&rt->semi_part, 0, sizeof(struct edf_wm_params));
+                ret = parse_edfwm_slice(ts, sliceno, task_id, rt);
+                if (ret < 0)
+                        goto err;
+        }
+
+        return 0;
+
+err:
+        fprintf(stderr, "Error parsing file\n");
+        return -1;
+}
+
diff --git a/bin/rt_launch_edfwm.c b/bin/rt_launch_edfwm.c
new file mode 100644
index 0000000..9e8a322
--- /dev/null
+++ b/bin/rt_launch_edfwm.c
@@ -0,0 +1,98 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+#include <limits.h>
+#include <signal.h>
+
+#include "litmus.h"
+#include "common.h"
+
+typedef struct {
+        int  wait;
+        char * exec_path;
+        char ** argv;
+} startup_info_t;
+
+
+int launch(void *task_info_p) {
+        startup_info_t *info = (startup_info_t*) task_info_p;
+        int ret;
+        if (info->wait) {
+                ret = wait_for_ts_release();
+                if (ret != 0)
+                        perror("wait_for_ts_release()");
+        }
+        ret = execvp(info->exec_path, info->argv);
+        perror("execv failed");
+        return ret;
+}
+
+void usage(char *error) {
+        fprintf(stderr, "%s\nUsage: rt_launch [-w] task_parameters_file "
+                        "program [arg1 arg2 ...]\n"
+                        "\t-w\tSynchronous release\n"
+                        "\tprogram to be launched\n",
+                        error);
+        exit(1);
+}
+
+#define OPTSTR "w"
+
+int main(int argc, char** argv)
+{
+        int ret;
+        int wait = 0;
+        int opt;
+        startup_info_t info;
+
+        struct rt_task rt;
+        FILE *file;
+
+        while ((opt = getopt(argc, argv, OPTSTR)) != -1) {
+                switch (opt) {
+                case 'w':
+                        wait = 1;
+                        break;
+                case ':':
+                        usage("Argument missing.");
+                        break;
+                case '?':
+                default:
+                        usage("Bad argument.");
+                        break;
+                }
+        }
+
+        signal(SIGUSR1, SIG_IGN);
+
+        if (argc - optind < 2)
+                usage("Arguments missing.");
+
+        if ((file = fopen(argv[optind + 0], "r")) == NULL) {
+                fprintf(stderr, "Cannot open %s\n", argv[1]);
+                return -1;
+        }
+
+        memset(&rt, 0, sizeof(struct rt_task));
+
+        if (parse_edfwm_ts_file(file, &rt) < 0)
+                bail_out("Could not parse file\n");
+
+        if (sporadic_task_ns_semi(&rt) < 0)
+                bail_out("could not setup rt task params");
+
+        fclose(file);
+
+        info.exec_path = argv[optind + 1];
+        info.argv      = argv + optind + 1;
+        info.wait      = wait;
+
+        ret = create_rt_task_semi(launch, &info, &rt);
+
+        if (ret < 0)
+                bail_out("could not create rt child process");
+
+        return 0;
+}
+
diff --git a/bin/rtspin_edfwm.c b/bin/rtspin_edfwm.c
new file mode 100644
index 0000000..21a5f3b
--- /dev/null
+++ b/bin/rtspin_edfwm.c
@@ -0,0 +1,233 @@
+#include <sys/time.h>
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+#include <time.h>
+#include <string.h>
+
+#include "litmus.h"
+#include "common.h"
+
+
+static double cputime()
+{
+        struct timespec ts;
+        int err;
+        err = clock_gettime(CLOCK_THREAD_CPUTIME_ID, &ts);
+        if (err != 0)
+                perror("clock_gettime");
+        return (ts.tv_sec + 1E-9 * ts.tv_nsec);
+}
+
+static double wctime()
+{
+        struct timeval tv;
+        gettimeofday(&tv, NULL);
+        return (tv.tv_sec + 1E-6 * tv.tv_usec);
+}
+
+void usage(char *error) {
+        fprintf(stderr, "Error: %s\n", error);
+        fprintf(stderr,
+                "Usage: rt_spin [-w] task_parameters_file duration\n"
+                "       rt_spin -l\n");
+        exit(1);
+}
+
+#define NUMS 4096
+static int num[NUMS];
+static double loop_length = 1.0;
+static char* progname;
+
+static int loop_once(void)
+{
+        int i, j = 0;
+        for (i = 0; i < NUMS; i++)
+                j += num[i]++;
+        return j;
+}
+
+static int loop_for(double exec_time)
+{
+        double t = 0;
+        int tmp = 0;
+/*      while (t + loop_length < exec_time) {
+                tmp += loop_once();
+                t += loop_length;
+        }
+*/
+        double start = cputime();
+        double now = cputime();
+        while (now + loop_length < start + exec_time) {
+                tmp += loop_once();
+                t += loop_length;
+                now = cputime();
+        }
+
+        return tmp;
+}
+
+static void fine_tune(double interval)
+{
+        double start, end, delta;
+
+        start = wctime();
+        loop_for(interval);
+        end = wctime();
+        delta = (end - start - interval) / interval;
+        if (delta != 0)
+                loop_length = loop_length / (1 - delta);
+}
+
+static void configure_loop(void)
+{
+        double start;
+
+        /* prime cache */
+        loop_once();
+        loop_once();
+        loop_once();
+
+        /* measure */
+        start = wctime();
+        loop_once(); /* hope we didn't get preempted  */
+        loop_length = wctime();
+        loop_length -= start;
+
+        /* fine tune */
+        fine_tune(0.1);
+        fine_tune(0.1);
+        fine_tune(0.1);
+}
+
+static void show_loop_length(void)
+{
+        printf("%s/%d: loop_length=%f (%ldus)\n",
+               progname, getpid(), loop_length,
+               (long) (loop_length * 1000000));
+}
+
+static void debug_delay_loop(void)
+{
+        double start, end, delay;
+        show_loop_length();
+        while (1) {
+                for (delay = 0.5; delay > 0.01; delay -= 0.01) {
+                        start = wctime();
+                        loop_for(delay);
+                        end = wctime();
+                        printf("%6.4fs: looped for %10.8fs, delta=%11.8fs, error=%7.4f%%\n",
+                               delay,
+                               end - start,
+                               end - start - delay,
+                               100 * (end - start - delay) / delay);
+                }
+        }
+}
+
+static int job(double exec_time)
+{
+        loop_for(exec_time);
+        sleep_next_period();
+        return 0;
+}
+
+#define OPTSTR "wld:v"
+
+int main(int argc, char** argv)
+{
+        int ret;
+
+        int opt;
+        int wait = 0;
+        int test_loop = 0;
+        int skip_config = 0;
+        int verbose = 0;
+        double wcet_ms;
+        double duration, start;
+
+        struct rt_task rt;
+        FILE *file;
+
+        progname = argv[0];
+
+        while ((opt = getopt(argc, argv, OPTSTR)) != -1) {
+                switch (opt) {
+                case 'w':
+                        wait = 1;
+                        break;
+                case 'l':
+                        test_loop = 1;
+                        break;
+                case 'd':
+                        /* manually configure delay per loop iteration
+                         * unit: microseconds */
+                        loop_length = atof(optarg) / 1000000;
+                        skip_config = 1;
+                        break;
+                case 'v':
+                        verbose = 1;
+                        break;
+                case ':':
+                        usage("Argument missing.");
+                        break;
+                case '?':
+                default:
+                        usage("Bad argument.");
+                        break;
+                }
+        }
+
+
+        if (!skip_config)
+                configure_loop();
+
+        if (test_loop) {
+                debug_delay_loop();
+                return 0;
+        }
+
+        if (argc - optind < 2)
+                usage("Arguments missing.");
+
+        if ((file = fopen(argv[optind + 0], "r")) == NULL) {
+                fprintf(stderr, "Cannot open %s\n", argv[1]);
+                return -1;
+        }
+        duration = atof(argv[optind + 1]);
+
+        memset(&rt, 0, sizeof(struct rt_task));
+
+        if (parse_edfwm_ts_file(file, &rt) < 0)
+                bail_out("Could not parse file\n");
+
+        if (sporadic_task_ns_semi(&rt) < 0)
+                bail_out("could not setup rt task params");
+
+        fclose(file);
+
+        if (verbose)
+                show_loop_length();
+
+        init_litmus();
+
+        ret = task_mode(LITMUS_RT_TASK);
+        if (ret != 0)
+                bail_out("could not become RT task");
+
+        if (wait) {
+                ret = wait_for_ts_release();
+                if (ret != 0)
+                        bail_out("wait_for_ts_release()");
+        }
+
+        wcet_ms = ((double) rt.exec_cost ) / __NS_PER_MS;
+        start = wctime();
+
+        while (start + duration > wctime()) {
+                job(wcet_ms * 0.0009); /* 90% wcet, in seconds */
+        }
+
+        return 0;
+}
diff --git a/include/common.h b/include/common.h
index d1234ba..dbcfd34 100644
--- a/include/common.h
+++ b/include/common.h
@@ -1,7 +1,11 @@
 #ifndef COMMON_H
 #define COMMON_H
 
+#include "litmus.h"
 
 void bail_out(const char* msg);
 
+/* EDF-WM helper functions to parse task parameters from file */
+int parse_edfwm_ts_file(FILE *ts, struct rt_task *rt);
+
 #endif
diff --git a/include/litmus.h b/include/litmus.h
index 7382936..6c3483c 100644
--- a/include/litmus.h
+++ b/include/litmus.h
@@ -9,6 +9,7 @@ extern "C" {
  * This is required for the rt_param
  * and control_page structures.
  */
+#include <linux/threads.h>
 #include <litmus/rt_param.h>
 
 #include <sys/types.h>
@@ -40,6 +41,7 @@ int sporadic_task_ns(
                 int cpu, task_class_t cls,
                 budget_policy_t budget_policy, int set_cpu_set);
 
+/* Semi-partitioned schedulers --- sporadic task helpers (ns) */
 int sporadic_task_ns_edffm(lt_t e, lt_t p, lt_t phase, int cpu,
                 lt_t *frac1, lt_t *frac2, int cpu1, int cpu2,
                 task_class_t cls, budget_policy_t budget_policy,
@@ -50,6 +52,8 @@ int sporadic_task_ns_npsf(
                 int cpu, task_class_t cls, int npsf_id,
                 budget_policy_t budget_policy, int set_cpu_set);
 
+int sporadic_task_ns_semi(struct rt_task *rt);
+
 /* budget enforcement off by default in these macros */
 #define sporadic_global(e, p) \
         sporadic_task(e, p, 0, 0, RT_CLASS_SOFT, NO_ENFORCEMENT, 0)
@@ -95,11 +99,14 @@ typedef int (*rt_fn_t)(void*);
 int create_rt_task(rt_fn_t rt_prog, void *arg, int cpu, int wcet, int period);
 int __create_rt_task(rt_fn_t rt_prog, void *arg, int cpu, int wcet,
                      int period, task_class_t cls);
+
+/* Semi-partitioned schedulers helper to wrap __launch_rt_task() */
 int __create_rt_task_edffm(rt_fn_t rt_prog, void *arg, int cpu, int wcet,
                 int period, lt_t *frac1, lt_t *frac2,
                 int cpu1, int cpu2, task_class_t class);
 int __create_rt_task_npsf(rt_fn_t rt_prog, void *arg, int cpu, int wcet,
                 int period, int npsf_id, task_class_t class);
+int create_rt_task_semi(rt_fn_t rt_prog, void *arg, struct rt_task *params);
 
 /*      per-task modes */
 enum rt_task_mode_t {
diff --git a/src/litmus.c b/src/litmus.c
index b339e62..33e1a6d 100644
--- a/src/litmus.c
+++ b/src/litmus.c
@@ -29,8 +29,6 @@ task_class_t str2class(const char* str)
                 return -1;
 }
 
-#define NS_PER_MS 1000000
-
 /* only for best-effort execution: migrate to target_cpu */
 int be_migrate_to(int target_cpu)
 {
@@ -45,7 +43,7 @@ int sporadic_task(lt_t e, lt_t p, lt_t phase,
                   int cpu, task_class_t cls,
                   budget_policy_t budget_policy, int set_cpu_set)
 {
-        return sporadic_task_ns(e * NS_PER_MS, p * NS_PER_MS, phase * NS_PER_MS,
+        return sporadic_task_ns(e * __NS_PER_MS, p * __NS_PER_MS, phase * __NS_PER_MS,
                                 cpu, cls, budget_policy, set_cpu_set);
 }
 
@@ -69,6 +67,7 @@ int sporadic_task_ns(lt_t e, lt_t p, lt_t phase,
         return set_rt_task_param(gettid(), &param);
 }
 
+/* Sporadic task helper function for Semi-Partitioned algorithms. */
 int sporadic_task_ns_edffm(lt_t e, lt_t p, lt_t phase, int cpu,
                 lt_t *frac1, lt_t *frac2, int cpu1, int cpu2,
                 task_class_t cls, budget_policy_t budget_policy,
@@ -124,6 +123,16 @@ int sporadic_task_ns_npsf(lt_t e, lt_t p, lt_t phase,
         return set_rt_task_param(gettid(), &param);
 }
 
+int sporadic_task_ns_semi(struct rt_task *param)
+{
+        int ret;
+
+        ret = be_migrate_to(param->cpu);
+        check("migrate to cpu");
+
+        return set_rt_task_param(gettid(), param);
+}
+
 int init_kernel_iface(void);
 
 int init_litmus(void)
diff --git a/src/task.c b/src/task.c
index 2db9c98..daf95ca 100644
--- a/src/task.c
+++ b/src/task.c
@@ -108,6 +108,11 @@ int create_rt_task(rt_fn_t rt_prog, void *arg, int cpu, int wcet, int period) {
         return __create_rt_task(rt_prog, arg, cpu, wcet, period, RT_CLASS_HARD);
 }
 
+int create_rt_task_semi(rt_fn_t rt_prog, void *arg, struct rt_task *params)
+{
+        return __launch_rt_task(rt_prog, arg,
+                        (rt_setup_fn_t) set_rt_task_param, params);
+}
 
 #define SCHED_NORMAL 0
 #define SCHED_LITMUS 6