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 $ */
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
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
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 $");
44 #include <sys/param.h>
45 #include <sys/malloc.h>
48 #include <sys/socket.h>
49 #include <sys/systm.h>
51 #include <sys/errno.h>
53 #include <sys/kernel.h>
54 #include <sys/kauth.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>
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
;
92 wfq_setenable(struct wfq_interface
*ifacep
, int flag
)
97 if ((wfqp
= altq_lookup(ifacep
->wfq_ifacename
, ALTQT_WFQ
)) == NULL
)
102 error
= altq_enable(wfqp
->ifq
);
105 error
= altq_disable(wfqp
->ifq
);
113 wfq_ifattach(struct wfq_interface
*ifacep
)
117 wfq_state_t
*new_wfqp
;
120 if ((ifp
= ifunit(ifacep
->wfq_ifacename
)) == NULL
) {
122 printf("wfq_ifattach()...no ifp found\n");
127 if (!ALTQ_IS_READY(&ifp
->if_snd
)) {
129 printf("wfq_ifattach()...altq is not ready\n");
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
)
139 queue
= malloc(sizeof(wfq
) * DEFAULT_QSIZE
, M_DEVBUF
, M_WAITOK
|M_ZERO
);
141 free(new_wfqp
, M_DEVBUF
);
146 new_wfqp
->ifq
= &ifp
->if_snd
;
147 new_wfqp
->nums
= DEFAULT_QSIZE
;
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;
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
);
173 new_wfqp
->next
= wfq_list
;
181 wfq_ifdetach(struct wfq_interface
*ifacep
)
186 if ((wfqp
= altq_lookup(ifacep
->wfq_ifacename
, ALTQT_WFQ
)) == NULL
)
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
;
200 wfq_state_t
*wp
= wfq_list
;
202 if (wp
->next
== wfqp
) {
203 wp
->next
= wfqp
->next
;
206 } while ((wp
= wp
->next
) != NULL
);
209 /* deallocate wfq_state_t */
210 free(wfqp
->queue
, M_DEVBUF
);
211 free(wfqp
, M_DEVBUF
);
216 wfq_request(struct ifaltq
*ifq
, int req
, void *arg
)
218 wfq_state_t
*wfqp
= (wfq_state_t
*)ifq
->altq_disc
;
222 wfq_flush(wfqp
->ifq
);
230 wfq_flush(struct ifaltq
*ifq
)
234 while ((mp
= wfq_ifdequeue(ifq
, ALTDQ_REMOVE
)) != NULL
)
236 if (ALTQ_IS_ENABLED(ifq
))
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
)]);
252 wfq_ifenqueue(struct ifaltq
*ifq
, struct mbuf
*mp
, struct altq_pktattr
*pktattr
)
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
)
268 queue
->tail
->m_nextpkt
= mp
;
270 byte
= mp
->m_pkthdr
.len
;
271 queue
->bytes
+= byte
;
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
;
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
;
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
);
308 if(drop_queue
== queue
)
309 /* the queue for this flow is selected to drop */
316 wfq_hash(struct flowinfo
*flow
, int n
)
321 if (flow
->fi_family
== AF_INET
) {
322 struct flowinfo_in
*fp
= (struct flowinfo_in
*)flow
;
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);
332 else if (flow
->fi_family
== AF_INET6
) {
333 struct flowinfo_in6
*fp6
= (struct flowinfo_in6
*)flow
;
335 val
= ntohl(fp6
->fi6_flowlabel
);
344 wfq_hashbydstaddr(struct flowinfo
*flow
, int n
)
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);
356 else if (flow
->fi_family
== AF_INET6
) {
357 struct flowinfo_in6
*fp6
= (struct flowinfo_in6
*)flow
;
359 val
= ntohl(fp6
->fi6_flowlabel
);
368 wfq_hashbysrcaddr(struct flowinfo
*flow
, int n
)
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);
380 else if (flow
->fi_family
== AF_INET6
) {
381 struct flowinfo_in6
*fp6
= (struct flowinfo_in6
*)flow
;
383 val
= ntohl(fp6
->fi6_flowlabel
);
392 wfq_hashbysrcport(struct flowinfo
*flow
, int n
)
397 if (flow
->fi_family
== AF_INET
) {
398 struct flowinfo_in
*fp
= (struct flowinfo_in
*)flow
;
403 else if (flow
->fi_family
== AF_INET6
) {
404 struct flowinfo_in6
*fp6
= (struct flowinfo_in6
*)flow
;
406 val
= fp6
->fi6_sport
;
410 val
= val
^ (val
>> 8);
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
)
425 if ((byte
= queue
->bytes
* 100 / queue
->weight
) > max_byte
) {
429 } while ((queue
= queue
->next
) != wfqp
->rrp
);
436 wfq_ifdequeue(struct ifaltq
*ifq
, int op
)
443 wfqp
= (wfq_state_t
*)ifq
->altq_disc
;
445 if ((wfqp
->bytes
== 0) || ((queue
= wfqp
->rrp
) == NULL
))
446 /* no packet in the queues */
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
458 queue
->next
= queue
->prev
= NULL
;
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
;
474 /* dequeue a packet from this queue */
476 if (op
== ALTDQ_REMOVE
) {
477 if((queue
->head
= mp
->m_nextpkt
) == 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
);
485 if (ALTQ_IS_ENABLED(ifq
))
490 /* if the queue gets empty by this dequeueing,
491 the queue will be removed from the active list
495 /* advance the round-robin pointer */
496 queue
= wfqp
->rrp
= queue
->next
;
502 wfq_getqid(struct wfq_getqid
*gqidp
)
506 if ((wfqp
= altq_lookup(gqidp
->iface
.wfq_ifacename
, ALTQT_WFQ
))
510 gqidp
->qid
= (*wfqp
->hash_func
)(&gqidp
->flow
, wfqp
->nums
);
515 wfq_setweight(struct wfq_setweight
*swp
)
521 if (swp
->weight
< 0) {
522 printf("set weight in natural number\n");
526 if ((wfqp
= altq_lookup(swp
->iface
.wfq_ifacename
, ALTQT_WFQ
)) == NULL
)
529 queue
= &wfqp
->queue
[swp
->qid
];
531 queue
->weight
= swp
->weight
;
538 wfq_getstats(struct wfq_getstats
*gsp
)
544 if ((wfqp
= altq_lookup(gsp
->iface
.wfq_ifacename
, ALTQT_WFQ
)) == NULL
)
547 if (gsp
->qid
>= wfqp
->nums
)
550 queue
= &wfqp
->queue
[gsp
->qid
];
553 stats
->bytes
= queue
->bytes
;
554 stats
->weight
= queue
->weight
;
555 stats
->xmit_cnt
= queue
->xmit_cnt
;
556 stats
->drop_cnt
= queue
->drop_cnt
;
563 wfq_config(struct wfq_conf
*cf
)
569 if ((wfqp
= altq_lookup(cf
->iface
.wfq_ifacename
, ALTQT_WFQ
)) == NULL
)
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
,
585 wfqp
->nums
= cf
->nqueues
;
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;
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
;
605 wfqp
->fbmask
|= FIMB6_FLABEL
; /* use flowlabel for ipv6 */
608 case WFQ_HASH_SRCPORT
:
609 wfqp
->hash_func
= wfq_hashbysrcport
;
610 wfqp
->fbmask
= FIMB4_SPORT
;
612 wfqp
->fbmask
|= FIMB6_SPORT
;
616 wfqp
->hash_func
= wfq_hash
;
617 wfqp
->fbmask
= FIMB4_ALL
;
619 wfqp
->fbmask
|= FIMB6_FLABEL
; /* use flowlabel for ipv6 */
622 case WFQ_HASH_SRCADDR
:
623 wfqp
->hash_func
= wfq_hashbysrcaddr
;
624 wfqp
->fbmask
= FIMB4_DADDR
;
626 wfqp
->fbmask
|= FIMB6_FLABEL
; /* use flowlabel for ipv6 */
637 * wfq device interface
643 wfqopen(dev_t dev
, int flag
, int fmt
,
650 wfqclose(dev_t dev
, int flag
, int fmt
,
654 struct wfq_interface iface
;
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
);
669 wfqioctl(dev_t dev
, ioctlcmd_t cmd
, void *addr
, int flag
,
675 /* check cmd for superuser only */
681 #if (__FreeBSD_version > 400000)
682 if ((error
= suser(p
)) != 0)
684 if ((error
= kauth_authorize_network(l
->l_cred
,
685 KAUTH_NETWORK_ALTQ
, KAUTH_REQ_NETWORK_ALTQ_WFQ
, NULL
,
696 error
= wfq_setenable((struct wfq_interface
*)addr
, ENABLE
);
700 error
= wfq_setenable((struct wfq_interface
*)addr
, DISABLE
);
704 error
= wfq_ifattach((struct wfq_interface
*)addr
);
708 error
= wfq_ifdetach((struct wfq_interface
*)addr
);
712 error
= wfq_getqid((struct wfq_getqid
*)addr
);
716 error
= wfq_setweight((struct wfq_setweight
*)addr
);
720 error
= wfq_getstats((struct wfq_getstats
*)addr
);
724 error
= wfq_config((struct wfq_conf
*)addr
);
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 */