sys/netpfil/ipfw/dn_sched_rr.c

   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);