dn_sched_rr.c

Version: - FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10
    1 /*-
    2  * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
    3  *
    4  * Copyright (c) 2010 Riccardo Panicucci, Universita` di Pisa
    5  * All rights reserved
    6  *
    7  * Redistribution and use in source and binary forms, with or without
    8  * modification, are permitted provided that the following conditions
    9  * are met:
   10  * 1. Redistributions of source code must retain the above copyright
   11  *    notice, this list of conditions and the following disclaimer.
   12  * 2. Redistributions in binary form must reproduce the above copyright
   13  *    notice, this list of conditions and the following disclaimer in the
   14  *    documentation and/or other materials provided with the distribution.
   15  *
   16  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
   17  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   19  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
   20  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   21  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
   22  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   23  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   24  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
   25  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   26  * SUCH DAMAGE.
   27  */
   28 
   29 /*
   30  * $FreeBSD$
   31  */
   32 
   33 #ifdef _KERNEL
   34 #include <sys/malloc.h>
   35 #include <sys/socket.h>
   36 #include <sys/socketvar.h>
   37 #include <sys/kernel.h>
   38 #include <sys/lock.h>
   39 #include <sys/mbuf.h>
   40 #include <sys/module.h>
   41 #include <sys/rwlock.h>
   42 #include <net/if.h>     /* IFNAMSIZ */
   43 #include <netinet/in.h>
   44 #include <netinet/ip_var.h>             /* ipfw_rule_ref */
   45 #include <netinet/ip_fw.h>      /* flow_id */
   46 #include <netinet/ip_dummynet.h>
   47 #include <netpfil/ipfw/ip_fw_private.h>
   48 #include <netpfil/ipfw/dn_heap.h>
   49 #include <netpfil/ipfw/ip_dn_private.h>
   50 #ifdef NEW_AQM
   51 #include <netpfil/ipfw/dn_aqm.h>
   52 #endif
   53 #include <netpfil/ipfw/dn_sched.h>
   54 #else
   55 #include <dn_test.h>
   56 #endif
   57 
   58 #define DN_SCHED_RR     3 // XXX Where?
   59 
   60 struct rr_queue {
   61         struct dn_queue q;              /* Standard queue */
   62         int status;                     /* 1: queue is in the list */
   63         uint32_t credit;                /* max bytes we can transmit */
   64         uint32_t quantum;               /* quantum * weight */
   65         struct rr_queue *qnext;         /* */
   66 };
   67 
   68 /* struct rr_schk contains global config parameters
   69  * and is right after dn_schk
   70  */
   71 struct rr_schk {
   72         uint32_t min_q;         /* Min quantum */
   73         uint32_t max_q;         /* Max quantum */
   74         uint32_t q_bytes;       /* default quantum in bytes */
   75 };
   76 
   77 /* per-instance round robin list, right after dn_sch_inst */
   78 struct rr_si {
   79         struct rr_queue *head, *tail;   /* Pointer to current queue */
   80 };
   81 
   82 /* Append a queue to the rr list */
   83 static inline void
   84 rr_append(struct rr_queue *q, struct rr_si *si)
   85 {
   86         q->status = 1;          /* mark as in-rr_list */
   87         q->credit = q->quantum; /* initialize credit */
   88 
   89         /* append to the tail */
   90         if (si->head == NULL)
   91                 si->head = q;
   92         else
   93                 si->tail->qnext = q;
   94         si->tail = q;           /* advance the tail pointer */
   95         q->qnext = si->head;    /* make it circular */
   96 }
   97 
   98 /* Remove the head queue from circular list. */
   99 static inline void
  100 rr_remove_head(struct rr_si *si)
  101 {
  102         if (si->head == NULL)
  103                 return; /* empty queue */
  104         si->head->status = 0;
  105 
  106         if (si->head == si->tail) {
  107                 si->head = si->tail = NULL;
  108                 return;
  109         }
  110 
  111         si->head = si->head->qnext;
  112         si->tail->qnext = si->head;
  113 }
  114 
  115 /* Remove a queue from circular list.
  116  * XXX see if ti can be merge with remove_queue()
  117  */
  118 static inline void
  119 remove_queue_q(struct rr_queue *q, struct rr_si *si)
  120 {
  121         struct rr_queue *prev;
  122 
  123         if (q->status != 1)
  124                 return;
  125         if (q == si->head) {
  126                 rr_remove_head(si);
  127                 return;
  128         }
  129 
  130         for (prev = si->head; prev; prev = prev->qnext) {
  131                 if (prev->qnext != q)
  132                         continue;
  133                 prev->qnext = q->qnext;
  134                 if (q == si->tail)
  135                         si->tail = prev;
  136                 q->status = 0;
  137                 break;
  138         }
  139 }
  140 
  141 static inline void
  142 next_pointer(struct rr_si *si)
  143 {
  144         if (si->head == NULL)
  145                 return; /* empty queue */
  146 
  147         si->head = si->head->qnext;
  148         si->tail = si->tail->qnext;
  149 }
  150 
  151 static int
  152 rr_enqueue(struct dn_sch_inst *_si, struct dn_queue *q, struct mbuf *m)
  153 {
  154         struct rr_si *si;
  155         struct rr_queue *rrq;
  156 
  157         if (m != q->mq.head) {
  158                 if (dn_enqueue(q, m, 0)) /* packet was dropped */
  159                         return 1;
  160                 if (m != q->mq.head)
  161                         return 0;
  162         }
  163 
  164         /* If reach this point, queue q was idle */
  165         si = (struct rr_si *)(_si + 1);
  166         rrq = (struct rr_queue *)q;
  167 
  168         if (rrq->status == 1) /* Queue is already in the queue list */
  169                 return 0;
  170 
  171         /* Insert the queue in the queue list */
  172         rr_append(rrq, si);
  173 
  174         return 0;
  175 }
  176 
  177 static struct mbuf *
  178 rr_dequeue(struct dn_sch_inst *_si)
  179 {
  180         /* Access scheduler instance private data */
  181         struct rr_si *si = (struct rr_si *)(_si + 1);
  182         struct rr_queue *rrq;
  183         uint64_t len;
  184 
  185         while ( (rrq = si->head) ) {
  186                 struct mbuf *m = rrq->q.mq.head;
  187                 if ( m == NULL) {
  188                         /* empty queue, remove from list */
  189                         rr_remove_head(si);
  190                         continue;
  191                 }
  192                 len = m->m_pkthdr.len;
  193 
  194                 if (len > rrq->credit) {
  195                         /* Packet too big */
  196                         rrq->credit += rrq->quantum;
  197                         /* Try next queue */
  198                         next_pointer(si);
  199                 } else {
  200                         rrq->credit -= len;
  201                         return dn_dequeue(&rrq->q);
  202                 }
  203         }
  204 
  205         /* no packet to dequeue*/
  206         return NULL;
  207 }
  208 
  209 static int
  210 rr_config(struct dn_schk *_schk)
  211 {
  212         struct rr_schk *schk = (struct rr_schk *)(_schk + 1);
  213         ND("called");
  214 
  215         /* use reasonable quantums (64..2k bytes, default 1500) */
  216         schk->min_q = 64;
  217         schk->max_q = 2048;
  218         schk->q_bytes = 1500;   /* quantum */
  219 
  220         return 0;
  221 }
  222 
  223 static int
  224 rr_new_sched(struct dn_sch_inst *_si)
  225 {
  226         struct rr_si *si = (struct rr_si *)(_si + 1);
  227 
  228         ND("called");
  229         si->head = si->tail = NULL;
  230 
  231         return 0;
  232 }
  233 
  234 static int
  235 rr_free_sched(struct dn_sch_inst *_si)
  236 {
  237         (void)_si;
  238         ND("called");
  239         /* Nothing to do? */
  240         return 0;
  241 }
  242 
  243 static int
  244 rr_new_fsk(struct dn_fsk *fs)
  245 {
  246         struct rr_schk *schk = (struct rr_schk *)(fs->sched + 1);
  247         /* par[0] is the weight, par[1] is the quantum step */
  248         /* make sure the product fits an uint32_t */
  249         ipdn_bound_var(&fs->fs.par[0], 1,
  250                 1, 65536, "RR weight");
  251         ipdn_bound_var(&fs->fs.par[1], schk->q_bytes,
  252                 schk->min_q, schk->max_q, "RR quantum");
  253         return 0;
  254 }
  255 
  256 static int
  257 rr_new_queue(struct dn_queue *_q)
  258 {
  259         struct rr_queue *q = (struct rr_queue *)_q;
  260         uint64_t quantum;
  261 
  262         _q->ni.oid.subtype = DN_SCHED_RR;
  263 
  264         quantum = (uint64_t)_q->fs->fs.par[0] * _q->fs->fs.par[1];
  265         if (quantum >= (1ULL<< 32)) {
  266                 D("quantum too large, truncating to 4G - 1");
  267                 quantum = (1ULL<< 32) - 1;
  268         }
  269         q->quantum = quantum;
  270         ND("called, q->quantum %d", q->quantum);
  271         q->credit = q->quantum;
  272         q->status = 0;
  273 
  274         if (_q->mq.head != NULL) {
  275                 /* Queue NOT empty, insert in the queue list */
  276                 rr_append(q, (struct rr_si *)(_q->_si + 1));
  277         }
  278         return 0;
  279 }
  280 
  281 static int
  282 rr_free_queue(struct dn_queue *_q)
  283 {
  284         struct rr_queue *q = (struct rr_queue *)_q;
  285 
  286         ND("called");
  287         if (q->status == 1) {
  288                 struct rr_si *si = (struct rr_si *)(_q->_si + 1);
  289                 remove_queue_q(q, si);
  290         }
  291         return 0;
  292 }
  293 
  294 /*
  295  * RR scheduler descriptor
  296  * contains the type of the scheduler, the name, the size of the
  297  * structures and function pointers.
  298  */
  299 static struct dn_alg rr_desc = {
  300         _SI( .type = ) DN_SCHED_RR,
  301         _SI( .name = ) "RR",
  302         _SI( .flags = ) DN_MULTIQUEUE,
  303 
  304         _SI( .schk_datalen = ) sizeof(struct rr_schk),
  305         _SI( .si_datalen = ) sizeof(struct rr_si),
  306         _SI( .q_datalen = ) sizeof(struct rr_queue) - sizeof(struct dn_queue),
  307 
  308         _SI( .enqueue = ) rr_enqueue,
  309         _SI( .dequeue = ) rr_dequeue,
  310 
  311         _SI( .config = ) rr_config,
  312         _SI( .destroy = ) NULL,
  313         _SI( .new_sched = ) rr_new_sched,
  314         _SI( .free_sched = ) rr_free_sched,
  315         _SI( .new_fsk = ) rr_new_fsk,
  316         _SI( .free_fsk = ) NULL,
  317         _SI( .new_queue = ) rr_new_queue,
  318         _SI( .free_queue = ) rr_free_queue,
  319 #ifdef NEW_AQM
  320         _SI( .getconfig = )  NULL,
  321 #endif
  322 };
  323 
  324 DECLARE_DNSCHED_MODULE(dn_rr, &rr_desc);
Cache object: 136110ddc5297a248efa5793ccf6b3a6
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]
This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.
FreeBSD/Linux Kernel Cross Reference sys/netpfil/ipfw/dn_sched_rr.c

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