sch_hfsc.c (14f0290ba44de6ed435fea24bba26e7868421c66) sch_hfsc.c (cc7ec456f82da7f89a5b376e613b3ac4311b3e9a)
1/*
2 * Copyright (c) 2003 Patrick McHardy, <kaber@trash.net>
3 *
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.
8 *

--- 67 unchanged lines hidden (view full) ---

76 *
77 * The service curve parameters are converted to the internal
78 * representation. The slope values are scaled to avoid overflow.
79 * the inverse slope values as well as the y-projection of the 1st
80 * segment are kept in order to avoid 64-bit divide operations
81 * that are expensive on 32-bit architectures.
82 */
83
1/*
2 * Copyright (c) 2003 Patrick McHardy, <kaber@trash.net>
3 *
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.
8 *

--- 67 unchanged lines hidden (view full) ---

76 *
77 * The service curve parameters are converted to the internal
78 * representation. The slope values are scaled to avoid overflow.
79 * the inverse slope values as well as the y-projection of the 1st
80 * segment are kept in order to avoid 64-bit divide operations
81 * that are expensive on 32-bit architectures.
82 */
83
84struct internal_sc
85{
84struct internal_sc {
86 u64 sm1; /* scaled slope of the 1st segment */
87 u64 ism1; /* scaled inverse-slope of the 1st segment */
88 u64 dx; /* the x-projection of the 1st segment */
89 u64 dy; /* the y-projection of the 1st segment */
90 u64 sm2; /* scaled slope of the 2nd segment */
91 u64 ism2; /* scaled inverse-slope of the 2nd segment */
92};
93
94/* runtime service curve */
85 u64 sm1; /* scaled slope of the 1st segment */
86 u64 ism1; /* scaled inverse-slope of the 1st segment */
87 u64 dx; /* the x-projection of the 1st segment */
88 u64 dy; /* the y-projection of the 1st segment */
89 u64 sm2; /* scaled slope of the 2nd segment */
90 u64 ism2; /* scaled inverse-slope of the 2nd segment */
91};
92
93/* runtime service curve */
95struct runtime_sc
96{
94struct runtime_sc {
97 u64 x; /* current starting position on x-axis */
98 u64 y; /* current starting position on y-axis */
99 u64 sm1; /* scaled slope of the 1st segment */
100 u64 ism1; /* scaled inverse-slope of the 1st segment */
101 u64 dx; /* the x-projection of the 1st segment */
102 u64 dy; /* the y-projection of the 1st segment */
103 u64 sm2; /* scaled slope of the 2nd segment */
104 u64 ism2; /* scaled inverse-slope of the 2nd segment */
105};
106
95 u64 x; /* current starting position on x-axis */
96 u64 y; /* current starting position on y-axis */
97 u64 sm1; /* scaled slope of the 1st segment */
98 u64 ism1; /* scaled inverse-slope of the 1st segment */
99 u64 dx; /* the x-projection of the 1st segment */
100 u64 dy; /* the y-projection of the 1st segment */
101 u64 sm2; /* scaled slope of the 2nd segment */
102 u64 ism2; /* scaled inverse-slope of the 2nd segment */
103};
104
107enum hfsc_class_flags
108{
105enum hfsc_class_flags {
109 HFSC_RSC = 0x1,
110 HFSC_FSC = 0x2,
111 HFSC_USC = 0x4
112};
113
106 HFSC_RSC = 0x1,
107 HFSC_FSC = 0x2,
108 HFSC_USC = 0x4
109};
110
114struct hfsc_class
115{
111struct hfsc_class {
116 struct Qdisc_class_common cl_common;
117 unsigned int refcnt; /* usage count */
118
119 struct gnet_stats_basic_packed bstats;
120 struct gnet_stats_queue qstats;
121 struct gnet_stats_rate_est rate_est;
122 unsigned int level; /* class level in hierarchy */
123 struct tcf_proto *filter_list; /* filter list */

--- 11 unchanged lines hidden (view full) ---

135 struct rb_root cf_tree; /* active children sorted by cl_f */
136 struct rb_node cf_node; /* parent's cf_heap member */
137 struct list_head dlist; /* drop list member */
138
139 u64 cl_total; /* total work in bytes */
140 u64 cl_cumul; /* cumulative work in bytes done by
141 real-time criteria */
142
112 struct Qdisc_class_common cl_common;
113 unsigned int refcnt; /* usage count */
114
115 struct gnet_stats_basic_packed bstats;
116 struct gnet_stats_queue qstats;
117 struct gnet_stats_rate_est rate_est;
118 unsigned int level; /* class level in hierarchy */
119 struct tcf_proto *filter_list; /* filter list */

--- 11 unchanged lines hidden (view full) ---

131 struct rb_root cf_tree; /* active children sorted by cl_f */
132 struct rb_node cf_node; /* parent's cf_heap member */
133 struct list_head dlist; /* drop list member */
134
135 u64 cl_total; /* total work in bytes */
136 u64 cl_cumul; /* cumulative work in bytes done by
137 real-time criteria */
138
143 u64 cl_d; /* deadline*/
144 u64 cl_e; /* eligible time */
139 u64 cl_d; /* deadline*/
140 u64 cl_e; /* eligible time */
145 u64 cl_vt; /* virtual time */
146 u64 cl_f; /* time when this class will fit for
147 link-sharing, max(myf, cfmin) */
148 u64 cl_myf; /* my fit-time (calculated from this
149 class's own upperlimit curve) */
150 u64 cl_myfadj; /* my fit-time adjustment (to cancel
151 history dependence) */
152 u64 cl_cfmin; /* earliest children's fit-time (used

--- 18 unchanged lines hidden (view full) ---

171 struct runtime_sc cl_ulimit; /* upperlimit curve */
172
173 unsigned long cl_flags; /* which curves are valid */
174 unsigned long cl_vtperiod; /* vt period sequence number */
175 unsigned long cl_parentperiod;/* parent's vt period sequence number*/
176 unsigned long cl_nactive; /* number of active children */
177};
178
141 u64 cl_vt; /* virtual time */
142 u64 cl_f; /* time when this class will fit for
143 link-sharing, max(myf, cfmin) */
144 u64 cl_myf; /* my fit-time (calculated from this
145 class's own upperlimit curve) */
146 u64 cl_myfadj; /* my fit-time adjustment (to cancel
147 history dependence) */
148 u64 cl_cfmin; /* earliest children's fit-time (used

--- 18 unchanged lines hidden (view full) ---

167 struct runtime_sc cl_ulimit; /* upperlimit curve */
168
169 unsigned long cl_flags; /* which curves are valid */
170 unsigned long cl_vtperiod; /* vt period sequence number */
171 unsigned long cl_parentperiod;/* parent's vt period sequence number*/
172 unsigned long cl_nactive; /* number of active children */
173};
174
179struct hfsc_sched
180{
175struct hfsc_sched {
181 u16 defcls; /* default class id */
182 struct hfsc_class root; /* root class */
183 struct Qdisc_class_hash clhash; /* class hash */
184 struct rb_root eligible; /* eligible tree */
185 struct list_head droplist; /* active leaf class list (for
186 dropping) */
187 struct qdisc_watchdog watchdog; /* watchdog timer */
188};

--- 499 unchanged lines hidden (view full) ---

688 if (go_active && cl->cl_nactive++ == 0)
689 go_active = 1;
690 else
691 go_active = 0;
692
693 if (go_active) {
694 n = rb_last(&cl->cl_parent->vt_tree);
695 if (n != NULL) {
176 u16 defcls; /* default class id */
177 struct hfsc_class root; /* root class */
178 struct Qdisc_class_hash clhash; /* class hash */
179 struct rb_root eligible; /* eligible tree */
180 struct list_head droplist; /* active leaf class list (for
181 dropping) */
182 struct qdisc_watchdog watchdog; /* watchdog timer */
183};

--- 499 unchanged lines hidden (view full) ---

683 if (go_active && cl->cl_nactive++ == 0)
684 go_active = 1;
685 else
686 go_active = 0;
687
688 if (go_active) {
689 n = rb_last(&cl->cl_parent->vt_tree);
690 if (n != NULL) {
696 max_cl = rb_entry(n, struct hfsc_class,vt_node);
691 max_cl = rb_entry(n, struct hfsc_class, vt_node);
697 /*
698 * set vt to the average of the min and max
699 * classes. if the parent's period didn't
700 * change, don't decrease vt of the class.
701 */
702 vt = max_cl->cl_vt;
703 if (cl->cl_parent->cl_cvtmin != 0)
704 vt = (cl->cl_parent->cl_cvtmin + vt)/2;

--- 467 unchanged lines hidden (view full) ---

1172 switch (result) {
1173 case TC_ACT_QUEUED:
1174 case TC_ACT_STOLEN:
1175 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
1176 case TC_ACT_SHOT:
1177 return NULL;
1178 }
1179#endif
692 /*
693 * set vt to the average of the min and max
694 * classes. if the parent's period didn't
695 * change, don't decrease vt of the class.
696 */
697 vt = max_cl->cl_vt;
698 if (cl->cl_parent->cl_cvtmin != 0)
699 vt = (cl->cl_parent->cl_cvtmin + vt)/2;

--- 467 unchanged lines hidden (view full) ---

1167 switch (result) {
1168 case TC_ACT_QUEUED:
1169 case TC_ACT_STOLEN:
1170 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
1171 case TC_ACT_SHOT:
1172 return NULL;
1173 }
1174#endif
1180 if ((cl = (struct hfsc_class *)res.class) == NULL) {
1181 if ((cl = hfsc_find_class(res.classid, sch)) == NULL)
1175 cl = (struct hfsc_class *)res.class;
1176 if (!cl) {
1177 cl = hfsc_find_class(res.classid, sch);
1178 if (!cl)
1182 break; /* filter selected invalid classid */
1183 if (cl->level >= head->level)
1184 break; /* filter may only point downwards */
1185 }
1186
1187 if (cl->level == 0)
1188 return cl; /* hit leaf class */
1189

--- 121 unchanged lines hidden (view full) ---

1311 NLA_PUT(skb, attr, sizeof(tsc), &tsc);
1312
1313 return skb->len;
1314
1315 nla_put_failure:
1316 return -1;
1317}
1318
1179 break; /* filter selected invalid classid */
1180 if (cl->level >= head->level)
1181 break; /* filter may only point downwards */
1182 }
1183
1184 if (cl->level == 0)
1185 return cl; /* hit leaf class */
1186

--- 121 unchanged lines hidden (view full) ---

1308 NLA_PUT(skb, attr, sizeof(tsc), &tsc);
1309
1310 return skb->len;
1311
1312 nla_put_failure:
1313 return -1;
1314}
1315
1319static inline int
1316static int
1320hfsc_dump_curves(struct sk_buff *skb, struct hfsc_class *cl)
1321{
1322 if ((cl->cl_flags & HFSC_RSC) &&
1323 (hfsc_dump_sc(skb, TCA_HFSC_RSC, &cl->cl_rsc) < 0))
1324 goto nla_put_failure;
1325
1326 if ((cl->cl_flags & HFSC_FSC) &&
1327 (hfsc_dump_sc(skb, TCA_HFSC_FSC, &cl->cl_fsc) < 0))

--- 87 unchanged lines hidden (view full) ---

1415
1416static void
1417hfsc_schedule_watchdog(struct Qdisc *sch)
1418{
1419 struct hfsc_sched *q = qdisc_priv(sch);
1420 struct hfsc_class *cl;
1421 u64 next_time = 0;
1422
1317hfsc_dump_curves(struct sk_buff *skb, struct hfsc_class *cl)
1318{
1319 if ((cl->cl_flags & HFSC_RSC) &&
1320 (hfsc_dump_sc(skb, TCA_HFSC_RSC, &cl->cl_rsc) < 0))
1321 goto nla_put_failure;
1322
1323 if ((cl->cl_flags & HFSC_FSC) &&
1324 (hfsc_dump_sc(skb, TCA_HFSC_FSC, &cl->cl_fsc) < 0))

--- 87 unchanged lines hidden (view full) ---

1412
1413static void
1414hfsc_schedule_watchdog(struct Qdisc *sch)
1415{
1416 struct hfsc_sched *q = qdisc_priv(sch);
1417 struct hfsc_class *cl;
1418 u64 next_time = 0;
1419
1423 if ((cl = eltree_get_minel(q)) != NULL)
1420 cl = eltree_get_minel(q);
1421 if (cl)
1424 next_time = cl->cl_e;
1425 if (q->root.cl_cfmin != 0) {
1426 if (next_time == 0 || next_time > q->root.cl_cfmin)
1427 next_time = q->root.cl_cfmin;
1428 }
1429 WARN_ON(next_time == 0);
1430 qdisc_watchdog_schedule(&q->watchdog, next_time);
1431}

--- 189 unchanged lines hidden (view full) ---

1621
1622 cur_time = psched_get_time();
1623
1624 /*
1625 * if there are eligible classes, use real-time criteria.
1626 * find the class with the minimum deadline among
1627 * the eligible classes.
1628 */
1422 next_time = cl->cl_e;
1423 if (q->root.cl_cfmin != 0) {
1424 if (next_time == 0 || next_time > q->root.cl_cfmin)
1425 next_time = q->root.cl_cfmin;
1426 }
1427 WARN_ON(next_time == 0);
1428 qdisc_watchdog_schedule(&q->watchdog, next_time);
1429}

--- 189 unchanged lines hidden (view full) ---

1619
1620 cur_time = psched_get_time();
1621
1622 /*
1623 * if there are eligible classes, use real-time criteria.
1624 * find the class with the minimum deadline among
1625 * the eligible classes.
1626 */
1629 if ((cl = eltree_get_mindl(q, cur_time)) != NULL) {
1627 cl = eltree_get_mindl(q, cur_time);
1628 if (cl) {
1630 realtime = 1;
1631 } else {
1632 /*
1633 * use link-sharing criteria
1634 * get the class with the minimum vt in the hierarchy
1635 */
1636 cl = vttree_get_minvt(&q->root, cur_time);
1637 if (cl == NULL) {

--- 108 unchanged lines hidden --- 		1629 realtime = 1;
1630 } else {
1631 /*
1632 * use link-sharing criteria
1633 * get the class with the minimum vt in the hierarchy
1634 */
1635 cl = vttree_get_minvt(&q->root, cur_time);
1636 if (cl == NULL) {

--- 108 unchanged lines hidden ---