Merge with Linux 2.3.6. Sorry, this isn't tested on silicon, I don't

have a MIPS box at hand.

15 files changed, 504 insertions, 181 deletions

diff --git a/net/sched/cls_api.c b/net/sched/cls_api.c
index 683063137..9d2a95ea6 100644
--- a/net/sched/cls_api.c
+++ b/net/sched/cls_api.c
@@ -39,20 +39,24 @@
 
 static struct tcf_proto_ops *tcf_proto_base;
 
+/* Protects list of registered TC modules. It is pure SMP lock. */
+static rwlock_t cls_mod_lock = RW_LOCK_UNLOCKED;
 
 /* Find classifier type by string name */
 
 struct tcf_proto_ops * tcf_proto_lookup_ops(struct rtattr *kind)
 {
-	struct tcf_proto_ops *t;
+	struct tcf_proto_ops *t = NULL;
 
 	if (kind) {
+		read_lock(&cls_mod_lock);
 		for (t = tcf_proto_base; t; t = t->next) {
 			if (rtattr_strcmp(kind, t->kind) == 0)
-				return t;
+				break;
 		}
+		read_unlock(&cls_mod_lock);
 	}
-	return NULL;
+	return t;
 }
 
 /* Register(unregister) new classifier type */
@@ -61,12 +65,17 @@ int register_tcf_proto_ops(struct tcf_proto_ops *ops)
 {
 	struct tcf_proto_ops *t, **tp;
 
-	for (tp = &tcf_proto_base; (t=*tp) != NULL; tp = &t->next)
-		if (strcmp(ops->kind, t->kind) == 0)
+	write_lock(&cls_mod_lock);
+	for (tp = &tcf_proto_base; (t=*tp) != NULL; tp = &t->next) {
+		if (strcmp(ops->kind, t->kind) == 0) {
+			write_unlock(&cls_mod_lock);
 			return -EEXIST;
+		}
+	}
 
 	ops->next = NULL;
 	*tp = ops;
+	write_unlock(&cls_mod_lock);
 	return 0;
 }
 
@@ -74,13 +83,17 @@ int unregister_tcf_proto_ops(struct tcf_proto_ops *ops)
 {
 	struct tcf_proto_ops *t, **tp;
 
+	write_lock(&cls_mod_lock);
 	for (tp = &tcf_proto_base; (t=*tp) != NULL; tp = &t->next)
 		if (t == ops)
 			break;
 
-	if (!t)
+	if (!t) {
+		write_unlock(&cls_mod_lock);
 		return -ENOENT;
+	}
 	*tp = t->next;
+	write_unlock(&cls_mod_lock);
 	return 0;
 }
 
@@ -217,8 +230,12 @@ static int tc_ctl_tfilter(struct sk_buff *skb, struct nlmsghdr *n, void *arg)
 			kfree(tp);
 			goto errout;
 		}
+		write_lock(&qdisc_tree_lock);
+		spin_lock_bh(&dev->queue_lock);
 		tp->next = *back;
 		*back = tp;
+		spin_unlock_bh(&dev->queue_lock);
+		write_unlock(&qdisc_tree_lock);
 	} else if (tca[TCA_KIND-1] && rtattr_strcmp(tca[TCA_KIND-1], tp->ops->kind))
 		goto errout;
 
@@ -226,8 +243,11 @@ static int tc_ctl_tfilter(struct sk_buff *skb, struct nlmsghdr *n, void *arg)
 
 	if (fh == 0) {
 		if (n->nlmsg_type == RTM_DELTFILTER && t->tcm_handle == 0) {
+			write_lock(&qdisc_tree_lock);
+			spin_lock_bh(&dev->queue_lock);
 			*back = tp->next;
-			synchronize_bh();
+			spin_unlock_bh(&dev->queue_lock);
+			write_unlock(&qdisc_tree_lock);
 
 			tp->ops->destroy(tp);
 			kfree(tp);
@@ -344,12 +364,16 @@ static int tc_dump_tfilter(struct sk_buff *skb, struct netlink_callback *cb)
 		return skb->len;
 	if ((dev = dev_get_by_index(tcm->tcm_ifindex)) == NULL)
 		return skb->len;
+
+	read_lock(&qdisc_tree_lock);
 	if (!tcm->tcm_parent)
 		q = dev->qdisc_sleeping;
 	else
 		q = qdisc_lookup(dev, TC_H_MAJ(tcm->tcm_parent));
-	if (q == NULL)
+	if (q == NULL) {
+		read_unlock(&qdisc_tree_lock);
 		return skb->len;
+	}
 	if ((cops = q->ops->cl_ops) == NULL)
 		goto errout;
 	if (TC_H_MIN(tcm->tcm_parent)) {
@@ -400,6 +424,7 @@ errout:
 	if (cl)
 		cops->put(q, cl);
 
+	read_unlock(&qdisc_tree_lock);
 	return skb->len;
 }
 
diff --git a/net/sched/cls_fw.c b/net/sched/cls_fw.c
index e92b846ee..598867187 100644
--- a/net/sched/cls_fw.c
+++ b/net/sched/cls_fw.c
@@ -136,7 +136,7 @@ static void fw_destroy(struct tcf_proto *tp)
 			unsigned long cl;
 			head->ht[h] = f->next;
 
-			if ((cl = cls_set_class(&f->res.class, 0)) != 0)
+			if ((cl = __cls_set_class(&f->res.class, 0)) != 0)
 				tp->q->ops->cl_ops->unbind_tcf(tp->q, cl);
 #ifdef CONFIG_NET_CLS_POLICE
 			tcf_police_release(f->police);
@@ -161,10 +161,11 @@ static int fw_delete(struct tcf_proto *tp, unsigned long arg)
 		if (*fp == f) {
 			unsigned long cl;
 
+			tcf_tree_lock(tp);
 			*fp = f->next;
-			synchronize_bh();
+			tcf_tree_unlock(tp);
 
-			if ((cl = cls_set_class(&f->res.class, 0)) != 0)
+			if ((cl = cls_set_class(tp, &f->res.class, 0)) != 0)
 				tp->q->ops->cl_ops->unbind_tcf(tp->q, cl);
 #ifdef CONFIG_NET_CLS_POLICE
 			tcf_police_release(f->police);
@@ -203,7 +204,7 @@ static int fw_change(struct tcf_proto *tp, unsigned long base,
 
 			f->res.classid = *(u32*)RTA_DATA(tb[TCA_FW_CLASSID-1]);
 			cl = tp->q->ops->cl_ops->bind_tcf(tp->q, base, f->res.classid);
-			cl = cls_set_class(&f->res.class, cl);
+			cl = cls_set_class(tp, &f->res.class, cl);
 			if (cl)
 				tp->q->ops->cl_ops->unbind_tcf(tp->q, cl);
 		}
@@ -211,8 +212,9 @@ static int fw_change(struct tcf_proto *tp, unsigned long base,
 		if (tb[TCA_FW_POLICE-1]) {
 			struct tcf_police *police = tcf_police_locate(tb[TCA_FW_POLICE-1], tca[TCA_RATE-1]);
 
+			tcf_tree_lock(tp);
 			police = xchg(&f->police, police);
-			synchronize_bh();
+			tcf_tree_unlock(tp);
 
 			tcf_police_release(police);
 		}
@@ -229,8 +231,9 @@ static int fw_change(struct tcf_proto *tp, unsigned long base,
 			return -ENOBUFS;
 		memset(head, 0, sizeof(*head));
 
+		tcf_tree_lock(tp);
 		tp->root = head;
-		synchronize_bh();
+		tcf_tree_unlock(tp);
 	}
 
 	f = kmalloc(sizeof(struct fw_filter), GFP_KERNEL);
@@ -245,7 +248,7 @@ static int fw_change(struct tcf_proto *tp, unsigned long base,
 		if (RTA_PAYLOAD(tb[TCA_FW_CLASSID-1]) != 4)
 			goto errout;
 		f->res.classid = *(u32*)RTA_DATA(tb[TCA_FW_CLASSID-1]);
-		cls_set_class(&f->res.class, tp->q->ops->cl_ops->bind_tcf(tp->q, base, f->res.classid));
+		cls_set_class(tp, &f->res.class, tp->q->ops->cl_ops->bind_tcf(tp->q, base, f->res.classid));
 	}
 
 #ifdef CONFIG_NET_CLS_POLICE
@@ -254,8 +257,9 @@ static int fw_change(struct tcf_proto *tp, unsigned long base,
 #endif
 
 	f->next = head->ht[fw_hash(handle)];
-	wmb();
+	tcf_tree_lock(tp);
 	head->ht[fw_hash(handle)] = f;
+	tcf_tree_unlock(tp);
 
 	*arg = (unsigned long)f;
 	return 0;
@@ -335,7 +339,8 @@ static int fw_dump(struct tcf_proto *tp, unsigned long fh,
 	rta->rta_len = skb->tail - b;
 #ifdef CONFIG_NET_CLS_POLICE
 	if (f->police) {
-		RTA_PUT(skb, TCA_STATS, sizeof(struct tc_stats), &f->police->stats);
+		if (qdisc_copy_stats(skb, &f->police->stats))
+			goto rtattr_failure;
 	}
 #endif
 	return skb->len;
diff --git a/net/sched/cls_route.c b/net/sched/cls_route.c
index f83e79134..cb0d21d0f 100644
--- a/net/sched/cls_route.c
+++ b/net/sched/cls_route.c
@@ -83,11 +83,11 @@ static __inline__ int route4_fastmap_hash(u32 id, int iif)
 	return id&0xF;
 }
 
-static void route4_reset_fastmap(struct route4_head *head, u32 id)
+static void route4_reset_fastmap(struct device *dev, struct route4_head *head, u32 id)
 {
-	start_bh_atomic();
+	spin_lock_bh(&dev->queue_lock);
 	memset(head->fastmap, 0, sizeof(head->fastmap));
-	end_bh_atomic();
+	spin_unlock_bh(&dev->queue_lock);
 }
 
 static void __inline__
@@ -297,7 +297,7 @@ static void route4_destroy(struct tcf_proto *tp)
 					unsigned long cl;
 
 					b->ht[h2] = f->next;
-					if ((cl = cls_set_class(&f->res.class, 0)) != 0)
+					if ((cl = __cls_set_class(&f->res.class, 0)) != 0)
 						tp->q->ops->cl_ops->unbind_tcf(tp->q, cl);
 #ifdef CONFIG_NET_CLS_POLICE
 					tcf_police_release(f->police);
@@ -329,12 +329,13 @@ static int route4_delete(struct tcf_proto *tp, unsigned long arg)
 		if (*fp == f) {
 			unsigned long cl;
 
+			tcf_tree_lock(tp);
 			*fp = f->next;
-			synchronize_bh();
+			tcf_tree_unlock(tp);
 
-			route4_reset_fastmap(head, f->id);
+			route4_reset_fastmap(tp->q->dev, head, f->id);
 
-			if ((cl = cls_set_class(&f->res.class, 0)) != 0)
+			if ((cl = cls_set_class(tp, &f->res.class, 0)) != 0)
 				tp->q->ops->cl_ops->unbind_tcf(tp->q, cl);
 
 #ifdef CONFIG_NET_CLS_POLICE
@@ -349,8 +350,9 @@ static int route4_delete(struct tcf_proto *tp, unsigned long arg)
 					return 0;
 
 			/* OK, session has no flows */
+			tcf_tree_lock(tp);
 			head->table[to_hash(h)] = NULL;
-			synchronize_bh();
+			tcf_tree_unlock(tp);
 
 			kfree(b);
 			return 0;
@@ -387,7 +389,7 @@ static int route4_change(struct tcf_proto *tp, unsigned long base,
 			unsigned long cl;
 
 			f->res.classid = *(u32*)RTA_DATA(tb[TCA_ROUTE4_CLASSID-1]);
-			cl = cls_set_class(&f->res.class, tp->q->ops->cl_ops->bind_tcf(tp->q, base, f->res.classid));
+			cl = cls_set_class(tp, &f->res.class, tp->q->ops->cl_ops->bind_tcf(tp->q, base, f->res.classid));
 			if (cl)
 				tp->q->ops->cl_ops->unbind_tcf(tp->q, cl);
 		}
@@ -395,8 +397,9 @@ static int route4_change(struct tcf_proto *tp, unsigned long base,
 		if (tb[TCA_ROUTE4_POLICE-1]) {
 			struct tcf_police *police = tcf_police_locate(tb[TCA_ROUTE4_POLICE-1], tca[TCA_RATE-1]);
 
+			tcf_tree_lock(tp);
 			police = xchg(&f->police, police);
-			synchronize_bh();
+			tcf_tree_unlock(tp);
 
 			tcf_police_release(police);
 		}
@@ -412,8 +415,9 @@ static int route4_change(struct tcf_proto *tp, unsigned long base,
 			return -ENOBUFS;
 		memset(head, 0, sizeof(struct route4_head));
 
+		tcf_tree_lock(tp);
 		tp->root = head;
-		synchronize_bh();
+		tcf_tree_unlock(tp);
 	}
 
 	f = kmalloc(sizeof(struct route4_filter), GFP_KERNEL);
@@ -475,8 +479,9 @@ static int route4_change(struct tcf_proto *tp, unsigned long base,
 			goto errout;
 		memset(b, 0, sizeof(*b));
 
+		tcf_tree_lock(tp);
 		head->table[h1] = b;
-		synchronize_bh();
+		tcf_tree_unlock(tp);
 	}
 	f->bkt = b;
 
@@ -489,17 +494,18 @@ static int route4_change(struct tcf_proto *tp, unsigned long base,
 			goto errout;
 	}
 
-	cls_set_class(&f->res.class, tp->q->ops->cl_ops->bind_tcf(tp->q, base, f->res.classid));
+	cls_set_class(tp, &f->res.class, tp->q->ops->cl_ops->bind_tcf(tp->q, base, f->res.classid));
 #ifdef CONFIG_NET_CLS_POLICE
 	if (tb[TCA_ROUTE4_POLICE-1])
 		f->police = tcf_police_locate(tb[TCA_ROUTE4_POLICE-1], tca[TCA_RATE-1]);
 #endif
 
 	f->next = f1;
-	wmb();
+	tcf_tree_lock(tp);
 	*ins_f = f;
+	tcf_tree_unlock(tp);
 
-	route4_reset_fastmap(head, f->id);
+	route4_reset_fastmap(tp->q->dev, head, f->id);
 	*arg = (unsigned long)f;
 	return 0;
 
@@ -589,7 +595,8 @@ static int route4_dump(struct tcf_proto *tp, unsigned long fh,
 	rta->rta_len = skb->tail - b;
 #ifdef CONFIG_NET_CLS_POLICE
 	if (f->police) {
-		RTA_PUT(skb, TCA_STATS, sizeof(struct tc_stats), &f->police->stats);
+		if (qdisc_copy_stats(skb, &f->police->stats))
+			goto rtattr_failure;
 	}
 #endif
 	return skb->len;
diff --git a/net/sched/cls_rsvp.h b/net/sched/cls_rsvp.h
index 48142c6e7..be4471d78 100644
--- a/net/sched/cls_rsvp.h
+++ b/net/sched/cls_rsvp.h
@@ -282,7 +282,7 @@ static void rsvp_destroy(struct tcf_proto *tp)
 					unsigned long cl;
 
 					s->ht[h2] = f->next;
-					if ((cl = cls_set_class(&f->res.class, 0)) != 0)
+					if ((cl = __cls_set_class(&f->res.class, 0)) != 0)
 						tp->q->ops->cl_ops->unbind_tcf(tp->q, cl);
 #ifdef CONFIG_NET_CLS_POLICE
 					tcf_police_release(f->police);
@@ -310,10 +310,11 @@ static int rsvp_delete(struct tcf_proto *tp, unsigned long arg)
 			unsigned long cl;
 
 
+			tcf_tree_lock(tp);
 			*fp = f->next;
-			synchronize_bh();
+			tcf_tree_unlock(tp);
 
-			if ((cl = cls_set_class(&f->res.class, 0)) != 0)
+			if ((cl = cls_set_class(tp, &f->res.class, 0)) != 0)
 				tp->q->ops->cl_ops->unbind_tcf(tp->q, cl);
 
 #ifdef CONFIG_NET_CLS_POLICE
@@ -332,8 +333,9 @@ static int rsvp_delete(struct tcf_proto *tp, unsigned long arg)
 			for (sp = &((struct rsvp_head*)tp->root)->ht[h&0xFF];
 			     *sp; sp = &(*sp)->next) {
 				if (*sp == s) {
+					tcf_tree_lock(tp);
 					*sp = s->next;
-					synchronize_bh();
+					tcf_tree_unlock(tp);
 
 					kfree(s);
 					return 0;
@@ -446,7 +448,7 @@ static int rsvp_change(struct tcf_proto *tp, unsigned long base,
 			unsigned long cl;
 
 			f->res.classid = *(u32*)RTA_DATA(tb[TCA_RSVP_CLASSID-1]);
-			cl = cls_set_class(&f->res.class, tp->q->ops->cl_ops->bind_tcf(tp->q, base, f->res.classid));
+			cl = cls_set_class(tp, &f->res.class, tp->q->ops->cl_ops->bind_tcf(tp->q, base, f->res.classid));
 			if (cl)
 				tp->q->ops->cl_ops->unbind_tcf(tp->q, cl);
 		}
@@ -454,8 +456,9 @@ static int rsvp_change(struct tcf_proto *tp, unsigned long base,
 		if (tb[TCA_RSVP_POLICE-1]) {
 			struct tcf_police *police = tcf_police_locate(tb[TCA_RSVP_POLICE-1], tca[TCA_RATE-1]);
 
+			tcf_tree_lock(tp);
 			police = xchg(&f->police, police);
-			synchronize_bh();
+			tcf_tree_unlock(tp);
 
 			tcf_police_release(police);
 		}
@@ -536,7 +539,7 @@ insert:
 
 			f->sess = s;
 			if (f->tunnelhdr == 0)
-				cls_set_class(&f->res.class, tp->q->ops->cl_ops->bind_tcf(tp->q, base, f->res.classid));
+				cls_set_class(tp, &f->res.class, tp->q->ops->cl_ops->bind_tcf(tp->q, base, f->res.classid));
 #ifdef CONFIG_NET_CLS_POLICE
 			if (tb[TCA_RSVP_POLICE-1])
 				f->police = tcf_police_locate(tb[TCA_RSVP_POLICE-1], tca[TCA_RATE-1]);
@@ -659,7 +662,8 @@ static int rsvp_dump(struct tcf_proto *tp, unsigned long fh,
 	rta->rta_len = skb->tail - b;
 #ifdef CONFIG_NET_CLS_POLICE
 	if (f->police) {
-		RTA_PUT(skb, TCA_STATS, sizeof(struct tc_stats), &f->police->stats);
+		if (qdisc_copy_stats(skb, &f->police->stats))
+			goto rtattr_failure;
 	}
 #endif
 	return skb->len;
diff --git a/net/sched/cls_u32.c b/net/sched/cls_u32.c
index 98d4e1f7b..f759d150a 100644
--- a/net/sched/cls_u32.c
+++ b/net/sched/cls_u32.c
@@ -307,7 +307,7 @@ static int u32_destroy_key(struct tcf_proto *tp, struct tc_u_knode *n)
 {
 	unsigned long cl;
 
-	if ((cl = cls_set_class(&n->res.class, 0)) != 0)
+	if ((cl = __cls_set_class(&n->res.class, 0)) != 0)
 		tp->q->ops->cl_ops->unbind_tcf(tp->q, cl);
 #ifdef CONFIG_NET_CLS_POLICE
 	tcf_police_release(n->police);
@@ -326,8 +326,9 @@ static int u32_delete_key(struct tcf_proto *tp, struct tc_u_knode* key)
 	if (ht) {
 		for (kp = &ht->ht[TC_U32_HASH(key->handle)]; *kp; kp = &(*kp)->next) {
 			if (*kp == key) {
+				tcf_tree_lock(tp);
 				*kp = key->next;
-				synchronize_bh();
+				tcf_tree_unlock(tp);
 
 				u32_destroy_key(tp, key);
 				return 0;
@@ -346,7 +347,6 @@ static void u32_clear_hnode(struct tcf_proto *tp, struct tc_u_hnode *ht)
 	for (h=0; h<=ht->divisor; h++) {
 		while ((n = ht->ht[h]) != NULL) {
 			ht->ht[h] = n->next;
-			synchronize_bh();
 
 			u32_destroy_key(tp, n);
 		}
@@ -465,8 +465,9 @@ static int u32_set_parms(struct Qdisc *q, unsigned long base,
 			ht_down->refcnt++;
 		}
 
+		sch_tree_lock(q);
 		ht_down = xchg(&n->ht_down, ht_down);
-		synchronize_bh();
+		sch_tree_unlock(q);
 
 		if (ht_down)
 			ht_down->refcnt--;
@@ -475,7 +476,9 @@ static int u32_set_parms(struct Qdisc *q, unsigned long base,
 		unsigned long cl;
 
 		n->res.classid = *(u32*)RTA_DATA(tb[TCA_U32_CLASSID-1]);
-		cl = cls_set_class(&n->res.class, q->ops->cl_ops->bind_tcf(q, base, n->res.classid));
+		sch_tree_lock(q);
+		cl = __cls_set_class(&n->res.class, q->ops->cl_ops->bind_tcf(q, base, n->res.classid));
+		sch_tree_unlock(q);
 		if (cl)
 			q->ops->cl_ops->unbind_tcf(q, cl);
 	}
@@ -483,8 +486,9 @@ static int u32_set_parms(struct Qdisc *q, unsigned long base,
 	if (tb[TCA_U32_POLICE-1]) {
 		struct tcf_police *police = tcf_police_locate(tb[TCA_U32_POLICE-1], est);
 
+		sch_tree_lock(q);
 		police = xchg(&n->police, police);
-		synchronize_bh();
+		sch_tree_lock(q);
 
 		tcf_police_release(police);
 	}
@@ -682,7 +686,8 @@ static int u32_dump(struct tcf_proto *tp, unsigned long fh,
 	rta->rta_len = skb->tail - b;
 #ifdef CONFIG_NET_CLS_POLICE
 	if (TC_U32_KEY(n->handle) && n->police) {
-		RTA_PUT(skb, TCA_STATS, sizeof(struct tc_stats), &n->police->stats);
+		if (qdisc_copy_stats(skb, &n->police->stats))
+			goto rtattr_failure;
 	}
 #endif
 	return skb->len;
diff --git a/net/sched/estimator.c b/net/sched/estimator.c
index d51017c84..e70066f9c 100644
--- a/net/sched/estimator.c
+++ b/net/sched/estimator.c
@@ -97,29 +97,38 @@ struct qdisc_estimator_head
 
 static struct qdisc_estimator_head elist[EST_MAX_INTERVAL+1];
 
+/* Estimator array lock */
+static rwlock_t est_lock = RW_LOCK_UNLOCKED;
+
 static void est_timer(unsigned long arg)
 {
 	int idx = (int)arg;
 	struct qdisc_estimator *e;
 
+	read_lock(&est_lock);
 	for (e = elist[idx].list; e; e = e->next) {
-		u64 nbytes = e->stats->bytes;
-		u32 npackets = e->stats->packets;
+		struct tc_stats *st = e->stats;
+		u64 nbytes;
+		u32 npackets;
 		u32 rate;
-		
+
+		spin_lock(st->lock);
+		nbytes = st->bytes;
+		npackets = st->packets;
 		rate = (nbytes - e->last_bytes)<<(7 - idx);
 		e->last_bytes = nbytes;
 		e->avbps += ((long)rate - (long)e->avbps) >> e->ewma_log;
-		e->stats->bps = (e->avbps+0xF)>>5;
+		st->bps = (e->avbps+0xF)>>5;
 
 		rate = (npackets - e->last_packets)<<(12 - idx);
 		e->last_packets = npackets;
 		e->avpps += ((long)rate - (long)e->avpps) >> e->ewma_log;
 		e->stats->pps = (e->avpps+0x1FF)>>10;
+		spin_unlock(st->lock);
 	}
 
-	elist[idx].timer.expires = jiffies + ((HZ/4)<<idx);
-	add_timer(&elist[idx].timer);
+	mod_timer(&elist[idx].timer, jiffies + ((HZ/4)<<idx));
+	read_unlock(&est_lock);
 }
 
 int qdisc_new_estimator(struct tc_stats *stats, struct rtattr *opt)
@@ -154,7 +163,9 @@ int qdisc_new_estimator(struct tc_stats *stats, struct rtattr *opt)
 		elist[est->interval].timer.function = est_timer;
 		add_timer(&elist[est->interval].timer);
 	}
+	write_lock_bh(&est_lock);
 	elist[est->interval].list = est;
+	write_unlock_bh(&est_lock);
 	return 0;
 }
 
@@ -172,8 +183,9 @@ void qdisc_kill_estimator(struct tc_stats *stats)
 				continue;
 			}
 
+			write_lock_bh(&est_lock);
 			*pest = est->next;
-			synchronize_bh();
+			write_unlock_bh(&est_lock);
 
 			kfree(est);
 			killed++;
diff --git a/net/sched/police.c b/net/sched/police.c
index 89e58d8be..f81f89aed 100644
--- a/net/sched/police.c
+++ b/net/sched/police.c
@@ -38,6 +38,10 @@
 
 static u32 idx_gen;
 static struct tcf_police *tcf_police_ht[16];
+/* Policer hash table lock */
+static rwlock_t police_lock = RW_LOCK_UNLOCKED;
+
+/* Each policer is serialized by its individual spinlock */
 
 static __inline__ unsigned tcf_police_hash(u32 index)
 {
@@ -48,11 +52,13 @@ static __inline__ struct tcf_police * tcf_police_lookup(u32 index)
 {
 	struct tcf_police *p;
 
+	read_lock(&police_lock);
 	for (p = tcf_police_ht[tcf_police_hash(index)]; p; p = p->next) {
 		if (p->index == index)
-			return p;
+			break;
 	}
-	return NULL;
+	read_unlock(&police_lock);
+	return p;
 }
 
 static __inline__ u32 tcf_police_new_index(void)
@@ -73,7 +79,9 @@ void tcf_police_destroy(struct tcf_police *p)
 	
 	for (p1p = &tcf_police_ht[h]; *p1p; p1p = &(*p1p)->next) {
 		if (*p1p == p) {
+			write_lock_bh(&police_lock);
 			*p1p = p->next;
+			write_unlock_bh(&police_lock);
 #ifdef CONFIG_NET_ESTIMATOR
 			qdisc_kill_estimator(&p->stats);
 #endif
@@ -114,6 +122,8 @@ struct tcf_police * tcf_police_locate(struct rtattr *rta, struct rtattr *est)
 
 	memset(p, 0, sizeof(*p));
 	p->refcnt = 1;
+	spin_lock_init(&p->lock);
+	p->stats.lock = &p->lock;
 	if (parm->rate.rate) {
 		if ((p->R_tab = qdisc_get_rtab(&parm->rate, tb[TCA_POLICE_RATE-1])) == NULL)
 			goto failure;
@@ -144,8 +154,10 @@ struct tcf_police * tcf_police_locate(struct rtattr *rta, struct rtattr *est)
 		qdisc_new_estimator(&p->stats, est);
 #endif
 	h = tcf_police_hash(p->index);
+	write_lock_bh(&police_lock);
 	p->next = tcf_police_ht[h];
 	tcf_police_ht[h] = p;
+	write_unlock_bh(&police_lock);
 	return p;
 
 failure:
@@ -161,19 +173,24 @@ int tcf_police(struct sk_buff *skb, struct tcf_police *p)
 	long toks;
 	long ptoks = 0;
 
+	spin_lock(&p->lock);
+
 	p->stats.bytes += skb->len;
 	p->stats.packets++;
 
 #ifdef CONFIG_NET_ESTIMATOR
 	if (p->ewma_rate && p->stats.bps >= p->ewma_rate) {
 		p->stats.overlimits++;
+		spin_unlock(&p->lock);
 		return p->action;
 	}
 #endif
 
 	if (skb->len <= p->mtu) {
-		if (p->R_tab == NULL)
+		if (p->R_tab == NULL) {
+			spin_unlock(&p->lock);
 			return p->result;
+		}
 
 		PSCHED_GET_TIME(now);
 
@@ -194,11 +211,13 @@ int tcf_police(struct sk_buff *skb, struct tcf_police *p)
 			p->t_c = now;
 			p->toks = toks;
 			p->ptoks = ptoks;
+			spin_unlock(&p->lock);
 			return p->result;
 		}
 	}
 
 	p->stats.overlimits++;
+	spin_unlock(&p->lock);
 	return p->action;
 }
 
diff --git a/net/sched/sch_api.c b/net/sched/sch_api.c
index 0ced70bbc..fec6faefe 100644
--- a/net/sched/sch_api.c
+++ b/net/sched/sch_api.c
@@ -124,6 +124,10 @@ static int tclass_notify(struct sk_buff *oskb, struct nlmsghdr *n,
    changes qdisc parameters.
  */
 
+/* Protects list of registered TC modules. It is pure SMP lock. */
+static rwlock_t qdisc_mod_lock = RW_LOCK_UNLOCKED;
+
+
 /************************************************
  *	Queueing disciplines manipulation.	*
  ************************************************/
@@ -139,9 +143,13 @@ int register_qdisc(struct Qdisc_ops *qops)
 {
 	struct Qdisc_ops *q, **qp;
 
-	for (qp = &qdisc_base; (q=*qp)!=NULL; qp = &q->next)
-		if (strcmp(qops->id, q->id) == 0)
+	write_lock(&qdisc_mod_lock);
+	for (qp = &qdisc_base; (q=*qp)!=NULL; qp = &q->next) {
+		if (strcmp(qops->id, q->id) == 0) {
+			write_unlock(&qdisc_mod_lock);
 			return -EEXIST;
+		}
+	}
 
 	if (qops->enqueue == NULL)
 		qops->enqueue = noop_qdisc_ops.enqueue;
@@ -152,20 +160,26 @@ int register_qdisc(struct Qdisc_ops *qops)
 
 	qops->next = NULL;
 	*qp = qops;
+	write_unlock(&qdisc_mod_lock);
 	return 0;
 }
 
 int unregister_qdisc(struct Qdisc_ops *qops)
 {
 	struct Qdisc_ops *q, **qp;
+	int err = -ENOENT;
+
+	write_lock(&qdisc_mod_lock);
 	for (qp = &qdisc_base; (q=*qp)!=NULL; qp = &q->next)
 		if (q == qops)
 			break;
-	if (!q)
-		return -ENOENT;
-	*qp = q->next;
-	q->next = NULL;
-	return 0;
+	if (q) {
+		*qp = q->next;
+		q->next = NULL;
+		err = 0;
+	}
+	write_unlock(&qdisc_mod_lock);
+	return err;
 }
 
 /* We know handle. Find qdisc among all qdisc's attached to device
@@ -203,15 +217,17 @@ struct Qdisc *qdisc_leaf(struct Qdisc *p, u32 classid)
 
 struct Qdisc_ops *qdisc_lookup_ops(struct rtattr *kind)
 {
-	struct Qdisc_ops *q;
+	struct Qdisc_ops *q = NULL;
 
 	if (kind) {
+		read_lock(&qdisc_mod_lock);
 		for (q = qdisc_base; q; q = q->next) {
 			if (rtattr_strcmp(kind, q->id) == 0)
-				return q;
+				break;
 		}
+		read_unlock(&qdisc_mod_lock);
 	}
-	return NULL;
+	return q;
 }
 
 static struct qdisc_rate_table *qdisc_rtab_list;
@@ -284,7 +300,8 @@ dev_graft_qdisc(struct device *dev, struct Qdisc *qdisc)
 	if (dev->flags & IFF_UP)
 		dev_deactivate(dev);
 
-	start_bh_atomic();
+	write_lock(&qdisc_tree_lock);
+	spin_lock_bh(&dev->queue_lock);
 	oqdisc = dev->qdisc_sleeping;
 
 	/* Prune old scheduler */
@@ -296,7 +313,8 @@ dev_graft_qdisc(struct device *dev, struct Qdisc *qdisc)
 		qdisc = &noop_qdisc;
 	dev->qdisc_sleeping = qdisc;
 	dev->qdisc = &noop_qdisc;
-	end_bh_atomic();
+	spin_unlock_bh(&dev->queue_lock);
+	write_unlock(&qdisc_tree_lock);
 
 	if (dev->flags & IFF_UP)
 		dev_activate(dev);
@@ -376,7 +394,7 @@ qdisc_create(struct device *dev, u32 handle, struct rtattr **tca, int *errp)
 		goto err_out;
 
 	/* Grrr... Resolve race condition with module unload */
-	
+
 	err = -EINVAL;
 	if (ops != qdisc_lookup_ops(kind))
 		goto err_out;
@@ -389,6 +407,7 @@ qdisc_create(struct device *dev, u32 handle, struct rtattr **tca, int *errp)
 	sch->dequeue = ops->dequeue;
 	sch->dev = dev;
 	atomic_set(&sch->refcnt, 1);
+	sch->stats.lock = &dev->queue_lock;
 	if (handle == 0) {
 		handle = qdisc_alloc_handle(dev);
 		err = -ENOMEM;
@@ -398,8 +417,10 @@ qdisc_create(struct device *dev, u32 handle, struct rtattr **tca, int *errp)
 	sch->handle = handle;
 
 	if (!ops->init || (err = ops->init(sch, tca[TCA_OPTIONS-1])) == 0) {
+		write_lock(&qdisc_tree_lock);
 		sch->next = dev->qdisc_list;
 		dev->qdisc_list = sch;
+		write_unlock(&qdisc_tree_lock);
 #ifdef CONFIG_NET_ESTIMATOR
 		if (tca[TCA_RATE-1])
 			qdisc_new_estimator(&sch->stats, tca[TCA_RATE-1]);
@@ -521,7 +542,9 @@ static int tc_get_qdisc(struct sk_buff *skb, struct nlmsghdr *n, void *arg)
 			return err;
 		if (q) {
 			qdisc_notify(skb, n, clid, q, NULL);
+			spin_lock_bh(&dev->queue_lock);
 			qdisc_destroy(q);
+			spin_unlock_bh(&dev->queue_lock);
 		}
 	} else {
 		qdisc_notify(skb, n, clid, NULL, q);
@@ -637,17 +660,36 @@ graft:
 		struct Qdisc *old_q = NULL;
 		err = qdisc_graft(dev, p, clid, q, &old_q);
 		if (err) {
-			if (q)
+			if (q) {
+				spin_lock_bh(&dev->queue_lock);
 				qdisc_destroy(q);
+				spin_unlock_bh(&dev->queue_lock);
+			}
 			return err;
 		}
 		qdisc_notify(skb, n, clid, old_q, q);
-		if (old_q)
+		if (old_q) {
+			spin_lock_bh(&dev->queue_lock);
 			qdisc_destroy(old_q);
+			spin_unlock_bh(&dev->queue_lock);
+		}
 	}
 	return 0;
 }
 
+int qdisc_copy_stats(struct sk_buff *skb, struct tc_stats *st)
+{
+	spin_lock_bh(st->lock);
+	RTA_PUT(skb, TCA_STATS, (char*)&st->lock - (char*)st, st);
+	spin_unlock_bh(st->lock);
+	return 0;
+
+rtattr_failure:
+	spin_unlock_bh(st->lock);
+	return -1;
+}
+
+
 static int tc_fill_qdisc(struct sk_buff *skb, struct Qdisc *q, u32 clid,
 			 u32 pid, u32 seq, unsigned flags, int event)
 {
@@ -667,7 +709,8 @@ static int tc_fill_qdisc(struct sk_buff *skb, struct Qdisc *q, u32 clid,
 	if (q->ops->dump && q->ops->dump(q, skb) < 0)
 		goto rtattr_failure;
 	q->stats.qlen = q->q.qlen;
-	RTA_PUT(skb, TCA_STATS, sizeof(q->stats), &q->stats);
+	if (qdisc_copy_stats(skb, &q->stats))
+		goto rtattr_failure;
 	nlh->nlmsg_len = skb->tail - b;
 	return skb->len;
 
@@ -713,22 +756,29 @@ static int tc_dump_qdisc(struct sk_buff *skb, struct netlink_callback *cb)
 
 	s_idx = cb->args[0];
 	s_q_idx = q_idx = cb->args[1];
+	read_lock(&dev_base_lock);
 	for (dev=dev_base, idx=0; dev; dev = dev->next, idx++) {
 		if (idx < s_idx)
 			continue;
 		if (idx > s_idx)
 			s_q_idx = 0;
+		read_lock(&qdisc_tree_lock);
 		for (q = dev->qdisc_list, q_idx = 0; q;
 		     q = q->next, q_idx++) {
 			if (q_idx < s_q_idx)
 				continue;
 			if (tc_fill_qdisc(skb, q, 0, NETLINK_CB(cb->skb).pid,
-					  cb->nlh->nlmsg_seq, NLM_F_MULTI, RTM_NEWQDISC) <= 0)
+					  cb->nlh->nlmsg_seq, NLM_F_MULTI, RTM_NEWQDISC) <= 0) {
+				read_unlock(&qdisc_tree_lock);
 				goto done;
+			}
 		}
+		read_unlock(&qdisc_tree_lock);
 	}
 
 done:
+	read_unlock(&dev_base_lock);
+
 	cb->args[0] = idx;
 	cb->args[1] = q_idx;
 
@@ -933,6 +983,7 @@ static int tc_dump_tclass(struct sk_buff *skb, struct netlink_callback *cb)
 
 	s_t = cb->args[0];
 
+	read_lock(&qdisc_tree_lock);
 	for (q=dev->qdisc_list, t=0; q; q = q->next, t++) {
 		if (t < s_t) continue;
 		if (!q->ops->cl_ops) continue;
@@ -951,6 +1002,7 @@ static int tc_dump_tclass(struct sk_buff *skb, struct netlink_callback *cb)
 		if (arg.w.stop)
 			break;
 	}
+	read_unlock(&qdisc_tree_lock);
 
 	cb->args[0] = t;
 
diff --git a/net/sched/sch_cbq.c b/net/sched/sch_cbq.c
index c8094a882..2244b68ed 100644
--- a/net/sched/sch_cbq.c
+++ b/net/sched/sch_cbq.c
@@ -1417,6 +1417,7 @@ static int cbq_init(struct Qdisc *sch, struct rtattr *opt)
 	q->link.ewma_log = TC_CBQ_DEF_EWMA;
 	q->link.avpkt = q->link.allot/2;
 	q->link.minidle = -0x7FFFFFFF;
+	q->link.stats.lock = &sch->dev->queue_lock;
 
 	init_timer(&q->wd_timer);
 	q->wd_timer.data = (unsigned long)sch;
@@ -1558,6 +1559,16 @@ static int cbq_dump_attr(struct sk_buff *skb, struct cbq_class *cl)
 	return 0;
 }
 
+int cbq_copy_xstats(struct sk_buff *skb, struct tc_cbq_xstats *st)
+{
+	RTA_PUT(skb, TCA_STATS, sizeof(*st), st);
+	return 0;
+
+rtattr_failure:
+	return -1;
+}
+
+
 static int cbq_dump(struct Qdisc *sch, struct sk_buff *skb)
 {
 	struct cbq_sched_data *q = (struct cbq_sched_data*)sch->data;
@@ -1569,8 +1580,13 @@ static int cbq_dump(struct Qdisc *sch, struct sk_buff *skb)
 	if (cbq_dump_attr(skb, &q->link) < 0)
 		goto rtattr_failure;
 	rta->rta_len = skb->tail - b;
+	spin_lock_bh(&sch->dev->queue_lock);
 	q->link.xstats.avgidle = q->link.avgidle;
-	RTA_PUT(skb, TCA_XSTATS, sizeof(q->link.xstats), &q->link.xstats);
+	if (cbq_copy_xstats(skb, &q->link.xstats)) {
+		spin_unlock_bh(&sch->dev->queue_lock);
+		goto rtattr_failure;
+	}
+	spin_unlock_bh(&sch->dev->queue_lock);
 	return skb->len;
 
 rtattr_failure:
@@ -1600,12 +1616,19 @@ cbq_dump_class(struct Qdisc *sch, unsigned long arg,
 		goto rtattr_failure;
 	rta->rta_len = skb->tail - b;
 	cl->stats.qlen = cl->q->q.qlen;
-	RTA_PUT(skb, TCA_STATS, sizeof(cl->stats), &cl->stats);
+	if (qdisc_copy_stats(skb, &cl->stats))
+		goto rtattr_failure;
+	spin_lock_bh(&sch->dev->queue_lock);
 	cl->xstats.avgidle = cl->avgidle;
 	cl->xstats.undertime = 0;
 	if (!PSCHED_IS_PASTPERFECT(cl->undertime))
 		cl->xstats.undertime = PSCHED_TDIFF(cl->undertime, q->now);
-	RTA_PUT(skb, TCA_XSTATS, sizeof(cl->xstats), &cl->xstats);
+	q->link.xstats.avgidle = q->link.avgidle;
+	if (cbq_copy_xstats(skb, &cl->xstats)) {
+		spin_unlock_bh(&sch->dev->queue_lock);
+		goto rtattr_failure;
+	}
+	spin_unlock_bh(&sch->dev->queue_lock);
 
 	return skb->len;
 
@@ -1631,8 +1654,11 @@ static int cbq_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
 				new->reshape_fail = cbq_reshape_fail;
 #endif
 		}
-		if ((*old = xchg(&cl->q, new)) != NULL)
-			qdisc_reset(*old);
+		sch_tree_lock(sch);
+		*old = cl->q;
+		cl->q = new;
+		qdisc_reset(*old);
+		sch_tree_unlock(sch);
 
 		return 0;
 	}
@@ -1710,16 +1736,16 @@ static void cbq_put(struct Qdisc *sch, unsigned long arg)
 	struct cbq_sched_data *q = (struct cbq_sched_data *)sch->data;
 	struct cbq_class *cl = (struct cbq_class*)arg;
 
-	start_bh_atomic();
 	if (--cl->refcnt == 0) {
 #ifdef CONFIG_NET_CLS_POLICE
+		spin_lock_bh(&sch->dev->queue_lock);
 		if (q->rx_class == cl)
 			q->rx_class = NULL;
+		spin_unlock_bh(&sch->dev->queue_lock);
 #endif
+
 		cbq_destroy_class(cl);
 	}
-	end_bh_atomic();
-	return;
 }
 
 static int
@@ -1780,7 +1806,7 @@ cbq_change_class(struct Qdisc *sch, u32 classid, u32 parentid, struct rtattr **t
 		}
 
 		/* Change class parameters */
-		start_bh_atomic();
+		sch_tree_lock(sch);
 
 		if (cl->next_alive != NULL)
 			cbq_deactivate_class(cl);
@@ -1812,7 +1838,7 @@ cbq_change_class(struct Qdisc *sch, u32 classid, u32 parentid, struct rtattr **t
 		if (cl->q->q.qlen)
 			cbq_activate_class(cl);
 
-		end_bh_atomic();
+		sch_tree_lock(sch);
 
 #ifdef CONFIG_NET_ESTIMATOR
 		if (tca[TCA_RATE-1]) {
@@ -1878,8 +1904,9 @@ cbq_change_class(struct Qdisc *sch, u32 classid, u32 parentid, struct rtattr **t
 	cl->allot = parent->allot;
 	cl->quantum = cl->allot;
 	cl->weight = cl->R_tab->rate.rate;
+	cl->stats.lock = &sch->dev->queue_lock;
 
-	start_bh_atomic();
+	sch_tree_lock(sch);
 	cbq_link_class(cl);
 	cl->borrow = cl->tparent;
 	if (cl->tparent != &q->link)
@@ -1903,7 +1930,7 @@ cbq_change_class(struct Qdisc *sch, u32 classid, u32 parentid, struct rtattr **t
 #endif
 	if (tb[TCA_CBQ_FOPT-1])
 		cbq_set_fopt(cl, RTA_DATA(tb[TCA_CBQ_FOPT-1]));
-	end_bh_atomic();
+	sch_tree_unlock(sch);
 
 #ifdef CONFIG_NET_ESTIMATOR
 	if (tca[TCA_RATE-1])
@@ -1926,7 +1953,7 @@ static int cbq_delete(struct Qdisc *sch, unsigned long arg)
 	if (cl->filters || cl->children || cl == &q->link)
 		return -EBUSY;
 
-	start_bh_atomic();
+	sch_tree_lock(sch);
 
 	if (cl->next_alive)
 		cbq_deactivate_class(cl);
@@ -1948,12 +1975,11 @@ static int cbq_delete(struct Qdisc *sch, unsigned long arg)
 	cbq_sync_defmap(cl);
 
 	cbq_rmprio(q, cl);
+	sch_tree_unlock(sch);
 
 	if (--cl->refcnt == 0)
 		cbq_destroy_class(cl);
 
-	end_bh_atomic();
-
 	return 0;
 }
 
diff --git a/net/sched/sch_csz.c b/net/sched/sch_csz.c
index 2202fd81a..c1be3729e 100644
--- a/net/sched/sch_csz.c
+++ b/net/sched/sch_csz.c
@@ -885,7 +885,7 @@ static int csz_change(struct Qdisc *sch, u32 handle, u32 parent, struct rtattr *
 
 		a = &q->flow[cl];
 
-		start_bh_atomic();	
+		spin_lock_bh(&sch->dev->queue_lock);
 #if 0
 		a->rate_log = copt->rate_log;
 #endif
@@ -899,7 +899,7 @@ static int csz_change(struct Qdisc *sch, u32 handle, u32 parent, struct rtattr *
 		if (tb[TCA_CSZ_RTAB-1])
 			memcpy(a->L_tab, RTA_DATA(tb[TCA_CSZ_RTAB-1]), 1024);
 
-		end_bh_atomic();
+		spin_unlock_bh(&sch->dev->queue_lock);
 		return 0;
 	}
 	/* NI */
@@ -920,14 +920,14 @@ static int csz_delete(struct Qdisc *sch, unsigned long cl)
 
 	a = &q->flow[cl];
 
-	start_bh_atomic();
+	spin_lock_bh(&sch->dev->queue_lock);
 	a->fprev->fnext = a->fnext;
 	a->fnext->fprev = a->fprev;
 	a->sprev->snext = a->snext;
 	a->snext->sprev = a->sprev;
 	a->start = a->finish = 0;
 	kfree(xchg(&q->flow[cl].L_tab, NULL));
-	end_bh_atomic();
+	spin_unlock_bh(&sch->dev->queue_lock);
 
 	return 0;
 }
diff --git a/net/sched/sch_generic.c b/net/sched/sch_generic.c
index ba40033e5..2dc1ed327 100644
--- a/net/sched/sch_generic.c
+++ b/net/sched/sch_generic.c
@@ -34,7 +34,45 @@
 
 /* Main transmission queue. */
 
-struct Qdisc_head qdisc_head = { &qdisc_head };
+struct Qdisc_head qdisc_head = { &qdisc_head, &qdisc_head };
+spinlock_t qdisc_runqueue_lock = SPIN_LOCK_UNLOCKED;
+
+/* Main qdisc structure lock. 
+
+   However, modifications
+   to data, participating in scheduling must be additionally
+   protected with dev->queue_lock spinlock.
+
+   The idea is the following:
+   - enqueue, dequeue are serialized via top level device
+     spinlock dev->queue_lock.
+   - tree walking is protected by read_lock(qdisc_tree_lock)
+     and this lock is used only in process context.
+   - updates to tree are made only under rtnl semaphore,
+     hence this lock may be made without local bh disabling.
+
+   qdisc_tree_lock must be grabbed BEFORE dev->queue_lock!
+ */
+rwlock_t qdisc_tree_lock = RW_LOCK_UNLOCKED;
+
+/* Anti deadlock rules:
+
+   qdisc_runqueue_lock protects main transmission list qdisc_head.
+   Run list is accessed only under this spinlock.
+
+   dev->queue_lock serializes queue accesses for this device
+   AND dev->qdisc pointer itself.
+
+   dev->xmit_lock serializes accesses to device driver.
+
+   dev->queue_lock and dev->xmit_lock are mutually exclusive,
+   if one is grabbed, another must be free.
+
+   qdisc_runqueue_lock may be requested under dev->queue_lock,
+   but neither dev->queue_lock nor dev->xmit_lock may be requested
+   under qdisc_runqueue_lock.
+ */
+
 
 /* Kick device.
    Note, that this procedure can be called by a watchdog timer, so that
@@ -44,7 +82,7 @@ struct Qdisc_head qdisc_head = { &qdisc_head };
             >0  - queue is not empty, but throttled.
 	    <0  - queue is not empty. Device is throttled, if dev->tbusy != 0.
 
-   NOTE: Called only from NET BH
+   NOTE: Called under dev->queue_lock with locally disabled BH.
 */
 
 int qdisc_restart(struct device *dev)
@@ -53,27 +91,97 @@ int qdisc_restart(struct device *dev)
 	struct sk_buff *skb;
 
 	if ((skb = q->dequeue(q)) != NULL) {
+		/* Dequeue packet and release queue */
+		spin_unlock(&dev->queue_lock);
+
 		if (netdev_nit)
 			dev_queue_xmit_nit(skb, dev);
 
-		if (dev->hard_start_xmit(skb, dev) == 0) {
-			q->tx_last = jiffies;
-			return -1;
+		if (spin_trylock(&dev->xmit_lock)) {
+			/* Remember that the driver is grabbed by us. */
+			dev->xmit_lock_owner = smp_processor_id();
+			if (dev->hard_start_xmit(skb, dev) == 0) {
+				dev->xmit_lock_owner = -1;
+				spin_unlock(&dev->xmit_lock);
+
+				spin_lock(&dev->queue_lock);
+				dev->qdisc->tx_last = jiffies;
+				return -1;
+			}
+			/* Release the driver */
+			dev->xmit_lock_owner = -1;
+			spin_unlock(&dev->xmit_lock);
+		} else {
+			/* So, someone grabbed the driver. */
+
+			/* It may be transient configuration error,
+			   when hard_start_xmit() recurses. We detect
+			   it by checking xmit owner and drop the
+			   packet when deadloop is detected.
+			 */
+			if (dev->xmit_lock_owner == smp_processor_id()) {
+				kfree_skb(skb);
+				if (net_ratelimit())
+					printk(KERN_DEBUG "Dead loop on virtual %s, fix it urgently!\n", dev->name);
+				spin_lock(&dev->queue_lock);
+				return -1;
+			}
+
+			/* Otherwise, packet is requeued
+			   and will be sent by the next net_bh run.
+			 */
+			mark_bh(NET_BH);
 		}
 
 		/* Device kicked us out :(
 		   This is possible in three cases:
 
+		   0. driver is locked
 		   1. fastroute is enabled
 		   2. device cannot determine busy state
 		      before start of transmission (f.e. dialout)
 		   3. device is buggy (ppp)
 		 */
 
+		spin_lock(&dev->queue_lock);
+		q = dev->qdisc;
 		q->ops->requeue(skb, q);
 		return -1;
 	}
-	return q->q.qlen;
+	return dev->qdisc->q.qlen;
+}
+
+static __inline__ void
+qdisc_stop_run(struct Qdisc *q)
+{
+	q->h.forw->back = q->h.back;
+	q->h.back->forw = q->h.forw;
+	q->h.forw = NULL;
+}
+
+extern __inline__ void
+qdisc_continue_run(struct Qdisc *q)
+{
+	if (!qdisc_on_runqueue(q) && q->dev) {
+		q->h.forw = &qdisc_head;
+		q->h.back = qdisc_head.back;
+		qdisc_head.back->forw = &q->h;
+		qdisc_head.back = &q->h;
+	}
+}
+
+static __inline__ int
+qdisc_init_run(struct Qdisc_head *lh)
+{
+	if (qdisc_head.forw != &qdisc_head) {
+		*lh = qdisc_head;
+		lh->forw->back = lh;
+		lh->back->forw = lh;
+		qdisc_head.forw = &qdisc_head;
+		qdisc_head.back = &qdisc_head;
+		return 1;
+	}
+	return 0;
 }
 
 /* Scan transmission queue and kick devices.
@@ -84,58 +192,90 @@ int qdisc_restart(struct device *dev)
    I have no idea how to solve it using only "anonymous" Linux mark_bh().
 
    To change queue from device interrupt? Ough... only not this...
+
+   This function is called only from net_bh.
  */
 
 void qdisc_run_queues(void)
 {
-	struct Qdisc_head **hp, *h;
+	struct Qdisc_head lh, *h;
+
+	spin_lock(&qdisc_runqueue_lock);
+	if (!qdisc_init_run(&lh))
+		goto out;
 
-	hp = &qdisc_head.forw;
-	while ((h = *hp) != &qdisc_head) {
-		int res = -1;
+	while ((h = lh.forw) != &lh) {
+		int res;
+		struct device *dev;
 		struct Qdisc *q = (struct Qdisc*)h;
-		struct device *dev = q->dev;
-
-		while (!dev->tbusy && (res = qdisc_restart(dev)) < 0)
-			/* NOTHING */;
-
-		/* An explanation is necessary here.
-		   qdisc_restart called dev->hard_start_xmit,
-		   if device is virtual, it could trigger one more
-		   dev_queue_xmit and a new device could appear
-		   in the active chain. In this case we cannot unlink
-		   the empty queue, because we lost the back pointer.
-		   No problem, we will unlink it during the next round.
-		 */
 
-		if (res == 0 && *hp == h) {
-			*hp = h->forw;
-			h->forw = NULL;
-			continue;
+		qdisc_stop_run(q);
+
+		dev = q->dev;
+		spin_unlock(&qdisc_runqueue_lock);
+
+		res = -1;
+		if (spin_trylock(&dev->queue_lock)) {
+			while (!dev->tbusy && (res = qdisc_restart(dev)) < 0)
+				/* NOTHING */;
+			spin_unlock(&dev->queue_lock);
 		}
-		hp = &h->forw;
+
+		spin_lock(&qdisc_runqueue_lock);
+		/* If qdisc is not empty add it to the tail of list */
+		if (res)
+			qdisc_continue_run(q);
 	}
+out:
+	spin_unlock(&qdisc_runqueue_lock);
 }
 
-/* Periodic watchdoc timer to recover from hard/soft device bugs. */
+/* Periodic watchdog timer to recover from hard/soft device bugs. */
 
 static void dev_do_watchdog(unsigned long dummy);
 
 static struct timer_list dev_watchdog =
 	{ NULL, NULL, 0L, 0L, &dev_do_watchdog };
 
+/*   This function is called only from timer */
+
 static void dev_do_watchdog(unsigned long dummy)
 {
-	struct Qdisc_head *h;
+	struct Qdisc_head lh, *h;
+
+	if (!spin_trylock(&qdisc_runqueue_lock)) {
+		/* No hurry with watchdog. */
+		mod_timer(&dev_watchdog, jiffies + HZ/10);
+		return;
+	}
 
-	for (h = qdisc_head.forw; h != &qdisc_head; h = h->forw) {
+	if (!qdisc_init_run(&lh))
+		goto out;
+
+	while ((h = lh.forw) != &lh) {
+		struct device *dev;
 		struct Qdisc *q = (struct Qdisc*)h;
-		struct device *dev = q->dev;
-		if (dev->tbusy && jiffies - q->tx_last > q->tx_timeo)
-			qdisc_restart(dev);
+
+		qdisc_stop_run(q);
+
+		dev = q->dev;
+		spin_unlock(&qdisc_runqueue_lock);
+
+		if (spin_trylock(&dev->queue_lock)) {
+			q = dev->qdisc;
+			if (dev->tbusy && jiffies - q->tx_last > q->tx_timeo)
+				qdisc_restart(dev);
+			spin_unlock(&dev->queue_lock);
+		}
+
+		spin_lock(&qdisc_runqueue_lock);
+
+		qdisc_continue_run(dev->qdisc);
 	}
-	dev_watchdog.expires = jiffies + 5*HZ;
-	add_timer(&dev_watchdog);
+
+out:
+	mod_timer(&dev_watchdog, jiffies + 5*HZ);
+	spin_unlock(&qdisc_runqueue_lock);
 }
 
 
@@ -206,7 +346,7 @@ struct Qdisc noqueue_qdisc =
 {
         { NULL }, 
 	NULL,
-	NULL,
+	noop_dequeue,
 	TCQ_F_BUILTIN,
 	&noqueue_qdisc_ops,
 };
@@ -322,6 +462,7 @@ struct Qdisc * qdisc_create_dflt(struct device *dev, struct Qdisc_ops *ops)
 	sch->enqueue = ops->enqueue;
 	sch->dequeue = ops->dequeue;
 	sch->dev = dev;
+	sch->stats.lock = &dev->queue_lock;
 	atomic_set(&sch->refcnt, 1);
 	if (!ops->init || ops->init(sch, NULL) == 0)
 		return sch;
@@ -330,42 +471,45 @@ struct Qdisc * qdisc_create_dflt(struct device *dev, struct Qdisc_ops *ops)
 	return NULL;
 }
 
+/* Under dev->queue_lock and BH! */
+
 void qdisc_reset(struct Qdisc *qdisc)
 {
 	struct Qdisc_ops *ops = qdisc->ops;
-	start_bh_atomic();
 	if (ops->reset)
 		ops->reset(qdisc);
-	end_bh_atomic();
 }
 
+/* Under dev->queue_lock and BH! */
+
 void qdisc_destroy(struct Qdisc *qdisc)
 {
 	struct Qdisc_ops *ops = qdisc->ops;
+	struct device *dev;
 
 	if (!atomic_dec_and_test(&qdisc->refcnt))
 		return;
 
+	dev = qdisc->dev;
+
 #ifdef CONFIG_NET_SCHED
-	if (qdisc->dev) {
+	if (dev) {
 		struct Qdisc *q, **qp;
-		for (qp = &qdisc->dev->qdisc_list; (q=*qp) != NULL; qp = &q->next)
+		for (qp = &qdisc->dev->qdisc_list; (q=*qp) != NULL; qp = &q->next) {
 			if (q == qdisc) {
 				*qp = q->next;
-				q->next = NULL;
 				break;
 			}
+		}
 	}
 #ifdef CONFIG_NET_ESTIMATOR
 	qdisc_kill_estimator(&qdisc->stats);
 #endif
 #endif
-	start_bh_atomic();
 	if (ops->reset)
 		ops->reset(qdisc);
 	if (ops->destroy)
 		ops->destroy(qdisc);
-	end_bh_atomic();
 	if (!(qdisc->flags&TCQ_F_BUILTIN))
 		kfree(qdisc);
 }
@@ -380,19 +524,23 @@ void dev_activate(struct device *dev)
 	 */
 
 	if (dev->qdisc_sleeping == &noop_qdisc) {
+		struct Qdisc *qdisc;
 		if (dev->tx_queue_len) {
-			struct Qdisc *qdisc;
 			qdisc = qdisc_create_dflt(dev, &pfifo_fast_ops);
 			if (qdisc == NULL) {
 				printk(KERN_INFO "%s: activation failed\n", dev->name);
 				return;
 			}
-			dev->qdisc_sleeping = qdisc;
-		} else
-			dev->qdisc_sleeping = &noqueue_qdisc;
+		} else {
+			qdisc =  &noqueue_qdisc;
+		}
+		write_lock(&qdisc_tree_lock);
+		dev->qdisc_sleeping = qdisc;
+		write_unlock(&qdisc_tree_lock);
 	}
 
-	start_bh_atomic();
+	spin_lock_bh(&dev->queue_lock);
+	spin_lock(&qdisc_runqueue_lock);
 	if ((dev->qdisc = dev->qdisc_sleeping) != &noqueue_qdisc) {
 		dev->qdisc->tx_timeo = 5*HZ;
 		dev->qdisc->tx_last = jiffies - dev->qdisc->tx_timeo;
@@ -400,51 +548,50 @@ void dev_activate(struct device *dev)
 			dev_watchdog.expires = jiffies + 5*HZ;
 		add_timer(&dev_watchdog);
 	}
-	end_bh_atomic();
+	spin_unlock(&qdisc_runqueue_lock);
+	spin_unlock_bh(&dev->queue_lock);
 }
 
 void dev_deactivate(struct device *dev)
 {
 	struct Qdisc *qdisc;
 
-	start_bh_atomic();
-
-	qdisc = xchg(&dev->qdisc, &noop_qdisc);
+	spin_lock_bh(&dev->queue_lock);
+	qdisc = dev->qdisc;
+	dev->qdisc = &noop_qdisc;
 
 	qdisc_reset(qdisc);
 
-	if (qdisc->h.forw) {
-		struct Qdisc_head **hp, *h;
-
-		for (hp = &qdisc_head.forw; (h = *hp) != &qdisc_head; hp = &h->forw) {
-			if (h == &qdisc->h) {
-				*hp = h->forw;
-				break;
-			}
-		}
-	}
-
-	end_bh_atomic();
+	spin_lock(&qdisc_runqueue_lock);
+	if (qdisc_on_runqueue(qdisc))
+		qdisc_stop_run(qdisc);
+	spin_unlock(&qdisc_runqueue_lock);
+	spin_unlock_bh(&dev->queue_lock);
 }
 
 void dev_init_scheduler(struct device *dev)
 {
+	write_lock(&qdisc_tree_lock);
+	spin_lock_bh(&dev->queue_lock);
 	dev->qdisc = &noop_qdisc;
+	spin_unlock_bh(&dev->queue_lock);
 	dev->qdisc_sleeping = &noop_qdisc;
 	dev->qdisc_list = NULL;
+	write_unlock(&qdisc_tree_lock);
 }
 
 void dev_shutdown(struct device *dev)
 {
 	struct Qdisc *qdisc;
 
-	start_bh_atomic();
+	write_lock(&qdisc_tree_lock);
+	spin_lock_bh(&dev->queue_lock);
 	qdisc = dev->qdisc_sleeping;
 	dev->qdisc = &noop_qdisc;
 	dev->qdisc_sleeping = &noop_qdisc;
 	qdisc_destroy(qdisc);
 	BUG_TRAP(dev->qdisc_list == NULL);
 	dev->qdisc_list = NULL;
-	end_bh_atomic();
+	spin_unlock_bh(&dev->queue_lock);
+	write_unlock(&qdisc_tree_lock);
 }
-
diff --git a/net/sched/sch_prio.c b/net/sched/sch_prio.c
index 5222d149d..a7069dec7 100644
--- a/net/sched/sch_prio.c
+++ b/net/sched/sch_prio.c
@@ -178,7 +178,7 @@ static int prio_tune(struct Qdisc *sch, struct rtattr *opt)
 			return -EINVAL;
 	}
 
-	start_bh_atomic();
+	sch_tree_lock(sch);
 	q->bands = qopt->bands;
 	memcpy(q->prio2band, qopt->priomap, TC_PRIO_MAX+1);
 
@@ -187,7 +187,7 @@ static int prio_tune(struct Qdisc *sch, struct rtattr *opt)
 		if (child != &noop_qdisc)
 			qdisc_destroy(child);
 	}
-	end_bh_atomic();
+	sch_tree_unlock(sch);
 
 	for (i=0; i<=TC_PRIO_MAX; i++) {
 		int band = q->prio2band[i];
@@ -195,11 +195,12 @@ static int prio_tune(struct Qdisc *sch, struct rtattr *opt)
 			struct Qdisc *child;
 			child = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops);
 			if (child) {
+				sch_tree_lock(sch);
 				child = xchg(&q->queues[band], child);
-				synchronize_bh();
 
 				if (child != &noop_qdisc)
 					qdisc_destroy(child);
+				sch_tree_unlock(sch);
 			}
 		}
 	}
@@ -265,7 +266,11 @@ static int prio_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
 	if (new == NULL)
 		new = &noop_qdisc;
 
-	*old = xchg(&q->queues[band], new);
+	sch_tree_lock(sch);
+	*old = q->queues[band];
+	q->queues[band] = new;
+	qdisc_reset(*old);
+	sch_tree_unlock(sch);
 
 	return 0;
 }
diff --git a/net/sched/sch_sfq.c b/net/sched/sch_sfq.c
index 8baf254eb..dfde116f3 100644
--- a/net/sched/sch_sfq.c
+++ b/net/sched/sch_sfq.c
@@ -387,7 +387,7 @@ static int sfq_change(struct Qdisc *sch, struct rtattr *opt)
 	if (opt->rta_len < RTA_LENGTH(sizeof(*ctl)))
 		return -EINVAL;
 
-	start_bh_atomic();
+	sch_tree_lock(sch);
 	q->quantum = ctl->quantum ? : psched_mtu(sch->dev);
 	q->perturb_period = ctl->perturb_period*HZ;
 
@@ -396,7 +396,7 @@ static int sfq_change(struct Qdisc *sch, struct rtattr *opt)
 		q->perturb_timer.expires = jiffies + q->perturb_period;
 		add_timer(&q->perturb_timer);
 	}
-	end_bh_atomic();
+	sch_tree_unlock(sch);
 	return 0;
 }
 
diff --git a/net/sched/sch_tbf.c b/net/sched/sch_tbf.c
index a4d13b628..90e469b02 100644
--- a/net/sched/sch_tbf.c
+++ b/net/sched/sch_tbf.c
@@ -308,7 +308,7 @@ static int tbf_change(struct Qdisc* sch, struct rtattr *opt)
 	if (rtab->data[max_size>>qopt->rate.cell_log] > qopt->buffer)
 		goto done;
 
-	start_bh_atomic();
+	sch_tree_lock(sch);
 	q->limit = qopt->limit;
 	q->mtu = qopt->mtu;
 	q->max_size = max_size;
@@ -317,7 +317,7 @@ static int tbf_change(struct Qdisc* sch, struct rtattr *opt)
 	q->ptokens = q->mtu;
 	rtab = xchg(&q->R_tab, rtab);
 	ptab = xchg(&q->P_tab, ptab);
-	end_bh_atomic();
+	sch_tree_unlock(sch);
 	err = 0;
 done:
 	if (rtab)
diff --git a/net/sched/sch_teql.c b/net/sched/sch_teql.c
index 66040d5e9..ffed0de11 100644
--- a/net/sched/sch_teql.c
+++ b/net/sched/sch_teql.c
@@ -125,9 +125,11 @@ teql_dequeue(struct Qdisc* sch)
 	if (skb == NULL) {
 		struct device *m = dat->m->dev.qdisc->dev;
 		if (m) {
-			m->tbusy = 0;
 			dat->m->slaves = sch;
+			spin_lock(&m->queue_lock);
+			m->tbusy = 0;
 			qdisc_restart(m);
+			spin_unlock(&m->queue_lock);
 		}
 	}
 	sch->q.qlen = dat->q.qlen + dat->m->dev.qdisc->q.qlen;
@@ -167,7 +169,9 @@ teql_destroy(struct Qdisc* sch)
 					master->slaves = NEXT_SLAVE(q);
 					if (q == master->slaves) {
 						master->slaves = NULL;
+						spin_lock_bh(&master->dev.queue_lock);
 						qdisc_reset(master->dev.qdisc);
+						spin_unlock_bh(&master->dev.queue_lock);
 					}
 				}
 				skb_queue_purge(&dat->q);
@@ -190,6 +194,9 @@ static int teql_qdisc_init(struct Qdisc *sch, struct rtattr *opt)
 	if (dev->hard_header_len > m->dev.hard_header_len)
 		return -EINVAL;
 
+	if (&m->dev == dev)
+		return -ELOOP;
+
 	q->m = m;
 
 	skb_queue_head_init(&q->q);
@@ -244,7 +251,11 @@ __teql_resolve(struct sk_buff *skb, struct sk_buff *skb_res, struct device *dev)
 			return -ENOBUFS;
 	}
 	if (neigh_event_send(n, skb_res) == 0) {
-		if (dev->hard_header(skb, dev, ntohs(skb->protocol), n->ha, NULL, skb->len) < 0) {
+		int err;
+		read_lock(&n->lock);
+		err = dev->hard_header(skb, dev, ntohs(skb->protocol), n->ha, NULL, skb->len);
+		read_unlock(&n->lock);
+		if (err < 0) {
 			neigh_release(n);
 			return -EINVAL;
 		}
@@ -295,19 +306,24 @@ restart:
 			continue;
 		}
 
-		if (q->h.forw == NULL) {
-			q->h.forw = qdisc_head.forw;
-			qdisc_head.forw = &q->h;
-		}
+		if (!qdisc_on_runqueue(q))
+			qdisc_run(q);
 
 		switch (teql_resolve(skb, skb_res, slave)) {
 		case 0:
-			if (slave->hard_start_xmit(skb, slave) == 0) {
-				master->slaves = NEXT_SLAVE(q);
-				dev->tbusy = 0;
-				master->stats.tx_packets++;
-				master->stats.tx_bytes += len;
+			if (spin_trylock(&slave->xmit_lock)) {
+				slave->xmit_lock_owner = smp_processor_id();
+				if (slave->hard_start_xmit(skb, slave) == 0) {
+					slave->xmit_lock_owner = -1;
+					spin_unlock(&slave->xmit_lock);
+					master->slaves = NEXT_SLAVE(q);
+					dev->tbusy = 0;
+					master->stats.tx_packets++;
+					master->stats.tx_bytes += len;
 					return 0;
+				}
+				slave->xmit_lock_owner = -1;
+				spin_unlock(&slave->xmit_lock);
 			}
 			if (dev->tbusy)
 				busy = 1;