X-Git-Url: http://pilppa.org/gitweb/gitweb.cgi?a=blobdiff_plain;f=net%2Fsched%2Fsch_htb.c;h=2f0f0b04d3fb127efa75b362beeb62c9aab11bde;hb=96cf45cf559be375de29dd45afc50fa8946fb2aa;hp=83f5e69243c10821dea52b19e28ee791b49e9e1b;hpb=198d6ba4d7f48c94f990f4604f0b3d73925e0ded;p=linux-2.6-omap-h63xx.git diff --git a/net/sched/sch_htb.c b/net/sched/sch_htb.c index 83f5e69243c..2f0f0b04d3f 100644 --- a/net/sched/sch_htb.c +++ b/net/sched/sch_htb.c @@ -84,12 +84,12 @@ struct htb_class { unsigned int children; struct htb_class *parent; /* parent class */ + int prio; /* these two are used only by leaves... */ + int quantum; /* but stored for parent-to-leaf return */ + union { struct htb_class_leaf { struct Qdisc *q; - int prio; - int aprio; - int quantum; int deficit[TC_HTB_MAXDEPTH]; struct list_head drop_list; } leaf; @@ -123,19 +123,8 @@ struct htb_class { psched_tdiff_t mbuffer; /* max wait time */ long tokens, ctokens; /* current number of tokens */ psched_time_t t_c; /* checkpoint time */ - - int prio; /* For parent to leaf return possible here */ - int quantum; /* we do backup. Finally full replacement */ - /* of un.leaf originals should be done. */ }; -static inline long L2T(struct htb_class *cl, struct qdisc_rate_table *rate, - int size) -{ - long result = qdisc_l2t(rate, size); - return result; -} - struct htb_sched { struct Qdisc_class_hash clhash; struct list_head drops[TC_HTB_NUMPRIO];/* active leaves (for drops) */ @@ -152,9 +141,6 @@ struct htb_sched { /* time of nearest event per level (row) */ psched_time_t near_ev_cache[TC_HTB_MAXDEPTH]; - /* whether we hit non-work conserving class during this dequeue; we use */ - int nwc_hit; /* this to disable mindelay complaint in dequeue */ - int defcls; /* class where unclassified flows go to */ /* filters for qdisc itself */ @@ -527,10 +513,10 @@ static inline void htb_activate(struct htb_sched *q, struct htb_class *cl) WARN_ON(cl->level || !cl->un.leaf.q || !cl->un.leaf.q->q.qlen); if (!cl->prio_activity) { - cl->prio_activity = 1 << (cl->un.leaf.aprio = cl->un.leaf.prio); + cl->prio_activity = 1 << cl->prio; htb_activate_prios(q, cl); list_add_tail(&cl->un.leaf.drop_list, - q->drops + cl->un.leaf.aprio); + q->drops + cl->prio); } } @@ -591,6 +577,32 @@ static int htb_enqueue(struct sk_buff *skb, struct Qdisc *sch) return NET_XMIT_SUCCESS; } +static inline void htb_accnt_tokens(struct htb_class *cl, int bytes, long diff) +{ + long toks = diff + cl->tokens; + + if (toks > cl->buffer) + toks = cl->buffer; + toks -= (long) qdisc_l2t(cl->rate, bytes); + if (toks <= -cl->mbuffer) + toks = 1 - cl->mbuffer; + + cl->tokens = toks; +} + +static inline void htb_accnt_ctokens(struct htb_class *cl, int bytes, long diff) +{ + long toks = diff + cl->ctokens; + + if (toks > cl->cbuffer) + toks = cl->cbuffer; + toks -= (long) qdisc_l2t(cl->ceil, bytes); + if (toks <= -cl->mbuffer) + toks = 1 - cl->mbuffer; + + cl->ctokens = toks; +} + /** * htb_charge_class - charges amount "bytes" to leaf and ancestors * @@ -606,26 +618,20 @@ static void htb_charge_class(struct htb_sched *q, struct htb_class *cl, int level, struct sk_buff *skb) { int bytes = qdisc_pkt_len(skb); - long toks, diff; enum htb_cmode old_mode; - -#define HTB_ACCNT(T,B,R) toks = diff + cl->T; \ - if (toks > cl->B) toks = cl->B; \ - toks -= L2T(cl, cl->R, bytes); \ - if (toks <= -cl->mbuffer) toks = 1-cl->mbuffer; \ - cl->T = toks + long diff; while (cl) { diff = psched_tdiff_bounded(q->now, cl->t_c, cl->mbuffer); if (cl->level >= level) { if (cl->level == level) cl->xstats.lends++; - HTB_ACCNT(tokens, buffer, rate); + htb_accnt_tokens(cl, bytes, diff); } else { cl->xstats.borrows++; cl->tokens += diff; /* we moved t_c; update tokens */ } - HTB_ACCNT(ctokens, cbuffer, ceil); + htb_accnt_ctokens(cl, bytes, diff); cl->t_c = q->now; old_mode = cl->cmode; @@ -655,12 +661,13 @@ static void htb_charge_class(struct htb_sched *q, struct htb_class *cl, * next pending event (0 for no event in pq). * Note: Applied are events whose have cl->pq_key <= q->now. */ -static psched_time_t htb_do_events(struct htb_sched *q, int level) +static psched_time_t htb_do_events(struct htb_sched *q, int level, + unsigned long start) { /* don't run for longer than 2 jiffies; 2 is used instead of 1 to simplify things when jiffy is going to be incremented too soon */ - unsigned long stop_at = jiffies + 2; + unsigned long stop_at = start + 2; while (time_before(jiffies, stop_at)) { struct htb_class *cl; long diff; @@ -679,8 +686,8 @@ static psched_time_t htb_do_events(struct htb_sched *q, int level) if (cl->cmode != HTB_CAN_SEND) htb_add_to_wait_tree(q, cl, diff); } - /* too much load - let's continue on next jiffie */ - return q->now + PSCHED_TICKS_PER_SEC / HZ; + /* too much load - let's continue on next jiffie (including above) */ + return q->now + 2 * PSCHED_TICKS_PER_SEC / HZ; } /* Returns class->node+prio from id-tree where classe's id is >= id. NULL @@ -692,14 +699,14 @@ static struct rb_node *htb_id_find_next_upper(int prio, struct rb_node *n, while (n) { struct htb_class *cl = rb_entry(n, struct htb_class, node[prio]); - if (id == cl->common.classid) - return n; if (id > cl->common.classid) { n = n->rb_right; - } else { + } else if (id < cl->common.classid) { r = n; n = n->rb_left; + } else { + return n; } } return r; @@ -720,7 +727,7 @@ static struct htb_class *htb_lookup_leaf(struct rb_root *tree, int prio, u32 *pid; } stk[TC_HTB_MAXDEPTH], *sp = stk; - WARN_ON(!tree->rb_node); + BUG_ON(!tree->rb_node); sp->root = tree->rb_node; sp->pptr = pptr; sp->pid = pid; @@ -740,9 +747,10 @@ static struct htb_class *htb_lookup_leaf(struct rb_root *tree, int prio, *sp->pptr = (*sp->pptr)->rb_left; if (sp > stk) { sp--; - WARN_ON(!*sp->pptr); - if (!*sp->pptr) + if (!*sp->pptr) { + WARN_ON(1); return NULL; + } htb_next_rb_node(sp->pptr); } } else { @@ -773,8 +781,7 @@ static struct sk_buff *htb_dequeue_tree(struct htb_sched *q, int prio, do { next: - WARN_ON(!cl); - if (!cl) + if (unlikely(!cl)) return NULL; /* class can be empty - it is unlikely but can be true if leaf @@ -808,7 +815,7 @@ next: cl->common.classid); cl->warned = 1; } - q->nwc_hit++; + htb_next_rb_node((level ? cl->parent->un.inner.ptr : q-> ptr[0]) + prio); cl = htb_lookup_leaf(q->row[level] + prio, prio, @@ -820,7 +827,7 @@ next: if (likely(skb != NULL)) { cl->un.leaf.deficit[level] -= qdisc_pkt_len(skb); if (cl->un.leaf.deficit[level] < 0) { - cl->un.leaf.deficit[level] += cl->un.leaf.quantum; + cl->un.leaf.deficit[level] += cl->quantum; htb_next_rb_node((level ? cl->parent->un.inner.ptr : q-> ptr[0]) + prio); } @@ -839,6 +846,7 @@ static struct sk_buff *htb_dequeue(struct Qdisc *sch) struct htb_sched *q = qdisc_priv(sch); int level; psched_time_t next_event; + unsigned long start_at; /* try to dequeue direct packets as high prio (!) to minimize cpu work */ skb = __skb_dequeue(&q->direct_queue); @@ -851,23 +859,24 @@ static struct sk_buff *htb_dequeue(struct Qdisc *sch) if (!sch->q.qlen) goto fin; q->now = psched_get_time(); + start_at = jiffies; next_event = q->now + 5 * PSCHED_TICKS_PER_SEC; - q->nwc_hit = 0; + for (level = 0; level < TC_HTB_MAXDEPTH; level++) { /* common case optimization - skip event handler quickly */ int m; psched_time_t event; if (q->now >= q->near_ev_cache[level]) { - event = htb_do_events(q, level); + event = htb_do_events(q, level, start_at); if (!event) event = q->now + PSCHED_TICKS_PER_SEC; q->near_ev_cache[level] = event; } else event = q->near_ev_cache[level]; - if (event && next_event > event) + if (next_event > event) next_event = event; m = ~q->row_mask[level]; @@ -1054,8 +1063,8 @@ static int htb_dump_class(struct Qdisc *sch, unsigned long arg, opt.buffer = cl->buffer; opt.ceil = cl->ceil->rate; opt.cbuffer = cl->cbuffer; - opt.quantum = cl->un.leaf.quantum; - opt.prio = cl->un.leaf.prio; + opt.quantum = cl->quantum; + opt.prio = cl->prio; opt.level = cl->level; NLA_PUT(skb, TCA_HTB_PARMS, sizeof(opt), &opt); @@ -1100,7 +1109,9 @@ static int htb_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new, == NULL) return -ENOBUFS; sch_tree_lock(sch); - if ((*old = xchg(&cl->un.leaf.q, new)) != NULL) { + *old = cl->un.leaf.q; + cl->un.leaf.q = new; + if (*old != NULL) { qdisc_tree_decrease_qlen(*old, (*old)->q.qlen); qdisc_reset(*old); } @@ -1157,8 +1168,6 @@ static void htb_parent_to_leaf(struct htb_sched *q, struct htb_class *cl, memset(&parent->un.inner, 0, sizeof(parent->un.inner)); INIT_LIST_HEAD(&parent->un.leaf.drop_list); parent->un.leaf.q = new_q ? new_q : &noop_qdisc; - parent->un.leaf.quantum = parent->quantum; - parent->un.leaf.prio = parent->prio; parent->tokens = parent->buffer; parent->ctokens = parent->cbuffer; parent->t_c = psched_get_time(); @@ -1330,9 +1339,14 @@ static int htb_change_class(struct Qdisc *sch, u32 classid, if ((cl = kzalloc(sizeof(*cl), GFP_KERNEL)) == NULL) goto failure; - gen_new_estimator(&cl->bstats, &cl->rate_est, - qdisc_root_sleeping_lock(sch), - tca[TCA_RATE] ? : &est.nla); + err = gen_new_estimator(&cl->bstats, &cl->rate_est, + qdisc_root_sleeping_lock(sch), + tca[TCA_RATE] ? : &est.nla); + if (err) { + kfree(cl); + goto failure; + } + cl->refcnt = 1; cl->children = 0; INIT_LIST_HEAD(&cl->un.leaf.drop_list); @@ -1384,37 +1398,36 @@ static int htb_change_class(struct Qdisc *sch, u32 classid, if (parent) parent->children++; } else { - if (tca[TCA_RATE]) - gen_replace_estimator(&cl->bstats, &cl->rate_est, - qdisc_root_sleeping_lock(sch), - tca[TCA_RATE]); + if (tca[TCA_RATE]) { + err = gen_replace_estimator(&cl->bstats, &cl->rate_est, + qdisc_root_sleeping_lock(sch), + tca[TCA_RATE]); + if (err) + return err; + } sch_tree_lock(sch); } /* it used to be a nasty bug here, we have to check that node is really leaf before changing cl->un.leaf ! */ if (!cl->level) { - cl->un.leaf.quantum = rtab->rate.rate / q->rate2quantum; - if (!hopt->quantum && cl->un.leaf.quantum < 1000) { + cl->quantum = rtab->rate.rate / q->rate2quantum; + if (!hopt->quantum && cl->quantum < 1000) { printk(KERN_WARNING "HTB: quantum of class %X is small. Consider r2q change.\n", cl->common.classid); - cl->un.leaf.quantum = 1000; + cl->quantum = 1000; } - if (!hopt->quantum && cl->un.leaf.quantum > 200000) { + if (!hopt->quantum && cl->quantum > 200000) { printk(KERN_WARNING "HTB: quantum of class %X is big. Consider r2q change.\n", cl->common.classid); - cl->un.leaf.quantum = 200000; + cl->quantum = 200000; } if (hopt->quantum) - cl->un.leaf.quantum = hopt->quantum; - if ((cl->un.leaf.prio = hopt->prio) >= TC_HTB_NUMPRIO) - cl->un.leaf.prio = TC_HTB_NUMPRIO - 1; - - /* backup for htb_parent_to_leaf */ - cl->quantum = cl->un.leaf.quantum; - cl->prio = cl->un.leaf.prio; + cl->quantum = hopt->quantum; + if ((cl->prio = hopt->prio) >= TC_HTB_NUMPRIO) + cl->prio = TC_HTB_NUMPRIO - 1; } cl->buffer = hopt->buffer;