Subversion Repositories shark

/*

 * Project: S.Ha.R.K.

 *

 * Coordinators:

 *   Giorgio Buttazzo    <giorgio@sssup.it>

 *   Paolo Gai           <pj@gandalf.sssup.it>

 *

 * Authors     :

 *   Paolo Gai           <pj@gandalf.sssup.it>

 *   Massimiliano Giorgi <massy@gandalf.sssup.it>

 *   Luca Abeni          <luca@gandalf.sssup.it>

 *   (see the web pages for full authors list)

 *

 * ReTiS Lab (Scuola Superiore S.Anna - Pisa - Italy)

 *

 * http://www.sssup.it

 * http://retis.sssup.it

 * http://shark.sssup.it

 */

/*

 ------------

 CVS :        $Id: cbsstar.c,v 1.4 2003-01-07 17:10:16 pj Exp $

 File:        $File$

 Revision:    $Revision: 1.4 $

 Last update: $Date: 2003-01-07 17:10:16 $

 ------------

 Read CBSSTAR.h for general details.

 Basically, a budget can be in 2 states:

 - Active -> the budget queue is not empty

 - Idle   -> the budget queue is empty

 The fact that a task into a budget is inserted into the master module depends

 on the value of the remaining time the tasks can spend in the period.

 The module does handle only one oslib event, used to enforce the

 temporal isolation between buffers. Note that all is implemented

 without using the CONTROL_CAP field.

 Basically, for each budget there can be at most one task inserted

 into the master level. Its deadline is modified according to the

 usage of its capacity, that is, when a budget is exausted its

 deadline is postponed.

*/

/*

 * Copyright (C) 2002 Paolo Gai

 *

 * This program is free software; you can redistribute it and/or modify

 * it under the terms of the GNU General Public License as published by

 * the Free Software Foundation; either version 2 of the License, or

 * (at your option) any later version.

 *

 * This program is distributed in the hope that it will be useful,

 * but WITHOUT ANY WARRANTY; without even the implied warranty of

 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

 * GNU General Public License for more details.

 *

 * You should have received a copy of the GNU General Public License

 * along with this program; if not, write to the Free Software

 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

 *

 */

#include "cbsstar.h"

#include <ll/string.h>

/*

 * DEBUG stuffs begin

 */

//#define CBSSTAR_DEBUG

#ifdef CBSSTAR_DEBUG

static __inline__ void fake_printf(char *fmt, ...) {}

//#define cbsstar_printf kern_printf

//#define cbsstar_printf2 kern_printf

//#define cbsstar_printf3 kern_printf

#define cbsstar_printf fake_printf

#define cbsstar_printf2 fake_printf

#define cbsstar_printf3 fake_printf

#if 0

void cbsstar_printq(QQUEUE *q)

{

  PID p;

  kern_printf("[");

  p = q->first;

  kern_printf("->%d",p);

  while (p != NIL) {

    p = proc_table[p].next;

    kern_printf("->%d",p);

  }

  kern_printf("]");

}

#else

static __inline__ void cbsstar_printq(QQUEUE *q) {}

#endif

#if 0

static __inline__ void cbsstar_printblob(int x) { if (x) cputc('±'); else cputc('Û'); }

#else

static __inline__ void cbsstar_printblob(int x) {}

#endif

#endif

/*

 * DEBUG stuffs end

 */

/* this structure contains the status for a single budget */

struct budget_struct {

  TIME Q;                 /* budget */

  TIME T;                 /* period */

  struct timespec dline;  /* deadline */

  int dline_timer;        /* oslib event for budget reactivation*/

  int avail;              /* current budget */

  PID current;            /* the task currently put in execution */

  IQUEUE tasks;           /* a FIFO queue for the tasks handled

                             using the budget */

};

typedef struct {

  level_des l;               /* the standard level descriptor */

  struct budget_struct *b;   /* the budgets! */

  int n;                     /* the maximum index for the budgets */

  int freebudgets;           /* number of free budgets; starts from n */

  int tb[MAX_PROC];          /* link task->budget (used in guest_end) */

  bandwidth_t U;   /*+ the used bandwidth by the server       +*/

  LEVEL scheduling_level;

} CBSSTAR_level_des;

static void CBSSTAR_activation(CBSSTAR_level_des *lev,

                           PID p,

                           struct timespec *acttime)

{

  JOB_TASK_MODEL job;

  struct budget_struct *b = &lev->b[lev->tb[p]];

  /* we have to check if the deadline and the wcet are correct before

     activating a new task or an old task... */

  /* check 1: if the deadline is before than the actual scheduling time */

  /* check 2: if ( avail_time >= (cbs_dline - acttime)* (wcet/period) )

     (rule 7 in the CBS article!) */

  TIME t;

  struct timespec t2,t3;

  t = (b->T * b->avail) / b->Q;

  t3.tv_sec = t / 1000000;

  t3.tv_nsec = (t % 1000000) * 1000;

  SUBTIMESPEC(&b->dline, acttime, &t2);

  if (/* 1 */ TIMESPEC_A_LT_B(&b->dline, acttime) ||

      /* 2 */ TIMESPEC_A_GT_B(&t3, &t2) ) {

/*    if (TIMESPEC_A_LT_B(&lev->cbs_dline[p], acttime) )

      kern_printf("$");

    else

      kern_printf("(Ûdline%d.%d act%d.%d wcet%d per%d avail%dÛ)",

                  lev->cbs_dline[p].tv_sec,lev->cbs_dline[p].tv_nsec/1000,

                  acttime->tv_sec, acttime->tv_nsec/1000,

                  proc_table[p].wcet, lev->period[p], proc_table[p].avail_time);

*/  /* we modify the deadline ... */

    TIMESPEC_ASSIGN(&b->dline, acttime);

    ADDUSEC2TIMESPEC(b->T, &b->dline);

    /* and the capacity */

    b->avail = b->Q;

#ifdef CBSSTAR_DEBUG

    cbsstar_printf3("±%d±",lev->tb[p]);

    cbsstar_printblob(lev->tb[p]);

#endif

  }

  /* record the current task inserted in the master module */

  b->current = p;

#ifdef CBSSTAR_DEBUG

  cbsstar_printf("(C:iact p%d %ld.%ld av=%d)",p,b->dline.tv_sec,b->dline.tv_nsec/1000, b->avail);

#endif

  /* and, finally, we reinsert the task in the master level */

  job_task_default_model(job, b->dline);

  job_task_def_noexc(job);

  level_table[ lev->scheduling_level ]->

    private_insert(lev->scheduling_level, p, (TASK_MODEL *)&job);

}

static void CBSSTAR_account_capacity(CBSSTAR_level_des *lev, PID p)

{

  struct timespec ty;

  TIME tx;

  SUBTIMESPEC(&schedule_time, &cap_lasttime, &ty);

  tx = TIMESPEC2USEC(&ty);

  lev->b[lev->tb[p]].avail -= tx;

#ifdef CBSSTAR_DEBUG

  cbsstar_printf2("(C:cap p%d av=%d)", p, lev->b[lev->tb[p]].avail);

#endif

}

/* The on-line guarantee is enabled only if the appropriate flag is set... */

static int CBSSTAR_public_guarantee(LEVEL l, bandwidth_t *freebandwidth)

{

  CBSSTAR_level_des *lev = (CBSSTAR_level_des *)(level_table[l]);

#ifdef CBSSTAR_DEBUG

  cbsstar_printf("(C:gua)");

#endif

  if (*freebandwidth >= lev->U) {

    *freebandwidth -= lev->U;

    return 1;

  }

  else

    return 0;

}

static int CBSSTAR_private_eligible(LEVEL l, PID p)

{

  CBSSTAR_level_des *lev = (CBSSTAR_level_des *)(level_table[l]);

  struct budget_struct *b = &lev->b[lev->tb[p]];

  JOB_TASK_MODEL job;

#ifdef CBSSTAR_DEBUG

  cbsstar_printf("(C:eli %d",p);

#endif

  /* we have to check if the deadline and the wcet are correct...

     if the CBSSTAR level schedules in background with respect to others

     levels, there can be the case in witch a task is scheduled by

     schedule_time > CBSSTAR_deadline; in this case (not covered in the

     article because if there is only the standard scheduling policy

     this never apply) we reassign the deadline */

  if ( TIMESPEC_A_LT_B(&b->dline, &schedule_time) ) {

    /* we kill the current activation */

    level_table[ lev->scheduling_level ]->

      private_extract(lev->scheduling_level, p);

    /* we modify the deadline ... */

    TIMESPEC_ASSIGN(&b->dline, &schedule_time);

    ADDUSEC2TIMESPEC(b->T, &b->dline);

    /* and the capacity */

    b->avail = b->Q;

#ifdef CBSSTAR_DEBUG

    cbsstar_printf2(" %ld.%ld av=%d)",b->dline.tv_sec,b->dline.tv_nsec/1000, b->Q);

    cbsstar_printf3("±%d±",lev->tb[p]);

    cbsstar_printblob(lev->tb[p]);

#endif

    /* and, finally, we reinsert the task in the master level */

    job_task_default_model(job, b->dline);

    job_task_def_noexc(job);

    level_table[ lev->scheduling_level ]->

      private_insert(lev->scheduling_level, p, (TASK_MODEL *)&job);

    return -1;

  }

#ifdef CBSSTAR_DEBUG

  cbsstar_printf(")");

#endif

  return 0;

}

static void CBSSTAR_private_insert(LEVEL l, PID p, TASK_MODEL *m)

{

  /* A task has been activated for some reason. Basically, the task is

  inserted in the queue if the queue is empty, otherwise the task is

  inserted into the master module, and an oslib event is posted. */

  CBSSTAR_level_des *lev = (CBSSTAR_level_des *)(level_table[l]);

  BUDGET_TASK_MODEL *budget;

  if (m->pclass != BUDGET_PCLASS ||

      (m->level != 0 && m->level != l)) {

    kern_raise(XINVALID_TASK, p);

    return;

  }

  budget = (BUDGET_TASK_MODEL *)m;

#ifdef CBSSTAR_DEBUG

  cbsstar_printf("(C:gcr %d b%d", p, budget->b);

#endif

  lev->tb[p] = budget->b;

  if (lev->b[budget->b].current == NIL) {

    /* This is the first task in the budget,

       the task have to be inserted into the master module */

    struct timespec t;

    kern_gettime(&t);

    CBSSTAR_activation(lev,p,&t);

  } else {

    /* The budget is not empty, another task is already into the

       master module, so the task is inserted at the end of the budget

       queue */

    iq_insertlast(p,&lev->b[budget->b].tasks);

#ifdef CBSSTAR_DEBUG

    cbsstar_printf(" ilast");

    cbsstar_printq(&lev->b[budget->b].tasks);

#endif

  }

#ifdef CBSSTAR_DEBUG

  cbsstar_printf(")");

#endif

}

static void CBSSTAR_private_extract(LEVEL l, PID p)

{

  CBSSTAR_level_des *lev = (CBSSTAR_level_des *)(level_table[l]);

#ifdef CBSSTAR_DEBUG

  cbsstar_printf("(C:gend p%d c%d av=%d)", p, lev->b[lev->tb[p]].current, lev->b[lev->tb[p]].avail);

  cbsstar_printq(&lev->b[lev->tb[p]].tasks);

#endif

  /* a task is removed from execution for some reasons. It must be

     that it is the first in its budget queue (only the first task in

     a budget queue is put into execution!) */

  CBSSTAR_account_capacity(lev,p);

  /* remove the task from execution (or from the ready queue) */

  if (lev->b[lev->tb[p]].current == p) {

    /* remove the task from the master module */

    level_table[ lev->scheduling_level ]->

      private_extract(lev->scheduling_level, p);

#ifdef CBSSTAR_DEBUG

    cbsstar_printq(&lev->b[lev->tb[p]].tasks);

#endif

    /* check if the buffer has someone else to schedule */

    if (iq_query_first(&lev->b[lev->tb[p]].tasks) == NIL) {

      /* the buffer has no tasks! */

      lev->b[lev->tb[p]].current = NIL;

    }

    else {

      /* if so, insert the new task into the master module */

      PID n;

      struct timespec t;

      kern_gettime(&t);

      n = iq_getfirst(&lev->b[lev->tb[p]].tasks);

#ifdef CBSSTAR_DEBUG

      cbsstar_printf("{p%d n%d}",p,n);

#endif

      CBSSTAR_activation(lev,n,&t);  // it modifies b[lev->tb[p]].current

    }

  }

  else

    iq_extract(p, &lev->b[lev->tb[p]].tasks);

}

static void CBSSTAR_private_dispatch(LEVEL l, PID p, int nostop)

{

  CBSSTAR_level_des *lev = (CBSSTAR_level_des *)(level_table[l]);

  struct timespec ty;

#ifdef CBSSTAR_DEBUG

  cbsstar_printf("(C:gdisp p%d c%d av=%d)", p, lev->b[lev->tb[p]].current, lev->b[lev->tb[p]].avail);

  cbsstar_printq(&lev->b[lev->tb[p]].tasks);

#endif

  /* the current task (that is the only one inserted in the master module

     for the corresponding budget) is dispatched. Note that the current

     task is not inserted in any FIFO queue, so the task does not have to

     be extracted! */

  /* ... then, we dispatch it to the master level */

  level_table[ lev->scheduling_level ]->

    private_dispatch(lev->scheduling_level,p,nostop);

  /* ...and finally, we have to post a capacity event */

  if (!nostop) {

    TIMESPEC_ASSIGN(&ty, &schedule_time);

    ADDUSEC2TIMESPEC(lev->b[lev->tb[p]].avail,&ty);

    cap_timer = kern_event_post(&ty, capacity_timer, NULL);

  }

}

static void CBSSTAR_private_epilogue(LEVEL l, PID p)

{

  CBSSTAR_level_des *lev = (CBSSTAR_level_des *)(level_table[l]);

  struct budget_struct *b = &lev->b[lev->tb[p]];

#ifdef CBSSTAR_DEBUG

  cbsstar_printf("(C:gepi %d",p);

#endif

  CBSSTAR_account_capacity(lev,p);

  /* we have to check if the capacity is still available */

  if (b->avail > 0) {

    /* there is capacity available, maybe it is simply a preemption;

       the task have to return to the ready queue */

    level_table[ lev->scheduling_level ]->

      private_epilogue(lev->scheduling_level,p);

#ifdef CBSSTAR_DEBUG

    cbsstar_printf2(" *av=%d", b->avail);

#endif

  } else {

    /* The capacity is exausted; the deadline have to be postponed and

       the task have to be reinserted in the master module */

    JOB_TASK_MODEL job;

    /* we kill the current activation */

    level_table[ lev->scheduling_level ]->

      private_extract(lev->scheduling_level, p);

    /* we modify the deadline according to rule 4 ... */

    /* there is a while because if the wcet is << than the system tick

       we need to postpone the deadline many times */

    while (b->avail <= 0) {

      ADDUSEC2TIMESPEC(b->T, &b->dline);

      b->avail += b->Q;

#ifdef CBSSTAR_DEBUG

      cbsstar_printf3("±%d±",lev->tb[p]);

      cbsstar_printblob(lev->tb[p]);

#endif

    }

#ifdef CBSSTAR_DEBUG

    cbsstar_printf2(" %ld.%ld av=%d",b->dline.tv_sec,b->dline.tv_nsec/1000, b->avail);

#endif

    /* and, finally, we reinsert the task in the master level */

    job_task_default_model(job, b->dline);

    job_task_def_noexc(job);

    level_table[ lev->scheduling_level ]->

      private_insert(lev->scheduling_level, p, (TASK_MODEL *)&job);

  }

#ifdef CBSSTAR_DEBUG

  cbsstar_printf(")");

#endif

}

/* Registration functions */

/*+ Registration function:

    int flags                 the init flags ... see CBSSTAR.h +*/

LEVEL CBSSTAR_register_level(int n, LEVEL master)

{

  LEVEL l;            /* the level that we register */

  CBSSTAR_level_des *lev;  /* for readableness only */

  PID i;              /* a counter */

#ifdef CBSSTAR_DEBUG

  cbsstar_printf("CBSSTAR_register_level\n");

#endif

  /* request an entry in the level_table */

  l = level_alloc_descriptor(sizeof(CBSSTAR_level_des));

  lev = (CBSSTAR_level_des *)level_table[l];

  printk("    lev=%d\n",(int)lev);

  /* fill the standard descriptor */

  lev->l.private_insert   = CBSSTAR_private_insert;

  lev->l.private_extract  = CBSSTAR_private_extract;

  lev->l.private_eligible = CBSSTAR_private_eligible;

  lev->l.private_dispatch = CBSSTAR_private_dispatch;

  lev->l.private_epilogue = CBSSTAR_private_epilogue;

  lev->l.public_guarantee = CBSSTAR_public_guarantee;

  /* fill the CBSSTAR descriptor part */

  lev->b = (struct budget_struct *)kern_alloc(sizeof(struct budget_struct)*n);

  for (i=0; i<n; i++) {

    lev->b[i].Q = 0;

    lev->b[i].T = 0;

    NULL_TIMESPEC(&lev->b[i].dline);

    lev->b[i].dline_timer = 0;

    lev->b[i].avail = 0;

    lev->b[i].current = -1;

    iq_init(&lev->b[i].tasks, &freedesc, 0);

  }

  lev->n = n;

  lev->freebudgets = 0;

  for (i=0; i<MAX_PROC; i++)

    lev->tb[i] = NIL;

  lev->U = 0;

  lev->scheduling_level = master;

  return l;

}

int CBSSTAR_setbudget(LEVEL l, TIME Q, TIME T)

{

  CBSSTAR_level_des *lev = (CBSSTAR_level_des *)(level_table[l]);

#ifdef CBSSTAR_DEBUG

  cbsstar_printf("(C:sbud)");

#endif

  if (lev->freebudgets != lev->n) {

    bandwidth_t b;

    b = (MAX_BANDWIDTH / T) * Q;

    /* really update lev->U, checking an overflow... */

    if (Q< T && MAX_BANDWIDTH - lev->U > b) {

      int r = lev->freebudgets;  // the return value

      lev->U += b;

      lev->freebudgets++;

      lev->b[r].Q = Q;

      lev->b[r].T = T;

      return r;

    }

    else

      return -2;

  }

  else

    return -1;

}