sys/netpfil/ipfw/dn_sched_fq_codel_helper.h

   1 /*
   2  * Codel - The Controlled-Delay Active Queue Management algorithm.
   3  *
   4  * Copyright (C) 2016 Centre for Advanced Internet Architectures,
   5  *  Swinburne University of Technology, Melbourne, Australia.
   6  * Portions of this code were made possible in part by a gift from
   7  *  The Comcast Innovation Fund.
   8  * Implemented by Rasool Al-Saadi <ralsaadi@swin.edu.au>
   9  *
  10  * Copyright (C) 2011-2014 Kathleen Nichols <nichols@pollere.com>.
  11  *
  12  * Redistribution and use in source and binary forms, with or without
  13  * modification, are permitted provided that the following conditions
  14  * are met:
  15  *
  16  * o  Redistributions of source code must retain the above copyright
  17  *  notice, this list of conditions, and the following disclaimer,
  18  *  without modification.
  19  *
  20  * o  Redistributions in binary form must reproduce the above copyright
  21  *  notice, this list of conditions and the following disclaimer in
  22  *  the documentation and/or other materials provided with the
  23  *  distribution.
  24  *
  25  * o  The names of the authors may not be used to endorse or promote
  26  *  products derived from this software without specific prior written
  27  *  permission.
  28  *
  29  * Alternatively, provided that this notice is retained in full, this
  30  * software may be distributed under the terms of the GNU General Public
  31  * License ("GPL") version 2, in which case the provisions of the GPL
  32  * apply INSTEAD OF those given above.
  33
  34  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  35  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  36  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  37  * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT
  38  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  39  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  40  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  41  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  42  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  43  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  44  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  45  */
  46
  47 #ifndef _IP_DN_SCHED_FQ_CODEL_HELPER_H
  48 #define _IP_DN_SCHED_FQ_CODEL_HELPER_H
  49
  50 __inline static struct mbuf *
  51 fqc_dodequeue(struct fq_codel_flow *q, aqm_time_t now, uint16_t *ok_to_drop,
  52         struct fq_codel_si *si)
  53 {
  54         struct mbuf * m;
  55         struct fq_codel_schk *schk = (struct fq_codel_schk *)(si->_si.sched+1);
  56         aqm_time_t  pkt_ts, sojourn_time;
  57
  58         *ok_to_drop = 0;
  59         m = fq_codel_extract_head(q, &pkt_ts, si);
  60
  61         if (m == NULL) {
  62                 /*queue is empty - we can't be above target*/
  63                 q->cst.first_above_time= 0;
  64                 return m;
  65         }
  66
  67         /* To span a large range of bandwidths, CoDel runs two
  68          * different AQMs in parallel. One is sojourn-time-based
  69          * and takes effect when the time to send an MTU-sized
  70          * packet is less than target.  The 1st term of the "if"
  71          * below does this.  The other is backlog-based and takes
  72          * effect when the time to send an MTU-sized packet is >=
  73         * target. The goal here is to keep the output link
  74         * utilization high by never allowing the queue to get
  75         * smaller than the amount that arrives in a typical
  76          * interarrival time (MTU-sized packets arriving spaced
  77          * by the amount of time it takes to send such a packet on
  78          * the bottleneck). The 2nd term of the "if" does this.
  79          */
  80         sojourn_time = now - pkt_ts;
  81         if (sojourn_time < schk->cfg.ccfg.target || q->stats.len_bytes <= q->cst.maxpkt_size) {
  82                 /* went below - stay below for at least interval */
  83                 q->cst.first_above_time = 0;
  84         } else {
  85                 if (q->cst.first_above_time == 0) {
  86                         /* just went above from below. if still above at
  87                          * first_above_time, will say it's ok to drop. */
  88                         q->cst.first_above_time = now + schk->cfg.ccfg.interval;
  89                 } else if (now >= q->cst.first_above_time) {
  90                         *ok_to_drop = 1;
  91                 }
  92         }
  93         return m;
  94 }
  95
  96 /* Codel dequeue function */
  97 __inline static struct mbuf *
  98 fqc_codel_dequeue(struct fq_codel_flow *q, struct fq_codel_si *si)
  99 {
 100         struct mbuf *m;
 101         struct dn_aqm_codel_parms *cprms;
 102         struct codel_status *cst;
 103         aqm_time_t now;
 104         uint16_t ok_to_drop;
 105         struct fq_codel_schk *schk = (struct fq_codel_schk *)(si->_si.sched+1);
 106
 107         cst = &q->cst;
 108         cprms = &schk->cfg.ccfg;
 109
 110         now = AQM_UNOW;
 111         m = fqc_dodequeue(q, now, &ok_to_drop, si);
 112
 113         if (cst->dropping) {
 114                 if (!ok_to_drop) {
 115                         /* sojourn time below target - leave dropping state */
 116                         cst->dropping = false;
 117                 }
 118
 119                 /* Time for the next drop. Drop current packet and dequeue
 120                  * next.  If the dequeue doesn't take us out of dropping
 121                  * state, schedule the next drop. A large backlog might
 122                  * result in drop rates so high that the next drop should
 123                  * happen now, hence the 'while' loop.
 124                  */
 125                 while (now >= cst->drop_next_time && cst->dropping) {
 126                         /* mark the packet */
 127                         if (cprms->flags & CODEL_ECN_ENABLED && ecn_mark(m)) {
 128                                 cst->count++;
 129                                 /* schedule the next mark. */
 130                                 cst->drop_next_time = control_law(cst, cprms, cst->drop_next_time);
 131                                 return m;
 132                         }
 133
 134                         /* drop the packet */
 135                         fq_update_stats(q, si, 0, 1);
 136                         m_freem(m);
 137                         m = fqc_dodequeue(q, now, &ok_to_drop, si);
 138
 139                         if (!ok_to_drop) {
 140                                 /* leave dropping state */
 141                                 cst->dropping = false;
 142                         } else {
 143                                 cst->count++;
 144                                 /* schedule the next drop. */
 145                                 cst->drop_next_time = control_law(cst, cprms, cst->drop_next_time);
 146                         }
 147                 }
 148         /* If we get here we're not in dropping state. The 'ok_to_drop'
 149          * return from dodequeue means that the sojourn time has been
 150          * above 'target' for 'interval' so enter dropping state.
 151          */
 152         } else if (ok_to_drop) {
 153                 /* if ECN option is disabled or the packet cannot be marked,
 154                  * drop the packet and extract another.
 155                  */
 156                 if (!(cprms->flags & CODEL_ECN_ENABLED) || !ecn_mark(m)) {
 157                         fq_update_stats(q, si, 0, 1);
 158                         m_freem(m);
 159                         m = fqc_dodequeue(q, now, &ok_to_drop,si);
 160                 }
 161
 162                 cst->dropping = true;
 163
 164                 /* If min went above target close to when it last went
 165                  * below, assume that the drop rate that controlled the
 166                  * queue on the last cycle is a good starting point to
 167                  * control it now. ('drop_next' will be at most 'interval'
 168                  * later than the time of the last drop so 'now - drop_next'
 169                  * is a good approximation of the time from the last drop
 170                  * until now.)
 171                  */
 172                 cst->count = (cst->count > 2 && ((aqm_stime_t)now -
 173                         (aqm_stime_t)cst->drop_next_time) < 8* cprms->interval)? cst->count - 2 : 1;
 174
 175                 /* we don't have to set initial guess for Newton's method isqrt as
 176                  * we initilaize  isqrt in control_law function when count == 1 */
 177                 cst->drop_next_time = control_law(cst, cprms, now);
 178         }
 179
 180         return m;
 181 }
 182
 183 #endif