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