xref: /dragonfly/sys/net/altq/altq_cbq.c (revision 20c2db9a) 
1 /*	$KAME: altq_cbq.c,v 1.20 2004/04/17 10:54:48 kjc Exp $	*/
2 /*	$DragonFly: src/sys/net/altq/altq_cbq.c,v 1.7 2008/05/14 11:59:23 sephe Exp $ */
3 
4 /*
5  * Copyright (c) Sun Microsystems, Inc. 1993-1998 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  *
11  * 1. Redistributions of source code must retain the above copyright
12  *    notice, this list of conditions and the following disclaimer.
13  *
14  * 2. Redistributions in binary form must reproduce the above copyright
15  *    notice, this list of conditions and the following disclaimer in the
16  *    documentation and/or other materials provided with the distribution.
17  *
18  * 3. All advertising materials mentioning features or use of this software
19  *    must display the following acknowledgement:
20  *      This product includes software developed by the SMCC Technology
21  *      Development Group at Sun Microsystems, Inc.
22  *
23  * 4. The name of the Sun Microsystems, Inc nor may not be used to endorse or
24  *      promote products derived from this software without specific prior
25  *      written permission.
26  *
27  * SUN MICROSYSTEMS DOES NOT CLAIM MERCHANTABILITY OF THIS SOFTWARE OR THE
28  * SUITABILITY OF THIS SOFTWARE FOR ANY PARTICULAR PURPOSE.  The software is
29  * provided "as is" without express or implied warranty of any kind.
30  *
31  * These notices must be retained in any copies of any part of this software.
32  */
33 
34 #include "opt_altq.h"
35 #include "opt_inet.h"
36 #include "opt_inet6.h"
37 
38 #ifdef ALTQ_CBQ	/* cbq is enabled by ALTQ_CBQ option in opt_altq.h */
39 
40 #include <sys/param.h>
41 #include <sys/malloc.h>
42 #include <sys/mbuf.h>
43 #include <sys/socket.h>
44 #include <sys/systm.h>
45 #include <sys/proc.h>
46 #include <sys/callout.h>
47 #include <sys/errno.h>
48 #include <sys/time.h>
49 #include <sys/thread.h>
50 
51 #include <net/if.h>
52 #include <net/ifq_var.h>
53 #include <netinet/in.h>
54 
55 #include <net/pf/pfvar.h>
56 #include <net/altq/altq.h>
57 #include <net/altq/altq_cbq.h>
58 
59 #include <sys/thread2.h>
60 
61 #define CBQ_SUBQ_INDEX		ALTQ_SUBQ_INDEX_DEFAULT
62 #define CBQ_LOCK(ifq) \
63     ALTQ_SQ_LOCK(&(ifq)->altq_subq[CBQ_SUBQ_INDEX])
64 #define CBQ_UNLOCK(ifq) \
65     ALTQ_SQ_UNLOCK(&(ifq)->altq_subq[CBQ_SUBQ_INDEX])
66 #define CBQ_ASSERT_LOCKED(ifq) \
67     ALTQ_SQ_ASSERT_LOCKED(&(ifq)->altq_subq[CBQ_SUBQ_INDEX])
68 
69 /*
70  * Forward Declarations.
71  */
72 static int		 cbq_class_destroy(cbq_state_t *, struct rm_class *);
73 static struct rm_class  *clh_to_clp(cbq_state_t *, uint32_t);
74 static int		 cbq_clear_interface(cbq_state_t *);
75 static int		 cbq_request(struct ifaltq_subque *, int, void *);
76 static int		 cbq_enqueue(struct ifaltq_subque *, struct mbuf *,
77 			     struct altq_pktattr *);
78 static struct mbuf	*cbq_dequeue(struct ifaltq_subque *, struct mbuf *,
79 			     int);
80 static void		 cbqrestart(struct ifaltq *);
81 static void		 get_class_stats(class_stats_t *, struct rm_class *);
82 static void		 cbq_purge(cbq_state_t *);
83 
84 /*
85  * int
86  * cbq_class_destroy(cbq_mod_state_t *, struct rm_class *) - This
87  *	function destroys a given traffic class.  Before destroying
88  *	the class, all traffic for that class is released.
89  */
90 static int
91 cbq_class_destroy(cbq_state_t *cbqp, struct rm_class *cl)
92 {
93 	int	i;
94 
95 	/* delete the class */
96 	rmc_delete_class(&cbqp->ifnp, cl);
97 
98 	/*
99 	 * free the class handle
100 	 */
101 	for (i = 0; i < CBQ_MAX_CLASSES; i++)
102 		if (cbqp->cbq_class_tbl[i] == cl)
103 			cbqp->cbq_class_tbl[i] = NULL;
104 
105 	if (cl == cbqp->ifnp.root_)
106 		cbqp->ifnp.root_ = NULL;
107 	if (cl == cbqp->ifnp.default_)
108 		cbqp->ifnp.default_ = NULL;
109 	return (0);
110 }
111 
112 /* convert class handle to class pointer */
113 static struct rm_class *
114 clh_to_clp(cbq_state_t *cbqp, uint32_t chandle)
115 {
116 	int i;
117 	struct rm_class *cl;
118 
119 	if (chandle == 0)
120 		return (NULL);
121 	/*
122 	 * first, try optimistically the slot matching the lower bits of
123 	 * the handle.  if it fails, do the linear table search.
124 	 */
125 	i = chandle % CBQ_MAX_CLASSES;
126 	if ((cl = cbqp->cbq_class_tbl[i]) != NULL &&
127 	    cl->stats_.handle == chandle)
128 		return (cl);
129 	for (i = 0; i < CBQ_MAX_CLASSES; i++)
130 		if ((cl = cbqp->cbq_class_tbl[i]) != NULL &&
131 		    cl->stats_.handle == chandle)
132 			return (cl);
133 	return (NULL);
134 }
135 
136 static int
137 cbq_clear_interface(cbq_state_t *cbqp)
138 {
139 	int		 again, i;
140 	struct rm_class	*cl;
141 
142 	/* clear out the classes now */
143 	do {
144 		again = 0;
145 		for (i = 0; i < CBQ_MAX_CLASSES; i++) {
146 			if ((cl = cbqp->cbq_class_tbl[i]) != NULL) {
147 				if (is_a_parent_class(cl))
148 					again++;
149 				else {
150 					cbq_class_destroy(cbqp, cl);
151 					cbqp->cbq_class_tbl[i] = NULL;
152 					if (cl == cbqp->ifnp.root_)
153 						cbqp->ifnp.root_ = NULL;
154 					if (cl == cbqp->ifnp.default_)
155 						cbqp->ifnp.default_ = NULL;
156 				}
157 			}
158 		}
159 	} while (again);
160 
161 	return (0);
162 }
163 
164 static int
165 cbq_request(struct ifaltq_subque *ifsq, int req, void *arg)
166 {
167 	struct ifaltq *ifq = ifsq->ifsq_altq;
168 	cbq_state_t	*cbqp = (cbq_state_t *)ifq->altq_disc;
169 
170 	crit_enter();
171 	switch (req) {
172 	case ALTRQ_PURGE:
173 		if (ifsq_get_index(ifsq) == CBQ_SUBQ_INDEX) {
174 			cbq_purge(cbqp);
175 		} else {
176 			/*
177 			 * Race happened, the unrelated subqueue was
178 			 * picked during the packet scheduler transition.
179 			 */
180 			ifsq_classic_request(ifsq, ALTRQ_PURGE, NULL);
181 		}
182 		break;
183 	}
184 	crit_exit();
185 	return (0);
186 }
187 
188 /* copy the stats info in rm_class to class_states_t */
189 static void
190 get_class_stats(class_stats_t *statsp, struct rm_class *cl)
191 {
192 	statsp->xmit_cnt	= cl->stats_.xmit_cnt;
193 	statsp->drop_cnt	= cl->stats_.drop_cnt;
194 	statsp->over		= cl->stats_.over;
195 	statsp->borrows		= cl->stats_.borrows;
196 	statsp->overactions	= cl->stats_.overactions;
197 	statsp->delays		= cl->stats_.delays;
198 
199 	statsp->depth		= cl->depth_;
200 	statsp->priority	= cl->pri_;
201 	statsp->maxidle		= cl->maxidle_;
202 	statsp->minidle		= cl->minidle_;
203 	statsp->offtime		= cl->offtime_;
204 	statsp->qmax		= qlimit(cl->q_);
205 	statsp->ns_per_byte	= cl->ns_per_byte_;
206 	statsp->wrr_allot	= cl->w_allotment_;
207 	statsp->qcnt		= qlen(cl->q_);
208 	statsp->avgidle		= cl->avgidle_;
209 
210 	statsp->qtype		= qtype(cl->q_);
211 #ifdef ALTQ_RED
212 	if (q_is_red(cl->q_))
213 		red_getstats(cl->red_, &statsp->red[0]);
214 #endif
215 #ifdef ALTQ_RIO
216 	if (q_is_rio(cl->q_))
217 		rio_getstats((rio_t *)cl->red_, &statsp->red[0]);
218 #endif
219 }
220 
221 int
222 cbq_pfattach(struct pf_altq *a, struct ifaltq *ifq)
223 {
224 	return altq_attach(ifq, ALTQT_CBQ, a->altq_disc, ifq_mapsubq_default,
225 	    cbq_enqueue, cbq_dequeue, cbq_request, NULL, NULL);
226 }
227 
228 int
229 cbq_add_altq(struct pf_altq *a)
230 {
231 	cbq_state_t	*cbqp;
232 	struct ifnet	*ifp;
233 
234 	if ((ifp = ifunit(a->ifname)) == NULL)
235 		return (EINVAL);
236 	if (!ifq_is_ready(&ifp->if_snd))
237 		return (ENODEV);
238 
239 	/* allocate and initialize cbq_state_t */
240 	cbqp = kmalloc(sizeof(*cbqp), M_ALTQ, M_WAITOK | M_ZERO);
241 	callout_init(&cbqp->cbq_callout);
242 	cbqp->cbq_qlen = 0;
243 	cbqp->ifnp.ifq_ = &ifp->if_snd;	    /* keep the ifq */
244 	ifq_purge_all(&ifp->if_snd);
245 
246 	/* keep the state in pf_altq */
247 	a->altq_disc = cbqp;
248 
249 	return (0);
250 }
251 
252 int
253 cbq_remove_altq(struct pf_altq *a)
254 {
255 	cbq_state_t	*cbqp;
256 
257 	if ((cbqp = a->altq_disc) == NULL)
258 		return (EINVAL);
259 	a->altq_disc = NULL;
260 
261 	cbq_clear_interface(cbqp);
262 
263 	if (cbqp->ifnp.default_)
264 		cbq_class_destroy(cbqp, cbqp->ifnp.default_);
265 	if (cbqp->ifnp.root_)
266 		cbq_class_destroy(cbqp, cbqp->ifnp.root_);
267 
268 	/* deallocate cbq_state_t */
269 	kfree(cbqp, M_ALTQ);
270 
271 	return (0);
272 }
273 
274 static int
275 cbq_add_queue_locked(struct pf_altq *a, cbq_state_t *cbqp)
276 {
277 	struct rm_class	*borrow, *parent;
278 	struct rm_class	*cl;
279 	struct cbq_opts	*opts;
280 	int		i;
281 
282 	KKASSERT(a->qid != 0);
283 
284 	/*
285 	 * find a free slot in the class table.  if the slot matching
286 	 * the lower bits of qid is free, use this slot.  otherwise,
287 	 * use the first free slot.
288 	 */
289 	i = a->qid % CBQ_MAX_CLASSES;
290 	if (cbqp->cbq_class_tbl[i] != NULL) {
291 		for (i = 0; i < CBQ_MAX_CLASSES; i++)
292 			if (cbqp->cbq_class_tbl[i] == NULL)
293 				break;
294 		if (i == CBQ_MAX_CLASSES)
295 			return (EINVAL);
296 	}
297 
298 	opts = &a->pq_u.cbq_opts;
299 	/* check parameters */
300 	if (a->priority >= CBQ_MAXPRI)
301 		return (EINVAL);
302 
303 	/* Get pointers to parent and borrow classes.  */
304 	parent = clh_to_clp(cbqp, a->parent_qid);
305 	if (opts->flags & CBQCLF_BORROW)
306 		borrow = parent;
307 	else
308 		borrow = NULL;
309 
310 	/*
311 	 * A class must borrow from it's parent or it can not
312 	 * borrow at all.  Hence, borrow can be null.
313 	 */
314 	if (parent == NULL && (opts->flags & CBQCLF_ROOTCLASS) == 0) {
315 		kprintf("cbq_add_queue: no parent class!\n");
316 		return (EINVAL);
317 	}
318 
319 	if ((borrow != parent)  && (borrow != NULL)) {
320 		kprintf("cbq_add_class: borrow class != parent\n");
321 		return (EINVAL);
322 	}
323 
324 	/*
325 	 * check parameters
326 	 */
327 	switch (opts->flags & CBQCLF_CLASSMASK) {
328 	case CBQCLF_ROOTCLASS:
329 		if (parent != NULL)
330 			return (EINVAL);
331 		if (cbqp->ifnp.root_)
332 			return (EINVAL);
333 		break;
334 	case CBQCLF_DEFCLASS:
335 		if (cbqp->ifnp.default_)
336 			return (EINVAL);
337 		break;
338 	case 0:
339 		if (a->qid == 0)
340 			return (EINVAL);
341 		break;
342 	default:
343 		/* more than two flags bits set */
344 		return (EINVAL);
345 	}
346 
347 	/*
348 	 * create a class.  if this is a root class, initialize the
349 	 * interface.
350 	 */
351 	if ((opts->flags & CBQCLF_CLASSMASK) == CBQCLF_ROOTCLASS) {
352 		rmc_init(cbqp->ifnp.ifq_, &cbqp->ifnp, opts->ns_per_byte,
353 		    cbqrestart, a->qlimit, RM_MAXQUEUED,
354 		    opts->maxidle, opts->minidle, opts->offtime,
355 		    opts->flags);
356 		cl = cbqp->ifnp.root_;
357 	} else {
358 		cl = rmc_newclass(a->priority,
359 				  &cbqp->ifnp, opts->ns_per_byte,
360 				  rmc_delay_action, a->qlimit, parent, borrow,
361 				  opts->maxidle, opts->minidle, opts->offtime,
362 				  opts->pktsize, opts->flags);
363 	}
364 	if (cl == NULL)
365 		return (ENOMEM);
366 
367 	/* return handle to user space. */
368 	cl->stats_.handle = a->qid;
369 	cl->stats_.depth = cl->depth_;
370 
371 	/* save the allocated class */
372 	cbqp->cbq_class_tbl[i] = cl;
373 
374 	if ((opts->flags & CBQCLF_CLASSMASK) == CBQCLF_DEFCLASS)
375 		cbqp->ifnp.default_ = cl;
376 
377 	return (0);
378 }
379 
380 int
381 cbq_add_queue(struct pf_altq *a)
382 {
383 	cbq_state_t *cbqp;
384 	struct ifaltq *ifq;
385 	int error;
386 
387 	if (a->qid == 0)
388 		return (EINVAL);
389 
390 	/* XXX not MP safe */
391 	if ((cbqp = a->altq_disc) == NULL)
392 		return (EINVAL);
393 	ifq = cbqp->ifnp.ifq_;
394 
395 	CBQ_LOCK(ifq);
396 	error = cbq_add_queue_locked(a, cbqp);
397 	CBQ_UNLOCK(ifq);
398 
399 	return error;
400 }
401 
402 static int
403 cbq_remove_queue_locked(struct pf_altq *a, cbq_state_t *cbqp)
404 {
405 	struct rm_class	*cl;
406 	int		i;
407 
408 	if ((cl = clh_to_clp(cbqp, a->qid)) == NULL)
409 		return (EINVAL);
410 
411 	/* if we are a parent class, then return an error. */
412 	if (is_a_parent_class(cl))
413 		return (EINVAL);
414 
415 	/* delete the class */
416 	rmc_delete_class(&cbqp->ifnp, cl);
417 
418 	/*
419 	 * free the class handle
420 	 */
421 	for (i = 0; i < CBQ_MAX_CLASSES; i++)
422 		if (cbqp->cbq_class_tbl[i] == cl) {
423 			cbqp->cbq_class_tbl[i] = NULL;
424 			if (cl == cbqp->ifnp.root_)
425 				cbqp->ifnp.root_ = NULL;
426 			if (cl == cbqp->ifnp.default_)
427 				cbqp->ifnp.default_ = NULL;
428 			break;
429 		}
430 
431 	return (0);
432 }
433 
434 int
435 cbq_remove_queue(struct pf_altq *a)
436 {
437 	cbq_state_t *cbqp;
438 	struct ifaltq *ifq;
439 	int error;
440 
441 	/* XXX not MP safe */
442 	if ((cbqp = a->altq_disc) == NULL)
443 		return (EINVAL);
444 	ifq = cbqp->ifnp.ifq_;
445 
446 	CBQ_LOCK(ifq);
447 	error = cbq_remove_queue_locked(a, cbqp);
448 	CBQ_UNLOCK(ifq);
449 
450 	return error;
451 }
452 
453 int
454 cbq_getqstats(struct pf_altq *a, void *ubuf, int *nbytes)
455 {
456 	cbq_state_t	*cbqp;
457 	struct rm_class	*cl;
458 	class_stats_t	 stats;
459 	int		 error = 0;
460 	struct ifaltq 	*ifq;
461 
462 	if (*nbytes < sizeof(stats))
463 		return (EINVAL);
464 
465 	/* XXX not MP safe */
466 	if ((cbqp = altq_lookup(a->ifname, ALTQT_CBQ)) == NULL)
467 		return (EBADF);
468 	ifq = cbqp->ifnp.ifq_;
469 
470 	CBQ_LOCK(ifq);
471 
472 	if ((cl = clh_to_clp(cbqp, a->qid)) == NULL) {
473 		CBQ_UNLOCK(ifq);
474 		return (EINVAL);
475 	}
476 
477 	get_class_stats(&stats, cl);
478 
479 	CBQ_UNLOCK(ifq);
480 
481 	if ((error = copyout((caddr_t)&stats, ubuf, sizeof(stats))) != 0)
482 		return (error);
483 	*nbytes = sizeof(stats);
484 	return (0);
485 }
486 
487 /*
488  * int
489  * cbq_enqueue(struct ifaltq_subqueue *ifq, struct mbuf *m,
490  *     struct altq_pktattr *pattr)
491  *		- Queue data packets.
492  *
493  *	cbq_enqueue is set to ifp->if_altqenqueue and called by an upper
494  *	layer (e.g. ether_output).  cbq_enqueue queues the given packet
495  *	to the cbq, then invokes the driver's start routine.
496  *
497  *	Returns:	0 if the queueing is successful.
498  *			ENOBUFS if a packet dropping occurred as a result of
499  *			the queueing.
500  */
501 
502 static int
503 cbq_enqueue(struct ifaltq_subque *ifsq, struct mbuf *m,
504     struct altq_pktattr *pktattr __unused)
505 {
506 	struct ifaltq *ifq = ifsq->ifsq_altq;
507 	cbq_state_t	*cbqp = (cbq_state_t *)ifq->altq_disc;
508 	struct rm_class	*cl;
509 	int len;
510 
511 	if (ifsq_get_index(ifsq) != CBQ_SUBQ_INDEX) {
512 		/*
513 		 * Race happened, the unrelated subqueue was
514 		 * picked during the packet scheduler transition.
515 		 */
516 		ifsq_classic_request(ifsq, ALTRQ_PURGE, NULL);
517 		m_freem(m);
518 		return (ENOBUFS);
519 	}
520 
521 	/* grab class set by classifier */
522 	if ((m->m_flags & M_PKTHDR) == 0) {
523 		/* should not happen */
524 		if_printf(ifq->altq_ifp, "altq: packet does not have pkthdr\n");
525 		m_freem(m);
526 		return (ENOBUFS);
527 	}
528 	if (m->m_pkthdr.fw_flags & PF_MBUF_STRUCTURE)
529 		cl = clh_to_clp(cbqp, m->m_pkthdr.pf.qid);
530 	else
531 		cl = NULL;
532 	if (cl == NULL) {
533 		cl = cbqp->ifnp.default_;
534 		if (cl == NULL) {
535 			m_freem(m);
536 			return (ENOBUFS);
537 		}
538 	}
539 	crit_enter();
540 	cl->pktattr_ = NULL;
541 	len = m_pktlen(m);
542 	if (rmc_queue_packet(cl, m) != 0) {
543 		/* drop occurred.  some mbuf was freed in rmc_queue_packet. */
544 		PKTCNTR_ADD(&cl->stats_.drop_cnt, len);
545 		crit_exit();
546 		return (ENOBUFS);
547 	}
548 
549 	/* successfully queued. */
550 	++cbqp->cbq_qlen;
551 	++ifsq->ifq_len;
552 	crit_exit();
553 	return (0);
554 }
555 
556 static struct mbuf *
557 cbq_dequeue(struct ifaltq_subque *ifsq, struct mbuf *mpolled, int op)
558 {
559 	struct ifaltq *ifq = ifsq->ifsq_altq;
560 	cbq_state_t	*cbqp = (cbq_state_t *)ifq->altq_disc;
561 	struct mbuf	*m;
562 
563 	if (ifsq_get_index(ifsq) != CBQ_SUBQ_INDEX) {
564 		/*
565 		 * Race happened, the unrelated subqueue was
566 		 * picked during the packet scheduler transition.
567 		 */
568 		ifsq_classic_request(ifsq, ALTRQ_PURGE, NULL);
569 		return NULL;
570 	}
571 
572 	crit_enter();
573 	m = rmc_dequeue_next(&cbqp->ifnp, op);
574 
575 	if (m && op == ALTDQ_REMOVE) {
576 		--cbqp->cbq_qlen;  /* decrement # of packets in cbq */
577 		--ifsq->ifq_len;
578 
579 		/* Update the class. */
580 		rmc_update_class_util(&cbqp->ifnp);
581 	}
582 	crit_exit();
583 	KKASSERT(mpolled == NULL || mpolled == m);
584 	return (m);
585 }
586 
587 /*
588  * void
589  * cbqrestart(queue_t *) - Restart sending of data.
590  * called from rmc_restart in a critical section via timeout after waking up
591  * a suspended class.
592  *	Returns:	NONE
593  */
594 
595 static void
596 cbqrestart(struct ifaltq *ifq)
597 {
598 	cbq_state_t	*cbqp;
599 
600 	CBQ_ASSERT_LOCKED(ifq);
601 
602 	if (!ifq_is_enabled(ifq))
603 		/* cbq must have been detached */
604 		return;
605 
606 	if ((cbqp = (cbq_state_t *)ifq->altq_disc) == NULL)
607 		/* should not happen */
608 		return;
609 
610 	if (cbqp->cbq_qlen > 0) {
611 		struct ifnet *ifp = ifq->altq_ifp;
612 		struct ifaltq_subque *ifsq = &ifq->altq_subq[CBQ_SUBQ_INDEX];
613 
614 		/* Release the altq lock to avoid deadlock */
615 		CBQ_UNLOCK(ifq);
616 
617 		ifsq_serialize_hw(ifsq);
618 		if (ifp->if_start && !ifsq_is_oactive(ifsq))
619 			(*ifp->if_start)(ifp, ifsq);
620 		ifsq_deserialize_hw(ifsq);
621 
622 		CBQ_LOCK(ifq);
623 	}
624 }
625 
626 static void
627 cbq_purge(cbq_state_t *cbqp)
628 {
629 	struct rm_class	*cl;
630 	int i;
631 	for (i = 0; i < CBQ_MAX_CLASSES; i++) {
632 		if ((cl = cbqp->cbq_class_tbl[i]) != NULL)
633 			rmc_dropall(cl);
634 	}
635 	if (ifq_is_enabled(cbqp->ifnp.ifq_))
636 		cbqp->ifnp.ifq_->altq_subq[CBQ_SUBQ_INDEX].ifq_len = 0;
637 }
638 
639 #endif /* ALTQ_CBQ */
640