dn_aqm_pie.c

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  * PIE - Proportional Integral controller Enhanced AQM 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  * Redistribution and use in source and binary forms, with or without
   13  * modification, are permitted provided that the following conditions
   14  * are met:
   15  * 1. Redistributions of source code must retain the above copyright
   16  *    notice, this list of conditions and the following disclaimer.
   17  * 2. Redistributions in binary form must reproduce the above copyright
   18  *    notice, this list of conditions and the following disclaimer in the
   19  *    documentation and/or other materials provided with the distribution.
   20  *
   21  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
   22  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   23  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   24  * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
   25  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   26  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
   27  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   28  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
   30  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   31  * SUCH DAMAGE.
   32  */
   33 
   34 #include <sys/cdefs.h>
   35 #include "opt_inet6.h"
   36 
   37 #include <sys/param.h>
   38 #include <sys/systm.h>
   39 #include <sys/malloc.h>
   40 #include <sys/mbuf.h>
   41 #include <sys/kernel.h>
   42 #include <sys/lock.h>
   43 #include <sys/module.h>
   44 #include <sys/mutex.h>
   45 #include <sys/priv.h>
   46 #include <sys/proc.h>
   47 #include <sys/rwlock.h>
   48 #include <sys/socket.h>
   49 #include <sys/time.h>
   50 #include <sys/sysctl.h>
   51 
   52 #include <net/if.h>     /* IFNAMSIZ, struct ifaddr, ifq head, lock.h mutex.h */
   53 #include <net/netisr.h>
   54 #include <net/vnet.h>
   55 
   56 #include <netinet/in.h>
   57 #include <netinet/ip.h>         /* ip_len, ip_off */
   58 #include <netinet/ip_var.h>     /* ip_output(), IP_FORWARDING */
   59 #include <netinet/ip_fw.h>
   60 #include <netinet/ip_dummynet.h>
   61 #include <netinet/if_ether.h> /* various ether_* routines */
   62 #include <netinet/ip6.h>       /* for ip6_input, ip6_output prototypes */
   63 #include <netinet6/ip6_var.h>
   64 #include <netpfil/ipfw/dn_heap.h>
   65 
   66 #ifdef NEW_AQM
   67 #include <netpfil/ipfw/ip_fw_private.h>
   68 #include <netpfil/ipfw/ip_dn_private.h>
   69 #include <netpfil/ipfw/dn_aqm.h>
   70 #include <netpfil/ipfw/dn_aqm_pie.h>
   71 #include <netpfil/ipfw/dn_sched.h>
   72 
   73 /* for debugging */
   74 #include <sys/syslog.h>
   75 
   76 static struct dn_aqm pie_desc;
   77 
   78 /*  PIE defaults
   79  * target=15ms, tupdate=15ms, max_burst=150ms, 
   80  * max_ecnth=0.1, alpha=0.125, beta=1.25, 
   81  */
   82 struct dn_aqm_pie_parms pie_sysctl = 
   83         { 15 * AQM_TIME_1MS,  15 * AQM_TIME_1MS, 150 * AQM_TIME_1MS,
   84         PIE_SCALE/10 , PIE_SCALE * 0.125,  PIE_SCALE * 1.25 ,
   85         PIE_CAPDROP_ENABLED | PIE_DEPRATEEST_ENABLED | PIE_DERAND_ENABLED };
   86 
   87 static int
   88 pie_sysctl_alpha_beta_handler(SYSCTL_HANDLER_ARGS)
   89 {
   90         int error;
   91         long  value;
   92 
   93         if (!strcmp(oidp->oid_name,"alpha"))
   94                 value = pie_sysctl.alpha;
   95         else
   96                 value = pie_sysctl.beta;
   97                 
   98         value = value * 1000 / PIE_SCALE;
   99         error = sysctl_handle_long(oidp, &value, 0, req);
  100         if (error != 0 || req->newptr == NULL)
  101                 return (error);
  102         if (value < 1 || value > 7 * PIE_SCALE)
  103                 return (EINVAL);
  104         value = (value * PIE_SCALE) / 1000;
  105         if (!strcmp(oidp->oid_name,"alpha"))
  106                         pie_sysctl.alpha = value;
  107         else
  108                 pie_sysctl.beta = value;
  109         return (0);
  110 }
  111 
  112 static int
  113 pie_sysctl_target_tupdate_maxb_handler(SYSCTL_HANDLER_ARGS)
  114 {
  115         int error;
  116         long  value;
  117 
  118         if (!strcmp(oidp->oid_name,"target"))
  119                 value = pie_sysctl.qdelay_ref;
  120         else if (!strcmp(oidp->oid_name,"tupdate"))
  121                 value = pie_sysctl.tupdate;
  122         else
  123                 value = pie_sysctl.max_burst;
  124 
  125         value = value / AQM_TIME_1US;
  126         error = sysctl_handle_long(oidp, &value, 0, req);
  127         if (error != 0 || req->newptr == NULL)
  128                 return (error);
  129         if (value < 1 || value > 10 * AQM_TIME_1S)
  130                 return (EINVAL);
  131         value = value * AQM_TIME_1US;
  132 
  133         if (!strcmp(oidp->oid_name,"target"))
  134                 pie_sysctl.qdelay_ref  = value;
  135         else if (!strcmp(oidp->oid_name,"tupdate"))
  136                 pie_sysctl.tupdate  = value;
  137         else
  138                 pie_sysctl.max_burst = value;
  139         return (0);
  140 }
  141 
  142 static int
  143 pie_sysctl_max_ecnth_handler(SYSCTL_HANDLER_ARGS)
  144 {
  145         int error;
  146         long  value;
  147 
  148         value = pie_sysctl.max_ecnth;
  149         value = value * 1000 / PIE_SCALE;
  150         error = sysctl_handle_long(oidp, &value, 0, req);
  151         if (error != 0 || req->newptr == NULL)
  152                 return (error);
  153         if (value < 1 || value > PIE_SCALE)
  154                 return (EINVAL);
  155         value = (value * PIE_SCALE) / 1000;
  156         pie_sysctl.max_ecnth = value;
  157         return (0);
  158 }
  159 
  160 /* define PIE sysctl variables */
  161 SYSBEGIN(f4)
  162 SYSCTL_DECL(_net_inet);
  163 SYSCTL_DECL(_net_inet_ip);
  164 SYSCTL_DECL(_net_inet_ip_dummynet);
  165 static SYSCTL_NODE(_net_inet_ip_dummynet, OID_AUTO, pie,
  166     CTLFLAG_RW | CTLFLAG_MPSAFE, 0,
  167     "PIE");
  168 
  169 #ifdef SYSCTL_NODE
  170 SYSCTL_PROC(_net_inet_ip_dummynet_pie, OID_AUTO, target,
  171     CTLTYPE_LONG | CTLFLAG_RW | CTLFLAG_NEEDGIANT, NULL, 0,
  172     pie_sysctl_target_tupdate_maxb_handler, "L",
  173     "queue target in microsecond");
  174 SYSCTL_PROC(_net_inet_ip_dummynet_pie, OID_AUTO, tupdate,
  175     CTLTYPE_LONG | CTLFLAG_RW | CTLFLAG_NEEDGIANT, NULL, 0,
  176     pie_sysctl_target_tupdate_maxb_handler, "L",
  177     "the frequency of drop probability calculation in microsecond");
  178 SYSCTL_PROC(_net_inet_ip_dummynet_pie, OID_AUTO, max_burst,
  179     CTLTYPE_LONG | CTLFLAG_RW | CTLFLAG_NEEDGIANT, NULL, 0,
  180     pie_sysctl_target_tupdate_maxb_handler, "L",
  181     "Burst allowance interval in microsecond");
  182 
  183 SYSCTL_PROC(_net_inet_ip_dummynet_pie, OID_AUTO, max_ecnth,
  184     CTLTYPE_LONG | CTLFLAG_RW | CTLFLAG_NEEDGIANT, NULL, 0,
  185     pie_sysctl_max_ecnth_handler, "L",
  186     "ECN safeguard threshold scaled by 1000");
  187 
  188 SYSCTL_PROC(_net_inet_ip_dummynet_pie, OID_AUTO, alpha,
  189     CTLTYPE_LONG | CTLFLAG_RW | CTLFLAG_NEEDGIANT, NULL, 0,
  190     pie_sysctl_alpha_beta_handler, "L",
  191     "PIE alpha scaled by 1000");
  192 SYSCTL_PROC(_net_inet_ip_dummynet_pie, OID_AUTO, beta,
  193     CTLTYPE_LONG | CTLFLAG_RW | CTLFLAG_NEEDGIANT, NULL, 0,
  194     pie_sysctl_alpha_beta_handler, "L",
  195     "beta scaled by 1000");
  196 #endif
  197 
  198 /*
  199  * Callout function for drop probability calculation 
  200  * This function is called over tupdate ms and takes pointer of PIE
  201  * status variables as an argument
  202   */
  203 static void
  204 calculate_drop_prob(void *x)
  205 {
  206         int64_t p, prob, oldprob;
  207         struct dn_aqm_pie_parms *pprms;
  208         struct pie_status *pst = (struct pie_status *) x;
  209         int p_isneg;
  210 
  211         pprms = pst->parms;
  212         prob = pst->drop_prob;
  213 
  214         /* calculate current qdelay using DRE method.
  215          * If TS is used and no data in the queue, reset current_qdelay
  216          * as it stays at last value during dequeue process. 
  217         */
  218         if (pprms->flags & PIE_DEPRATEEST_ENABLED)
  219                 pst->current_qdelay = ((uint64_t)pst->pq->ni.len_bytes *
  220                         pst->avg_dq_time) >> PIE_DQ_THRESHOLD_BITS;
  221         else 
  222                 if (!pst->pq->ni.len_bytes)
  223                          pst->current_qdelay = 0;
  224 
  225         /* calculate drop probability */
  226         p = (int64_t)pprms->alpha * 
  227                 ((int64_t)pst->current_qdelay - (int64_t)pprms->qdelay_ref); 
  228         p +=(int64_t) pprms->beta * 
  229                 ((int64_t)pst->current_qdelay - (int64_t)pst->qdelay_old); 
  230 
  231         /* take absolute value so right shift result is well defined */
  232         p_isneg = p < 0;
  233         if (p_isneg) {
  234                 p = -p;
  235         }
  236                 
  237         /* We PIE_MAX_PROB shift by 12-bits to increase the division precision */
  238         p *= (PIE_MAX_PROB << 12) / AQM_TIME_1S;
  239 
  240         /* auto-tune drop probability */
  241         if (prob < (PIE_MAX_PROB / 1000000)) /* 0.000001 */
  242                 p >>= 11 + PIE_FIX_POINT_BITS + 12;
  243         else if (prob < (PIE_MAX_PROB / 100000)) /* 0.00001 */
  244                 p >>= 9 + PIE_FIX_POINT_BITS + 12;
  245         else if (prob < (PIE_MAX_PROB / 10000)) /* 0.0001 */
  246                 p >>= 7 + PIE_FIX_POINT_BITS + 12;
  247         else if (prob < (PIE_MAX_PROB / 1000)) /* 0.001 */
  248                 p >>= 5 + PIE_FIX_POINT_BITS + 12;
  249         else if (prob < (PIE_MAX_PROB / 100)) /* 0.01 */
  250                 p >>= 3 + PIE_FIX_POINT_BITS + 12;
  251         else if (prob < (PIE_MAX_PROB / 10)) /* 0.1 */
  252                 p >>= 1 + PIE_FIX_POINT_BITS + 12;
  253         else
  254                 p >>= PIE_FIX_POINT_BITS + 12;
  255 
  256         oldprob = prob;
  257 
  258         if (p_isneg) {
  259                 prob = prob - p;
  260 
  261                 /* check for multiplication underflow */
  262                 if (prob > oldprob) {
  263                         prob= 0;
  264                         D("underflow");
  265                 }
  266         } else {
  267                 /* Cap Drop adjustment */
  268                 if ((pprms->flags & PIE_CAPDROP_ENABLED) &&
  269                     prob >= PIE_MAX_PROB / 10 &&
  270                     p > PIE_MAX_PROB / 50 ) {
  271                         p = PIE_MAX_PROB / 50;
  272                 }
  273 
  274                 prob = prob + p;
  275 
  276                 /* check for multiplication overflow */
  277                 if (prob<oldprob) {
  278                         D("overflow");
  279                         prob= PIE_MAX_PROB;
  280                 }
  281         }
  282 
  283         /*
  284          * decay the drop probability exponentially
  285          * and restrict it to range 0 to PIE_MAX_PROB
  286          */
  287         if (prob < 0) {
  288                 prob = 0;
  289         } else {
  290                 if (pst->current_qdelay == 0 && pst->qdelay_old == 0) {
  291                         /* 0.98 ~= 1- 1/64 */
  292                         prob = prob - (prob >> 6); 
  293                 }
  294 
  295                 if (prob > PIE_MAX_PROB) {
  296                         prob = PIE_MAX_PROB;
  297                 }
  298         }
  299 
  300         pst->drop_prob = prob;
  301 
  302         /* store current queue delay value in old queue delay*/
  303         pst->qdelay_old = pst->current_qdelay;
  304 
  305         /* update burst allowance */
  306         if ((pst->sflags & PIE_ACTIVE) && pst->burst_allowance>0) {
  307                 
  308                 if (pst->burst_allowance > pprms->tupdate )
  309                         pst->burst_allowance -= pprms->tupdate;
  310                 else 
  311                         pst->burst_allowance = 0;
  312         }
  313 
  314         /* reschedule calculate_drop_prob function */
  315         if (pst->sflags & PIE_ACTIVE)
  316                 callout_reset_sbt(&pst->aqm_pie_callout,
  317                         (uint64_t)pprms->tupdate * SBT_1US, 0, calculate_drop_prob, pst, 0);
  318 
  319         mtx_unlock(&pst->lock_mtx);
  320 }
  321 
  322 /*
  323  * Extract a packet from the head of queue 'q'
  324  * Return a packet or NULL if the queue is empty.
  325  * If getts is set, also extract packet's timestamp from mtag.
  326  */
  327 static struct mbuf *
  328 pie_extract_head(struct dn_queue *q, aqm_time_t *pkt_ts, int getts)
  329 {
  330         struct m_tag *mtag;
  331         struct mbuf *m;
  332 
  333 next:   m = q->mq.head;
  334         if (m == NULL)
  335                 return m;
  336         q->mq.head = m->m_nextpkt;
  337 
  338         /* Update stats */
  339         update_stats(q, -m->m_pkthdr.len, 0);
  340 
  341         if (q->ni.length == 0) /* queue is now idle */
  342                         q->q_time = V_dn_cfg.curr_time;
  343 
  344         if (getts) {
  345                 /* extract packet TS*/
  346                 mtag = m_tag_locate(m, MTAG_ABI_COMPAT, DN_AQM_MTAG_TS, NULL);
  347                 if (mtag == NULL) {
  348                         D("PIE timestamp mtag not found!");
  349                         *pkt_ts = 0;
  350                 } else {
  351                         *pkt_ts = *(aqm_time_t *)(mtag + 1);
  352                         m_tag_delete(m,mtag); 
  353                 }
  354         }
  355         if (m->m_pkthdr.rcvif != NULL &&
  356             __predict_false(m_rcvif_restore(m) == NULL)) {
  357                 m_freem(m);
  358                 goto next;
  359         }
  360         return m;
  361 }
  362 
  363 /* 
  364  * Initiate PIE  variable and optionally activate it
  365  */
  366 __inline static void
  367 init_activate_pie(struct pie_status *pst, int resettimer)
  368 {
  369         struct dn_aqm_pie_parms *pprms;
  370 
  371         mtx_lock(&pst->lock_mtx);
  372         pprms = pst->parms;
  373         pst->drop_prob = 0;
  374         pst->qdelay_old = 0;
  375         pst->burst_allowance = pprms->max_burst;
  376         pst->accu_prob = 0;
  377         pst->dq_count = 0;
  378         pst->avg_dq_time = 0;
  379         pst->sflags = PIE_INMEASUREMENT;
  380         pst->measurement_start = AQM_UNOW;
  381 
  382         if (resettimer) {
  383                 pst->sflags |= PIE_ACTIVE;
  384                 callout_reset_sbt(&pst->aqm_pie_callout,
  385                         (uint64_t)pprms->tupdate * SBT_1US,
  386                         0, calculate_drop_prob, pst, 0);
  387         }
  388         //DX(2, "PIE Activated");
  389         mtx_unlock(&pst->lock_mtx);
  390 }
  391 
  392 /* 
  393  * Deactivate PIE and stop probe update callout 
  394  */
  395 __inline static void
  396 deactivate_pie(struct pie_status *pst)
  397 {
  398         mtx_lock(&pst->lock_mtx);
  399         pst->sflags &= ~(PIE_ACTIVE | PIE_INMEASUREMENT);
  400         callout_stop(&pst->aqm_pie_callout);
  401         //D("PIE Deactivated");
  402         mtx_unlock(&pst->lock_mtx);
  403 }
  404 
  405 /* 
  406  * Dequeue and return a pcaket from queue 'q' or NULL if 'q' is empty.
  407  * Also, caculate depature time or queue delay using timestamp
  408  */
  409 static struct mbuf *
  410 aqm_pie_dequeue(struct dn_queue *q)
  411 {
  412         struct mbuf *m;
  413         struct dn_aqm_pie_parms *pprms;
  414         struct pie_status *pst;
  415         aqm_time_t now;
  416         aqm_time_t pkt_ts, dq_time;
  417         int32_t w;
  418 
  419         pst  = q->aqm_status;
  420         pprms = pst->parms;
  421 
  422         /*we extarct packet ts only when Departure Rate Estimation dis not used*/
  423         m = pie_extract_head(q, &pkt_ts, !(pprms->flags & PIE_DEPRATEEST_ENABLED));
  424 
  425         if (!m || !(pst->sflags & PIE_ACTIVE))
  426                 return m;
  427 
  428         now = AQM_UNOW;
  429         if (pprms->flags & PIE_DEPRATEEST_ENABLED) {
  430                 /* calculate average depature time */
  431                 if(pst->sflags & PIE_INMEASUREMENT) {
  432                         pst->dq_count += m->m_pkthdr.len;
  433 
  434                         if (pst->dq_count >= PIE_DQ_THRESHOLD) {
  435                                 dq_time = now - pst->measurement_start;
  436 
  437                                 /* 
  438                                  * if we don't have old avg dq_time i.e PIE is (re)initialized, 
  439                                  * don't use weight to calculate new avg_dq_time
  440                                  */
  441                                 if(pst->avg_dq_time == 0)
  442                                         pst->avg_dq_time = dq_time;
  443                                 else {
  444                                         /*
  445                                          * weight = PIE_DQ_THRESHOLD/2^6, but we scaled
  446                                          * weight by 2^8. Thus, scaled
  447                                          * weight = PIE_DQ_THRESHOLD /2^8
  448                                          * */
  449                                         w = PIE_DQ_THRESHOLD >> 8;
  450                                         pst->avg_dq_time = (dq_time* w
  451                                                 + (pst->avg_dq_time * ((1L << 8) - w))) >> 8;
  452                                         pst->sflags &= ~PIE_INMEASUREMENT;
  453                                 }
  454                         }
  455                 }
  456 
  457                 /*
  458                  * Start new measurement cycle when the queue has
  459                  * PIE_DQ_THRESHOLD worth of bytes.
  460                  */
  461                 if(!(pst->sflags & PIE_INMEASUREMENT) &&
  462                         q->ni.len_bytes >= PIE_DQ_THRESHOLD) {
  463                         pst->sflags |= PIE_INMEASUREMENT;
  464                         pst->measurement_start = now;
  465                         pst->dq_count = 0;
  466                 }
  467         }
  468         /* Optionally, use packet timestamp to estimate queue delay */
  469         else
  470                 pst->current_qdelay = now - pkt_ts;
  471 
  472         return m;
  473 }
  474 
  475 /*
  476  * Enqueue a packet in q, subject to space and  PIE queue management policy
  477  * (whose parameters are in q->fs).
  478  * Update stats for the queue and the scheduler.
  479  * Return 0 on success, 1 on drop. The packet is consumed anyways.
  480  */
  481 static int
  482 aqm_pie_enqueue(struct dn_queue *q, struct mbuf* m)
  483 {
  484         struct dn_fs *f;
  485         uint64_t len;
  486         uint32_t qlen;
  487         struct pie_status *pst;
  488         struct dn_aqm_pie_parms *pprms;
  489         int t;
  490 
  491         len = m->m_pkthdr.len;
  492         pst  = q->aqm_status;
  493         if(!pst) {
  494                 DX(2, "PIE queue is not initialized\n");
  495                 update_stats(q, 0, 1);
  496                 FREE_PKT(m);
  497                 return 1;
  498         }
  499 
  500         f = &(q->fs->fs);
  501         pprms = pst->parms;
  502         t = ENQUE;
  503 
  504         /* get current queue length in bytes or packets*/
  505         qlen = (f->flags & DN_QSIZE_BYTES) ?
  506                 q->ni.len_bytes : q->ni.length;
  507 
  508         /* check for queue size and drop the tail if exceed queue limit*/
  509         if (qlen >= f->qsize)
  510                 t = DROP;
  511         /* drop/mark the packet when PIE is active and burst time elapsed */
  512         else if ((pst->sflags & PIE_ACTIVE) && pst->burst_allowance==0
  513                         && drop_early(pst, q->ni.len_bytes) == DROP) {
  514                                 /* 
  515                                  * if drop_prob over ECN threshold, drop the packet 
  516                                  * otherwise mark and enqueue it.
  517                                  */
  518                                 if ((pprms->flags & PIE_ECN_ENABLED) && pst->drop_prob <
  519                                         (pprms->max_ecnth << (PIE_PROB_BITS - PIE_FIX_POINT_BITS))
  520                                         && ecn_mark(m))
  521                                         t = ENQUE;
  522                                 else
  523                                         t = DROP;
  524         }
  525 
  526         /* Turn PIE on when 1/3 of the queue is full */ 
  527         if (!(pst->sflags & PIE_ACTIVE) && qlen >= pst->one_third_q_size) {
  528                 init_activate_pie(pst, 1);
  529         }
  530 
  531         /*  Reset burst tolerance and optinally turn PIE off*/
  532         if ((pst->sflags & PIE_ACTIVE) && pst->drop_prob == 0 &&
  533                 pst->current_qdelay < (pprms->qdelay_ref >> 1) &&
  534                 pst->qdelay_old < (pprms->qdelay_ref >> 1)) {
  535                         pst->burst_allowance = pprms->max_burst;
  536                         if ((pprms->flags & PIE_ON_OFF_MODE_ENABLED) && qlen<=0)
  537                                 deactivate_pie(pst);
  538         }
  539 
  540         /* Timestamp the packet if Departure Rate Estimation is disabled */
  541         if (t != DROP && !(pprms->flags & PIE_DEPRATEEST_ENABLED)) {
  542                 /* Add TS to mbuf as a TAG */
  543                 struct m_tag *mtag;
  544                 mtag = m_tag_locate(m, MTAG_ABI_COMPAT, DN_AQM_MTAG_TS, NULL);
  545                 if (mtag == NULL)
  546                         mtag = m_tag_alloc(MTAG_ABI_COMPAT, DN_AQM_MTAG_TS,
  547                                 sizeof(aqm_time_t), M_NOWAIT);
  548                 if (mtag == NULL) {
  549                         t = DROP;
  550                 } else {
  551                         *(aqm_time_t *)(mtag + 1) = AQM_UNOW;
  552                         m_tag_prepend(m, mtag);
  553                 }
  554         }
  555 
  556         if (t != DROP) {
  557                 mq_append(&q->mq, m);
  558                 update_stats(q, len, 0);
  559                 return (0);
  560         } else {
  561                 update_stats(q, 0, 1);
  562 
  563                 /* reset accu_prob after packet drop */
  564                 pst->accu_prob = 0;
  565                 FREE_PKT(m);
  566                 return 1;
  567         }
  568         return 0;
  569 }
  570 
  571 /* 
  572  * initialize PIE for queue 'q' 
  573  * First allocate memory for PIE status.
  574  */
  575 static int
  576 aqm_pie_init(struct dn_queue *q)
  577 {
  578         struct pie_status *pst;
  579         struct dn_aqm_pie_parms *pprms;
  580         int err = 0;
  581 
  582         pprms = q->fs->aqmcfg;
  583 
  584         do { /* exit with break when error occurs*/
  585                 if (!pprms){
  586                         DX(2, "AQM_PIE is not configured");
  587                         err = EINVAL;
  588                         break;
  589                 }
  590 
  591                 q->aqm_status = malloc(sizeof(struct pie_status),
  592                                  M_DUMMYNET, M_NOWAIT | M_ZERO);
  593                 if (q->aqm_status == NULL) {
  594                         D("cannot allocate PIE private data");
  595                         err =  ENOMEM ; 
  596                         break;
  597                 }
  598 
  599                 pst = q->aqm_status;
  600                 dummynet_sched_lock();
  601                 /* increase reference count for PIE module */
  602                 pie_desc.ref_count++;
  603                 dummynet_sched_unlock();
  604                 
  605                 pst->pq = q;
  606                 pst->parms = pprms;
  607                 
  608                 /* For speed optimization, we caculate 1/3 queue size once here */
  609                 // we can use x/3 = (x >>2) + (x >>4) + (x >>7)
  610                 pst->one_third_q_size = q->fs->fs.qsize/3;
  611                 
  612                 mtx_init(&pst->lock_mtx, "mtx_pie", NULL, MTX_DEF);
  613                 callout_init_mtx(&pst->aqm_pie_callout, &pst->lock_mtx,
  614                         CALLOUT_RETURNUNLOCKED);
  615                 
  616                 pst->current_qdelay = 0;
  617                 init_activate_pie(pst, !(pprms->flags & PIE_ON_OFF_MODE_ENABLED));
  618                 
  619                 //DX(2, "aqm_PIE_init");
  620 
  621         } while(0);
  622 
  623         return err;
  624 }
  625 
  626 /* 
  627  * Callout function to destroy pie mtx and free PIE status memory
  628  */
  629 static void
  630 pie_callout_cleanup(void *x)
  631 {
  632         struct pie_status *pst = (struct pie_status *) x;
  633 
  634         mtx_unlock(&pst->lock_mtx);
  635         mtx_destroy(&pst->lock_mtx);
  636         free(x, M_DUMMYNET);
  637         dummynet_sched_lock();
  638         pie_desc.ref_count--;
  639         dummynet_sched_unlock();
  640 }
  641 
  642 /* 
  643  * Clean up PIE status for queue 'q' 
  644  * Destroy memory allocated for PIE status.
  645  */
  646 static int
  647 aqm_pie_cleanup(struct dn_queue *q)
  648 {
  649 
  650         if(!q) {
  651                 D("q is null");
  652                 return 0;
  653         }
  654         struct pie_status *pst  = q->aqm_status;
  655         if(!pst) {
  656                 //D("queue is already cleaned up");
  657                 return 0;
  658         }
  659         if(!q->fs || !q->fs->aqmcfg) {
  660                 D("fs is null or no cfg");
  661                 return 1;
  662         }
  663         if (q->fs->aqmfp && q->fs->aqmfp->type !=DN_AQM_PIE) {
  664                 D("Not PIE fs (%d)", q->fs->fs.fs_nr);
  665                 return 1;
  666         }
  667 
  668         /* 
  669          * Free PIE status allocated memory using pie_callout_cleanup() callout
  670          * function to avoid any potential race.
  671          * We reset aqm_pie_callout to call pie_callout_cleanup() in next 1um. This
  672          * stops the scheduled calculate_drop_prob() callout and call pie_callout_cleanup() 
  673          * which does memory freeing.
  674          */
  675         mtx_lock(&pst->lock_mtx);
  676         callout_reset_sbt(&pst->aqm_pie_callout,
  677                 SBT_1US, 0, pie_callout_cleanup, pst, 0);
  678         q->aqm_status = NULL;
  679         mtx_unlock(&pst->lock_mtx);
  680 
  681         return 0;
  682 }
  683 
  684 /* 
  685  * Config PIE parameters
  686  * also allocate memory for PIE configurations
  687  */
  688 static int 
  689 aqm_pie_config(struct dn_fsk* fs, struct dn_extra_parms *ep, int len)
  690 { 
  691         struct dn_aqm_pie_parms *pcfg;
  692 
  693         int l = sizeof(struct dn_extra_parms);
  694         if (len < l) {
  695                 D("invalid sched parms length got %d need %d", len, l);
  696                 return EINVAL;
  697         }
  698         /* we free the old cfg because maybe the orignal allocation 
  699          * was used for diffirent AQM type.
  700          */
  701         if (fs->aqmcfg) {
  702                 free(fs->aqmcfg, M_DUMMYNET);
  703                 fs->aqmcfg = NULL;
  704         }
  705 
  706         fs->aqmcfg = malloc(sizeof(struct dn_aqm_pie_parms),
  707                          M_DUMMYNET, M_NOWAIT | M_ZERO);
  708         if (fs->aqmcfg== NULL) {
  709                 D("cannot allocate PIE configuration parameters");
  710                 return ENOMEM; 
  711         }
  712 
  713         /* par array contains pie configuration as follow
  714          * 0- qdelay_ref,1- tupdate, 2- max_burst
  715          * 3- max_ecnth, 4- alpha, 5- beta, 6- flags
  716          */
  717 
  718         /* configure PIE parameters */
  719         pcfg = fs->aqmcfg;
  720 
  721         if (ep->par[0] < 0)
  722                 pcfg->qdelay_ref = pie_sysctl.qdelay_ref * AQM_TIME_1US;
  723         else
  724                 pcfg->qdelay_ref = ep->par[0];
  725         if (ep->par[1] < 0)
  726                 pcfg->tupdate = pie_sysctl.tupdate * AQM_TIME_1US;
  727         else
  728                 pcfg->tupdate = ep->par[1];
  729         if (ep->par[2] < 0)
  730                 pcfg->max_burst = pie_sysctl.max_burst * AQM_TIME_1US;
  731         else
  732                 pcfg->max_burst = ep->par[2];
  733         if (ep->par[3] < 0)
  734                 pcfg->max_ecnth = pie_sysctl.max_ecnth;
  735         else
  736                 pcfg->max_ecnth = ep->par[3];
  737         if (ep->par[4] < 0)
  738                 pcfg->alpha = pie_sysctl.alpha;
  739         else
  740                 pcfg->alpha = ep->par[4];
  741         if (ep->par[5] < 0)
  742                 pcfg->beta = pie_sysctl.beta;
  743         else
  744                 pcfg->beta = ep->par[5];
  745         if (ep->par[6] < 0)
  746                 pcfg->flags = pie_sysctl.flags;
  747         else
  748                 pcfg->flags = ep->par[6];
  749 
  750         /* bound PIE configurations */
  751         pcfg->qdelay_ref = BOUND_VAR(pcfg->qdelay_ref, 1, 10 * AQM_TIME_1S);
  752         pcfg->tupdate = BOUND_VAR(pcfg->tupdate, 1, 10 * AQM_TIME_1S);
  753         pcfg->max_burst = BOUND_VAR(pcfg->max_burst, 0, 10 * AQM_TIME_1S);
  754         pcfg->max_ecnth = BOUND_VAR(pcfg->max_ecnth, 0, PIE_SCALE);
  755         pcfg->alpha = BOUND_VAR(pcfg->alpha, 0, 7 * PIE_SCALE);
  756         pcfg->beta = BOUND_VAR(pcfg->beta, 0 , 7 * PIE_SCALE);
  757 
  758         pie_desc.cfg_ref_count++;
  759         //D("pie cfg_ref_count=%d", pie_desc.cfg_ref_count);
  760         return 0;
  761 }
  762 
  763 /*
  764  * Deconfigure PIE and free memory allocation
  765  */
  766 static int
  767 aqm_pie_deconfig(struct dn_fsk* fs)
  768 {
  769         if (fs && fs->aqmcfg) {
  770                 free(fs->aqmcfg, M_DUMMYNET);
  771                 fs->aqmcfg = NULL;
  772                 pie_desc.cfg_ref_count--;
  773         }
  774         return 0;
  775 }
  776 
  777 /* 
  778  * Retrieve PIE configuration parameters.
  779  */ 
  780 static int 
  781 aqm_pie_getconfig (struct dn_fsk *fs, struct dn_extra_parms * ep)
  782 {
  783         struct dn_aqm_pie_parms *pcfg;
  784         if (fs->aqmcfg) {
  785                 strlcpy(ep->name, pie_desc.name, sizeof(ep->name));
  786                 pcfg = fs->aqmcfg;
  787                 ep->par[0] = pcfg->qdelay_ref / AQM_TIME_1US;
  788                 ep->par[1] = pcfg->tupdate / AQM_TIME_1US;
  789                 ep->par[2] = pcfg->max_burst / AQM_TIME_1US;
  790                 ep->par[3] = pcfg->max_ecnth;
  791                 ep->par[4] = pcfg->alpha;
  792                 ep->par[5] = pcfg->beta;
  793                 ep->par[6] = pcfg->flags;
  794 
  795                 return 0;
  796         }
  797         return 1;
  798 }
  799 
  800 static struct dn_aqm pie_desc = {
  801         _SI( .type = )  DN_AQM_PIE,
  802         _SI( .name = )  "PIE",
  803         _SI( .ref_count = )  0,
  804         _SI( .cfg_ref_count = )  0,
  805         _SI( .enqueue = )  aqm_pie_enqueue,
  806         _SI( .dequeue = )  aqm_pie_dequeue,
  807         _SI( .config = )  aqm_pie_config,
  808         _SI( .deconfig = )  aqm_pie_deconfig,
  809         _SI( .getconfig = )  aqm_pie_getconfig,
  810         _SI( .init = )  aqm_pie_init,
  811         _SI( .cleanup = )  aqm_pie_cleanup,
  812 };
  813 
  814 DECLARE_DNAQM_MODULE(dn_aqm_pie, &pie_desc);
  815 #endif
Cache object: 778dc8353309ecb8cda77e26e31dd57b
[ 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.
FreeBSD/Linux Kernel Cross Reference sys/netpfil/ipfw/dn_aqm_pie.c

FreeBSD/Linux Kernel Cross Reference
sys/netpfil/ipfw/dn_aqm_pie.c
