2 * Copyright (c) 2003 Patrick McHardy, <kaber@trash.net>
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License
6 * as published by the Free Software Foundation; either version 2
7 * of the License, or (at your option) any later version.
9 * 2003-10-17 - Ported from altq
12 * Copyright (c) 1997-1999 Carnegie Mellon University. All Rights Reserved.
14 * Permission to use, copy, modify, and distribute this software and
15 * its documentation is hereby granted (including for commercial or
16 * for-profit use), provided that both the copyright notice and this
17 * permission notice appear in all copies of the software, derivative
18 * works, or modified versions, and any portions thereof.
20 * THIS SOFTWARE IS EXPERIMENTAL AND IS KNOWN TO HAVE BUGS, SOME OF
21 * WHICH MAY HAVE SERIOUS CONSEQUENCES. CARNEGIE MELLON PROVIDES THIS
22 * SOFTWARE IN ITS ``AS IS'' CONDITION, AND ANY EXPRESS OR IMPLIED
23 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
24 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
25 * DISCLAIMED. IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY BE LIABLE
26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
27 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
28 * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
29 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
30 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
31 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
32 * USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
35 * Carnegie Mellon encourages (but does not require) users of this
36 * software to return any improvements or extensions that they make,
37 * and to grant Carnegie Mellon the rights to redistribute these
38 * changes without encumbrance.
41 * H-FSC is described in Proceedings of SIGCOMM'97,
42 * "A Hierarchical Fair Service Curve Algorithm for Link-Sharing,
43 * Real-Time and Priority Service"
44 * by Ion Stoica, Hui Zhang, and T. S. Eugene Ng.
46 * Oleg Cherevko <olwi@aq.ml.com.ua> added the upperlimit for link-sharing.
47 * when a class has an upperlimit, the fit-time is computed from the
48 * upperlimit service curve. the link-sharing scheduler does not schedule
49 * a class whose fit-time exceeds the current time.
52 #include <linux/kernel.h>
53 #include <linux/module.h>
54 #include <linux/types.h>
55 #include <linux/errno.h>
56 #include <linux/jiffies.h>
57 #include <linux/compiler.h>
58 #include <linux/spinlock.h>
59 #include <linux/skbuff.h>
60 #include <linux/string.h>
61 #include <linux/slab.h>
62 #include <linux/timer.h>
63 #include <linux/list.h>
64 #include <linux/rbtree.h>
65 #include <linux/init.h>
66 #include <linux/netdevice.h>
67 #include <linux/rtnetlink.h>
68 #include <linux/pkt_sched.h>
69 #include <net/pkt_sched.h>
70 #include <net/pkt_cls.h>
71 #include <asm/system.h>
72 #include <asm/div64.h>
77 * kernel internal service curve representation:
78 * coordinates are given by 64 bit unsigned integers.
79 * x-axis: unit is clock count.
80 * y-axis: unit is byte.
82 * The service curve parameters are converted to the internal
83 * representation. The slope values are scaled to avoid overflow.
84 * the inverse slope values as well as the y-projection of the 1st
85 * segment are kept in order to to avoid 64-bit divide operations
86 * that are expensive on 32-bit architectures.
91 u64 sm1
; /* scaled slope of the 1st segment */
92 u64 ism1
; /* scaled inverse-slope of the 1st segment */
93 u64 dx
; /* the x-projection of the 1st segment */
94 u64 dy
; /* the y-projection of the 1st segment */
95 u64 sm2
; /* scaled slope of the 2nd segment */
96 u64 ism2
; /* scaled inverse-slope of the 2nd segment */
99 /* runtime service curve */
102 u64 x
; /* current starting position on x-axis */
103 u64 y
; /* current starting position on y-axis */
104 u64 sm1
; /* scaled slope of the 1st segment */
105 u64 ism1
; /* scaled inverse-slope of the 1st segment */
106 u64 dx
; /* the x-projection of the 1st segment */
107 u64 dy
; /* the y-projection of the 1st segment */
108 u64 sm2
; /* scaled slope of the 2nd segment */
109 u64 ism2
; /* scaled inverse-slope of the 2nd segment */
112 enum hfsc_class_flags
121 u32 classid
; /* class id */
122 unsigned int refcnt
; /* usage count */
124 struct gnet_stats_basic bstats
;
125 struct gnet_stats_queue qstats
;
126 struct gnet_stats_rate_est rate_est
;
127 spinlock_t
*stats_lock
;
128 unsigned int level
; /* class level in hierarchy */
129 struct tcf_proto
*filter_list
; /* filter list */
130 unsigned int filter_cnt
; /* filter count */
132 struct hfsc_sched
*sched
; /* scheduler data */
133 struct hfsc_class
*cl_parent
; /* parent class */
134 struct list_head siblings
; /* sibling classes */
135 struct list_head children
; /* child classes */
136 struct Qdisc
*qdisc
; /* leaf qdisc */
138 struct rb_node el_node
; /* qdisc's eligible tree member */
139 struct rb_root vt_tree
; /* active children sorted by cl_vt */
140 struct rb_node vt_node
; /* parent's vt_tree member */
141 struct rb_root cf_tree
; /* active children sorted by cl_f */
142 struct rb_node cf_node
; /* parent's cf_heap member */
143 struct list_head hlist
; /* hash list member */
144 struct list_head dlist
; /* drop list member */
146 u64 cl_total
; /* total work in bytes */
147 u64 cl_cumul
; /* cumulative work in bytes done by
148 real-time criteria */
150 u64 cl_d
; /* deadline*/
151 u64 cl_e
; /* eligible time */
152 u64 cl_vt
; /* virtual time */
153 u64 cl_f
; /* time when this class will fit for
154 link-sharing, max(myf, cfmin) */
155 u64 cl_myf
; /* my fit-time (calculated from this
156 class's own upperlimit curve) */
157 u64 cl_myfadj
; /* my fit-time adjustment (to cancel
158 history dependence) */
159 u64 cl_cfmin
; /* earliest children's fit-time (used
160 with cl_myf to obtain cl_f) */
161 u64 cl_cvtmin
; /* minimal virtual time among the
162 children fit for link-sharing
163 (monotonic within a period) */
164 u64 cl_vtadj
; /* intra-period cumulative vt
166 u64 cl_vtoff
; /* inter-period cumulative vt offset */
167 u64 cl_cvtmax
; /* max child's vt in the last period */
168 u64 cl_cvtoff
; /* cumulative cvtmax of all periods */
169 u64 cl_pcvtoff
; /* parent's cvtoff at initalization
172 struct internal_sc cl_rsc
; /* internal real-time service curve */
173 struct internal_sc cl_fsc
; /* internal fair service curve */
174 struct internal_sc cl_usc
; /* internal upperlimit service curve */
175 struct runtime_sc cl_deadline
; /* deadline curve */
176 struct runtime_sc cl_eligible
; /* eligible curve */
177 struct runtime_sc cl_virtual
; /* virtual curve */
178 struct runtime_sc cl_ulimit
; /* upperlimit curve */
180 unsigned long cl_flags
; /* which curves are valid */
181 unsigned long cl_vtperiod
; /* vt period sequence number */
182 unsigned long cl_parentperiod
;/* parent's vt period sequence number*/
183 unsigned long cl_nactive
; /* number of active children */
186 #define HFSC_HSIZE 16
190 u16 defcls
; /* default class id */
191 struct hfsc_class root
; /* root class */
192 struct list_head clhash
[HFSC_HSIZE
]; /* class hash */
193 struct rb_root eligible
; /* eligible tree */
194 struct list_head droplist
; /* active leaf class list (for
196 struct sk_buff_head requeue
; /* requeued packet */
197 struct timer_list wd_timer
; /* watchdog timer */
203 #ifdef CONFIG_NET_SCH_CLK_GETTIMEOFDAY
204 #include <linux/time.h>
205 #undef PSCHED_GET_TIME
206 #define PSCHED_GET_TIME(stamp) \
209 do_gettimeofday(&tv); \
210 (stamp) = 1ULL * USEC_PER_SEC * tv.tv_sec + tv.tv_usec; \
215 #define ASSERT(cond) \
217 if (unlikely(!(cond))) \
218 printk("assertion %s failed at %s:%i (%s)\n", \
219 #cond, __FILE__, __LINE__, __FUNCTION__); \
223 #endif /* HFSC_DEBUG */
225 #define HT_INFINITY 0xffffffffffffffffULL /* infinite time value */
229 * eligible tree holds backlogged classes being sorted by their eligible times.
230 * there is one eligible tree per hfsc instance.
234 eltree_insert(struct hfsc_class
*cl
)
236 struct rb_node
**p
= &cl
->sched
->eligible
.rb_node
;
237 struct rb_node
*parent
= NULL
;
238 struct hfsc_class
*cl1
;
242 cl1
= rb_entry(parent
, struct hfsc_class
, el_node
);
243 if (cl
->cl_e
>= cl1
->cl_e
)
244 p
= &parent
->rb_right
;
246 p
= &parent
->rb_left
;
248 rb_link_node(&cl
->el_node
, parent
, p
);
249 rb_insert_color(&cl
->el_node
, &cl
->sched
->eligible
);
253 eltree_remove(struct hfsc_class
*cl
)
255 rb_erase(&cl
->el_node
, &cl
->sched
->eligible
);
259 eltree_update(struct hfsc_class
*cl
)
265 /* find the class with the minimum deadline among the eligible classes */
266 static inline struct hfsc_class
*
267 eltree_get_mindl(struct hfsc_sched
*q
, u64 cur_time
)
269 struct hfsc_class
*p
, *cl
= NULL
;
272 for (n
= rb_first(&q
->eligible
); n
!= NULL
; n
= rb_next(n
)) {
273 p
= rb_entry(n
, struct hfsc_class
, el_node
);
274 if (p
->cl_e
> cur_time
)
276 if (cl
== NULL
|| p
->cl_d
< cl
->cl_d
)
282 /* find the class with minimum eligible time among the eligible classes */
283 static inline struct hfsc_class
*
284 eltree_get_minel(struct hfsc_sched
*q
)
288 n
= rb_first(&q
->eligible
);
291 return rb_entry(n
, struct hfsc_class
, el_node
);
295 * vttree holds holds backlogged child classes being sorted by their virtual
296 * time. each intermediate class has one vttree.
299 vttree_insert(struct hfsc_class
*cl
)
301 struct rb_node
**p
= &cl
->cl_parent
->vt_tree
.rb_node
;
302 struct rb_node
*parent
= NULL
;
303 struct hfsc_class
*cl1
;
307 cl1
= rb_entry(parent
, struct hfsc_class
, vt_node
);
308 if (cl
->cl_vt
>= cl1
->cl_vt
)
309 p
= &parent
->rb_right
;
311 p
= &parent
->rb_left
;
313 rb_link_node(&cl
->vt_node
, parent
, p
);
314 rb_insert_color(&cl
->vt_node
, &cl
->cl_parent
->vt_tree
);
318 vttree_remove(struct hfsc_class
*cl
)
320 rb_erase(&cl
->vt_node
, &cl
->cl_parent
->vt_tree
);
324 vttree_update(struct hfsc_class
*cl
)
330 static inline struct hfsc_class
*
331 vttree_firstfit(struct hfsc_class
*cl
, u64 cur_time
)
333 struct hfsc_class
*p
;
336 for (n
= rb_first(&cl
->vt_tree
); n
!= NULL
; n
= rb_next(n
)) {
337 p
= rb_entry(n
, struct hfsc_class
, vt_node
);
338 if (p
->cl_f
<= cur_time
)
345 * get the leaf class with the minimum vt in the hierarchy
347 static struct hfsc_class
*
348 vttree_get_minvt(struct hfsc_class
*cl
, u64 cur_time
)
350 /* if root-class's cfmin is bigger than cur_time nothing to do */
351 if (cl
->cl_cfmin
> cur_time
)
354 while (cl
->level
> 0) {
355 cl
= vttree_firstfit(cl
, cur_time
);
359 * update parent's cl_cvtmin.
361 if (cl
->cl_parent
->cl_cvtmin
< cl
->cl_vt
)
362 cl
->cl_parent
->cl_cvtmin
= cl
->cl_vt
;
368 cftree_insert(struct hfsc_class
*cl
)
370 struct rb_node
**p
= &cl
->cl_parent
->cf_tree
.rb_node
;
371 struct rb_node
*parent
= NULL
;
372 struct hfsc_class
*cl1
;
376 cl1
= rb_entry(parent
, struct hfsc_class
, cf_node
);
377 if (cl
->cl_f
>= cl1
->cl_f
)
378 p
= &parent
->rb_right
;
380 p
= &parent
->rb_left
;
382 rb_link_node(&cl
->cf_node
, parent
, p
);
383 rb_insert_color(&cl
->cf_node
, &cl
->cl_parent
->cf_tree
);
387 cftree_remove(struct hfsc_class
*cl
)
389 rb_erase(&cl
->cf_node
, &cl
->cl_parent
->cf_tree
);
393 cftree_update(struct hfsc_class
*cl
)
400 * service curve support functions
402 * external service curve parameters
405 * internal service curve parameters
406 * sm: (bytes/psched_us) << SM_SHIFT
407 * ism: (psched_us/byte) << ISM_SHIFT
410 * Clock source resolution (CONFIG_NET_SCH_CLK_*)
411 * JIFFIES: for 48<=HZ<=1534 resolution is between 0.63us and 1.27us.
412 * CPU: resolution is between 0.5us and 1us.
413 * GETTIMEOFDAY: resolution is exactly 1us.
415 * sm and ism are scaled in order to keep effective digits.
416 * SM_SHIFT and ISM_SHIFT are selected to keep at least 4 effective
417 * digits in decimal using the following table.
419 * Note: We can afford the additional accuracy (altq hfsc keeps at most
420 * 3 effective digits) thanks to the fact that linux clock is bounded
423 * bits/sec 100Kbps 1Mbps 10Mbps 100Mbps 1Gbps
424 * ------------+-------------------------------------------------------
425 * bytes/0.5us 6.25e-3 62.5e-3 625e-3 6250e-e 62500e-3
426 * bytes/us 12.5e-3 125e-3 1250e-3 12500e-3 125000e-3
427 * bytes/1.27us 15.875e-3 158.75e-3 1587.5e-3 15875e-3 158750e-3
429 * 0.5us/byte 160 16 1.6 0.16 0.016
430 * us/byte 80 8 0.8 0.08 0.008
431 * 1.27us/byte 63 6.3 0.63 0.063 0.0063
436 #define SM_MASK ((1ULL << SM_SHIFT) - 1)
437 #define ISM_MASK ((1ULL << ISM_SHIFT) - 1)
440 seg_x2y(u64 x
, u64 sm
)
446 * y = x * sm >> SM_SHIFT
447 * but divide it for the upper and lower bits to avoid overflow
449 y
= (x
>> SM_SHIFT
) * sm
+ (((x
& SM_MASK
) * sm
) >> SM_SHIFT
);
454 seg_y2x(u64 y
, u64 ism
)
460 else if (ism
== HT_INFINITY
)
463 x
= (y
>> ISM_SHIFT
) * ism
464 + (((y
& ISM_MASK
) * ism
) >> ISM_SHIFT
);
469 /* Convert m (bps) into sm (bytes/psched us) */
475 sm
= ((u64
)m
<< SM_SHIFT
);
476 sm
+= PSCHED_JIFFIE2US(HZ
) - 1;
477 do_div(sm
, PSCHED_JIFFIE2US(HZ
));
481 /* convert m (bps) into ism (psched us/byte) */
490 ism
= ((u64
)PSCHED_JIFFIE2US(HZ
) << ISM_SHIFT
);
497 /* convert d (us) into dx (psched us) */
503 dx
= ((u64
)d
* PSCHED_JIFFIE2US(HZ
));
504 dx
+= USEC_PER_SEC
- 1;
505 do_div(dx
, USEC_PER_SEC
);
509 /* convert sm (bytes/psched us) into m (bps) */
515 m
= (sm
* PSCHED_JIFFIE2US(HZ
)) >> SM_SHIFT
;
519 /* convert dx (psched us) into d (us) */
525 d
= dx
* USEC_PER_SEC
;
526 do_div(d
, PSCHED_JIFFIE2US(HZ
));
531 sc2isc(struct tc_service_curve
*sc
, struct internal_sc
*isc
)
533 isc
->sm1
= m2sm(sc
->m1
);
534 isc
->ism1
= m2ism(sc
->m1
);
535 isc
->dx
= d2dx(sc
->d
);
536 isc
->dy
= seg_x2y(isc
->dx
, isc
->sm1
);
537 isc
->sm2
= m2sm(sc
->m2
);
538 isc
->ism2
= m2ism(sc
->m2
);
542 * initialize the runtime service curve with the given internal
543 * service curve starting at (x, y).
546 rtsc_init(struct runtime_sc
*rtsc
, struct internal_sc
*isc
, u64 x
, u64 y
)
550 rtsc
->sm1
= isc
->sm1
;
551 rtsc
->ism1
= isc
->ism1
;
554 rtsc
->sm2
= isc
->sm2
;
555 rtsc
->ism2
= isc
->ism2
;
559 * calculate the y-projection of the runtime service curve by the
560 * given x-projection value
563 rtsc_y2x(struct runtime_sc
*rtsc
, u64 y
)
569 else if (y
<= rtsc
->y
+ rtsc
->dy
) {
570 /* x belongs to the 1st segment */
572 x
= rtsc
->x
+ rtsc
->dx
;
574 x
= rtsc
->x
+ seg_y2x(y
- rtsc
->y
, rtsc
->ism1
);
576 /* x belongs to the 2nd segment */
577 x
= rtsc
->x
+ rtsc
->dx
578 + seg_y2x(y
- rtsc
->y
- rtsc
->dy
, rtsc
->ism2
);
584 rtsc_x2y(struct runtime_sc
*rtsc
, u64 x
)
590 else if (x
<= rtsc
->x
+ rtsc
->dx
)
591 /* y belongs to the 1st segment */
592 y
= rtsc
->y
+ seg_x2y(x
- rtsc
->x
, rtsc
->sm1
);
594 /* y belongs to the 2nd segment */
595 y
= rtsc
->y
+ rtsc
->dy
596 + seg_x2y(x
- rtsc
->x
- rtsc
->dx
, rtsc
->sm2
);
601 * update the runtime service curve by taking the minimum of the current
602 * runtime service curve and the service curve starting at (x, y).
605 rtsc_min(struct runtime_sc
*rtsc
, struct internal_sc
*isc
, u64 x
, u64 y
)
610 if (isc
->sm1
<= isc
->sm2
) {
611 /* service curve is convex */
612 y1
= rtsc_x2y(rtsc
, x
);
614 /* the current rtsc is smaller */
622 * service curve is concave
623 * compute the two y values of the current rtsc
627 y1
= rtsc_x2y(rtsc
, x
);
629 /* rtsc is below isc, no change to rtsc */
633 y2
= rtsc_x2y(rtsc
, x
+ isc
->dx
);
634 if (y2
>= y
+ isc
->dy
) {
635 /* rtsc is above isc, replace rtsc by isc */
644 * the two curves intersect
645 * compute the offsets (dx, dy) using the reverse
646 * function of seg_x2y()
647 * seg_x2y(dx, sm1) == seg_x2y(dx, sm2) + (y1 - y)
649 dx
= (y1
- y
) << SM_SHIFT
;
650 dsm
= isc
->sm1
- isc
->sm2
;
653 * check if (x, y1) belongs to the 1st segment of rtsc.
654 * if so, add the offset.
656 if (rtsc
->x
+ rtsc
->dx
> x
)
657 dx
+= rtsc
->x
+ rtsc
->dx
- x
;
658 dy
= seg_x2y(dx
, isc
->sm1
);
668 init_ed(struct hfsc_class
*cl
, unsigned int next_len
)
672 PSCHED_GET_TIME(cur_time
);
674 /* update the deadline curve */
675 rtsc_min(&cl
->cl_deadline
, &cl
->cl_rsc
, cur_time
, cl
->cl_cumul
);
678 * update the eligible curve.
679 * for concave, it is equal to the deadline curve.
680 * for convex, it is a linear curve with slope m2.
682 cl
->cl_eligible
= cl
->cl_deadline
;
683 if (cl
->cl_rsc
.sm1
<= cl
->cl_rsc
.sm2
) {
684 cl
->cl_eligible
.dx
= 0;
685 cl
->cl_eligible
.dy
= 0;
688 /* compute e and d */
689 cl
->cl_e
= rtsc_y2x(&cl
->cl_eligible
, cl
->cl_cumul
);
690 cl
->cl_d
= rtsc_y2x(&cl
->cl_deadline
, cl
->cl_cumul
+ next_len
);
696 update_ed(struct hfsc_class
*cl
, unsigned int next_len
)
698 cl
->cl_e
= rtsc_y2x(&cl
->cl_eligible
, cl
->cl_cumul
);
699 cl
->cl_d
= rtsc_y2x(&cl
->cl_deadline
, cl
->cl_cumul
+ next_len
);
705 update_d(struct hfsc_class
*cl
, unsigned int next_len
)
707 cl
->cl_d
= rtsc_y2x(&cl
->cl_deadline
, cl
->cl_cumul
+ next_len
);
711 update_cfmin(struct hfsc_class
*cl
)
713 struct rb_node
*n
= rb_first(&cl
->cf_tree
);
714 struct hfsc_class
*p
;
720 p
= rb_entry(n
, struct hfsc_class
, cf_node
);
721 cl
->cl_cfmin
= p
->cl_f
;
725 init_vf(struct hfsc_class
*cl
, unsigned int len
)
727 struct hfsc_class
*max_cl
;
734 for (; cl
->cl_parent
!= NULL
; cl
= cl
->cl_parent
) {
735 if (go_active
&& cl
->cl_nactive
++ == 0)
741 n
= rb_last(&cl
->cl_parent
->vt_tree
);
743 max_cl
= rb_entry(n
, struct hfsc_class
,vt_node
);
745 * set vt to the average of the min and max
746 * classes. if the parent's period didn't
747 * change, don't decrease vt of the class.
750 if (cl
->cl_parent
->cl_cvtmin
!= 0)
751 vt
= (cl
->cl_parent
->cl_cvtmin
+ vt
)/2;
753 if (cl
->cl_parent
->cl_vtperiod
!=
754 cl
->cl_parentperiod
|| vt
> cl
->cl_vt
)
758 * first child for a new parent backlog period.
759 * add parent's cvtmax to cvtoff to make a new
760 * vt (vtoff + vt) larger than the vt in the
761 * last period for all children.
763 vt
= cl
->cl_parent
->cl_cvtmax
;
764 cl
->cl_parent
->cl_cvtoff
+= vt
;
765 cl
->cl_parent
->cl_cvtmax
= 0;
766 cl
->cl_parent
->cl_cvtmin
= 0;
770 cl
->cl_vtoff
= cl
->cl_parent
->cl_cvtoff
-
773 /* update the virtual curve */
774 vt
= cl
->cl_vt
+ cl
->cl_vtoff
;
775 rtsc_min(&cl
->cl_virtual
, &cl
->cl_fsc
, vt
,
777 if (cl
->cl_virtual
.x
== vt
) {
778 cl
->cl_virtual
.x
-= cl
->cl_vtoff
;
783 cl
->cl_vtperiod
++; /* increment vt period */
784 cl
->cl_parentperiod
= cl
->cl_parent
->cl_vtperiod
;
785 if (cl
->cl_parent
->cl_nactive
== 0)
786 cl
->cl_parentperiod
++;
792 if (cl
->cl_flags
& HFSC_USC
) {
793 /* class has upper limit curve */
795 PSCHED_GET_TIME(cur_time
);
797 /* update the ulimit curve */
798 rtsc_min(&cl
->cl_ulimit
, &cl
->cl_usc
, cur_time
,
801 cl
->cl_myf
= rtsc_y2x(&cl
->cl_ulimit
,
807 f
= max(cl
->cl_myf
, cl
->cl_cfmin
);
811 update_cfmin(cl
->cl_parent
);
817 update_vf(struct hfsc_class
*cl
, unsigned int len
, u64 cur_time
)
819 u64 f
; /* , myf_bound, delta; */
822 if (cl
->qdisc
->q
.qlen
== 0 && cl
->cl_flags
& HFSC_FSC
)
825 for (; cl
->cl_parent
!= NULL
; cl
= cl
->cl_parent
) {
828 if (!(cl
->cl_flags
& HFSC_FSC
) || cl
->cl_nactive
== 0)
831 if (go_passive
&& --cl
->cl_nactive
== 0)
837 /* no more active child, going passive */
839 /* update cvtmax of the parent class */
840 if (cl
->cl_vt
> cl
->cl_parent
->cl_cvtmax
)
841 cl
->cl_parent
->cl_cvtmax
= cl
->cl_vt
;
843 /* remove this class from the vt tree */
847 update_cfmin(cl
->cl_parent
);
855 cl
->cl_vt
= rtsc_y2x(&cl
->cl_virtual
, cl
->cl_total
)
856 - cl
->cl_vtoff
+ cl
->cl_vtadj
;
859 * if vt of the class is smaller than cvtmin,
860 * the class was skipped in the past due to non-fit.
861 * if so, we need to adjust vtadj.
863 if (cl
->cl_vt
< cl
->cl_parent
->cl_cvtmin
) {
864 cl
->cl_vtadj
+= cl
->cl_parent
->cl_cvtmin
- cl
->cl_vt
;
865 cl
->cl_vt
= cl
->cl_parent
->cl_cvtmin
;
868 /* update the vt tree */
871 if (cl
->cl_flags
& HFSC_USC
) {
872 cl
->cl_myf
= cl
->cl_myfadj
+ rtsc_y2x(&cl
->cl_ulimit
,
876 * This code causes classes to stay way under their
877 * limit when multiple classes are used at gigabit
878 * speed. needs investigation. -kaber
881 * if myf lags behind by more than one clock tick
882 * from the current time, adjust myfadj to prevent
883 * a rate-limited class from going greedy.
884 * in a steady state under rate-limiting, myf
885 * fluctuates within one clock tick.
887 myf_bound
= cur_time
- PSCHED_JIFFIE2US(1);
888 if (cl
->cl_myf
< myf_bound
) {
889 delta
= cur_time
- cl
->cl_myf
;
890 cl
->cl_myfadj
+= delta
;
896 f
= max(cl
->cl_myf
, cl
->cl_cfmin
);
900 update_cfmin(cl
->cl_parent
);
906 set_active(struct hfsc_class
*cl
, unsigned int len
)
908 if (cl
->cl_flags
& HFSC_RSC
)
910 if (cl
->cl_flags
& HFSC_FSC
)
913 list_add_tail(&cl
->dlist
, &cl
->sched
->droplist
);
917 set_passive(struct hfsc_class
*cl
)
919 if (cl
->cl_flags
& HFSC_RSC
)
922 list_del(&cl
->dlist
);
925 * vttree is now handled in update_vf() so that update_vf(cl, 0, 0)
926 * needs to be called explicitly to remove a class from vttree.
931 * hack to get length of first packet in queue.
934 qdisc_peek_len(struct Qdisc
*sch
)
939 skb
= sch
->dequeue(sch
);
942 printk("qdisc_peek_len: non work-conserving qdisc ?\n");
946 if (unlikely(sch
->ops
->requeue(skb
, sch
) != NET_XMIT_SUCCESS
)) {
948 printk("qdisc_peek_len: failed to requeue\n");
955 hfsc_purge_queue(struct Qdisc
*sch
, struct hfsc_class
*cl
)
957 unsigned int len
= cl
->qdisc
->q
.qlen
;
959 qdisc_reset(cl
->qdisc
);
968 hfsc_adjust_levels(struct hfsc_class
*cl
)
970 struct hfsc_class
*p
;
975 list_for_each_entry(p
, &cl
->children
, siblings
) {
976 if (p
->level
>= level
)
977 level
= p
->level
+ 1;
980 } while ((cl
= cl
->cl_parent
) != NULL
);
983 static inline unsigned int
989 return h
& (HFSC_HSIZE
- 1);
992 static inline struct hfsc_class
*
993 hfsc_find_class(u32 classid
, struct Qdisc
*sch
)
995 struct hfsc_sched
*q
= qdisc_priv(sch
);
996 struct hfsc_class
*cl
;
998 list_for_each_entry(cl
, &q
->clhash
[hfsc_hash(classid
)], hlist
) {
999 if (cl
->classid
== classid
)
1006 hfsc_change_rsc(struct hfsc_class
*cl
, struct tc_service_curve
*rsc
,
1009 sc2isc(rsc
, &cl
->cl_rsc
);
1010 rtsc_init(&cl
->cl_deadline
, &cl
->cl_rsc
, cur_time
, cl
->cl_cumul
);
1011 cl
->cl_eligible
= cl
->cl_deadline
;
1012 if (cl
->cl_rsc
.sm1
<= cl
->cl_rsc
.sm2
) {
1013 cl
->cl_eligible
.dx
= 0;
1014 cl
->cl_eligible
.dy
= 0;
1016 cl
->cl_flags
|= HFSC_RSC
;
1020 hfsc_change_fsc(struct hfsc_class
*cl
, struct tc_service_curve
*fsc
)
1022 sc2isc(fsc
, &cl
->cl_fsc
);
1023 rtsc_init(&cl
->cl_virtual
, &cl
->cl_fsc
, cl
->cl_vt
, cl
->cl_total
);
1024 cl
->cl_flags
|= HFSC_FSC
;
1028 hfsc_change_usc(struct hfsc_class
*cl
, struct tc_service_curve
*usc
,
1031 sc2isc(usc
, &cl
->cl_usc
);
1032 rtsc_init(&cl
->cl_ulimit
, &cl
->cl_usc
, cur_time
, cl
->cl_total
);
1033 cl
->cl_flags
|= HFSC_USC
;
1037 hfsc_change_class(struct Qdisc
*sch
, u32 classid
, u32 parentid
,
1038 struct rtattr
**tca
, unsigned long *arg
)
1040 struct hfsc_sched
*q
= qdisc_priv(sch
);
1041 struct hfsc_class
*cl
= (struct hfsc_class
*)*arg
;
1042 struct hfsc_class
*parent
= NULL
;
1043 struct rtattr
*opt
= tca
[TCA_OPTIONS
-1];
1044 struct rtattr
*tb
[TCA_HFSC_MAX
];
1045 struct tc_service_curve
*rsc
= NULL
, *fsc
= NULL
, *usc
= NULL
;
1048 if (opt
== NULL
|| rtattr_parse_nested(tb
, TCA_HFSC_MAX
, opt
))
1051 if (tb
[TCA_HFSC_RSC
-1]) {
1052 if (RTA_PAYLOAD(tb
[TCA_HFSC_RSC
-1]) < sizeof(*rsc
))
1054 rsc
= RTA_DATA(tb
[TCA_HFSC_RSC
-1]);
1055 if (rsc
->m1
== 0 && rsc
->m2
== 0)
1059 if (tb
[TCA_HFSC_FSC
-1]) {
1060 if (RTA_PAYLOAD(tb
[TCA_HFSC_FSC
-1]) < sizeof(*fsc
))
1062 fsc
= RTA_DATA(tb
[TCA_HFSC_FSC
-1]);
1063 if (fsc
->m1
== 0 && fsc
->m2
== 0)
1067 if (tb
[TCA_HFSC_USC
-1]) {
1068 if (RTA_PAYLOAD(tb
[TCA_HFSC_USC
-1]) < sizeof(*usc
))
1070 usc
= RTA_DATA(tb
[TCA_HFSC_USC
-1]);
1071 if (usc
->m1
== 0 && usc
->m2
== 0)
1077 if (cl
->cl_parent
&& cl
->cl_parent
->classid
!= parentid
)
1079 if (cl
->cl_parent
== NULL
&& parentid
!= TC_H_ROOT
)
1082 PSCHED_GET_TIME(cur_time
);
1086 hfsc_change_rsc(cl
, rsc
, cur_time
);
1088 hfsc_change_fsc(cl
, fsc
);
1090 hfsc_change_usc(cl
, usc
, cur_time
);
1092 if (cl
->qdisc
->q
.qlen
!= 0) {
1093 if (cl
->cl_flags
& HFSC_RSC
)
1094 update_ed(cl
, qdisc_peek_len(cl
->qdisc
));
1095 if (cl
->cl_flags
& HFSC_FSC
)
1096 update_vf(cl
, 0, cur_time
);
1098 sch_tree_unlock(sch
);
1100 #ifdef CONFIG_NET_ESTIMATOR
1101 if (tca
[TCA_RATE
-1])
1102 gen_replace_estimator(&cl
->bstats
, &cl
->rate_est
,
1103 cl
->stats_lock
, tca
[TCA_RATE
-1]);
1108 if (parentid
== TC_H_ROOT
)
1113 parent
= hfsc_find_class(parentid
, sch
);
1118 if (classid
== 0 || TC_H_MAJ(classid
^ sch
->handle
) != 0)
1120 if (hfsc_find_class(classid
, sch
))
1123 if (rsc
== NULL
&& fsc
== NULL
)
1126 cl
= kmalloc(sizeof(struct hfsc_class
), GFP_KERNEL
);
1129 memset(cl
, 0, sizeof(struct hfsc_class
));
1132 hfsc_change_rsc(cl
, rsc
, 0);
1134 hfsc_change_fsc(cl
, fsc
);
1136 hfsc_change_usc(cl
, usc
, 0);
1139 cl
->classid
= classid
;
1141 cl
->cl_parent
= parent
;
1142 cl
->qdisc
= qdisc_create_dflt(sch
->dev
, &pfifo_qdisc_ops
);
1143 if (cl
->qdisc
== NULL
)
1144 cl
->qdisc
= &noop_qdisc
;
1145 cl
->stats_lock
= &sch
->dev
->queue_lock
;
1146 INIT_LIST_HEAD(&cl
->children
);
1147 cl
->vt_tree
= RB_ROOT
;
1148 cl
->cf_tree
= RB_ROOT
;
1151 list_add_tail(&cl
->hlist
, &q
->clhash
[hfsc_hash(classid
)]);
1152 list_add_tail(&cl
->siblings
, &parent
->children
);
1153 if (parent
->level
== 0)
1154 hfsc_purge_queue(sch
, parent
);
1155 hfsc_adjust_levels(parent
);
1156 cl
->cl_pcvtoff
= parent
->cl_cvtoff
;
1157 sch_tree_unlock(sch
);
1159 #ifdef CONFIG_NET_ESTIMATOR
1160 if (tca
[TCA_RATE
-1])
1161 gen_new_estimator(&cl
->bstats
, &cl
->rate_est
,
1162 cl
->stats_lock
, tca
[TCA_RATE
-1]);
1164 *arg
= (unsigned long)cl
;
1169 hfsc_destroy_filters(struct tcf_proto
**fl
)
1171 struct tcf_proto
*tp
;
1173 while ((tp
= *fl
) != NULL
) {
1180 hfsc_destroy_class(struct Qdisc
*sch
, struct hfsc_class
*cl
)
1182 struct hfsc_sched
*q
= qdisc_priv(sch
);
1184 hfsc_destroy_filters(&cl
->filter_list
);
1185 qdisc_destroy(cl
->qdisc
);
1186 #ifdef CONFIG_NET_ESTIMATOR
1187 gen_kill_estimator(&cl
->bstats
, &cl
->rate_est
);
1194 hfsc_delete_class(struct Qdisc
*sch
, unsigned long arg
)
1196 struct hfsc_sched
*q
= qdisc_priv(sch
);
1197 struct hfsc_class
*cl
= (struct hfsc_class
*)arg
;
1199 if (cl
->level
> 0 || cl
->filter_cnt
> 0 || cl
== &q
->root
)
1204 list_del(&cl
->hlist
);
1205 list_del(&cl
->siblings
);
1206 hfsc_adjust_levels(cl
->cl_parent
);
1207 hfsc_purge_queue(sch
, cl
);
1208 if (--cl
->refcnt
== 0)
1209 hfsc_destroy_class(sch
, cl
);
1211 sch_tree_unlock(sch
);
1215 static struct hfsc_class
*
1216 hfsc_classify(struct sk_buff
*skb
, struct Qdisc
*sch
, int *qerr
)
1218 struct hfsc_sched
*q
= qdisc_priv(sch
);
1219 struct hfsc_class
*cl
;
1220 struct tcf_result res
;
1221 struct tcf_proto
*tcf
;
1224 if (TC_H_MAJ(skb
->priority
^ sch
->handle
) == 0 &&
1225 (cl
= hfsc_find_class(skb
->priority
, sch
)) != NULL
)
1229 *qerr
= NET_XMIT_BYPASS
;
1230 tcf
= q
->root
.filter_list
;
1231 while (tcf
&& (result
= tc_classify(skb
, tcf
, &res
)) >= 0) {
1232 #ifdef CONFIG_NET_CLS_ACT
1236 *qerr
= NET_XMIT_SUCCESS
;
1240 #elif defined(CONFIG_NET_CLS_POLICE)
1241 if (result
== TC_POLICE_SHOT
)
1244 if ((cl
= (struct hfsc_class
*)res
.class) == NULL
) {
1245 if ((cl
= hfsc_find_class(res
.classid
, sch
)) == NULL
)
1246 break; /* filter selected invalid classid */
1250 return cl
; /* hit leaf class */
1252 /* apply inner filter chain */
1253 tcf
= cl
->filter_list
;
1256 /* classification failed, try default class */
1257 cl
= hfsc_find_class(TC_H_MAKE(TC_H_MAJ(sch
->handle
), q
->defcls
), sch
);
1258 if (cl
== NULL
|| cl
->level
> 0)
1265 hfsc_graft_class(struct Qdisc
*sch
, unsigned long arg
, struct Qdisc
*new,
1268 struct hfsc_class
*cl
= (struct hfsc_class
*)arg
;
1275 new = qdisc_create_dflt(sch
->dev
, &pfifo_qdisc_ops
);
1281 hfsc_purge_queue(sch
, cl
);
1282 *old
= xchg(&cl
->qdisc
, new);
1283 sch_tree_unlock(sch
);
1287 static struct Qdisc
*
1288 hfsc_class_leaf(struct Qdisc
*sch
, unsigned long arg
)
1290 struct hfsc_class
*cl
= (struct hfsc_class
*)arg
;
1292 if (cl
!= NULL
&& cl
->level
== 0)
1298 static unsigned long
1299 hfsc_get_class(struct Qdisc
*sch
, u32 classid
)
1301 struct hfsc_class
*cl
= hfsc_find_class(classid
, sch
);
1306 return (unsigned long)cl
;
1310 hfsc_put_class(struct Qdisc
*sch
, unsigned long arg
)
1312 struct hfsc_class
*cl
= (struct hfsc_class
*)arg
;
1314 if (--cl
->refcnt
== 0)
1315 hfsc_destroy_class(sch
, cl
);
1318 static unsigned long
1319 hfsc_bind_tcf(struct Qdisc
*sch
, unsigned long parent
, u32 classid
)
1321 struct hfsc_class
*p
= (struct hfsc_class
*)parent
;
1322 struct hfsc_class
*cl
= hfsc_find_class(classid
, sch
);
1325 if (p
!= NULL
&& p
->level
<= cl
->level
)
1330 return (unsigned long)cl
;
1334 hfsc_unbind_tcf(struct Qdisc
*sch
, unsigned long arg
)
1336 struct hfsc_class
*cl
= (struct hfsc_class
*)arg
;
1341 static struct tcf_proto
**
1342 hfsc_tcf_chain(struct Qdisc
*sch
, unsigned long arg
)
1344 struct hfsc_sched
*q
= qdisc_priv(sch
);
1345 struct hfsc_class
*cl
= (struct hfsc_class
*)arg
;
1350 return &cl
->filter_list
;
1354 hfsc_dump_sc(struct sk_buff
*skb
, int attr
, struct internal_sc
*sc
)
1356 struct tc_service_curve tsc
;
1358 tsc
.m1
= sm2m(sc
->sm1
);
1359 tsc
.d
= dx2d(sc
->dx
);
1360 tsc
.m2
= sm2m(sc
->sm2
);
1361 RTA_PUT(skb
, attr
, sizeof(tsc
), &tsc
);
1370 hfsc_dump_curves(struct sk_buff
*skb
, struct hfsc_class
*cl
)
1372 if ((cl
->cl_flags
& HFSC_RSC
) &&
1373 (hfsc_dump_sc(skb
, TCA_HFSC_RSC
, &cl
->cl_rsc
) < 0))
1374 goto rtattr_failure
;
1376 if ((cl
->cl_flags
& HFSC_FSC
) &&
1377 (hfsc_dump_sc(skb
, TCA_HFSC_FSC
, &cl
->cl_fsc
) < 0))
1378 goto rtattr_failure
;
1380 if ((cl
->cl_flags
& HFSC_USC
) &&
1381 (hfsc_dump_sc(skb
, TCA_HFSC_USC
, &cl
->cl_usc
) < 0))
1382 goto rtattr_failure
;
1391 hfsc_dump_class(struct Qdisc
*sch
, unsigned long arg
, struct sk_buff
*skb
,
1394 struct hfsc_class
*cl
= (struct hfsc_class
*)arg
;
1395 unsigned char *b
= skb
->tail
;
1396 struct rtattr
*rta
= (struct rtattr
*)b
;
1398 tcm
->tcm_parent
= cl
->cl_parent
? cl
->cl_parent
->classid
: TC_H_ROOT
;
1399 tcm
->tcm_handle
= cl
->classid
;
1401 tcm
->tcm_info
= cl
->qdisc
->handle
;
1403 RTA_PUT(skb
, TCA_OPTIONS
, 0, NULL
);
1404 if (hfsc_dump_curves(skb
, cl
) < 0)
1405 goto rtattr_failure
;
1406 rta
->rta_len
= skb
->tail
- b
;
1410 skb_trim(skb
, b
- skb
->data
);
1415 hfsc_dump_class_stats(struct Qdisc
*sch
, unsigned long arg
,
1416 struct gnet_dump
*d
)
1418 struct hfsc_class
*cl
= (struct hfsc_class
*)arg
;
1419 struct tc_hfsc_stats xstats
;
1421 cl
->qstats
.qlen
= cl
->qdisc
->q
.qlen
;
1422 xstats
.level
= cl
->level
;
1423 xstats
.period
= cl
->cl_vtperiod
;
1424 xstats
.work
= cl
->cl_total
;
1425 xstats
.rtwork
= cl
->cl_cumul
;
1427 if (gnet_stats_copy_basic(d
, &cl
->bstats
) < 0 ||
1428 #ifdef CONFIG_NET_ESTIMATOR
1429 gnet_stats_copy_rate_est(d
, &cl
->rate_est
) < 0 ||
1431 gnet_stats_copy_queue(d
, &cl
->qstats
) < 0)
1434 return gnet_stats_copy_app(d
, &xstats
, sizeof(xstats
));
1440 hfsc_walk(struct Qdisc
*sch
, struct qdisc_walker
*arg
)
1442 struct hfsc_sched
*q
= qdisc_priv(sch
);
1443 struct hfsc_class
*cl
;
1449 for (i
= 0; i
< HFSC_HSIZE
; i
++) {
1450 list_for_each_entry(cl
, &q
->clhash
[i
], hlist
) {
1451 if (arg
->count
< arg
->skip
) {
1455 if (arg
->fn(sch
, (unsigned long)cl
, arg
) < 0) {
1465 hfsc_watchdog(unsigned long arg
)
1467 struct Qdisc
*sch
= (struct Qdisc
*)arg
;
1469 sch
->flags
&= ~TCQ_F_THROTTLED
;
1470 netif_schedule(sch
->dev
);
1474 hfsc_schedule_watchdog(struct Qdisc
*sch
, u64 cur_time
)
1476 struct hfsc_sched
*q
= qdisc_priv(sch
);
1477 struct hfsc_class
*cl
;
1481 if ((cl
= eltree_get_minel(q
)) != NULL
)
1482 next_time
= cl
->cl_e
;
1483 if (q
->root
.cl_cfmin
!= 0) {
1484 if (next_time
== 0 || next_time
> q
->root
.cl_cfmin
)
1485 next_time
= q
->root
.cl_cfmin
;
1487 ASSERT(next_time
!= 0);
1488 delay
= next_time
- cur_time
;
1489 delay
= PSCHED_US2JIFFIE(delay
);
1491 sch
->flags
|= TCQ_F_THROTTLED
;
1492 mod_timer(&q
->wd_timer
, jiffies
+ delay
);
1496 hfsc_init_qdisc(struct Qdisc
*sch
, struct rtattr
*opt
)
1498 struct hfsc_sched
*q
= qdisc_priv(sch
);
1499 struct tc_hfsc_qopt
*qopt
;
1502 if (opt
== NULL
|| RTA_PAYLOAD(opt
) < sizeof(*qopt
))
1504 qopt
= RTA_DATA(opt
);
1506 sch
->stats_lock
= &sch
->dev
->queue_lock
;
1508 q
->defcls
= qopt
->defcls
;
1509 for (i
= 0; i
< HFSC_HSIZE
; i
++)
1510 INIT_LIST_HEAD(&q
->clhash
[i
]);
1511 q
->eligible
= RB_ROOT
;
1512 INIT_LIST_HEAD(&q
->droplist
);
1513 skb_queue_head_init(&q
->requeue
);
1516 q
->root
.classid
= sch
->handle
;
1518 q
->root
.qdisc
= qdisc_create_dflt(sch
->dev
, &pfifo_qdisc_ops
);
1519 if (q
->root
.qdisc
== NULL
)
1520 q
->root
.qdisc
= &noop_qdisc
;
1521 q
->root
.stats_lock
= &sch
->dev
->queue_lock
;
1522 INIT_LIST_HEAD(&q
->root
.children
);
1523 q
->root
.vt_tree
= RB_ROOT
;
1524 q
->root
.cf_tree
= RB_ROOT
;
1526 list_add(&q
->root
.hlist
, &q
->clhash
[hfsc_hash(q
->root
.classid
)]);
1528 init_timer(&q
->wd_timer
);
1529 q
->wd_timer
.function
= hfsc_watchdog
;
1530 q
->wd_timer
.data
= (unsigned long)sch
;
1536 hfsc_change_qdisc(struct Qdisc
*sch
, struct rtattr
*opt
)
1538 struct hfsc_sched
*q
= qdisc_priv(sch
);
1539 struct tc_hfsc_qopt
*qopt
;
1541 if (opt
== NULL
|| RTA_PAYLOAD(opt
) < sizeof(*qopt
))
1543 qopt
= RTA_DATA(opt
);
1546 q
->defcls
= qopt
->defcls
;
1547 sch_tree_unlock(sch
);
1553 hfsc_reset_class(struct hfsc_class
*cl
)
1566 cl
->cl_vtperiod
= 0;
1567 cl
->cl_parentperiod
= 0;
1574 cl
->vt_tree
= RB_ROOT
;
1575 cl
->cf_tree
= RB_ROOT
;
1576 qdisc_reset(cl
->qdisc
);
1578 if (cl
->cl_flags
& HFSC_RSC
)
1579 rtsc_init(&cl
->cl_deadline
, &cl
->cl_rsc
, 0, 0);
1580 if (cl
->cl_flags
& HFSC_FSC
)
1581 rtsc_init(&cl
->cl_virtual
, &cl
->cl_fsc
, 0, 0);
1582 if (cl
->cl_flags
& HFSC_USC
)
1583 rtsc_init(&cl
->cl_ulimit
, &cl
->cl_usc
, 0, 0);
1587 hfsc_reset_qdisc(struct Qdisc
*sch
)
1589 struct hfsc_sched
*q
= qdisc_priv(sch
);
1590 struct hfsc_class
*cl
;
1593 for (i
= 0; i
< HFSC_HSIZE
; i
++) {
1594 list_for_each_entry(cl
, &q
->clhash
[i
], hlist
)
1595 hfsc_reset_class(cl
);
1597 __skb_queue_purge(&q
->requeue
);
1598 q
->eligible
= RB_ROOT
;
1599 INIT_LIST_HEAD(&q
->droplist
);
1600 del_timer(&q
->wd_timer
);
1601 sch
->flags
&= ~TCQ_F_THROTTLED
;
1606 hfsc_destroy_qdisc(struct Qdisc
*sch
)
1608 struct hfsc_sched
*q
= qdisc_priv(sch
);
1609 struct hfsc_class
*cl
, *next
;
1612 for (i
= 0; i
< HFSC_HSIZE
; i
++) {
1613 list_for_each_entry_safe(cl
, next
, &q
->clhash
[i
], hlist
)
1614 hfsc_destroy_class(sch
, cl
);
1616 __skb_queue_purge(&q
->requeue
);
1617 del_timer(&q
->wd_timer
);
1621 hfsc_dump_qdisc(struct Qdisc
*sch
, struct sk_buff
*skb
)
1623 struct hfsc_sched
*q
= qdisc_priv(sch
);
1624 unsigned char *b
= skb
->tail
;
1625 struct tc_hfsc_qopt qopt
;
1627 qopt
.defcls
= q
->defcls
;
1628 RTA_PUT(skb
, TCA_OPTIONS
, sizeof(qopt
), &qopt
);
1632 skb_trim(skb
, b
- skb
->data
);
1637 hfsc_enqueue(struct sk_buff
*skb
, struct Qdisc
*sch
)
1639 struct hfsc_class
*cl
;
1643 cl
= hfsc_classify(skb
, sch
, &err
);
1645 if (err
== NET_XMIT_BYPASS
)
1646 sch
->qstats
.drops
++;
1652 err
= cl
->qdisc
->enqueue(skb
, cl
->qdisc
);
1653 if (unlikely(err
!= NET_XMIT_SUCCESS
)) {
1655 sch
->qstats
.drops
++;
1659 if (cl
->qdisc
->q
.qlen
== 1)
1660 set_active(cl
, len
);
1662 cl
->bstats
.packets
++;
1663 cl
->bstats
.bytes
+= len
;
1664 sch
->bstats
.packets
++;
1665 sch
->bstats
.bytes
+= len
;
1668 return NET_XMIT_SUCCESS
;
1671 static struct sk_buff
*
1672 hfsc_dequeue(struct Qdisc
*sch
)
1674 struct hfsc_sched
*q
= qdisc_priv(sch
);
1675 struct hfsc_class
*cl
;
1676 struct sk_buff
*skb
;
1678 unsigned int next_len
;
1681 if (sch
->q
.qlen
== 0)
1683 if ((skb
= __skb_dequeue(&q
->requeue
)))
1686 PSCHED_GET_TIME(cur_time
);
1689 * if there are eligible classes, use real-time criteria.
1690 * find the class with the minimum deadline among
1691 * the eligible classes.
1693 if ((cl
= eltree_get_mindl(q
, cur_time
)) != NULL
) {
1697 * use link-sharing criteria
1698 * get the class with the minimum vt in the hierarchy
1700 cl
= vttree_get_minvt(&q
->root
, cur_time
);
1702 sch
->qstats
.overlimits
++;
1703 hfsc_schedule_watchdog(sch
, cur_time
);
1708 skb
= cl
->qdisc
->dequeue(cl
->qdisc
);
1710 if (net_ratelimit())
1711 printk("HFSC: Non-work-conserving qdisc ?\n");
1715 update_vf(cl
, skb
->len
, cur_time
);
1717 cl
->cl_cumul
+= skb
->len
;
1719 if (cl
->qdisc
->q
.qlen
!= 0) {
1720 if (cl
->cl_flags
& HFSC_RSC
) {
1722 next_len
= qdisc_peek_len(cl
->qdisc
);
1724 update_ed(cl
, next_len
);
1726 update_d(cl
, next_len
);
1729 /* the class becomes passive */
1734 sch
->flags
&= ~TCQ_F_THROTTLED
;
1741 hfsc_requeue(struct sk_buff
*skb
, struct Qdisc
*sch
)
1743 struct hfsc_sched
*q
= qdisc_priv(sch
);
1745 __skb_queue_head(&q
->requeue
, skb
);
1747 sch
->qstats
.requeues
++;
1748 return NET_XMIT_SUCCESS
;
1752 hfsc_drop(struct Qdisc
*sch
)
1754 struct hfsc_sched
*q
= qdisc_priv(sch
);
1755 struct hfsc_class
*cl
;
1758 list_for_each_entry(cl
, &q
->droplist
, dlist
) {
1759 if (cl
->qdisc
->ops
->drop
!= NULL
&&
1760 (len
= cl
->qdisc
->ops
->drop(cl
->qdisc
)) > 0) {
1761 if (cl
->qdisc
->q
.qlen
== 0) {
1762 update_vf(cl
, 0, 0);
1765 list_move_tail(&cl
->dlist
, &q
->droplist
);
1768 sch
->qstats
.drops
++;
1776 static struct Qdisc_class_ops hfsc_class_ops
= {
1777 .change
= hfsc_change_class
,
1778 .delete = hfsc_delete_class
,
1779 .graft
= hfsc_graft_class
,
1780 .leaf
= hfsc_class_leaf
,
1781 .get
= hfsc_get_class
,
1782 .put
= hfsc_put_class
,
1783 .bind_tcf
= hfsc_bind_tcf
,
1784 .unbind_tcf
= hfsc_unbind_tcf
,
1785 .tcf_chain
= hfsc_tcf_chain
,
1786 .dump
= hfsc_dump_class
,
1787 .dump_stats
= hfsc_dump_class_stats
,
1791 static struct Qdisc_ops hfsc_qdisc_ops
= {
1793 .init
= hfsc_init_qdisc
,
1794 .change
= hfsc_change_qdisc
,
1795 .reset
= hfsc_reset_qdisc
,
1796 .destroy
= hfsc_destroy_qdisc
,
1797 .dump
= hfsc_dump_qdisc
,
1798 .enqueue
= hfsc_enqueue
,
1799 .dequeue
= hfsc_dequeue
,
1800 .requeue
= hfsc_requeue
,
1802 .cl_ops
= &hfsc_class_ops
,
1803 .priv_size
= sizeof(struct hfsc_sched
),
1804 .owner
= THIS_MODULE
1810 return register_qdisc(&hfsc_qdisc_ops
);
1816 unregister_qdisc(&hfsc_qdisc_ops
);
1819 MODULE_LICENSE("GPL");
1820 module_init(hfsc_init
);
1821 module_exit(hfsc_cleanup
);