sys/netpfil/ipfw/dn_sched_rr.c

   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$
  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 #ifdef NEW_AQM
  46 #include <netpfil/ipfw/dn_aqm.h>
  47 #endif
  48 #include <netpfil/ipfw/dn_sched.h>
  49 #else
  50 #include <dn_test.h>
  51 #endif
  52
  53 #define DN_SCHED_RR     3 // XXX Where?
  54
  55 struct rr_queue {
  56         struct dn_queue q;              /* Standard queue */
  57         int status;                     /* 1: queue is in the list */
  58         int credit;                     /* Number of bytes to transmit */
  59         int quantum;                    /* quantum * C */
  60         struct rr_queue *qnext;         /* */
  61 };
  62
  63 /* struct rr_schk contains global config parameters
  64  * and is right after dn_schk
  65  */
  66 struct rr_schk {
  67         int min_q;              /* Min quantum */
  68         int max_q;              /* Max quantum */
  69         int q_bytes;            /* Bytes per quantum */
  70 };
  71
  72 /* per-instance round robin list, right after dn_sch_inst */
  73 struct rr_si {
  74         struct rr_queue *head, *tail;   /* Pointer to current queue */
  75 };
  76
  77 /* Append a queue to the rr list */
  78 static inline void
  79 rr_append(struct rr_queue *q, struct rr_si *si)
  80 {
  81         q->status = 1;          /* mark as in-rr_list */
  82         q->credit = q->quantum; /* initialize credit */
  83
  84         /* append to the tail */
  85         if (si->head == NULL)
  86                 si->head = q;
  87         else
  88                 si->tail->qnext = q;
  89         si->tail = q;           /* advance the tail pointer */
  90         q->qnext = si->head;    /* make it circular */
  91 }
  92
  93 /* Remove the head queue from circular list. */
  94 static inline void
  95 rr_remove_head(struct rr_si *si)
  96 {
  97         if (si->head == NULL)
  98                 return; /* empty queue */
  99         si->head->status = 0;
 100
 101         if (si->head == si->tail) {
 102                 si->head = si->tail = NULL;
 103                 return;
 104         }
 105
 106         si->head = si->head->qnext;
 107         si->tail->qnext = si->head;
 108 }
 109
 110 /* Remove a queue from circular list.
 111  * XXX see if ti can be merge with remove_queue()
 112  */
 113 static inline void
 114 remove_queue_q(struct rr_queue *q, struct rr_si *si)
 115 {
 116         struct rr_queue *prev;
 117
 118         if (q->status != 1)
 119                 return;
 120         if (q == si->head) {
 121                 rr_remove_head(si);
 122                 return;
 123         }
 124
 125         for (prev = si->head; prev; prev = prev->qnext) {
 126                 if (prev->qnext != q)
 127                         continue;
 128                 prev->qnext = q->qnext;
 129                 if (q == si->tail)
 130                         si->tail = prev;
 131                 q->status = 0;
 132                 break;
 133         }
 134 }
 135
 136
 137 static inline void
 138 next_pointer(struct rr_si *si)
 139 {
 140         if (si->head == NULL)
 141                 return; /* empty queue */
 142
 143         si->head = si->head->qnext;
 144         si->tail = si->tail->qnext;
 145 }
 146
 147 static int
 148 rr_enqueue(struct dn_sch_inst *_si, struct dn_queue *q, struct mbuf *m)
 149 {
 150         struct rr_si *si;
 151         struct rr_queue *rrq;
 152
 153         if (m != q->mq.head) {
 154                 if (dn_enqueue(q, m, 0)) /* packet was dropped */
 155                         return 1;
 156                 if (m != q->mq.head)
 157                         return 0;
 158         }
 159
 160         /* If reach this point, queue q was idle */
 161         si = (struct rr_si *)(_si + 1);
 162         rrq = (struct rr_queue *)q;
 163
 164         if (rrq->status == 1) /* Queue is already in the queue list */
 165                 return 0;
 166
 167         /* Insert the queue in the queue list */
 168         rr_append(rrq, si);
 169
 170         return 0;
 171 }
 172
 173 static struct mbuf *
 174 rr_dequeue(struct dn_sch_inst *_si)
 175 {
 176         /* Access scheduler instance private data */
 177         struct rr_si *si = (struct rr_si *)(_si + 1);
 178         struct rr_queue *rrq;
 179         uint64_t len;
 180
 181         while ( (rrq = si->head) ) {
 182                 struct mbuf *m = rrq->q.mq.head;
 183                 if ( m == NULL) {
 184                         /* empty queue, remove from list */
 185                         rr_remove_head(si);
 186                         continue;
 187                 }
 188                 len = m->m_pkthdr.len;
 189
 190                 if (len > rrq->credit) {
 191                         /* Packet too big */
 192                         rrq->credit += rrq->quantum;
 193                         /* Try next queue */
 194                         next_pointer(si);
 195                 } else {
 196                         rrq->credit -= len;
 197                         return dn_dequeue(&rrq->q);
 198                 }
 199         }
 200
 201         /* no packet to dequeue*/
 202         return NULL;
 203 }
 204
 205 static int
 206 rr_config(struct dn_schk *_schk)
 207 {
 208         struct rr_schk *schk = (struct rr_schk *)(_schk + 1);
 209         ND("called");
 210
 211         /* use reasonable quantums (64..2k bytes, default 1500) */
 212         schk->min_q = 64;
 213         schk->max_q = 2048;
 214         schk->q_bytes = 1500;   /* quantum */
 215
 216         return 0;
 217 }
 218
 219 static int
 220 rr_new_sched(struct dn_sch_inst *_si)
 221 {
 222         struct rr_si *si = (struct rr_si *)(_si + 1);
 223
 224         ND("called");
 225         si->head = si->tail = NULL;
 226
 227         return 0;
 228 }
 229
 230 static int
 231 rr_free_sched(struct dn_sch_inst *_si)
 232 {
 233         ND("called");
 234         /* Nothing to do? */
 235         return 0;
 236 }
 237
 238 static int
 239 rr_new_fsk(struct dn_fsk *fs)
 240 {
 241         struct rr_schk *schk = (struct rr_schk *)(fs->sched + 1);
 242         /* par[0] is the weight, par[1] is the quantum step */
 243         ipdn_bound_var(&fs->fs.par[0], 1,
 244                 1, 65536, "RR weight");
 245         ipdn_bound_var(&fs->fs.par[1], schk->q_bytes,
 246                 schk->min_q, schk->max_q, "RR quantum");
 247         return 0;
 248 }
 249
 250 static int
 251 rr_new_queue(struct dn_queue *_q)
 252 {
 253         struct rr_queue *q = (struct rr_queue *)_q;
 254
 255         _q->ni.oid.subtype = DN_SCHED_RR;
 256
 257         q->quantum = _q->fs->fs.par[0] * _q->fs->fs.par[1];
 258         ND("called, q->quantum %d", q->quantum);
 259         q->credit = q->quantum;
 260         q->status = 0;
 261
 262         if (_q->mq.head != NULL) {
 263                 /* Queue NOT empty, insert in the queue list */
 264                 rr_append(q, (struct rr_si *)(_q->_si + 1));
 265         }
 266         return 0;
 267 }
 268
 269 static int
 270 rr_free_queue(struct dn_queue *_q)
 271 {
 272         struct rr_queue *q = (struct rr_queue *)_q;
 273
 274         ND("called");
 275         if (q->status == 1) {
 276                 struct rr_si *si = (struct rr_si *)(_q->_si + 1);
 277                 remove_queue_q(q, si);
 278         }
 279         return 0;
 280 }
 281
 282 /*
 283  * RR scheduler descriptor
 284  * contains the type of the scheduler, the name, the size of the
 285  * structures and function pointers.
 286  */
 287 static struct dn_alg rr_desc = {
 288         _SI( .type = ) DN_SCHED_RR,
 289         _SI( .name = ) "RR",
 290         _SI( .flags = ) DN_MULTIQUEUE,
 291
 292         _SI( .schk_datalen = ) 0,
 293         _SI( .si_datalen = ) sizeof(struct rr_si),
 294         _SI( .q_datalen = ) sizeof(struct rr_queue) - sizeof(struct dn_queue),
 295
 296         _SI( .enqueue = ) rr_enqueue,
 297         _SI( .dequeue = ) rr_dequeue,
 298
 299         _SI( .config = ) rr_config,
 300         _SI( .destroy = ) NULL,
 301         _SI( .new_sched = ) rr_new_sched,
 302         _SI( .free_sched = ) rr_free_sched,
 303         _SI( .new_fsk = ) rr_new_fsk,
 304         _SI( .free_fsk = ) NULL,
 305         _SI( .new_queue = ) rr_new_queue,
 306         _SI( .free_queue = ) rr_free_queue,
 307 #ifdef NEW_AQM
 308         _SI( .getconfig = )  NULL,
 309 #endif
 310 };
 311
 312
 313 DECLARE_DNSCHED_MODULE(dn_rr, &rr_desc);