sys/netpfil/ipfw/dn_sched_fq_codel.h

   1 /*-
   2  * Copyright (C) 2016 Centre for Advanced Internet Architectures,
   3  *  Swinburne University of Technology, Melbourne, Australia.
   4  * Portions of this code were made possible in part by a gift from
   5  *  The Comcast Innovation Fund.
   6  * Implemented by Rasool Al-Saadi <ralsaadi@swin.edu.au>
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  20  * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  27  * SUCH DAMAGE.
  28  */
  29
  30 /*
  31  * FQ_Codel Structures and helper functions
  32  *
  33  * $FreeBSD$
  34  */
  35
  36 #ifndef _IP_DN_SCHED_FQ_CODEL_H
  37 #define _IP_DN_SCHED_FQ_CODEL_H
  38
  39 /* list of queues */
  40 STAILQ_HEAD(fq_codel_list, fq_codel_flow) ;
  41
  42 /* fq_codel parameters including codel */
  43 struct dn_sch_fq_codel_parms {
  44         struct dn_aqm_codel_parms       ccfg;   /* CoDel Parameters */
  45         /* FQ_CODEL Parameters */
  46         uint32_t flows_cnt;     /* number of flows */
  47         uint32_t limit; /* hard limit of fq_codel queue size*/
  48         uint32_t quantum;
  49 };      /* defaults */
  50
  51 /* flow (sub-queue) stats */
  52 struct flow_stats {
  53         uint64_t tot_pkts;      /* statistics counters  */
  54         uint64_t tot_bytes;
  55         uint32_t length;                /* Queue length, in packets */
  56         uint32_t len_bytes;     /* Queue length, in bytes */
  57         uint32_t drops;
  58 };
  59
  60 /* A flow of packets (sub-queue).*/
  61 struct fq_codel_flow {
  62         struct mq       mq;     /* list of packets */
  63         struct flow_stats stats;        /* statistics */
  64         int     deficit;
  65         int active;             /* 1: flow is active (in a list) */
  66         struct codel_status cst;
  67         STAILQ_ENTRY(fq_codel_flow) flowchain;
  68 };
  69
  70 /* extra fq_codel scheduler configurations */
  71 struct fq_codel_schk {
  72         struct dn_sch_fq_codel_parms cfg;
  73 };
  74
  75 /* fq_codel scheduler instance */
  76 struct fq_codel_si {
  77         struct dn_sch_inst _si; /* standard scheduler instance */
  78         struct dn_queue main_q; /* main queue is after si directly */
  79
  80         struct fq_codel_flow *flows; /* array of flows (queues) */
  81         uint32_t perturbation; /* random value */
  82         struct fq_codel_list newflows;  /* list of new queues */
  83         struct fq_codel_list oldflows;          /* list of old queues */
  84 };
  85
  86 /* Helper function to update queue&main-queue and scheduler statistics.
  87  * negative len + drop -> drop
  88  * negative len -> dequeue
  89  * positive len -> enqueue
  90  * positive len + drop -> drop during enqueue
  91  */
  92 __inline static void
  93 fq_update_stats(struct fq_codel_flow *q, struct fq_codel_si *si, int len,
  94         int drop)
  95 {
  96         int inc = 0;
  97
  98         if (len < 0)
  99                 inc = -1;
 100         else if (len > 0)
 101                 inc = 1;
 102
 103         if (drop) {
 104                 si->main_q.ni.drops ++;
 105                 q->stats.drops ++;
 106                 si->_si.ni.drops ++;
 107                 io_pkt_drop ++;
 108         }
 109
 110         if (!drop || (drop && len < 0)) {
 111                 /* Update stats for the main queue */
 112                 si->main_q.ni.length += inc;
 113                 si->main_q.ni.len_bytes += len;
 114
 115                 /*update sub-queue stats */
 116                 q->stats.length += inc;
 117                 q->stats.len_bytes += len;
 118
 119                 /*update scheduler instance stats */
 120                 si->_si.ni.length += inc;
 121                 si->_si.ni.len_bytes += len;
 122         }
 123
 124         if (inc > 0) {
 125                 si->main_q.ni.tot_bytes += len;
 126                 si->main_q.ni.tot_pkts ++;
 127
 128                 q->stats.tot_bytes +=len;
 129                 q->stats.tot_pkts++;
 130
 131                 si->_si.ni.tot_bytes +=len;
 132                 si->_si.ni.tot_pkts ++;
 133         }
 134
 135 }
 136
 137 /* extract the head of fq_codel sub-queue */
 138 __inline static struct mbuf *
 139 fq_codel_extract_head(struct fq_codel_flow *q, aqm_time_t *pkt_ts, struct fq_codel_si *si)
 140 {
 141         struct mbuf *m = q->mq.head;
 142
 143         if (m == NULL)
 144                 return m;
 145         q->mq.head = m->m_nextpkt;
 146
 147         fq_update_stats(q, si, -m->m_pkthdr.len, 0);
 148
 149         if (si->main_q.ni.length == 0) /* queue is now idle */
 150                         si->main_q.q_time = dn_cfg.curr_time;
 151
 152         /* extract packet timestamp*/
 153         struct m_tag *mtag;
 154         mtag = m_tag_locate(m, MTAG_ABI_COMPAT, DN_AQM_MTAG_TS, NULL);
 155         if (mtag == NULL){
 156                 D("timestamp tag is not found!");
 157                 *pkt_ts = 0;
 158         } else {
 159                 *pkt_ts = *(aqm_time_t *)(mtag + 1);
 160                 m_tag_delete(m,mtag);
 161         }
 162
 163         return m;
 164 }
 165
 166
 167 #endif