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 #ifdef _KERNEL 33 #include <sys/malloc.h> 34 #include <sys/socket.h> 35 #include <sys/socketvar.h> 36 #include <sys/kernel.h> 37 #include <sys/lock.h> 38 #include <sys/mbuf.h> 39 #include <sys/module.h> 40 #include <sys/rwlock.h> 41 #include <net/if.h> /* IFNAMSIZ */ 42 #include <netinet/in.h> 43 #include <netinet/ip_var.h> /* ipfw_rule_ref */ 44 #include <netinet/ip_fw.h> /* flow_id */ 45 #include <netinet/ip_dummynet.h> 46 #include <netpfil/ipfw/ip_fw_private.h> 47 #include <netpfil/ipfw/dn_heap.h> 48 #include <netpfil/ipfw/ip_dn_private.h> 49 #ifdef NEW_AQM 50 #include <netpfil/ipfw/dn_aqm.h> 51 #endif 52 #include <netpfil/ipfw/dn_sched.h> 53 #else 54 #include <dn_test.h> 55 #endif 56 57 #define DN_SCHED_PRIO 5 //XXX 58 59 #if !defined(_KERNEL) || !defined(__linux__) 60 #define test_bit(ix, pData) ((*pData) & (1<<(ix))) 61 #define __set_bit(ix, pData) (*pData) |= (1<<(ix)) 62 #define __clear_bit(ix, pData) (*pData) &= ~(1<<(ix)) 63 #endif 64 65 #ifdef __MIPSEL__ 66 #define __clear_bit(ix, pData) (*pData) &= ~(1<<(ix)) 67 #endif 68 69 /* Size of the array of queues pointers. */ 70 #define BITMAP_T unsigned long 71 #define MAXPRIO (sizeof(BITMAP_T) * 8) 72 73 /* 74 * The scheduler instance contains an array of pointers to queues, 75 * one for each priority, and a bitmap listing backlogged queues. 76 */ 77 struct prio_si { 78 BITMAP_T bitmap; /* array bitmap */ 79 struct dn_queue *q_array[MAXPRIO]; /* Array of queues pointers */ 80 }; 81 82 /* 83 * If a queue with the same priority is already backlogged, use 84 * that one instead of the queue passed as argument. 85 */ 86 static int 87 prio_enqueue(struct dn_sch_inst *_si, struct dn_queue *q, struct mbuf *m) 88 { 89 struct prio_si *si = (struct prio_si *)(_si + 1); 90 int prio = q->fs->fs.par[0]; 91 92 if (test_bit(prio, &si->bitmap) == 0) { 93 /* No queue with this priority, insert */ 94 __set_bit(prio, &si->bitmap); 95 si->q_array[prio] = q; 96 } else { /* use the existing queue */ 97 q = si->q_array[prio]; 98 } 99 if (dn_enqueue(q, m, 0)) 100 return 1; 101 return 0; 102 } 103 104 /* 105 * Packets are dequeued only from the highest priority queue. 106 * The function ffs() return the lowest bit in the bitmap that rapresent 107 * the array index (-1) which contains the pointer to the highest priority 108 * queue. 109 * After the dequeue, if this queue become empty, it is index is removed 110 * from the bitmap. 111 * Scheduler is idle if the bitmap is empty 112 * 113 * NOTE: highest priority is 0, lowest is sched->max_prio_q 114 */ 115 static struct mbuf * 116 prio_dequeue(struct dn_sch_inst *_si) 117 { 118 struct prio_si *si = (struct prio_si *)(_si + 1); 119 struct mbuf *m; 120 struct dn_queue *q; 121 int prio; 122 123 if (si->bitmap == 0) /* scheduler idle */ 124 return NULL; 125 126 prio = ffs(si->bitmap) - 1; 127 128 /* Take the highest priority queue in the scheduler */ 129 q = si->q_array[prio]; 130 // assert(q) 131 132 m = dn_dequeue(q); 133 if (q->mq.head == NULL) { 134 /* Queue is now empty, remove from scheduler 135 * and mark it 136 */ 137 si->q_array[prio] = NULL; 138 __clear_bit(prio, &si->bitmap); 139 } 140 return m; 141 } 142 143 static int 144 prio_new_sched(struct dn_sch_inst *_si) 145 { 146 struct prio_si *si = (struct prio_si *)(_si + 1); 147 148 bzero(si->q_array, sizeof(si->q_array)); 149 si->bitmap = 0; 150 151 return 0; 152 } 153 154 static int 155 prio_new_fsk(struct dn_fsk *fs) 156 { 157 /* Check if the prioritiy is between 0 and MAXPRIO-1 */ 158 ipdn_bound_var(&fs->fs.par[0], 0, 0, MAXPRIO - 1, "PRIO priority"); 159 return 0; 160 } 161 162 static int 163 prio_new_queue(struct dn_queue *q) 164 { 165 struct prio_si *si = (struct prio_si *)(q->_si + 1); 166 int prio = q->fs->fs.par[0]; 167 struct dn_queue *oldq; 168 169 q->ni.oid.subtype = DN_SCHED_PRIO; 170 171 if (q->mq.head == NULL) 172 return 0; 173 174 /* Queue already full, must insert in the scheduler or append 175 * mbufs to existing queue. This partly duplicates prio_enqueue 176 */ 177 if (test_bit(prio, &si->bitmap) == 0) { 178 /* No queue with this priority, insert */ 179 __set_bit(prio, &si->bitmap); 180 si->q_array[prio] = q; 181 } else if ( (oldq = si->q_array[prio]) != q) { 182 /* must append to the existing queue. 183 * can simply append q->mq.head to q2->... 184 * and add the counters to those of q2 185 */ 186 oldq->mq.tail->m_nextpkt = q->mq.head; 187 oldq->mq.tail = q->mq.tail; 188 oldq->ni.length += q->ni.length; 189 q->ni.length = 0; 190 oldq->ni.len_bytes += q->ni.len_bytes; 191 q->ni.len_bytes = 0; 192 q->mq.tail = q->mq.head = NULL; 193 } 194 return 0; 195 } 196 197 static int 198 prio_free_queue(struct dn_queue *q) 199 { 200 int prio = q->fs->fs.par[0]; 201 struct prio_si *si = (struct prio_si *)(q->_si + 1); 202 203 if (si->q_array[prio] == q) { 204 si->q_array[prio] = NULL; 205 __clear_bit(prio, &si->bitmap); 206 } 207 return 0; 208 } 209 210 static struct dn_alg prio_desc = { 211 _SI( .type = ) DN_SCHED_PRIO, 212 _SI( .name = ) "PRIO", 213 _SI( .flags = ) DN_MULTIQUEUE, 214 215 /* we need extra space in the si and the queue */ 216 _SI( .schk_datalen = ) 0, 217 _SI( .si_datalen = ) sizeof(struct prio_si), 218 _SI( .q_datalen = ) 0, 219 220 _SI( .enqueue = ) prio_enqueue, 221 _SI( .dequeue = ) prio_dequeue, 222 223 _SI( .config = ) NULL, 224 _SI( .destroy = ) NULL, 225 _SI( .new_sched = ) prio_new_sched, 226 _SI( .free_sched = ) NULL, 227 228 _SI( .new_fsk = ) prio_new_fsk, 229 _SI( .free_fsk = ) NULL, 230 231 _SI( .new_queue = ) prio_new_queue, 232 _SI( .free_queue = ) prio_free_queue, 233 #ifdef NEW_AQM 234 _SI( .getconfig = ) NULL, 235 #endif 236 }; 237 238 DECLARE_DNSCHED_MODULE(dn_prio, &prio_desc); 239