# HG changeset patch
# User George Dunlap <gdunlap@xensource.com>
# Date 1255979687 -3600
# Node ID 18f3d6e25ffc9a02ef947544e7043adcbc5133e8
# Parent  f7c1a67cf976d3b5a1b3060a85bf07c06ec9b84a
Add credit01 scheduler

diff -r f7c1a67cf976 -r 18f3d6e25ffc Makefile
--- a/Makefile	Mon Oct 19 20:12:54 2009 +0100
+++ b/Makefile	Mon Oct 19 20:14:47 2009 +0100
@@ -21,5 +21,5 @@ clean:
 %.o: %.c $(HDRS) Makefile
 	$(CC) $(CFLAGS) -c -o $@ $<
 
-simulator: simulator.o workloads.o sched_rr.o stats.o options.o
+simulator: simulator.o workloads.o sched_rr.o stats.o options.o sched_credit01.o
 	$(CC) $(CFLAGS) -o $@ $^
\ No newline at end of file
diff -r f7c1a67cf976 -r 18f3d6e25ffc sched_credit01.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/sched_credit01.c	Mon Oct 19 20:14:47 2009 +0100
@@ -0,0 +1,249 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <assert.h>
+
+#define ASSERT assert
+
+#include "list.h"
+#include "sim.h"
+
+
+#define MAX_VMS 16
+#define CREDIT_INIT  500
+#define CREDIT_RESET 0
+#define MAX_TIMER 200
+#define MIN_TIMER 100
+
+struct sched_vm {
+    struct list_head runq_elem;
+    struct vm *v;
+
+    int weight;
+
+    int credit;
+    int credit_per_min_timer; /* ? */
+    int start_time;
+    int vid;
+};
+
+struct {
+    struct list_head runq; /* Global run queue */
+    int max_vm;
+    struct sched_vm vms[MAX_VMS];
+    int ncpus;
+
+    int global_weight;
+    int scale_factor; /* ? */
+
+    int next_check;
+} sched_priv;
+
+
+
+void reset_credit(int time)
+{
+    int i;
+    for ( i=0; i<=sched_priv.max_vm; i++)
+    {
+        sched_priv.vms[i].credit = CREDIT_INIT;
+        sched_priv.vms[i].start_time = time;
+    }
+    /* No need to resort runq, as everyone's credit is now zero */
+}
+
+void dump_credit(int time, struct sched_vm *svm)
+{
+    printf("credit v%d %d %d\n", svm->vid, time, svm->credit);
+}
+
+void burn_credit(struct sched_vm *svm, int time)
+{
+    ASSERT(time >= svm->start_time);
+
+    svm->credit -= (time - svm->start_time);
+    svm->start_time = time;
+
+    dump_credit(time, svm);
+}
+
+int calc_timer(struct sched_vm *svm)
+{
+    int time = MAX_TIMER;
+
+    if ( time > svm->credit )
+        time = svm->credit;
+#if 0
+    if ( !list_empty(&sched_priv.runq) )
+    {
+        struct sched_vm *sq = list_entry(sched_priv.runq.next, struct sched_vm, runq_elem);
+
+        ASSERT(svm->credit >= sq->credit);
+
+        if ( (svm->credit - sq->credit) < time )
+            time = (svm->credit - sq->credit);
+    }
+
+#endif
+
+    if ( time < MIN_TIMER )
+        time = MIN_TIMER;
+    return time;
+}
+
+void runq_insert(struct sched_vm *svm)
+{
+    struct list_head *iter;
+    int pos = 0;
+
+    list_for_each( iter, &sched_priv.runq )
+    {
+        struct sched_vm * iter_svm;
+
+        iter_svm = list_entry(iter, struct sched_vm, runq_elem);
+
+        if ( svm->credit > iter_svm->credit )
+        {
+            printf(" p%d v%d\n",
+                   pos,
+                   iter_svm->vid);
+            break;
+        }
+        pos++;
+    }
+
+    list_add_tail(&svm->runq_elem, iter);
+}
+
+static void sched_credit_init(void)
+{
+    printf("%s()\n", __func__);
+    INIT_LIST_HEAD(&sched_priv.runq);
+    sched_priv.max_vm=0;
+}
+
+static void sched_credit_vm_init(int vid)
+{
+    struct sched_vm *svm;
+
+    printf("%s: vm %d\n", __func__, vid);
+
+    if ( vid > MAX_VMS )
+    {
+        fprintf(stderr, "vid %d > MAX_VMS %d!\n", vid, MAX_VMS);
+        exit(1);
+    }
+
+    svm = sched_priv.vms + vid;
+
+    INIT_LIST_HEAD(&svm->runq_elem);
+
+    svm->vid = vid;
+    svm->v = vm_from_vid(vid);
+
+    svm->credit = CREDIT_INIT;
+    svm->weight = 1;
+    svm->start_time = 0;
+    
+    if ( vid > sched_priv.max_vm )
+        sched_priv.max_vm = vid;
+}
+
+static void sched_credit_wake(int time, int vid)
+{
+    struct vm *v;
+    struct sched_vm *svm;
+
+    v = vm_from_vid(vid);
+
+    printf("%s: time %d vid %d\n",
+           __func__, time, v->vid);
+
+    svm = sched_priv.vms + v->vid;
+
+    ASSERT(list_empty(&svm->runq_elem));
+
+    runq_insert(svm);
+
+    /* Never preempt on wake; only kick idle processors */
+    if ( P.idle > 0 )
+    {
+        int i;
+
+        for ( i=0; i<P.count; i++ )
+            if ( P.pcpus[i].idle )
+                break;
+
+        printf(" %s: waking p%d\n", __func__, i);
+        sim_sched_timer(0, i);
+    }
+}
+
+static struct vm* sched_credit_schedule(int time, int pid)
+{
+    struct sched_vm *svm;
+    struct vm *next, *prev;
+    int timer;
+
+    printf("%s: time %d pid %d\n",
+           __func__, time, pid);
+    prev = current(pid);
+
+    if ( prev )
+    {
+        printf(" current v%d\n", prev->vid);
+        svm = sched_priv.vms + prev->vid;
+
+        burn_credit(svm, time);
+
+        if ( svm->v->runstate == RUNSTATE_RUNNING )
+        {
+            printf(" adding to runqueue\n");
+            runq_insert(svm);
+        }
+    }
+
+    /* Take guy on front of runqueue, set new timer */
+    if ( list_empty(&sched_priv.runq) )
+    {
+        printf(" No runnable entities\n");
+        return NULL;
+    }
+
+    svm = list_entry(sched_priv.runq.next, struct sched_vm, runq_elem);
+
+    list_del_init(&svm->runq_elem);
+
+    next = svm->v;
+
+    if ( svm->credit <= CREDIT_RESET )
+    {
+        printf(" vid %d credit %c, resetting credit at time %d\n",
+               svm->vid,
+               svm->credit,
+               time);
+        reset_credit(time);
+    }
+
+    dump_credit(time, svm);
+    svm->start_time = time;
+
+    timer = calc_timer(svm);
+
+    sim_sched_timer(timer, pid);
+
+    printf(" next: v%d\n", next->vid);
+    
+    return next;
+}
+
+struct scheduler sched_credit01 =
+{
+    .name="credit01",
+    .desc="Zero-start, burn based on weight, reset to zero at negative credit",
+    .ops = {
+        .sched_init = sched_credit_init,
+        .vm_init    = sched_credit_vm_init,
+        .wake       = sched_credit_wake,
+        .schedule   = sched_credit_schedule
+    }
+};
diff -r f7c1a67cf976 -r 18f3d6e25ffc simulator.c
--- a/simulator.c	Mon Oct 19 20:12:54 2009 +0100
+++ b/simulator.c	Mon Oct 19 20:14:47 2009 +0100
@@ -57,10 +57,12 @@ struct global_vm_data {
 struct global_vm_data V;
 
 extern struct scheduler sched_rr;
+extern struct scheduler sched_credit01;
 int default_scheduler = 0;
 struct scheduler *schedulers[] =
 {
     &sched_rr,
+    &sched_credit01,
     NULL
 };