sys/netpfil/ipfw/dn_sched_fq_pie.c

   1 /*
   2  * FQ_PIE - The FlowQueue-PIE scheduler/AQM
   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  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  20  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  22  * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  23  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  25  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  26  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  27  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  28  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  29  * SUCH DAMAGE.
  30  */
  31
  32 /* Important note:
  33  * As there is no an office document for FQ-PIE specification, we used
  34  * FQ-CoDel algorithm with some modifications to implement FQ-PIE.
  35  * This FQ-PIE implementation is a beta version and have not been tested
  36  * extensively. Our FQ-PIE uses stand-alone PIE AQM per sub-queue. By
  37  * default, timestamp is used to calculate queue delay instead of departure
  38  * rate estimation method. Although departure rate estimation is available
  39  * as testing option, the results could be incorrect. Moreover, turning PIE on
  40  * and off option is available but it does not work properly in this version.
  41  */
  42
  43 #ifdef _KERNEL
  44 #include <sys/malloc.h>
  45 #include <sys/socket.h>
  46 #include <sys/kernel.h>
  47 #include <sys/mbuf.h>
  48 #include <sys/lock.h>
  49 #include <sys/module.h>
  50 #include <sys/mutex.h>
  51 #include <net/if.h>     /* IFNAMSIZ */
  52 #include <netinet/in.h>
  53 #include <netinet/ip_var.h>             /* ipfw_rule_ref */
  54 #include <netinet/ip_fw.h>      /* flow_id */
  55 #include <netinet/ip_dummynet.h>
  56
  57 #include <sys/proc.h>
  58 #include <sys/rwlock.h>
  59
  60 #include <netpfil/ipfw/ip_fw_private.h>
  61 #include <sys/sysctl.h>
  62 #include <netinet/ip.h>
  63 #include <netinet/ip6.h>
  64 #include <netinet/ip_icmp.h>
  65 #include <netinet/tcp.h>
  66 #include <netinet/udp.h>
  67 #include <sys/queue.h>
  68 #include <sys/hash.h>
  69
  70 #include <netpfil/ipfw/dn_heap.h>
  71 #include <netpfil/ipfw/ip_dn_private.h>
  72
  73 #include <netpfil/ipfw/dn_aqm.h>
  74 #include <netpfil/ipfw/dn_aqm_pie.h>
  75 #include <netpfil/ipfw/dn_sched.h>
  76
  77 #else
  78 #include <dn_test.h>
  79 #endif
  80
  81 #define DN_SCHED_FQ_PIE 7
  82
  83 /* list of queues */
  84 STAILQ_HEAD(fq_pie_list, fq_pie_flow);
  85
  86 /* FQ_PIE parameters including PIE */
  87 struct dn_sch_fq_pie_parms {
  88         struct dn_aqm_pie_parms pcfg;   /* PIE configuration Parameters */
  89         /* FQ_PIE Parameters */
  90         uint32_t flows_cnt;     /* number of flows */
  91         uint32_t limit; /* hard limit of FQ_PIE queue size*/
  92         uint32_t quantum;
  93 };
  94
  95 /* flow (sub-queue) stats */
  96 struct flow_stats {
  97         uint64_t tot_pkts;      /* statistics counters  */
  98         uint64_t tot_bytes;
  99         uint32_t length;                /* Queue length, in packets */
 100         uint32_t len_bytes;     /* Queue length, in bytes */
 101         uint32_t drops;
 102 };
 103
 104 /* A flow of packets (sub-queue)*/
 105 struct fq_pie_flow {
 106         struct mq       mq;     /* list of packets */
 107         struct flow_stats stats;        /* statistics */
 108         int deficit;
 109         int active;             /* 1: flow is active (in a list) */
 110         struct pie_status pst;  /* pie status variables */
 111         struct fq_pie_si_extra *psi_extra;
 112         STAILQ_ENTRY(fq_pie_flow) flowchain;
 113 };
 114
 115 /* extra fq_pie scheduler configurations */
 116 struct fq_pie_schk {
 117         struct dn_sch_fq_pie_parms cfg;
 118 };
 119
 120 /* fq_pie scheduler instance extra state vars.
 121  * The purpose of separation this structure is to preserve number of active
 122  * sub-queues and the flows array pointer even after the scheduler instance
 123  * is destroyed.
 124  * Preserving these varaiables allows freeing the allocated memory by
 125  * fqpie_callout_cleanup() independently from fq_pie_free_sched().
 126  */
 127 struct fq_pie_si_extra {
 128         uint32_t nr_active_q;   /* number of active queues */
 129         struct fq_pie_flow *flows;      /* array of flows (queues) */
 130         };
 131
 132 /* fq_pie scheduler instance */
 133 struct fq_pie_si {
 134         struct dn_sch_inst _si; /* standard scheduler instance. SHOULD BE FIRST */
 135         struct dn_queue main_q; /* main queue is after si directly */
 136         uint32_t perturbation;  /* random value */
 137         struct fq_pie_list newflows;    /* list of new queues */
 138         struct fq_pie_list oldflows;    /* list of old queues */
 139         struct fq_pie_si_extra *si_extra; /* extra state vars*/
 140 };
 141
 142 static struct dn_alg fq_pie_desc;
 143
 144 /*  Default FQ-PIE parameters including PIE */
 145 /*  PIE defaults
 146  * target=15ms, max_burst=150ms, max_ecnth=0.1,
 147  * alpha=0.125, beta=1.25, tupdate=15ms
 148  * FQ-
 149  * flows=1024, limit=10240, quantum =1514
 150  */
 151 struct dn_sch_fq_pie_parms
 152  fq_pie_sysctl = {{15000 * AQM_TIME_1US, 15000 * AQM_TIME_1US,
 153         150000 * AQM_TIME_1US, PIE_SCALE * 0.1, PIE_SCALE * 0.125,
 154         PIE_SCALE * 1.25,       PIE_CAPDROP_ENABLED | PIE_DERAND_ENABLED},
 155         1024, 10240, 1514};
 156
 157 static int
 158 fqpie_sysctl_alpha_beta_handler(SYSCTL_HANDLER_ARGS)
 159 {
 160         int error;
 161         long  value;
 162
 163         if (!strcmp(oidp->oid_name,"alpha"))
 164                 value = fq_pie_sysctl.pcfg.alpha;
 165         else
 166                 value = fq_pie_sysctl.pcfg.beta;
 167
 168         value = value * 1000 / PIE_SCALE;
 169         error = sysctl_handle_long(oidp, &value, 0, req);
 170         if (error != 0 || req->newptr == NULL)
 171                 return (error);
 172         if (value < 1 || value > 7 * PIE_SCALE)
 173                 return (EINVAL);
 174         value = (value * PIE_SCALE) / 1000;
 175         if (!strcmp(oidp->oid_name,"alpha"))
 176                         fq_pie_sysctl.pcfg.alpha = value;
 177         else
 178                 fq_pie_sysctl.pcfg.beta = value;
 179         return (0);
 180 }
 181
 182 static int
 183 fqpie_sysctl_target_tupdate_maxb_handler(SYSCTL_HANDLER_ARGS)
 184 {
 185         int error;
 186         long  value;
 187
 188         if (!strcmp(oidp->oid_name,"target"))
 189                 value = fq_pie_sysctl.pcfg.qdelay_ref;
 190         else if (!strcmp(oidp->oid_name,"tupdate"))
 191                 value = fq_pie_sysctl.pcfg.tupdate;
 192         else
 193                 value = fq_pie_sysctl.pcfg.max_burst;
 194
 195         value = value / AQM_TIME_1US;
 196         error = sysctl_handle_long(oidp, &value, 0, req);
 197         if (error != 0 || req->newptr == NULL)
 198                 return (error);
 199         if (value < 1 || value > 10 * AQM_TIME_1S)
 200                 return (EINVAL);
 201         value = value * AQM_TIME_1US;
 202
 203         if (!strcmp(oidp->oid_name,"target"))
 204                 fq_pie_sysctl.pcfg.qdelay_ref  = value;
 205         else if (!strcmp(oidp->oid_name,"tupdate"))
 206                 fq_pie_sysctl.pcfg.tupdate  = value;
 207         else
 208                 fq_pie_sysctl.pcfg.max_burst = value;
 209         return (0);
 210 }
 211
 212 static int
 213 fqpie_sysctl_max_ecnth_handler(SYSCTL_HANDLER_ARGS)
 214 {
 215         int error;
 216         long  value;
 217
 218         value = fq_pie_sysctl.pcfg.max_ecnth;
 219         value = value * 1000 / PIE_SCALE;
 220         error = sysctl_handle_long(oidp, &value, 0, req);
 221         if (error != 0 || req->newptr == NULL)
 222                 return (error);
 223         if (value < 1 || value > PIE_SCALE)
 224                 return (EINVAL);
 225         value = (value * PIE_SCALE) / 1000;
 226         fq_pie_sysctl.pcfg.max_ecnth = value;
 227         return (0);
 228 }
 229
 230 /* define FQ- PIE sysctl variables */
 231 SYSBEGIN(f4)
 232 SYSCTL_DECL(_net_inet);
 233 SYSCTL_DECL(_net_inet_ip);
 234 SYSCTL_DECL(_net_inet_ip_dummynet);
 235 static SYSCTL_NODE(_net_inet_ip_dummynet, OID_AUTO, fqpie,
 236     CTLFLAG_RW | CTLFLAG_MPSAFE, 0,
 237     "FQ_PIE");
 238
 239 #ifdef SYSCTL_NODE
 240
 241 SYSCTL_PROC(_net_inet_ip_dummynet_fqpie, OID_AUTO, target,
 242     CTLTYPE_LONG | CTLFLAG_RW | CTLFLAG_NEEDGIANT, NULL, 0,
 243     fqpie_sysctl_target_tupdate_maxb_handler, "L",
 244     "queue target in microsecond");
 245
 246 SYSCTL_PROC(_net_inet_ip_dummynet_fqpie, OID_AUTO, tupdate,
 247     CTLTYPE_LONG | CTLFLAG_RW | CTLFLAG_NEEDGIANT, NULL, 0,
 248     fqpie_sysctl_target_tupdate_maxb_handler, "L",
 249     "the frequency of drop probability calculation in microsecond");
 250
 251 SYSCTL_PROC(_net_inet_ip_dummynet_fqpie, OID_AUTO, max_burst,
 252     CTLTYPE_LONG | CTLFLAG_RW | CTLFLAG_NEEDGIANT, NULL, 0,
 253     fqpie_sysctl_target_tupdate_maxb_handler, "L",
 254     "Burst allowance interval in microsecond");
 255
 256 SYSCTL_PROC(_net_inet_ip_dummynet_fqpie, OID_AUTO, max_ecnth,
 257     CTLTYPE_LONG | CTLFLAG_RW | CTLFLAG_NEEDGIANT, NULL, 0,
 258     fqpie_sysctl_max_ecnth_handler, "L",
 259     "ECN safeguard threshold scaled by 1000");
 260
 261 SYSCTL_PROC(_net_inet_ip_dummynet_fqpie, OID_AUTO, alpha,
 262     CTLTYPE_LONG | CTLFLAG_RW | CTLFLAG_NEEDGIANT, NULL, 0,
 263     fqpie_sysctl_alpha_beta_handler, "L",
 264     "PIE alpha scaled by 1000");
 265
 266 SYSCTL_PROC(_net_inet_ip_dummynet_fqpie, OID_AUTO, beta,
 267     CTLTYPE_LONG | CTLFLAG_RW | CTLFLAG_NEEDGIANT, NULL, 0,
 268     fqpie_sysctl_alpha_beta_handler, "L",
 269     "beta scaled by 1000");
 270
 271 SYSCTL_UINT(_net_inet_ip_dummynet_fqpie, OID_AUTO, quantum,
 272         CTLFLAG_RW, &fq_pie_sysctl.quantum, 1514, "quantum for FQ_PIE");
 273 SYSCTL_UINT(_net_inet_ip_dummynet_fqpie, OID_AUTO, flows,
 274         CTLFLAG_RW, &fq_pie_sysctl.flows_cnt, 1024, "Number of queues for FQ_PIE");
 275 SYSCTL_UINT(_net_inet_ip_dummynet_fqpie, OID_AUTO, limit,
 276         CTLFLAG_RW, &fq_pie_sysctl.limit, 10240, "limit for FQ_PIE");
 277 #endif
 278
 279 /* Helper function to update queue&main-queue and scheduler statistics.
 280  * negative len & drop -> drop
 281  * negative len -> dequeue
 282  * positive len -> enqueue
 283  * positive len + drop -> drop during enqueue
 284  */
 285 __inline static void
 286 fq_update_stats(struct fq_pie_flow *q, struct fq_pie_si *si, int len,
 287         int drop)
 288 {
 289         int inc = 0;
 290
 291         if (len < 0)
 292                 inc = -1;
 293         else if (len > 0)
 294                 inc = 1;
 295
 296         if (drop) {
 297                 si->main_q.ni.drops ++;
 298                 q->stats.drops ++;
 299                 si->_si.ni.drops ++;
 300                 V_dn_cfg.io_pkt_drop ++;
 301         }
 302
 303         if (!drop || (drop && len < 0)) {
 304                 /* Update stats for the main queue */
 305                 si->main_q.ni.length += inc;
 306                 si->main_q.ni.len_bytes += len;
 307
 308                 /*update sub-queue stats */
 309                 q->stats.length += inc;
 310                 q->stats.len_bytes += len;
 311
 312                 /*update scheduler instance stats */
 313                 si->_si.ni.length += inc;
 314                 si->_si.ni.len_bytes += len;
 315         }
 316
 317         if (inc > 0) {
 318                 si->main_q.ni.tot_bytes += len;
 319                 si->main_q.ni.tot_pkts ++;
 320
 321                 q->stats.tot_bytes +=len;
 322                 q->stats.tot_pkts++;
 323
 324                 si->_si.ni.tot_bytes +=len;
 325                 si->_si.ni.tot_pkts ++;
 326         }
 327
 328 }
 329
 330 /*
 331  * Extract a packet from the head of sub-queue 'q'
 332  * Return a packet or NULL if the queue is empty.
 333  * If getts is set, also extract packet's timestamp from mtag.
 334  */
 335 __inline static struct mbuf *
 336 fq_pie_extract_head(struct fq_pie_flow *q, aqm_time_t *pkt_ts,
 337         struct fq_pie_si *si, int getts)
 338 {
 339         struct mbuf *m;
 340
 341 next:   m = q->mq.head;
 342         if (m == NULL)
 343                 return m;
 344         q->mq.head = m->m_nextpkt;
 345
 346         fq_update_stats(q, si, -m->m_pkthdr.len, 0);
 347
 348         if (si->main_q.ni.length == 0) /* queue is now idle */
 349                         si->main_q.q_time = V_dn_cfg.curr_time;
 350
 351         if (getts) {
 352                 /* extract packet timestamp*/
 353                 struct m_tag *mtag;
 354                 mtag = m_tag_locate(m, MTAG_ABI_COMPAT, DN_AQM_MTAG_TS, NULL);
 355                 if (mtag == NULL){
 356                         D("PIE timestamp mtag not found!");
 357                         *pkt_ts = 0;
 358                 } else {
 359                         *pkt_ts = *(aqm_time_t *)(mtag + 1);
 360                         m_tag_delete(m,mtag);
 361                 }
 362         }
 363         if (m->m_pkthdr.rcvif != NULL &&
 364             __predict_false(m_rcvif_restore(m) == NULL)) {
 365                 m_freem(m);
 366                 goto next;
 367         }
 368         return m;
 369 }
 370
 371 /*
 372  * Callout function for drop probability calculation
 373  * This function is called over tupdate ms and takes pointer of FQ-PIE
 374  * flow as an argument
 375   */
 376 static void
 377 fq_calculate_drop_prob(void *x)
 378 {
 379         struct fq_pie_flow *q = (struct fq_pie_flow *) x;
 380         struct pie_status *pst = &q->pst;
 381         struct dn_aqm_pie_parms *pprms;
 382         int64_t p, prob, oldprob;
 383         int p_isneg;
 384
 385         pprms = pst->parms;
 386         prob = pst->drop_prob;
 387
 388         /* calculate current qdelay using DRE method.
 389          * If TS is used and no data in the queue, reset current_qdelay
 390          * as it stays at last value during dequeue process.
 391         */
 392         if (pprms->flags & PIE_DEPRATEEST_ENABLED)
 393                 pst->current_qdelay = ((uint64_t)q->stats.len_bytes  * pst->avg_dq_time)
 394                         >> PIE_DQ_THRESHOLD_BITS;
 395         else
 396                 if (!q->stats.len_bytes)
 397                         pst->current_qdelay = 0;
 398
 399         /* calculate drop probability */
 400         p = (int64_t)pprms->alpha *
 401                 ((int64_t)pst->current_qdelay - (int64_t)pprms->qdelay_ref);
 402         p +=(int64_t) pprms->beta *
 403                 ((int64_t)pst->current_qdelay - (int64_t)pst->qdelay_old);
 404
 405         /* take absolute value so right shift result is well defined */
 406         p_isneg = p < 0;
 407         if (p_isneg) {
 408                 p = -p;
 409         }
 410
 411         /* We PIE_MAX_PROB shift by 12-bits to increase the division precision  */
 412         p *= (PIE_MAX_PROB << 12) / AQM_TIME_1S;
 413
 414         /* auto-tune drop probability */
 415         if (prob < (PIE_MAX_PROB / 1000000)) /* 0.000001 */
 416                 p >>= 11 + PIE_FIX_POINT_BITS + 12;
 417         else if (prob < (PIE_MAX_PROB / 100000)) /* 0.00001 */
 418                 p >>= 9 + PIE_FIX_POINT_BITS + 12;
 419         else if (prob < (PIE_MAX_PROB / 10000)) /* 0.0001 */
 420                 p >>= 7 + PIE_FIX_POINT_BITS + 12;
 421         else if (prob < (PIE_MAX_PROB / 1000)) /* 0.001 */
 422                 p >>= 5 + PIE_FIX_POINT_BITS + 12;
 423         else if (prob < (PIE_MAX_PROB / 100)) /* 0.01 */
 424                 p >>= 3 + PIE_FIX_POINT_BITS + 12;
 425         else if (prob < (PIE_MAX_PROB / 10)) /* 0.1 */
 426                 p >>= 1 + PIE_FIX_POINT_BITS + 12;
 427         else
 428                 p >>= PIE_FIX_POINT_BITS + 12;
 429
 430         oldprob = prob;
 431
 432         if (p_isneg) {
 433                 prob = prob - p;
 434
 435                 /* check for multiplication underflow */
 436                 if (prob > oldprob) {
 437                         prob= 0;
 438                         D("underflow");
 439                 }
 440         } else {
 441                 /* Cap Drop adjustment */
 442                 if ((pprms->flags & PIE_CAPDROP_ENABLED) &&
 443                     prob >= PIE_MAX_PROB / 10 &&
 444                     p > PIE_MAX_PROB / 50 ) {
 445                         p = PIE_MAX_PROB / 50;
 446                 }
 447
 448                 prob = prob + p;
 449
 450                 /* check for multiplication overflow */
 451                 if (prob<oldprob) {
 452                         D("overflow");
 453                         prob= PIE_MAX_PROB;
 454                 }
 455         }
 456
 457         /*
 458          * decay the drop probability exponentially
 459          * and restrict it to range 0 to PIE_MAX_PROB
 460          */
 461         if (prob < 0) {
 462                 prob = 0;
 463         } else {
 464                 if (pst->current_qdelay == 0 && pst->qdelay_old == 0) {
 465                         /* 0.98 ~= 1- 1/64 */
 466                         prob = prob - (prob >> 6);
 467                 }
 468
 469                 if (prob > PIE_MAX_PROB) {
 470                         prob = PIE_MAX_PROB;
 471                 }
 472         }
 473
 474         pst->drop_prob = prob;
 475
 476         /* store current delay value */
 477         pst->qdelay_old = pst->current_qdelay;
 478
 479         /* update burst allowance */
 480         if ((pst->sflags & PIE_ACTIVE) && pst->burst_allowance) {
 481                 if (pst->burst_allowance > pprms->tupdate)
 482                         pst->burst_allowance -= pprms->tupdate;
 483                 else
 484                         pst->burst_allowance = 0;
 485         }
 486
 487         if (pst->sflags & PIE_ACTIVE)
 488         callout_reset_sbt(&pst->aqm_pie_callout,
 489                 (uint64_t)pprms->tupdate * SBT_1US,
 490                 0, fq_calculate_drop_prob, q, 0);
 491
 492         mtx_unlock(&pst->lock_mtx);
 493 }
 494
 495 /*
 496  * Reset PIE variables & activate the queue
 497  */
 498 __inline static void
 499 fq_activate_pie(struct fq_pie_flow *q)
 500 {
 501         struct pie_status *pst = &q->pst;
 502         struct dn_aqm_pie_parms *pprms;
 503
 504         mtx_lock(&pst->lock_mtx);
 505         pprms = pst->parms;
 506
 507         pprms = pst->parms;
 508         pst->drop_prob = 0;
 509         pst->qdelay_old = 0;
 510         pst->burst_allowance = pprms->max_burst;
 511         pst->accu_prob = 0;
 512         pst->dq_count = 0;
 513         pst->avg_dq_time = 0;
 514         pst->sflags = PIE_INMEASUREMENT | PIE_ACTIVE;
 515         pst->measurement_start = AQM_UNOW;
 516
 517         callout_reset_sbt(&pst->aqm_pie_callout,
 518                 (uint64_t)pprms->tupdate * SBT_1US,
 519                 0, fq_calculate_drop_prob, q, 0);
 520
 521         mtx_unlock(&pst->lock_mtx);
 522 }
 523
 524  /*
 525   * Deactivate PIE and stop probe update callout
 526   */
 527 __inline static void
 528 fq_deactivate_pie(struct pie_status *pst)
 529 {
 530         mtx_lock(&pst->lock_mtx);
 531         pst->sflags &= ~(PIE_ACTIVE | PIE_INMEASUREMENT);
 532         callout_stop(&pst->aqm_pie_callout);
 533         //D("PIE Deactivated");
 534         mtx_unlock(&pst->lock_mtx);
 535 }
 536
 537  /*
 538   * Initialize PIE for sub-queue 'q'
 539   */
 540 static int
 541 pie_init(struct fq_pie_flow *q, struct fq_pie_schk *fqpie_schk)
 542 {
 543         struct pie_status *pst=&q->pst;
 544         struct dn_aqm_pie_parms *pprms = pst->parms;
 545
 546         int err = 0;
 547         if (!pprms){
 548                 D("AQM_PIE is not configured");
 549                 err = EINVAL;
 550         } else {
 551                 q->psi_extra->nr_active_q++;
 552
 553                 /* For speed optimization, we caculate 1/3 queue size once here */
 554                 // XXX limit divided by number of queues divided by 3 ???
 555                 pst->one_third_q_size = (fqpie_schk->cfg.limit /
 556                         fqpie_schk->cfg.flows_cnt) / 3;
 557
 558                 mtx_init(&pst->lock_mtx, "mtx_pie", NULL, MTX_DEF);
 559                 callout_init_mtx(&pst->aqm_pie_callout, &pst->lock_mtx,
 560                         CALLOUT_RETURNUNLOCKED);
 561         }
 562
 563         return err;
 564 }
 565
 566 /*
 567  * callout function to destroy PIE lock, and free fq_pie flows and fq_pie si
 568  * extra memory when number of active sub-queues reaches zero.
 569  * 'x' is a fq_pie_flow to be destroyed
 570  */
 571 static void
 572 fqpie_callout_cleanup(void *x)
 573 {
 574         struct fq_pie_flow *q = x;
 575         struct pie_status *pst = &q->pst;
 576         struct fq_pie_si_extra *psi_extra;
 577
 578         mtx_unlock(&pst->lock_mtx);
 579         mtx_destroy(&pst->lock_mtx);
 580         psi_extra = q->psi_extra;
 581
 582         dummynet_sched_lock();
 583         psi_extra->nr_active_q--;
 584
 585         /* when all sub-queues are destroyed, free flows fq_pie extra vars memory */
 586         if (!psi_extra->nr_active_q) {
 587                 free(psi_extra->flows, M_DUMMYNET);
 588                 free(psi_extra, M_DUMMYNET);
 589                 fq_pie_desc.ref_count--;
 590         }
 591         dummynet_sched_unlock();
 592 }
 593
 594 /*
 595  * Clean up PIE status for sub-queue 'q'
 596  * Stop callout timer and destroy mtx using fqpie_callout_cleanup() callout.
 597  */
 598 static int
 599 pie_cleanup(struct fq_pie_flow *q)
 600 {
 601         struct pie_status *pst  = &q->pst;
 602
 603         mtx_lock(&pst->lock_mtx);
 604         callout_reset_sbt(&pst->aqm_pie_callout,
 605                 SBT_1US, 0, fqpie_callout_cleanup, q, 0);
 606         mtx_unlock(&pst->lock_mtx);
 607         return 0;
 608 }
 609
 610 /*
 611  * Dequeue and return a pcaket from sub-queue 'q' or NULL if 'q' is empty.
 612  * Also, caculate depature time or queue delay using timestamp
 613  */
 614  static struct mbuf *
 615 pie_dequeue(struct fq_pie_flow *q, struct fq_pie_si *si)
 616 {
 617         struct mbuf *m;
 618         struct dn_aqm_pie_parms *pprms;
 619         struct pie_status *pst;
 620         aqm_time_t now;
 621         aqm_time_t pkt_ts, dq_time;
 622         int32_t w;
 623
 624         pst  = &q->pst;
 625         pprms = q->pst.parms;
 626
 627         /*we extarct packet ts only when Departure Rate Estimation dis not used*/
 628         m = fq_pie_extract_head(q, &pkt_ts, si,
 629                 !(pprms->flags & PIE_DEPRATEEST_ENABLED));
 630
 631         if (!m || !(pst->sflags & PIE_ACTIVE))
 632                 return m;
 633
 634         now = AQM_UNOW;
 635         if (pprms->flags & PIE_DEPRATEEST_ENABLED) {
 636                 /* calculate average depature time */
 637                 if(pst->sflags & PIE_INMEASUREMENT) {
 638                         pst->dq_count += m->m_pkthdr.len;
 639
 640                         if (pst->dq_count >= PIE_DQ_THRESHOLD) {
 641                                 dq_time = now - pst->measurement_start;
 642
 643                                 /*
 644                                  * if we don't have old avg dq_time i.e PIE is (re)initialized,
 645                                  * don't use weight to calculate new avg_dq_time
 646                                  */
 647                                 if(pst->avg_dq_time == 0)
 648                                         pst->avg_dq_time = dq_time;
 649                                 else {
 650                                         /*
 651                                          * weight = PIE_DQ_THRESHOLD/2^6, but we scaled
 652                                          * weight by 2^8. Thus, scaled
 653                                          * weight = PIE_DQ_THRESHOLD /2^8
 654                                          * */
 655                                         w = PIE_DQ_THRESHOLD >> 8;
 656                                         pst->avg_dq_time = (dq_time* w
 657                                                 + (pst->avg_dq_time * ((1L << 8) - w))) >> 8;
 658                                         pst->sflags &= ~PIE_INMEASUREMENT;
 659                                 }
 660                         }
 661                 }
 662
 663                 /*
 664                  * Start new measurement cycle when the queue has
 665                  * PIE_DQ_THRESHOLD worth of bytes.
 666                  */
 667                 if(!(pst->sflags & PIE_INMEASUREMENT) &&
 668                         q->stats.len_bytes >= PIE_DQ_THRESHOLD) {
 669                         pst->sflags |= PIE_INMEASUREMENT;
 670                         pst->measurement_start = now;
 671                         pst->dq_count = 0;
 672                 }
 673         }
 674         /* Optionally, use packet timestamp to estimate queue delay */
 675         else
 676                 pst->current_qdelay = now - pkt_ts;
 677
 678         return m;
 679 }
 680
 681  /*
 682  * Enqueue a packet in q, subject to space and FQ-PIE queue management policy
 683  * (whose parameters are in q->fs).
 684  * Update stats for the queue and the scheduler.
 685  * Return 0 on success, 1 on drop. The packet is consumed anyways.
 686  */
 687 static int
 688 pie_enqueue(struct fq_pie_flow *q, struct mbuf* m, struct fq_pie_si *si)
 689 {
 690         uint64_t len;
 691         struct pie_status *pst;
 692         struct dn_aqm_pie_parms *pprms;
 693         int t;
 694
 695         len = m->m_pkthdr.len;
 696         pst  = &q->pst;
 697         pprms = pst->parms;
 698         t = ENQUE;
 699
 700         /* drop/mark the packet when PIE is active and burst time elapsed */
 701         if (pst->sflags & PIE_ACTIVE && pst->burst_allowance == 0
 702                 && drop_early(pst, q->stats.len_bytes) == DROP) {
 703                         /*
 704                          * if drop_prob over ECN threshold, drop the packet
 705                          * otherwise mark and enqueue it.
 706                          */
 707                         if (pprms->flags & PIE_ECN_ENABLED && pst->drop_prob <
 708                                 (pprms->max_ecnth << (PIE_PROB_BITS - PIE_FIX_POINT_BITS))
 709                                 && ecn_mark(m))
 710                                 t = ENQUE;
 711                         else
 712                                 t = DROP;
 713                 }
 714
 715         /* Turn PIE on when 1/3 of the queue is full */
 716         if (!(pst->sflags & PIE_ACTIVE) && q->stats.len_bytes >=
 717                 pst->one_third_q_size) {
 718                 fq_activate_pie(q);
 719         }
 720
 721         /*  reset burst tolerance and optinally turn PIE off*/
 722         if (pst->drop_prob == 0 && pst->current_qdelay < (pprms->qdelay_ref >> 1)
 723                 && pst->qdelay_old < (pprms->qdelay_ref >> 1)) {
 724
 725                         pst->burst_allowance = pprms->max_burst;
 726                 if (pprms->flags & PIE_ON_OFF_MODE_ENABLED && q->stats.len_bytes<=0)
 727                         fq_deactivate_pie(pst);
 728         }
 729
 730         /* Use timestamp if Departure Rate Estimation mode is disabled */
 731         if (t != DROP && !(pprms->flags & PIE_DEPRATEEST_ENABLED)) {
 732                 /* Add TS to mbuf as a TAG */
 733                 struct m_tag *mtag;
 734                 mtag = m_tag_locate(m, MTAG_ABI_COMPAT, DN_AQM_MTAG_TS, NULL);
 735                 if (mtag == NULL)
 736                         mtag = m_tag_alloc(MTAG_ABI_COMPAT, DN_AQM_MTAG_TS,
 737                                 sizeof(aqm_time_t), M_NOWAIT);
 738                 if (mtag == NULL) {
 739                         t = DROP;
 740                 } else {
 741                         *(aqm_time_t *)(mtag + 1) = AQM_UNOW;
 742                         m_tag_prepend(m, mtag);
 743                 }
 744         }
 745
 746         if (t != DROP) {
 747                 mq_append(&q->mq, m);
 748                 fq_update_stats(q, si, len, 0);
 749                 return 0;
 750         } else {
 751                 fq_update_stats(q, si, len, 1);
 752                 pst->accu_prob = 0;
 753                 FREE_PKT(m);
 754                 return 1;
 755         }
 756
 757         return 0;
 758 }
 759
 760 /* Drop a packet form the head of FQ-PIE sub-queue */
 761 static void
 762 pie_drop_head(struct fq_pie_flow *q, struct fq_pie_si *si)
 763 {
 764         struct mbuf *m = q->mq.head;
 765
 766         if (m == NULL)
 767                 return;
 768         q->mq.head = m->m_nextpkt;
 769
 770         fq_update_stats(q, si, -m->m_pkthdr.len, 1);
 771
 772         if (si->main_q.ni.length == 0) /* queue is now idle */
 773                         si->main_q.q_time = V_dn_cfg.curr_time;
 774         /* reset accu_prob after packet drop */
 775         q->pst.accu_prob = 0;
 776
 777         FREE_PKT(m);
 778 }
 779
 780 /*
 781  * Classify a packet to queue number using Jenkins hash function.
 782  * Return: queue number
 783  * the input of the hash are protocol no, perturbation, src IP, dst IP,
 784  * src port, dst port,
 785  */
 786 static inline int
 787 fq_pie_classify_flow(struct mbuf *m, uint16_t fcount, struct fq_pie_si *si)
 788 {
 789         struct ip *ip;
 790         struct tcphdr *th;
 791         struct udphdr *uh;
 792         uint8_t tuple[41];
 793         uint16_t hash=0;
 794
 795         ip = (struct ip *)mtodo(m, dn_tag_get(m)->iphdr_off);
 796 //#ifdef INET6
 797         struct ip6_hdr *ip6;
 798         int isip6;
 799         isip6 = (ip->ip_v == 6);
 800
 801         if(isip6) {
 802                 ip6 = (struct ip6_hdr *)ip;
 803                 *((uint8_t *) &tuple[0]) = ip6->ip6_nxt;
 804                 *((uint32_t *) &tuple[1]) = si->perturbation;
 805                 memcpy(&tuple[5], ip6->ip6_src.s6_addr, 16);
 806                 memcpy(&tuple[21], ip6->ip6_dst.s6_addr, 16);
 807
 808                 switch (ip6->ip6_nxt) {
 809                 case IPPROTO_TCP:
 810                         th = (struct tcphdr *)(ip6 + 1);
 811                         *((uint16_t *) &tuple[37]) = th->th_dport;
 812                         *((uint16_t *) &tuple[39]) = th->th_sport;
 813                         break;
 814
 815                 case IPPROTO_UDP:
 816                         uh = (struct udphdr *)(ip6 + 1);
 817                         *((uint16_t *) &tuple[37]) = uh->uh_dport;
 818                         *((uint16_t *) &tuple[39]) = uh->uh_sport;
 819                         break;
 820                 default:
 821                         memset(&tuple[37], 0, 4);
 822                 }
 823
 824                 hash = jenkins_hash(tuple, 41, HASHINIT) %  fcount;
 825                 return hash;
 826         }
 827 //#endif
 828
 829         /* IPv4 */
 830         *((uint8_t *) &tuple[0]) = ip->ip_p;
 831         *((uint32_t *) &tuple[1]) = si->perturbation;
 832         *((uint32_t *) &tuple[5]) = ip->ip_src.s_addr;
 833         *((uint32_t *) &tuple[9]) = ip->ip_dst.s_addr;
 834
 835         switch (ip->ip_p) {
 836                 case IPPROTO_TCP:
 837                         th = (struct tcphdr *)(ip + 1);
 838                         *((uint16_t *) &tuple[13]) = th->th_dport;
 839                         *((uint16_t *) &tuple[15]) = th->th_sport;
 840                         break;
 841
 842                 case IPPROTO_UDP:
 843                         uh = (struct udphdr *)(ip + 1);
 844                         *((uint16_t *) &tuple[13]) = uh->uh_dport;
 845                         *((uint16_t *) &tuple[15]) = uh->uh_sport;
 846                         break;
 847                 default:
 848                         memset(&tuple[13], 0, 4);
 849         }
 850         hash = jenkins_hash(tuple, 17, HASHINIT) % fcount;
 851
 852         return hash;
 853 }
 854
 855 /*
 856  * Enqueue a packet into an appropriate queue according to
 857  * FQ-CoDe; algorithm.
 858  */
 859 static int
 860 fq_pie_enqueue(struct dn_sch_inst *_si, struct dn_queue *_q,
 861         struct mbuf *m)
 862 {
 863         struct fq_pie_si *si;
 864         struct fq_pie_schk *schk;
 865         struct dn_sch_fq_pie_parms *param;
 866         struct dn_queue *mainq;
 867         struct fq_pie_flow *flows;
 868         int idx, drop, i, maxidx;
 869
 870         mainq = (struct dn_queue *)(_si + 1);
 871         si = (struct fq_pie_si *)_si;
 872         flows = si->si_extra->flows;
 873         schk = (struct fq_pie_schk *)(si->_si.sched+1);
 874         param = &schk->cfg;
 875
 876          /* classify a packet to queue number*/
 877         idx = fq_pie_classify_flow(m, param->flows_cnt, si);
 878
 879         /* enqueue packet into appropriate queue using PIE AQM.
 880          * Note: 'pie_enqueue' function returns 1 only when it unable to
 881          * add timestamp to packet (no limit check)*/
 882         drop = pie_enqueue(&flows[idx], m, si);
 883
 884         /* pie unable to timestamp a packet */
 885         if (drop)
 886                 return 1;
 887
 888         /* If the flow (sub-queue) is not active ,then add it to tail of
 889          * new flows list, initialize and activate it.
 890          */
 891         if (!flows[idx].active) {
 892                 STAILQ_INSERT_TAIL(&si->newflows, &flows[idx], flowchain);
 893                 flows[idx].deficit = param->quantum;
 894                 fq_activate_pie(&flows[idx]);
 895                 flows[idx].active = 1;
 896         }
 897
 898         /* check the limit for all queues and remove a packet from the
 899          * largest one
 900          */
 901         if (mainq->ni.length > schk->cfg.limit) {
 902                 /* find first active flow */
 903                 for (maxidx = 0; maxidx < schk->cfg.flows_cnt; maxidx++)
 904                         if (flows[maxidx].active)
 905                                 break;
 906                 if (maxidx < schk->cfg.flows_cnt) {
 907                         /* find the largest sub- queue */
 908                         for (i = maxidx + 1; i < schk->cfg.flows_cnt; i++)
 909                                 if (flows[i].active && flows[i].stats.length >
 910                                         flows[maxidx].stats.length)
 911                                         maxidx = i;
 912                         pie_drop_head(&flows[maxidx], si);
 913                         drop = 1;
 914                 }
 915         }
 916
 917         return drop;
 918 }
 919
 920 /*
 921  * Dequeue a packet from an appropriate queue according to
 922  * FQ-CoDel algorithm.
 923  */
 924 static struct mbuf *
 925 fq_pie_dequeue(struct dn_sch_inst *_si)
 926 {
 927         struct fq_pie_si *si;
 928         struct fq_pie_schk *schk;
 929         struct dn_sch_fq_pie_parms *param;
 930         struct fq_pie_flow *f;
 931         struct mbuf *mbuf;
 932         struct fq_pie_list *fq_pie_flowlist;
 933
 934         si = (struct fq_pie_si *)_si;
 935         schk = (struct fq_pie_schk *)(si->_si.sched+1);
 936         param = &schk->cfg;
 937
 938         do {
 939                 /* select a list to start with */
 940                 if (STAILQ_EMPTY(&si->newflows))
 941                         fq_pie_flowlist = &si->oldflows;
 942                 else
 943                         fq_pie_flowlist = &si->newflows;
 944
 945                 /* Both new and old queue lists are empty, return NULL */
 946                 if (STAILQ_EMPTY(fq_pie_flowlist))
 947                         return NULL;
 948
 949                 f = STAILQ_FIRST(fq_pie_flowlist);
 950                 while (f != NULL)       {
 951                         /* if there is no flow(sub-queue) deficit, increase deficit
 952                          * by quantum, move the flow to the tail of old flows list
 953                          * and try another flow.
 954                          * Otherwise, the flow will be used for dequeue.
 955                          */
 956                         if (f->deficit < 0) {
 957                                  f->deficit += param->quantum;
 958                                  STAILQ_REMOVE_HEAD(fq_pie_flowlist, flowchain);
 959                                  STAILQ_INSERT_TAIL(&si->oldflows, f, flowchain);
 960                          } else
 961                                  break;
 962
 963                         f = STAILQ_FIRST(fq_pie_flowlist);
 964                 }
 965
 966                 /* the new flows list is empty, try old flows list */
 967                 if (STAILQ_EMPTY(fq_pie_flowlist))
 968                         continue;
 969
 970                 /* Dequeue a packet from the selected flow */
 971                 mbuf = pie_dequeue(f, si);
 972
 973                 /* pie did not return a packet */
 974                 if (!mbuf) {
 975                         /* If the selected flow belongs to new flows list, then move
 976                          * it to the tail of old flows list. Otherwise, deactivate it and
 977                          * remove it from the old list and
 978                          */
 979                         if (fq_pie_flowlist == &si->newflows) {
 980                                 STAILQ_REMOVE_HEAD(fq_pie_flowlist, flowchain);
 981                                 STAILQ_INSERT_TAIL(&si->oldflows, f, flowchain);
 982                         }       else {
 983                                 f->active = 0;
 984                                 fq_deactivate_pie(&f->pst);
 985                                 STAILQ_REMOVE_HEAD(fq_pie_flowlist, flowchain);
 986                         }
 987                         /* start again */
 988                         continue;
 989                 }
 990
 991                 /* we have a packet to return,
 992                  * update flow deficit and return the packet*/
 993                 f->deficit -= mbuf->m_pkthdr.len;
 994                 return mbuf;
 995
 996         } while (1);
 997
 998         /* unreachable point */
 999         return NULL;
1000 }
1001
1002 /*
1003  * Initialize fq_pie scheduler instance.
1004  * also, allocate memory for flows array.
1005  */
1006 static int
1007 fq_pie_new_sched(struct dn_sch_inst *_si)
1008 {
1009         struct fq_pie_si *si;
1010         struct dn_queue *q;
1011         struct fq_pie_schk *schk;
1012         struct fq_pie_flow *flows;
1013         int i;
1014
1015         si = (struct fq_pie_si *)_si;
1016         schk = (struct fq_pie_schk *)(_si->sched+1);
1017
1018         if(si->si_extra) {
1019                 D("si already configured!");
1020                 return 0;
1021         }
1022
1023         /* init the main queue */
1024         q = &si->main_q;
1025         set_oid(&q->ni.oid, DN_QUEUE, sizeof(*q));
1026         q->_si = _si;
1027         q->fs = _si->sched->fs;
1028
1029         /* allocate memory for scheduler instance extra vars */
1030         si->si_extra = malloc(sizeof(struct fq_pie_si_extra),
1031                  M_DUMMYNET, M_NOWAIT | M_ZERO);
1032         if (si->si_extra == NULL) {
1033                 D("cannot allocate memory for fq_pie si extra vars");
1034                 return ENOMEM ;
1035         }
1036         /* allocate memory for flows array */
1037         si->si_extra->flows = mallocarray(schk->cfg.flows_cnt,
1038             sizeof(struct fq_pie_flow), M_DUMMYNET, M_NOWAIT | M_ZERO);
1039         flows = si->si_extra->flows;
1040         if (flows == NULL) {
1041                 free(si->si_extra, M_DUMMYNET);
1042                 si->si_extra = NULL;
1043                 D("cannot allocate memory for fq_pie flows");
1044                 return ENOMEM ;
1045         }
1046
1047         /* init perturbation for this si */
1048         si->perturbation = random();
1049         si->si_extra->nr_active_q = 0;
1050
1051         /* init the old and new flows lists */
1052         STAILQ_INIT(&si->newflows);
1053         STAILQ_INIT(&si->oldflows);
1054
1055         /* init the flows (sub-queues) */
1056         for (i = 0; i < schk->cfg.flows_cnt; i++) {
1057                 flows[i].pst.parms = &schk->cfg.pcfg;
1058                 flows[i].psi_extra = si->si_extra;
1059                 pie_init(&flows[i], schk);
1060         }
1061
1062         dummynet_sched_lock();
1063         fq_pie_desc.ref_count++;
1064         dummynet_sched_unlock();
1065
1066         return 0;
1067 }
1068
1069 /*
1070  * Free fq_pie scheduler instance.
1071  */
1072 static int
1073 fq_pie_free_sched(struct dn_sch_inst *_si)
1074 {
1075         struct fq_pie_si *si;
1076         struct fq_pie_schk *schk;
1077         struct fq_pie_flow *flows;
1078         int i;
1079
1080         si = (struct fq_pie_si *)_si;
1081         schk = (struct fq_pie_schk *)(_si->sched+1);
1082         flows = si->si_extra->flows;
1083         for (i = 0; i < schk->cfg.flows_cnt; i++) {
1084                 pie_cleanup(&flows[i]);
1085         }
1086         si->si_extra = NULL;
1087         return 0;
1088 }
1089
1090 /*
1091  * Configure FQ-PIE scheduler.
1092  * the configurations for the scheduler is passed fromipfw  userland.
1093  */
1094 static int
1095 fq_pie_config(struct dn_schk *_schk)
1096 {
1097         struct fq_pie_schk *schk;
1098         struct dn_extra_parms *ep;
1099         struct dn_sch_fq_pie_parms *fqp_cfg;
1100
1101         schk = (struct fq_pie_schk *)(_schk+1);
1102         ep = (struct dn_extra_parms *) _schk->cfg;
1103
1104         /* par array contains fq_pie configuration as follow
1105          * PIE: 0- qdelay_ref,1- tupdate, 2- max_burst
1106          * 3- max_ecnth, 4- alpha, 5- beta, 6- flags
1107          * FQ_PIE: 7- quantum, 8- limit, 9- flows
1108          */
1109         if (ep && ep->oid.len ==sizeof(*ep) &&
1110                 ep->oid.subtype == DN_SCH_PARAMS) {
1111                 fqp_cfg = &schk->cfg;
1112                 if (ep->par[0] < 0)
1113                         fqp_cfg->pcfg.qdelay_ref = fq_pie_sysctl.pcfg.qdelay_ref;
1114                 else
1115                         fqp_cfg->pcfg.qdelay_ref = ep->par[0];
1116                 if (ep->par[1] < 0)
1117                         fqp_cfg->pcfg.tupdate = fq_pie_sysctl.pcfg.tupdate;
1118                 else
1119                         fqp_cfg->pcfg.tupdate = ep->par[1];
1120                 if (ep->par[2] < 0)
1121                         fqp_cfg->pcfg.max_burst = fq_pie_sysctl.pcfg.max_burst;
1122                 else
1123                         fqp_cfg->pcfg.max_burst = ep->par[2];
1124                 if (ep->par[3] < 0)
1125                         fqp_cfg->pcfg.max_ecnth = fq_pie_sysctl.pcfg.max_ecnth;
1126                 else
1127                         fqp_cfg->pcfg.max_ecnth = ep->par[3];
1128                 if (ep->par[4] < 0)
1129                         fqp_cfg->pcfg.alpha = fq_pie_sysctl.pcfg.alpha;
1130                 else
1131                         fqp_cfg->pcfg.alpha = ep->par[4];
1132                 if (ep->par[5] < 0)
1133                         fqp_cfg->pcfg.beta = fq_pie_sysctl.pcfg.beta;
1134                 else
1135                         fqp_cfg->pcfg.beta = ep->par[5];
1136                 if (ep->par[6] < 0)
1137                         fqp_cfg->pcfg.flags = 0;
1138                 else
1139                         fqp_cfg->pcfg.flags = ep->par[6];
1140
1141                 /* FQ configurations */
1142                 if (ep->par[7] < 0)
1143                         fqp_cfg->quantum = fq_pie_sysctl.quantum;
1144                 else
1145                         fqp_cfg->quantum = ep->par[7];
1146                 if (ep->par[8] < 0)
1147                         fqp_cfg->limit = fq_pie_sysctl.limit;
1148                 else
1149                         fqp_cfg->limit = ep->par[8];
1150                 if (ep->par[9] < 0)
1151                         fqp_cfg->flows_cnt = fq_pie_sysctl.flows_cnt;
1152                 else
1153                         fqp_cfg->flows_cnt = ep->par[9];
1154
1155                 /* Bound the configurations */
1156                 fqp_cfg->pcfg.qdelay_ref = BOUND_VAR(fqp_cfg->pcfg.qdelay_ref,
1157                         1, 5 * AQM_TIME_1S);
1158                 fqp_cfg->pcfg.tupdate = BOUND_VAR(fqp_cfg->pcfg.tupdate,
1159                         1, 5 * AQM_TIME_1S);
1160                 fqp_cfg->pcfg.max_burst = BOUND_VAR(fqp_cfg->pcfg.max_burst,
1161                         0, 5 * AQM_TIME_1S);
1162                 fqp_cfg->pcfg.max_ecnth = BOUND_VAR(fqp_cfg->pcfg.max_ecnth,
1163                         0, PIE_SCALE);
1164                 fqp_cfg->pcfg.alpha = BOUND_VAR(fqp_cfg->pcfg.alpha, 0, 7 * PIE_SCALE);
1165                 fqp_cfg->pcfg.beta = BOUND_VAR(fqp_cfg->pcfg.beta, 0, 7 * PIE_SCALE);
1166
1167                 fqp_cfg->quantum = BOUND_VAR(fqp_cfg->quantum,1,9000);
1168                 fqp_cfg->limit= BOUND_VAR(fqp_cfg->limit,1,20480);
1169                 fqp_cfg->flows_cnt= BOUND_VAR(fqp_cfg->flows_cnt,1,65536);
1170         }
1171         else {
1172                 D("Wrong parameters for fq_pie scheduler");
1173                 return 1;
1174         }
1175
1176         return 0;
1177 }
1178
1179 /*
1180  * Return FQ-PIE scheduler configurations
1181  * the configurations for the scheduler is passed to userland.
1182  */
1183 static int
1184 fq_pie_getconfig (struct dn_schk *_schk, struct dn_extra_parms *ep) {
1185         struct fq_pie_schk *schk = (struct fq_pie_schk *)(_schk+1);
1186         struct dn_sch_fq_pie_parms *fqp_cfg;
1187
1188         fqp_cfg = &schk->cfg;
1189
1190         strcpy(ep->name, fq_pie_desc.name);
1191         ep->par[0] = fqp_cfg->pcfg.qdelay_ref;
1192         ep->par[1] = fqp_cfg->pcfg.tupdate;
1193         ep->par[2] = fqp_cfg->pcfg.max_burst;
1194         ep->par[3] = fqp_cfg->pcfg.max_ecnth;
1195         ep->par[4] = fqp_cfg->pcfg.alpha;
1196         ep->par[5] = fqp_cfg->pcfg.beta;
1197         ep->par[6] = fqp_cfg->pcfg.flags;
1198
1199         ep->par[7] = fqp_cfg->quantum;
1200         ep->par[8] = fqp_cfg->limit;
1201         ep->par[9] = fqp_cfg->flows_cnt;
1202
1203         return 0;
1204 }
1205
1206 /*
1207  *  FQ-PIE scheduler descriptor
1208  * contains the type of the scheduler, the name, the size of extra
1209  * data structures, and function pointers.
1210  */
1211 static struct dn_alg fq_pie_desc = {
1212         _SI( .type = )  DN_SCHED_FQ_PIE,
1213         _SI( .name = ) "FQ_PIE",
1214         _SI( .flags = ) 0,
1215
1216         _SI( .schk_datalen = ) sizeof(struct fq_pie_schk),
1217         _SI( .si_datalen = ) sizeof(struct fq_pie_si) - sizeof(struct dn_sch_inst),
1218         _SI( .q_datalen = ) 0,
1219
1220         _SI( .enqueue = ) fq_pie_enqueue,
1221         _SI( .dequeue = ) fq_pie_dequeue,
1222         _SI( .config = ) fq_pie_config, /* new sched i.e. sched X config ...*/
1223         _SI( .destroy = ) NULL,  /*sched x delete */
1224         _SI( .new_sched = ) fq_pie_new_sched, /* new schd instance */
1225         _SI( .free_sched = ) fq_pie_free_sched, /* delete schd instance */
1226         _SI( .new_fsk = ) NULL,
1227         _SI( .free_fsk = ) NULL,
1228         _SI( .new_queue = ) NULL,
1229         _SI( .free_queue = ) NULL,
1230         _SI( .getconfig = )  fq_pie_getconfig,
1231         _SI( .ref_count = ) 0
1232 };
1233
1234 DECLARE_DNSCHED_MODULE(dn_fq_pie, &fq_pie_desc);