[PATCH][NET_SCHED] sch_htb: turn intermediate classes into leaves

[PATCH][NET_SCHED] sch_htb: turn intermediate classes into leaves

[Jarek Poplawski]

Here is a trial to do something suggested by Patrick McHardy. 

[NET_SCHED] sch_htb:

- turn intermediate classes into leaves again when their last child is deleted
  (qdisc of deleted class is reused; struct htb_class changed)
  
- sch_tree_lock added in htb_put before htb_destroy_class
  (for consistency with htb_delete and htb_destroy) - my own suggestion

PS: qdisc_reset added to htb_delete by P. McHardy's patch: "perform qlen
adjustment immediately in ->delete" should be reconsidered.


Signed-off-by: Jarek Poplawski <jarkao2@o2.pl>
---

diff -Nurp linux-2.6.19-rc6-/net/sched/sch_htb.c linux-2.6.19-rc6/net/sched/sch_htb.c
--- linux-2.6.19-rc6-/net/sched/sch_htb.c	2006-11-16 20:46:08.000000000 +0100
+++ linux-2.6.19-rc6/net/sched/sch_htb.c	2006-11-26 22:54:15.000000000 +0100
@@ -147,6 +147,10 @@ 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. */
 };
 
 /* TODO: maybe compute rate when size is too large .. or drop ? */
@@ -1266,6 +1270,37 @@ static void htb_destroy_filters(struct t
 	}
 }
 
+static void htb_parent_to_leaf(struct htb_sched *q, struct htb_class *cl)
+{
+	struct htb_class *parent = cl->parent;
+
+	if (!parent)
+		/* the root class */
+		return;
+
+	BUG_TRAP(!cl->level && cl->un.leaf.q && !cl->prio_activity);
+
+	if (!(parent->children.next == &cl->sibling &&
+		parent->children.prev == &cl->sibling))
+		/* not the last child */
+		return;	
+
+	parent->level = 0;
+	memset(&parent->un.inner, 0, sizeof(parent->un.inner));
+	INIT_LIST_HEAD(&parent->un.leaf.drop_list);
+	parent->un.leaf.q = cl->un.leaf.q;
+	cl->un.leaf.q = &noop_qdisc;
+	parent->un.leaf.quantum = parent->quantum;
+	parent->un.leaf.prio = parent->prio;
+	parent->tokens = parent->buffer;
+	parent->ctokens = parent->cbuffer;
+	PSCHED_GET_TIME(parent->t_c);
+	parent->cmode = HTB_CAN_SEND;
+
+	if (parent->un.leaf.q->q.qlen)
+		htb_activate(q, parent);
+}
+
 static void htb_destroy_class(struct Qdisc *sch, struct htb_class *cl)
 {
 	struct htb_sched *q = qdisc_priv(sch);
@@ -1337,6 +1372,9 @@ static int htb_delete(struct Qdisc *sch,
 	if (cl->prio_activity)
 		htb_deactivate(q, cl);
 
+	if (!cl->level)
+		htb_parent_to_leaf(q, cl);
+		
 	if (--cl->refcnt == 0)
 		htb_destroy_class(sch, cl);
 
@@ -1348,8 +1386,11 @@ static void htb_put(struct Qdisc *sch, u
 {
 	struct htb_class *cl = (struct htb_class *)arg;
 
-	if (--cl->refcnt == 0)
+	if (--cl->refcnt == 0) {
+		sch_tree_lock(sch);
 		htb_destroy_class(sch, cl);
+		sch_tree_unlock(sch);
+	}
 }
 
 static int htb_change_class(struct Qdisc *sch, u32 classid,
@@ -1468,6 +1509,10 @@ static int htb_change_class(struct Qdisc
 			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->buffer = hopt->buffer;

Re: [PATCH][NET_SCHED] sch_htb: turn intermediate classes into leaves

[Patrick McHardy]

Jarek Poplawski wrote:
> Here is a trial to do something suggested by Patrick McHardy. 
> 
> [NET_SCHED] sch_htb:
> 
> - turn intermediate classes into leaves again when their last child is deleted
>   (qdisc of deleted class is reused; struct htb_class changed)
>   
> - sch_tree_lock added in htb_put before htb_destroy_class
>   (for consistency with htb_delete and htb_destroy) - my own suggestion

->put() doesn't need the lock - if a class is deleted it must be
completely unlinked in ->delete().

> PS: qdisc_reset added to htb_delete by P. McHardy's patch: "perform qlen
> adjustment immediately in ->delete" should be reconsidered.

No, that is a necessary fix, even though it only causes a
shortly visible error.

> diff -Nurp linux-2.6.19-rc6-/net/sched/sch_htb.c linux-2.6.19-rc6/net/sched/sch_htb.c
> --- linux-2.6.19-rc6-/net/sched/sch_htb.c	2006-11-16 20:46:08.000000000 +0100
> +++ linux-2.6.19-rc6/net/sched/sch_htb.c	2006-11-26 22:54:15.000000000 +0100
> @@ -147,6 +147,10 @@ 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. */
>  };
>  
>  /* TODO: maybe compute rate when size is too large .. or drop ? */
> @@ -1266,6 +1270,37 @@ static void htb_destroy_filters(struct t
>  	}
>  }
>  
> +static void htb_parent_to_leaf(struct htb_sched *q, struct htb_class *cl)
> +{
> +	struct htb_class *parent = cl->parent;
> +
> +	if (!parent)
> +		/* the root class */
> +		return;
> +
> +	BUG_TRAP(!cl->level && cl->un.leaf.q && !cl->prio_activity);
> +
> +	if (!(parent->children.next == &cl->sibling &&
> +		parent->children.prev == &cl->sibling))
> +		/* not the last child */
> +		return;	
> +
> +	parent->level = 0;
> +	memset(&parent->un.inner, 0, sizeof(parent->un.inner));
> +	INIT_LIST_HEAD(&parent->un.leaf.drop_list);
> +	parent->un.leaf.q = cl->un.leaf.q;
> +	cl->un.leaf.q = &noop_qdisc;

default pfifo would be a better choice. Might be a bit ugly
though because you're holding the qdisc lock here and can't
call qdisc_create_dflt. Since you're already keeping backup
values from the union we could consider just turning it into
two seperate structures and keep the child qdisc when turning
a class into a parent.

> +	parent->un.leaf.quantum = parent->quantum;
> +	parent->un.leaf.prio = parent->prio;
> +	parent->tokens = parent->buffer;
> +	parent->ctokens = parent->cbuffer;
> +	PSCHED_GET_TIME(parent->t_c);
> +	parent->cmode = HTB_CAN_SEND;
> +
> +	if (parent->un.leaf.q->q.qlen)
> +		htb_activate(q, parent);

Not possible right now and even if we reuse the old child qdisc
it should be empty.

> +}
> +
>  static void htb_destroy_class(struct Qdisc *sch, struct htb_class *cl)
>  {
>  	struct htb_sched *q = qdisc_priv(sch);
> @@ -1337,6 +1372,9 @@ static int htb_delete(struct Qdisc *sch,
>  	if (cl->prio_activity)
>  		htb_deactivate(q, cl);
>  
> +	if (!cl->level)
> +		htb_parent_to_leaf(q, cl);
> +		

You have to manually adjust the classes level before checking for
zero, it is not done currently.

>  	if (--cl->refcnt == 0)
>  		htb_destroy_class(sch, cl);
>  
> @@ -1348,8 +1386,11 @@ static void htb_put(struct Qdisc *sch, u
>  {
>  	struct htb_class *cl = (struct htb_class *)arg;
>  
> -	if (--cl->refcnt == 0)
> +	if (--cl->refcnt == 0) {
> +		sch_tree_lock(sch);
>  		htb_destroy_class(sch, cl);
> +		sch_tree_unlock(sch);
> +	}
>  }

See above.

Re: [PATCH][NET_SCHED] sch_htb: turn intermediate classes into leaves

[Jarek Poplawski]

On Mon, Nov 27, 2006 at 11:12:23AM +0100, Patrick McHardy wrote:
> Jarek Poplawski wrote:
> > Here is a trial to do something suggested by Patrick McHardy. 
> > 
> > [NET_SCHED] sch_htb:
> > 
> > - turn intermediate classes into leaves again when their last child is deleted
> >   (qdisc of deleted class is reused; struct htb_class changed)
> >   
> > - sch_tree_lock added in htb_put before htb_destroy_class
> >   (for consistency with htb_delete and htb_destroy) - my own suggestion
> 
> ->put() doesn't need the lock - if a class is deleted it must be
> completely unlinked in ->delete().

Could you give me some hint why not unlock before
htb_destroy_class call in htb_delete, please?

> > PS: qdisc_reset added to htb_delete by P. McHardy's patch: "perform qlen
> > adjustment immediately in ->delete" should be reconsidered.
> 
> No, that is a necessary fix, even though it only causes a
> shortly visible error.
> 
> > diff -Nurp linux-2.6.19-rc6-/net/sched/sch_htb.c linux-2.6.19-rc6/net/sched/sch_htb.c
> > --- linux-2.6.19-rc6-/net/sched/sch_htb.c	2006-11-16 20:46:08.000000000 +0100
> > +++ linux-2.6.19-rc6/net/sched/sch_htb.c	2006-11-26 22:54:15.000000000 +0100
> > @@ -147,6 +147,10 @@ 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. */
> >  };
> >  
> >  /* TODO: maybe compute rate when size is too large .. or drop ? */
> > @@ -1266,6 +1270,37 @@ static void htb_destroy_filters(struct t
> >  	}
> >  }
> >  
> > +static void htb_parent_to_leaf(struct htb_sched *q, struct htb_class *cl)
> > +{
> > +	struct htb_class *parent = cl->parent;
> > +
> > +	if (!parent)
> > +		/* the root class */
> > +		return;
> > +
> > +	BUG_TRAP(!cl->level && cl->un.leaf.q && !cl->prio_activity);
> > +
> > +	if (!(parent->children.next == &cl->sibling &&
> > +		parent->children.prev == &cl->sibling))
> > +		/* not the last child */
> > +		return;	
> > +
> > +	parent->level = 0;
> > +	memset(&parent->un.inner, 0, sizeof(parent->un.inner));
> > +	INIT_LIST_HEAD(&parent->un.leaf.drop_list);
> > +	parent->un.leaf.q = cl->un.leaf.q;
> > +	cl->un.leaf.q = &noop_qdisc;
> 
> default pfifo would be a better choice. Might be a bit ugly

I considered this unnecessary risk. But it can be done as you
like. If I understand, you are not sure yet. 

> though because you're holding the qdisc lock here and can't
> call qdisc_create_dflt. Since you're already keeping backup
> values from the union we could consider just turning it into
> two seperate structures and keep the child qdisc when turning
> a class into a parent.

I've thought about this but it seems there could still be some
memory saving with the union - probably - with large number of
inner classes. 

> > +	parent->un.leaf.quantum = parent->quantum;
> > +	parent->un.leaf.prio = parent->prio;
> > +	parent->tokens = parent->buffer;
> > +	parent->ctokens = parent->cbuffer;
> > +	PSCHED_GET_TIME(parent->t_c);
> > +	parent->cmode = HTB_CAN_SEND;
> > +
> > +	if (parent->un.leaf.q->q.qlen)
> > +		htb_activate(q, parent);
> 
> Not possible right now and even if we reuse the old child qdisc
> it should be empty.

I'll remove this but then qdisc_reset have to be added.
Or maybe I should forget rc6 and redo this only on top
of your patch?

> > +}
> > +
> >  static void htb_destroy_class(struct Qdisc *sch, struct htb_class *cl)
> >  {
> >  	struct htb_sched *q = qdisc_priv(sch);
> > @@ -1337,6 +1372,9 @@ static int htb_delete(struct Qdisc *sch,
> >  	if (cl->prio_activity)
> >  		htb_deactivate(q, cl);
> >  
> > +	if (!cl->level)
> > +		htb_parent_to_leaf(q, cl);
> > +		
> 
> You have to manually adjust the classes level before checking for
> zero, it is not done currently.

Could you explain? Probably I miss something here.

> 
> >  	if (--cl->refcnt == 0)
> >  		htb_destroy_class(sch, cl);
> >  
> > @@ -1348,8 +1386,11 @@ static void htb_put(struct Qdisc *sch, u
> >  {
> >  	struct htb_class *cl = (struct htb_class *)arg;
> >  
> > -	if (--cl->refcnt == 0)
> > +	if (--cl->refcnt == 0) {
> > +		sch_tree_lock(sch);
> >  		htb_destroy_class(sch, cl);
> > +		sch_tree_unlock(sch);
> > +	}
> >  }
> 
> See above.
> 
> 
> 

[PATCH][NET_SCHED] sch_htb: turn intermediate classes into leaves

[Jarek Poplawski]

[NET_SCHED] sch_htb:

[PATCH 2.6.19-rc6 with "Fix endless loops" set of patches]

- turn intermediate classes into leaves again when their
  last child is deleted (struct htb_class changed)


Signed-off-by: Jarek Poplawski <jarkao2@o2.pl>
---

diff -Nurp linux-2.6.19-rc6-endless-/net/sched/sch_htb.c linux-2.6.19-rc6-endless/net/sched/sch_htb.c
--- linux-2.6.19-rc6-endless-/net/sched/sch_htb.c	2006-11-27 18:40:30.000000000 +0100
+++ linux-2.6.19-rc6-endless/net/sched/sch_htb.c	2006-11-27 20:27:52.000000000 +0100
@@ -147,6 +147,10 @@ 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. */
 };
 
 /* TODO: maybe compute rate when size is too large .. or drop ? */
@@ -1271,6 +1275,38 @@ static void htb_destroy_filters(struct t
 	}
 }
 
+static inline int htb_parent_last_child(struct htb_class *cl)
+{
+	if (!cl->parent)
+		/* the root class */
+		return 0;
+
+	if (!(cl->parent->children.next == &cl->sibling &&
+		cl->parent->children.prev == &cl->sibling))
+		/* not the last child */
+		return 0;	
+
+	return 1;
+}
+
+static void htb_parent_to_leaf(struct htb_class *cl, struct Qdisc *new_q)
+{
+	struct htb_class *parent = cl->parent;
+
+	BUG_TRAP(!cl->level && cl->un.leaf.q && !cl->prio_activity);
+
+	parent->level = 0;
+	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;
+	PSCHED_GET_TIME(parent->t_c);
+	parent->cmode = HTB_CAN_SEND;
+}
+
 static void htb_destroy_class(struct Qdisc *sch, struct htb_class *cl)
 {
 	struct htb_sched *q = qdisc_priv(sch);
@@ -1328,6 +1364,8 @@ static int htb_delete(struct Qdisc *sch,
 	struct htb_sched *q = qdisc_priv(sch);
 	struct htb_class *cl = (struct htb_class *)arg;
 	unsigned int qlen;
+	struct Qdisc *new_q = NULL;
+	int last_child = 0;
 
 	// TODO: why don't allow to delete subtree ? references ? does
 	// tc subsys quarantee us that in htb_destroy it holds no class
@@ -1335,6 +1373,12 @@ static int htb_delete(struct Qdisc *sch,
 	if (!list_empty(&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);
+		last_child = 1;
+	}
+
 	sch_tree_lock(sch);
 
 	/* delete from hash and active; remainder in destroy_class */
@@ -1349,6 +1393,9 @@ static int htb_delete(struct Qdisc *sch,
 	if (cl->prio_activity)
 		htb_deactivate(q, cl);
 
+	if (last_child)
+		htb_parent_to_leaf(cl, new_q);
+		
 	if (--cl->refcnt == 0)
 		htb_destroy_class(sch, cl);
 
@@ -1483,6 +1530,10 @@ static int htb_change_class(struct Qdisc
 			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->buffer = hopt->buffer;

Re: [PATCH][NET_SCHED] sch_htb: turn intermediate classes into leaves

[Patrick McHardy]

Jarek Poplawski wrote:
> [NET_SCHED] sch_htb:
> 
> [PATCH 2.6.19-rc6 with "Fix endless loops" set of patches]
> 
> - turn intermediate classes into leaves again when their
>   last child is deleted (struct htb_class changed)

Looks good to me too, but it still seems to be missing
class level adjustment after deletion. The classification
function refuses to queue packets to classes with level > 0.

Re: [PATCH][NET_SCHED] sch_htb: turn intermediate classes into leaves

[Jarek Poplawski]

On Thu, Nov 30, 2006 at 01:26:34PM +0100, Patrick McHardy wrote:
> Jarek Poplawski wrote:
> > [NET_SCHED] sch_htb:
> > 
> > [PATCH 2.6.19-rc6 with "Fix endless loops" set of patches]
> > 
> > - turn intermediate classes into leaves again when their
> >   last child is deleted (struct htb_class changed)
> 
> Looks good to me too, but it still seems to be missing
> class level adjustment after deletion. The classification
> function refuses to queue packets to classes with level > 0.

+static void htb_parent_to_leaf(struct htb_class *cl, struct Qdisc *new_q)
+{
+	struct htb_class *parent = cl->parent;
+
+	BUG_TRAP(!cl->level && cl->un.leaf.q && !cl->prio_activity);
+
+	parent->level = 0;

I've thought this is enough, but probably you mean something
else? 

Jarek P.

Re: [PATCH][NET_SCHED] sch_htb: turn intermediate classes into leaves

[Patrick McHardy]

Jarek Poplawski wrote:
> On Thu, Nov 30, 2006 at 01:26:34PM +0100, Patrick McHardy wrote:
> 
>>Jarek Poplawski wrote:
>>
>>>[NET_SCHED] sch_htb:
>>>
>>>[PATCH 2.6.19-rc6 with "Fix endless loops" set of patches]
>>>
>>>- turn intermediate classes into leaves again when their
>>>  last child is deleted (struct htb_class changed)
>>
>>Looks good to me too, but it still seems to be missing
>>class level adjustment after deletion. The classification
>>function refuses to queue packets to classes with level > 0.
> 
> 
> +static void htb_parent_to_leaf(struct htb_class *cl, struct Qdisc *new_q)
> +{
> +	struct htb_class *parent = cl->parent;
> +
> +	BUG_TRAP(!cl->level && cl->un.leaf.q && !cl->prio_activity);
> +
> +	parent->level = 0;
> 
> I've thought this is enough, but probably you mean something
> else? 

I missed that, thanks.

Re: [PATCH][NET_SCHED] sch_htb: turn intermediate classes into leaves

[David Miller]

From: Patrick McHardy <kaber@trash.net>
Date: Thu, 30 Nov 2006 14:12:32 +0100

> Jarek Poplawski wrote:
> > On Thu, Nov 30, 2006 at 01:26:34PM +0100, Patrick McHardy wrote:
> > 
> >>Jarek Poplawski wrote:
> >>
> >>>[NET_SCHED] sch_htb:
> >>>
> >>>[PATCH 2.6.19-rc6 with "Fix endless loops" set of patches]
> >>>
> >>>- turn intermediate classes into leaves again when their
> >>>  last child is deleted (struct htb_class changed)
> >>
> >>Looks good to me too, but it still seems to be missing
> >>class level adjustment after deletion. The classification
> >>function refuses to queue packets to classes with level > 0.
> > 
> > 
> > +static void htb_parent_to_leaf(struct htb_class *cl, struct Qdisc *new_q)
> > +{
> > +	struct htb_class *parent = cl->parent;
> > +
> > +	BUG_TRAP(!cl->level && cl->un.leaf.q && !cl->prio_activity);
> > +
> > +	parent->level = 0;
> > 
> > I've thought this is enough, but probably you mean something
> > else? 
> 
> I missed that, thanks.

Patch applied, thanks again.