sys/netpfil/ipfw/dn_sched_fq_pie.c

   1 /*
   2  * FQ_PIE - The FlowQueue-PIE scheduler/AQM
   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 /* Important note:
  35  * As there is no an office document for FQ-PIE specification, we used
  36  * FQ-CoDel algorithm with some modifications to implement FQ-PIE.
  37  * This FQ-PIE implementation is a beta version and have not been tested
  38  * extensively. Our FQ-PIE uses stand-alone PIE AQM per sub-queue. By
  39  * default, timestamp is used to calculate queue delay instead of departure
  40  * rate estimation method. Although departure rate estimation is available
  41  * as testing option, the results could be incorrect. Moreover, turning PIE on
  42  * and off option is available but it does not work properly in this version.
  43  */
  44
  45
  46 #ifdef _KERNEL
  47 #include <sys/malloc.h>
  48 #include <sys/socket.h>
  49 #include <sys/kernel.h>
  50 #include <sys/mbuf.h>
  51 #include <sys/lock.h>
  52 #include <sys/module.h>
  53 #include <sys/mutex.h>
  54 #include <net/if.h>     /* IFNAMSIZ */
  55 #include <netinet/in.h>
  56 #include <netinet/ip_var.h>             /* ipfw_rule_ref */
  57 #include <netinet/ip_fw.h>      /* flow_id */
  58 #include <netinet/ip_dummynet.h>
  59
  60 #include <sys/proc.h>
  61 #include <sys/rwlock.h>
  62
  63 #include <netpfil/ipfw/ip_fw_private.h>
  64 #include <sys/sysctl.h>
  65 #include <netinet/ip.h>
  66 #include <netinet/ip6.h>
  67 #include <netinet/ip_icmp.h>
  68 #include <netinet/tcp.h>
  69 #include <netinet/udp.h>
  70 #include <sys/queue.h>
  71 #include <sys/hash.h>
  72
  73 #include <netpfil/ipfw/dn_heap.h>
  74 #include <netpfil/ipfw/ip_dn_private.h>
  75
  76 #include <netpfil/ipfw/dn_aqm.h>
  77 #include <netpfil/ipfw/dn_aqm_pie.h>
  78 #include <netpfil/ipfw/dn_sched.h>
  79
  80 #else
  81 #include <dn_test.h>
  82 #endif
  83
  84 #define DN_SCHED_FQ_PIE 7
  85
  86 /* list of queues */
  87 STAILQ_HEAD(fq_pie_list, fq_pie_flow) ;
  88
  89 /* FQ_PIE parameters including PIE */
  90 struct dn_sch_fq_pie_parms {
  91         struct dn_aqm_pie_parms pcfg;   /* PIE configuration Parameters */
  92         /* FQ_PIE Parameters */
  93         uint32_t flows_cnt;     /* number of flows */
  94         uint32_t limit; /* hard limit of FQ_PIE queue size*/
  95         uint32_t quantum;
  96 };
  97
  98 /* flow (sub-queue) stats */
  99 struct flow_stats {
 100         uint64_t tot_pkts;      /* statistics counters  */
 101         uint64_t tot_bytes;
 102         uint32_t length;                /* Queue length, in packets */
 103         uint32_t len_bytes;     /* Queue length, in bytes */
 104         uint32_t drops;
 105 };
 106
 107 /* A flow of packets (sub-queue)*/
 108 struct fq_pie_flow {
 109         struct mq       mq;     /* list of packets */
 110         struct flow_stats stats;        /* statistics */
 111         int deficit;
 112         int active;             /* 1: flow is active (in a list) */
 113         struct pie_status pst;  /* pie status variables */
 114         struct fq_pie_si_extra *psi_extra;
 115         STAILQ_ENTRY(fq_pie_flow) flowchain;
 116 };
 117
 118 /* extra fq_pie scheduler configurations */
 119 struct fq_pie_schk {
 120         struct dn_sch_fq_pie_parms cfg;
 121 };
 122
 123
 124 /* fq_pie scheduler instance extra state vars.
 125  * The purpose of separation this structure is to preserve number of active
 126  * sub-queues and the flows array pointer even after the scheduler instance
 127  * is destroyed.
 128  * Preserving these varaiables allows freeing the allocated memory by
 129  * fqpie_callout_cleanup() independently from fq_pie_free_sched().
 130  */
 131 struct fq_pie_si_extra {
 132         uint32_t nr_active_q;   /* number of active queues */
 133         struct fq_pie_flow *flows;      /* array of flows (queues) */
 134         };
 135
 136 /* fq_pie scheduler instance */
 137 struct fq_pie_si {
 138         struct dn_sch_inst _si; /* standard scheduler instance. SHOULD BE FIRST */
 139         struct dn_queue main_q; /* main queue is after si directly */
 140         uint32_t perturbation;  /* random value */
 141         struct fq_pie_list newflows;    /* list of new queues */
 142         struct fq_pie_list oldflows;    /* list of old queues */
 143         struct fq_pie_si_extra *si_extra; /* extra state vars*/
 144 };
 145
 146
 147 static struct dn_alg fq_pie_desc;
 148
 149 /*  Default FQ-PIE parameters including PIE */
 150 /*  PIE defaults
 151  * target=15ms, max_burst=150ms, max_ecnth=0.1,
 152  * alpha=0.125, beta=1.25, tupdate=15ms
 153  * FQ-
 154  * flows=1024, limit=10240, quantum =1514
 155  */
 156 struct dn_sch_fq_pie_parms
 157  fq_pie_sysctl = {{15000 * AQM_TIME_1US, 15000 * AQM_TIME_1US,
 158         150000 * AQM_TIME_1US, PIE_SCALE * 0.1, PIE_SCALE * 0.125,
 159         PIE_SCALE * 1.25,       PIE_CAPDROP_ENABLED | PIE_DERAND_ENABLED},
 160         1024, 10240, 1514};
 161
 162 static int
 163 fqpie_sysctl_alpha_beta_handler(SYSCTL_HANDLER_ARGS)
 164 {
 165         int error;
 166         long  value;
 167
 168         if (!strcmp(oidp->oid_name,"alpha"))
 169                 value = fq_pie_sysctl.pcfg.alpha;
 170         else
 171                 value = fq_pie_sysctl.pcfg.beta;
 172
 173         value = value * 1000 / PIE_SCALE;
 174         error = sysctl_handle_long(oidp, &value, 0, req);
 175         if (error != 0 || req->newptr == NULL)
 176                 return (error);
 177         if (value < 1 || value > 7 * PIE_SCALE)
 178                 return (EINVAL);
 179         value = (value * PIE_SCALE) / 1000;
 180         if (!strcmp(oidp->oid_name,"alpha"))
 181                         fq_pie_sysctl.pcfg.alpha = value;
 182         else
 183                 fq_pie_sysctl.pcfg.beta = value;
 184         return (0);
 185 }
 186
 187 static int
 188 fqpie_sysctl_target_tupdate_maxb_handler(SYSCTL_HANDLER_ARGS)
 189 {
 190         int error;
 191         long  value;
 192
 193         if (!strcmp(oidp->oid_name,"target"))
 194                 value = fq_pie_sysctl.pcfg.qdelay_ref;
 195         else if (!strcmp(oidp->oid_name,"tupdate"))
 196                 value = fq_pie_sysctl.pcfg.tupdate;
 197         else
 198                 value = fq_pie_sysctl.pcfg.max_burst;
 199
 200         value = value / AQM_TIME_1US;
 201         error = sysctl_handle_long(oidp, &value, 0, req);
 202         if (error != 0 || req->newptr == NULL)
 203                 return (error);
 204         if (value < 1 || value > 10 * AQM_TIME_1S)
 205                 return (EINVAL);
 206         value = value * AQM_TIME_1US;
 207
 208         if (!strcmp(oidp->oid_name,"target"))
 209                 fq_pie_sysctl.pcfg.qdelay_ref  = value;
 210         else if (!strcmp(oidp->oid_name,"tupdate"))
 211                 fq_pie_sysctl.pcfg.tupdate  = value;
 212         else
 213                 fq_pie_sysctl.pcfg.max_burst = value;
 214         return (0);
 215 }
 216
 217 static int
 218 fqpie_sysctl_max_ecnth_handler(SYSCTL_HANDLER_ARGS)
 219 {
 220         int error;
 221         long  value;
 222
 223         value = fq_pie_sysctl.pcfg.max_ecnth;
 224         value = value * 1000 / PIE_SCALE;
 225         error = sysctl_handle_long(oidp, &value, 0, req);
 226         if (error != 0 || req->newptr == NULL)
 227                 return (error);
 228         if (value < 1 || value > PIE_SCALE)
 229                 return (EINVAL);
 230         value = (value * PIE_SCALE) / 1000;
 231         fq_pie_sysctl.pcfg.max_ecnth = value;
 232         return (0);
 233 }
 234
 235 /* define FQ- PIE sysctl variables */
 236 SYSBEGIN(f4)
 237 SYSCTL_DECL(_net_inet);
 238 SYSCTL_DECL(_net_inet_ip);
 239 SYSCTL_DECL(_net_inet_ip_dummynet);
 240 static SYSCTL_NODE(_net_inet_ip_dummynet, OID_AUTO, fqpie,
 241         CTLFLAG_RW, 0, "FQ_PIE");
 242
 243 #ifdef SYSCTL_NODE
 244
 245 SYSCTL_PROC(_net_inet_ip_dummynet_fqpie, OID_AUTO, target,
 246         CTLTYPE_LONG | CTLFLAG_RW, NULL, 0,
 247         fqpie_sysctl_target_tupdate_maxb_handler, "L",
 248         "queue target in microsecond");
 249
 250 SYSCTL_PROC(_net_inet_ip_dummynet_fqpie, OID_AUTO, tupdate,
 251         CTLTYPE_LONG | CTLFLAG_RW, NULL, 0,
 252         fqpie_sysctl_target_tupdate_maxb_handler, "L",
 253         "the frequency of drop probability calculation in microsecond");
 254
 255 SYSCTL_PROC(_net_inet_ip_dummynet_fqpie, OID_AUTO, max_burst,
 256         CTLTYPE_LONG | CTLFLAG_RW, NULL, 0,
 257         fqpie_sysctl_target_tupdate_maxb_handler, "L",
 258         "Burst allowance interval in microsecond");
 259
 260 SYSCTL_PROC(_net_inet_ip_dummynet_fqpie, OID_AUTO, max_ecnth,
 261         CTLTYPE_LONG | CTLFLAG_RW, NULL, 0,
 262         fqpie_sysctl_max_ecnth_handler, "L",
 263         "ECN safeguard threshold scaled by 1000");
 264
 265 SYSCTL_PROC(_net_inet_ip_dummynet_fqpie, OID_AUTO, alpha,
 266         CTLTYPE_LONG | CTLFLAG_RW, NULL, 0,
 267         fqpie_sysctl_alpha_beta_handler, "L", "PIE alpha scaled by 1000");
 268
 269 SYSCTL_PROC(_net_inet_ip_dummynet_fqpie, OID_AUTO, beta,
 270         CTLTYPE_LONG | CTLFLAG_RW, NULL, 0,
 271         fqpie_sysctl_alpha_beta_handler, "L", "beta scaled by 1000");
 272
 273 SYSCTL_UINT(_net_inet_ip_dummynet_fqpie, OID_AUTO, quantum,
 274         CTLFLAG_RW, &fq_pie_sysctl.quantum, 1514, "quantum for FQ_PIE");
 275 SYSCTL_UINT(_net_inet_ip_dummynet_fqpie, OID_AUTO, flows,
 276         CTLFLAG_RW, &fq_pie_sysctl.flows_cnt, 1024, "Number of queues for FQ_PIE");
 277 SYSCTL_UINT(_net_inet_ip_dummynet_fqpie, OID_AUTO, limit,
 278         CTLFLAG_RW, &fq_pie_sysctl.limit, 10240, "limit for FQ_PIE");
 279 #endif
 280
 281 /* Helper function to update queue&main-queue and scheduler statistics.
 282  * negative len & drop -> drop
 283  * negative len -> dequeue
 284  * positive len -> enqueue
 285  * positive len + drop -> drop during enqueue
 286  */
 287 __inline static void
 288 fq_update_stats(struct fq_pie_flow *q, struct fq_pie_si *si, int len,
 289         int drop)
 290 {
 291         int inc = 0;
 292
 293         if (len < 0)
 294                 inc = -1;
 295         else if (len > 0)
 296                 inc = 1;
 297
 298         if (drop) {
 299                 si->main_q.ni.drops ++;
 300                 q->stats.drops ++;
 301                 si->_si.ni.drops ++;
 302                 io_pkt_drop ++;
 303         }
 304
 305         if (!drop || (drop && len < 0)) {
 306                 /* Update stats for the main queue */
 307                 si->main_q.ni.length += inc;
 308                 si->main_q.ni.len_bytes += len;
 309
 310                 /*update sub-queue stats */
 311                 q->stats.length += inc;
 312                 q->stats.len_bytes += len;
 313
 314                 /*update scheduler instance stats */
 315                 si->_si.ni.length += inc;
 316                 si->_si.ni.len_bytes += len;
 317         }
 318
 319         if (inc > 0) {
 320                 si->main_q.ni.tot_bytes += len;
 321                 si->main_q.ni.tot_pkts ++;
 322
 323                 q->stats.tot_bytes +=len;
 324                 q->stats.tot_pkts++;
 325
 326                 si->_si.ni.tot_bytes +=len;
 327                 si->_si.ni.tot_pkts ++;
 328         }
 329
 330 }
 331
 332 /*
 333  * Extract a packet from the head of sub-queue 'q'
 334  * Return a packet or NULL if the queue is empty.
 335  * If getts is set, also extract packet's timestamp from mtag.
 336  */
 337 __inline static struct mbuf *
 338 fq_pie_extract_head(struct fq_pie_flow *q, aqm_time_t *pkt_ts,
 339         struct fq_pie_si *si, int getts)
 340 {
 341         struct mbuf *m = q->mq.head;
 342
 343         if (m == NULL)
 344                 return m;
 345         q->mq.head = m->m_nextpkt;
 346
 347         fq_update_stats(q, si, -m->m_pkthdr.len, 0);
 348
 349         if (si->main_q.ni.length == 0) /* queue is now idle */
 350                         si->main_q.q_time = dn_cfg.curr_time;
 351
 352         if (getts) {
 353                 /* extract packet timestamp*/
 354                 struct m_tag *mtag;
 355                 mtag = m_tag_locate(m, MTAG_ABI_COMPAT, DN_AQM_MTAG_TS, NULL);
 356                 if (mtag == NULL){
 357                         D("PIE timestamp mtag not found!");
 358                         *pkt_ts = 0;
 359                 } else {
 360                         *pkt_ts = *(aqm_time_t *)(mtag + 1);
 361                         m_tag_delete(m,mtag);
 362                 }
 363         }
 364         return m;
 365 }
 366
 367 /*
 368  * Callout function for drop probability calculation
 369  * This function is called over tupdate ms and takes pointer of FQ-PIE
 370  * flow as an argument
 371   */
 372 static void
 373 fq_calculate_drop_prob(void *x)
 374 {
 375         struct fq_pie_flow *q = (struct fq_pie_flow *) x;
 376         struct pie_status *pst = &q->pst;
 377         struct dn_aqm_pie_parms *pprms;
 378         int64_t p, prob, oldprob;
 379         aqm_time_t now;
 380         int p_isneg;
 381
 382         now = AQM_UNOW;
 383         pprms = pst->parms;
 384         prob = pst->drop_prob;
 385
 386         /* calculate current qdelay using DRE method.
 387          * If TS is used and no data in the queue, reset current_qdelay
 388          * as it stays at last value during dequeue process.
 389         */
 390         if (pprms->flags & PIE_DEPRATEEST_ENABLED)
 391                 pst->current_qdelay = ((uint64_t)q->stats.len_bytes  * pst->avg_dq_time)
 392                         >> PIE_DQ_THRESHOLD_BITS;
 393         else
 394                 if (!q->stats.len_bytes)
 395                         pst->current_qdelay = 0;
 396
 397         /* calculate drop probability */
 398         p = (int64_t)pprms->alpha *
 399                 ((int64_t)pst->current_qdelay - (int64_t)pprms->qdelay_ref);
 400         p +=(int64_t) pprms->beta *
 401                 ((int64_t)pst->current_qdelay - (int64_t)pst->qdelay_old);
 402
 403         /* take absolute value so right shift result is well defined */
 404         p_isneg = p < 0;
 405         if (p_isneg) {
 406                 p = -p;
 407         }
 408
 409         /* We PIE_MAX_PROB shift by 12-bits to increase the division precision  */
 410         p *= (PIE_MAX_PROB << 12) / AQM_TIME_1S;
 411
 412         /* auto-tune drop probability */
 413         if (prob < (PIE_MAX_PROB / 1000000)) /* 0.000001 */
 414                 p >>= 11 + PIE_FIX_POINT_BITS + 12;
 415         else if (prob < (PIE_MAX_PROB / 100000)) /* 0.00001 */
 416                 p >>= 9 + PIE_FIX_POINT_BITS + 12;
 417         else if (prob < (PIE_MAX_PROB / 10000)) /* 0.0001 */
 418                 p >>= 7 + PIE_FIX_POINT_BITS + 12;
 419         else if (prob < (PIE_MAX_PROB / 1000)) /* 0.001 */
 420                 p >>= 5 + PIE_FIX_POINT_BITS + 12;
 421         else if (prob < (PIE_MAX_PROB / 100)) /* 0.01 */
 422                 p >>= 3 + PIE_FIX_POINT_BITS + 12;
 423         else if (prob < (PIE_MAX_PROB / 10)) /* 0.1 */
 424                 p >>= 1 + PIE_FIX_POINT_BITS + 12;
 425         else
 426                 p >>= PIE_FIX_POINT_BITS + 12;
 427
 428         oldprob = prob;
 429
 430         if (p_isneg) {
 431                 prob = prob - p;
 432
 433                 /* check for multiplication underflow */
 434                 if (prob > oldprob) {
 435                         prob= 0;
 436                         D("underflow");
 437                 }
 438         } else {
 439                 /* Cap Drop adjustment */
 440                 if ((pprms->flags & PIE_CAPDROP_ENABLED) &&
 441                     prob >= PIE_MAX_PROB / 10 &&
 442                     p > PIE_MAX_PROB / 50 ) {
 443                         p = PIE_MAX_PROB / 50;
 444                 }
 445
 446                 prob = prob + p;
 447
 448                 /* check for multiplication overflow */
 449                 if (prob<oldprob) {
 450                         D("overflow");
 451                         prob= PIE_MAX_PROB;
 452                 }
 453         }
 454
 455         /*
 456          * decay the drop probability exponentially
 457          * and restrict it to range 0 to PIE_MAX_PROB
 458          */
 459         if (prob < 0) {
 460                 prob = 0;
 461         } else {
 462                 if (pst->current_qdelay == 0 && pst->qdelay_old == 0) {
 463                         /* 0.98 ~= 1- 1/64 */
 464                         prob = prob - (prob >> 6);
 465                 }
 466
 467                 if (prob > PIE_MAX_PROB) {
 468                         prob = PIE_MAX_PROB;
 469                 }
 470         }
 471
 472         pst->drop_prob = prob;
 473
 474         /* store current delay value */
 475         pst->qdelay_old = pst->current_qdelay;
 476
 477         /* update burst allowance */
 478         if ((pst->sflags & PIE_ACTIVE) && pst->burst_allowance) {
 479                 if (pst->burst_allowance > pprms->tupdate)
 480                         pst->burst_allowance -= pprms->tupdate;
 481                 else
 482                         pst->burst_allowance = 0;
 483         }
 484
 485         if (pst->sflags & PIE_ACTIVE)
 486         callout_reset_sbt(&pst->aqm_pie_callout,
 487                 (uint64_t)pprms->tupdate * SBT_1US,
 488                 0, fq_calculate_drop_prob, q, 0);
 489
 490         mtx_unlock(&pst->lock_mtx);
 491 }
 492
 493 /*
 494  * Reset PIE variables & activate the queue
 495  */
 496 __inline static void
 497 fq_activate_pie(struct fq_pie_flow *q)
 498 {
 499         struct pie_status *pst = &q->pst;
 500         struct dn_aqm_pie_parms *pprms;
 501
 502         mtx_lock(&pst->lock_mtx);
 503         pprms = pst->parms;
 504
 505         pprms = pst->parms;
 506         pst->drop_prob = 0;
 507         pst->qdelay_old = 0;
 508         pst->burst_allowance = pprms->max_burst;
 509         pst->accu_prob = 0;
 510         pst->dq_count = 0;
 511         pst->avg_dq_time = 0;
 512         pst->sflags = PIE_INMEASUREMENT | PIE_ACTIVE;
 513         pst->measurement_start = AQM_UNOW;
 514
 515         callout_reset_sbt(&pst->aqm_pie_callout,
 516                 (uint64_t)pprms->tupdate * SBT_1US,
 517                 0, fq_calculate_drop_prob, q, 0);
 518
 519         mtx_unlock(&pst->lock_mtx);
 520 }
 521
 522
 523  /*
 524   * Deactivate PIE and stop probe update callout
 525   */
 526 __inline static void
 527 fq_deactivate_pie(struct pie_status *pst)
 528 {
 529         mtx_lock(&pst->lock_mtx);
 530         pst->sflags &= ~(PIE_ACTIVE | PIE_INMEASUREMENT);
 531         callout_stop(&pst->aqm_pie_callout);
 532         //D("PIE Deactivated");
 533         mtx_unlock(&pst->lock_mtx);
 534 }
 535
 536  /*
 537   * Initialize PIE for sub-queue 'q'
 538   */
 539 static int
 540 pie_init(struct fq_pie_flow *q, struct fq_pie_schk *fqpie_schk)
 541 {
 542         struct pie_status *pst=&q->pst;
 543         struct dn_aqm_pie_parms *pprms = pst->parms;
 544
 545         int err = 0;
 546         if (!pprms){
 547                 D("AQM_PIE is not configured");
 548                 err = EINVAL;
 549         } else {
 550                 q->psi_extra->nr_active_q++;
 551
 552                 /* For speed optimization, we caculate 1/3 queue size once here */
 553                 // XXX limit divided by number of queues divided by 3 ???
 554                 pst->one_third_q_size = (fqpie_schk->cfg.limit /
 555                         fqpie_schk->cfg.flows_cnt) / 3;
 556
 557                 mtx_init(&pst->lock_mtx, "mtx_pie", NULL, MTX_DEF);
 558                 callout_init_mtx(&pst->aqm_pie_callout, &pst->lock_mtx,
 559                         CALLOUT_RETURNUNLOCKED);
 560         }
 561
 562         return err;
 563 }
 564
 565 /*
 566  * callout function to destroy PIE lock, and free fq_pie flows and fq_pie si
 567  * extra memory when number of active sub-queues reaches zero.
 568  * 'x' is a fq_pie_flow to be destroyed
 569  */
 570 static void
 571 fqpie_callout_cleanup(void *x)
 572 {
 573         struct fq_pie_flow *q = x;
 574         struct pie_status *pst = &q->pst;
 575         struct fq_pie_si_extra *psi_extra;
 576
 577         mtx_unlock(&pst->lock_mtx);
 578         mtx_destroy(&pst->lock_mtx);
 579         psi_extra = q->psi_extra;
 580
 581         DN_BH_WLOCK();
 582         psi_extra->nr_active_q--;
 583
 584         /* when all sub-queues are destroyed, free flows fq_pie extra vars memory */
 585         if (!psi_extra->nr_active_q) {
 586                 free(psi_extra->flows, M_DUMMYNET);
 587                 free(psi_extra, M_DUMMYNET);
 588                 fq_pie_desc.ref_count--;
 589         }
 590         DN_BH_WUNLOCK();
 591 }
 592
 593 /*
 594  * Clean up PIE status for sub-queue 'q'
 595  * Stop callout timer and destroy mtx using fqpie_callout_cleanup() callout.
 596  */
 597 static int
 598 pie_cleanup(struct fq_pie_flow *q)
 599 {
 600         struct pie_status *pst  = &q->pst;
 601
 602         mtx_lock(&pst->lock_mtx);
 603         callout_reset_sbt(&pst->aqm_pie_callout,
 604                 SBT_1US, 0, fqpie_callout_cleanup, q, 0);
 605         mtx_unlock(&pst->lock_mtx);
 606         return 0;
 607 }
 608
 609 /*
 610  * Dequeue and return a pcaket from sub-queue 'q' or NULL if 'q' is empty.
 611  * Also, caculate depature time or queue delay using timestamp
 612  */
 613  static struct mbuf *
 614 pie_dequeue(struct fq_pie_flow *q, struct fq_pie_si *si)
 615 {
 616         struct mbuf *m;
 617         struct dn_aqm_pie_parms *pprms;
 618         struct pie_status *pst;
 619         aqm_time_t now;
 620         aqm_time_t pkt_ts, dq_time;
 621         int32_t w;
 622
 623         pst  = &q->pst;
 624         pprms = q->pst.parms;
 625
 626         /*we extarct packet ts only when Departure Rate Estimation dis not used*/
 627         m = fq_pie_extract_head(q, &pkt_ts, si,
 628                 !(pprms->flags & PIE_DEPRATEEST_ENABLED));
 629
 630         if (!m || !(pst->sflags & PIE_ACTIVE))
 631                 return m;
 632
 633         now = AQM_UNOW;
 634         if (pprms->flags & PIE_DEPRATEEST_ENABLED) {
 635                 /* calculate average depature time */
 636                 if(pst->sflags & PIE_INMEASUREMENT) {
 637                         pst->dq_count += m->m_pkthdr.len;
 638
 639                         if (pst->dq_count >= PIE_DQ_THRESHOLD) {
 640                                 dq_time = now - pst->measurement_start;
 641
 642                                 /*
 643                                  * if we don't have old avg dq_time i.e PIE is (re)initialized,
 644                                  * don't use weight to calculate new avg_dq_time
 645                                  */
 646                                 if(pst->avg_dq_time == 0)
 647                                         pst->avg_dq_time = dq_time;
 648                                 else {
 649                                         /*
 650                                          * weight = PIE_DQ_THRESHOLD/2^6, but we scaled
 651                                          * weight by 2^8. Thus, scaled
 652                                          * weight = PIE_DQ_THRESHOLD /2^8
 653                                          * */
 654                                         w = PIE_DQ_THRESHOLD >> 8;
 655                                         pst->avg_dq_time = (dq_time* w
 656                                                 + (pst->avg_dq_time * ((1L << 8) - w))) >> 8;
 657                                         pst->sflags &= ~PIE_INMEASUREMENT;
 658                                 }
 659                         }
 660                 }
 661
 662                 /*
 663                  * Start new measurment cycle when the queue has
 664                  *  PIE_DQ_THRESHOLD worth of bytes.
 665                  */
 666                 if(!(pst->sflags & PIE_INMEASUREMENT) &&
 667                         q->stats.len_bytes >= PIE_DQ_THRESHOLD) {
 668                         pst->sflags |= PIE_INMEASUREMENT;
 669                         pst->measurement_start = now;
 670                         pst->dq_count = 0;
 671                 }
 672         }
 673         /* Optionally, use packet timestamp to estimate queue delay */
 674         else
 675                 pst->current_qdelay = now - pkt_ts;
 676
 677         return m;
 678 }
 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                         m_freem(m);
 740                         t = DROP;
 741                 }
 742                 *(aqm_time_t *)(mtag + 1) = AQM_UNOW;
 743                 m_tag_prepend(m, mtag);
 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 = 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 = malloc(schk->cfg.flows_cnt * sizeof(struct fq_pie_flow),
1038                  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         fq_pie_desc.ref_count++;
1063
1064         return 0;
1065 }
1066
1067
1068 /*
1069  * Free fq_pie scheduler instance.
1070  */
1071 static int
1072 fq_pie_free_sched(struct dn_sch_inst *_si)
1073 {
1074         struct fq_pie_si *si;
1075         struct fq_pie_schk *schk;
1076         struct fq_pie_flow *flows;
1077         int i;
1078
1079         si = (struct fq_pie_si *)_si;
1080         schk = (struct fq_pie_schk *)(_si->sched+1);
1081         flows = si->si_extra->flows;
1082         for (i = 0; i < schk->cfg.flows_cnt; i++) {
1083                 pie_cleanup(&flows[i]);
1084         }
1085         si->si_extra = NULL;
1086         return 0;
1087 }
1088
1089 /*
1090  * Configure FQ-PIE scheduler.
1091  * the configurations for the scheduler is passed fromipfw  userland.
1092  */
1093 static int
1094 fq_pie_config(struct dn_schk *_schk)
1095 {
1096         struct fq_pie_schk *schk;
1097         struct dn_extra_parms *ep;
1098         struct dn_sch_fq_pie_parms *fqp_cfg;
1099
1100         schk = (struct fq_pie_schk *)(_schk+1);
1101         ep = (struct dn_extra_parms *) _schk->cfg;
1102
1103         /* par array contains fq_pie configuration as follow
1104          * PIE: 0- qdelay_ref,1- tupdate, 2- max_burst
1105          * 3- max_ecnth, 4- alpha, 5- beta, 6- flags
1106          * FQ_PIE: 7- quantum, 8- limit, 9- flows
1107          */
1108         if (ep && ep->oid.len ==sizeof(*ep) &&
1109                 ep->oid.subtype == DN_SCH_PARAMS) {
1110
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
1186         struct fq_pie_schk *schk = (struct fq_pie_schk *)(_schk+1);
1187         struct dn_sch_fq_pie_parms *fqp_cfg;
1188
1189         fqp_cfg = &schk->cfg;
1190
1191         strcpy(ep->name, fq_pie_desc.name);
1192         ep->par[0] = fqp_cfg->pcfg.qdelay_ref;
1193         ep->par[1] = fqp_cfg->pcfg.tupdate;
1194         ep->par[2] = fqp_cfg->pcfg.max_burst;
1195         ep->par[3] = fqp_cfg->pcfg.max_ecnth;
1196         ep->par[4] = fqp_cfg->pcfg.alpha;
1197         ep->par[5] = fqp_cfg->pcfg.beta;
1198         ep->par[6] = fqp_cfg->pcfg.flags;
1199
1200         ep->par[7] = fqp_cfg->quantum;
1201         ep->par[8] = fqp_cfg->limit;
1202         ep->par[9] = fqp_cfg->flows_cnt;
1203
1204         return 0;
1205 }
1206
1207 /*
1208  *  FQ-PIE scheduler descriptor
1209  * contains the type of the scheduler, the name, the size of extra
1210  * data structures, and function pointers.
1211  */
1212 static struct dn_alg fq_pie_desc = {
1213         _SI( .type = )  DN_SCHED_FQ_PIE,
1214         _SI( .name = ) "FQ_PIE",
1215         _SI( .flags = ) 0,
1216
1217         _SI( .schk_datalen = ) sizeof(struct fq_pie_schk),
1218         _SI( .si_datalen = ) sizeof(struct fq_pie_si) - sizeof(struct dn_sch_inst),
1219         _SI( .q_datalen = ) 0,
1220
1221         _SI( .enqueue = ) fq_pie_enqueue,
1222         _SI( .dequeue = ) fq_pie_dequeue,
1223         _SI( .config = ) fq_pie_config, /* new sched i.e. sched X config ...*/
1224         _SI( .destroy = ) NULL,  /*sched x delete */
1225         _SI( .new_sched = ) fq_pie_new_sched, /* new schd instance */
1226         _SI( .free_sched = ) fq_pie_free_sched, /* delete schd instance */
1227         _SI( .new_fsk = ) NULL,
1228         _SI( .free_fsk = ) NULL,
1229         _SI( .new_queue = ) NULL,
1230         _SI( .free_queue = ) NULL,
1231         _SI( .getconfig = )  fq_pie_getconfig,
1232         _SI( .ref_count = ) 0
1233 };
1234
1235 DECLARE_DNSCHED_MODULE(dn_fq_pie, &fq_pie_desc);