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

Cache object: 071479ba7ce8bf6eba3f432992986f17

[ 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