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
 142 static inline void
 143 next_pointer(struct rr_si *si)
 144 {
 145         if (si->head == NULL)
 146                 return; /* empty queue */
 147
 148         si->head = si->head->qnext;
 149         si->tail = si->tail->qnext;
 150 }
 151
 152 static int
 153 rr_enqueue(struct dn_sch_inst *_si, struct dn_queue *q, struct mbuf *m)
 154 {
 155         struct rr_si *si;
 156         struct rr_queue *rrq;
 157
 158         if (m != q->mq.head) {
 159                 if (dn_enqueue(q, m, 0)) /* packet was dropped */
 160                         return 1;
 161                 if (m != q->mq.head)
 162                         return 0;
 163         }
 164
 165         /* If reach this point, queue q was idle */
 166         si = (struct rr_si *)(_si + 1);
 167         rrq = (struct rr_queue *)q;
 168
 169         if (rrq->status == 1) /* Queue is already in the queue list */
 170                 return 0;
 171
 172         /* Insert the queue in the queue list */
 173         rr_append(rrq, si);
 174
 175         return 0;
 176 }
 177
 178 static struct mbuf *
 179 rr_dequeue(struct dn_sch_inst *_si)
 180 {
 181         /* Access scheduler instance private data */
 182         struct rr_si *si = (struct rr_si *)(_si + 1);
 183         struct rr_queue *rrq;
 184         uint64_t len;
 185
 186         while ( (rrq = si->head) ) {
 187                 struct mbuf *m = rrq->q.mq.head;
 188                 if ( m == NULL) {
 189                         /* empty queue, remove from list */
 190                         rr_remove_head(si);
 191                         continue;
 192                 }
 193                 len = m->m_pkthdr.len;
 194
 195                 if (len > rrq->credit) {
 196                         /* Packet too big */
 197                         rrq->credit += rrq->quantum;
 198                         /* Try next queue */
 199                         next_pointer(si);
 200                 } else {
 201                         rrq->credit -= len;
 202                         return dn_dequeue(&rrq->q);
 203                 }
 204         }
 205
 206         /* no packet to dequeue*/
 207         return NULL;
 208 }
 209
 210 static int
 211 rr_config(struct dn_schk *_schk)
 212 {
 213         struct rr_schk *schk = (struct rr_schk *)(_schk + 1);
 214         ND("called");
 215
 216         /* use reasonable quantums (64..2k bytes, default 1500) */
 217         schk->min_q = 64;
 218         schk->max_q = 2048;
 219         schk->q_bytes = 1500;   /* quantum */
 220
 221         return 0;
 222 }
 223
 224 static int
 225 rr_new_sched(struct dn_sch_inst *_si)
 226 {
 227         struct rr_si *si = (struct rr_si *)(_si + 1);
 228
 229         ND("called");
 230         si->head = si->tail = NULL;
 231
 232         return 0;
 233 }
 234
 235 static int
 236 rr_free_sched(struct dn_sch_inst *_si)
 237 {
 238         (void)_si;
 239         ND("called");
 240         /* Nothing to do? */
 241         return 0;
 242 }
 243
 244 static int
 245 rr_new_fsk(struct dn_fsk *fs)
 246 {
 247         struct rr_schk *schk = (struct rr_schk *)(fs->sched + 1);
 248         /* par[0] is the weight, par[1] is the quantum step */
 249         /* make sure the product fits an uint32_t */
 250         ipdn_bound_var(&fs->fs.par[0], 1,
 251                 1, 65536, "RR weight");
 252         ipdn_bound_var(&fs->fs.par[1], schk->q_bytes,
 253                 schk->min_q, schk->max_q, "RR quantum");
 254         return 0;
 255 }
 256
 257 static int
 258 rr_new_queue(struct dn_queue *_q)
 259 {
 260         struct rr_queue *q = (struct rr_queue *)_q;
 261         uint64_t quantum;
 262
 263         _q->ni.oid.subtype = DN_SCHED_RR;
 264
 265         quantum = (uint64_t)_q->fs->fs.par[0] * _q->fs->fs.par[1];
 266         if (quantum >= (1ULL<< 32)) {
 267                 D("quantum too large, truncating to 4G - 1");
 268                 quantum = (1ULL<< 32) - 1;
 269         }
 270         q->quantum = quantum;
 271         ND("called, q->quantum %d", q->quantum);
 272         q->credit = q->quantum;
 273         q->status = 0;
 274
 275         if (_q->mq.head != NULL) {
 276                 /* Queue NOT empty, insert in the queue list */
 277                 rr_append(q, (struct rr_si *)(_q->_si + 1));
 278         }
 279         return 0;
 280 }
 281
 282 static int
 283 rr_free_queue(struct dn_queue *_q)
 284 {
 285         struct rr_queue *q = (struct rr_queue *)_q;
 286
 287         ND("called");
 288         if (q->status == 1) {
 289                 struct rr_si *si = (struct rr_si *)(_q->_si + 1);
 290                 remove_queue_q(q, si);
 291         }
 292         return 0;
 293 }
 294
 295 /*
 296  * RR scheduler descriptor
 297  * contains the type of the scheduler, the name, the size of the
 298  * structures and function pointers.
 299  */
 300 static struct dn_alg rr_desc = {
 301         _SI( .type = ) DN_SCHED_RR,
 302         _SI( .name = ) "RR",
 303         _SI( .flags = ) DN_MULTIQUEUE,
 304
 305         _SI( .schk_datalen = ) sizeof(struct rr_schk),
 306         _SI( .si_datalen = ) sizeof(struct rr_si),
 307         _SI( .q_datalen = ) sizeof(struct rr_queue) - sizeof(struct dn_queue),
 308
 309         _SI( .enqueue = ) rr_enqueue,
 310         _SI( .dequeue = ) rr_dequeue,
 311
 312         _SI( .config = ) rr_config,
 313         _SI( .destroy = ) NULL,
 314         _SI( .new_sched = ) rr_new_sched,
 315         _SI( .free_sched = ) rr_free_sched,
 316         _SI( .new_fsk = ) rr_new_fsk,
 317         _SI( .free_fsk = ) NULL,
 318         _SI( .new_queue = ) rr_new_queue,
 319         _SI( .free_queue = ) rr_free_queue,
 320 #ifdef NEW_AQM
 321         _SI( .getconfig = )  NULL,
 322 #endif
 323 };
 324
 325
 326 DECLARE_DNSCHED_MODULE(dn_rr, &rr_desc);