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
 381         now = AQM_UNOW;
 382         pprms = pst->parms;
 383         prob = pst->drop_prob;
 384
 385         /* calculate current qdelay */
 386         if (pprms->flags & PIE_DEPRATEEST_ENABLED) {
 387                 pst->current_qdelay = ((uint64_t)q->stats.len_bytes  * pst->avg_dq_time)
 388                         >> PIE_DQ_THRESHOLD_BITS;
 389         }
 390
 391         /* calculate drop probability */
 392         p = (int64_t)pprms->alpha *
 393                 ((int64_t)pst->current_qdelay - (int64_t)pprms->qdelay_ref);
 394         p +=(int64_t) pprms->beta *
 395                 ((int64_t)pst->current_qdelay - (int64_t)pst->qdelay_old);
 396
 397         /* We PIE_MAX_PROB shift by 12-bits to increase the division precision  */
 398         p *= (PIE_MAX_PROB << 12) / AQM_TIME_1S;
 399
 400         /* auto-tune drop probability */
 401         if (prob < (PIE_MAX_PROB / 1000000)) /* 0.000001 */
 402                 p >>= 11 + PIE_FIX_POINT_BITS + 12;
 403         else if (prob < (PIE_MAX_PROB / 100000)) /* 0.00001 */
 404                 p >>= 9 + PIE_FIX_POINT_BITS + 12;
 405         else if (prob < (PIE_MAX_PROB / 10000)) /* 0.0001 */
 406                 p >>= 7 + PIE_FIX_POINT_BITS + 12;
 407         else if (prob < (PIE_MAX_PROB / 1000)) /* 0.001 */
 408                 p >>= 5 + PIE_FIX_POINT_BITS + 12;
 409         else if (prob < (PIE_MAX_PROB / 100)) /* 0.01 */
 410                 p >>= 3 + PIE_FIX_POINT_BITS + 12;
 411         else if (prob < (PIE_MAX_PROB / 10)) /* 0.1 */
 412                 p >>= 1 + PIE_FIX_POINT_BITS + 12;
 413         else
 414                 p >>= PIE_FIX_POINT_BITS + 12;
 415
 416         oldprob = prob;
 417
 418         /* Cap Drop adjustment */
 419         if ((pprms->flags & PIE_CAPDROP_ENABLED) && prob >= PIE_MAX_PROB / 10
 420                 && p > PIE_MAX_PROB / 50 )
 421                         p = PIE_MAX_PROB / 50;
 422
 423         prob = prob + p;
 424
 425         /* decay the drop probability exponentially */
 426         if (pst->current_qdelay == 0 && pst->qdelay_old == 0)
 427                 /* 0.98 ~= 1- 1/64 */
 428                 prob = prob - (prob >> 6);
 429
 430
 431         /* check for multiplication over/under flow */
 432         if (p>0) {
 433                 if (prob<oldprob) {
 434                         D("overflow");
 435                         prob= PIE_MAX_PROB;
 436                 }
 437         }
 438         else
 439                 if (prob>oldprob) {
 440                         prob= 0;
 441                         D("underflow");
 442                 }
 443
 444         /* make drop probability between 0 and PIE_MAX_PROB*/
 445         if (prob < 0)
 446                 prob = 0;
 447         else if (prob > PIE_MAX_PROB)
 448                 prob = PIE_MAX_PROB;
 449
 450         pst->drop_prob = prob;
 451
 452         /* store current delay value */
 453         pst->qdelay_old = pst->current_qdelay;
 454
 455         /* update burst allowance */
 456         if ((pst->sflags & PIE_ACTIVE) && pst->burst_allowance) {
 457                 if (pst->burst_allowance > pprms->tupdate)
 458                         pst->burst_allowance -= pprms->tupdate;
 459                 else
 460                         pst->burst_allowance = 0;
 461         }
 462
 463         if (pst->sflags & PIE_ACTIVE)
 464         callout_reset_sbt(&pst->aqm_pie_callout,
 465                 (uint64_t)pprms->tupdate * SBT_1US,
 466                 0, fq_calculate_drop_prob, q, 0);
 467
 468         mtx_unlock(&pst->lock_mtx);
 469 }
 470
 471 /*
 472  * Reset PIE variables & activate the queue
 473  */
 474 __inline static void
 475 fq_activate_pie(struct fq_pie_flow *q)
 476 {
 477         struct pie_status *pst = &q->pst;
 478         struct dn_aqm_pie_parms *pprms;
 479
 480         mtx_lock(&pst->lock_mtx);
 481         pprms = pst->parms;
 482
 483         pprms = pst->parms;
 484         pst->drop_prob = 0;
 485         pst->qdelay_old = 0;
 486         pst->burst_allowance = pprms->max_burst;
 487         pst->accu_prob = 0;
 488         pst->dq_count = 0;
 489         pst->avg_dq_time = 0;
 490         pst->sflags = PIE_INMEASUREMENT | PIE_ACTIVE;
 491         pst->measurement_start = AQM_UNOW;
 492
 493         callout_reset_sbt(&pst->aqm_pie_callout,
 494                 (uint64_t)pprms->tupdate * SBT_1US,
 495                 0, fq_calculate_drop_prob, q, 0);
 496
 497         mtx_unlock(&pst->lock_mtx);
 498 }
 499
 500
 501  /*
 502   * Deactivate PIE and stop probe update callout
 503   */
 504 __inline static void
 505 fq_deactivate_pie(struct pie_status *pst)
 506 {
 507         mtx_lock(&pst->lock_mtx);
 508         pst->sflags &= ~(PIE_ACTIVE | PIE_INMEASUREMENT);
 509         callout_stop(&pst->aqm_pie_callout);
 510         //D("PIE Deactivated");
 511         mtx_unlock(&pst->lock_mtx);
 512 }
 513
 514  /*
 515   * Initialize PIE for sub-queue 'q'
 516   */
 517 static int
 518 pie_init(struct fq_pie_flow *q, struct fq_pie_schk *fqpie_schk)
 519 {
 520         struct pie_status *pst=&q->pst;
 521         struct dn_aqm_pie_parms *pprms = pst->parms;
 522
 523         int err = 0;
 524         if (!pprms){
 525                 D("AQM_PIE is not configured");
 526                 err = EINVAL;
 527         } else {
 528                 q->psi_extra->nr_active_q++;
 529
 530                 /* For speed optimization, we caculate 1/3 queue size once here */
 531                 // XXX limit divided by number of queues divided by 3 ???
 532                 pst->one_third_q_size = (fqpie_schk->cfg.limit /
 533                         fqpie_schk->cfg.flows_cnt) / 3;
 534
 535                 mtx_init(&pst->lock_mtx, "mtx_pie", NULL, MTX_DEF);
 536                 callout_init_mtx(&pst->aqm_pie_callout, &pst->lock_mtx,
 537                         CALLOUT_RETURNUNLOCKED);
 538         }
 539
 540         return err;
 541 }
 542
 543 /*
 544  * callout function to destroy PIE lock, and free fq_pie flows and fq_pie si
 545  * extra memory when number of active sub-queues reaches zero.
 546  * 'x' is a fq_pie_flow to be destroyed
 547  */
 548 static void
 549 fqpie_callout_cleanup(void *x)
 550 {
 551         struct fq_pie_flow *q = x;
 552         struct pie_status *pst = &q->pst;
 553         struct fq_pie_si_extra *psi_extra;
 554
 555         mtx_unlock(&pst->lock_mtx);
 556         mtx_destroy(&pst->lock_mtx);
 557         psi_extra = q->psi_extra;
 558
 559         DN_BH_WLOCK();
 560         psi_extra->nr_active_q--;
 561
 562         /* when all sub-queues are destroyed, free flows fq_pie extra vars memory */
 563         if (!psi_extra->nr_active_q) {
 564                 free(psi_extra->flows, M_DUMMYNET);
 565                 free(psi_extra, M_DUMMYNET);
 566                 fq_pie_desc.ref_count--;
 567         }
 568         DN_BH_WUNLOCK();
 569 }
 570
 571 /*
 572  * Clean up PIE status for sub-queue 'q'
 573  * Stop callout timer and destroy mtx using fqpie_callout_cleanup() callout.
 574  */
 575 static int
 576 pie_cleanup(struct fq_pie_flow *q)
 577 {
 578         struct pie_status *pst  = &q->pst;
 579
 580         mtx_lock(&pst->lock_mtx);
 581         callout_reset_sbt(&pst->aqm_pie_callout,
 582                 SBT_1US, 0, fqpie_callout_cleanup, q, 0);
 583         mtx_unlock(&pst->lock_mtx);
 584         return 0;
 585 }
 586
 587 /*
 588  * Dequeue and return a pcaket from sub-queue 'q' or NULL if 'q' is empty.
 589  * Also, caculate depature time or queue delay using timestamp
 590  */
 591  static struct mbuf *
 592 pie_dequeue(struct fq_pie_flow *q, struct fq_pie_si *si)
 593 {
 594         struct mbuf *m;
 595         struct dn_aqm_pie_parms *pprms;
 596         struct pie_status *pst;
 597         aqm_time_t now;
 598         aqm_time_t pkt_ts, dq_time;
 599         int32_t w;
 600
 601         pst  = &q->pst;
 602         pprms = q->pst.parms;
 603
 604         /*we extarct packet ts only when Departure Rate Estimation dis not used*/
 605         m = fq_pie_extract_head(q, &pkt_ts, si,
 606                 !(pprms->flags & PIE_DEPRATEEST_ENABLED));
 607
 608         if (!m || !(pst->sflags & PIE_ACTIVE))
 609                 return m;
 610
 611         now = AQM_UNOW;
 612         if (pprms->flags & PIE_DEPRATEEST_ENABLED) {
 613                 /* calculate average depature time */
 614                 if(pst->sflags & PIE_INMEASUREMENT) {
 615                         pst->dq_count += m->m_pkthdr.len;
 616
 617                         if (pst->dq_count >= PIE_DQ_THRESHOLD) {
 618                                 dq_time = now - pst->measurement_start;
 619
 620                                 /*
 621                                  * if we don't have old avg dq_time i.e PIE is (re)initialized,
 622                                  * don't use weight to calculate new avg_dq_time
 623                                  */
 624                                 if(pst->avg_dq_time == 0)
 625                                         pst->avg_dq_time = dq_time;
 626                                 else {
 627                                         /*
 628                                          * weight = PIE_DQ_THRESHOLD/2^6, but we scaled
 629                                          * weight by 2^8. Thus, scaled
 630                                          * weight = PIE_DQ_THRESHOLD /2^8
 631                                          * */
 632                                         w = PIE_DQ_THRESHOLD >> 8;
 633                                         pst->avg_dq_time = (dq_time* w
 634                                                 + (pst->avg_dq_time * ((1L << 8) - w))) >> 8;
 635                                         pst->sflags &= ~PIE_INMEASUREMENT;
 636                                 }
 637                         }
 638                 }
 639
 640                 /*
 641                  * Start new measurment cycle when the queue has
 642                  *  PIE_DQ_THRESHOLD worth of bytes.
 643                  */
 644                 if(!(pst->sflags & PIE_INMEASUREMENT) &&
 645                         q->stats.len_bytes >= PIE_DQ_THRESHOLD) {
 646                         pst->sflags |= PIE_INMEASUREMENT;
 647                         pst->measurement_start = now;
 648                         pst->dq_count = 0;
 649                 }
 650         }
 651         /* Optionally, use packet timestamp to estimate queue delay */
 652         else
 653                 pst->current_qdelay = now - pkt_ts;
 654
 655         return m;
 656 }
 657
 658
 659  /*
 660  * Enqueue a packet in q, subject to space and FQ-PIE queue management policy
 661  * (whose parameters are in q->fs).
 662  * Update stats for the queue and the scheduler.
 663  * Return 0 on success, 1 on drop. The packet is consumed anyways.
 664  */
 665 static int
 666 pie_enqueue(struct fq_pie_flow *q, struct mbuf* m, struct fq_pie_si *si)
 667 {
 668         uint64_t len;
 669         struct pie_status *pst;
 670         struct dn_aqm_pie_parms *pprms;
 671         int t;
 672
 673         len = m->m_pkthdr.len;
 674         pst  = &q->pst;
 675         pprms = pst->parms;
 676         t = ENQUE;
 677
 678         /* drop/mark the packet when PIE is active and burst time elapsed */
 679         if (pst->sflags & PIE_ACTIVE && pst->burst_allowance == 0
 680                 && drop_early(pst, q->stats.len_bytes) == DROP) {
 681                         /*
 682                          * if drop_prob over ECN threshold, drop the packet
 683                          * otherwise mark and enqueue it.
 684                          */
 685                         if (pprms->flags & PIE_ECN_ENABLED && pst->drop_prob <
 686                                 (pprms->max_ecnth << (PIE_PROB_BITS - PIE_FIX_POINT_BITS))
 687                                 && ecn_mark(m))
 688                                 t = ENQUE;
 689                         else
 690                                 t = DROP;
 691                 }
 692
 693         /* Turn PIE on when 1/3 of the queue is full */
 694         if (!(pst->sflags & PIE_ACTIVE) && q->stats.len_bytes >=
 695                 pst->one_third_q_size) {
 696                 fq_activate_pie(q);
 697         }
 698
 699         /*  reset burst tolerance and optinally turn PIE off*/
 700         if (pst->drop_prob == 0 && pst->current_qdelay < (pprms->qdelay_ref >> 1)
 701                 && pst->qdelay_old < (pprms->qdelay_ref >> 1)) {
 702
 703                         pst->burst_allowance = pprms->max_burst;
 704                 if (pprms->flags & PIE_ON_OFF_MODE_ENABLED && q->stats.len_bytes<=0)
 705                         fq_deactivate_pie(pst);
 706         }
 707
 708         /* Use timestamp if Departure Rate Estimation mode is disabled */
 709         if (t != DROP && !(pprms->flags & PIE_DEPRATEEST_ENABLED)) {
 710                 /* Add TS to mbuf as a TAG */
 711                 struct m_tag *mtag;
 712                 mtag = m_tag_locate(m, MTAG_ABI_COMPAT, DN_AQM_MTAG_TS, NULL);
 713                 if (mtag == NULL)
 714                         mtag = m_tag_alloc(MTAG_ABI_COMPAT, DN_AQM_MTAG_TS,
 715                                 sizeof(aqm_time_t), M_NOWAIT);
 716                 if (mtag == NULL) {
 717                         m_freem(m);
 718                         t = DROP;
 719                 }
 720                 *(aqm_time_t *)(mtag + 1) = AQM_UNOW;
 721                 m_tag_prepend(m, mtag);
 722         }
 723
 724         if (t != DROP) {
 725                 mq_append(&q->mq, m);
 726                 fq_update_stats(q, si, len, 0);
 727                 return 0;
 728         } else {
 729                 fq_update_stats(q, si, len, 1);
 730                 pst->accu_prob = 0;
 731                 FREE_PKT(m);
 732                 return 1;
 733         }
 734
 735         return 0;
 736 }
 737
 738 /* Drop a packet form the head of FQ-PIE sub-queue */
 739 static void
 740 pie_drop_head(struct fq_pie_flow *q, struct fq_pie_si *si)
 741 {
 742         struct mbuf *m = q->mq.head;
 743
 744         if (m == NULL)
 745                 return;
 746         q->mq.head = m->m_nextpkt;
 747
 748         fq_update_stats(q, si, -m->m_pkthdr.len, 1);
 749
 750         if (si->main_q.ni.length == 0) /* queue is now idle */
 751                         si->main_q.q_time = dn_cfg.curr_time;
 752         /* reset accu_prob after packet drop */
 753         q->pst.accu_prob = 0;
 754
 755         FREE_PKT(m);
 756 }
 757
 758 /*
 759  * Classify a packet to queue number using Jenkins hash function.
 760  * Return: queue number
 761  * the input of the hash are protocol no, perturbation, src IP, dst IP,
 762  * src port, dst port,
 763  */
 764 static inline int
 765 fq_pie_classify_flow(struct mbuf *m, uint16_t fcount, struct fq_pie_si *si)
 766 {
 767         struct ip *ip;
 768         struct tcphdr *th;
 769         struct udphdr *uh;
 770         uint8_t tuple[41];
 771         uint16_t hash=0;
 772
 773 //#ifdef INET6
 774         struct ip6_hdr *ip6;
 775         int isip6;
 776         isip6 = (mtod(m, struct ip *)->ip_v == 6) ? 1 : 0;
 777
 778         if(isip6) {
 779                 ip6 = mtod(m, struct ip6_hdr *);
 780                 *((uint8_t *) &tuple[0]) = ip6->ip6_nxt;
 781                 *((uint32_t *) &tuple[1]) = si->perturbation;
 782                 memcpy(&tuple[5], ip6->ip6_src.s6_addr, 16);
 783                 memcpy(&tuple[21], ip6->ip6_dst.s6_addr, 16);
 784
 785                 switch (ip6->ip6_nxt) {
 786                 case IPPROTO_TCP:
 787                         th = (struct tcphdr *)(ip6 + 1);
 788                         *((uint16_t *) &tuple[37]) = th->th_dport;
 789                         *((uint16_t *) &tuple[39]) = th->th_sport;
 790                         break;
 791
 792                 case IPPROTO_UDP:
 793                         uh = (struct udphdr *)(ip6 + 1);
 794                         *((uint16_t *) &tuple[37]) = uh->uh_dport;
 795                         *((uint16_t *) &tuple[39]) = uh->uh_sport;
 796                         break;
 797                 default:
 798                         memset(&tuple[37], 0, 4);
 799                 }
 800
 801                 hash = jenkins_hash(tuple, 41, HASHINIT) %  fcount;
 802                 return hash;
 803         }
 804 //#endif
 805
 806         /* IPv4 */
 807         ip = mtod(m, struct ip *);
 808         *((uint8_t *) &tuple[0]) = ip->ip_p;
 809         *((uint32_t *) &tuple[1]) = si->perturbation;
 810         *((uint32_t *) &tuple[5]) = ip->ip_src.s_addr;
 811         *((uint32_t *) &tuple[9]) = ip->ip_dst.s_addr;
 812
 813         switch (ip->ip_p) {
 814                 case IPPROTO_TCP:
 815                         th = (struct tcphdr *)(ip + 1);
 816                         *((uint16_t *) &tuple[13]) = th->th_dport;
 817                         *((uint16_t *) &tuple[15]) = th->th_sport;
 818                         break;
 819
 820                 case IPPROTO_UDP:
 821                         uh = (struct udphdr *)(ip + 1);
 822                         *((uint16_t *) &tuple[13]) = uh->uh_dport;
 823                         *((uint16_t *) &tuple[15]) = uh->uh_sport;
 824                         break;
 825                 default:
 826                         memset(&tuple[13], 0, 4);
 827         }
 828         hash = jenkins_hash(tuple, 17, HASHINIT) % fcount;
 829
 830         return hash;
 831 }
 832
 833 /*
 834  * Enqueue a packet into an appropriate queue according to
 835  * FQ-CoDe; algorithm.
 836  */
 837 static int
 838 fq_pie_enqueue(struct dn_sch_inst *_si, struct dn_queue *_q,
 839         struct mbuf *m)
 840 {
 841         struct fq_pie_si *si;
 842         struct fq_pie_schk *schk;
 843         struct dn_sch_fq_pie_parms *param;
 844         struct dn_queue *mainq;
 845         struct fq_pie_flow *flows;
 846         int idx, drop, i, maxidx;
 847
 848         mainq = (struct dn_queue *)(_si + 1);
 849         si = (struct fq_pie_si *)_si;
 850         flows = si->si_extra->flows;
 851         schk = (struct fq_pie_schk *)(si->_si.sched+1);
 852         param = &schk->cfg;
 853
 854          /* classify a packet to queue number*/
 855         idx = fq_pie_classify_flow(m, param->flows_cnt, si);
 856
 857         /* enqueue packet into appropriate queue using PIE AQM.
 858          * Note: 'pie_enqueue' function returns 1 only when it unable to
 859          * add timestamp to packet (no limit check)*/
 860         drop = pie_enqueue(&flows[idx], m, si);
 861
 862         /* pie unable to timestamp a packet */
 863         if (drop)
 864                 return 1;
 865
 866         /* If the flow (sub-queue) is not active ,then add it to tail of
 867          * new flows list, initialize and activate it.
 868          */
 869         if (!flows[idx].active) {
 870                 STAILQ_INSERT_TAIL(&si->newflows, &flows[idx], flowchain);
 871                 flows[idx].deficit = param->quantum;
 872                 fq_activate_pie(&flows[idx]);
 873                 flows[idx].active = 1;
 874         }
 875
 876         /* check the limit for all queues and remove a packet from the
 877          * largest one
 878          */
 879         if (mainq->ni.length > schk->cfg.limit) {
 880                 /* find first active flow */
 881                 for (maxidx = 0; maxidx < schk->cfg.flows_cnt; maxidx++)
 882                         if (flows[maxidx].active)
 883                                 break;
 884                 if (maxidx < schk->cfg.flows_cnt) {
 885                         /* find the largest sub- queue */
 886                         for (i = maxidx + 1; i < schk->cfg.flows_cnt; i++)
 887                                 if (flows[i].active && flows[i].stats.length >
 888                                         flows[maxidx].stats.length)
 889                                         maxidx = i;
 890                         pie_drop_head(&flows[maxidx], si);
 891                         drop = 1;
 892                 }
 893         }
 894
 895         return drop;
 896 }
 897
 898 /*
 899  * Dequeue a packet from an appropriate queue according to
 900  * FQ-CoDel algorithm.
 901  */
 902 static struct mbuf *
 903 fq_pie_dequeue(struct dn_sch_inst *_si)
 904 {
 905         struct fq_pie_si *si;
 906         struct fq_pie_schk *schk;
 907         struct dn_sch_fq_pie_parms *param;
 908         struct fq_pie_flow *f;
 909         struct mbuf *mbuf;
 910         struct fq_pie_list *fq_pie_flowlist;
 911
 912         si = (struct fq_pie_si *)_si;
 913         schk = (struct fq_pie_schk *)(si->_si.sched+1);
 914         param = &schk->cfg;
 915
 916         do {
 917                 /* select a list to start with */
 918                 if (STAILQ_EMPTY(&si->newflows))
 919                         fq_pie_flowlist = &si->oldflows;
 920                 else
 921                         fq_pie_flowlist = &si->newflows;
 922
 923                 /* Both new and old queue lists are empty, return NULL */
 924                 if (STAILQ_EMPTY(fq_pie_flowlist))
 925                         return NULL;
 926
 927                 f = STAILQ_FIRST(fq_pie_flowlist);
 928                 while (f != NULL)       {
 929                         /* if there is no flow(sub-queue) deficit, increase deficit
 930                          * by quantum, move the flow to the tail of old flows list
 931                          * and try another flow.
 932                          * Otherwise, the flow will be used for dequeue.
 933                          */
 934                         if (f->deficit < 0) {
 935                                  f->deficit += param->quantum;
 936                                  STAILQ_REMOVE_HEAD(fq_pie_flowlist, flowchain);
 937                                  STAILQ_INSERT_TAIL(&si->oldflows, f, flowchain);
 938                          } else
 939                                  break;
 940
 941                         f = STAILQ_FIRST(fq_pie_flowlist);
 942                 }
 943
 944                 /* the new flows list is empty, try old flows list */
 945                 if (STAILQ_EMPTY(fq_pie_flowlist))
 946                         continue;
 947
 948                 /* Dequeue a packet from the selected flow */
 949                 mbuf = pie_dequeue(f, si);
 950
 951                 /* pie did not return a packet */
 952                 if (!mbuf) {
 953                         /* If the selected flow belongs to new flows list, then move
 954                          * it to the tail of old flows list. Otherwise, deactivate it and
 955                          * remove it from the old list and
 956                          */
 957                         if (fq_pie_flowlist == &si->newflows) {
 958                                 STAILQ_REMOVE_HEAD(fq_pie_flowlist, flowchain);
 959                                 STAILQ_INSERT_TAIL(&si->oldflows, f, flowchain);
 960                         }       else {
 961                                 f->active = 0;
 962                                 fq_deactivate_pie(&f->pst);
 963                                 STAILQ_REMOVE_HEAD(fq_pie_flowlist, flowchain);
 964                         }
 965                         /* start again */
 966                         continue;
 967                 }
 968
 969                 /* we have a packet to return,
 970                  * update flow deficit and return the packet*/
 971                 f->deficit -= mbuf->m_pkthdr.len;
 972                 return mbuf;
 973
 974         } while (1);
 975
 976         /* unreachable point */
 977         return NULL;
 978 }
 979
 980 /*
 981  * Initialize fq_pie scheduler instance.
 982  * also, allocate memory for flows array.
 983  */
 984 static int
 985 fq_pie_new_sched(struct dn_sch_inst *_si)
 986 {
 987         struct fq_pie_si *si;
 988         struct dn_queue *q;
 989         struct fq_pie_schk *schk;
 990         struct fq_pie_flow *flows;
 991         int i;
 992
 993         si = (struct fq_pie_si *)_si;
 994         schk = (struct fq_pie_schk *)(_si->sched+1);
 995
 996         if(si->si_extra) {
 997                 D("si already configured!");
 998                 return 0;
 999         }
1000
1001         /* init the main queue */
1002         q = &si->main_q;
1003         set_oid(&q->ni.oid, DN_QUEUE, sizeof(*q));
1004         q->_si = _si;
1005         q->fs = _si->sched->fs;
1006
1007         /* allocate memory for scheduler instance extra vars */
1008         si->si_extra = malloc(sizeof(struct fq_pie_si_extra),
1009                  M_DUMMYNET, M_NOWAIT | M_ZERO);
1010         if (si->si_extra == NULL) {
1011                 D("cannot allocate memory for fq_pie si extra vars");
1012                 return ENOMEM ;
1013         }
1014         /* allocate memory for flows array */
1015         si->si_extra->flows = malloc(schk->cfg.flows_cnt * sizeof(struct fq_pie_flow),
1016                  M_DUMMYNET, M_NOWAIT | M_ZERO);
1017         flows = si->si_extra->flows;
1018         if (flows == NULL) {
1019                 free(si->si_extra, M_DUMMYNET);
1020                 si->si_extra = NULL;
1021                 D("cannot allocate memory for fq_pie flows");
1022                 return ENOMEM ;
1023         }
1024
1025         /* init perturbation for this si */
1026         si->perturbation = random();
1027         si->si_extra->nr_active_q = 0;
1028
1029         /* init the old and new flows lists */
1030         STAILQ_INIT(&si->newflows);
1031         STAILQ_INIT(&si->oldflows);
1032
1033         /* init the flows (sub-queues) */
1034         for (i = 0; i < schk->cfg.flows_cnt; i++) {
1035                 flows[i].pst.parms = &schk->cfg.pcfg;
1036                 flows[i].psi_extra = si->si_extra;
1037                 pie_init(&flows[i], schk);
1038         }
1039
1040         fq_pie_desc.ref_count++;
1041
1042         return 0;
1043 }
1044
1045
1046 /*
1047  * Free fq_pie scheduler instance.
1048  */
1049 static int
1050 fq_pie_free_sched(struct dn_sch_inst *_si)
1051 {
1052         struct fq_pie_si *si;
1053         struct fq_pie_schk *schk;
1054         struct fq_pie_flow *flows;
1055         int i;
1056
1057         si = (struct fq_pie_si *)_si;
1058         schk = (struct fq_pie_schk *)(_si->sched+1);
1059         flows = si->si_extra->flows;
1060         for (i = 0; i < schk->cfg.flows_cnt; i++) {
1061                 pie_cleanup(&flows[i]);
1062         }
1063         si->si_extra = NULL;
1064         return 0;
1065 }
1066
1067 /*
1068  * Configure FQ-PIE scheduler.
1069  * the configurations for the scheduler is passed fromipfw  userland.
1070  */
1071 static int
1072 fq_pie_config(struct dn_schk *_schk)
1073 {
1074         struct fq_pie_schk *schk;
1075         struct dn_extra_parms *ep;
1076         struct dn_sch_fq_pie_parms *fqp_cfg;
1077
1078         schk = (struct fq_pie_schk *)(_schk+1);
1079         ep = (struct dn_extra_parms *) _schk->cfg;
1080
1081         /* par array contains fq_pie configuration as follow
1082          * PIE: 0- qdelay_ref,1- tupdate, 2- max_burst
1083          * 3- max_ecnth, 4- alpha, 5- beta, 6- flags
1084          * FQ_PIE: 7- quantum, 8- limit, 9- flows
1085          */
1086         if (ep && ep->oid.len ==sizeof(*ep) &&
1087                 ep->oid.subtype == DN_SCH_PARAMS) {
1088
1089                 fqp_cfg = &schk->cfg;
1090                 if (ep->par[0] < 0)
1091                         fqp_cfg->pcfg.qdelay_ref = fq_pie_sysctl.pcfg.qdelay_ref;
1092                 else
1093                         fqp_cfg->pcfg.qdelay_ref = ep->par[0];
1094                 if (ep->par[1] < 0)
1095                         fqp_cfg->pcfg.tupdate = fq_pie_sysctl.pcfg.tupdate;
1096                 else
1097                         fqp_cfg->pcfg.tupdate = ep->par[1];
1098                 if (ep->par[2] < 0)
1099                         fqp_cfg->pcfg.max_burst = fq_pie_sysctl.pcfg.max_burst;
1100                 else
1101                         fqp_cfg->pcfg.max_burst = ep->par[2];
1102                 if (ep->par[3] < 0)
1103                         fqp_cfg->pcfg.max_ecnth = fq_pie_sysctl.pcfg.max_ecnth;
1104                 else
1105                         fqp_cfg->pcfg.max_ecnth = ep->par[3];
1106                 if (ep->par[4] < 0)
1107                         fqp_cfg->pcfg.alpha = fq_pie_sysctl.pcfg.alpha;
1108                 else
1109                         fqp_cfg->pcfg.alpha = ep->par[4];
1110                 if (ep->par[5] < 0)
1111                         fqp_cfg->pcfg.beta = fq_pie_sysctl.pcfg.beta;
1112                 else
1113                         fqp_cfg->pcfg.beta = ep->par[5];
1114                 if (ep->par[6] < 0)
1115                         fqp_cfg->pcfg.flags = 0;
1116                 else
1117                         fqp_cfg->pcfg.flags = ep->par[6];
1118
1119                 /* FQ configurations */
1120                 if (ep->par[7] < 0)
1121                         fqp_cfg->quantum = fq_pie_sysctl.quantum;
1122                 else
1123                         fqp_cfg->quantum = ep->par[7];
1124                 if (ep->par[8] < 0)
1125                         fqp_cfg->limit = fq_pie_sysctl.limit;
1126                 else
1127                         fqp_cfg->limit = ep->par[8];
1128                 if (ep->par[9] < 0)
1129                         fqp_cfg->flows_cnt = fq_pie_sysctl.flows_cnt;
1130                 else
1131                         fqp_cfg->flows_cnt = ep->par[9];
1132
1133                 /* Bound the configurations */
1134                 fqp_cfg->pcfg.qdelay_ref = BOUND_VAR(fqp_cfg->pcfg.qdelay_ref,
1135                         1, 5 * AQM_TIME_1S);
1136                 fqp_cfg->pcfg.tupdate = BOUND_VAR(fqp_cfg->pcfg.tupdate,
1137                         1, 5 * AQM_TIME_1S);
1138                 fqp_cfg->pcfg.max_burst = BOUND_VAR(fqp_cfg->pcfg.max_burst,
1139                         0, 5 * AQM_TIME_1S);
1140                 fqp_cfg->pcfg.max_ecnth = BOUND_VAR(fqp_cfg->pcfg.max_ecnth,
1141                         0, PIE_SCALE);
1142                 fqp_cfg->pcfg.alpha = BOUND_VAR(fqp_cfg->pcfg.alpha, 0, 7 * PIE_SCALE);
1143                 fqp_cfg->pcfg.beta = BOUND_VAR(fqp_cfg->pcfg.beta, 0, 7 * PIE_SCALE);
1144
1145                 fqp_cfg->quantum = BOUND_VAR(fqp_cfg->quantum,1,9000);
1146                 fqp_cfg->limit= BOUND_VAR(fqp_cfg->limit,1,20480);
1147                 fqp_cfg->flows_cnt= BOUND_VAR(fqp_cfg->flows_cnt,1,65536);
1148         }
1149         else {
1150                 D("Wrong parameters for fq_pie scheduler");
1151                 return 1;
1152         }
1153
1154         return 0;
1155 }
1156
1157 /*
1158  * Return FQ-PIE scheduler configurations
1159  * the configurations for the scheduler is passed to userland.
1160  */
1161 static int
1162 fq_pie_getconfig (struct dn_schk *_schk, struct dn_extra_parms *ep) {
1163
1164         struct fq_pie_schk *schk = (struct fq_pie_schk *)(_schk+1);
1165         struct dn_sch_fq_pie_parms *fqp_cfg;
1166
1167         fqp_cfg = &schk->cfg;
1168
1169         strcpy(ep->name, fq_pie_desc.name);
1170         ep->par[0] = fqp_cfg->pcfg.qdelay_ref;
1171         ep->par[1] = fqp_cfg->pcfg.tupdate;
1172         ep->par[2] = fqp_cfg->pcfg.max_burst;
1173         ep->par[3] = fqp_cfg->pcfg.max_ecnth;
1174         ep->par[4] = fqp_cfg->pcfg.alpha;
1175         ep->par[5] = fqp_cfg->pcfg.beta;
1176         ep->par[6] = fqp_cfg->pcfg.flags;
1177
1178         ep->par[7] = fqp_cfg->quantum;
1179         ep->par[8] = fqp_cfg->limit;
1180         ep->par[9] = fqp_cfg->flows_cnt;
1181
1182         return 0;
1183 }
1184
1185 /*
1186  *  FQ-PIE scheduler descriptor
1187  * contains the type of the scheduler, the name, the size of extra
1188  * data structures, and function pointers.
1189  */
1190 static struct dn_alg fq_pie_desc = {
1191         _SI( .type = )  DN_SCHED_FQ_PIE,
1192         _SI( .name = ) "FQ_PIE",
1193         _SI( .flags = ) 0,
1194
1195         _SI( .schk_datalen = ) sizeof(struct fq_pie_schk),
1196         _SI( .si_datalen = ) sizeof(struct fq_pie_si) - sizeof(struct dn_sch_inst),
1197         _SI( .q_datalen = ) 0,
1198
1199         _SI( .enqueue = ) fq_pie_enqueue,
1200         _SI( .dequeue = ) fq_pie_dequeue,
1201         _SI( .config = ) fq_pie_config, /* new sched i.e. sched X config ...*/
1202         _SI( .destroy = ) NULL,  /*sched x delete */
1203         _SI( .new_sched = ) fq_pie_new_sched, /* new schd instance */
1204         _SI( .free_sched = ) fq_pie_free_sched, /* delete schd instance */
1205         _SI( .new_fsk = ) NULL,
1206         _SI( .free_fsk = ) NULL,
1207         _SI( .new_queue = ) NULL,
1208         _SI( .free_queue = ) NULL,
1209         _SI( .getconfig = )  fq_pie_getconfig,
1210         _SI( .ref_count = ) 0
1211 };
1212
1213 DECLARE_DNSCHED_MODULE(dn_fq_pie, &fq_pie_desc);