1.1 --- a/.rootkeys	Wed Apr 20 21:22:46 2005 +0000
     1.2 +++ b/.rootkeys	Thu Apr 21 01:42:29 2005 +0000
     1.3 @@ -21,6 +21,7 @@ 4022a73cgxX1ryj1HgS-IwwB6NUi2A docs/misc
     1.4  412f4bd9sm5mCQ8BkrgKcAKZGadq7Q docs/misc/blkif-drivers-explained.txt
     1.5  420b949cy9ZGzED74Fz_DaWlK7tT4g docs/misc/crashdb.txt
     1.6  4251a1f82AexscYEiF4Iku8Gc_kWfQ docs/misc/grant-tables.txt
     1.7 +424d462b5GuApQ_NyMsRFt9LbrsWow docs/misc/sedf_scheduler_mini-HOWTO.txt
     1.8  40d6ccbfKKBq8jE0ula4eHEzBiQuDA docs/misc/xen_config.html
     1.9  410a4c2bAO_m_l4RsiiPHnZ4ixHWbQ docs/misc/xend.tex
    1.10  3f9e7d564bWFB-Czjv1qdmE6o0GqNg docs/src/interface.tex
    1.11 @@ -732,6 +733,7 @@ 41cc934aO1m6NxEh_8eDr9bJIMoLFA tools/lib
    1.12  3fbba6dctWRWlFJkYb6hdix2X4WMuw tools/libxc/xc_private.c
    1.13  3fbba6dcbVrG2hPzEzwdeV_UC8kydQ tools/libxc/xc_private.h
    1.14  42337174PxyzzPk62raDiYCIsfStDg tools/libxc/xc_ptrace.c
    1.15 +41ebbfe9U0b0kI-HgjK7VEY4EvW7_w tools/libxc/xc_sedf.c
    1.16  41dde8b0pLfAKMs_L9Uri2hnzHiCRQ tools/libxc/xc_vmx_build.c
    1.17  40e1b09dMYB4ItGCqcMIzirdMd9I-w tools/libxutil/Makefile
    1.18  40e033325Sjqs-_4TuzeUEprP_gYFg tools/libxutil/allocate.c
    1.19 @@ -1266,6 +1268,7 @@ 3e54c38dkHAev597bPr71-hGzTdocg xen/commo
    1.20  4051bcecFeq4DE70p4zGO5setf47CA xen/common/physdev.c
    1.21  3ddb79bdHqdQpATqC0rmUZNbsb6L6A xen/common/resource.c
    1.22  40589968dD2D1aejwSOvrROg7fOvGQ xen/common/sched_bvt.c
    1.23 +41ebbfe9oF1BF3cH5v7yE3eOL9uPbA xen/common/sched_sedf.c
    1.24  3e397e6619PgAfBbw2XFbXkewvUWgw xen/common/schedule.c
    1.25  3ddb79bd0gVQYmL2zvuJnldvD0AGxQ xen/common/softirq.c
    1.26  3e7f358awXBC3Vw-wFRwPw18qL1khg xen/common/string.c
    1.27 @@ -1434,6 +1437,7 @@ 4266bd01Ul-pC01ZVvBkhBnv5eqzvw xen/inclu
    1.28  3ddb79c25UE59iu4JJcbRalx95mvcg xen/include/public/xen.h
    1.29  3e397e66m2tO3s-J8Jnr7Ws_tGoPTg xen/include/xen/ac_timer.h
    1.30  40715b2epYl2jBbxzz9CI2rgIca7Zg xen/include/xen/acpi.h
    1.31 +422f0995xCgnbsVhTjSncnqIABs64g xen/include/xen/adv_sched_hist.h
    1.32  3ddb79c0c0cX_DZE209-Bb-Rx1v-Aw xen/include/xen/cache.h
    1.33  41f2cea7Yna7xc0X9fyavIjoSFFeVg xen/include/xen/compile.h.in
    1.34  3f840f12CkbYSlwMrY2S11Mpyxg7Nw xen/include/xen/compiler.h

     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/docs/misc/sedf_scheduler_mini-HOWTO.txt	Thu Apr 21 01:42:29 2005 +0000
     2.3 @@ -0,0 +1,44 @@
     2.4 +sEDF scheduler
     2.5 +--------------
     2.6 +Author:
     2.7 +   Stephan.Diestelhorst@{cl.cam.ac.uk, inf.tu-dresden.de}
     2.8 +   
     2.9 +Overview:
    2.10 +  This scheduler provides weighted CPU sharing in an intuitive way and
    2.11 +  uses realtime-algorithms to ensure time guarantees.
    2.12 +
    2.13 +Usage:
    2.14 +   -add "sched=sedf" on Xen's boot command-line
    2.15 +   -create domains as usual
    2.16 +   -use "xm sedf <dom-id> <period> <slice> <latency-hint> <extra> <weight>"
    2.17 +    Where:
    2.18 +      -period/slice are the normal EDF scheduling parameters in nanosecs
    2.19 +      -latency-hint is the scaled period in case the domain is doing heavy I/O
    2.20 +         (unused by the currently compiled version)
    2.21 +      -extra is a flag (0/1), which controls whether the domain can run in
    2.22 +       extra-time
    2.23 +      -weight is mutually exclusive with period/slice and specifies another
    2.24 +       way of setting a domains cpu slice
    2.25 +
    2.26 +Examples:
    2.27 + normal EDF (20ms/5ms):
    2.28 +  xm sedf <dom-id> 20000000 5000000 0 0 0
    2.29 +  
    2.30 + best-effort domains (i.e. non-realtime):
    2.31 +  xm sedf <dom-id> 20000000 0 0 1 0
    2.32 + 
    2.33 + normal EDF (20ms/5ms) + share of extra-time:
    2.34 +  xm sedf <dom-id> 20000000 5000000 0 1 0
    2.35 +  
    2.36 + 4 domains with weights 2:3:4:2
    2.37 +  xm sedf <d1> 0 0 0 0 2
    2.38 +  xm sedf <d2> 0 0 0 0 3
    2.39 +  xm sedf <d3> 0 0 0 0 4
    2.40 +  xm sedf <d4> 0 0 0 0 2
    2.41 +  
    2.42 + 1 fully-specified (10ms/3ms) domain, 3 other domains share
    2.43 + available rest in 2:7:3 ratio:
    2.44 +  xm sedf <d1> 10000000 3000000 0 0 0
    2.45 +  xm sedf <d2> 0 0 0 0 2
    2.46 +  xm sedf <d3> 0 0 0 0 7
    2.47 +  xm sedf <d4> 0 0 0 0 3
    2.48 \ No newline at end of file

     3.1 --- a/tools/libxc/Makefile	Wed Apr 20 21:22:46 2005 +0000
     3.2 +++ b/tools/libxc/Makefile	Thu Apr 21 01:42:29 2005 +0000
     3.3 @@ -16,6 +16,7 @@ vpath %c       $(XEN_LIBXUTIL)
     3.4  INCLUDES += -I $(XEN_LIBXUTIL)
     3.5  
     3.6  SRCS     :=
     3.7 +SRCS     += xc_sedf.c
     3.8  SRCS     += xc_bvtsched.c
     3.9  SRCS     += xc_domain.c
    3.10  SRCS     += xc_evtchn.c

     4.1 --- a/tools/libxc/xc.h	Wed Apr 20 21:22:46 2005 +0000
     4.2 +++ b/tools/libxc/xc.h	Thu Apr 21 01:42:29 2005 +0000
     4.3 @@ -257,6 +257,14 @@ int xc_bvtsched_domain_get(int xc_handle
     4.4                             long long *warpl,
     4.5                             long long *warpu);
     4.6  
     4.7 +int xc_sedf_domain_set(int xc_handle,
     4.8 +                          u32 domid,
     4.9 +                          u64 period, u64 slice, u64 latency, u16 extratime, u16 weight);
    4.10 +
    4.11 +int xc_sedf_domain_get(int xc_handle,
    4.12 +                          u32 domid,
    4.13 +                          u64* period, u64 *slice, u64 *latency, u16 *extratime, u16* weight);
    4.14 +
    4.15  typedef evtchn_status_t xc_evtchn_status_t;
    4.16  
    4.17  /*

     5.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     5.2 +++ b/tools/libxc/xc_sedf.c	Thu Apr 21 01:42:29 2005 +0000
     5.3 @@ -0,0 +1,51 @@
     5.4 +/******************************************************************************
     5.5 + * xc_sedf.c
     5.6 + * 
     5.7 + * API for manipulating parameters of the Simple EDF scheduler.
     5.8 + * 
     5.9 + * changes by Stephan Diestelhorst
    5.10 + * based on code
    5.11 + * by Mark Williamson, Copyright (c) 2004 Intel Research Cambridge.
    5.12 + */
    5.13 +
    5.14 +#include "xc_private.h"
    5.15 +
    5.16 +int xc_sedf_domain_set(int xc_handle,
    5.17 +                          u32 domid, u64 period, u64 slice,u64 latency, u16 extratime,u16 weight)
    5.18 +{
    5.19 +    dom0_op_t op;
    5.20 +    struct sedf_adjdom *p = &op.u.adjustdom.u.sedf;
    5.21 +
    5.22 +    op.cmd = DOM0_ADJUSTDOM;
    5.23 +    op.u.adjustdom.domain  = (domid_t)domid;
    5.24 +    op.u.adjustdom.sched_id = SCHED_SEDF;
    5.25 +    op.u.adjustdom.direction = SCHED_INFO_PUT;
    5.26 +
    5.27 +    p->period    = period;
    5.28 +    p->slice     = slice;
    5.29 +    p->latency   = latency;
    5.30 +    p->extratime = extratime;
    5.31 +    p->weight    = weight;
    5.32 +    return do_dom0_op(xc_handle, &op);
    5.33 +}
    5.34 +
    5.35 +int xc_sedf_domain_get(int xc_handle, u32 domid, u64 *period, u64 *slice, u64* latency, u16* extratime, u16* weight)
    5.36 +{
    5.37 +    dom0_op_t op;
    5.38 +    int ret;
    5.39 +    struct sedf_adjdom *p = &op.u.adjustdom.u.sedf;
    5.40 +
    5.41 +    op.cmd = DOM0_ADJUSTDOM;    
    5.42 +    op.u.adjustdom.domain = (domid_t)domid;
    5.43 +    op.u.adjustdom.sched_id = SCHED_SEDF;
    5.44 +    op.u.adjustdom.direction = SCHED_INFO_GET;
    5.45 +
    5.46 +    ret = do_dom0_op(xc_handle, &op);
    5.47 +
    5.48 +    *period    = p->period;
    5.49 +    *slice     = p->slice;
    5.50 +    *latency   = p->latency;
    5.51 +    *extratime = p->extratime;
    5.52 +    *weight    = p->weight;
    5.53 +    return ret;
    5.54 +}

     6.1 --- a/tools/python/xen/lowlevel/xc/xc.c	Wed Apr 20 21:22:46 2005 +0000
     6.2 +++ b/tools/python/xen/lowlevel/xc/xc.c	Thu Apr 21 01:42:29 2005 +0000
     6.3 @@ -800,6 +800,52 @@ static PyObject *pyxc_physinfo(PyObject 
     6.4                           "cpu_khz",     info.cpu_khz);
     6.5  }
     6.6  
     6.7 +static PyObject *pyxc_sedf_domain_set(PyObject *self,
     6.8 +                                         PyObject *args,
     6.9 +                                         PyObject *kwds)
    6.10 +{
    6.11 +    XcObject *xc = (XcObject *)self;
    6.12 +    u32 domid;
    6.13 +    u64 period, slice, latency;
    6.14 +    u16 extratime, weight;
    6.15 +    static char *kwd_list[] = { "dom", "period", "slice", "latency", "extratime", "weight",NULL };
    6.16 +    
    6.17 +    if( !PyArg_ParseTupleAndKeywords(args, kwds, "iLLLhh", kwd_list, &domid,
    6.18 +                                     &period, &slice, &latency, &extratime, &weight) )
    6.19 +        return NULL;
    6.20 +   if ( xc_sedf_domain_set(xc->xc_handle, domid, period, slice, latency, extratime,weight) != 0 )
    6.21 +        return PyErr_SetFromErrno(xc_error);
    6.22 +
    6.23 +    Py_INCREF(zero);
    6.24 +    return zero;
    6.25 +}
    6.26 +
    6.27 +static PyObject *pyxc_sedf_domain_get(PyObject *self,
    6.28 +                                         PyObject *args,
    6.29 +                                         PyObject *kwds)
    6.30 +{
    6.31 +    XcObject *xc = (XcObject *)self;
    6.32 +    u32 domid;
    6.33 +    u64 period, slice,latency;
    6.34 +    u16 weight, extratime;
    6.35 +    
    6.36 +    static char *kwd_list[] = { "dom", NULL };
    6.37 +
    6.38 +    if( !PyArg_ParseTupleAndKeywords(args, kwds, "i", kwd_list, &domid) )
    6.39 +        return NULL;
    6.40 +    
    6.41 +    if ( xc_sedf_domain_get( xc->xc_handle, domid, &period,
    6.42 +                                &slice,&latency,&extratime,&weight) )
    6.43 +        return PyErr_SetFromErrno(xc_error);
    6.44 +
    6.45 +    return Py_BuildValue("{s:i,s:L,s:L,s:L,s:i}",
    6.46 +                         "domain",    domid,
    6.47 +                         "period",    period,
    6.48 +                         "slice",     slice,
    6.49 +			 "latency",   latency,
    6.50 +			 "extratime", extratime);
    6.51 +}
    6.52 +
    6.53  static PyObject *pyxc_shadow_control(PyObject *self,
    6.54                                       PyObject *args,
    6.55                                       PyObject *kwds)
    6.56 @@ -992,6 +1038,30 @@ static PyMethodDef pyxc_methods[] = {
    6.57        " warpu  [long]: Unwarp requirement.\n"
    6.58        " warpl  [long]: Warp limit,\n"
    6.59      },
    6.60 +    
    6.61 +    { "sedf_domain_set",
    6.62 +      (PyCFunction)pyxc_sedf_domain_set,
    6.63 +      METH_KEYWORDS, "\n"
    6.64 +      "Set the scheduling parameters for a domain when running with Atropos.\n"
    6.65 +      " dom       [int]:  domain to set\n"
    6.66 +      " period    [long]: domain's scheduling period\n"
    6.67 +      " slice     [long]: domain's slice per period\n"
    6.68 +      " latency   [long]: domain's wakeup latency hint\n"
    6.69 +      " extratime [int]:  domain aware of extratime?\n"
    6.70 +      "Returns: [int] 0 on success; -1 on error.\n" },
    6.71 +
    6.72 +    { "sedf_domain_get",
    6.73 +      (PyCFunction)pyxc_sedf_domain_get,
    6.74 +      METH_KEYWORDS, "\n"
    6.75 +      "Get the current scheduling parameters for a domain when running with\n"
    6.76 +      "the Atropos scheduler."
    6.77 +      " dom       [int]: domain to query\n"
    6.78 +      "Returns:   [dict]\n"
    6.79 +      " domain    [int]: domain ID\n"
    6.80 +      " period    [long]: scheduler period\n"
    6.81 +      " slice     [long]: CPU reservation per period\n"
    6.82 +      " latency   [long]: domain's wakeup latency hint\n"
    6.83 +      " extratime [int]:  domain aware of extratime?\n"},
    6.84  
    6.85      { "evtchn_alloc_unbound", 
    6.86        (PyCFunction)pyxc_evtchn_alloc_unbound,

     7.1 --- a/tools/python/xen/xend/XendClient.py	Wed Apr 20 21:22:46 2005 +0000
     7.2 +++ b/tools/python/xen/xend/XendClient.py	Thu Apr 21 01:42:29 2005 +0000
     7.3 @@ -260,6 +260,15 @@ class Xend:
     7.4                                'warpl'    : warpl,
     7.5                                'warpu'    : warpu })
     7.6  
     7.7 +    def xend_domain_cpu_sedf_set(self, id, period, slice, latency, extratime, weight):
     7.8 +        return self.xendPost(self.domainurl(id),
     7.9 +                             {'op'        : 'cpu_sedf_set',
    7.10 +                              'period'    : period,
    7.11 +                              'slice'     : slice,
    7.12 +			      'latency'   : latency,
    7.13 +			      'extratime' : extratime,
    7.14 +			      'weight'    : weight })
    7.15 +
    7.16      def xend_domain_maxmem_set(self, id, memory):
    7.17          return self.xendPost(self.domainurl(id),
    7.18                               { 'op'     : 'maxmem_set',

     8.1 --- a/tools/python/xen/xend/XendDomain.py	Wed Apr 20 21:22:46 2005 +0000
     8.2 +++ b/tools/python/xen/xend/XendDomain.py	Thu Apr 21 01:42:29 2005 +0000
     8.3 @@ -642,6 +642,24 @@ class XendDomain:
     8.4          except Exception, ex:
     8.5              raise XendError(str(ex))
     8.6      
     8.7 +    
     8.8 +    def domain_cpu_sedf_set(self, id, period, slice, latency, extratime, weight):
     8.9 +        """Set Simple EDF scheduler parameters for a domain.
    8.10 +        """
    8.11 +	dominfo = self.domain_lookup(id)
    8.12 +        try:
    8.13 +            return xc.sedf_domain_set(dominfo.dom, period, slice, latency, extratime, weight)
    8.14 +        except Exception, ex:
    8.15 +            raise XendError(str(ex))
    8.16 +
    8.17 +    def domain_cpu_sedf_get(self, id):
    8.18 +        """Get Atropos scheduler parameters for a domain.
    8.19 +        """
    8.20 +        dominfo = self.domain_lookup(id)
    8.21 +        try:
    8.22 +            return xc.sedf_domain_get(dominfo.dom)
    8.23 +        except Exception, ex:
    8.24 +            raise XendError(str(ex))
    8.25      def domain_device_create(self, id, devconfig):
    8.26          """Create a new device for a domain.
    8.27  

     9.1 --- a/tools/python/xen/xend/server/SrvDomain.py	Wed Apr 20 21:22:46 2005 +0000
     9.2 +++ b/tools/python/xen/xend/server/SrvDomain.py	Thu Apr 21 01:42:29 2005 +0000
     9.3 @@ -107,6 +107,18 @@ class SrvDomain(SrvDir):
     9.4          val = fn(req.args, {'dom': self.dom.id})
     9.5          return val
     9.6      
     9.7 +    
     9.8 +    def op_cpu_sedf_set(self, op, req):
     9.9 +        fn = FormFn(self.xd.domain_cpu_sedf_set,
    9.10 +                    [['dom', 'str'],
    9.11 +                     ['period', 'int'],
    9.12 +                     ['slice', 'int'],
    9.13 +		     ['latency', 'int'],
    9.14 +		     ['extratime', 'int'],
    9.15 +		     ['weight', 'int']])
    9.16 +        val = fn(req.args, {'dom': self.dom.id})
    9.17 +        return val
    9.18 +
    9.19      def op_maxmem_set(self, op, req):
    9.20          fn = FormFn(self.xd.domain_maxmem_set,
    9.21                      [['dom', 'str'],

    10.1 --- a/tools/python/xen/xm/main.py	Wed Apr 20 21:22:46 2005 +0000
    10.2 +++ b/tools/python/xen/xm/main.py	Thu Apr 21 01:42:29 2005 +0000
    10.3 @@ -591,6 +591,23 @@ class ProgBvtslice(Prog):
    10.4  
    10.5  xm.prog(ProgBvtslice)
    10.6  
    10.7 +class ProgSedf(Prog):
    10.8 +    group = 'scheduler'
    10.9 +    name= "sedf"
   10.10 +    info = """Set simple EDF parameters."""
   10.11 +
   10.12 +    def help(self, args):
   10.13 +        print args[0], "DOM PERIOD SLICE LATENCY EXTRATIME WEIGHT"
   10.14 +        print "\nSet simple EDF parameters."
   10.15 +
   10.16 +    def main(self, args):
   10.17 +	if len(args) != 7: self.err("%s: Invalid argument(s)" % args[0])
   10.18 +	dom = args[1]
   10.19 +	v = map(int, args[2:7])
   10.20 +	server.xend_domain_cpu_sedf_set(dom, *v)
   10.21 +
   10.22 +xm.prog(ProgSedf)
   10.23 +
   10.24  class ProgInfo(Prog):
   10.25      group = 'host'
   10.26      name = "info"

    11.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    11.2 +++ b/xen/common/sched_sedf.c	Thu Apr 21 01:42:29 2005 +0000
    11.3 @@ -0,0 +1,1420 @@
    11.4 +/****************************************************************************
    11.5 + * Simple EDF scheduler for xen
    11.6 + *
    11.7 + * by Stephan Diestelhorst (C)  2004 Cambridge University
    11.8 + * based on code by Mark Williamson (C) 2004 Intel Research Cambridge
    11.9 + */
   11.10 +
   11.11 +#include <xen/sched.h>
   11.12 +#include <xen/sched-if.h>
   11.13 +#include <public/sched_ctl.h>
   11.14 +#include <xen/ac_timer.h>
   11.15 +#include <xen/softirq.h>
   11.16 +#include <xen/time.h>
   11.17 +#include <xen/slab.h>
   11.18 +
   11.19 +/*#include <xen/adv_sched_hist.h>*/
   11.20 +
   11.21 +/*verbosity settings*/
   11.22 +#define SEDFLEVEL 0
   11.23 +#define PRINT(_f, _a...)  \
   11.24 +if ((_f)<=SEDFLEVEL) printk(_a );
   11.25 +
   11.26 +#ifdef DEBUG
   11.27 +	#define SEDF_STATS
   11.28 +#endif
   11.29 +
   11.30 +/*various ways of unblocking domains*/
   11.31 +#define UNBLOCK_ISOCHRONOUS_EDF 1
   11.32 +#define UNBLOCK_EDF 2
   11.33 +#define UNBLOCK_ATROPOS 3
   11.34 +#define UNBLOCK_SHORT_RESUME 4
   11.35 +#define UNBLOCK_BURST 5
   11.36 +#define UNBLOCK_EXTRA_SUPPORT 6
   11.37 +#define UNBLOCK UNBLOCK_EXTRA_SUPPORT
   11.38 +
   11.39 +/*various ways of treating extra-time*/
   11.40 +#define EXTRA_OFF 1
   11.41 +#define EXTRA_ROUNDR 2
   11.42 +#define EXTRA_SLICE_WEIGHT 3
   11.43 +#define EXTRA_BLOCK_WEIGHT 4
   11.44 +
   11.45 +#define EXTRA EXTRA_BLOCK_WEIGHT
   11.46 +
   11.47 +#define EXTRA_NONE (0)
   11.48 +#define EXTRA_AWARE (1)
   11.49 +#define EXTRA_RUN_PEN (2)
   11.50 +#define EXTRA_RUN_UTIL (4)
   11.51 +#define EXTRA_WANT_PEN_Q (8)
   11.52 +#define EXTRA_PEN_Q (0)
   11.53 +#define EXTRA_UTIL_Q (1)
   11.54 +
   11.55 +#define extra_runs(inf) ((inf->extra) & 6)
   11.56 +#define extra_get_cur_q(inf) (((inf->extra & 6) >> 1)-1)
   11.57 +
   11.58 +#define EXTRA_QUANTUM (MICROSECS(500)) 
   11.59 +#define WEIGHT_PERIOD (MILLISECS(100))
   11.60 +#define WEIGHT_SAFETY (MILLISECS(5))
   11.61 +
   11.62 +
   11.63 +struct sedf_dom_info
   11.64 +{
   11.65 +	struct domain		*owner;
   11.66 +	struct list_head	list;
   11.67 +	struct list_head	extralist[2];
   11.68 +	
   11.69 +	/*Parameters for EDF*/
   11.70 +	s_time_t		period;		/*=(relative deadline)*/
   11.71 +	s_time_t		slice;		/*=worst case execution time*/
   11.72 +	
   11.73 +	/*Advaced Parameters*/
   11.74 +	/*Latency Scaling*/
   11.75 +	s_time_t		period_orig;	
   11.76 +	s_time_t		slice_orig;
   11.77 +	s_time_t		latency;
   11.78 +	
   11.79 +	/*extra-time status of domain*/
   11.80 +	short			extra;
   11.81 +	/*weights for "Scheduling for beginners/ lazy/ etc." ;)*/
   11.82 +	short			weight;
   11.83 +	
   11.84 +	/*Bookkeeping*/
   11.85 +	s_time_t		absdead;
   11.86 +	s_time_t		sched_start;
   11.87 +	s_time_t		cputime;
   11.88 +	s_time_t		absblock;
   11.89 +	
   11.90 +	/*time the domain unblocked, used to determine unblocking intervals*/
   11.91 +	s_time_t		absunblock;
   11.92 +	
   11.93 +	/*scores for {util, block penalty}-weighted extratime distribution*/
   11.94 +	int			score[2];	
   11.95 +	s_time_t		short_block_lost_tot;
   11.96 +	
   11.97 +	/*Statistics*/
   11.98 +	s_time_t		extra_time_tot;
   11.99 +
  11.100 +#ifdef SEDF_STATS
  11.101 +	s_time_t		block_time_tot;
  11.102 +	s_time_t		penalty_time_tot;
  11.103 +	int			block_tot;
  11.104 +	int			short_block_tot;
  11.105 +	int			long_block_tot;
  11.106 +	int			short_cont;
  11.107 +	int			pen_extra_blocks;
  11.108 +	int			pen_extra_slices;
  11.109 +#endif
  11.110 +};
  11.111 +
  11.112 +struct sedf_cpu_info {
  11.113 +	struct list_head runnableq;
  11.114 +	struct list_head waitq;
  11.115 +	struct list_head extraq[2];
  11.116 +};
  11.117 +
  11.118 +#define DOM_INFO(d)		((struct sedf_dom_info *)((d)->sched_priv))
  11.119 +#define CPU_INFO(cpu)	((struct sedf_cpu_info *)schedule_data[cpu].sched_priv)
  11.120 +#define LIST(d)			(&DOM_INFO(d)->list)
  11.121 +#define EXTRALIST(d,i)		(&(DOM_INFO(d)->extralist[i]))
  11.122 +#define RUNQ(cpu)   		(&CPU_INFO(cpu)->runnableq)
  11.123 +#define WAITQ(cpu)   		(&CPU_INFO(cpu)->waitq)
  11.124 +#define EXTRAQ(cpu,i)  		(&(CPU_INFO(cpu)->extraq[i]))
  11.125 +#define IDLETASK(cpu)		((struct domain *)schedule_data[cpu].idle)
  11.126 +
  11.127 +#define PERIOD_BEGIN(inf)	((inf)->absdead - (inf)->period)
  11.128 +
  11.129 +#define MIN(x,y) (((x)<(y))?(x):(y))
  11.130 +#define DIV_UP(x,y) (((x) + (y) - 1) / y)
  11.131 +
  11.132 +static xmem_cache_t *dom_info_cache;
  11.133 +
  11.134 +static void sedf_dump_cpu_state(int i);
  11.135 +
  11.136 +static inline int extraq_on(struct domain *d, int i) {
  11.137 +	return ((EXTRALIST(d,i)->next != NULL) &&
  11.138 +		(EXTRALIST(d,i)->next != EXTRALIST(d,i)));
  11.139 +}
  11.140 +
  11.141 +static inline void extraq_add_head(struct domain *d, int i)
  11.142 +{
  11.143 +    list_add(EXTRALIST(d,i), EXTRAQ(d->processor,i));
  11.144 +}
  11.145 +
  11.146 +static inline void extraq_add_tail(struct domain *d, int i)
  11.147 +{
  11.148 +    list_add_tail(EXTRALIST(d,i), EXTRAQ(d->processor,i));
  11.149 +}
  11.150 +
  11.151 +static inline void extraq_del(struct domain *d, int i)
  11.152 +{
  11.153 +	struct list_head *list = EXTRALIST(d,i);
  11.154 +	/*if (!extraq_on(d,i)) {
  11.155 +		PRINT(0,"extraq_del: domain %i is NOT on L%i extraq "\
  11.156 +			"HALTING\n",d->id,i);
  11.157 +		sedf_dump_cpu_state(0);(*((int*)0))++;
  11.158 +	}*/
  11.159 +	PRINT(3, "Removing domain %i from L%i extraq\n", d->id,i);	
  11.160 +	list_del(list);
  11.161 +	list->next = NULL;
  11.162 +}
  11.163 +
  11.164 +/* adds a domain to the queue of processes which are aware of extra time. List
  11.165 +   is sorted by score, where a lower score means higher priority for an extra
  11.166 +   slice. It also updates the score, by simply subtracting a fixed value from
  11.167 +   each entry, in order to avoid overflow. The algorithm works by simply
  11.168 +   charging each domain that recieved extratime with an inverse of its weight.
  11.169 + */ 
  11.170 +static inline void extraq_add_sort_update(struct domain *d, int i, int sub) {
  11.171 +	struct list_head     *cur;
  11.172 +	struct sedf_dom_info *curinf;
  11.173 +	
  11.174 +	/*if (extraq_on(d,i)) {
  11.175 +		PRINT(0,"extraq_add_sort_update: domain %i is already on "\
  11.176 +		        "L%i extraq! HALTING\n",d->id,i);
  11.177 +		sedf_dump_cpu_state(0);(*((int*)0))++;
  11.178 +	}*/
  11.179 +	PRINT(3, "Adding domain %i (score= %i, short_pen= %lli) to L%i "\
  11.180 +	         "extraq\n", d->id, DOM_INFO(d)->score[i],
  11.181 +	         DOM_INFO(d)->short_block_lost_tot, i);	
  11.182 +	/*iterate through all elements to find our "hole" and on our way
  11.183 +	  update all the other scores*/
  11.184 +	list_for_each(cur,EXTRAQ(d->processor,i)){
  11.185 +		curinf = list_entry(cur,struct sedf_dom_info,extralist[i]);
  11.186 +		curinf->score[i] -= sub;
  11.187 +		if (DOM_INFO(d)->score[i] < curinf->score[i])
  11.188 +	 		break;
  11.189 +		else
  11.190 +			PRINT(4,"\tbehind domain %i (score= %i)\n",
  11.191 +			      curinf->owner->id, curinf->score[i]);
  11.192 +	}
  11.193 +	/*cur now contains the element, before which we'll enqueue*/
  11.194 +	PRINT(3, "\tlist_add to %x\n", cur->prev);
  11.195 +	list_add(EXTRALIST(d,i),cur->prev);
  11.196 +	
  11.197 +	/*continue updating the extraq*/
  11.198 +	if ((cur != EXTRAQ(d->processor,i)) && sub)
  11.199 +		for (cur = cur->next; cur != EXTRAQ(d->processor,i);
  11.200 +		     cur = cur-> next) {
  11.201 +			curinf = list_entry(cur,struct sedf_dom_info,
  11.202 +				extralist[i]);
  11.203 +			curinf->score[i] -= sub;
  11.204 +			PRINT(4, "\tupdating domain %i (score= %llu)\n",
  11.205 +			      curinf->owner->id, curinf->score[i]);
  11.206 +		}
  11.207 +}
  11.208 +static inline void extraq_check(struct domain *d) {
  11.209 +	if (extraq_on(d, EXTRA_UTIL_Q)) {
  11.210 +		PRINT(2,"Dom %i is on extraQ\n",d->id);
  11.211 +		if (!(DOM_INFO(d)->extra & EXTRA_AWARE) &&
  11.212 +		    !extra_runs(DOM_INFO(d))) {
  11.213 +			extraq_del(d, EXTRA_UTIL_Q);
  11.214 +			PRINT(2,"Removed dom %i from L1 extraQ\n",d->id);
  11.215 +		}
  11.216 +	} else {
  11.217 +		PRINT(2,"Dom %i is NOT on L1 extraQ\n",d->id);
  11.218 +		if ((DOM_INFO(d)->extra & EXTRA_AWARE) && domain_runnable(d))
  11.219 +		{
  11.220 +			#if (EXTRA == EXTRA_ROUNDR)
  11.221 +			/*Favour domains which got short unblocked*/
  11.222 +			extraq_add_tail(d, EXTRA_UTIL_Q);
  11.223 +			#elif (EXTRA == EXTRA_SLICE_WEIGHT || \
  11.224 +			       EXTRA == EXTRA_BLOCK_WEIGHT)
  11.225 +			extraq_add_sort_update(d, EXTRA_UTIL_Q, 0);
  11.226 +			#elif
  11.227 +			;
  11.228 +			#endif
  11.229 +			PRINT(2,"Added dom %i to L1 extraQ\n",d->id);
  11.230 +		}
  11.231 +	}
  11.232 +}
  11.233 +static inline void __del_from_queue(struct domain *d)
  11.234 +{
  11.235 +    struct list_head *list = LIST(d);
  11.236 +    PRINT(3,"Removing domain %i (bop= %llu) from runq/waitq\n", d->id,
  11.237 +          PERIOD_BEGIN(DOM_INFO(d)));
  11.238 +    list_del(list);
  11.239 +    list->next = NULL;
  11.240 +}
  11.241 +
  11.242 +/* adds a domain to the queue of processes which wait for the beginning of the
  11.243 +   next period; this list is therefore sortet by this time, which is simply
  11.244 +   absol. deadline - period
  11.245 + */ 
  11.246 +static inline void __add_to_waitqueue_sort(struct domain *d) {
  11.247 +	struct list_head     *cur;
  11.248 +	struct sedf_dom_info *curinf;
  11.249 +	
  11.250 +	PRINT(3,"Adding domain %i (bop= %llu) to waitq\n", d->id,
  11.251 +	      PERIOD_BEGIN(DOM_INFO(d)));
  11.252 +	      
  11.253 +	/*iterate through all elements to find our "hole"*/
  11.254 +	list_for_each(cur,WAITQ(d->processor)){
  11.255 +		curinf = list_entry(cur,struct sedf_dom_info,list);
  11.256 +		if (PERIOD_BEGIN(DOM_INFO(d)) < PERIOD_BEGIN(curinf))
  11.257 +	 		break;
  11.258 +		else
  11.259 +			PRINT(4,"\tbehind domain %i (bop= %llu)\n",
  11.260 +			      curinf->owner->id, PERIOD_BEGIN(curinf));
  11.261 +	}
  11.262 +	/*cur now contains the element, before which we'll enqueue*/
  11.263 +	PRINT(3,"\tlist_add to %x\n",cur->prev);
  11.264 +	list_add(LIST(d),cur->prev);
  11.265 +
  11.266 +}
  11.267 +
  11.268 +/* adds a domain to the queue of processes which have started their current
  11.269 +   period and are runnable (i.e. not blocked, dieing,...). The first element
  11.270 +   on this list is running on the processor, if the list is empty the idle
  11.271 +   task will run. As we are implementing EDF, this list is sorted by deadlines.
  11.272 + */ 
  11.273 +static inline void __add_to_runqueue_sort(struct domain *d) {
  11.274 +	struct list_head     *cur;
  11.275 +	struct sedf_dom_info *curinf;
  11.276 +
  11.277 +	PRINT(3,"Adding domain %i (deadl= %llu) to runq\n", d->id,
  11.278 +	      DOM_INFO(d)->absdead);	
  11.279 +	      
  11.280 +	/*iterate through all elements to find our "hole"*/
  11.281 +	list_for_each(cur, RUNQ(d->processor)) {
  11.282 +		curinf = list_entry(cur, struct sedf_dom_info, list);
  11.283 +		if (DOM_INFO(d)->absdead < curinf->absdead)
  11.284 +	 		break;
  11.285 +		else
  11.286 +			PRINT(4,"\tbehind domain %i (deadl= %llu)\n",
  11.287 +			      curinf->owner->id, curinf->absdead);
  11.288 +	}
  11.289 +	
  11.290 +	/*cur now contains the element, before which we'll enqueue*/
  11.291 +	PRINT(3,"\tlist_add to %x\n",cur->prev);
  11.292 +	list_add(LIST(d),cur->prev);
  11.293 +
  11.294 +}
  11.295 +static inline int __task_on_queue(struct domain *d) {
  11.296 +	return (((LIST(d))->next != NULL) && (LIST(d)->next != LIST(d)));
  11.297 +}
  11.298 +
  11.299 +/* Initialises the queues and creates the domain info cache */
  11.300 +static int sedf_init_scheduler() {
  11.301 +	int i;
  11.302 +	PRINT(2,"sedf_init_scheduler was called\n");
  11.303 +	
  11.304 +	for ( i = 0; i < NR_CPUS; i++ ) {
  11.305 +		schedule_data[i].sched_priv = 
  11.306 +			xmalloc(sizeof(struct sedf_cpu_info));
  11.307 +		if ( schedule_data[i].sched_priv == NULL )
  11.308 +			return -1;
  11.309 +		INIT_LIST_HEAD(WAITQ(i));
  11.310 +		INIT_LIST_HEAD(RUNQ(i));
  11.311 +		INIT_LIST_HEAD(EXTRAQ(i,EXTRA_PEN_Q));
  11.312 +		INIT_LIST_HEAD(EXTRAQ(i,EXTRA_UTIL_Q));
  11.313 +	}
  11.314 +	dom_info_cache = xmem_cache_create("SEDF dom info",
  11.315 +		sizeof(struct sedf_dom_info), 0, 0, 0, NULL);
  11.316 +	if ( dom_info_cache == NULL )
  11.317 +	{
  11.318 +		printk("Could not allocate SLAB cache.\n");
  11.319 +		return -1;
  11.320 +	}
  11.321 +	
  11.322 +	return 0;   
  11.323 +}
  11.324 +
  11.325 +/* Allocates memory for per domain private scheduling data*/
  11.326 +static int sedf_alloc_task(struct domain *d) {
  11.327 +	PRINT(2,"sedf_alloc_task was called, domain-id %i\n",d->id);
  11.328 +	if ( (d->sched_priv = xmem_cache_alloc(dom_info_cache)) == NULL )
  11.329 +		return -1;
  11.330 +	memset(d->sched_priv, 0, sizeof(struct sedf_dom_info));
  11.331 +	return 0;
  11.332 +}
  11.333 +
  11.334 +/* Setup the sedf_dom_info */
  11.335 +static void sedf_add_task(struct domain *d)
  11.336 +{
  11.337 +	struct sedf_dom_info *inf=DOM_INFO(d);
  11.338 +	inf->owner = d;
  11.339 +	
  11.340 +	PRINT(2,"sedf_add_task was called, domain-id %i\n",d->id);
  11.341 +	if (d->id==0) {
  11.342 +		/*set dom0 to something useful to boot the machine*/
  11.343 +		inf->period    = MILLISECS(20);
  11.344 +		inf->slice     = MILLISECS(15);
  11.345 +		inf->latency   = 0;
  11.346 +		inf->absdead   = 0;
  11.347 +		inf->extra     = EXTRA_NONE;/*EXTRA_AWARE; */
  11.348 +	}
  11.349 +	else {
  11.350 +		/*other domains run in best effort mode*/
  11.351 +		inf->period    = MILLISECS(20);
  11.352 +		inf->slice     = 0;
  11.353 +		inf->absdead   = 0;
  11.354 +		inf->latency   = 0;
  11.355 +		inf->extra     = EXTRA_AWARE;
  11.356 +	}
  11.357 +	inf->period_orig = inf->period; inf->slice_orig = inf->slice;
  11.358 +	INIT_LIST_HEAD(&(inf->list));
  11.359 +	INIT_LIST_HEAD(&(inf->extralist[EXTRA_PEN_Q]));
  11.360 +	INIT_LIST_HEAD(&(inf->extralist[EXTRA_UTIL_Q]));
  11.361 +}
  11.362 +
  11.363 +/* Frees memory used by domain info */
  11.364 +static void sedf_free_task(struct domain *d)
  11.365 +{
  11.366 +	PRINT(2,"sedf_free_task was called, domain-id %i\n",d->id);
  11.367 +	ASSERT(d->sched_priv != NULL);
  11.368 +	xmem_cache_free(dom_info_cache, d->sched_priv);
  11.369 +}
  11.370 +
  11.371 +/* Initialises idle task */
  11.372 +static int sedf_init_idle_task(struct domain *d) {
  11.373 +	PRINT(2,"sedf_init_idle_task was called, domain-id %i\n",d->id);
  11.374 +	if ( sedf_alloc_task(d) < 0 )
  11.375 +		return -1;
  11.376 +	
  11.377 +	sedf_add_task(d);
  11.378 +	DOM_INFO(d)->absdead = 0;
  11.379 +	set_bit(DF_RUNNING, &d->flags);
  11.380 +	/*the idle task doesn't have to turn up on any list...*/
  11.381 +	return 0;
  11.382 +}
  11.383 +
  11.384 +/* handles the rescheduling, bookkeeping of domains running in their realtime-time :)*/
  11.385 +static inline void desched_edf_dom (s_time_t now, struct domain* d) {
  11.386 +	struct sedf_dom_info* inf = DOM_INFO(d);
  11.387 +	/*current domain is running in real time mode*/
  11.388 +	
  11.389 +	/*update the domains cputime*/
  11.390 +	inf->cputime += now - inf->sched_start;
  11.391 +
  11.392 +	/*scheduling decisions, which don't remove the running domain
  11.393 +	  from the runq*/
  11.394 +	if ((inf->cputime < inf->slice) && domain_runnable(d))
  11.395 +		return;
  11.396 +		
  11.397 +	__del_from_queue(d);
  11.398 +	/*if (__task_on_queue(current)) {
  11.399 +		PRINT(0,"domain %i was removed but still on run/waitq => "\
  11.400 +		        "HALT\n",current->id);
  11.401 +		sedf_dump_cpu_state(0);(*((int*)0))++;
  11.402 +	}*/
  11.403 +	
  11.404 +	/*manage bookkeeping (i.e. calculate next deadline,
  11.405 +	  memorize overun-time of slice) of finished domains*/
  11.406 +	if (inf->cputime >= inf->slice) {
  11.407 +		inf->cputime -= inf->slice;
  11.408 +		
  11.409 +		if (inf->period < inf->period_orig) {
  11.410 +			/*this domain runs in latency scaling or burst mode*/
  11.411 +			#if (UNBLOCK == UNBLOCK_BURST)
  11.412 +			if (now - inf->absunblock >= 2 * inf->period)
  11.413 +			#endif
  11.414 +			{
  11.415 +				inf->period *= 2; inf->slice *= 2;
  11.416 +				if ((inf->period > inf->period_orig) ||
  11.417 +				    (inf->slice > inf->slice_orig)) {
  11.418 +					/*reset slice & period*/
  11.419 +					inf->period = inf->period_orig;
  11.420 +					inf->slice = inf->slice_orig;
  11.421 +				}
  11.422 +			}
  11.423 +		}
  11.424 +		/*set next deadline*/
  11.425 +		inf->absdead += inf->period;
  11.426 +	}
  11.427 +	/*if (inf->absdead<now)
  11.428 +		printk("Domain %i exceeded it't deadline!!!! "\
  11.429 +		       "(now: %llu ddl: %llu)\n", current->id, now,
  11.430 +		       inf->absdead);*/
  11.431 +		       
  11.432 +	/*add a runnable domain to the waitqueue*/
  11.433 +	if (domain_runnable(d))
  11.434 +		__add_to_waitqueue_sort(d);
  11.435 +	else {
  11.436 +		/*we have a blocked realtime task*/
  11.437 +		inf->absblock = now;
  11.438 +		#if (EXTRA > EXTRA_OFF)
  11.439 +		#if (EXTRA == EXTRA_BLOCK_WEIGHT)
  11.440 +		if (extraq_on(d,EXTRA_PEN_Q)) extraq_del(d,EXTRA_PEN_Q);
  11.441 +		#endif
  11.442 +		if (extraq_on(d,EXTRA_UTIL_Q)) extraq_del(d,EXTRA_UTIL_Q);
  11.443 +		#endif
  11.444 +	}
  11.445 +}
  11.446 +
  11.447 +/* Update all elements on the queues */
  11.448 +static inline void update_queues(
  11.449 +s_time_t now, struct list_head* runq, struct list_head* waitq) {
  11.450 +	struct list_head     *cur,*tmp;
  11.451 +	struct sedf_dom_info *curinf;
  11.452 +	
  11.453 +	PRINT(3,"Updating waitq..\n");
  11.454 +	/*check for the first elements of the waitqueue, whether their
  11.455 +	  next period has already started*/
  11.456 +	list_for_each_safe(cur, tmp, waitq) {
  11.457 +		curinf = list_entry(cur, struct sedf_dom_info, list);
  11.458 +		PRINT(4,"\tLooking @ dom %i\n", curinf->owner->id);
  11.459 +		if (PERIOD_BEGIN(curinf) <= now) {
  11.460 +			__del_from_queue(curinf->owner);
  11.461 +			__add_to_runqueue_sort(curinf->owner);
  11.462 +		}
  11.463 +		else
  11.464 +			break;
  11.465 +	}
  11.466 +	
  11.467 +	PRINT(3,"Updating runq..\n");
  11.468 +	/*process the runq, find domains that are on
  11.469 +	  the runqueue which shouldn't be there*/
  11.470 +	list_for_each_safe(cur, tmp, runq) {
  11.471 +		curinf = list_entry(cur,struct sedf_dom_info,list);
  11.472 +		PRINT(4,"\tLooking @ dom %i\n", curinf->owner->id);
  11.473 +		if (unlikely(curinf->slice == 0)) {
  11.474 +			/*ignore domains with empty slice*/
  11.475 +			PRINT(4,"\tUpdating zero-slice domain %i\n",
  11.476 +			      curinf->owner->id);
  11.477 +			__del_from_queue(curinf->owner);
  11.478 +			
  11.479 +			/*move them to their next period*/
  11.480 +			curinf->absdead += curinf->period;
  11.481 +			/*and put them back into the queue*/
  11.482 +			__add_to_waitqueue_sort(curinf->owner);
  11.483 +		}
  11.484 +		else {
  11.485 +			if (unlikely((curinf->absdead < now) ||
  11.486 +			   (curinf->cputime > curinf->slice))) {
  11.487 +				/*we missed the deadline or the slice was
  11.488 +				  already finished... might hapen because
  11.489 +				  of dom_adj.*/
  11.490 +				PRINT(4,"\tDomain %i exceeded it's deadline/"\
  11.491 +				       "slice (%llu / %llu) now: %llu "\
  11.492 +				       "cputime: %llu\n", curinf->owner->id,
  11.493 +				       curinf->absdead, curinf->slice, now,
  11.494 +				       curinf->cputime);
  11.495 +				__del_from_queue(curinf->owner);
  11.496 +				/*common case: we miss one period!*/
  11.497 +				curinf->absdead += curinf->period;
  11.498 +				
  11.499 +				/*if we are still behind: modulo arithmetic,
  11.500 +				  force deadline to be in future and
  11.501 +				  aligned to period borders!*/
  11.502 +				if (unlikely(curinf->absdead < now))
  11.503 +					curinf->absdead += 
  11.504 +					  DIV_UP(now - curinf->absdead,
  11.505 +					     curinf->period) * curinf->period;
  11.506 +					     
  11.507 +				/*give a fresh slice*/
  11.508 +				curinf->cputime = 0;
  11.509 +				if (PERIOD_BEGIN(curinf) < now)
  11.510 +					__add_to_waitqueue_sort(curinf->owner);
  11.511 +				else
  11.512 +					__add_to_runqueue_sort(curinf->owner);
  11.513 +			}
  11.514 +			else
  11.515 +				break;
  11.516 +		}
  11.517 +	}
  11.518 +	PRINT(3,"done updating the queues\n");
  11.519 +}
  11.520 +
  11.521 +#if (EXTRA > EXTRA_OFF)
  11.522 +/* removes a domain from the head of the according extraQ and
  11.523 +   requeues it at a specified position:
  11.524 +     round-robin extratime: end of extraQ
  11.525 +     weighted ext.: insert in sorted list by score
  11.526 +   if the domain is blocked / has regained its short-block-loss
  11.527 +   time it is not put on any queue */
  11.528 +static inline void desched_extra_dom(s_time_t now, struct domain* d) {
  11.529 +	struct sedf_dom_info	*inf = DOM_INFO(d);
  11.530 +	int 			i    = extra_get_cur_q(inf);
  11.531 +	
  11.532 +	#if (EXTRA == EXTRA_SLICE_WEIGHT || EXTRA == EXTRA_BLOCK_WEIGHT)
  11.533 +	unsigned long         oldscore;
  11.534 +	#endif
  11.535 +	
  11.536 +	/*unset all running flags*/
  11.537 +	inf->extra  &= ~(EXTRA_RUN_PEN | EXTRA_RUN_UTIL);
  11.538 +	/*fresh slice for the next run*/
  11.539 +	inf->cputime = 0;
  11.540 +	/*accumulate total extratime*/
  11.541 +	inf->extra_time_tot += now - inf->sched_start;
  11.542 +	/*remove extradomain from head of the queue*/
  11.543 +	extraq_del(d, i);
  11.544 +
  11.545 +	#if (EXTRA == EXTRA_ROUNDR)
  11.546 +	if (domain_runnable(d))
  11.547 +		/*add to the tail if it is runnable => round-robin*/
  11.548 +		extraq_add_tail(d, EXTRA_UTIL_Q);
  11.549 +	#elif (EXTRA == EXTRA_SLICE_WEIGHT || EXTRA == EXTRA_BLOCK_WEIGHT)
  11.550 +	/*update the score*/
  11.551 +	oldscore      = inf->score[i];
  11.552 +	#if (EXTRA == EXTRA_BLOCK_WEIGHT)
  11.553 +	if (i == EXTRA_PEN_Q) {
  11.554 +		/*domain was running in L0 extraq*/
  11.555 +		/*reduce block lost, probably more sophistication here!*/
  11.556 +		/*inf->short_block_lost_tot -= EXTRA_QUANTUM;*/
  11.557 +		inf->short_block_lost_tot -= now - inf->sched_start;
  11.558 +		PRINT(3,"Domain %i: Short_block_lost: %lli\n", 
  11.559 +		      inf->owner->id, inf->short_block_lost_tot);
  11.560 +		if (inf->short_block_lost_tot <= 0) {
  11.561 +			PRINT(4,"Domain %i compensated short block loss!\n");
  11.562 +			/*we have (over-)compensated our block penalty*/
  11.563 +			inf->short_block_lost_tot = 0;
  11.564 +			/*we don't want a place on the penalty queue anymore!*/
  11.565 +			inf->extra &= ~EXTRA_WANT_PEN_Q;
  11.566 +			/*do not add us on this block extraq again!*/
  11.567 +			return;
  11.568 +		}
  11.569 +		/*we have to go again for another try in the block-extraq,
  11.570 +		  the score is not used incremantally here, as this is
  11.571 +		  already done by recalculating the block_lost*/
  11.572 +		inf->score[EXTRA_PEN_Q] = (inf->period << 10) /
  11.573 +		                          inf->short_block_lost_tot;
  11.574 +		oldscore = 0;
  11.575 +	} else
  11.576 +	#endif
  11.577 +	{
  11.578 +		/*domain was running in L1 extraq => score is inverse of
  11.579 +		  utilization and is used somewhat incremental!*/
  11.580 +		if (inf->slice)
  11.581 +			/*NB: use fixed point arithmetic with 10 bits*/
  11.582 +			inf->score[EXTRA_UTIL_Q] = (inf->period << 10) /
  11.583 +			                            inf->slice;
  11.584 +		else
  11.585 +			/*set best effort domains to the maximum value*/
  11.586 +			inf->score[EXTRA_UTIL_Q] = 2^10;
  11.587 +	}
  11.588 +	if (domain_runnable(d))
  11.589 +		/*add according to score: weighted round robin*/
  11.590 +		extraq_add_sort_update(d, i, oldscore);
  11.591 +	else {
  11.592 +		inf->absblock = now;
  11.593 +		/*if (!__task_on_queue(d)) 
  11.594 +			printf("Oops... We attempt to remove d %i from the "\
  11.595 +			       "waitq, but it is not on :(\n",d->id);*/
  11.596 +		/*remove this blocked domain from the waitq!*/
  11.597 +		__del_from_queue(d);				
  11.598 +		/*make sure that we remove a blocked domain from the other
  11.599 +		  extraq aswell (this caused hours of debugging!)*/
  11.600 +		#if (EXTRA == EXTRA_BLOCK_WEIGHT)
  11.601 +		if (i == EXTRA_PEN_Q) {
  11.602 +			if (extraq_on(d,EXTRA_UTIL_Q))
  11.603 +				extraq_del(d,EXTRA_UTIL_Q);
  11.604 +		}
  11.605 +		else {
  11.606 +			if (extraq_on(d,EXTRA_PEN_Q))
  11.607 +				extraq_del(d,EXTRA_PEN_Q);
  11.608 +		}
  11.609 +		#endif
  11.610 +	}
  11.611 +	#endif
  11.612 +	/*if (!domain_runnable(d)) {
  11.613 +		if (extraq_on(d,EXTRA_UTIL_Q)) {
  11.614 +			PRINT(0,"domain %i is blocked but still on L1 "\
  11.615 +			        "xq=> HALT\n",d->id);
  11.616 +			sedf_dump_cpu_state(0);(*((int*)0))++;
  11.617 +		}
  11.618 +		if (__task_on_queue(d)) {
  11.619 +			PRINT(0,"domain %i is blocked but still on run/waitq"\
  11.620 +			        "=> HALT\n",d->id);
  11.621 +			sedf_dump_cpu_state(0);(*((int*)0))++;
  11.622 +		}
  11.623 +	}*/
  11.624 +}
  11.625 +#endif
  11.626 +
  11.627 +
  11.628 +static inline task_slice_t sedf_do_extra_schedule
  11.629 +(s_time_t now, s_time_t end_xt, struct list_head *extraq[], int cpu) {
  11.630 +	task_slice_t 		ret;
  11.631 +	struct sedf_dom_info	*runinf;
  11.632 +	
  11.633 +	if (end_xt - now < EXTRA_QUANTUM)
  11.634 +		goto return_idle;
  11.635 +#if (EXTRA == EXTRA_BLOCK_WEIGHT)
  11.636 +	if (!list_empty(extraq[EXTRA_PEN_Q])) {
  11.637 +		/*we still have elements on the level 0 extraq 
  11.638 +		  => let those run first!*/
  11.639 +		runinf   = list_entry(extraq[EXTRA_PEN_Q]->next, 
  11.640 +		              struct sedf_dom_info, extralist[EXTRA_PEN_Q]);
  11.641 +		runinf->extra |= EXTRA_RUN_PEN;
  11.642 +		ret.task = runinf->owner;
  11.643 +		ret.time = EXTRA_QUANTUM;
  11.644 +#ifdef SEDF_STATS
  11.645 +		runinf->pen_extra_slices++;
  11.646 +#endif
  11.647 +	} else
  11.648 +#endif
  11.649 +	if (!list_empty(extraq[EXTRA_UTIL_Q])) {
  11.650 +		/*use elements from the normal extraqueue*/
  11.651 +		runinf   = list_entry(extraq[EXTRA_UTIL_Q]->next,
  11.652 +		              struct sedf_dom_info,extralist[EXTRA_UTIL_Q]);
  11.653 +		runinf->extra |= EXTRA_RUN_UTIL;
  11.654 +		ret.task = runinf->owner;
  11.655 +		ret.time = EXTRA_QUANTUM;
  11.656 +	}
  11.657 +	else
  11.658 +		goto return_idle;
  11.659 +
  11.660 +	return ret;
  11.661 +	
  11.662 +return_idle:
  11.663 +	ret.task = IDLETASK(cpu);
  11.664 +	ret.time = end_xt - now;
  11.665 +	return ret;
  11.666 +}
  11.667 +/* Main scheduling function
  11.668 +   Reasons for calling this function are:
  11.669 +   -timeslice for the current period used up
  11.670 +   -domain on waitqueue has started it's period
  11.671 +   -and various others ;) in general: determine which domain to run next*/
  11.672 +static task_slice_t sedf_do_schedule(s_time_t now)
  11.673 +{
  11.674 +	int                   cpu      = current->processor;
  11.675 +	struct list_head     *runq     = RUNQ(cpu);
  11.676 +	struct list_head     *waitq    = WAITQ(cpu);
  11.677 +	#if (EXTRA > EXTRA_OFF)
  11.678 +	struct sedf_dom_info *inf      = DOM_INFO(current);
  11.679 +	struct list_head     *extraq[] = {EXTRAQ(cpu,EXTRA_PEN_Q),
  11.680 +	                                  EXTRAQ(cpu, EXTRA_UTIL_Q)};
  11.681 +	#endif
  11.682 +	task_slice_t          ret;
  11.683 +	/*int i = 0;*/
  11.684 +	/*idle tasks don't need any of the following stuf*/
  11.685 +	if (is_idle_task(current))
  11.686 +		goto check_waitq;
  11.687 +	
  11.688 +	#if (EXTRA > EXTRA_OFF)
  11.689 +	if (unlikely(extra_runs(inf))) {
  11.690 +		/*i=1;*/
  11.691 +		/*special treatment of domains running in extra time*/
  11.692 +		desched_extra_dom(now, current);
  11.693 +	}
  11.694 +	else 
  11.695 +	#endif
  11.696 +	{
  11.697 +		/*i=2;*/
  11.698 +		desched_edf_dom(now, current);
  11.699 +	}
  11.700 +	/*if (!domain_runnable(current)) {
  11.701 +		if (extraq_on(current,EXTRA_UTIL_Q)) {
  11.702 +			PRINT(0,"domain %i is blocked but still on L1 xq"\
  11.703 +			        " branch %i=> HALT\n", current->id, i);
  11.704 +			sedf_dump_cpu_state(0);(*((int*)0))++;
  11.705 +		}
  11.706 +		if (__task_on_queue(current)) {
  11.707 +			PRINT(0,"domain %i is blocked but still on run/waitq"\
  11.708 +			        " branch %i=> HALT\n",current->id,i);
  11.709 +			sedf_dump_cpu_state(0);(*((int*)0))++;
  11.710 +		}
  11.711 +	}*/
  11.712 +check_waitq:
  11.713 +	update_queues(now, runq, waitq);
  11.714 +	
  11.715 +	/*now simply pick the first domain from the runqueue*/
  11.716 +	struct sedf_dom_info *runinf, *waitinf;
  11.717 +	
  11.718 +	if (!list_empty(runq)) {
  11.719 +		runinf   = list_entry(runq->next,struct sedf_dom_info,list);
  11.720 +		ret.task = runinf->owner;
  11.721 +		if (!list_empty(waitq)) {
  11.722 +			waitinf  = list_entry(waitq->next,
  11.723 +			               struct sedf_dom_info,list);
  11.724 +			/*rerun scheduler, when scheduled domain reaches it's
  11.725 +			  end of slice or the first domain from the waitqueue
  11.726 +			  gets ready*/
  11.727 +			ret.time = MIN(now + runinf->slice - runinf->cputime,
  11.728 +			               PERIOD_BEGIN(waitinf)) - now;
  11.729 +		}
  11.730 +		else {
  11.731 +			ret.time = runinf->slice - runinf->cputime;
  11.732 +		}
  11.733 +		goto sched_done;
  11.734 +	}
  11.735 +	
  11.736 +	if (!list_empty(waitq)) {
  11.737 +		waitinf  = list_entry(waitq->next,struct sedf_dom_info,list);
  11.738 +		/*we could not find any suitable domain 
  11.739 +		  => look for domains that are aware of extratime*/
  11.740 +		#if (EXTRA > EXTRA_OFF)
  11.741 +		ret = sedf_do_extra_schedule(now, PERIOD_BEGIN(waitinf),
  11.742 +		                             extraq, cpu);
  11.743 +		#else
  11.744 +		ret.task = IDLETASK(cpu);
  11.745 +		ret.time = PERIOD_BEGIN(waitinf) - now;
  11.746 +		#endif
  11.747 +	}
  11.748 +	else {
  11.749 +		/*this could probably never happen, but one never knows...*/
  11.750 +		/*it can... imagine a second CPU, which is pure scifi ATM,
  11.751 +		  but one never knows ;)*/
  11.752 +		ret.task = IDLETASK(cpu);
  11.753 +		ret.time = SECONDS(1);
  11.754 +	}
  11.755 +
  11.756 +sched_done:	
  11.757 +	/*TODO: Do something USEFUL when this happens and find out, why it
  11.758 +	still can happen!!!*/
  11.759 +	if (ret.time<0) {
  11.760 +		printk("Ouch! We are seriously BEHIND schedule! %lli\n",
  11.761 +		       ret.time);
  11.762 +		ret.time = EXTRA_QUANTUM;
  11.763 +	}
  11.764 +	DOM_INFO(ret.task)->sched_start=now;
  11.765 +	return ret;
  11.766 +}
  11.767 +
  11.768 +static void sedf_sleep(struct domain *d) {
  11.769 +	PRINT(2,"sedf_sleep was called, domain-id %i\n",d->id);
  11.770 +	if ( test_bit(DF_RUNNING, &d->flags) ) {
  11.771 +#ifdef ADV_SCHED_HISTO
  11.772 +		adv_sched_hist_start(d->processor);
  11.773 +#endif
  11.774 +		cpu_raise_softirq(d->processor, SCHEDULE_SOFTIRQ);
  11.775 +	}
  11.776 +	else  {
  11.777 +		if ( __task_on_queue(d) )
  11.778 +			__del_from_queue(d);
  11.779 +		#if (EXTRA > EXTRA_OFF)
  11.780 +		if (extraq_on(d, EXTRA_UTIL_Q)) 
  11.781 +			extraq_del(d, EXTRA_UTIL_Q);
  11.782 +		#endif
  11.783 +		#if (EXTRA == EXTRA_BLOCK_WEIGHT)
  11.784 +		if (extraq_on(d, EXTRA_PEN_Q))
  11.785 +			extraq_del(d, EXTRA_PEN_Q);
  11.786 +		#endif
  11.787 +	}
  11.788 +}
  11.789 +
  11.790 +/* This function wakes up a domain, i.e. moves them into the waitqueue
  11.791 + * things to mention are: admission control is taking place nowhere at
  11.792 + * the moment, so we can't be sure, whether it is safe to wake the domain
  11.793 + * up at all. Anyway, even if it is safe (total cpu usage <=100%) there are
  11.794 + * some considerations on when to allow the domain to wake up and have it's
  11.795 + * first deadline...
  11.796 + * I detected 3 cases, which could describe the possible behaviour of the
  11.797 + * scheduler,
  11.798 + * and I'll try to make them more clear:
  11.799 + *
  11.800 + * 1. Very conservative
  11.801 + *     -when a blocked domain unblocks, it is allowed to start execution at
  11.802 + *      the beginning of the next complete period
  11.803 + *      (D..deadline, R..running, B..blocking/sleeping, U..unblocking/waking up
  11.804 + *
  11.805 + *      DRRB_____D__U_____DRRRRR___D________ ... 
  11.806 + *
  11.807 + *     -this causes the domain to miss a period (and a deadlline)
  11.808 + *     -doesn't disturb the schedule at all
  11.809 + *     -deadlines keep occuring isochronous
  11.810 + *
  11.811 + * 2. Conservative Part 1: Short Unblocking
  11.812 + *     -when a domain unblocks in the same period as it was blocked it
  11.813 + *      unblocks and may consume the rest of it's original time-slice minus
  11.814 + *      the time it was blocked
  11.815 + *      (assume period=9, slice=5)
  11.816 + *
  11.817 + *      DRB_UR___DRRRRR___D...
  11.818 + *
  11.819 + *     -this also doesn't disturb scheduling, but might lead to the fact, that
  11.820 + *      the domain can't finish it's workload in the period
  11.821 + *     -in addition to that the domain can be treated prioritised when
  11.822 + *      extratime is available
  11.823 + *     -addition: experiments hve shown that this may have a HUGE impact on
  11.824 + *      performance of other domains, becaus it can lead to excessive context
  11.825 + *      switches
  11.826 + 
  11.827 + *    Part2: Long Unblocking
  11.828 + *    Part 2a
  11.829 + *     -it is obvious that such accounting of block time, applied when
  11.830 + *      unblocking is happening in later periods, works fine aswell
  11.831 + *     -the domain is treated as if it would have been running since the start
  11.832 + *      of its new period
  11.833 + *
  11.834 + *      DRB______D___UR___D... 
  11.835 + *
  11.836 + *    Part 2b
  11.837 + *     -if one needs the full slice in the next period, it is necessary to
  11.838 + *      treat the unblocking time as the start of the new period, i.e. move
  11.839 + *      the deadline further back (later)
  11.840 + *     -this doesn't disturb scheduling as well, because for EDF periods can
  11.841 + *      be treated as minimal inter-release times and scheduling stays
  11.842 + *      correct, when deadlines are kept relative to the time the process
  11.843 + *      unblocks
  11.844 + *
  11.845 + *      DRB______D___URRRR___D...<prev [Thread] next>
  11.846 + *                       (D) <- old deadline was here
  11.847 + *     -problem: deadlines don't occur isochronous anymore
  11.848 + *    Part 2c (Improved Atropos design)
  11.849 + *     -when a domain unblocks it is given a very short period (=latency hint)
  11.850 + *      and slice length scaled accordingly
  11.851 + *     -both rise again to the original value (e.g. get doubled every period)
  11.852 + *
  11.853 + * 3. Unconservative (i.e. incorrect)
  11.854 + *     -to boost the performance of I/O dependent domains it would be possible
  11.855 + *      to put the domain into the runnable queue immediately, and let it run
  11.856 + *      for the remainder of the slice of the current period
  11.857 + *      (or even worse: allocate a new full slice for the domain) 
  11.858 + *     -either behaviour can lead to missed deadlines in other domains as
  11.859 + *      opposed to approaches 1,2a,2b
  11.860 + */
  11.861 +static inline void unblock_short_vcons
  11.862 +(struct sedf_dom_info* inf, s_time_t now) {
  11.863 +	inf->absdead += inf->period;
  11.864 +	inf->cputime = 0;
  11.865 +}
  11.866 +
  11.867 +static inline void unblock_short_cons(struct sedf_dom_info* inf, s_time_t now)
  11.868 +{
  11.869 +	/*treat blocked time as consumed by the domain*/
  11.870 +	inf->cputime += now - inf->absblock;	
  11.871 +	if (inf->cputime + EXTRA_QUANTUM > inf->slice) {
  11.872 +		/*we don't have a reasonable amount of time in 
  11.873 +		  our slice left :( => start in next period!*/
  11.874 +		unblock_short_vcons(inf, now);
  11.875 +	}
  11.876 +#ifdef SEDF_STATS
  11.877 +	else
  11.878 +		inf->short_cont++;
  11.879 +#endif
  11.880 +}
  11.881 +static inline void unblock_short_extra_support (struct sedf_dom_info* inf,
  11.882 +   s_time_t now) {
  11.883 +	/*this unblocking scheme tries to support the domain, by assigning it
  11.884 +	   a priority in extratime distribution according to the loss of time
  11.885 +	   in this slice due to blocking*/
  11.886 +	s_time_t pen;
  11.887 +	
  11.888 +	/*no more realtime execution in this period!*/
  11.889 +	inf->absdead += inf->period;
  11.890 +	if (likely(inf->absblock)) {
  11.891 +		//treat blocked time as consumed by the domain*/
  11.892 +		/*inf->cputime += now - inf->absblock;*/	
  11.893 +		pen = (inf->slice - inf->cputime);
  11.894 +		if (pen < 0) pen = 0;
  11.895 +		/*accumulate all penalties over the periods*/
  11.896 +		/*inf->short_block_lost_tot += pen;*/
  11.897 +		/*set penalty to the current value*/
  11.898 +		inf->short_block_lost_tot = pen;
  11.899 +		/*not sure which one is better.. but seems to work well...*/
  11.900 +		
  11.901 +		if (inf->short_block_lost_tot) {
  11.902 +			inf->score[0] = (inf->period << 10) /
  11.903 +			                 inf->short_block_lost_tot;
  11.904 +#ifdef SEDF_STATS
  11.905 +			inf->pen_extra_blocks++;
  11.906 +#endif
  11.907 +			if (extraq_on(inf->owner, EXTRA_PEN_Q))
  11.908 +				/*remove domain for possible resorting!*/
  11.909 +				extraq_del(inf->owner, EXTRA_PEN_Q);
  11.910 +			else
  11.911 +				/*remember that we want to be on the penalty q
  11.912 +				  so that we can continue when we (un-)block
  11.913 +				  in penalty-extratime*/
  11.914 +				inf->extra |= EXTRA_WANT_PEN_Q;
  11.915 +			
  11.916 +			/*(re-)add domain to the penalty extraq*/
  11.917 +			extraq_add_sort_update(inf->owner,
  11.918 +					 EXTRA_PEN_Q, 0);
  11.919 +		}
  11.920 +	}
  11.921 +	/*give it a fresh slice in the next period!*/
  11.922 +	inf->cputime = 0;
  11.923 +}
  11.924 +static inline void unblock_long_vcons(struct sedf_dom_info* inf, s_time_t now)
  11.925 +{
  11.926 +	/* align to next future period */
  11.927 +	inf->absdead += ((now - inf->absdead) / inf->period + 1)
  11.928 +	                 * inf->period;
  11.929 +	inf->cputime = 0;
  11.930 +}
  11.931 +
  11.932 +static inline void unblock_long_cons_a (struct sedf_dom_info* inf,
  11.933 +   s_time_t now) {
  11.934 +	/*treat the time the domain was blocked in the
  11.935 +	  CURRENT period as consumed by the domain*/
  11.936 +	inf->cputime = (now - inf->absdead) % inf->period;	
  11.937 +	if (inf->cputime + EXTRA_QUANTUM > inf->slice) {
  11.938 +		/*we don't have a reasonable amount of time in our slice
  11.939 +		  left :( => start in next period!*/
  11.940 +		unblock_long_vcons(inf, now);
  11.941 +	}
  11.942 +}
  11.943 +static inline void unblock_long_cons_b(struct sedf_dom_info* inf,s_time_t now) {
  11.944 +	/*Conservative 2b*/
  11.945 +	/*Treat the unblocking time as a start of a new period */
  11.946 +	inf->absdead = now + inf->period;
  11.947 +	inf->cputime = 0;
  11.948 +}
  11.949 +static inline void unblock_long_cons_c(struct sedf_dom_info* inf,s_time_t now) {
  11.950 +	if (likely(inf->latency)) {
  11.951 +		/*scale the slice and period accordingly to the latency hint*/
  11.952 +		/*reduce period temporarily to the latency hint*/
  11.953 +		inf->period = inf->latency;
  11.954 +		/*this results in max. 4s slice/period length*/
  11.955 +		ASSERT((inf->period < ULONG_MAX)
  11.956 +		    && (inf->slice_orig < ULONG_MAX));
  11.957 +		/*scale slice accordingly, so that utilisation stays the same*/
  11.958 +		inf->slice = (inf->period * inf->slice_orig)
  11.959 +		            / inf->period_orig;
  11.960 +		inf->absdead = now + inf->period;
  11.961 +		inf->cputime = 0;
  11.962 +	}	
  11.963 +	else {
  11.964 +		/*we don't have a latency hint.. use some other technique*/
  11.965 +		unblock_long_cons_b(inf, now);
  11.966 +	}
  11.967 +}
  11.968 +/*a new idea of dealing with short blocks: burst period scaling*/
  11.969 +static inline void unblock_short_burst(struct sedf_dom_info* inf, s_time_t now)
  11.970 +{
  11.971 +	/*treat blocked time as consumed by the domain*/
  11.972 +	inf->cputime += now - inf->absblock;
  11.973 +	
  11.974 +	if (inf->cputime + EXTRA_QUANTUM <= inf->slice) {
  11.975 +		/*if we can still use some time in the current slice
  11.976 +		  then use it!*/
  11.977 +#ifdef SEDF_STATS
  11.978 +		/*we let the domain run in the current period*/
  11.979 +		inf->short_cont++;
  11.980 +#endif
  11.981 +	}
  11.982 +	else {
  11.983 +		/*we don't have a reasonable amount of time in
  11.984 +		  our slice left => switch to burst mode*/
  11.985 +		if (likely(inf->absunblock)) {
  11.986 +			/*set the period-length to the current blocking
  11.987 +			  interval, possible enhancements: average over last
  11.988 +			  blocking intervals, user-specified minimum,...*/
  11.989 +			inf->period = now - inf->absunblock;
  11.990 +			/*check for overflow on multiplication*/
  11.991 +			ASSERT((inf->period < ULONG_MAX) 
  11.992 +			    && (inf->slice_orig < ULONG_MAX));
  11.993 +			/*scale slice accordingly, so that utilisation
  11.994 +			  stays the same*/
  11.995 +			inf->slice = (inf->period * inf->slice_orig)
  11.996 +			            / inf->period_orig;
  11.997 +			/*set new (shorter) deadline*/
  11.998 +			inf->absdead += inf->period;
  11.999 +		}
 11.1000 +		else {
 11.1001 +			/*in case we haven't unblocked before
 11.1002 +			  start in next period!*/
 11.1003 +			inf->cputime=0;
 11.1004 +			inf->absdead += inf->period;
 11.1005 +		}
 11.1006 +	}
 11.1007 +	inf->absunblock = now;
 11.1008 +}
 11.1009 +static inline void unblock_long_burst(struct sedf_dom_info* inf,s_time_t now) {
 11.1010 +	if (unlikely(inf->latency && (inf->period > inf->latency))) {
 11.1011 +		/*scale the slice and period accordingly to the latency hint*/
 11.1012 +		inf->period = inf->latency;
 11.1013 +		/*check for overflows on multiplication*/
 11.1014 +		ASSERT((inf->period < ULONG_MAX)
 11.1015 +		    && (inf->slice_orig < ULONG_MAX));
 11.1016 +		/*scale slice accordingly, so that utilisation stays the same*/
 11.1017 +		inf->slice = (inf->period * inf->slice_orig)
 11.1018 +		            / inf->period_orig;
 11.1019 +		inf->absdead = now + inf->period;
 11.1020 +		inf->cputime = 0;
 11.1021 +	}
 11.1022 +	else {
 11.1023 +		/*we don't have a latency hint.. or we are currently in 
 11.1024 +		 "burst mode": use some other technique
 11.1025 +		  NB: this should be in fact the normal way of operation,
 11.1026 +		  when we are in sync with the device!*/
 11.1027 +		unblock_long_cons_b(inf, now);
 11.1028 +	}
 11.1029 +	inf->absunblock = now;
 11.1030 +}
 11.1031 +
 11.1032 +#define DOMAIN_EDF 		1
 11.1033 +#define DOMAIN_EXTRA_PEN 	2
 11.1034 +#define DOMAIN_EXTRA_UTIL 	3
 11.1035 +#define DOMAIN_IDLE 		4
 11.1036 +static inline int get_run_type(struct domain* d) {
 11.1037 +	struct sedf_dom_info* inf = DOM_INFO(d);
 11.1038 +	if (is_idle_task(d))
 11.1039 +		return DOMAIN_IDLE;
 11.1040 +	if (inf->extra & EXTRA_RUN_PEN)
 11.1041 +		return DOMAIN_EXTRA_PEN;
 11.1042 +	if (inf->extra & EXTRA_RUN_UTIL)
 11.1043 +		return DOMAIN_EXTRA_UTIL;
 11.1044 +	return DOMAIN_EDF;
 11.1045 +}
 11.1046 +/*Compares two domains in the relation of whether the one is allowed to
 11.1047 +  interrupt the others execution.
 11.1048 +  It returns true (!=0) if a switch to the other domain is good.
 11.1049 +  Current Priority scheme is as follows:
 11.1050 +  	EDF > L0 (penalty based) extra-time > 
 11.1051 +  	L1 (utilization) extra-time > idle-domain
 11.1052 +  In the same class priorities are assigned as following:
 11.1053 +  	EDF: early deadline > late deadline
 11.1054 +  	L0 extra-time: lower score > higher score*/
 11.1055 +static inline int should_switch(struct domain* cur, struct domain* other,
 11.1056 +    s_time_t now) {
 11.1057 +	struct sedf_dom_info *cur_inf, *other_inf;
 11.1058 +	cur_inf   = DOM_INFO(cur);
 11.1059 +	other_inf = DOM_INFO(other);
 11.1060 +	
 11.1061 +	/*check whether we need to make an earlier sched-decision*/
 11.1062 +	if ((PERIOD_BEGIN(other_inf) < 
 11.1063 +	     schedule_data[other->processor].s_timer.expires))
 11.1064 +		return 1;
 11.1065 +	/*no timing-based switches need to be taken into account here*/
 11.1066 +	switch (get_run_type(cur)) {
 11.1067 +		case DOMAIN_EDF:
 11.1068 +			/* do not interrupt a running EDF domain */ 
 11.1069 +			return 0;
 11.1070 +		case DOMAIN_EXTRA_PEN:
 11.1071 +			/*check whether we also want 
 11.1072 +			  the L0 ex-q with lower score*/
 11.1073 +			if ((other_inf->extra & EXTRA_WANT_PEN_Q)
 11.1074 +			&&  (other_inf->score[EXTRA_PEN_Q] < 
 11.1075 +			     cur_inf->score[EXTRA_PEN_Q]))
 11.1076 +				return 1;
 11.1077 +			else	return 0;
 11.1078 +		case DOMAIN_EXTRA_UTIL:
 11.1079 +			/*check whether we want the L0 extraq, don't
 11.1080 +			  switch if both domains want L1 extraq */
 11.1081 +			if (other_inf->extra & EXTRA_WANT_PEN_Q)
 11.1082 +				return 1;
 11.1083 +			else	return 0;
 11.1084 +		case DOMAIN_IDLE:
 11.1085 +			return 1;
 11.1086 +	}
 11.1087 +}
 11.1088 +void sedf_wake(struct domain *d) {
 11.1089 +	s_time_t              now = NOW();
 11.1090 +	struct sedf_dom_info* inf = DOM_INFO(d);
 11.1091 +	
 11.1092 +	PRINT(3,"sedf_wake was called, domain-id %i\n",d->id);
 11.1093 +	
 11.1094 +	if (unlikely(is_idle_task(d)))
 11.1095 +		return;
 11.1096 +	
 11.1097 +	if ( unlikely(__task_on_queue(d)) ) {
 11.1098 +		PRINT(3,"\tdomain %i is already in some queue\n",d->id);
 11.1099 +		return;
 11.1100 +	}
 11.1101 +	if ( unlikely(extraq_on(d,EXTRA_UTIL_Q) || extraq_on(d,EXTRA_PEN_Q)) ) {
 11.1102 +		PRINT(3,"\tdomain %i is already in the extraQ\n",d->id);
 11.1103 +	}
 11.1104 +	if (unlikely(inf->absdead == 0))
 11.1105 +		/*initial setup of the deadline*/
 11.1106 +		inf->absdead = now + inf->slice;
 11.1107 +		
 11.1108 +	PRINT(3,"waking up domain %i (deadl= %llu period= %llu "\
 11.1109 +	        "now= %llu)\n",d->id,inf->absdead,inf->period,now);
 11.1110 +#ifdef SEDF_STATS	
 11.1111 +	inf->block_tot++;
 11.1112 +#endif
 11.1113 +	if (unlikely(now< PERIOD_BEGIN(inf))) {
 11.1114 +		PRINT(4,"extratime unblock\n");
 11.1115 +		/*this might happen, imagine unblocking in extra-time!*/
 11.1116 +		#if (EXTRA == EXTRA_BLOCK_WEIGHT)
 11.1117 +		if (inf->extra & EXTRA_WANT_PEN_Q) {
 11.1118 +			/*we have a domain that wants compensation
 11.1119 +			  for block penalty and did just block in
 11.1120 +			  its compensation time. Give it another
 11.1121 +			  chance!*/
 11.1122 +			extraq_add_sort_update(d, EXTRA_PEN_Q, 0);
 11.1123 +		}
 11.1124 +		#endif
 11.1125 +		if (inf->extra & EXTRA_AWARE) 
 11.1126 +		#if (EXTRA == EXTRA_ROUNDR)
 11.1127 +			extraq_add_tail(d,EXTRA_UTIL_Q);
 11.1128 +			#elif (EXTRA == EXTRA_SLICE_WEIGHT \
 11.1129 +			    || EXTRA == EXTRA_BLOCK_WEIGHT)
 11.1130 +			/*put in on the weighted extraq, 
 11.1131 +			  without updating any scores*/
 11.1132 +			extraq_add_sort_update(d, EXTRA_UTIL_Q, 0);
 11.1133 +		#else
 11.1134 +			;
 11.1135 +		#endif
 11.1136 +		/*else*/
 11.1137 +		/*This is very very unlikely, ie. might even be an error?!*/
 11.1138 +	}		
 11.1139 +	else {		
 11.1140 +		if (now < inf->absdead) {
 11.1141 +			PRINT(4,"short unblocking\n");
 11.1142 +			/*short blocking*/
 11.1143 +#ifdef SEDF_STATS
 11.1144 +			inf->short_block_tot++;
 11.1145 +#endif
 11.1146 +			#if (UNBLOCK <= UNBLOCK_ATROPOS)
 11.1147 +			unblock_short_vcons(inf, now);
 11.1148 +			#elif (UNBLOCK == UNBLOCK_SHORT_RESUME)
 11.1149 +			unblock_short_cons(inf, now);
 11.1150 +			#elif (UNBLOCK == UNBLOCK_BURST)
 11.1151 +			unblock_short_burst(inf, now);
 11.1152 +			#elif (UNBLOCK == UNBLOCK_EXTRA_SUPPORT)
 11.1153 +			unblock_short_extra_support(inf, now);
 11.1154 +			#endif
 11.1155 +
 11.1156 +			if (inf->extra & EXTRA_AWARE)
 11.1157 +				#if (EXTRA == EXTRA_OFF)
 11.1158 +				;
 11.1159 +				#elif (EXTRA == EXTRA_ROUNDR)
 11.1160 +				/*Favour domains which got short unblocked*/
 11.1161 +				extraq_add_head(d, EXTRA_UTIL_Q);
 11.1162 +				#elif (EXTRA == EXTRA_SLICE_WEIGHT \
 11.1163 +				    || EXTRA == EXTRA_BLOCK_WEIGHT)
 11.1164 +				extraq_add_sort_update(d, EXTRA_UTIL_Q, 0);
 11.1165 +				#endif
 11.1166 +		}
 11.1167 +		else {
 11.1168 +			PRINT(4,"long unblocking\n");
 11.1169 +			/*long unblocking*/
 11.1170 +#ifdef SEDF_STATS
 11.1171 +			inf->long_block_tot++;
 11.1172 +#endif
 11.1173 +			#if (UNBLOCK == UNBLOCK_ISOCHRONOUS_EDF)
 11.1174 +			unblock_long_vcons(inf, now);
 11.1175 +			#elif (UNBLOCK == UNBLOCK_EDF \
 11.1176 +			    || UNBLOCK == UNBLOCK_EXTRA_SUPPORT)
 11.1177 +			unblock_long_cons_b(inf, now);
 11.1178 +			#elif (UNBLOCK == UNBLOCK_ATROPOS)
 11.1179 +			unblock_long_cons_c(inf, now);
 11.1180 +			#elif (UNBLOCK == UNBLOCK_SHORT_RESUME)
 11.1181 +			unblock_long_cons_b(inf, now);
 11.1182 +			/*unblock_short_cons_c(inf, now);*/
 11.1183 +			#elif (UNBLOCK == UNBLOCK_BURST)
 11.1184 +			unblock_long_burst(inf, now);
 11.1185 +			#endif
 11.1186 +			
 11.1187 +			if (inf->extra & EXTRA_AWARE) {
 11.1188 +				#if (EXTRA == EXTRA_OFF)
 11.1189 +				;
 11.1190 +				#elif (EXTRA == EXTRA_ROUNDR)
 11.1191 +				extraq_add_head(d, EXTRA_UTIL_Q);
 11.1192 +				#elif (EXTRA == EXTRA_SLICE_WEIGHT \
 11.1193 +				    || EXTRA == EXTRA_BLOCK_WEIGHT)
 11.1194 +				extraq_add_sort_update(d, EXTRA_UTIL_Q, 0);
 11.1195 +				#endif
 11.1196 +			}
 11.1197 +			
 11.1198 +		}
 11.1199 +	}
 11.1200 +	PRINT(3,"woke up domain %i (deadl= %llu period= %llu "\
 11.1201 +	        "now= %llu)\n",d->id,inf->absdead,inf->period,now);
 11.1202 +	__add_to_waitqueue_sort(d);
 11.1203 +	PRINT(3,"added to waitq\n");	
 11.1204 +	
 11.1205 +#ifdef SEDF_STATS
 11.1206 +	/*do some statistics here...*/
 11.1207 +	if (inf->absblock != 0) {
 11.1208 +		inf->block_time_tot += now - inf->absblock;
 11.1209 +		inf->penalty_time_tot +=
 11.1210 +		   PERIOD_BEGIN(inf) + inf->cputime - inf->absblock;
 11.1211 +	}
 11.1212 +#endif
 11.1213 +	/*sanity check: make sure each extra-aware domain IS on the util-q!*/
 11.1214 +	/*if (inf->extra & EXTRA_AWARE) {
 11.1215 +		if (!extraq_on(d, EXTRA_UTIL_Q))
 11.1216 +			printf("sedf_wake: domain %i is extra-aware, "\
 11.1217 +			       "but NOT on L1 extraq!\n",d->id);
 11.1218 +	}*/
 11.1219 +	
 11.1220 +	/*check whether the awakened task needs to invoke the do_schedule
 11.1221 +	  routine. Try to avoid unnecessary runs but:
 11.1222 +	  Save approximation: Always switch to scheduler!*/
 11.1223 +	if (should_switch(schedule_data[d->processor].curr, d, now)){
 11.1224 +#ifdef ADV_SCHED_HISTO
 11.1225 +		adv_sched_hist_start(d->processor);
 11.1226 +#endif
 11.1227 +		cpu_raise_softirq(d->processor, SCHEDULE_SOFTIRQ);
 11.1228 +	}
 11.1229 +}
 11.1230 +
 11.1231 +/*Print a lot of use-{full, less} information about a domains in the system*/
 11.1232 +static void sedf_dump_domain(struct domain *d) {
 11.1233 +	printk("%u has=%c ", d->id,
 11.1234 +		test_bit(DF_RUNNING, &d->flags) ? 'T':'F');
 11.1235 +	printk("p=%llu sl=%llu ddl=%llu w=%hu c=%llu sc=%i xtr(%s)=%llu",
 11.1236 +	  DOM_INFO(d)->period, DOM_INFO(d)->slice, DOM_INFO(d)->absdead,
 11.1237 +	  DOM_INFO(d)->weight, d->cpu_time, DOM_INFO(d)->score[EXTRA_UTIL_Q],
 11.1238 +	 (DOM_INFO(d)->extra & EXTRA_AWARE) ? "yes" : "no",
 11.1239 +	  DOM_INFO(d)->extra_time_tot);
 11.1240 +	if (d->cpu_time !=0)
 11.1241 +		printf(" (%lu%)", (DOM_INFO(d)->extra_time_tot * 100)
 11.1242 +		                 / d->cpu_time);
 11.1243 +#ifdef SEDF_STATS
 11.1244 +	if (DOM_INFO(d)->block_time_tot!=0)
 11.1245 +		printf(" pen=%lu%", (DOM_INFO(d)->penalty_time_tot * 100) /
 11.1246 +		                     DOM_INFO(d)->block_time_tot);
 11.1247 +	if (DOM_INFO(d)->block_tot!=0)
 11.1248 +		printf("\n   blks=%lu sh=%lu (%lu%) (shc=%lu (%lu%) shex=%i "\
 11.1249 +		       "shexsl=%i) l=%lu (%lu%) avg: b=%llu p=%llu",
 11.1250 +		    DOM_INFO(d)->block_tot, DOM_INFO(d)->short_block_tot,
 11.1251 +		   (DOM_INFO(d)->short_block_tot * 100) 
 11.1252 +		  / DOM_INFO(d)->block_tot, DOM_INFO(d)->short_cont,
 11.1253 +		   (DOM_INFO(d)->short_cont * 100) / DOM_INFO(d)->block_tot,
 11.1254 +		    DOM_INFO(d)->pen_extra_blocks,
 11.1255 +		    DOM_INFO(d)->pen_extra_slices,
 11.1256 +		    DOM_INFO(d)->long_block_tot,
 11.1257 +		   (DOM_INFO(d)->long_block_tot * 100) / DOM_INFO(d)->block_tot,
 11.1258 +		   (DOM_INFO(d)->block_time_tot) / DOM_INFO(d)->block_tot,
 11.1259 +		   (DOM_INFO(d)->penalty_time_tot) / DOM_INFO(d)->block_tot);
 11.1260 +#endif
 11.1261 +	printf("\n");
 11.1262 +}
 11.1263 +
 11.1264 +/*dumps all domains on hte specified cpu*/
 11.1265 +static void sedf_dump_cpu_state(int i)
 11.1266 +{
 11.1267 +	struct list_head *list, *queue, *tmp;
 11.1268 +	int loop = 0;
 11.1269 +	struct sedf_dom_info *d_inf;
 11.1270 +	struct domain* d;
 11.1271 +	
 11.1272 +	printk("now=%llu\n",NOW());
 11.1273 +	queue = RUNQ(i);
 11.1274 +	printk("RUNQ rq %lx   n: %lx, p: %lx\n",  (unsigned long)queue,
 11.1275 +		(unsigned long) queue->next, (unsigned long) queue->prev);
 11.1276 +	list_for_each_safe ( list, tmp, queue ) {
 11.1277 +		printk("%3d: ",loop++);
 11.1278 +		d_inf = list_entry(list, struct sedf_dom_info, list);
 11.1279 +		sedf_dump_domain(d_inf->owner);
 11.1280 +	}
 11.1281 +	
 11.1282 +	queue = WAITQ(i); loop = 0;
 11.1283 +	printk("\nWAITQ rq %lx   n: %lx, p: %lx\n",  (unsigned long)queue,
 11.1284 +		(unsigned long) queue->next, (unsigned long) queue->prev);
 11.1285 +	list_for_each_safe ( list, tmp, queue ) {
 11.1286 +		printk("%3d: ",loop++);
 11.1287 +		d_inf = list_entry(list, struct sedf_dom_info, list);
 11.1288 +		sedf_dump_domain(d_inf->owner);
 11.1289 +	}
 11.1290 +	
 11.1291 +	queue = EXTRAQ(i,EXTRA_PEN_Q); loop = 0;
 11.1292 +	printk("\nEXTRAQ (penalty) rq %lx   n: %lx, p: %lx\n",
 11.1293 +	       (unsigned long)queue, (unsigned long) queue->next,
 11.1294 +	       (unsigned long) queue->prev);
 11.1295 +	list_for_each_safe ( list, tmp, queue ) {
 11.1296 +		d_inf = list_entry(list, struct sedf_dom_info,
 11.1297 +		                   extralist[EXTRA_PEN_Q]);
 11.1298 +		printk("%3d: ",loop++);
 11.1299 +		sedf_dump_domain(d_inf->owner);
 11.1300 +	}
 11.1301 +	
 11.1302 +	queue = EXTRAQ(i,EXTRA_UTIL_Q); loop = 0;
 11.1303 +	printk("\nEXTRAQ (utilization) rq %lx   n: %lx, p: %lx\n",
 11.1304 +	       (unsigned long)queue, (unsigned long) queue->next,
 11.1305 +	       (unsigned long) queue->prev);
 11.1306 +	list_for_each_safe ( list, tmp, queue )	{
 11.1307 +		d_inf = list_entry(list, struct sedf_dom_info,
 11.1308 +		                   extralist[EXTRA_UTIL_Q]);
 11.1309 +		printk("%3d: ",loop++);
 11.1310 +		sedf_dump_domain(d_inf->owner);
 11.1311 +	}
 11.1312 +	
 11.1313 +	loop = 0;
 11.1314 +	printk("\nnot on Q\n");
 11.1315 +	for_each_domain(d) {
 11.1316 +		if (!__task_on_queue(d) && (d->processor == i)) {
 11.1317 +			printk("%3d: ",loop++);
 11.1318 +			sedf_dump_domain(d);
 11.1319 +		}
 11.1320 +	}
 11.1321 +}
 11.1322 +/*Adjusts periods and slices of the domains accordingly to their weights*/
 11.1323 +static inline int sedf_adjust_weights(struct domain *p, 
 11.1324 +struct sched_adjdom_cmd *cmd) {
 11.1325 +	int sumw[NR_CPUS];
 11.1326 +	s_time_t sumt[NR_CPUS];
 11.1327 +	int cpu;
 11.1328 +	
 11.1329 +	for (cpu=0; cpu < NR_CPUS; cpu++) {
 11.1330 +		sumw[cpu] = 0;
 11.1331 +		sumt[cpu] = 0;
 11.1332 +	}
 11.1333 +	/*sum up all weights*/
 11.1334 +	for_each_domain(p) {
 11.1335 +		if (DOM_INFO(p)->weight)
 11.1336 +			sumw[p->processor] += DOM_INFO(p)->weight;
 11.1337 +		else {
 11.1338 +			/*don't modify domains who don't have a weight, but sum
 11.1339 +			  up the time they need, projected to a WEIGHT_PERIOD,
 11.1340 +			  so that this time is not given to the weight-driven
 11.1341 +			  domains*/
 11.1342 +			/*check for overflows*/
 11.1343 +			ASSERT((WEIGHT_PERIOD < ULONG_MAX) 
 11.1344 +			    && (DOM_INFO(p)->slice_orig < ULONG_MAX));
 11.1345 +			sumt[p->processor] += (WEIGHT_PERIOD *
 11.1346 +			    DOM_INFO(p)->slice_orig) / DOM_INFO(p)->period_orig;
 11.1347 +		}
 11.1348 +	}
 11.1349 +	/*adjust all slices (and periods) to the new weight*/
 11.1350 +	for_each_domain(p) {
 11.1351 +		if (DOM_INFO(p)->weight) {
 11.1352 +			DOM_INFO(p)->period_orig = 
 11.1353 +			     DOM_INFO(p)->period = WEIGHT_PERIOD;
 11.1354 +			DOM_INFO(p)->slice_orig  =
 11.1355 +			      DOM_INFO(p)->slice = (DOM_INFO(p)->weight *
 11.1356 +			      (WEIGHT_PERIOD -WEIGHT_SAFETY -
 11.1357 +			       sumt[p->processor])) / sumw[p->processor];
 11.1358 +		}
 11.1359 +	}
 11.1360 +	return 0;
 11.1361 +}
 11.1362 +
 11.1363 +/* set or fetch domain scheduling parameters */
 11.1364 +static int sedf_adjdom(struct domain *p, struct sched_adjdom_cmd *cmd) {
 11.1365 +	PRINT(2,"sedf_adjdom was called, domain-id %i new period %llu "\
 11.1366 +	        "new slice %llu\nlatency %llu extra:%s\n",
 11.1367 +		p->id, cmd->u.sedf.period, cmd->u.sedf.slice,
 11.1368 +		cmd->u.sedf.latency, (cmd->u.sedf.extratime)?"yes":"no");
 11.1369 +	if ( cmd->direction == SCHED_INFO_PUT )
 11.1370 +	{
 11.1371 +		/*check for sane parameters*/
 11.1372 +		if (!cmd->u.sedf.period && !cmd->u.sedf.weight)
 11.1373 +			return -EINVAL;
 11.1374 +		/*weight driven domains*/
 11.1375 +		if (cmd->u.sedf.weight) {
 11.1376 +			DOM_INFO(p)->weight = cmd->u.sedf.weight;
 11.1377 +		}
 11.1378 +		else {
 11.1379 +			/*time driven domains*/
 11.1380 +			DOM_INFO(p)->weight = 0;
 11.1381 +			/* sanity checking! */
 11.1382 +			if(cmd->u.sedf.slice > cmd->u.sedf.period )
 11.1383 +				return -EINVAL;
 11.1384 +			DOM_INFO(p)->period_orig = 
 11.1385 +			   DOM_INFO(p)->period   = cmd->u.sedf.period;
 11.1386 +			DOM_INFO(p)->slice_orig  = 
 11.1387 +			   DOM_INFO(p)->slice    = cmd->u.sedf.slice;
 11.1388 +		}
 11.1389 +		if (sedf_adjust_weights(p,cmd))
 11.1390 +			return -EINVAL;
 11.1391 +		DOM_INFO(p)->extra       = (DOM_INFO(p)-> extra & ~EXTRA_AWARE)
 11.1392 +		    | (cmd->u.sedf.extratime & EXTRA_AWARE);
 11.1393 +		DOM_INFO(p)->latency     = cmd->u.sedf.latency;
 11.1394 +		extraq_check(p);
 11.1395 +	}
 11.1396 +	else if ( cmd->direction == SCHED_INFO_GET )
 11.1397 +	{
 11.1398 +		cmd->u.sedf.period    = DOM_INFO(p)->period;
 11.1399 +		cmd->u.sedf.slice     = DOM_INFO(p)->slice;
 11.1400 +		cmd->u.sedf.extratime = DOM_INFO(p)->extra & EXTRA_AWARE;
 11.1401 +		cmd->u.sedf.latency   = DOM_INFO(p)->latency;
 11.1402 +		cmd->u.sedf.weight    = DOM_INFO(p)->weight;
 11.1403 +	}
 11.1404 +	PRINT(2,"sedf_adjdom_finished\n");
 11.1405 +	return 0;
 11.1406 +}
 11.1407 +
 11.1408 +struct scheduler sched_sedf_def = {
 11.1409 +    .name     = "Simple EDF Scheduler",
 11.1410 +    .opt_name = "sedf",
 11.1411 +    .sched_id = SCHED_SEDF,
 11.1412 +    
 11.1413 +    .init_idle_task = sedf_init_idle_task,
 11.1414 +    .alloc_task     = sedf_alloc_task,
 11.1415 +    .add_task       = sedf_add_task,
 11.1416 +    .free_task      = sedf_free_task,
 11.1417 +    .init_scheduler = sedf_init_scheduler,
 11.1418 +    .do_schedule    = sedf_do_schedule,
 11.1419 +    .dump_cpu_state = sedf_dump_cpu_state,
 11.1420 +    .sleep          = sedf_sleep,
 11.1421 +    .wake           = sedf_wake,
 11.1422 +    .adjdom         = sedf_adjdom,
 11.1423 +};

    12.1 --- a/xen/common/schedule.c	Wed Apr 20 21:22:46 2005 +0000
    12.2 +++ b/xen/common/schedule.c	Thu Apr 21 01:42:29 2005 +0000
    12.3 @@ -40,6 +40,17 @@
    12.4  static char opt_sched[10] = "bvt";
    12.5  string_param("sched", opt_sched);
    12.6  
    12.7 +/*#define WAKE_HISTO*/
    12.8 +/*#define BLOCKTIME_HISTO*/
    12.9 +/*#define ADV_SCHED_HISTO*/
   12.10 +//#include <xen/adv_sched_hist.h>
   12.11 +
   12.12 +#if defined(WAKE_HISTO)
   12.13 +#define BUCKETS 31
   12.14 +#elif defined(BLOCKTIME_HISTO)
   12.15 +#define BUCKETS 200
   12.16 +#endif
   12.17 +
   12.18  #define TIME_SLOP      (s32)MICROSECS(50)     /* allow time to slip a bit */
   12.19  
   12.20  /* Various timer handlers. */
   12.21 @@ -51,8 +62,10 @@ static void dom_timer_fn(unsigned long d
   12.22  struct schedule_data schedule_data[NR_CPUS];
   12.23  
   12.24  extern struct scheduler sched_bvt_def;
   12.25 +extern struct scheduler sched_sedf_def;
   12.26  static struct scheduler *schedulers[] = { 
   12.27      &sched_bvt_def,
   12.28 +    &sched_sedf_def,
   12.29      NULL
   12.30  };
   12.31  
   12.32 @@ -223,6 +236,10 @@ long do_block(void)
   12.33  {
   12.34      struct exec_domain *ed = current;
   12.35  
   12.36 +#ifdef ADV_SCHED_HISTO
   12.37 +    adv_sched_hist_start(current->processor);
   12.38 +#endif
   12.39 +
   12.40      ed->vcpu_info->evtchn_upcall_mask = 0;
   12.41      set_bit(EDF_BLOCKED, &ed->ed_flags);
   12.42  
   12.43 @@ -241,6 +258,10 @@ long do_block(void)
   12.44  /* Voluntarily yield the processor for this allocation. */
   12.45  static long do_yield(void)
   12.46  {
   12.47 +#ifdef ADV_SCHED_HISTO
   12.48 +    adv_sched_hist_start(current->processor);
   12.49 +#endif
   12.50 +    
   12.51      TRACE_2D(TRC_SCHED_YIELD, current->domain->id, current->eid);
   12.52      __enter_scheduler();
   12.53      return 0;
   12.54 @@ -320,7 +341,7 @@ long sched_adjdom(struct sched_adjdom_cm
   12.55  
   12.56      if ( cmd->sched_id != ops.sched_id )
   12.57          return -EINVAL;
   12.58 -
   12.59 +    
   12.60      if ( cmd->direction != SCHED_INFO_PUT && cmd->direction != SCHED_INFO_GET )
   12.61          return -EINVAL;
   12.62  
   12.63 @@ -353,8 +374,14 @@ static void __enter_scheduler(void)
   12.64      perfc_incrc(sched_run);
   12.65      
   12.66      spin_lock_irq(&schedule_data[cpu].schedule_lock);
   12.67 - 
   12.68 +
   12.69 +#ifdef ADV_SCHED_HISTO
   12.70 +    adv_sched_hist_from_stop(cpu);
   12.71 +#endif
   12.72      now = NOW();
   12.73 +#ifdef ADV_SCHED_HISTO
   12.74 +    adv_sched_hist_start(cpu);
   12.75 +#endif
   12.76  
   12.77      rem_ac_timer(&schedule_data[cpu].s_timer);
   12.78      
   12.79 @@ -381,9 +408,12 @@ static void __enter_scheduler(void)
   12.80  
   12.81      spin_unlock_irq(&schedule_data[cpu].schedule_lock);
   12.82  
   12.83 -    if ( unlikely(prev == next) )
   12.84 +    if ( unlikely(prev == next) ) {
   12.85 +#ifdef ADV_SCHED_HISTO
   12.86 +        adv_sched_hist_to_stop(cpu);
   12.87 +#endif
   12.88          return;
   12.89 -    
   12.90 +    }
   12.91      perfc_incrc(sched_ctx);
   12.92  
   12.93  #if defined(WAKE_HISTO)
   12.94 @@ -418,6 +448,10 @@ static void __enter_scheduler(void)
   12.95               prev->domain->id, prev->eid,
   12.96               next->domain->id, next->eid);
   12.97  
   12.98 +#ifdef ADV_SCHED_HISTO
   12.99 +    adv_sched_hist_to_stop(cpu);
  12.100 +#endif
  12.101 +
  12.102      context_switch(prev, next);
  12.103  }
  12.104  
  12.105 @@ -439,6 +473,10 @@ int idle_cpu(int cpu)
  12.106  /* The scheduler timer: force a run through the scheduler */
  12.107  static void s_timer_fn(unsigned long unused)
  12.108  {
  12.109 +#ifdef ADV_SCHED_HISTO
  12.110 +    adv_sched_hist_start(current->processor);
  12.111 +#endif
  12.112 +
  12.113      raise_softirq(SCHEDULE_SOFTIRQ);
  12.114      perfc_incrc(sched_irq);
  12.115  }
  12.116 @@ -582,9 +620,66 @@ void reset_sched_histo(unsigned char key
  12.117              schedule_data[j].hist[i] = 0;
  12.118  }
  12.119  #else
  12.120 +#if defined(ADV_SCHED_HISTO)
  12.121 +void print_sched_histo(unsigned char key)
  12.122 +{
  12.123 +    int i, j, k,t;
  12.124 +    printf("Hello!\n");
  12.125 +    for ( k = 0; k < smp_num_cpus; k++ )
  12.126 +    {
  12.127 +        j = 0;
  12.128 +	t = 0;
  12.129 +        printf ("CPU[%02d]: scheduler latency histogram FROM (ms:[count])\n", k);
  12.130 +        for ( i = 0; i < BUCKETS; i++ )
  12.131 +        {
  12.132 +            //if ( schedule_data[k].hist[i] != 0 )
  12.133 +            {
  12.134 +	        t += schedule_data[k].from_hist[i];
  12.135 +                if ( i < BUCKETS-1 )
  12.136 +                    printk("%3d:[%7u]    ", i, schedule_data[k].from_hist[i]);
  12.137 +                else
  12.138 +                    printk(" >:[%7u]    ", schedule_data[k].from_hist[i]);
  12.139 +                //if ( !(++j % 5) )
  12.140 +                    printk("\n");
  12.141 +            }
  12.142 +        }
  12.143 +        printk("\nTotal: %i\n",t);
  12.144 +    }
  12.145 +    for ( k = 0; k < smp_num_cpus; k++ )
  12.146 +    {
  12.147 +        j = 0; t = 0;
  12.148 +        printf ("CPU[%02d]: scheduler latency histogram TO (ms:[count])\n", k);
  12.149 +        for ( i = 0; i < BUCKETS; i++ )
  12.150 +        {
  12.151 +            //if ( schedule_data[k].hist[i] != 0 )
  12.152 +            {
  12.153 +	    	t += schedule_data[k].from_hist[i];
  12.154 +                if ( i < BUCKETS-1 )
  12.155 +                    printk("%3d:[%7u]    ", i, schedule_data[k].to_hist[i]);
  12.156 +                else
  12.157 +                    printk(" >:[%7u]    ", schedule_data[k].to_hist[i]);
  12.158 +                //if ( !(++j % 5) )
  12.159 +                    printk("\n");
  12.160 +            }
  12.161 +        }
  12.162 +	printk("\nTotal: %i\n",t);
  12.163 +    }
  12.164 +      
  12.165 +}
  12.166 +void reset_sched_histo(unsigned char key)
  12.167 +{
  12.168 +    int i, j;
  12.169 +    for ( j = 0; j < smp_num_cpus; j++ ) {
  12.170 +        for ( i=0; i < BUCKETS; i++ ) 
  12.171 +            schedule_data[j].to_hist[i] = schedule_data[j].from_hist[i] = 0;
  12.172 +        schedule_data[j].save_tsc = 0;
  12.173 +    }
  12.174 +}
  12.175 +#else
  12.176  void print_sched_histo(unsigned char key) { }
  12.177  void reset_sched_histo(unsigned char key) { }
  12.178  #endif
  12.179 +#endif
  12.180  
  12.181  /*
  12.182   * Local variables:

    13.1 --- a/xen/include/public/sched_ctl.h	Wed Apr 20 21:22:46 2005 +0000
    13.2 +++ b/xen/include/public/sched_ctl.h	Thu Apr 21 01:42:29 2005 +0000
    13.3 @@ -9,6 +9,7 @@
    13.4  
    13.5  /* Scheduler types. */
    13.6  #define SCHED_BVT      0
    13.7 +#define SCHED_SEDF     4
    13.8  
    13.9  /* Set or get info? */
   13.10  #define SCHED_INFO_PUT 0
   13.11 @@ -31,18 +32,31 @@ struct sched_ctl_cmd
   13.12  
   13.13  struct sched_adjdom_cmd
   13.14  {
   13.15 -    u32     sched_id;
   13.16 -    u32     direction;
   13.17 -    domid_t domain;
   13.18 -    union {
   13.19 -        struct bvt_adjdom {
   13.20 -            u32 mcu_adv;            /* mcu advance: inverse of weight */
   13.21 -            u32 warpback;           /* warp? */
   13.22 -            s32 warpvalue;          /* warp value */
   13.23 -            long long warpl;        /* warp limit */
   13.24 -            long long warpu;        /* unwarp time requirement */
   13.25 -        } bvt;
   13.26 -    } u;
   13.27 -};
   13.28 +    u32     sched_id;                 /*  0 */
   13.29 +    u32     direction;                /*  4 */
   13.30 +    domid_t domain;                   /*  8 */
   13.31 +    u16     __pad0;
   13.32 +    u32     __pad1;
   13.33 +    union {                           /* 16 */
   13.34 +        struct bvt_adjdom
   13.35 +        {
   13.36 +            u32 mcu_adv;            /* 16: mcu advance: inverse of weight */
   13.37 +            u32 warpback;           /* 20: warp? */
   13.38 +            s32 warpvalue;          /* 24: warp value */
   13.39 +            long long warpl;        /* 32: warp limit */
   13.40 +            long long warpu;        /* 40: unwarp time requirement */
   13.41 +        } PACKED bvt;
   13.42 +        
   13.43 +	struct sedf_adjdom
   13.44 +        {
   13.45 +            u64 period;     /* 16 */
   13.46 +            u64 slice;      /* 24 */
   13.47 +            u64 latency;    /* 32 */
   13.48 +            u16 extratime;  /* 36 */
   13.49 +	    u16 weight;     /* 38 */
   13.50 +        } PACKED sedf;
   13.51 +
   13.52 +    } PACKED u;
   13.53 +} PACKED; /* 40 bytes */
   13.54  
   13.55  #endif /* __XEN_PUBLIC_SCHED_CTL_H__ */

    14.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    14.2 +++ b/xen/include/xen/adv_sched_hist.h	Thu Apr 21 01:42:29 2005 +0000
    14.3 @@ -0,0 +1,40 @@
    14.4 +/* Some functions to suport advanced scheduler histograms
    14.5 +   Author: Stephan.Diestelhorst@cl.cam.ac.uk */
    14.6 +//#include <xen/sched.h>
    14.7 +//#include <xen/sched-if.h>
    14.8 +#include <asm/msr.h>
    14.9 +#define ADV_SCHED_HISTO
   14.10 +static inline void adv_sched_hist_start(int cpu) {
   14.11 +	u64 now;
   14.12 +	rdtscll(now);
   14.13 +	if (!schedule_data[cpu].save_tsc)
   14.14 +		schedule_data[cpu].save_tsc = now;
   14.15 +}
   14.16 +static inline void adv_sched_hist_from_stop(int cpu) {
   14.17 +	u64 now;
   14.18 +	rdtscll(now);
   14.19 +	if (schedule_data[cpu].save_tsc) {
   14.20 +		now -= schedule_data[cpu].save_tsc;
   14.21 +		now /= 7;
   14.22 +		if (now < BUCKETS-1)
   14.23 +			schedule_data[cpu].from_hist[now]++;
   14.24 +		else
   14.25 +			schedule_data[cpu].from_hist[BUCKETS-1]++;
   14.26 +
   14.27 +		schedule_data[cpu].save_tsc = 0;
   14.28 +	}
   14.29 +}
   14.30 +static inline void adv_sched_hist_to_stop(int cpu) {
   14.31 +	u64 now;
   14.32 +	rdtscll(now);
   14.33 +	if (schedule_data[cpu].save_tsc) {
   14.34 +		now -= schedule_data[cpu].save_tsc;
   14.35 +		now /= 24;
   14.36 +		if (now < BUCKETS-1)
   14.37 +			schedule_data[cpu].to_hist[now]++;
   14.38 +		else
   14.39 +			schedule_data[cpu].to_hist[BUCKETS-1]++;
   14.40 +
   14.41 +		schedule_data[cpu].save_tsc = 0;
   14.42 +	}
   14.43 +}

    15.1 --- a/xen/include/xen/sched-if.h	Wed Apr 20 21:22:46 2005 +0000
    15.2 +++ b/xen/include/xen/sched-if.h	Thu Apr 21 01:42:29 2005 +0000
    15.3 @@ -8,6 +8,10 @@
    15.4  #ifndef __XEN_SCHED_IF_H__
    15.5  #define __XEN_SCHED_IF_H__
    15.6  
    15.7 +//#define ADV_SCHED_HISTO
    15.8 +#define BUCKETS  10
    15.9 +/*300*/
   15.10 +
   15.11  struct schedule_data {
   15.12      spinlock_t          schedule_lock;  /* spinlock protecting curr        */
   15.13      struct exec_domain *curr;           /* current task                    */
   15.14 @@ -15,6 +19,11 @@ struct schedule_data {
   15.15      void               *sched_priv;
   15.16      struct ac_timer     s_timer;        /* scheduling timer                */
   15.17      unsigned long       tick;           /* current periodic 'tick'         */
   15.18 +#ifdef ADV_SCHED_HISTO
   15.19 +    u32			to_hist[BUCKETS];
   15.20 +    u32			from_hist[BUCKETS];
   15.21 +    u64			save_tsc;
   15.22 +#endif
   15.23  #ifdef BUCKETS
   15.24      u32                 hist[BUCKETS];  /* for scheduler latency histogram */
   15.25  #endif