* Jiri Fojtasek
* fixed requeue routine
* and many others. thanks.
- *
- * $Id: sch_htb.c,v 1.25 2003/12/07 11:08:25 devik Exp devik $
*/
#include <linux/module.h>
#include <linux/moduleparam.h>
one less than their parent.
*/
-#define HTB_HSIZE 16 /* classid hash size */
static int htb_hysteresis __read_mostly = 0; /* whether to use mode hysteresis for speedup */
#define HTB_VER 0x30011 /* major must be matched with number suplied by TC as version */
/* interior & leaf nodes; props specific to leaves are marked L: */
struct htb_class {
+ struct Qdisc_class_common common;
/* general class parameters */
- u32 classid;
struct gnet_stats_basic bstats;
struct gnet_stats_queue qstats;
struct gnet_stats_rate_est rate_est;
/* topology */
int level; /* our level (see above) */
+ unsigned int children;
struct htb_class *parent; /* parent class */
- struct hlist_node hlist; /* classid hash list item */
- struct list_head sibling; /* sibling list item */
- struct list_head children; /* children list */
union {
struct htb_class_leaf {
}
struct htb_sched {
- struct list_head root; /* root classes list */
- struct hlist_head hash[HTB_HSIZE]; /* hashed by classid */
+ struct Qdisc_class_hash clhash;
struct list_head drops[TC_HTB_NUMPRIO];/* active leaves (for drops) */
/* self list - roots of self generating tree */
/* filters for qdisc itself */
struct tcf_proto *filter_list;
- int filter_cnt;
int rate2quantum; /* quant = rate / rate2quantum */
psched_time_t now; /* cached dequeue time */
long direct_pkts;
};
-/* compute hash of size HTB_HSIZE for given handle */
-static inline int htb_hash(u32 h)
-{
-#if HTB_HSIZE != 16
-#error "Declare new hash for your HTB_HSIZE"
-#endif
- h ^= h >> 8; /* stolen from cbq_hash */
- h ^= h >> 4;
- return h & 0xf;
-}
-
/* find class in global hash table using given handle */
static inline struct htb_class *htb_find(u32 handle, struct Qdisc *sch)
{
struct htb_sched *q = qdisc_priv(sch);
- struct hlist_node *p;
- struct htb_class *cl;
+ struct Qdisc_class_common *clc;
- if (TC_H_MAJ(handle) != sch->handle)
+ clc = qdisc_class_find(&q->clhash, handle);
+ if (clc == NULL)
return NULL;
-
- hlist_for_each_entry(cl, p, q->hash + htb_hash(handle), hlist) {
- if (cl->classid == handle)
- return cl;
- }
- return NULL;
+ return container_of(clc, struct htb_class, common);
}
/**
parent = *p;
c = rb_entry(parent, struct htb_class, node[prio]);
- if (cl->classid > c->classid)
+ if (cl->common.classid > c->common.classid)
p = &parent->rb_right;
else
p = &parent->rb_left;
/* we are removing child which is pointed to from
parent feed - forget the pointer but remember
classid */
- p->un.inner.last_ptr_id[prio] = cl->classid;
+ p->un.inner.last_ptr_id[prio] = cl->common.classid;
p->un.inner.ptr[prio] = NULL;
}
kfree_skb(skb);
return ret;
#endif
- } else if (cl->un.leaf.q->enqueue(skb, cl->un.leaf.q) !=
- NET_XMIT_SUCCESS) {
+ } else if (qdisc_enqueue(skb, cl->un.leaf.q) != NET_XMIT_SUCCESS) {
sch->qstats.drops++;
cl->qstats.drops++;
return NET_XMIT_DROP;
} else {
cl->bstats.packets +=
skb_is_gso(skb)?skb_shinfo(skb)->gso_segs:1;
- cl->bstats.bytes += skb->len;
+ cl->bstats.bytes += qdisc_pkt_len(skb);
htb_activate(q, cl);
}
sch->q.qlen++;
sch->bstats.packets += skb_is_gso(skb)?skb_shinfo(skb)->gso_segs:1;
- sch->bstats.bytes += skb->len;
+ sch->bstats.bytes += qdisc_pkt_len(skb);
return NET_XMIT_SUCCESS;
}
static void htb_charge_class(struct htb_sched *q, struct htb_class *cl,
int level, struct sk_buff *skb)
{
- int bytes = skb->len;
+ int bytes = qdisc_pkt_len(skb);
long toks, diff;
enum htb_cmode old_mode;
while (n) {
struct htb_class *cl =
rb_entry(n, struct htb_class, node[prio]);
- if (id == cl->classid)
+ if (id == cl->common.classid)
return n;
- if (id > cl->classid) {
+ if (id > cl->common.classid) {
n = n->rb_right;
} else {
r = n;
if (!cl->warned) {
printk(KERN_WARNING
"htb: class %X isn't work conserving ?!\n",
- cl->classid);
+ cl->common.classid);
cl->warned = 1;
}
q->nwc_hit++;
} while (cl != start);
if (likely(skb != NULL)) {
- if ((cl->un.leaf.deficit[level] -= skb->len) < 0) {
+ 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;
htb_next_rb_node((level ? cl->parent->un.inner.ptr : q->
ptr[0]) + prio);
static void htb_reset(struct Qdisc *sch)
{
struct htb_sched *q = qdisc_priv(sch);
- int i;
-
- for (i = 0; i < HTB_HSIZE; i++) {
- struct hlist_node *p;
- struct htb_class *cl;
+ struct htb_class *cl;
+ struct hlist_node *n;
+ unsigned int i;
- hlist_for_each_entry(cl, p, q->hash + i, hlist) {
+ for (i = 0; i < q->clhash.hashsize; i++) {
+ hlist_for_each_entry(cl, n, &q->clhash.hash[i], common.hnode) {
if (cl->level)
memset(&cl->un.inner, 0, sizeof(cl->un.inner));
else {
return -EINVAL;
}
- INIT_LIST_HEAD(&q->root);
- for (i = 0; i < HTB_HSIZE; i++)
- INIT_HLIST_HEAD(q->hash + i);
+ err = qdisc_class_hash_init(&q->clhash);
+ if (err < 0)
+ return err;
for (i = 0; i < TC_HTB_NUMPRIO; i++)
INIT_LIST_HEAD(q->drops + i);
qdisc_watchdog_init(&q->watchdog, sch);
skb_queue_head_init(&q->direct_queue);
- q->direct_qlen = sch->dev->tx_queue_len;
+ q->direct_qlen = qdisc_dev(sch)->tx_queue_len;
if (q->direct_qlen < 2) /* some devices have zero tx_queue_len */
q->direct_qlen = 2;
static int htb_dump(struct Qdisc *sch, struct sk_buff *skb)
{
+ spinlock_t *root_lock = qdisc_root_lock(sch);
struct htb_sched *q = qdisc_priv(sch);
struct nlattr *nest;
struct tc_htb_glob gopt;
- spin_lock_bh(&sch->dev->queue_lock);
+ spin_lock_bh(root_lock);
gopt.direct_pkts = q->direct_pkts;
gopt.version = HTB_VER;
NLA_PUT(skb, TCA_HTB_INIT, sizeof(gopt), &gopt);
nla_nest_end(skb, nest);
- spin_unlock_bh(&sch->dev->queue_lock);
+ spin_unlock_bh(root_lock);
return skb->len;
nla_put_failure:
- spin_unlock_bh(&sch->dev->queue_lock);
+ spin_unlock_bh(root_lock);
nla_nest_cancel(skb, nest);
return -1;
}
struct sk_buff *skb, struct tcmsg *tcm)
{
struct htb_class *cl = (struct htb_class *)arg;
+ spinlock_t *root_lock = qdisc_root_lock(sch);
struct nlattr *nest;
struct tc_htb_opt opt;
- spin_lock_bh(&sch->dev->queue_lock);
- tcm->tcm_parent = cl->parent ? cl->parent->classid : TC_H_ROOT;
- tcm->tcm_handle = cl->classid;
+ spin_lock_bh(root_lock);
+ tcm->tcm_parent = cl->parent ? cl->parent->common.classid : TC_H_ROOT;
+ tcm->tcm_handle = cl->common.classid;
if (!cl->level && cl->un.leaf.q)
tcm->tcm_info = cl->un.leaf.q->handle;
NLA_PUT(skb, TCA_HTB_PARMS, sizeof(opt), &opt);
nla_nest_end(skb, nest);
- spin_unlock_bh(&sch->dev->queue_lock);
+ spin_unlock_bh(root_lock);
return skb->len;
nla_put_failure:
- spin_unlock_bh(&sch->dev->queue_lock);
+ spin_unlock_bh(root_lock);
nla_nest_cancel(skb, nest);
return -1;
}
if (cl && !cl->level) {
if (new == NULL &&
- (new = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops,
- cl->classid))
+ (new = qdisc_create_dflt(qdisc_dev(sch), sch->dev_queue,
+ &pfifo_qdisc_ops,
+ cl->common.classid))
== NULL)
return -ENOBUFS;
sch_tree_lock(sch);
if (!cl->parent)
/* the root class */
return 0;
-
- if (!(cl->parent->children.next == &cl->sibling &&
- cl->parent->children.prev == &cl->sibling))
+ if (cl->parent->children > 1)
/* not the last child */
return 0;
-
return 1;
}
static void htb_destroy_class(struct Qdisc *sch, struct htb_class *cl)
{
- struct htb_sched *q = qdisc_priv(sch);
-
if (!cl->level) {
BUG_TRAP(cl->un.leaf.q);
qdisc_destroy(cl->un.leaf.q);
qdisc_put_rtab(cl->ceil);
tcf_destroy_chain(&cl->filter_list);
-
- while (!list_empty(&cl->children))
- htb_destroy_class(sch, list_entry(cl->children.next,
- struct htb_class, sibling));
-
- /* note: this delete may happen twice (see htb_delete) */
- hlist_del_init(&cl->hlist);
- list_del(&cl->sibling);
-
- if (cl->prio_activity)
- htb_deactivate(q, cl);
-
- if (cl->cmode != HTB_CAN_SEND)
- htb_safe_rb_erase(&cl->pq_node, q->wait_pq + cl->level);
-
kfree(cl);
}
static void htb_destroy(struct Qdisc *sch)
{
struct htb_sched *q = qdisc_priv(sch);
+ struct hlist_node *n, *next;
+ struct htb_class *cl;
+ unsigned int i;
qdisc_watchdog_cancel(&q->watchdog);
/* This line used to be after htb_destroy_class call below
unbind_filter on it (without Oops). */
tcf_destroy_chain(&q->filter_list);
- while (!list_empty(&q->root))
- htb_destroy_class(sch, list_entry(q->root.next,
- struct htb_class, sibling));
-
+ for (i = 0; i < q->clhash.hashsize; i++) {
+ hlist_for_each_entry(cl, n, &q->clhash.hash[i], common.hnode)
+ tcf_destroy_chain(&cl->filter_list);
+ }
+ for (i = 0; i < q->clhash.hashsize; i++) {
+ hlist_for_each_entry_safe(cl, n, next, &q->clhash.hash[i],
+ common.hnode)
+ htb_destroy_class(sch, cl);
+ }
+ qdisc_class_hash_destroy(&q->clhash);
__skb_queue_purge(&q->direct_queue);
}
// TODO: why don't allow to delete subtree ? references ? does
// tc subsys quarantee us that in htb_destroy it holds no class
// refs so that we can remove children safely there ?
- if (!list_empty(&cl->children) || cl->filter_cnt)
+ if (cl->children || cl->filter_cnt)
return -EBUSY;
if (!cl->level && htb_parent_last_child(cl)) {
- new_q = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops,
- cl->parent->classid);
+ new_q = qdisc_create_dflt(qdisc_dev(sch), sch->dev_queue,
+ &pfifo_qdisc_ops,
+ cl->parent->common.classid);
last_child = 1;
}
}
/* delete from hash and active; remainder in destroy_class */
- hlist_del_init(&cl->hlist);
+ qdisc_class_hash_remove(&q->clhash, &cl->common);
+ cl->parent->children--;
if (cl->prio_activity)
htb_deactivate(q, cl);
+ if (cl->cmode != HTB_CAN_SEND)
+ htb_safe_rb_erase(&cl->pq_node, q->wait_pq + cl->level);
+
if (last_child)
htb_parent_to_leaf(q, cl, new_q);
goto failure;
gen_new_estimator(&cl->bstats, &cl->rate_est,
- &sch->dev->queue_lock,
+ qdisc_root_lock(sch),
tca[TCA_RATE] ? : &est.nla);
cl->refcnt = 1;
- INIT_LIST_HEAD(&cl->sibling);
- INIT_HLIST_NODE(&cl->hlist);
- INIT_LIST_HEAD(&cl->children);
+ cl->children = 0;
INIT_LIST_HEAD(&cl->un.leaf.drop_list);
RB_CLEAR_NODE(&cl->pq_node);
/* create leaf qdisc early because it uses kmalloc(GFP_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, classid);
+ new_q = qdisc_create_dflt(qdisc_dev(sch), sch->dev_queue,
+ &pfifo_qdisc_ops, classid);
sch_tree_lock(sch);
if (parent && !parent->level) {
unsigned int qlen = parent->un.leaf.q->q.qlen;
/* leaf (we) needs elementary qdisc */
cl->un.leaf.q = new_q ? new_q : &noop_qdisc;
- cl->classid = classid;
+ cl->common.classid = classid;
cl->parent = parent;
/* set class to be in HTB_CAN_SEND state */
cl->cmode = HTB_CAN_SEND;
/* attach to the hash list and parent's family */
- hlist_add_head(&cl->hlist, q->hash + htb_hash(classid));
- list_add_tail(&cl->sibling,
- parent ? &parent->children : &q->root);
+ qdisc_class_hash_insert(&q->clhash, &cl->common);
+ if (parent)
+ parent->children++;
} else {
if (tca[TCA_RATE])
gen_replace_estimator(&cl->bstats, &cl->rate_est,
- &sch->dev->queue_lock,
+ qdisc_root_lock(sch),
tca[TCA_RATE]);
sch_tree_lock(sch);
}
if (!hopt->quantum && cl->un.leaf.quantum < 1000) {
printk(KERN_WARNING
"HTB: quantum of class %X is small. Consider r2q change.\n",
- cl->classid);
+ cl->common.classid);
cl->un.leaf.quantum = 1000;
}
if (!hopt->quantum && cl->un.leaf.quantum > 200000) {
printk(KERN_WARNING
"HTB: quantum of class %X is big. Consider r2q change.\n",
- cl->classid);
+ cl->common.classid);
cl->un.leaf.quantum = 200000;
}
if (hopt->quantum)
cl->ceil = ctab;
sch_tree_unlock(sch);
+ qdisc_class_hash_grow(sch, &q->clhash);
+
*arg = (unsigned long)cl;
return 0;
static unsigned long htb_bind_filter(struct Qdisc *sch, unsigned long parent,
u32 classid)
{
- struct htb_sched *q = qdisc_priv(sch);
struct htb_class *cl = htb_find(classid, sch);
/*if (cl && !cl->level) return 0;
*/
if (cl)
cl->filter_cnt++;
- else
- q->filter_cnt++;
return (unsigned long)cl;
}
static void htb_unbind_filter(struct Qdisc *sch, unsigned long arg)
{
- struct htb_sched *q = qdisc_priv(sch);
struct htb_class *cl = (struct htb_class *)arg;
if (cl)
cl->filter_cnt--;
- else
- q->filter_cnt--;
}
static void htb_walk(struct Qdisc *sch, struct qdisc_walker *arg)
{
struct htb_sched *q = qdisc_priv(sch);
- int i;
+ struct htb_class *cl;
+ struct hlist_node *n;
+ unsigned int i;
if (arg->stop)
return;
- for (i = 0; i < HTB_HSIZE; i++) {
- struct hlist_node *p;
- struct htb_class *cl;
-
- hlist_for_each_entry(cl, p, q->hash + i, hlist) {
+ for (i = 0; i < q->clhash.hashsize; i++) {
+ hlist_for_each_entry(cl, n, &q->clhash.hash[i], common.hnode) {
if (arg->count < arg->skip) {
arg->count++;
continue;
git.openpandora.org / pandora-kernel.git / blobdiff