aboutsummaryrefslogtreecommitdiffstats
path: root/net/sched/sch_htb.c
diff options
context:
space:
mode:
Diffstat (limited to 'net/sched/sch_htb.c')
-rw-r--r--net/sched/sch_htb.c106
1 files changed, 62 insertions, 44 deletions
diff --git a/net/sched/sch_htb.c b/net/sched/sch_htb.c
index fc12fe6f559..e1429a85091 100644
--- a/net/sched/sch_htb.c
+++ b/net/sched/sch_htb.c
@@ -99,9 +99,10 @@ struct htb_class {
99 struct rb_root feed[TC_HTB_NUMPRIO]; /* feed trees */ 99 struct rb_root feed[TC_HTB_NUMPRIO]; /* feed trees */
100 struct rb_node *ptr[TC_HTB_NUMPRIO]; /* current class ptr */ 100 struct rb_node *ptr[TC_HTB_NUMPRIO]; /* current class ptr */
101 /* When class changes from state 1->2 and disconnects from 101 /* When class changes from state 1->2 and disconnects from
102 parent's feed then we lost ptr value and start from the 102 * parent's feed then we lost ptr value and start from the
103 first child again. Here we store classid of the 103 * first child again. Here we store classid of the
104 last valid ptr (used when ptr is NULL). */ 104 * last valid ptr (used when ptr is NULL).
105 */
105 u32 last_ptr_id[TC_HTB_NUMPRIO]; 106 u32 last_ptr_id[TC_HTB_NUMPRIO];
106 } inner; 107 } inner;
107 } un; 108 } un;
@@ -185,7 +186,7 @@ static inline struct htb_class *htb_find(u32 handle, struct Qdisc *sch)
185 * have no valid leaf we try to use MAJOR:default leaf. It still unsuccessfull 186 * have no valid leaf we try to use MAJOR:default leaf. It still unsuccessfull
186 * then finish and return direct queue. 187 * then finish and return direct queue.
187 */ 188 */
188#define HTB_DIRECT (struct htb_class*)-1 189#define HTB_DIRECT ((struct htb_class *)-1L)
189 190
190static struct htb_class *htb_classify(struct sk_buff *skb, struct Qdisc *sch, 191static struct htb_class *htb_classify(struct sk_buff *skb, struct Qdisc *sch,
191 int *qerr) 192 int *qerr)
@@ -197,11 +198,13 @@ static struct htb_class *htb_classify(struct sk_buff *skb, struct Qdisc *sch,
197 int result; 198 int result;
198 199
199 /* allow to select class by setting skb->priority to valid classid; 200 /* allow to select class by setting skb->priority to valid classid;
200 note that nfmark can be used too by attaching filter fw with no 201 * note that nfmark can be used too by attaching filter fw with no
201 rules in it */ 202 * rules in it
203 */
202 if (skb->priority == sch->handle) 204 if (skb->priority == sch->handle)
203 return HTB_DIRECT; /* X:0 (direct flow) selected */ 205 return HTB_DIRECT; /* X:0 (direct flow) selected */
204 if ((cl = htb_find(skb->priority, sch)) != NULL && cl->level == 0) 206 cl = htb_find(skb->priority, sch);
207 if (cl && cl->level == 0)
205 return cl; 208 return cl;
206 209
207 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS; 210 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
@@ -216,10 +219,12 @@ static struct htb_class *htb_classify(struct sk_buff *skb, struct Qdisc *sch,
216 return NULL; 219 return NULL;
217 } 220 }
218#endif 221#endif
219 if ((cl = (void *)res.class) == NULL) { 222 cl = (void *)res.class;
223 if (!cl) {
220 if (res.classid == sch->handle) 224 if (res.classid == sch->handle)
221 return HTB_DIRECT; /* X:0 (direct flow) */ 225 return HTB_DIRECT; /* X:0 (direct flow) */
222 if ((cl = htb_find(res.classid, sch)) == NULL) 226 cl = htb_find(res.classid, sch);
227 if (!cl)
223 break; /* filter selected invalid classid */ 228 break; /* filter selected invalid classid */
224 } 229 }
225 if (!cl->level) 230 if (!cl->level)
@@ -378,7 +383,8 @@ static void htb_activate_prios(struct htb_sched *q, struct htb_class *cl)
378 383
379 if (p->un.inner.feed[prio].rb_node) 384 if (p->un.inner.feed[prio].rb_node)
380 /* parent already has its feed in use so that 385 /* parent already has its feed in use so that
381 reset bit in mask as parent is already ok */ 386 * reset bit in mask as parent is already ok
387 */
382 mask &= ~(1 << prio); 388 mask &= ~(1 << prio);
383 389
384 htb_add_to_id_tree(p->un.inner.feed + prio, cl, prio); 390 htb_add_to_id_tree(p->un.inner.feed + prio, cl, prio);
@@ -413,8 +419,9 @@ static void htb_deactivate_prios(struct htb_sched *q, struct htb_class *cl)
413 419
414 if (p->un.inner.ptr[prio] == cl->node + prio) { 420 if (p->un.inner.ptr[prio] == cl->node + prio) {
415 /* we are removing child which is pointed to from 421 /* we are removing child which is pointed to from
416 parent feed - forget the pointer but remember 422 * parent feed - forget the pointer but remember
417 classid */ 423 * classid
424 */
418 p->un.inner.last_ptr_id[prio] = cl->common.classid; 425 p->un.inner.last_ptr_id[prio] = cl->common.classid;
419 p->un.inner.ptr[prio] = NULL; 426 p->un.inner.ptr[prio] = NULL;
420 } 427 }
@@ -663,8 +670,9 @@ static psched_time_t htb_do_events(struct htb_sched *q, int level,
663 unsigned long start) 670 unsigned long start)
664{ 671{
665 /* don't run for longer than 2 jiffies; 2 is used instead of 672 /* don't run for longer than 2 jiffies; 2 is used instead of
666 1 to simplify things when jiffy is going to be incremented 673 * 1 to simplify things when jiffy is going to be incremented
667 too soon */ 674 * too soon
675 */
668 unsigned long stop_at = start + 2; 676 unsigned long stop_at = start + 2;
669 while (time_before(jiffies, stop_at)) { 677 while (time_before(jiffies, stop_at)) {
670 struct htb_class *cl; 678 struct htb_class *cl;
@@ -687,7 +695,7 @@ static psched_time_t htb_do_events(struct htb_sched *q, int level,
687 695
688 /* too much load - let's continue after a break for scheduling */ 696 /* too much load - let's continue after a break for scheduling */
689 if (!(q->warned & HTB_WARN_TOOMANYEVENTS)) { 697 if (!(q->warned & HTB_WARN_TOOMANYEVENTS)) {
690 printk(KERN_WARNING "htb: too many events!\n"); 698 pr_warning("htb: too many events!\n");
691 q->warned |= HTB_WARN_TOOMANYEVENTS; 699 q->warned |= HTB_WARN_TOOMANYEVENTS;
692 } 700 }
693 701
@@ -695,7 +703,8 @@ static psched_time_t htb_do_events(struct htb_sched *q, int level,
695} 703}
696 704
697/* Returns class->node+prio from id-tree where classe's id is >= id. NULL 705/* Returns class->node+prio from id-tree where classe's id is >= id. NULL
698 is no such one exists. */ 706 * is no such one exists.
707 */
699static struct rb_node *htb_id_find_next_upper(int prio, struct rb_node *n, 708static struct rb_node *htb_id_find_next_upper(int prio, struct rb_node *n,
700 u32 id) 709 u32 id)
701{ 710{
@@ -739,12 +748,14 @@ static struct htb_class *htb_lookup_leaf(struct rb_root *tree, int prio,
739 for (i = 0; i < 65535; i++) { 748 for (i = 0; i < 65535; i++) {
740 if (!*sp->pptr && *sp->pid) { 749 if (!*sp->pptr && *sp->pid) {
741 /* ptr was invalidated but id is valid - try to recover 750 /* ptr was invalidated but id is valid - try to recover
742 the original or next ptr */ 751 * the original or next ptr
752 */
743 *sp->pptr = 753 *sp->pptr =
744 htb_id_find_next_upper(prio, sp->root, *sp->pid); 754 htb_id_find_next_upper(prio, sp->root, *sp->pid);
745 } 755 }
746 *sp->pid = 0; /* ptr is valid now so that remove this hint as it 756 *sp->pid = 0; /* ptr is valid now so that remove this hint as it
747 can become out of date quickly */ 757 * can become out of date quickly
758 */
748 if (!*sp->pptr) { /* we are at right end; rewind & go up */ 759 if (!*sp->pptr) { /* we are at right end; rewind & go up */
749 *sp->pptr = sp->root; 760 *sp->pptr = sp->root;
750 while ((*sp->pptr)->rb_left) 761 while ((*sp->pptr)->rb_left)
@@ -772,7 +783,8 @@ static struct htb_class *htb_lookup_leaf(struct rb_root *tree, int prio,
772} 783}
773 784
774/* dequeues packet at given priority and level; call only if 785/* dequeues packet at given priority and level; call only if
775 you are sure that there is active class at prio/level */ 786 * you are sure that there is active class at prio/level
787 */
776static struct sk_buff *htb_dequeue_tree(struct htb_sched *q, int prio, 788static struct sk_buff *htb_dequeue_tree(struct htb_sched *q, int prio,
777 int level) 789 int level)
778{ 790{
@@ -789,9 +801,10 @@ next:
789 return NULL; 801 return NULL;
790 802
791 /* class can be empty - it is unlikely but can be true if leaf 803 /* class can be empty - it is unlikely but can be true if leaf
792 qdisc drops packets in enqueue routine or if someone used 804 * qdisc drops packets in enqueue routine or if someone used
793 graft operation on the leaf since last dequeue; 805 * graft operation on the leaf since last dequeue;
794 simply deactivate and skip such class */ 806 * simply deactivate and skip such class
807 */
795 if (unlikely(cl->un.leaf.q->q.qlen == 0)) { 808 if (unlikely(cl->un.leaf.q->q.qlen == 0)) {
796 struct htb_class *next; 809 struct htb_class *next;
797 htb_deactivate(q, cl); 810 htb_deactivate(q, cl);
@@ -831,7 +844,8 @@ next:
831 ptr[0]) + prio); 844 ptr[0]) + prio);
832 } 845 }
833 /* this used to be after charge_class but this constelation 846 /* this used to be after charge_class but this constelation
834 gives us slightly better performance */ 847 * gives us slightly better performance
848 */
835 if (!cl->un.leaf.q->q.qlen) 849 if (!cl->un.leaf.q->q.qlen)
836 htb_deactivate(q, cl); 850 htb_deactivate(q, cl);
837 htb_charge_class(q, cl, level, skb); 851 htb_charge_class(q, cl, level, skb);
@@ -852,7 +866,7 @@ static struct sk_buff *htb_dequeue(struct Qdisc *sch)
852 if (skb != NULL) { 866 if (skb != NULL) {
853ok: 867ok:
854 qdisc_bstats_update(sch, skb); 868 qdisc_bstats_update(sch, skb);
855 sch->flags &= ~TCQ_F_THROTTLED; 869 qdisc_unthrottled(sch);
856 sch->q.qlen--; 870 sch->q.qlen--;
857 return skb; 871 return skb;
858 } 872 }
@@ -883,6 +897,7 @@ ok:
883 m = ~q->row_mask[level]; 897 m = ~q->row_mask[level];
884 while (m != (int)(-1)) { 898 while (m != (int)(-1)) {
885 int prio = ffz(m); 899 int prio = ffz(m);
900
886 m |= 1 << prio; 901 m |= 1 << prio;
887 skb = htb_dequeue_tree(q, prio, level); 902 skb = htb_dequeue_tree(q, prio, level);
888 if (likely(skb != NULL)) 903 if (likely(skb != NULL))
@@ -987,13 +1002,12 @@ static int htb_init(struct Qdisc *sch, struct nlattr *opt)
987 return err; 1002 return err;
988 1003
989 if (tb[TCA_HTB_INIT] == NULL) { 1004 if (tb[TCA_HTB_INIT] == NULL) {
990 printk(KERN_ERR "HTB: hey probably you have bad tc tool ?\n"); 1005 pr_err("HTB: hey probably you have bad tc tool ?\n");
991 return -EINVAL; 1006 return -EINVAL;
992 } 1007 }
993 gopt = nla_data(tb[TCA_HTB_INIT]); 1008 gopt = nla_data(tb[TCA_HTB_INIT]);
994 if (gopt->version != HTB_VER >> 16) { 1009 if (gopt->version != HTB_VER >> 16) {
995 printk(KERN_ERR 1010 pr_err("HTB: need tc/htb version %d (minor is %d), you have %d\n",
996 "HTB: need tc/htb version %d (minor is %d), you have %d\n",
997 HTB_VER >> 16, HTB_VER & 0xffff, gopt->version); 1011 HTB_VER >> 16, HTB_VER & 0xffff, gopt->version);
998 return -EINVAL; 1012 return -EINVAL;
999 } 1013 }
@@ -1206,9 +1220,10 @@ static void htb_destroy(struct Qdisc *sch)
1206 cancel_work_sync(&q->work); 1220 cancel_work_sync(&q->work);
1207 qdisc_watchdog_cancel(&q->watchdog); 1221 qdisc_watchdog_cancel(&q->watchdog);
1208 /* This line used to be after htb_destroy_class call below 1222 /* This line used to be after htb_destroy_class call below
1209 and surprisingly it worked in 2.4. But it must precede it 1223 * and surprisingly it worked in 2.4. But it must precede it
1210 because filter need its target class alive to be able to call 1224 * because filter need its target class alive to be able to call
1211 unbind_filter on it (without Oops). */ 1225 * unbind_filter on it (without Oops).
1226 */
1212 tcf_destroy_chain(&q->filter_list); 1227 tcf_destroy_chain(&q->filter_list);
1213 1228
1214 for (i = 0; i < q->clhash.hashsize; i++) { 1229 for (i = 0; i < q->clhash.hashsize; i++) {
@@ -1342,11 +1357,12 @@ static int htb_change_class(struct Qdisc *sch, u32 classid,
1342 1357
1343 /* check maximal depth */ 1358 /* check maximal depth */
1344 if (parent && parent->parent && parent->parent->level < 2) { 1359 if (parent && parent->parent && parent->parent->level < 2) {
1345 printk(KERN_ERR "htb: tree is too deep\n"); 1360 pr_err("htb: tree is too deep\n");
1346 goto failure; 1361 goto failure;
1347 } 1362 }
1348 err = -ENOBUFS; 1363 err = -ENOBUFS;
1349 if ((cl = kzalloc(sizeof(*cl), GFP_KERNEL)) == NULL) 1364 cl = kzalloc(sizeof(*cl), GFP_KERNEL);
1365 if (!cl)
1350 goto failure; 1366 goto failure;
1351 1367
1352 err = gen_new_estimator(&cl->bstats, &cl->rate_est, 1368 err = gen_new_estimator(&cl->bstats, &cl->rate_est,
@@ -1366,8 +1382,9 @@ static int htb_change_class(struct Qdisc *sch, u32 classid,
1366 RB_CLEAR_NODE(&cl->node[prio]); 1382 RB_CLEAR_NODE(&cl->node[prio]);
1367 1383
1368 /* create leaf qdisc early because it uses kmalloc(GFP_KERNEL) 1384 /* create leaf qdisc early because it uses kmalloc(GFP_KERNEL)
1369 so that can't be used inside of sch_tree_lock 1385 * so that can't be used inside of sch_tree_lock
1370 -- thanks to Karlis Peisenieks */ 1386 * -- thanks to Karlis Peisenieks
1387 */
1371 new_q = qdisc_create_dflt(sch->dev_queue, 1388 new_q = qdisc_create_dflt(sch->dev_queue,
1372 &pfifo_qdisc_ops, classid); 1389 &pfifo_qdisc_ops, classid);
1373 sch_tree_lock(sch); 1390 sch_tree_lock(sch);
@@ -1419,17 +1436,18 @@ static int htb_change_class(struct Qdisc *sch, u32 classid,
1419 } 1436 }
1420 1437
1421 /* it used to be a nasty bug here, we have to check that node 1438 /* it used to be a nasty bug here, we have to check that node
1422 is really leaf before changing cl->un.leaf ! */ 1439 * is really leaf before changing cl->un.leaf !
1440 */
1423 if (!cl->level) { 1441 if (!cl->level) {
1424 cl->quantum = rtab->rate.rate / q->rate2quantum; 1442 cl->quantum = rtab->rate.rate / q->rate2quantum;
1425 if (!hopt->quantum && cl->quantum < 1000) { 1443 if (!hopt->quantum && cl->quantum < 1000) {
1426 printk(KERN_WARNING 1444 pr_warning(
1427 "HTB: quantum of class %X is small. Consider r2q change.\n", 1445 "HTB: quantum of class %X is small. Consider r2q change.\n",
1428 cl->common.classid); 1446 cl->common.classid);
1429 cl->quantum = 1000; 1447 cl->quantum = 1000;
1430 } 1448 }
1431 if (!hopt->quantum && cl->quantum > 200000) { 1449 if (!hopt->quantum && cl->quantum > 200000) {
1432 printk(KERN_WARNING 1450 pr_warning(
1433 "HTB: quantum of class %X is big. Consider r2q change.\n", 1451 "HTB: quantum of class %X is big. Consider r2q change.\n",
1434 cl->common.classid); 1452 cl->common.classid);
1435 cl->quantum = 200000; 1453 cl->quantum = 200000;
@@ -1478,13 +1496,13 @@ static unsigned long htb_bind_filter(struct Qdisc *sch, unsigned long parent,
1478 struct htb_class *cl = htb_find(classid, sch); 1496 struct htb_class *cl = htb_find(classid, sch);
1479 1497
1480 /*if (cl && !cl->level) return 0; 1498 /*if (cl && !cl->level) return 0;
1481 The line above used to be there to prevent attaching filters to 1499 * The line above used to be there to prevent attaching filters to
1482 leaves. But at least tc_index filter uses this just to get class 1500 * leaves. But at least tc_index filter uses this just to get class
1483 for other reasons so that we have to allow for it. 1501 * for other reasons so that we have to allow for it.
1484 ---- 1502 * ----
1485 19.6.2002 As Werner explained it is ok - bind filter is just 1503 * 19.6.2002 As Werner explained it is ok - bind filter is just
1486 another way to "lock" the class - unlike "get" this lock can 1504 * another way to "lock" the class - unlike "get" this lock can
1487 be broken by class during destroy IIUC. 1505 * be broken by class during destroy IIUC.
1488 */ 1506 */
1489 if (cl) 1507 if (cl)
1490 cl->filter_cnt++; 1508 cl->filter_cnt++;