No empty .Rs/.Re
[netbsd-mini2440.git] / sys / altq / altq_wfq.c
blob4a732b59176b801bf5c872288db638e5f8d4f322
1 /* $NetBSD: altq_wfq.c,v 1.18 2007/03/04 05:59:03 christos Exp $ */
2 /* $KAME: altq_wfq.c,v 1.14 2005/04/13 03:44:25 suz Exp $ */
4 /*
5 * Copyright (C) 1997-2002
6 * Sony Computer Science Laboratories Inc. All rights reserved.
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
17 * THIS SOFTWARE IS PROVIDED BY SONY CSL AND CONTRIBUTORS ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL SONY CSL OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27 * SUCH DAMAGE.
30 * March 27, 1997. Written by Hiroshi Kyusojin of Keio University
31 * (kyu@mt.cs.keio.ac.jp).
34 #include <sys/cdefs.h>
35 __KERNEL_RCSID(0, "$NetBSD: altq_wfq.c,v 1.18 2007/03/04 05:59:03 christos Exp $");
37 #ifdef _KERNEL_OPT
38 #include "opt_altq.h"
39 #include "opt_inet.h"
40 #endif
42 #ifdef ALTQ_WFQ
44 #include <sys/param.h>
45 #include <sys/malloc.h>
46 #include <sys/mbuf.h>
47 #include <sys/uio.h>
48 #include <sys/socket.h>
49 #include <sys/systm.h>
50 #include <sys/proc.h>
51 #include <sys/errno.h>
52 #include <sys/time.h>
53 #include <sys/kernel.h>
54 #include <sys/kauth.h>
56 #include <net/if.h>
57 #include <net/if_types.h>
58 #include <netinet/in.h>
60 #include <altq/altq.h>
61 #include <altq/altq_conf.h>
62 #include <altq/altq_wfq.h>
64 #ifdef ALTQ3_COMPAT
66 #define WFQ_DEBUG
69 static int wfq_setenable(struct wfq_interface *, int);
70 static int wfq_ifattach(struct wfq_interface *);
71 static int wfq_ifdetach(struct wfq_interface *);
72 static int wfq_ifenqueue(struct ifaltq *, struct mbuf *,
73 struct altq_pktattr *);
74 static u_long wfq_hash(struct flowinfo *, int);
75 static inline u_long wfq_hashbydstaddr(struct flowinfo *, int);
76 static inline u_long wfq_hashbysrcaddr(struct flowinfo *, int);
77 static inline u_long wfq_hashbysrcport(struct flowinfo *, int);
78 static wfq *wfq_maxqueue(wfq_state_t *);
79 static struct mbuf *wfq_ifdequeue(struct ifaltq *, int);
80 static int wfq_getqid(struct wfq_getqid *);
81 static int wfq_setweight(struct wfq_setweight *);
82 static int wfq_getstats(struct wfq_getstats *);
83 static int wfq_config(struct wfq_conf *);
84 static int wfq_request(struct ifaltq *, int, void *);
85 static int wfq_flush(struct ifaltq *);
86 static void *wfq_classify(void *, struct mbuf *, int);
88 /* global value : pointer to wfq queue list */
89 static wfq_state_t *wfq_list = NULL;
91 static int
92 wfq_setenable(struct wfq_interface *ifacep, int flag)
94 wfq_state_t *wfqp;
95 int error = 0;
97 if ((wfqp = altq_lookup(ifacep->wfq_ifacename, ALTQT_WFQ)) == NULL)
98 return (EBADF);
100 switch(flag){
101 case ENABLE:
102 error = altq_enable(wfqp->ifq);
103 break;
104 case DISABLE:
105 error = altq_disable(wfqp->ifq);
106 break;
108 return error;
112 static int
113 wfq_ifattach(struct wfq_interface *ifacep)
115 int error = 0, i;
116 struct ifnet *ifp;
117 wfq_state_t *new_wfqp;
118 wfq *queue;
120 if ((ifp = ifunit(ifacep->wfq_ifacename)) == NULL) {
121 #ifdef WFQ_DEBUG
122 printf("wfq_ifattach()...no ifp found\n");
123 #endif
124 return (ENXIO);
127 if (!ALTQ_IS_READY(&ifp->if_snd)) {
128 #ifdef WFQ_DEBUG
129 printf("wfq_ifattach()...altq is not ready\n");
130 #endif
131 return (ENXIO);
134 /* allocate and initialize wfq_state_t */
135 new_wfqp = malloc(sizeof(wfq_state_t), M_DEVBUF, M_WAITOK|M_ZERO);
136 if (new_wfqp == NULL)
137 return (ENOMEM);
139 queue = malloc(sizeof(wfq) * DEFAULT_QSIZE, M_DEVBUF, M_WAITOK|M_ZERO);
140 if (queue == NULL) {
141 free(new_wfqp, M_DEVBUF);
142 return (ENOMEM);
145 /* keep the ifq */
146 new_wfqp->ifq = &ifp->if_snd;
147 new_wfqp->nums = DEFAULT_QSIZE;
148 new_wfqp->hwm = HWM;
149 new_wfqp->bytes = 0;
150 new_wfqp->rrp = NULL;
151 new_wfqp->queue = queue;
152 new_wfqp->hash_func = wfq_hashbydstaddr;
153 new_wfqp->fbmask = FIMB4_DADDR;
155 for (i = 0; i < new_wfqp->nums; i++, queue++) {
156 queue->next = queue->prev = NULL;
157 queue->head = queue->tail = NULL;
158 queue->bytes = queue->quota = 0;
159 queue->weight = 100;
163 * set WFQ to this ifnet structure.
165 if ((error = altq_attach(&ifp->if_snd, ALTQT_WFQ, new_wfqp,
166 wfq_ifenqueue, wfq_ifdequeue, wfq_request,
167 new_wfqp, wfq_classify)) != 0) {
168 free(queue, M_DEVBUF);
169 free(new_wfqp, M_DEVBUF);
170 return (error);
173 new_wfqp->next = wfq_list;
174 wfq_list = new_wfqp;
176 return (error);
180 static int
181 wfq_ifdetach(struct wfq_interface *ifacep)
183 int error = 0;
184 wfq_state_t *wfqp;
186 if ((wfqp = altq_lookup(ifacep->wfq_ifacename, ALTQT_WFQ)) == NULL)
187 return (EBADF);
189 /* free queued mbuf */
190 wfq_flush(wfqp->ifq);
192 /* remove WFQ from the ifnet structure. */
193 (void)altq_disable(wfqp->ifq);
194 (void)altq_detach(wfqp->ifq);
196 /* remove from the wfqstate list */
197 if (wfq_list == wfqp)
198 wfq_list = wfqp->next;
199 else {
200 wfq_state_t *wp = wfq_list;
201 do {
202 if (wp->next == wfqp) {
203 wp->next = wfqp->next;
204 break;
206 } while ((wp = wp->next) != NULL);
209 /* deallocate wfq_state_t */
210 free(wfqp->queue, M_DEVBUF);
211 free(wfqp, M_DEVBUF);
212 return (error);
215 static int
216 wfq_request(struct ifaltq *ifq, int req, void *arg)
218 wfq_state_t *wfqp = (wfq_state_t *)ifq->altq_disc;
220 switch (req) {
221 case ALTRQ_PURGE:
222 wfq_flush(wfqp->ifq);
223 break;
225 return (0);
229 static int
230 wfq_flush(struct ifaltq *ifq)
232 struct mbuf *mp;
234 while ((mp = wfq_ifdequeue(ifq, ALTDQ_REMOVE)) != NULL)
235 m_freem(mp);
236 if (ALTQ_IS_ENABLED(ifq))
237 ifq->ifq_len = 0;
238 return 0;
241 static void *
242 wfq_classify(void *clfier, struct mbuf *m, int af)
244 wfq_state_t *wfqp = (wfq_state_t *)clfier;
245 struct flowinfo flow;
247 altq_extractflow(m, af, &flow, wfqp->fbmask);
248 return (&wfqp->queue[(*wfqp->hash_func)(&flow, wfqp->nums)]);
251 static int
252 wfq_ifenqueue(struct ifaltq *ifq, struct mbuf *mp, struct altq_pktattr *pktattr)
254 wfq_state_t *wfqp;
255 wfq *queue;
256 int byte, error = 0;
258 wfqp = (wfq_state_t *)ifq->altq_disc;
259 mp->m_nextpkt = NULL;
261 /* grab a queue selected by classifier */
262 if (pktattr == NULL || (queue = pktattr->pattr_class) == NULL)
263 queue = &wfqp->queue[0];
265 if (queue->tail == NULL)
266 queue->head = mp;
267 else
268 queue->tail->m_nextpkt = mp;
269 queue->tail = mp;
270 byte = mp->m_pkthdr.len;
271 queue->bytes += byte;
272 wfqp->bytes += byte;
273 ifq->ifq_len++;
275 if (queue->next == NULL) {
276 /* this queue gets active. add the queue to the active list */
277 if (wfqp->rrp == NULL){
278 /* no queue in the active list */
279 queue->next = queue->prev = queue;
280 wfqp->rrp = queue;
281 WFQ_ADDQUOTA(queue);
282 } else {
283 /* insert the queue at the tail of the active list */
284 queue->prev = wfqp->rrp->prev;
285 wfqp->rrp->prev->next = queue;
286 wfqp->rrp->prev = queue;
287 queue->next = wfqp->rrp;
288 queue->quota = 0;
292 /* check overflow. if the total size exceeds the high water mark,
293 drop packets from the longest queue. */
294 while (wfqp->bytes > wfqp->hwm) {
295 wfq *drop_queue = wfq_maxqueue(wfqp);
297 /* drop the packet at the head. */
298 mp = drop_queue->head;
299 if ((drop_queue->head = mp->m_nextpkt) == NULL)
300 drop_queue->tail = NULL;
301 mp->m_nextpkt = NULL;
302 byte = mp->m_pkthdr.len;
303 drop_queue->bytes -= byte;
304 PKTCNTR_ADD(&drop_queue->drop_cnt, byte);
305 wfqp->bytes -= byte;
306 m_freem(mp);
307 ifq->ifq_len--;
308 if(drop_queue == queue)
309 /* the queue for this flow is selected to drop */
310 error = ENOBUFS;
312 return error;
315 static u_long
316 wfq_hash(struct flowinfo *flow, int n)
318 u_long val = 0;
320 if (flow != NULL) {
321 if (flow->fi_family == AF_INET) {
322 struct flowinfo_in *fp = (struct flowinfo_in *)flow;
323 u_long val2;
325 val = fp->fi_dst.s_addr ^ fp->fi_src.s_addr;
326 val = val ^ (val >> 8) ^ (val >> 16) ^ (val >> 24);
327 val2 = fp->fi_dport ^ fp->fi_sport ^ fp->fi_proto;
328 val2 = val2 ^ (val2 >> 8);
329 val = val ^ val2;
331 #ifdef INET6
332 else if (flow->fi_family == AF_INET6) {
333 struct flowinfo_in6 *fp6 = (struct flowinfo_in6 *)flow;
335 val = ntohl(fp6->fi6_flowlabel);
337 #endif
340 return (val % n);
343 static inline u_long
344 wfq_hashbydstaddr(struct flowinfo *flow, int n)
346 u_long val = 0;
348 if (flow != NULL) {
349 if (flow->fi_family == AF_INET) {
350 struct flowinfo_in *fp = (struct flowinfo_in *)flow;
352 val = fp->fi_dst.s_addr;
353 val = val ^ (val >> 8) ^ (val >> 16) ^ (val >> 24);
355 #ifdef INET6
356 else if (flow->fi_family == AF_INET6) {
357 struct flowinfo_in6 *fp6 = (struct flowinfo_in6 *)flow;
359 val = ntohl(fp6->fi6_flowlabel);
361 #endif
364 return (val % n);
367 static inline u_long
368 wfq_hashbysrcaddr(struct flowinfo *flow, int n)
370 u_long val = 0;
372 if (flow != NULL) {
373 if (flow->fi_family == AF_INET) {
374 struct flowinfo_in *fp = (struct flowinfo_in *)flow;
376 val = fp->fi_src.s_addr;
377 val = val ^ (val >> 8) ^ (val >> 16) ^ (val >> 24);
379 #ifdef INET6
380 else if (flow->fi_family == AF_INET6) {
381 struct flowinfo_in6 *fp6 = (struct flowinfo_in6 *)flow;
383 val = ntohl(fp6->fi6_flowlabel);
385 #endif
388 return (val % n);
391 static inline u_long
392 wfq_hashbysrcport(struct flowinfo *flow, int n)
394 u_long val = 0;
396 if (flow != NULL) {
397 if (flow->fi_family == AF_INET) {
398 struct flowinfo_in *fp = (struct flowinfo_in *)flow;
400 val = fp->fi_sport;
402 #ifdef INET6
403 else if (flow->fi_family == AF_INET6) {
404 struct flowinfo_in6 *fp6 = (struct flowinfo_in6 *)flow;
406 val = fp6->fi6_sport;
408 #endif
410 val = val ^ (val >> 8);
412 return (val % n);
415 static wfq *
416 wfq_maxqueue(wfq_state_t *wfqp)
418 int byte, max_byte = 0;
419 wfq *queue, *max_queue = NULL;
421 if((queue = wfqp->rrp) == NULL)
422 /* never happens */
423 return NULL;
425 if ((byte = queue->bytes * 100 / queue->weight) > max_byte) {
426 max_queue = queue;
427 max_byte = byte;
429 } while ((queue = queue->next) != wfqp->rrp);
431 return max_queue;
435 static struct mbuf *
436 wfq_ifdequeue(struct ifaltq *ifq, int op)
438 wfq_state_t *wfqp;
439 wfq *queue;
440 struct mbuf *mp;
441 int byte;
443 wfqp = (wfq_state_t *)ifq->altq_disc;
445 if ((wfqp->bytes == 0) || ((queue = wfqp->rrp) == NULL))
446 /* no packet in the queues */
447 return NULL;
449 while (1) {
450 if (queue->quota > 0) {
451 if (queue->bytes <= 0) {
452 /* this queue no longer has packet.
453 remove the queue from the active list. */
454 if (queue->next == queue){
455 /* no other active queue
456 -- this case never happens in
457 this algorithm. */
458 queue->next = queue->prev = NULL;
459 wfqp->rrp = NULL;
460 return NULL;
461 } else {
462 queue->prev->next = queue->next;
463 queue->next->prev = queue->prev;
464 /* the round-robin pointer points
465 to this queue, advance the rrp */
466 wfqp->rrp = queue->next;
467 queue->next = queue->prev = NULL;
468 queue = wfqp->rrp;
469 WFQ_ADDQUOTA(queue);
470 continue;
474 /* dequeue a packet from this queue */
475 mp = queue->head;
476 if (op == ALTDQ_REMOVE) {
477 if((queue->head = mp->m_nextpkt) == NULL)
478 queue->tail = NULL;
479 byte = mp->m_pkthdr.len;
480 mp->m_nextpkt = NULL;
481 queue->quota -= byte;
482 queue->bytes -= byte;
483 PKTCNTR_ADD(&queue->xmit_cnt, byte);
484 wfqp->bytes -= byte;
485 if (ALTQ_IS_ENABLED(ifq))
486 ifq->ifq_len--;
488 return mp;
490 /* if the queue gets empty by this dequeueing,
491 the queue will be removed from the active list
492 at the next round */
495 /* advance the round-robin pointer */
496 queue = wfqp->rrp = queue->next;
497 WFQ_ADDQUOTA(queue);
501 static int
502 wfq_getqid(struct wfq_getqid *gqidp)
504 wfq_state_t *wfqp;
506 if ((wfqp = altq_lookup(gqidp->iface.wfq_ifacename, ALTQT_WFQ))
507 == NULL)
508 return (EBADF);
510 gqidp->qid = (*wfqp->hash_func)(&gqidp->flow, wfqp->nums);
511 return 0;
514 static int
515 wfq_setweight(struct wfq_setweight *swp)
517 wfq_state_t *wfqp;
518 wfq *queue;
519 int old;
521 if (swp->weight < 0) {
522 printf("set weight in natural number\n");
523 return (EINVAL);
526 if ((wfqp = altq_lookup(swp->iface.wfq_ifacename, ALTQT_WFQ)) == NULL)
527 return (EBADF);
529 queue = &wfqp->queue[swp->qid];
530 old = queue->weight;
531 queue->weight = swp->weight;
532 swp->weight = old;
533 return 0;
537 static int
538 wfq_getstats(struct wfq_getstats *gsp)
540 wfq_state_t *wfqp;
541 wfq *queue;
542 queue_stats *stats;
544 if ((wfqp = altq_lookup(gsp->iface.wfq_ifacename, ALTQT_WFQ)) == NULL)
545 return (EBADF);
547 if (gsp->qid >= wfqp->nums)
548 return (EINVAL);
550 queue = &wfqp->queue[gsp->qid];
551 stats = &gsp->stats;
553 stats->bytes = queue->bytes;
554 stats->weight = queue->weight;
555 stats->xmit_cnt = queue->xmit_cnt;
556 stats->drop_cnt = queue->drop_cnt;
558 return 0;
562 static int
563 wfq_config(struct wfq_conf *cf)
565 wfq_state_t *wfqp;
566 wfq *queue;
567 int i, error = 0;
569 if ((wfqp = altq_lookup(cf->iface.wfq_ifacename, ALTQT_WFQ)) == NULL)
570 return (EBADF);
572 if(cf->nqueues <= 0 || MAX_QSIZE < cf->nqueues)
573 cf->nqueues = DEFAULT_QSIZE;
575 if (cf->nqueues != wfqp->nums) {
576 /* free queued mbuf */
577 wfq_flush(wfqp->ifq);
578 free(wfqp->queue, M_DEVBUF);
580 queue = malloc(sizeof(wfq) * cf->nqueues, M_DEVBUF,
581 M_WAITOK|M_ZERO);
582 if (queue == NULL)
583 return (ENOMEM);
585 wfqp->nums = cf->nqueues;
586 wfqp->bytes = 0;
587 wfqp->rrp = NULL;
588 wfqp->queue = queue;
589 for (i = 0; i < wfqp->nums; i++, queue++) {
590 queue->next = queue->prev = NULL;
591 queue->head = queue->tail = NULL;
592 queue->bytes = queue->quota = 0;
593 queue->weight = 100;
597 if (cf->qlimit != 0)
598 wfqp->hwm = cf->qlimit;
600 switch (cf->hash_policy) {
601 case WFQ_HASH_DSTADDR:
602 wfqp->hash_func = wfq_hashbydstaddr;
603 wfqp->fbmask = FIMB4_DADDR;
604 #ifdef INET6
605 wfqp->fbmask |= FIMB6_FLABEL; /* use flowlabel for ipv6 */
606 #endif
607 break;
608 case WFQ_HASH_SRCPORT:
609 wfqp->hash_func = wfq_hashbysrcport;
610 wfqp->fbmask = FIMB4_SPORT;
611 #ifdef INET6
612 wfqp->fbmask |= FIMB6_SPORT;
613 #endif
614 break;
615 case WFQ_HASH_FULL:
616 wfqp->hash_func = wfq_hash;
617 wfqp->fbmask = FIMB4_ALL;
618 #ifdef INET6
619 wfqp->fbmask |= FIMB6_FLABEL; /* use flowlabel for ipv6 */
620 #endif
621 break;
622 case WFQ_HASH_SRCADDR:
623 wfqp->hash_func = wfq_hashbysrcaddr;
624 wfqp->fbmask = FIMB4_DADDR;
625 #ifdef INET6
626 wfqp->fbmask |= FIMB6_FLABEL; /* use flowlabel for ipv6 */
627 #endif
628 break;
629 default:
630 error = EINVAL;
631 break;
633 return error;
637 * wfq device interface
640 altqdev_decl(wfq);
643 wfqopen(dev_t dev, int flag, int fmt,
644 struct lwp *l)
646 return 0;
650 wfqclose(dev_t dev, int flag, int fmt,
651 struct lwp *l)
653 struct ifnet *ifp;
654 struct wfq_interface iface;
655 wfq_state_t *wfqp;
656 int s;
658 s = splnet();
659 while ((wfqp = wfq_list) != NULL) {
660 ifp = wfqp->ifq->altq_ifp;
661 sprintf(iface.wfq_ifacename, "%s", ifp->if_xname);
662 wfq_ifdetach(&iface);
664 splx(s);
665 return 0;
669 wfqioctl(dev_t dev, ioctlcmd_t cmd, void *addr, int flag,
670 struct lwp *l)
672 int error = 0;
673 int s;
675 /* check cmd for superuser only */
676 switch (cmd) {
677 case WFQ_GET_QID:
678 case WFQ_GET_STATS:
679 break;
680 default:
681 #if (__FreeBSD_version > 400000)
682 if ((error = suser(p)) != 0)
683 #else
684 if ((error = kauth_authorize_network(l->l_cred,
685 KAUTH_NETWORK_ALTQ, KAUTH_REQ_NETWORK_ALTQ_WFQ, NULL,
686 NULL, NULL)) != 0)
687 #endif
688 return (error);
689 break;
692 s = splnet();
693 switch (cmd) {
695 case WFQ_ENABLE:
696 error = wfq_setenable((struct wfq_interface *)addr, ENABLE);
697 break;
699 case WFQ_DISABLE:
700 error = wfq_setenable((struct wfq_interface *)addr, DISABLE);
701 break;
703 case WFQ_IF_ATTACH:
704 error = wfq_ifattach((struct wfq_interface *)addr);
705 break;
707 case WFQ_IF_DETACH:
708 error = wfq_ifdetach((struct wfq_interface *)addr);
709 break;
711 case WFQ_GET_QID:
712 error = wfq_getqid((struct wfq_getqid *)addr);
713 break;
715 case WFQ_SET_WEIGHT:
716 error = wfq_setweight((struct wfq_setweight *)addr);
717 break;
719 case WFQ_GET_STATS:
720 error = wfq_getstats((struct wfq_getstats *)addr);
721 break;
723 case WFQ_CONFIG:
724 error = wfq_config((struct wfq_conf *)addr);
725 break;
727 default:
728 error = EINVAL;
729 break;
731 splx(s);
732 return error;
735 #ifdef KLD_MODULE
737 static struct altqsw wfq_sw =
738 {"wfq", wfqopen, wfqclose, wfqioctl};
740 ALTQ_MODULE(altq_wfq, ALTQT_WFQ, &wfq_sw);
742 #endif /* KLD_MODULE */
744 #endif /* ALTQ3_COMPAT */
745 #endif /* ALTQ_WFQ */