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
 */

/*
 * 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 "grubstar.h"

#define GRUBSTAR_DEBUG

/* 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 vtimer;
  int avail;              /* current budget */
 
  LEVEL l;                /* Current GRUBSTAR level */
  int loc_sched_id;       /* Local scheduler id */
  LEVEL loc_sched_level;  /* Local scheduler level */
 
  PID current;            /* the task currently put in execution */
  int flags;

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

};

#define GRUBSTAR_NOACTIVE   0
#define GRUBSTAR_ACTIVE     1
#define GRUBSTAR_RECLAIMING 2

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       +*/
  bandwidth_t Uf;   /*+ the actual used bandwidth by the server       +*/

  int cap_lev;

  LEVEL scheduling_level;

} GRUBSTAR_level_des;


static void GRUBSTAR_deadline_timer_hardreservation(void *a)
{
  struct budget_struct *b = a;
  PID p;
  GRUBSTAR_level_des *lev;
 
  lev = (GRUBSTAR_level_des *)(level_table[b->l]);

  #ifdef GRUBSTAR_DEBUG
    kern_printf("(GS:HrdRes:");  
  #endif

  b->dline_timer = NIL;

  b->avail += b->Q;
  if (b->avail > b->Q) b->avail = b->Q;
 
  if (b->flags==GRUBSTAR_RECLAIMING && b->avail>0) {
         bandwidth_t bw;
         bw = (MAX_BANDWIDTH / b->T) * b->Q;

         lev->Uf += bw;

         #ifdef GRUBSTAR_DEBUG
              kern_printf("BW=%ld, U=%u, Uf=%u",(long)bw, lev->U, lev->Uf);
         #endif
  }

  if (b->avail > 0) b->flags = GRUBSTAR_ACTIVE;

  if (b->current == NIL && b->flags) {
      if (iq_query_first(&(b->tasks)) != NIL) {
        JOB_TASK_MODEL job;
 
        p = iq_getfirst(&b->tasks);
 
        #ifdef GRUBSTAR_DEBUG
          kern_printf("%d",p);
        #endif

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

        b->current = p;

       
        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);
       
        event_need_reschedule();

    }
  }
 
  if (b->flags == GRUBSTAR_NOACTIVE) {
    kern_gettime(&b->dline);
    ADDUSEC2TIMESPEC(b->T, &b->dline);
 
    b->dline_timer=kern_event_post(&b->dline, GRUBSTAR_deadline_timer_hardreservation, b);
  }

  #ifdef GRUBSTAR_DEBUG
    kern_printf(")");
  #endif

}

void GRUBSTAR_ANC(void *arg)
{
  struct budget_struct *b = arg;
  GRUBSTAR_level_des *lev=(GRUBSTAR_level_des *)level_table[b->l];
 
  #ifdef GRUBSTAR_DEBUG
    kern_printf("(GS:Rec:");
  #endif

  b->vtimer = NIL;
  if (b->current != NIL && iq_query_first(&(b->tasks)) != NIL) {
     bandwidth_t bw;

     b->flags=GRUBSTAR_RECLAIMING;

     bw = (MAX_BANDWIDTH / b->T) * b->Q;

     lev->Uf -= bw;
     
     #ifdef GRUBSTAR_DEBUG
       kern_printf("bw=%ld, U=%u, Uf=%u",(long)bw, lev->U, lev->Uf);
     #endif

     
  }

  #ifdef GRUBSTAR_DEBUG
    kern_printf(")");
  #endif


}

static void GRUBSTAR_activation(GRUBSTAR_level_des *lev,
                           PID p,
                           struct timespec *acttime)
{
  JOB_TASK_MODEL job;
  struct budget_struct *b = &lev->b[lev->tb[p]];
  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) ) {
       TIMESPEC_ASSIGN(&b->dline, acttime);
       ADDUSEC2TIMESPEC(b->T, &b->dline);
       b->avail=b->Q;
       if (b->flags==GRUBSTAR_RECLAIMING) {
         bandwidth_t bw;
 
         bw = (MAX_BANDWIDTH / b->T) * b->Q;

         lev->Uf += bw;
     
         #ifdef grubSTAR_DEBUG
            kern_printf("BW=%ld, U=%u, Uf=%u",(long)bw, lev->U, lev->Uf);
         #endif
       }


       b->flags=GRUBSTAR_ACTIVE;

  }

  SUBTIMESPEC(&b->dline, &t3, &t2);
  if (b->vtimer!=NIL) kern_event_delete(b->vtimer);
  b->vtimer=NIL;
  b->vtimer = kern_event_post(&t2, GRUBSTAR_ANC, b);


  /* record the current task inserted in the master module */
  b->current = p;

  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 GRUBSTAR_account_capacity(GRUBSTAR_level_des *lev, PID p)
{
  struct timespec ty;
  TIME tx;
  struct budget_struct *b = &lev->b[lev->tb[p]];

  if (lev->cap_lev != NIL && b->current == p) {
    kern_event_delete(lev->cap_lev);
    lev->cap_lev = NIL;
  }

  SUBTIMESPEC(&schedule_time, &cap_lasttime, &ty);
  tx = TIMESPEC2USEC(&ty);
  b->avail -= (int)((long long)tx * (long long)lev->Uf / (int)lev->U);

  #ifdef GRUBSTAR_DEBUG
    kern_printf("(GS:Cap p%d av=%d Uf=%u U=%u)", p, b->avail,lev->Uf, lev->U);
  #endif

  if (b->avail <= 0) b->flags = GRUBSTAR_NOACTIVE;

  if (TIMESPEC_A_LT_B(&b->dline, &schedule_time)) {
    /* we modify the deadline ... */
    TIMESPEC_ASSIGN(&b->dline, &schedule_time);
    ADDUSEC2TIMESPEC(b->T, &b->dline);
  }

  if (b->flags == GRUBSTAR_NOACTIVE && b->dline_timer == NIL)  {
    b->dline_timer=kern_event_post(&b->dline, GRUBSTAR_deadline_timer_hardreservation, b);
  }
 
}


/* The on-line guarantee is enabled only if the appropriate flag is set... */
static int GRUBSTAR_public_guarantee(LEVEL l, bandwidth_t *freebandwidth)
{
  GRUBSTAR_level_des *lev = (GRUBSTAR_level_des *)(level_table[l]);

  #ifdef GRUBSTAR_DEBUG
    kern_printf("(GS:Gua)");
  #endif

  if (*freebandwidth >= lev->U) {
    *freebandwidth -= lev->U;
    return 1;
  }
  else
    return 0;
}

static void capacity_handler(void *l)
{
 
  GRUBSTAR_level_des *lev = l;
  lev->cap_lev = NIL;
  event_need_reschedule();
 
}

static int GRUBSTAR_private_eligible(LEVEL l, PID p)
{
  GRUBSTAR_level_des *lev = (GRUBSTAR_level_des *)(level_table[l]);
  struct budget_struct *b = &lev->b[lev->tb[p]];
  JOB_TASK_MODEL job;

  if (b->current == p) {
    if ( TIMESPEC_A_LT_B(&b->dline, &schedule_time)) {
      if (lev->cap_lev!=NIL) {
        kern_event_delete(lev->cap_lev);
        lev->cap_lev=NIL;
      }
           
      /* 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;
      b->flags = GRUBSTAR_ACTIVE;

      if (b->dline_timer!=NIL)  {
        kern_event_delete(b->dline_timer);
        b->dline_timer=NIL;
      }
   
      /* 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;
   
    }  
  }

  return 0;

}

static void GRUBSTAR_private_insert(LEVEL l, PID p, TASK_MODEL *m)
{
  GRUBSTAR_level_des *lev = (GRUBSTAR_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 GRUBSTAR_DEBUG
    kern_printf("(GS:PriIns:%d:%d", p, budget->b);
  #endif
 
  if (budget->b == -1)
    return;

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

  if (lev->b[budget->b].current == NIL && lev->b[budget->b].flags ) {
    /* This is the first task in the budget,
       the task have to be inserted into the master module */
    struct timespec t;
    kern_gettime(&t);
    GRUBSTAR_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 GRUBSTAR_DEBUG
    kern_printf(")");
  #endif

}

static void GRUBSTAR_private_extract(LEVEL l, PID p)
{
  GRUBSTAR_level_des *lev = (GRUBSTAR_level_des *)(level_table[l]);

  #ifdef GRUBSTAR_DEBUG
    kern_printf("(GS:Ext:%d)", p);
  #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!) */

  /* remove the task from execution (or from the ready queue) */
  if (lev->b[lev->tb[p]].current == p) {

   GRUBSTAR_account_capacity(lev,p);
    /* remove the task from the master module */
    level_table[ lev->scheduling_level ]->
      private_extract(lev->scheduling_level, p);

    /* 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 (lev->b[lev->tb[p]].flags) {
      /* 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);
      GRUBSTAR_activation(lev,n,&t);  // it modifies b[lev->tb[p]].current
    }
    else
      lev->b[lev->tb[p]].current=NIL;

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

static void GRUBSTAR_private_dispatch(LEVEL l, PID p, int nostop)
{
  GRUBSTAR_level_des *lev = (GRUBSTAR_level_des *)(level_table[l]);
  struct timespec ty;

  #ifdef GRUBSTAR_DEBUG
    kern_printf("(GS:Dsp:%d)", p);
  #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);
    lev->cap_lev = kern_event_post(&ty,capacity_handler, lev);
  }
 
}

static void GRUBSTAR_private_epilogue(LEVEL l, PID p)
{
  GRUBSTAR_level_des *lev = (GRUBSTAR_level_des *)(level_table[l]);
  struct budget_struct *b = &lev->b[lev->tb[p]];

  #ifdef GRUBSTAR_DEBUG
    kern_printf("(CS:Epi:%d)",p);
  #endif

  if (p==b->current)  {
   
    GRUBSTAR_account_capacity(lev,p);

    // L'evento di capacità va cancellato perchè sarà ripristinato nella successiva dispatch
    /* we have to check if the capacity is still available */
    if (b->flags)  {
      /* 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);
   
    } else {
      /* we kill the current activation */
      level_table[ lev->scheduling_level ]->
        private_extract(lev->scheduling_level, p);    

      iq_insertfirst(p, &b->tasks);
      b->current = NIL;
 
    }
   
  }

}

/* Registration functions }*/

LEVEL GRUBSTAR_register_level(int n, LEVEL master)
{
  LEVEL l;            /* the level that we register */
  GRUBSTAR_level_des *lev;  /* for readableness only */
  PID i;              /* a counter */

  printk("GRUBSTAR_register_level\n");

  /* request an entry in the level_table */
  l = level_alloc_descriptor(sizeof(GRUBSTAR_level_des));

  lev = (GRUBSTAR_level_des *)level_table[l];

  /* fill the standard descriptor */
  lev->l.private_insert   = GRUBSTAR_private_insert;
  lev->l.private_extract  = GRUBSTAR_private_extract;
  lev->l.private_eligible = GRUBSTAR_private_eligible;
  lev->l.private_dispatch = GRUBSTAR_private_dispatch;
  lev->l.private_epilogue = GRUBSTAR_private_epilogue;

  lev->l.public_guarantee = GRUBSTAR_public_guarantee;

  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 = NIL;
    lev->b[i].vtimer=NIL;
    lev->b[i].avail = 0;
    lev->b[i].current = -1;
    lev->b[i].flags = GRUBSTAR_ACTIVE;
    lev->b[i].l=l;
    iq_init(&lev->b[i].tasks, NULL, 0);
  }

  lev->n = n;
  lev->freebudgets = 0;

  for (i=0; i<MAX_PROC; i++)
    lev->tb[i] = NIL;

  lev->U = 0;
  lev->Uf = 0;
  lev->cap_lev = NIL;
  lev->scheduling_level = master;

  return l;

}

int GRUBSTAR_setbudget(LEVEL l, TIME Q, TIME T, LEVEL local_scheduler_level, int scheduler_id)
{
  GRUBSTAR_level_des *lev = (GRUBSTAR_level_des *)(level_table[l]);
  int r;

  #ifdef GRUBSTAR_DEBUG
    kern_printf("(GS:SetBud)");
  #endif

  for (r = 0; r < lev->n; r++)
    if (lev->b[r].Q == 0) break;

  if (r != 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) {
     
      lev->U += b;
      lev->Uf += b;
      lev->freebudgets++;
     
      lev->b[r].Q = Q;
      lev->b[r].T = T;
      lev->b[r].avail = Q;
      lev->b[r].flags = GRUBSTAR_ACTIVE;
      lev->b[r].loc_sched_id = scheduler_id;
      lev->b[r].loc_sched_level = local_scheduler_level;
     
      return r;
    }
    else
      return -2;
  }
  else
    return -1;
}

int GRUBSTAR_removebudget(LEVEL l, int budget)
{

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

  bandwidth_t b;
 
  b = (MAX_BANDWIDTH / lev->b[budget].T) * lev->b[budget].Q;

  lev->U -= b;

  lev->b[budget].Q = 0;
  lev->b[budget].T = 0;
  NULL_TIMESPEC(&lev->b[budget].dline);
  lev->b[budget].dline_timer = NIL;
  lev->b[budget].avail = 0;
  lev->b[budget].current = -1;
  lev->b[budget].flags = GRUBSTAR_ACTIVE;

  return 0;

}

int GRUBSTAR_adjust_budget(LEVEL l, TIME Q, TIME T, int budget)
{

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

  lev->b[budget].Q = Q;
  lev->b[budget].T = T;

  return 0;

}

int GRUBSTAR_getbudgetinfo(LEVEL l, TIME *Q, TIME *T, int budget)
{

  GRUBSTAR_level_des *lev = (GRUBSTAR_level_des *)(level_table[l]);
 
  *Q = lev->b[budget].Q;
  *T = lev->b[budget].T;

  return 0;

}

int GRUBSTAR_is_active(LEVEL l, int budget)
{
  GRUBSTAR_level_des *lev = (GRUBSTAR_level_des *)(level_table[l]);

  return lev->b[budget].flags;

}

int GRUBSTAR_get_local_scheduler_level_from_budget(LEVEL l, int budget)
{
  GRUBSTAR_level_des *lev = (GRUBSTAR_level_des *)(level_table[l]);

  return lev->b[budget].loc_sched_level;

}

int GRUBSTAR_get_local_scheduler_level_from_pid(LEVEL l, PID p)
{
  GRUBSTAR_level_des *lev = (GRUBSTAR_level_des *)(level_table[l]);

  return lev->b[lev->tb[p]].loc_sched_level;

}

int GRUBSTAR_get_local_scheduler_id_from_budget(LEVEL l, int budget)
{
  GRUBSTAR_level_des *lev = (GRUBSTAR_level_des *)(level_table[l]);

  return lev->b[budget].loc_sched_id;

}

int GRUBSTAR_get_local_scheduler_id_from_pid(LEVEL l, PID p)
{
  GRUBSTAR_level_des *lev = (GRUBSTAR_level_des *)(level_table[l]);

  return lev->b[lev->tb[p]].loc_sched_id;

}