aboutsummaryrefslogtreecommitdiffstats
path: root/net
diff options
context:
space:
mode:
authorPatrick McHardy <kaber@trash.net>2008-07-06 02:22:05 -0400
committerDavid S. Miller <davem@davemloft.net>2008-07-06 02:22:05 -0400
commitd77fea2eb9206833c7aa1b013044ddeb5225b92c (patch)
tree716d9994e60b8ed0cf395e98dde7414a8324f161 /net
parentbe0d39d52ce35554e856de7e9ea37ac1fa4a7f91 (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.c112
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
74struct cbq_class 74struct 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
145struct cbq_sched_data 144struct 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
181static __inline__ unsigned cbq_hash(u32 h)
182{
183 h ^= h>>8;
184 h ^= h>>4;
185 return h&0xF;
186}
187
188static __inline__ struct cbq_class * 179static __inline__ struct cbq_class *
189cbq_class_lookup(struct cbq_sched_data *q, u32 classid) 180cbq_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)
1071static void cbq_normalize_quanta(struct cbq_sched_data *q, int prio) 1062static 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)
1195static void cbq_link_class(struct cbq_class *this) 1183static 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
1436put_rtab:
1437 qdisc_put_rtab(q->link.R_tab);
1438 return err;
1444} 1439}
1445 1440
1446static __inline__ int cbq_dump_rate(struct sk_buff *skb, struct cbq_class *cl) 1441static __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
1716cbq_destroy(struct Qdisc* sch) 1712cbq_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
1744static void cbq_put(struct Qdisc *sch, unsigned long arg) 1739static 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)
2008static void cbq_walk(struct Qdisc *sch, struct qdisc_walker *arg) 2006static 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;