--- sch_htb.c 2003/01/11 21:31:31 1.16 +++ sch_htb.c 2003/03/20 14:08:36 @@ -19,7 +19,7 @@ * created test case so that I was able to fix nasty bug * and many others. thanks. * - * $Id: sch_htb.c,v 1.16 2003/01/11 21:31:31 devik Exp $ + * $Id: sch_htb.c,v 1.19 2003/03/20 12:13:14 devik Exp devik $ */ #include #include @@ -71,16 +71,12 @@ #define HTB_HYSTERESIS 1/* whether to use mode hysteresis for speedup */ #define HTB_QLOCK(S) spin_lock_bh(&(S)->dev->queue_lock) #define HTB_QUNLOCK(S) spin_unlock_bh(&(S)->dev->queue_lock) -#define HTB_VER 0x30008 /* major must be matched with number suplied by TC as version */ +#define HTB_VER 0x3000c /* major must be matched with number suplied by TC as version */ #if HTB_VER >> 16 != TC_HTB_PROTOVER #error "Mismatched sch_htb.c and pkt_sch.h" #endif -/* temporary debug defines to be removed after beta stage */ -#define DEVIK_MEND(N) -#define DEVIK_MSTART(N) - /* debugging support; S is subsystem, these are defined: 0 - netlink messages 1 - enqueue @@ -219,6 +215,9 @@ /* time of nearest event per level (row) */ unsigned long near_ev_cache[TC_HTB_MAXDEPTH]; + /* cached value of jiffies in dequeue */ + unsigned long jiffies; + /* whether we hit non-work conserving class during this dequeue; we use */ int nwc_hit; /* this to disable mindelay complaint in dequeue */ @@ -338,7 +337,7 @@ static void htb_debug_dump (struct htb_sched *q) { int i,p; - printk(KERN_DEBUG "htb*g j=%lu\n",jiffies); + printk(KERN_DEBUG "htb*g j=%lu lj=%lu\n",jiffies,q->jiffies); /* rows */ for (i=TC_HTB_MAXDEPTH-1;i>=0;i--) { printk(KERN_DEBUG "htb*r%d m=%x",i,q->row_mask[i]); @@ -421,9 +420,8 @@ if ((delay <= 0 || delay > cl->mbuffer) && net_ratelimit()) printk(KERN_ERR "HTB: suspicious delay in wait_tree d=%ld cl=%X h=%d\n",delay,cl->classid,debug_hint); #endif - DEVIK_MSTART(9); - cl->pq_key = jiffies + PSCHED_US2JIFFIE(delay); - if (cl->pq_key == jiffies) + cl->pq_key = q->jiffies + PSCHED_US2JIFFIE(delay); + if (cl->pq_key == q->jiffies) cl->pq_key++; /* update the nearest event cache */ @@ -440,7 +438,6 @@ } rb_link_node(&cl->pq_node, parent, p); rb_insert_color(&cl->pq_node, &q->wait_pq[cl->level]); - DEVIK_MEND(9); } /** @@ -689,7 +686,6 @@ struct htb_sched *q = (struct htb_sched *)sch->data; struct htb_class *cl = htb_classify(skb,sch); - DEVIK_MSTART(0); if (cl == HTB_DIRECT || !cl) { /* enqueue to helper queue */ if (q->direct_queue.qlen < q->direct_qlen && cl) { @@ -698,25 +694,20 @@ } else { kfree_skb (skb); sch->stats.drops++; - DEVIK_MEND(0); return NET_XMIT_DROP; } } else if (cl->un.leaf.q->enqueue(skb, cl->un.leaf.q) != NET_XMIT_SUCCESS) { sch->stats.drops++; cl->stats.drops++; - DEVIK_MEND(0); return NET_XMIT_DROP; } else { cl->stats.packets++; cl->stats.bytes += skb->len; - DEVIK_MSTART(1); htb_activate (q,cl); - DEVIK_MEND(1); } sch->q.qlen++; sch->stats.packets++; sch->stats.bytes += skb->len; HTB_DBG(1,1,"htb_enq_ok cl=%X skb=%p\n",cl?cl->classid:0,skb); - DEVIK_MEND(0); return NET_XMIT_SUCCESS; } @@ -819,7 +810,7 @@ cl->classid, diff, (unsigned long long) q->now, (unsigned long long) cl->t_c, - jiffies); + q->jiffies); diff = 1000; } #endif @@ -862,6 +853,7 @@ * * Scans event queue for pending events and applies them. Returns jiffies to * next pending event (0 for no event in pq). + * Note: Aplied are events whose have cl->pq_key <= jiffies. */ static long htb_do_events(struct htb_sched *q,int level) { @@ -876,9 +868,9 @@ while (p->rb_left) p = p->rb_left; cl = rb_entry(p, struct htb_class, pq_node); - if (cl->pq_key - (jiffies+1) < 0x80000000) { - HTB_DBG(8,3,"htb_do_ev_ret delay=%ld\n",cl->pq_key - jiffies); - return cl->pq_key - jiffies; + if (cl->pq_key - (q->jiffies+1) < 0x80000000) { + HTB_DBG(8,3,"htb_do_ev_ret delay=%ld\n",cl->pq_key - q->jiffies); + return cl->pq_key - q->jiffies; } htb_safe_rb_erase(p,q->wait_pq+level); diff = PSCHED_TDIFF_SAFE(q->now, cl->t_c, (u32)cl->mbuffer, 0); @@ -889,7 +881,7 @@ cl->classid, diff, (unsigned long long) q->now, (unsigned long long) cl->t_c, - jiffies); + q->jiffies); diff = 1000; } #endif @@ -952,7 +944,6 @@ //struct htb_sched *q = (struct htb_sched *)sch->data; struct htb_class *cl,*start; /* look initial class up in the row */ - DEVIK_MSTART(6); start = cl = htb_lookup_leaf (q->row[level]+prio,prio,q->ptr[level]+prio); do { @@ -971,8 +962,6 @@ cl = htb_lookup_leaf (q->row[level]+prio,prio,q->ptr[level]+prio); } while (cl != start); - DEVIK_MEND(6); - DEVIK_MSTART(7); if (likely(skb != NULL)) { if ((cl->un.leaf.deficit[level] -= skb->len) < 0) { HTB_DBG(4,2,"htb_next_cl oldptr=%p quant_add=%d\n", @@ -984,11 +973,8 @@ gives us slightly better performance */ if (!cl->un.leaf.q->q.qlen) htb_deactivate (q,cl); - DEVIK_MSTART(8); htb_charge_class (q,cl,level,skb->len); - DEVIK_MEND(8); } - DEVIK_MEND(7); return skb; } @@ -1003,7 +989,8 @@ delay = 5*HZ; } del_timer(&q->timer); - q->timer.expires = jiffies + delay; + /* why don't use jiffies here ? because expires can be in past */ + q->timer.expires = q->jiffies + delay; add_timer(&q->timer); sch->flags |= TCQ_F_THROTTLED; sch->stats.overlimits++; @@ -1016,7 +1003,11 @@ struct htb_sched *q = (struct htb_sched *)sch->data; int level; long min_delay; +#ifdef HTB_DEBUG + int evs_used = 0; +#endif + q->jiffies = jiffies; HTB_DBG(3,1,"htb_deq dircnt=%d qlen=%d\n",skb_queue_len(&q->direct_queue), sch->q.qlen); @@ -1027,7 +1018,6 @@ return skb; } - DEVIK_MSTART(2); if (!sch->q.qlen) goto fin; PSCHED_GET_TIME(q->now); @@ -1037,17 +1027,17 @@ /* common case optimization - skip event handler quickly */ int m; long delay; - DEVIK_MSTART(3); - if (jiffies - q->near_ev_cache[level] < 0x80000000 || 0) { + if (q->jiffies - q->near_ev_cache[level] < 0x80000000 || 0) { delay = htb_do_events(q,level); - q->near_ev_cache[level] += delay ? delay : HZ; + q->near_ev_cache[level] = q->jiffies + (delay ? delay : HZ); +#ifdef HTB_DEBUG + evs_used++; +#endif } else - delay = q->near_ev_cache[level] - jiffies; + delay = q->near_ev_cache[level] - q->jiffies; if (delay && min_delay > delay) min_delay = delay; - DEVIK_MEND(3); - DEVIK_MSTART(5); m = ~q->row_mask[level]; while (m != (int)(-1)) { int prio = ffz (m); @@ -1056,29 +1046,24 @@ if (likely(skb != NULL)) { sch->q.qlen--; sch->flags &= ~TCQ_F_THROTTLED; - DEVIK_MEND(5); goto fin; } } - DEVIK_MEND(5); } - DEVIK_MSTART(4); #ifdef HTB_DEBUG if (!q->nwc_hit && min_delay >= 10*HZ && net_ratelimit()) { - if (min_delay == LONG_MAX) - printk(KERN_ERR "HTB: dequeue bug, report it please !\n"); - else { + if (min_delay == LONG_MAX) { + printk(KERN_ERR "HTB: dequeue bug (%d,%lu,%lu), report it please !\n", + evs_used,q->jiffies,jiffies); + htb_debug_dump(q); + } else printk(KERN_WARNING "HTB: mindelay=%ld, some class has " "too small rate\n",min_delay); - htb_debug_dump(q); - } } #endif htb_delay_by (sch,min_delay > 5*HZ ? 5*HZ : min_delay); - DEVIK_MEND(4); fin: - HTB_DBG(3,1,"htb_deq_end %s j=%lu skb=%p\n",sch->dev->name,jiffies,skb); - DEVIK_MEND(2); + HTB_DBG(3,1,"htb_deq_end %s j=%lu skb=%p\n",sch->dev->name,q->jiffies,skb); return skb; } @@ -1449,6 +1434,7 @@ if (!rtab || !ctab) goto failure; if (!cl) { /* new class */ + struct Qdisc *new_q; /* check for valid classid */ if (!classid || TC_H_MAJ(classid^sch->handle) || htb_find(classid,sch)) goto failure; @@ -1472,6 +1458,10 @@ cl->magic = HTB_CMAGIC; #endif + /* create leaf qdisc early because it uses kmalloc(GPF_KERNEL) + so that can't be used inside of sch_tree_lock + -- thanks to Karlis Peisenieks */ + new_q = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops); sch_tree_lock(sch); if (parent && !parent->level) { /* turn parent into inner node */ @@ -1490,8 +1480,7 @@ memset (&parent->un.inner,0,sizeof(parent->un.inner)); } /* leaf (we) needs elementary qdisc */ - if (!(cl->un.leaf.q = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops))) - cl->un.leaf.q = &noop_qdisc; + cl->un.leaf.q = new_q ? new_q : &noop_qdisc; cl->classid = classid; cl->parent = parent;