The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/netpfil/ipfw/dn_sched_fq_codel_helper.h

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

    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_SCHED_FQ_CODEL_HELPER_H
   50 #define _IP_DN_SCHED_FQ_CODEL_HELPER_H
   51 
   52 __inline static struct mbuf *
   53 fqc_dodequeue(struct fq_codel_flow *q, aqm_time_t now, uint16_t *ok_to_drop,
   54         struct fq_codel_si *si)
   55 {
   56         struct mbuf * m;
   57         struct fq_codel_schk *schk = (struct fq_codel_schk *)(si->_si.sched+1);
   58         aqm_time_t  pkt_ts, sojourn_time;
   59 
   60         *ok_to_drop = 0;
   61         m = fq_codel_extract_head(q, &pkt_ts, si);
   62 
   63         if (m == NULL) {
   64                 /*queue is empty - we can't be above target*/
   65                 q->cst.first_above_time= 0;
   66                 return m;
   67         }
   68 
   69         /* To span a large range of bandwidths, CoDel runs two
   70          * different AQMs in parallel. One is sojourn-time-based
   71          * and takes effect when the time to send an MTU-sized
   72          * packet is less than target.  The 1st term of the "if"
   73          * below does this.  The other is backlog-based and takes
   74          * effect when the time to send an MTU-sized packet is >=
   75         * target. The goal here is to keep the output link
   76         * utilization high by never allowing the queue to get
   77         * smaller than the amount that arrives in a typical
   78          * interarrival time (MTU-sized packets arriving spaced
   79          * by the amount of time it takes to send such a packet on
   80          * the bottleneck). The 2nd term of the "if" does this.
   81          */
   82         sojourn_time = now - pkt_ts;
   83         if (sojourn_time < schk->cfg.ccfg.target || q->stats.len_bytes <= q->cst.maxpkt_size) {
   84                 /* went below - stay below for at least interval */
   85                 q->cst.first_above_time = 0;
   86         } else {
   87                 if (q->cst.first_above_time == 0) {
   88                         /* just went above from below. if still above at
   89                          * first_above_time, will say it's ok to drop. */
   90                         q->cst.first_above_time = now + schk->cfg.ccfg.interval;
   91                 } else if (now >= q->cst.first_above_time) {
   92                         *ok_to_drop = 1;
   93                 }
   94         }
   95         return m;
   96 }
   97 
   98 /* Codel dequeue function */
   99 __inline static struct mbuf * 
  100 fqc_codel_dequeue(struct fq_codel_flow *q, struct fq_codel_si *si)
  101 {
  102         struct mbuf *m;
  103         struct dn_aqm_codel_parms *cprms;
  104         struct codel_status *cst;
  105         aqm_time_t now;
  106         uint16_t ok_to_drop;
  107         struct fq_codel_schk *schk = (struct fq_codel_schk *)(si->_si.sched+1);
  108 
  109         cst = &q->cst;
  110         cprms = &schk->cfg.ccfg;
  111 
  112         now = AQM_UNOW;
  113         m = fqc_dodequeue(q, now, &ok_to_drop, si);
  114 
  115         if (cst->dropping) {
  116                 if (!ok_to_drop) {
  117                         /* sojourn time below target - leave dropping state */
  118                         cst->dropping = false;
  119                 }
  120 
  121                 /* Time for the next drop. Drop current packet and dequeue
  122                  * next.  If the dequeue doesn't take us out of dropping
  123                  * state, schedule the next drop. A large backlog might
  124                  * result in drop rates so high that the next drop should
  125                  * happen now, hence the 'while' loop.
  126                  */
  127                 while (now >= cst->drop_next_time && cst->dropping) {
  128                         /* mark the packet */
  129                         if (cprms->flags & CODEL_ECN_ENABLED && ecn_mark(m)) {
  130                                 cst->count++;
  131                                 /* schedule the next mark. */
  132                                 cst->drop_next_time = control_law(cst, cprms, cst->drop_next_time);
  133                                 return m;
  134                         }
  135 
  136                         /* drop the packet */
  137                         fq_update_stats(q, si, 0, 1);
  138                         m_freem(m);
  139                         m = fqc_dodequeue(q, now, &ok_to_drop, si);
  140 
  141                         if (!ok_to_drop) {
  142                                 /* leave dropping state */
  143                                 cst->dropping = false;
  144                         } else {
  145                                 cst->count++;
  146                                 /* schedule the next drop. */
  147                                 cst->drop_next_time = control_law(cst, cprms, cst->drop_next_time);
  148                         }
  149                 }
  150         /* If we get here we're not in dropping state. The 'ok_to_drop'
  151          * return from dodequeue means that the sojourn time has been
  152          * above 'target' for 'interval' so enter dropping state.
  153          */
  154         } else if (ok_to_drop) {
  155                 /* if ECN option is disabled or the packet cannot be marked,
  156                  * drop the packet and extract another.
  157                  */
  158                 if (!(cprms->flags & CODEL_ECN_ENABLED) || !ecn_mark(m)) {
  159                         fq_update_stats(q, si, 0, 1);
  160                         m_freem(m);
  161                         m = fqc_dodequeue(q, now, &ok_to_drop,si);
  162                 }
  163 
  164                 cst->dropping = true;
  165 
  166                 /* If min went above target close to when it last went
  167                  * below, assume that the drop rate that controlled the
  168                  * queue on the last cycle is a good starting point to
  169                  * control it now. ('drop_next' will be at most 'interval'
  170                  * later than the time of the last drop so 'now - drop_next'
  171                  * is a good approximation of the time from the last drop
  172                  * until now.)
  173                  */
  174                 cst->count = (cst->count > 2 && ((aqm_stime_t)now - 
  175                         (aqm_stime_t)cst->drop_next_time) < 8* cprms->interval)? cst->count - 2 : 1;
  176 
  177                 /* we don't have to set initial guess for Newton's method isqrt as
  178                  * we initilaize  isqrt in control_law function when count == 1 */
  179                 cst->drop_next_time = control_law(cst, cprms, now);
  180         }
  181 
  182         return m;
  183 }
  184 
  185 #endif

Cache object: 66258041437e0a85fd2ae64464f9fb72


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.