1fe267a55SPedro F. Giffuni /*-
24d846d26SWarner Losh * SPDX-License-Identifier: BSD-2-Clause
3fe267a55SPedro F. Giffuni *
43b3a8eb9SGleb Smirnoff * Copyright (c) 2010 Riccardo Panicucci, Universita` di Pisa
53b3a8eb9SGleb Smirnoff * All rights reserved
63b3a8eb9SGleb Smirnoff *
73b3a8eb9SGleb Smirnoff * Redistribution and use in source and binary forms, with or without
83b3a8eb9SGleb Smirnoff * modification, are permitted provided that the following conditions
93b3a8eb9SGleb Smirnoff * are met:
103b3a8eb9SGleb Smirnoff * 1. Redistributions of source code must retain the above copyright
113b3a8eb9SGleb Smirnoff * notice, this list of conditions and the following disclaimer.
123b3a8eb9SGleb Smirnoff * 2. Redistributions in binary form must reproduce the above copyright
133b3a8eb9SGleb Smirnoff * notice, this list of conditions and the following disclaimer in the
143b3a8eb9SGleb Smirnoff * documentation and/or other materials provided with the distribution.
153b3a8eb9SGleb Smirnoff *
163b3a8eb9SGleb Smirnoff * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
173b3a8eb9SGleb Smirnoff * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
183b3a8eb9SGleb Smirnoff * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
193b3a8eb9SGleb Smirnoff * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
203b3a8eb9SGleb Smirnoff * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
213b3a8eb9SGleb Smirnoff * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
223b3a8eb9SGleb Smirnoff * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
233b3a8eb9SGleb Smirnoff * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
243b3a8eb9SGleb Smirnoff * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
253b3a8eb9SGleb Smirnoff * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
263b3a8eb9SGleb Smirnoff * SUCH DAMAGE.
273b3a8eb9SGleb Smirnoff */
283b3a8eb9SGleb Smirnoff
293b3a8eb9SGleb Smirnoff /*
303b3a8eb9SGleb Smirnoff */
313b3a8eb9SGleb Smirnoff #ifdef _KERNEL
323b3a8eb9SGleb Smirnoff #include <sys/malloc.h>
333b3a8eb9SGleb Smirnoff #include <sys/socket.h>
343b3a8eb9SGleb Smirnoff #include <sys/socketvar.h>
353b3a8eb9SGleb Smirnoff #include <sys/kernel.h>
364001fcbeSDon Lewis #include <sys/lock.h>
373b3a8eb9SGleb Smirnoff #include <sys/mbuf.h>
383b3a8eb9SGleb Smirnoff #include <sys/module.h>
394001fcbeSDon Lewis #include <sys/rwlock.h>
403b3a8eb9SGleb Smirnoff #include <net/if.h> /* IFNAMSIZ */
413b3a8eb9SGleb Smirnoff #include <netinet/in.h>
423b3a8eb9SGleb Smirnoff #include <netinet/ip_var.h> /* ipfw_rule_ref */
433b3a8eb9SGleb Smirnoff #include <netinet/ip_fw.h> /* flow_id */
443b3a8eb9SGleb Smirnoff #include <netinet/ip_dummynet.h>
454001fcbeSDon Lewis #include <netpfil/ipfw/ip_fw_private.h>
463b3a8eb9SGleb Smirnoff #include <netpfil/ipfw/dn_heap.h>
473b3a8eb9SGleb Smirnoff #include <netpfil/ipfw/ip_dn_private.h>
4891336b40SDon Lewis #ifdef NEW_AQM
4991336b40SDon Lewis #include <netpfil/ipfw/dn_aqm.h>
5091336b40SDon Lewis #endif
513b3a8eb9SGleb Smirnoff #include <netpfil/ipfw/dn_sched.h>
523b3a8eb9SGleb Smirnoff #else
533b3a8eb9SGleb Smirnoff #include <dn_test.h>
543b3a8eb9SGleb Smirnoff #endif
553b3a8eb9SGleb Smirnoff
563b3a8eb9SGleb Smirnoff #define DN_SCHED_PRIO 5 //XXX
573b3a8eb9SGleb Smirnoff
583b3a8eb9SGleb Smirnoff #if !defined(_KERNEL) || !defined(__linux__)
593b3a8eb9SGleb Smirnoff #define test_bit(ix, pData) ((*pData) & (1<<(ix)))
603b3a8eb9SGleb Smirnoff #define __set_bit(ix, pData) (*pData) |= (1<<(ix))
613b3a8eb9SGleb Smirnoff #define __clear_bit(ix, pData) (*pData) &= ~(1<<(ix))
623b3a8eb9SGleb Smirnoff #endif
633b3a8eb9SGleb Smirnoff
643b3a8eb9SGleb Smirnoff #ifdef __MIPSEL__
653b3a8eb9SGleb Smirnoff #define __clear_bit(ix, pData) (*pData) &= ~(1<<(ix))
663b3a8eb9SGleb Smirnoff #endif
673b3a8eb9SGleb Smirnoff
683b3a8eb9SGleb Smirnoff /* Size of the array of queues pointers. */
693b3a8eb9SGleb Smirnoff #define BITMAP_T unsigned long
703b3a8eb9SGleb Smirnoff #define MAXPRIO (sizeof(BITMAP_T) * 8)
713b3a8eb9SGleb Smirnoff
723b3a8eb9SGleb Smirnoff /*
733b3a8eb9SGleb Smirnoff * The scheduler instance contains an array of pointers to queues,
743b3a8eb9SGleb Smirnoff * one for each priority, and a bitmap listing backlogged queues.
753b3a8eb9SGleb Smirnoff */
763b3a8eb9SGleb Smirnoff struct prio_si {
773b3a8eb9SGleb Smirnoff BITMAP_T bitmap; /* array bitmap */
783b3a8eb9SGleb Smirnoff struct dn_queue *q_array[MAXPRIO]; /* Array of queues pointers */
793b3a8eb9SGleb Smirnoff };
803b3a8eb9SGleb Smirnoff
813b3a8eb9SGleb Smirnoff /*
823b3a8eb9SGleb Smirnoff * If a queue with the same priority is already backlogged, use
833b3a8eb9SGleb Smirnoff * that one instead of the queue passed as argument.
843b3a8eb9SGleb Smirnoff */
853b3a8eb9SGleb Smirnoff static int
prio_enqueue(struct dn_sch_inst * _si,struct dn_queue * q,struct mbuf * m)863b3a8eb9SGleb Smirnoff prio_enqueue(struct dn_sch_inst *_si, struct dn_queue *q, struct mbuf *m)
873b3a8eb9SGleb Smirnoff {
883b3a8eb9SGleb Smirnoff struct prio_si *si = (struct prio_si *)(_si + 1);
893b3a8eb9SGleb Smirnoff int prio = q->fs->fs.par[0];
903b3a8eb9SGleb Smirnoff
913b3a8eb9SGleb Smirnoff if (test_bit(prio, &si->bitmap) == 0) {
923b3a8eb9SGleb Smirnoff /* No queue with this priority, insert */
933b3a8eb9SGleb Smirnoff __set_bit(prio, &si->bitmap);
943b3a8eb9SGleb Smirnoff si->q_array[prio] = q;
953b3a8eb9SGleb Smirnoff } else { /* use the existing queue */
963b3a8eb9SGleb Smirnoff q = si->q_array[prio];
973b3a8eb9SGleb Smirnoff }
983b3a8eb9SGleb Smirnoff if (dn_enqueue(q, m, 0))
993b3a8eb9SGleb Smirnoff return 1;
1003b3a8eb9SGleb Smirnoff return 0;
1013b3a8eb9SGleb Smirnoff }
1023b3a8eb9SGleb Smirnoff
1033b3a8eb9SGleb Smirnoff /*
1043b3a8eb9SGleb Smirnoff * Packets are dequeued only from the highest priority queue.
1053b3a8eb9SGleb Smirnoff * The function ffs() return the lowest bit in the bitmap that rapresent
1063b3a8eb9SGleb Smirnoff * the array index (-1) which contains the pointer to the highest priority
1073b3a8eb9SGleb Smirnoff * queue.
1083b3a8eb9SGleb Smirnoff * After the dequeue, if this queue become empty, it is index is removed
1093b3a8eb9SGleb Smirnoff * from the bitmap.
1103b3a8eb9SGleb Smirnoff * Scheduler is idle if the bitmap is empty
1113b3a8eb9SGleb Smirnoff *
1123b3a8eb9SGleb Smirnoff * NOTE: highest priority is 0, lowest is sched->max_prio_q
1133b3a8eb9SGleb Smirnoff */
1143b3a8eb9SGleb Smirnoff static struct mbuf *
prio_dequeue(struct dn_sch_inst * _si)1153b3a8eb9SGleb Smirnoff prio_dequeue(struct dn_sch_inst *_si)
1163b3a8eb9SGleb Smirnoff {
1173b3a8eb9SGleb Smirnoff struct prio_si *si = (struct prio_si *)(_si + 1);
1183b3a8eb9SGleb Smirnoff struct mbuf *m;
1193b3a8eb9SGleb Smirnoff struct dn_queue *q;
1203b3a8eb9SGleb Smirnoff int prio;
1213b3a8eb9SGleb Smirnoff
1223b3a8eb9SGleb Smirnoff if (si->bitmap == 0) /* scheduler idle */
1233b3a8eb9SGleb Smirnoff return NULL;
1243b3a8eb9SGleb Smirnoff
1253b3a8eb9SGleb Smirnoff prio = ffs(si->bitmap) - 1;
1263b3a8eb9SGleb Smirnoff
1273b3a8eb9SGleb Smirnoff /* Take the highest priority queue in the scheduler */
1283b3a8eb9SGleb Smirnoff q = si->q_array[prio];
1293b3a8eb9SGleb Smirnoff // assert(q)
1303b3a8eb9SGleb Smirnoff
1313b3a8eb9SGleb Smirnoff m = dn_dequeue(q);
1323b3a8eb9SGleb Smirnoff if (q->mq.head == NULL) {
1333b3a8eb9SGleb Smirnoff /* Queue is now empty, remove from scheduler
1343b3a8eb9SGleb Smirnoff * and mark it
1353b3a8eb9SGleb Smirnoff */
1363b3a8eb9SGleb Smirnoff si->q_array[prio] = NULL;
1373b3a8eb9SGleb Smirnoff __clear_bit(prio, &si->bitmap);
1383b3a8eb9SGleb Smirnoff }
1393b3a8eb9SGleb Smirnoff return m;
1403b3a8eb9SGleb Smirnoff }
1413b3a8eb9SGleb Smirnoff
1423b3a8eb9SGleb Smirnoff static int
prio_new_sched(struct dn_sch_inst * _si)1433b3a8eb9SGleb Smirnoff prio_new_sched(struct dn_sch_inst *_si)
1443b3a8eb9SGleb Smirnoff {
1453b3a8eb9SGleb Smirnoff struct prio_si *si = (struct prio_si *)(_si + 1);
1463b3a8eb9SGleb Smirnoff
1473b3a8eb9SGleb Smirnoff bzero(si->q_array, sizeof(si->q_array));
1483b3a8eb9SGleb Smirnoff si->bitmap = 0;
1493b3a8eb9SGleb Smirnoff
1503b3a8eb9SGleb Smirnoff return 0;
1513b3a8eb9SGleb Smirnoff }
1523b3a8eb9SGleb Smirnoff
1533b3a8eb9SGleb Smirnoff static int
prio_new_fsk(struct dn_fsk * fs)1543b3a8eb9SGleb Smirnoff prio_new_fsk(struct dn_fsk *fs)
1553b3a8eb9SGleb Smirnoff {
1563b3a8eb9SGleb Smirnoff /* Check if the prioritiy is between 0 and MAXPRIO-1 */
1573b3a8eb9SGleb Smirnoff ipdn_bound_var(&fs->fs.par[0], 0, 0, MAXPRIO - 1, "PRIO priority");
1583b3a8eb9SGleb Smirnoff return 0;
1593b3a8eb9SGleb Smirnoff }
1603b3a8eb9SGleb Smirnoff
1613b3a8eb9SGleb Smirnoff static int
prio_new_queue(struct dn_queue * q)1623b3a8eb9SGleb Smirnoff prio_new_queue(struct dn_queue *q)
1633b3a8eb9SGleb Smirnoff {
1643b3a8eb9SGleb Smirnoff struct prio_si *si = (struct prio_si *)(q->_si + 1);
1653b3a8eb9SGleb Smirnoff int prio = q->fs->fs.par[0];
1663b3a8eb9SGleb Smirnoff struct dn_queue *oldq;
1673b3a8eb9SGleb Smirnoff
1683b3a8eb9SGleb Smirnoff q->ni.oid.subtype = DN_SCHED_PRIO;
1693b3a8eb9SGleb Smirnoff
1703b3a8eb9SGleb Smirnoff if (q->mq.head == NULL)
1713b3a8eb9SGleb Smirnoff return 0;
1723b3a8eb9SGleb Smirnoff
1733b3a8eb9SGleb Smirnoff /* Queue already full, must insert in the scheduler or append
1743b3a8eb9SGleb Smirnoff * mbufs to existing queue. This partly duplicates prio_enqueue
1753b3a8eb9SGleb Smirnoff */
1763b3a8eb9SGleb Smirnoff if (test_bit(prio, &si->bitmap) == 0) {
1773b3a8eb9SGleb Smirnoff /* No queue with this priority, insert */
1783b3a8eb9SGleb Smirnoff __set_bit(prio, &si->bitmap);
1793b3a8eb9SGleb Smirnoff si->q_array[prio] = q;
1803b3a8eb9SGleb Smirnoff } else if ( (oldq = si->q_array[prio]) != q) {
1813b3a8eb9SGleb Smirnoff /* must append to the existing queue.
1823b3a8eb9SGleb Smirnoff * can simply append q->mq.head to q2->...
1833b3a8eb9SGleb Smirnoff * and add the counters to those of q2
1843b3a8eb9SGleb Smirnoff */
1853b3a8eb9SGleb Smirnoff oldq->mq.tail->m_nextpkt = q->mq.head;
1863b3a8eb9SGleb Smirnoff oldq->mq.tail = q->mq.tail;
1873b3a8eb9SGleb Smirnoff oldq->ni.length += q->ni.length;
1883b3a8eb9SGleb Smirnoff q->ni.length = 0;
1893b3a8eb9SGleb Smirnoff oldq->ni.len_bytes += q->ni.len_bytes;
1903b3a8eb9SGleb Smirnoff q->ni.len_bytes = 0;
1913b3a8eb9SGleb Smirnoff q->mq.tail = q->mq.head = NULL;
1923b3a8eb9SGleb Smirnoff }
1933b3a8eb9SGleb Smirnoff return 0;
1943b3a8eb9SGleb Smirnoff }
1953b3a8eb9SGleb Smirnoff
1963b3a8eb9SGleb Smirnoff static int
prio_free_queue(struct dn_queue * q)1973b3a8eb9SGleb Smirnoff prio_free_queue(struct dn_queue *q)
1983b3a8eb9SGleb Smirnoff {
1993b3a8eb9SGleb Smirnoff int prio = q->fs->fs.par[0];
2003b3a8eb9SGleb Smirnoff struct prio_si *si = (struct prio_si *)(q->_si + 1);
2013b3a8eb9SGleb Smirnoff
2023b3a8eb9SGleb Smirnoff if (si->q_array[prio] == q) {
2033b3a8eb9SGleb Smirnoff si->q_array[prio] = NULL;
2043b3a8eb9SGleb Smirnoff __clear_bit(prio, &si->bitmap);
2053b3a8eb9SGleb Smirnoff }
2063b3a8eb9SGleb Smirnoff return 0;
2073b3a8eb9SGleb Smirnoff }
2083b3a8eb9SGleb Smirnoff
2093b3a8eb9SGleb Smirnoff static struct dn_alg prio_desc = {
2103b3a8eb9SGleb Smirnoff _SI( .type = ) DN_SCHED_PRIO,
2113b3a8eb9SGleb Smirnoff _SI( .name = ) "PRIO",
2123b3a8eb9SGleb Smirnoff _SI( .flags = ) DN_MULTIQUEUE,
2133b3a8eb9SGleb Smirnoff
2143b3a8eb9SGleb Smirnoff /* we need extra space in the si and the queue */
2153b3a8eb9SGleb Smirnoff _SI( .schk_datalen = ) 0,
2163b3a8eb9SGleb Smirnoff _SI( .si_datalen = ) sizeof(struct prio_si),
2173b3a8eb9SGleb Smirnoff _SI( .q_datalen = ) 0,
2183b3a8eb9SGleb Smirnoff
2193b3a8eb9SGleb Smirnoff _SI( .enqueue = ) prio_enqueue,
2203b3a8eb9SGleb Smirnoff _SI( .dequeue = ) prio_dequeue,
2213b3a8eb9SGleb Smirnoff
2223b3a8eb9SGleb Smirnoff _SI( .config = ) NULL,
2233b3a8eb9SGleb Smirnoff _SI( .destroy = ) NULL,
2243b3a8eb9SGleb Smirnoff _SI( .new_sched = ) prio_new_sched,
2253b3a8eb9SGleb Smirnoff _SI( .free_sched = ) NULL,
2263b3a8eb9SGleb Smirnoff
2273b3a8eb9SGleb Smirnoff _SI( .new_fsk = ) prio_new_fsk,
2283b3a8eb9SGleb Smirnoff _SI( .free_fsk = ) NULL,
2293b3a8eb9SGleb Smirnoff
2303b3a8eb9SGleb Smirnoff _SI( .new_queue = ) prio_new_queue,
2313b3a8eb9SGleb Smirnoff _SI( .free_queue = ) prio_free_queue,
23291336b40SDon Lewis #ifdef NEW_AQM
23391336b40SDon Lewis _SI( .getconfig = ) NULL,
23491336b40SDon Lewis #endif
2353b3a8eb9SGleb Smirnoff };
2363b3a8eb9SGleb Smirnoff
2373b3a8eb9SGleb Smirnoff DECLARE_DNSCHED_MODULE(dn_prio, &prio_desc);
238