diff options
author | Patrick McHardy <kaber@trash.net> | 2008-07-06 02:22:05 -0400 |
---|---|---|
committer | David S. Miller <davem@davemloft.net> | 2008-07-06 02:22:05 -0400 |
commit | d77fea2eb9206833c7aa1b013044ddeb5225b92c (patch) | |
tree | 716d9994e60b8ed0cf395e98dde7414a8324f161 /net | |
parent | be0d39d52ce35554e856de7e9ea37ac1fa4a7f91 (diff) |
net-sched: sch_cbq: use dynamic class hash helpers
Signed-off-by: Patrick McHardy <kaber@trash.net>
Signed-off-by: David S. Miller <davem@davemloft.net>
Diffstat (limited to 'net')
-rw-r--r-- | net/sched/sch_cbq.c | 112 |
1 files changed, 55 insertions, 57 deletions
diff --git a/net/sched/sch_cbq.c b/net/sched/sch_cbq.c index 2a3c97f7dc63..968b4c73c9c1 100644 --- a/net/sched/sch_cbq.c +++ b/net/sched/sch_cbq.c | |||
@@ -73,11 +73,10 @@ struct cbq_sched_data; | |||
73 | 73 | ||
74 | struct cbq_class | 74 | struct cbq_class |
75 | { | 75 | { |
76 | struct cbq_class *next; /* hash table link */ | 76 | struct Qdisc_class_common common; |
77 | struct cbq_class *next_alive; /* next class with backlog in this priority band */ | 77 | struct cbq_class *next_alive; /* next class with backlog in this priority band */ |
78 | 78 | ||
79 | /* Parameters */ | 79 | /* Parameters */ |
80 | u32 classid; | ||
81 | unsigned char priority; /* class priority */ | 80 | unsigned char priority; /* class priority */ |
82 | unsigned char priority2; /* priority to be used after overlimit */ | 81 | unsigned char priority2; /* priority to be used after overlimit */ |
83 | unsigned char ewma_log; /* time constant for idle time calculation */ | 82 | unsigned char ewma_log; /* time constant for idle time calculation */ |
@@ -144,7 +143,7 @@ struct cbq_class | |||
144 | 143 | ||
145 | struct cbq_sched_data | 144 | struct cbq_sched_data |
146 | { | 145 | { |
147 | struct cbq_class *classes[16]; /* Hash table of all classes */ | 146 | struct Qdisc_class_hash clhash; /* Hash table of all classes */ |
148 | int nclasses[TC_CBQ_MAXPRIO+1]; | 147 | int nclasses[TC_CBQ_MAXPRIO+1]; |
149 | unsigned quanta[TC_CBQ_MAXPRIO+1]; | 148 | unsigned quanta[TC_CBQ_MAXPRIO+1]; |
150 | 149 | ||
@@ -177,23 +176,15 @@ struct cbq_sched_data | |||
177 | 176 | ||
178 | #define L2T(cl,len) qdisc_l2t((cl)->R_tab,len) | 177 | #define L2T(cl,len) qdisc_l2t((cl)->R_tab,len) |
179 | 178 | ||
180 | |||
181 | static __inline__ unsigned cbq_hash(u32 h) | ||
182 | { | ||
183 | h ^= h>>8; | ||
184 | h ^= h>>4; | ||
185 | return h&0xF; | ||
186 | } | ||
187 | |||
188 | static __inline__ struct cbq_class * | 179 | static __inline__ struct cbq_class * |
189 | cbq_class_lookup(struct cbq_sched_data *q, u32 classid) | 180 | cbq_class_lookup(struct cbq_sched_data *q, u32 classid) |
190 | { | 181 | { |
191 | struct cbq_class *cl; | 182 | struct Qdisc_class_common *clc; |
192 | 183 | ||
193 | for (cl = q->classes[cbq_hash(classid)]; cl; cl = cl->next) | 184 | clc = qdisc_class_find(&q->clhash, classid); |
194 | if (cl->classid == classid) | 185 | if (clc == NULL) |
195 | return cl; | 186 | return NULL; |
196 | return NULL; | 187 | return container_of(clc, struct cbq_class, common); |
197 | } | 188 | } |
198 | 189 | ||
199 | #ifdef CONFIG_NET_CLS_ACT | 190 | #ifdef CONFIG_NET_CLS_ACT |
@@ -1071,13 +1062,14 @@ static void cbq_adjust_levels(struct cbq_class *this) | |||
1071 | static void cbq_normalize_quanta(struct cbq_sched_data *q, int prio) | 1062 | static void cbq_normalize_quanta(struct cbq_sched_data *q, int prio) |
1072 | { | 1063 | { |
1073 | struct cbq_class *cl; | 1064 | struct cbq_class *cl; |
1074 | unsigned h; | 1065 | struct hlist_node *n; |
1066 | unsigned int h; | ||
1075 | 1067 | ||
1076 | if (q->quanta[prio] == 0) | 1068 | if (q->quanta[prio] == 0) |
1077 | return; | 1069 | return; |
1078 | 1070 | ||
1079 | for (h=0; h<16; h++) { | 1071 | for (h = 0; h < q->clhash.hashsize; h++) { |
1080 | for (cl = q->classes[h]; cl; cl = cl->next) { | 1072 | hlist_for_each_entry(cl, n, &q->clhash.hash[h], common.hnode) { |
1081 | /* BUGGGG... Beware! This expression suffer of | 1073 | /* BUGGGG... Beware! This expression suffer of |
1082 | arithmetic overflows! | 1074 | arithmetic overflows! |
1083 | */ | 1075 | */ |
@@ -1086,7 +1078,7 @@ static void cbq_normalize_quanta(struct cbq_sched_data *q, int prio) | |||
1086 | q->quanta[prio]; | 1078 | q->quanta[prio]; |
1087 | } | 1079 | } |
1088 | if (cl->quantum <= 0 || cl->quantum>32*cl->qdisc->dev->mtu) { | 1080 | if (cl->quantum <= 0 || cl->quantum>32*cl->qdisc->dev->mtu) { |
1089 | printk(KERN_WARNING "CBQ: class %08x has bad quantum==%ld, repaired.\n", cl->classid, cl->quantum); | 1081 | printk(KERN_WARNING "CBQ: class %08x has bad quantum==%ld, repaired.\n", cl->common.classid, cl->quantum); |
1090 | cl->quantum = cl->qdisc->dev->mtu/2 + 1; | 1082 | cl->quantum = cl->qdisc->dev->mtu/2 + 1; |
1091 | } | 1083 | } |
1092 | } | 1084 | } |
@@ -1114,10 +1106,12 @@ static void cbq_sync_defmap(struct cbq_class *cl) | |||
1114 | if (split->defaults[i]) | 1106 | if (split->defaults[i]) |
1115 | continue; | 1107 | continue; |
1116 | 1108 | ||
1117 | for (h=0; h<16; h++) { | 1109 | for (h = 0; h < q->clhash.hashsize; h++) { |
1110 | struct hlist_node *n; | ||
1118 | struct cbq_class *c; | 1111 | struct cbq_class *c; |
1119 | 1112 | ||
1120 | for (c = q->classes[h]; c; c = c->next) { | 1113 | hlist_for_each_entry(c, n, &q->clhash.hash[h], |
1114 | common.hnode) { | ||
1121 | if (c->split == split && c->level < level && | 1115 | if (c->split == split && c->level < level && |
1122 | c->defmap&(1<<i)) { | 1116 | c->defmap&(1<<i)) { |
1123 | split->defaults[i] = c; | 1117 | split->defaults[i] = c; |
@@ -1135,12 +1129,12 @@ static void cbq_change_defmap(struct cbq_class *cl, u32 splitid, u32 def, u32 ma | |||
1135 | if (splitid == 0) { | 1129 | if (splitid == 0) { |
1136 | if ((split = cl->split) == NULL) | 1130 | if ((split = cl->split) == NULL) |
1137 | return; | 1131 | return; |
1138 | splitid = split->classid; | 1132 | splitid = split->common.classid; |
1139 | } | 1133 | } |
1140 | 1134 | ||
1141 | if (split == NULL || split->classid != splitid) { | 1135 | if (split == NULL || split->common.classid != splitid) { |
1142 | for (split = cl->tparent; split; split = split->tparent) | 1136 | for (split = cl->tparent; split; split = split->tparent) |
1143 | if (split->classid == splitid) | 1137 | if (split->common.classid == splitid) |
1144 | break; | 1138 | break; |
1145 | } | 1139 | } |
1146 | 1140 | ||
@@ -1163,13 +1157,7 @@ static void cbq_unlink_class(struct cbq_class *this) | |||
1163 | struct cbq_class *cl, **clp; | 1157 | struct cbq_class *cl, **clp; |
1164 | struct cbq_sched_data *q = qdisc_priv(this->qdisc); | 1158 | struct cbq_sched_data *q = qdisc_priv(this->qdisc); |
1165 | 1159 | ||
1166 | for (clp = &q->classes[cbq_hash(this->classid)]; (cl = *clp) != NULL; clp = &cl->next) { | 1160 | qdisc_class_hash_remove(&q->clhash, &this->common); |
1167 | if (cl == this) { | ||
1168 | *clp = cl->next; | ||
1169 | cl->next = NULL; | ||
1170 | break; | ||
1171 | } | ||
1172 | } | ||
1173 | 1161 | ||
1174 | if (this->tparent) { | 1162 | if (this->tparent) { |
1175 | clp=&this->sibling; | 1163 | clp=&this->sibling; |
@@ -1195,12 +1183,10 @@ static void cbq_unlink_class(struct cbq_class *this) | |||
1195 | static void cbq_link_class(struct cbq_class *this) | 1183 | static void cbq_link_class(struct cbq_class *this) |
1196 | { | 1184 | { |
1197 | struct cbq_sched_data *q = qdisc_priv(this->qdisc); | 1185 | struct cbq_sched_data *q = qdisc_priv(this->qdisc); |
1198 | unsigned h = cbq_hash(this->classid); | ||
1199 | struct cbq_class *parent = this->tparent; | 1186 | struct cbq_class *parent = this->tparent; |
1200 | 1187 | ||
1201 | this->sibling = this; | 1188 | this->sibling = this; |
1202 | this->next = q->classes[h]; | 1189 | qdisc_class_hash_insert(&q->clhash, &this->common); |
1203 | q->classes[h] = this; | ||
1204 | 1190 | ||
1205 | if (parent == NULL) | 1191 | if (parent == NULL) |
1206 | return; | 1192 | return; |
@@ -1242,6 +1228,7 @@ cbq_reset(struct Qdisc* sch) | |||
1242 | { | 1228 | { |
1243 | struct cbq_sched_data *q = qdisc_priv(sch); | 1229 | struct cbq_sched_data *q = qdisc_priv(sch); |
1244 | struct cbq_class *cl; | 1230 | struct cbq_class *cl; |
1231 | struct hlist_node *n; | ||
1245 | int prio; | 1232 | int prio; |
1246 | unsigned h; | 1233 | unsigned h; |
1247 | 1234 | ||
@@ -1258,8 +1245,8 @@ cbq_reset(struct Qdisc* sch) | |||
1258 | for (prio = 0; prio <= TC_CBQ_MAXPRIO; prio++) | 1245 | for (prio = 0; prio <= TC_CBQ_MAXPRIO; prio++) |
1259 | q->active[prio] = NULL; | 1246 | q->active[prio] = NULL; |
1260 | 1247 | ||
1261 | for (h = 0; h < 16; h++) { | 1248 | for (h = 0; h < q->clhash.hashsize; h++) { |
1262 | for (cl = q->classes[h]; cl; cl = cl->next) { | 1249 | hlist_for_each_entry(cl, n, &q->clhash.hash[h], common.hnode) { |
1263 | qdisc_reset(cl->q); | 1250 | qdisc_reset(cl->q); |
1264 | 1251 | ||
1265 | cl->next_alive = NULL; | 1252 | cl->next_alive = NULL; |
@@ -1406,9 +1393,13 @@ static int cbq_init(struct Qdisc *sch, struct nlattr *opt) | |||
1406 | if ((q->link.R_tab = qdisc_get_rtab(r, tb[TCA_CBQ_RTAB])) == NULL) | 1393 | if ((q->link.R_tab = qdisc_get_rtab(r, tb[TCA_CBQ_RTAB])) == NULL) |
1407 | return -EINVAL; | 1394 | return -EINVAL; |
1408 | 1395 | ||
1396 | err = qdisc_class_hash_init(&q->clhash); | ||
1397 | if (err < 0) | ||
1398 | goto put_rtab; | ||
1399 | |||
1409 | q->link.refcnt = 1; | 1400 | q->link.refcnt = 1; |
1410 | q->link.sibling = &q->link; | 1401 | q->link.sibling = &q->link; |
1411 | q->link.classid = sch->handle; | 1402 | q->link.common.classid = sch->handle; |
1412 | q->link.qdisc = sch; | 1403 | q->link.qdisc = sch; |
1413 | if (!(q->link.q = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops, | 1404 | if (!(q->link.q = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops, |
1414 | sch->handle))) | 1405 | sch->handle))) |
@@ -1441,6 +1432,10 @@ static int cbq_init(struct Qdisc *sch, struct nlattr *opt) | |||
1441 | 1432 | ||
1442 | cbq_addprio(q, &q->link); | 1433 | cbq_addprio(q, &q->link); |
1443 | return 0; | 1434 | return 0; |
1435 | |||
1436 | put_rtab: | ||
1437 | qdisc_put_rtab(q->link.R_tab); | ||
1438 | return err; | ||
1444 | } | 1439 | } |
1445 | 1440 | ||
1446 | static __inline__ int cbq_dump_rate(struct sk_buff *skb, struct cbq_class *cl) | 1441 | static __inline__ int cbq_dump_rate(struct sk_buff *skb, struct cbq_class *cl) |
@@ -1521,7 +1516,7 @@ static __inline__ int cbq_dump_fopt(struct sk_buff *skb, struct cbq_class *cl) | |||
1521 | struct tc_cbq_fopt opt; | 1516 | struct tc_cbq_fopt opt; |
1522 | 1517 | ||
1523 | if (cl->split || cl->defmap) { | 1518 | if (cl->split || cl->defmap) { |
1524 | opt.split = cl->split ? cl->split->classid : 0; | 1519 | opt.split = cl->split ? cl->split->common.classid : 0; |
1525 | opt.defmap = cl->defmap; | 1520 | opt.defmap = cl->defmap; |
1526 | opt.defchange = ~0; | 1521 | opt.defchange = ~0; |
1527 | NLA_PUT(skb, TCA_CBQ_FOPT, sizeof(opt), &opt); | 1522 | NLA_PUT(skb, TCA_CBQ_FOPT, sizeof(opt), &opt); |
@@ -1602,10 +1597,10 @@ cbq_dump_class(struct Qdisc *sch, unsigned long arg, | |||
1602 | struct nlattr *nest; | 1597 | struct nlattr *nest; |
1603 | 1598 | ||
1604 | if (cl->tparent) | 1599 | if (cl->tparent) |
1605 | tcm->tcm_parent = cl->tparent->classid; | 1600 | tcm->tcm_parent = cl->tparent->common.classid; |
1606 | else | 1601 | else |
1607 | tcm->tcm_parent = TC_H_ROOT; | 1602 | tcm->tcm_parent = TC_H_ROOT; |
1608 | tcm->tcm_handle = cl->classid; | 1603 | tcm->tcm_handle = cl->common.classid; |
1609 | tcm->tcm_info = cl->q->handle; | 1604 | tcm->tcm_info = cl->q->handle; |
1610 | 1605 | ||
1611 | nest = nla_nest_start(skb, TCA_OPTIONS); | 1606 | nest = nla_nest_start(skb, TCA_OPTIONS); |
@@ -1650,8 +1645,9 @@ static int cbq_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new, | |||
1650 | 1645 | ||
1651 | if (cl) { | 1646 | if (cl) { |
1652 | if (new == NULL) { | 1647 | if (new == NULL) { |
1653 | if ((new = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops, | 1648 | new = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops, |
1654 | cl->classid)) == NULL) | 1649 | cl->common.classid); |
1650 | if (new == NULL) | ||
1655 | return -ENOBUFS; | 1651 | return -ENOBUFS; |
1656 | } else { | 1652 | } else { |
1657 | #ifdef CONFIG_NET_CLS_ACT | 1653 | #ifdef CONFIG_NET_CLS_ACT |
@@ -1716,6 +1712,7 @@ static void | |||
1716 | cbq_destroy(struct Qdisc* sch) | 1712 | cbq_destroy(struct Qdisc* sch) |
1717 | { | 1713 | { |
1718 | struct cbq_sched_data *q = qdisc_priv(sch); | 1714 | struct cbq_sched_data *q = qdisc_priv(sch); |
1715 | struct hlist_node *n, *next; | ||
1719 | struct cbq_class *cl; | 1716 | struct cbq_class *cl; |
1720 | unsigned h; | 1717 | unsigned h; |
1721 | 1718 | ||
@@ -1727,18 +1724,16 @@ cbq_destroy(struct Qdisc* sch) | |||
1727 | * classes from root to leafs which means that filters can still | 1724 | * classes from root to leafs which means that filters can still |
1728 | * be bound to classes which have been destroyed already. --TGR '04 | 1725 | * be bound to classes which have been destroyed already. --TGR '04 |
1729 | */ | 1726 | */ |
1730 | for (h = 0; h < 16; h++) { | 1727 | for (h = 0; h < q->clhash.hashsize; h++) { |
1731 | for (cl = q->classes[h]; cl; cl = cl->next) | 1728 | hlist_for_each_entry(cl, n, &q->clhash.hash[h], common.hnode) |
1732 | tcf_destroy_chain(&cl->filter_list); | 1729 | tcf_destroy_chain(&cl->filter_list); |
1733 | } | 1730 | } |
1734 | for (h = 0; h < 16; h++) { | 1731 | for (h = 0; h < q->clhash.hashsize; h++) { |
1735 | struct cbq_class *next; | 1732 | hlist_for_each_entry_safe(cl, n, next, &q->clhash.hash[h], |
1736 | 1733 | common.hnode) | |
1737 | for (cl = q->classes[h]; cl; cl = next) { | ||
1738 | next = cl->next; | ||
1739 | cbq_destroy_class(sch, cl); | 1734 | cbq_destroy_class(sch, cl); |
1740 | } | ||
1741 | } | 1735 | } |
1736 | qdisc_class_hash_destroy(&q->clhash); | ||
1742 | } | 1737 | } |
1743 | 1738 | ||
1744 | static void cbq_put(struct Qdisc *sch, unsigned long arg) | 1739 | static void cbq_put(struct Qdisc *sch, unsigned long arg) |
@@ -1781,7 +1776,8 @@ cbq_change_class(struct Qdisc *sch, u32 classid, u32 parentid, struct nlattr **t | |||
1781 | if (cl) { | 1776 | if (cl) { |
1782 | /* Check parent */ | 1777 | /* Check parent */ |
1783 | if (parentid) { | 1778 | if (parentid) { |
1784 | if (cl->tparent && cl->tparent->classid != parentid) | 1779 | if (cl->tparent && |
1780 | cl->tparent->common.classid != parentid) | ||
1785 | return -EINVAL; | 1781 | return -EINVAL; |
1786 | if (!cl->tparent && parentid != TC_H_ROOT) | 1782 | if (!cl->tparent && parentid != TC_H_ROOT) |
1787 | return -EINVAL; | 1783 | return -EINVAL; |
@@ -1883,7 +1879,7 @@ cbq_change_class(struct Qdisc *sch, u32 classid, u32 parentid, struct nlattr **t | |||
1883 | cl->refcnt = 1; | 1879 | cl->refcnt = 1; |
1884 | if (!(cl->q = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops, classid))) | 1880 | if (!(cl->q = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops, classid))) |
1885 | cl->q = &noop_qdisc; | 1881 | cl->q = &noop_qdisc; |
1886 | cl->classid = classid; | 1882 | cl->common.classid = classid; |
1887 | cl->tparent = parent; | 1883 | cl->tparent = parent; |
1888 | cl->qdisc = sch; | 1884 | cl->qdisc = sch; |
1889 | cl->allot = parent->allot; | 1885 | cl->allot = parent->allot; |
@@ -1916,6 +1912,8 @@ cbq_change_class(struct Qdisc *sch, u32 classid, u32 parentid, struct nlattr **t | |||
1916 | cbq_set_fopt(cl, nla_data(tb[TCA_CBQ_FOPT])); | 1912 | cbq_set_fopt(cl, nla_data(tb[TCA_CBQ_FOPT])); |
1917 | sch_tree_unlock(sch); | 1913 | sch_tree_unlock(sch); |
1918 | 1914 | ||
1915 | qdisc_class_hash_grow(sch, &q->clhash); | ||
1916 | |||
1919 | if (tca[TCA_RATE]) | 1917 | if (tca[TCA_RATE]) |
1920 | gen_new_estimator(&cl->bstats, &cl->rate_est, | 1918 | gen_new_estimator(&cl->bstats, &cl->rate_est, |
1921 | &sch->dev->queue_lock, tca[TCA_RATE]); | 1919 | &sch->dev->queue_lock, tca[TCA_RATE]); |
@@ -2008,15 +2006,15 @@ static void cbq_unbind_filter(struct Qdisc *sch, unsigned long arg) | |||
2008 | static void cbq_walk(struct Qdisc *sch, struct qdisc_walker *arg) | 2006 | static void cbq_walk(struct Qdisc *sch, struct qdisc_walker *arg) |
2009 | { | 2007 | { |
2010 | struct cbq_sched_data *q = qdisc_priv(sch); | 2008 | struct cbq_sched_data *q = qdisc_priv(sch); |
2009 | struct cbq_class *cl; | ||
2010 | struct hlist_node *n; | ||
2011 | unsigned h; | 2011 | unsigned h; |
2012 | 2012 | ||
2013 | if (arg->stop) | 2013 | if (arg->stop) |
2014 | return; | 2014 | return; |
2015 | 2015 | ||
2016 | for (h = 0; h < 16; h++) { | 2016 | for (h = 0; h < q->clhash.hashsize; h++) { |
2017 | struct cbq_class *cl; | 2017 | hlist_for_each_entry(cl, n, &q->clhash.hash[h], common.hnode) { |
2018 | |||
2019 | for (cl = q->classes[h]; cl; cl = cl->next) { | ||
2020 | if (arg->count < arg->skip) { | 2018 | if (arg->count < arg->skip) { |
2021 | arg->count++; | 2019 | arg->count++; |
2022 | continue; | 2020 | continue; |