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: ds.c,v 1.1.1.1 2002-03-29 14:12:52 pj Exp $

 File:        $File$
 Revision:    $Revision: 1.1.1.1 $
 Last update: $Date: 2002-03-29 14:12:52 $
 ------------

 This file contains the aperiodic server DS (Deferrable Server)

 This module is directly derived from the Polling server one.
 All the notes writed for the PS are valid for the DS.

 The difference between DS and PS is that when there are not task to
 schedule the capacity is not reset to 0...

**/

/*
 * Copyright (C) 2000 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 <modules/ds.h>
#include <ll/stdio.h>
#include <ll/string.h>
#include <kernel/model.h>
#include <kernel/descr.h>
#include <kernel/var.h>
#include <kernel/func.h>

/*+ Status used in the level +*/
#define DS_WAIT          APER_STATUS_BASE    /*+ waiting the service   +*/

/*+ the level redefinition for the Total Bandwidth Server level +*/
typedef struct {
  level_des l;     /*+ the standard level descriptor          +*/

  /* The wcet are stored in the task descriptor's priority
     field, so no other fields are needed                      */

  int nact[MAX_PROC]; /*+ number of pending activations       +*/

  struct timespec lastdline; /*+ the last deadline assigned to
                                 a DS task                    +*/

  int Cs;          /*+ server capacity                        +*/
  int availCs;     /*+ server avail time                      +*/

  QQUEUE wait;      /*+ the wait queue of the DS              +*/
  PID activated;   /*+ the task inserted in another queue     +*/

  int flags;       /*+ the init flags...                      +*/

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

  LEVEL scheduling_level;

} DS_level_des;

/* This static function activates the task pointed by lev->activated) */
static __inline__ void DS_activation(DS_level_des *lev)
{
    PID p;                     /* for readableness    */
    JOB_TASK_MODEL j;          /* the guest model     */
    LEVEL m;                   /* the master level... only for readableness*/

    p = lev->activated;
    m = lev->scheduling_level;
    job_task_default_model(j,lev->lastdline);
    job_task_def_period(j,lev->period);
    level_table[m]->guest_create(m,p,(TASK_MODEL *)&j);
    level_table[m]->guest_activate(m,p);
//    kern_printf("(%d %d)",lev->lastdline.tv_sec,lev->lastdline.tv_nsec);
}

static void DS_deadline_timer(void *a)
{
  DS_level_des *lev = (DS_level_des *)(level_table[(LEVEL)a]);

  ADDUSEC2TIMESPEC(lev->period, &lev->lastdline);

//  kern_printf("(%d:%d %d)",lev->lastdline.tv_sec,lev->lastdline.tv_nsec, lev->period);
  if (lev->availCs >= 0)
    lev->availCs = lev->Cs;
  else
    lev->availCs += lev->Cs;

  /* availCs may be <0 because a task executed via a shadow fo many time
     lev->activated == NIL only if the prec task was finished and there
     was not any other task to be put in the ready queue
     ... we are now activating the next task */
  if (lev->availCs > 0 && lev->activated == NIL) {
      if (qq_queryfirst(&lev->wait) != NIL) {
        lev->activated = qq_getfirst(&lev->wait);
        DS_activation(lev);
        event_need_reschedule();
      }
  }

  kern_event_post(&lev->lastdline, DS_deadline_timer, a);
//  kern_printf("!");
}

static char *DS_status_to_a(WORD status)
{
  if (status < MODULE_STATUS_BASE)
    return status_to_a(status);

  switch (status) {
    case DS_WAIT         : return "DS_Wait";
    default              : return "DS_Unknown";
  }
}


static int DS_level_accept_task_model(LEVEL l, TASK_MODEL *m)
{
  if (m->pclass == SOFT_PCLASS || m->pclass == (SOFT_PCLASS | l) ) {
    SOFT_TASK_MODEL *s = (SOFT_TASK_MODEL *)m;

    if (s->periodicity == APERIODIC)
      return 0;
  }
  return -1;
}

static int DS_level_accept_guest_model(LEVEL l, TASK_MODEL *m)
{
  return -1;
}

static char *onoff(int i)
{
  if (i)
    return "On ";
  else
    return "Off";
}

static void DS_level_status(LEVEL l)
{
  DS_level_des *lev = (DS_level_des *)(level_table[l]);
  PID p = qq_queryfirst(&lev->wait);

  kern_printf("On-line guarantee : %s\n",
            onoff(lev->flags & DS_ENABLE_GUARANTEE_EDF ||
                  lev->flags & DS_ENABLE_GUARANTEE_RM  ));
  kern_printf("Used Bandwidth    : %u/%u\n",
            lev->U, MAX_BANDWIDTH);

  if (lev->activated != -1)
    kern_printf("Activated: Pid: %2d Name: %10s Dl: %ld.%ld Nact: %d Stat: %s\n",
              lev->activated,
              proc_table[lev->activated].name,
              proc_table[lev->activated].timespec_priority.tv_sec,
              proc_table[lev->activated].timespec_priority.tv_nsec,
              lev->nact[lev->activated],
              DS_status_to_a(proc_table[lev->activated].status));

  while (p != NIL) {
    kern_printf("Pid: %2d Name: %10s Stat: %s\n",
              p,
              proc_table[p].name,
              DS_status_to_a(proc_table[p].status));
    p = proc_table[p].next;
  }
}

static PID DS_level_scheduler(LEVEL l)
{
  /* the DS don't schedule anything...
     it's an EDF level or similar that do it! */
  return NIL;
}

static PID DS_level_schedulerbackground(LEVEL l)
{
  /* the DS catch the background time to exec aperiodic activities */
  DS_level_des *lev = (DS_level_des *)(level_table[l]);

  lev->flags |= DS_BACKGROUND;

  if (lev->flags & DS_BACKGROUND_BLOCK)
    return NIL;
  else
    return qq_queryfirst(&lev->wait);
}

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

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

static int DS_level_guaranteeRM(LEVEL l, bandwidth_t *freebandwidth)
{
  DS_level_des *lev = (DS_level_des *)(level_table[l]);

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

static int DS_task_create(LEVEL l, PID p, TASK_MODEL *m)
{
  DS_level_des *lev = (DS_level_des *)(level_table[l]);

  /* if the DS_task_create is called, then the pclass must be a
     valid pclass. */
  SOFT_TASK_MODEL *s = (SOFT_TASK_MODEL *)m;

  if (s->arrivals == SAVE_ARRIVALS)
    lev->nact[p] = 0;
  else
    lev->nact[p] = -1;

  return 0; /* OK, also if the task cannot be guaranteed... */
}

static void DS_task_detach(LEVEL l, PID p)
{
  /* the DS level doesn't introduce any dinamic allocated new field. */
}

static int DS_task_eligible(LEVEL l, PID p)
{
  return 0; /* if the task p is chosen, it is always eligible */
}

#ifdef __TEST1__
extern int testactive;
extern struct timespec s_stime[];
extern TIME s_curr[];
extern TIME s_PID[];
extern int useds;
#endif

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

//  if (nostop) kern_printf("NOSTOP!!!!!!!!!!!!");
  /* there is at least one task ready inserted in an EDF or similar
     level note that we can't check the status because the scheduler set it
     to exe before calling task_dispatch. we have to check
     lev->activated != p instead */
  if (lev->activated != p) {
    qq_extract(p, &lev->wait);
    //kern_printf("#%d#",p);
  }
  else {
    //if (nostop) kern_printf("(gd status=%d)",proc_table[p].status);
    level_table[ lev->scheduling_level ]->
      guest_dispatch(lev->scheduling_level,p,nostop);
  }

  /* set the capacity timer */
  if (!nostop) {
    TIMESPEC_ASSIGN(&ty, &schedule_time);
    ADDUSEC2TIMESPEC(lev->availCs,&ty);
    cap_timer = kern_event_post(&ty, capacity_timer, NULL);
  }

//  kern_printf("(disp %d %d)",ty.tv_sec, ty.tv_nsec);

  #ifdef __TEST1__
  if (testactive)
  {
    TIMESPEC_ASSIGN(&s_stime[useds], &schedule_time);
    s_curr[useds] = proc_table[p].avail_time;
    s_PID[useds]  = p;
    useds++;
  }
  #endif
}

static void DS_task_epilogue(LEVEL l, PID p)
{
  DS_level_des *lev = (DS_level_des *)(level_table[l]);
  struct timespec ty;
  TIME tx;

  /* update the server capacity */
  if (lev->flags & DS_BACKGROUND)
    lev->flags &= ~DS_BACKGROUND;
  else {
    SUBTIMESPEC(&schedule_time, &cap_lasttime, &ty);
    tx = TIMESPEC2USEC(&ty);
    lev->availCs -= tx;
  }

//  kern_printf("(epil %d %d)",lev->availCs, proc_table[p].avail_time);

  /* check if the server capacity is finished... */
  if (lev->availCs < 0) {
//    kern_printf("(epil Cs%d %d:%d act%d p%d)",
//              lev->availCs,proc_table[p].timespec_priority.tv_sec,
//              proc_table[p].timespec_priority.tv_nsec,
//              lev->activated,p);
    /* the server slice has finished... do the task_end!!!
       a first version of the module used the task_endcycle, but it was
       not conceptually correct because the task didn't stop because it
       finished all the work but because the server didn't have budget!
       So, if the task_endcycle is called, the task remain into the
       master level, and we can't wake him up if, for example, another
       task point the shadow to it!!!*/
    if (lev->activated == p)
      level_table[ lev->scheduling_level ]->
        guest_end(lev->scheduling_level,p);
    qq_insertfirst(p, &lev->wait);
    proc_table[p].status = DS_WAIT;
    lev->activated = NIL;
  }
  else
    /* the task has been preempted. it returns into the ready queue or to the
       wait queue by calling the guest_epilogue... */
    if (lev->activated == p) {//kern_printf("Û1");
      level_table[ lev->scheduling_level ]->
        guest_epilogue(lev->scheduling_level,p);
    } else { //kern_printf("Û2");
      qq_insertfirst(p, &lev->wait);
      proc_table[p].status = DS_WAIT;
    }
}

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

  if (lev->activated == p || proc_table[p].status == DS_WAIT) {
    if (lev->nact[p] != -1)
      lev->nact[p]++;
  }
  else if (proc_table[p].status == SLEEP) {
    ll_gettime(TIME_EXACT, &proc_table[p].request_time);

    if (lev->activated == NIL && lev->availCs > 0) {
      lev->activated = p;
      DS_activation(lev);
    }
    else {
      qq_insertlast(p, &lev->wait);
      proc_table[p].status = DS_WAIT;
    }
  }
  else
  {  kern_printf("DS_REJ%d %d %d %d ",p, proc_table[p].status, lev->activated, lev->wait.first);
     return; }

}

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

  lev->flags &= ~DS_BACKGROUND_BLOCK;

  lev->activated = -1;

  /* when we reinsert the task into the system, the server capacity
     is always 0 because nobody executes with the DS before... */
  qq_insertfirst(p, &lev->wait);
  proc_table[p].status = DS_WAIT;
}

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

  /* update the server capacity */
  lev->availCs = 0;

  lev->flags |= DS_BACKGROUND_BLOCK;

  if (lev->activated == p)
    level_table[ lev->scheduling_level ]->
      guest_end(lev->scheduling_level,p);
}

static void DS_task_endcycle(LEVEL l, PID p)
{
  DS_level_des *lev = (DS_level_des *)(level_table[l]);
  struct timespec ty;
  TIME tx;

  /* update the server capacity */
  if (lev->flags & DS_BACKGROUND)
    lev->flags &= ~DS_BACKGROUND;
  else {
    SUBTIMESPEC(&schedule_time, &cap_lasttime, &ty);
    tx = TIMESPEC2USEC(&ty);
    lev->availCs -= tx;
  }

  if (lev->activated == p)
    level_table[ lev->scheduling_level ]->
      guest_end(lev->scheduling_level,p);
  else
    qq_extract(p, &lev->wait);

  if (lev->nact[p] > 0)
  {
    lev->nact[p]--;
    qq_insertlast(p, &lev->wait);
    proc_table[p].status = DS_WAIT;
  }
  else
    proc_table[p].status = SLEEP;
 
  lev->activated = qq_getfirst(&lev->wait);
  if (lev->activated != NIL)
    DS_activation(lev);
}

static void DS_task_end(LEVEL l, PID p)
{
  DS_level_des *lev = (DS_level_des *)(level_table[l]);
  struct timespec ty;
  TIME tx;

  /* update the server capacity */
  if (lev->flags & DS_BACKGROUND)
    lev->flags &= ~DS_BACKGROUND;
  else {
    SUBTIMESPEC(&schedule_time, &cap_lasttime, &ty);
    tx = TIMESPEC2USEC(&ty);
    lev->availCs -= tx;
  }

  if (lev->activated == p)
    level_table[ lev->scheduling_level ]->
      guest_end(lev->scheduling_level,p);

  proc_table[p].status = FREE;
  q_insertfirst(p,&freedesc);

  lev->activated = qq_getfirst(&lev->wait);
  if (lev->activated != NIL)
    DS_activation(lev);
}

static void DS_task_sleep(LEVEL l, PID p)
{
  DS_level_des *lev = (DS_level_des *)(level_table[l]);
  struct timespec ty;
  TIME tx;

  /* update the server capacity */
  if (lev->flags & DS_BACKGROUND)
    lev->flags &= ~DS_BACKGROUND;
  else {
    SUBTIMESPEC(&schedule_time, &cap_lasttime, &ty);
    tx = TIMESPEC2USEC(&ty);
    lev->availCs -= tx;
  }

  if (lev->nact[p] >= 0) lev->nact[p] = 0;

  if (lev->activated == p)
    level_table[ lev->scheduling_level ]->
      guest_end(lev->scheduling_level,p);
  else
    qq_extract(p, &lev->wait);

  proc_table[p].status = SLEEP;

  lev->activated = qq_getfirst(&lev->wait);
  if (lev->activated != NIL)
    DS_activation(lev);
}
static void DS_task_delay(LEVEL l, PID p, TIME usdelay)
{
  DS_level_des *lev = (DS_level_des *)(level_table[l]);
  struct timespec ty;
  TIME tx;

  /* update the server capacity */
  if (lev->flags & DS_BACKGROUND)
    lev->flags &= ~DS_BACKGROUND;
  else {
    SUBTIMESPEC(&schedule_time, &cap_lasttime, &ty);
    tx = TIMESPEC2USEC(&ty);
    lev->availCs -= tx;
  }

  /* I hope no delay when owning a mutex... */
  if (lev->activated == p)
    level_table[ lev->scheduling_level ]->
      guest_delay(lev->scheduling_level,p,usdelay);
}


static int DS_guest_create(LEVEL l, PID p, TASK_MODEL *m)
{ kern_raise(XUNVALID_GUEST,exec_shadow); return 0; }

static void DS_guest_detach(LEVEL l, PID p)
{ kern_raise(XUNVALID_GUEST,exec_shadow); }

static void DS_guest_dispatch(LEVEL l, PID p, int nostop)
{ kern_raise(XUNVALID_GUEST,exec_shadow); }

static void DS_guest_epilogue(LEVEL l, PID p)
{ kern_raise(XUNVALID_GUEST,exec_shadow); }

static void DS_guest_activate(LEVEL l, PID p)
{ kern_raise(XUNVALID_GUEST,exec_shadow); }

static void DS_guest_insert(LEVEL l, PID p)
{ kern_raise(XUNVALID_GUEST,exec_shadow); }

static void DS_guest_extract(LEVEL l, PID p)
{ kern_raise(XUNVALID_GUEST,exec_shadow); }

static void DS_guest_endcycle(LEVEL l, PID p)
{ kern_raise(XUNVALID_GUEST,exec_shadow); }

static void DS_guest_end(LEVEL l, PID p)
{ kern_raise(XUNVALID_GUEST,exec_shadow); }

static void DS_guest_sleep(LEVEL l, PID p)
{ kern_raise(XUNVALID_GUEST,exec_shadow); }

static void DS_guest_delay(LEVEL l, PID p,DWORD tickdelay)
{ kern_raise(XUNVALID_GUEST,exec_shadow); }




/* Registration functions */


/*+ This init function install the DS deadline timer
    +*/
static void DS_dline_install(void *l)
{
  DS_level_des *lev = (DS_level_des *)(level_table[(LEVEL)l]);

  ll_gettime(TIME_EXACT,&lev->lastdline);
  ADDUSEC2TIMESPEC(lev->period, &lev->lastdline);

  kern_event_post(&lev->lastdline, DS_deadline_timer, l);
}



/*+ Registration function:
    int flags                 the init flags ... see DS.h +*/
void DS_register_level(int flags, LEVEL master, int Cs, int per)
{
  LEVEL l;            /* the level that we register */
  DS_level_des *lev;  /* for readableness only */
  PID i;              /* a counter */

  printk("DS_register_level\n");

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

  printk("    alloco descrittore %d %d\n",l,(int)sizeof(DS_level_des));

  /* alloc the space needed for the DS_level_des */
  lev = (DS_level_des *)kern_alloc(sizeof(DS_level_des));

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

  /* update the level_table with the new entry */
  level_table[l] = (level_des *)lev;

  /* fill the standard descriptor */
  strncpy(lev->l.level_name,  DS_LEVELNAME, MAX_LEVELNAME);
  lev->l.level_code               = DS_LEVEL_CODE;
  lev->l.level_version            = DS_LEVEL_VERSION;

  lev->l.level_accept_task_model  = DS_level_accept_task_model;
  lev->l.level_accept_guest_model = DS_level_accept_guest_model;
  lev->l.level_status             = DS_level_status;

  if (flags & DS_ENABLE_BACKGROUND)
    lev->l.level_scheduler          = DS_level_schedulerbackground;
  else
    lev->l.level_scheduler          = DS_level_scheduler;

  if (flags & DS_ENABLE_GUARANTEE_EDF)
    lev->l.level_guarantee        = DS_level_guaranteeEDF;
  else if (flags & DS_ENABLE_GUARANTEE_RM)
    lev->l.level_guarantee        = DS_level_guaranteeRM;
  else
    lev->l.level_guarantee        = NULL;

  lev->l.task_create              = DS_task_create;
  lev->l.task_detach              = DS_task_detach;
  lev->l.task_eligible            = DS_task_eligible;
  lev->l.task_dispatch            = DS_task_dispatch;
  lev->l.task_epilogue            = DS_task_epilogue;
  lev->l.task_activate            = DS_task_activate;
  lev->l.task_insert              = DS_task_insert;
  lev->l.task_extract             = DS_task_extract;
  lev->l.task_endcycle            = DS_task_endcycle;
  lev->l.task_end                 = DS_task_end;
  lev->l.task_sleep               = DS_task_sleep;
  lev->l.task_delay               = DS_task_delay;

  lev->l.guest_create             = DS_guest_create;
  lev->l.guest_detach             = DS_guest_detach;
  lev->l.guest_dispatch           = DS_guest_dispatch;
  lev->l.guest_epilogue           = DS_guest_epilogue;
  lev->l.guest_activate           = DS_guest_activate;
  lev->l.guest_insert             = DS_guest_insert;
  lev->l.guest_extract            = DS_guest_extract;
  lev->l.guest_endcycle           = DS_guest_endcycle;
  lev->l.guest_end                = DS_guest_end;
  lev->l.guest_sleep              = DS_guest_sleep;
  lev->l.guest_delay              = DS_guest_delay;

  /* fill the DS descriptor part */

  for (i=0; i<MAX_PROC; i++)
     lev->nact[i] = -1;

  lev->Cs = Cs;
  lev->availCs = 0;

  lev->period = per;

  qq_init(&lev->wait);
  lev->activated = NIL;

  lev->U = (MAX_BANDWIDTH / per) * Cs;

  lev->scheduling_level = master;

  lev->flags = flags & 0x07;

  sys_atrunlevel(DS_dline_install,(void *) l, RUNLEVEL_INIT);
}

bandwidth_t DS_usedbandwidth(LEVEL l)
{
  DS_level_des *lev = (DS_level_des *)(level_table[l]);
  if (lev->l.level_code    == DS_LEVEL_CODE &&
      lev->l.level_version == DS_LEVEL_VERSION)
    return lev->U;
  else
    return 0;
}