/* 
 * red.c
 *
 * x-kernel v3.2
 *
 * Copyright (c) 1993,1991,1990  Arizona Board of Regents
 *
 *
 */

#include <sys/types.h>
#include "x_stdio.h"
#include "xkernel.h"
#include "eth.h"
#include "../protocols/eth/eth_i.h"
#include "ip.h"
#include "ip_i.h"
#include "sim_i.h"
#include "sim_router.h"
#include <stdio.h>

/*    
 * RED Routers
 */           
                     
/*                   
 * Support functions
 *  
 *  EXTERNAL USAGE:
 *
 *  At init time call set_qmax(int x) with the effective total
 *  queueinq capacity for the transmit side on this interface.
 *
 *  When a packet comes in of the bus, call red_ipkt().  If it returns
 *  nonzero keep the packet.  If it is zero discard the packet and
 *  reuse the buffer(s).
 *    
 *  After transmit is completed (not queued for transmit), call red_opkt().
 *      
 *  If the calls to red_ipkt or red_opkt are not properly balanced,
 *  things won't work well.
 */
      
typedef struct redStateStruct {
  short current_queue;
  short stale_drop_counter;
  int   save_avg;    
  int   save_sl;     
  short was_idle;
  short pkt_counter;
  int   last_random;
  
  short qmax;
  short qmin;
  short qhalf;
  short c1;
  short sh1;
  short c2;
  short sh2;
} RedState;
        
void set_qmax(int, int, void **);
static int red_pktavg(RedState *);
static int red_ipkt(RedState *);
static void red_opkt(RedState *);

/*  
 *  set_qmax(int x)
 * 
 *  This function should be called at initialization time.  The one
 *  argument should be the value of the effective transmit side queue
 *  capacity for this interface.  This thing sets up all the
 *  parameters for the magic Approx[R/pb] calculation.  How these
 *  numbers come about needs to be explained. */
  
void set_qmax(int qmax, int qmin, void **sa)
{ 
  int qidx, tmp1;
  RedState *s;
  
  s = (RedState *) xMalloc(sizeof(RedState));
  *sa = (void *)s;
  
  s->qmax = qmax;
/*  s->qmin = x >> 5;             don't even start counting until 1/32 que */
  s->qmin = qmin;
  for (s->qhalf = (1<<14), qidx = 14;
       s->qhalf && !(s->qmax & s->qhalf);
       s->qhalf >>= 1)
    --qidx;                     /* infinite loop if qmax = 0 */
  if (s->qmax == s->qhalf) {
    s->qhalf >>= 1;
    --qidx;
  } 
  tmp1 = s->qhalf / (14 - (16 - qidx));
  for (s->sh2 = 16; !(tmp1 & (1 << s->sh2)); --s->sh2)
    ;                           /* infinite loop if x < 4 */
  --s->sh2;
  s->c2 = 14 - (s->qmax >> s->sh2);
  tmp1 = s->qmax << 2; 
  for (s->c1 = 16; !(tmp1 & (1 << s->c1)); --s->c1)
    ;
  s->c1 = 16 - s->c1;
  s->sh1 = qidx;  
  s->qhalf = (1<<16) * (s->c2 - s->c1) /
    ((1 << (16 - s->sh1)) - (1 << (16 - s->sh2)));
}
  
/*
 *  This is the random number generator.  The variable "s" is the 31
 *  bit random number.  The return value is a scaled integer in the
 *  range of 1/2 to 1, which is what our variation of RED wants.
 */
    
#define A0 16807                /* magic cookies */
#define S0 40                   /* don't change them */
  
static int quick_red_random()
{   
  static unsigned long s = S0;
  unsigned long p, q;
  
  q = (s & 0x7fff) * A0;
  p = (s >> 15) * A0;
  s = (p + q) & 0x7fffffff;
  return ((s & 0x7fff) | 0x8000); /* scaled integer in the range 1/2 - 1 */
} 
    
/*
 *  WQ - is a weighting factor described in "Notes on the Holt-Winters
 *  Procedure" ftp://ftp.ee.lbl.gov/papers/holt.ps.Z by Sally Floyd.
 *  
 *  WQ2 is WQ/2
 *  WQm1(x) is ((1 - WQ) * x)
 *  WQ2m1(x) is ((1 - WQ2) * x)
 *  WQmult(x) is (WQ * x)
 *  WQ2mult(x) is (WQ2 * 2)
 *
 *  WQ is 1/512 to make the math easy
 */
#define SHIFTY          16      /* use scale integer math scaled this much */
#define WQsh            9       /* shift 9 bits for WQ */
#define WQ2sh           10      /* shift 10 bits for WQ2 */
#define WQm1(x)         ((x) - ((x) >> WQsh))
#define WQ2m1(x)        ((x) - ((x) >> WQ2sh))
#define WQmult(x)       ((x) >> WQsh)
#define WQ2mult(x)      ((x) >> WQ2sh)
  
/*
 *  This thing does the Holt Winters filtering
 */
 
static int red_pktavg(RedState *s)
{   
  register int avg, sl, que;
 
  /* the following code implements the average queue size filter */
  avg = s->save_avg; 
  sl = s->save_sl;
  que = s->current_queue << SHIFTY;
  avg = (WQm1(avg + sl)) + (WQmult(que));
  sl = (WQ2m1(sl)) + (WQ2mult(avg - s->save_avg));
  s->save_avg = avg;
  s->save_sl = sl;
  return avg;
}

/*
 *  red_ipkt()
 *
 *  This function is called when a packet is received on the input
 *  side of the transmitting card -- that is off the MCA bus.  The
 *  return value of the function indicates whether to keep or drop the
 *  packet, a nonzero value indicating keep it, and a zero value
 *  indicating drop it.  There are no arguments to this function and
 *  only the static variables in this module are used.
 */
 
#define KEEP_IT         1       /* return this to keep the packet */
#define DROP_IT         0       /* return this to drop the packet */
  
static int red_ipkt(RedState *s)
{ 
  int avg, fudge;
  
  if (++s->current_queue <= 1) {
    /* queue was empty and in effect still is */
    return KEEP_IT;
  }
  
  if (s->was_idle) {
    /* note: no way to know how long we were idle */
    s->was_idle = 0;
    s->save_avg >>= 1;
    s->save_sl = 0;
    s->pkt_counter = -1;
    if (s->qmax < 0) {
      Kabort("s->qmax < 0");
    }
  }
  avg = red_pktavg(s);
  /* adjust the result down from the scale integer math */ 
  avg >>= SHIFTY;
  /* minimum drop threshhold */
  if (avg <= s->qmin) {  
    /* this one gets by unharmed - and the counter is reset */
    s->pkt_counter = -1;
    return KEEP_IT;
  }
  /* determine whether we need a new count */ 
  ++s->pkt_counter;
  if (s->pkt_counter <= 0) {
    if (s->stale_drop_counter)
      s->last_random = quick_red_random();
    s->stale_drop_counter = 0;
    return KEEP_IT; 
  } 
  /* this is the magic Approx[R/pb] in RED */
  if (avg >= s->qmax) {
    fudge = 14;
  } else if (avg > s->qhalf) {
    fudge = s->c2 + (avg >> s->sh2);
  } else {
    fudge = s->c1 + (avg >> s->sh1); 
  }
  if (s->pkt_counter < (s->last_random >> fudge)) {
    /* this one gets by unharmed */
    return KEEP_IT;
  } 
  /* NUKE IT! */
  s->pkt_counter = -1;
  s->stale_drop_counter = 1;
  --s->current_queue;
  return DROP_IT;
}   
      
static void red_opkt(RedState *s)
{   
  if (--s->current_queue == 0) {
    /* queue just emptied completely */
    s->was_idle = 1;
    return; 
  } 
  red_pktavg(s);
  
} 
    
void sim_RED_init (ROUTER_STATE *rs, int argc, char **argv)
{
  int k, qmax=0, qmin=0;

  rs->inFun = sim_RED_input;
  rs->cbFun = sim_RED_callback;
  for (k=0; k<argc; k++) {
    if (!strcmp(argv[k], "qmin"))
      sscanf(argv[++k], "%d", &qmin);
    else if (!strncmp(argv[k], "qmin=", 5))
      sscanf(argv[k]+5, "%d", &qmin);
    else if (!strcmp(argv[k], "qmax"))
      sscanf(argv[++k], "%d", &qmax);
    else if (!strncmp(argv[k], "qmax=", 5))
      sscanf(argv[k]+5, "%d", &qmax); 
    }
    if (qmax <= 0)
      qmax = rs->defBufferCnt;
    if (qmin <= 0)
      qmin = qmax >> 5;
    /* venkat: changed this to a for loop */
    for (k=0;k<rs->connectCnt;k++)
      set_qmax(qmax, qmin, (void **)&rs->outState[k]);
}

static void
sim_RED_send (Event ev, void *arg)
{   
  CallBack      *cbp=(CallBack *)arg;
  int           outPort=(int)cbp->arg1;
  ROUTER_STATE  *rs=(ROUTER_STATE *)cbp->state;
  SimPacket     *pkt; 
  Net           *np;
  
  pkt = rs->outQueueBeg[outPort];
  np = pkt->net;
  if (np->control(np, OP_ISBUSY, NULL, NULL, NULL, NULL)) {
    if (rs->traceType == TRACE_TYPE_DETAILED) {
      DO_TRACE_L(rs->ts, TRACE_EVENT_SEND_BUSY, rs->outQueueCnt[outPort],
                 pkt->id, outPort);
    }
    np->control(np, OP_NOTBUSY_CB, rs->cbFun, (void *)rs,
                (void *)outPort, NULL);
  } 
  else {
    if (rs->traceType == TRACE_TYPE_DETAILED) {
      DO_TRACE_L(rs->ts, TRACE_EVENT_SEND_OKAY, pkt->len, pkt->id, outPort);
    }
    np->control(np, OP_SEND, rs->cbFun, (void *)rs, (void *)outPort,
                (void *)pkt);
  }
  freeCallBack(cbp);
} 
  
  
void
sim_RED_callback (Event ev, void *arg)
{ 
  CallBack      *cbp=(CallBack *)arg;
  int           outPort=(int)cbp->arg1;
  long 		t; /* venkat: changed from int */
  int           rvar; 
  ROUTER_STATE  *rs=(ROUTER_STATE *)cbp->state;
  SimPacket     *pkt=(SimPacket *)cbp->arg2;
  ITrace        *itp; 
  MaxMinTrace   *mtp;
  
  /* --- May want to free callback on top, so it can be reused (still in
     cache) */
    
  xsimDbg(SL2_FLAG, printf("[RED cb] host:%d, op:%d\n", cbp->host, cbp->op));
  if (rs->traceType == TRACE_TYPE_DETAILED) {
    DO_TRACE_WT(rs->ts, TRACE_EVENT_CB, cbp->op, cbp->rv);
  }
  if (cbp->op == OP_SENT_CB  ||  cbp->op == OP_RESEND_CB) {
    if (rs->traceType == TRACE_TYPE_DETAILED) {
      DO_TRACE_L(rs->ts, TRACE_EVENT_DATA, outPort, pkt->id, 0);
    }
  }
  else {
    if (rs->traceType == TRACE_TYPE_DETAILED) {
      DO_TRACE_L(rs->ts, TRACE_EVENT_DATA, outPort, 0, 0);
    }           
  }
  switch (cbp->op) {
  
  case OP_SENT_CB:
    if (cbp->rv == RV_SUCCEED) {
      /* --- sent successfully */
      rs->outQueueCnt[outPort]--;
      rs->outQueueLen[outPort] -= pkt->len;
      red_opkt((RedState *)rs->outState[outPort]);
    
      t = traceGetTime();
      if ((itp = rs->traceOut[outPort] )!= NULL)
        TRACE_INOUT(itp, pkt->len, t);
      if ((mtp=rs->traceQueue[outPort]) != NULL)
        TRACE_QUEUE(mtp, rs->outQueueCnt[outPort], t);
      if ((mtp=rs->traceQueueLen[outPort]) != NULL)
        TRACE_QUEUE(mtp, rs->outQueueLen[outPort]/1024, t);
    
      if (rs->traceType == TRACE_TYPE_DETAILED) {
        DO_TRACE_L(rs->ts, TRACE_EVENT_SENT_OKAY, pkt->len,
                   rs->outQueueCnt[outPort], outPort);
      } 
/*       else { */
/*      DO_TRACE_WT(rs->ts, TRACE_EVENT_QUEUE, rs->outQueueCnt[outPort],  */
/*                  outPort); */
/*       } */
      xsimDbg(SL2_FLAG, printf("[RED cb] %s op:SENT_CB succeeded, q:%d\n",
                               rs->name,
                               rs->outQueueCnt[outPort]));
      rs->outQueueBeg[outPort] = rs->outQueueBeg[outPort]->next;
      rs->outRetryCnt[outPort] = 1;
      rs->outRetryDelay[outPort] = 1;
      if (rs->outQueueBeg[outPort] == NULL) {
        rs->outQueueEnd[outPort] = NULL;
        freeCallBack(cbp);
      }
      else
        sim_RED_send(NULL, (void *)cbp);
    }   
    else {
      /* --- send failed, try again */
      /* --- Should I do exp backoff? */
      xsimDbg(SPC_FLAG, printf("[RED cb] %s op:SENT_CB failed, q:%d\n",
                               rs->name,
                               rs->outQueueCnt[outPort]));
      if (++(rs->outRetryCnt[outPort]) > 15) { 
        printf("WARNING in RED router, 15 retries already, dropping pkt\n");
        if (rs->traceType == TRACE_TYPE_DETAILED) {
          DO_TRACE_L(rs->ts, TRACE_EVENT_DROP, pkt->len,
                     rs->outQueueCnt[outPort], outPort);
        }         
        else {
          DO_TRACE_WT(rs->ts, TRACE_EVENT_DROP, pkt->len, outPort);
        }
        rs->outQueueCnt[outPort]--;
        red_opkt((RedState *)rs->outState[outPort]);
        /* --- Need to destroy packet */
        msgDestroy(&pkt->msg);
        rs->outQueueBeg[outPort] = rs->outQueueBeg[outPort]->next;
        freeSimPacket(pkt);
        rs->outRetryCnt[outPort] = 1;
        rs->outRetryDelay[outPort] = 1;
        if (rs->outQueueBeg[outPort] == NULL) {
          rs->outQueueEnd[outPort] = NULL;
          freeCallBack(cbp);
        }
        else      
          sim_RED_send(NULL, (void *)cbp);
      } 
      else {
        rs->outRetryDelay[outPort] *= 2;
        rvar = lrand48() % rs->outRetryDelay[outPort] + 1;
        xsimDbg(SPC_FLAG, printf("[RED cb] %s delaying for:%d slots\n",
                                 rs->name, rvar));
        evDetach(evSchedule(sim_RED_send, (void *)cbp, rvar*51));  
        if (rs->traceType == TRACE_TYPE_DETAILED) {
          DO_TRACE_L(rs->ts, TRACE_EVENT_BACKOFF, rvar*51,
                     rs->outQueueCnt[outPort], 0);  
          DO_TRACE_L(rs->ts, TRACE_EVENT_DATA, rs->outRetryCnt[outPort],
                     rs->outRetryDelay[outPort], 0);
        }
      } 
    }   
    break;
        
  case OP_NOTBUSY_CB:
    xsimDbg(SL2_FLAG, printf("[RED cb] %s op:NOTBUSY_CB, q:%d\n",
                             rs->name,
                             rs->outQueueCnt[outPort]));
    if ((pkt = rs->outQueueBeg[outPort]) != NULL)
      sim_RED_send(NULL, (void *)cbp);
    else
      freeCallBack(cbp);
    break;
        
  default:                       
    printf("ERROR: Unknown callback (op: %d) in sim_RED_callback\n", cbp->op);
    freeCallBack(cbp);
  }       
}                    
          
void                 
sim_RED_input (ROUTER_STATE *rs, SimPacket *pkt, int inPort)
{     
  int           outPort, sendit=1;
  long 		t;	/* venkat: changed from int */
  void		*buf;
  IPheader      ihdr;
  Simhost       nextHop;
  Net           *np; 
  ITrace        *itp; 
  MaxMinTrace   *mtp;
                  
  xsimDbg(SL2_FLAG,
          printf("> RED_input %s, for packet %d at port %d\n",
                 rs->name, pkt->id, inPort));
      
  if (rs->traceType == TRACE_TYPE_DETAILED) {
    DO_TRACE_WT(rs->ts, TRACE_EVENT_IN, pkt->len, inPort);
    DO_TRACE_L(rs->ts, TRACE_EVENT_DATA, 0, pkt->id, 0);
  } 
  t = traceGetTime(); 
  if ((itp = rs->traceIn[inPort] )!= NULL) {
    TRACE_INOUT(itp, pkt->len, t);
  }       

  if (rs->inPortNets[inPort]->type == TYPE_ETH || pkt->type == TYPE_ETH) {
     /* venkat: changed to Pop from Peek TRUE */
    buf = msgPop(&pkt->msg, sizeof(ETHhdr));
    xAssert(buf);
    ethdMsgLoad(&pkt->ehdr, buf, sizeof(ETHhdr), 0);

    /* venkat: changed from msgPeek FALSE to msgPeek */
    buf = msgPeek(&pkt->msg, sizeof(IPheader));
    xAssert(buf);
    ipStdHdrLoad(&ihdr, buf, sizeof(IPheader), 0);

    pkt->dst.type = TYPE_IP;
    pkt->dst.addr.ip = ihdr.dest;
    pkt->len -= sizeof(ETHhdr);

/*  buf = msgPush(&pkt->msg, sizeof(IPheader));
    xAssert(buf);
    ipHdrStore(&ihdr, buf, sizeof(IPheader), 0);
*/
    xsimDbg(SL2_FLAG,
            printf(">    input packet is type ETH, final dest: [%s]\n",
                   sim_simaddr2str(&pkt->dst)));
  }       
                 
  if (sim_getNextHop(rs, &pkt->dst.addr.ip, &outPort, &nextHop)) {
    if (rs->traceType == TRACE_TYPE_DETAILED) {
      DO_TRACE_L(rs->ts, TRACE_EVENT_ERROR, pkt->len, 0, inPort);
    }
    else {
      DO_TRACE_WT(rs->ts, TRACE_EVENT_ERROR, pkt->len, inPort);
    }
    printf("getNextHop error in RED_input\n");
    msgDestroy(&pkt->msg);
    freeSimPacket(pkt);
  }
  
  if ((itp = rs->traceInOut[outPort] )!= NULL) 
    TRACE_INOUT(itp, pkt->len, t);
  if (outPort == 0)
    printf("avg queue size is %d\n",((RedState *)rs->outState[outPort])->save_avg);
  if (rs->outQueueCnt[outPort] >= rs->defBufferCnt  ||
      red_ipkt((RedState *)rs->outState[outPort]) == DROP_IT) {
    /* --- dropping packet */
    if (rs->traceType != TRACE_TYPE_DETAILED) {
      DO_TRACE_WT(rs->ts, TRACE_EVENT_DROP, pkt->len, outPort);
    }
    else {  
      DO_TRACE_L(rs->ts, TRACE_EVENT_DROP, pkt->len, rs->outQueueCnt[outPort],
                 outPort);
    }            
    xsimDbg(SL2_FLAG,
            printf(">   output port %d full!, dropping packet\n", outPort));
    msgDestroy(&pkt->msg);
    freeSimPacket(pkt);
    return;
  }
  rs->outQueueCnt[outPort]++;
  rs->outQueueLen[outPort] += pkt->len;
  if ((mtp=rs->traceQueue[outPort]) != NULL) 
    TRACE_QUEUE(mtp, rs->outQueueCnt[outPort], t);
  if ((mtp=rs->traceQueueLen[outPort]) != NULL) 
    TRACE_QUEUE(mtp, rs->outQueueLen[outPort]/1024, t);
   
  if (rs->outQueueEnd[outPort] == NULL) {
    rs->outQueueBeg[outPort] = rs->outQueueEnd[outPort] = pkt;
    rs->outRetryCnt[outPort] = 1;
    rs->outRetryDelay[outPort] = 1;
  } 
  else {
    sendit = 0;
    rs->outQueueEnd[outPort]->next = pkt;
    rs->outQueueEnd[outPort] = pkt;
  }              
  pkt->next = NULL;
/*   rs->outQueuedCnt[outPort]++; */
  pkt->src = rs->myAddr[outPort];
  pkt->hop = nextHop;
  np = rs->outPortNets[outPort];
    
  if (nextHop.type == TYPE_ETH) {
    pkt->type = TYPE_ETH;
    pkt->len += sizeof(ETHhdr);
    rs->outQueueLen[outPort] += sizeof(ETHhdr);    
    pkt->ehdr.src = rs->myAddr[outPort].addr.eth; 
    pkt->ehdr.dst = nextHop.addr.eth;
    xsimDbg(SL2_FLAG,
            printf(">    sending on ETH to %s\n",
                   sim_addr2str(&pkt->ehdr.dst, TYPE_ETH)));  

    buf = msgPush(&pkt->msg, sizeof(ETHhdr));
    xAssert(buf);
    ethdMsgStore(&pkt->ehdr, buf, sizeof(ETHhdr), 0);

    pkt->net = np;
  } 
  else if (nextHop.type = TYPE_IP) {
    pkt->type = TYPE_IP;
    pkt->net = rs->outPortNets[outPort]; 
  } 
  else {         
    Kabort("Wrong type in FSCS_input\n");
  }  
/*   rs->delay = 0; */
  if (rs->traceType == TRACE_TYPE_DETAILED) {
    DO_TRACE_L(rs->ts, TRACE_EVENT_QUEUE, outPort, rs->outQueueCnt[outPort],
               0);
  }
/*   else { */
/*     DO_TRACE_WT(rs->ts, TRACE_EVENT_QUEUE, rs->outQueueCnt[outPort], outPort
/*   } */
  if (sendit) {
    if (np->control(np, OP_ISBUSY, NULL, NULL, NULL, NULL)) {
      if (rs->traceType == TRACE_TYPE_DETAILED) {
        DO_TRACE_L(rs->ts, TRACE_EVENT_SEND_BUSY, rs->outQueueCnt[outPort],
                   pkt->id, outPort);
      }
      np->control(np, OP_NOTBUSY_CB, rs->cbFun, (void *)rs,
                  (void *)outPort, NULL);
    }
    else {
      if (rs->traceType == TRACE_TYPE_DETAILED) {
        DO_TRACE_L(rs->ts, TRACE_EVENT_SEND_OKAY, pkt->len, pkt->id, outPort);
      }
      np->control(np, OP_SEND, rs->cbFun, (void *)rs, (void *)outPort,
                  (void *)pkt);
    }
  }   
}