sys/netpfil/ipfw/dn_aqm_codel.h

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