sch_htb: turn intermediate classes into leaves
Subsystems (3)
PATCH 1/1 sch_htb: turn intermediate classes into leaves
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.
---
net/sched/sch_htb.c +46 -1
@@ -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;
Quoted 9 lines · 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_classchanged)-
sch_tree_lockadded inhtb_putbeforehtb_destroy_class(for consistency withhtb_deleteandhtb_destroy) - my own suggestion
->put() doesn't need the lock - if a class is deleted it must be completely unlinked in ->delete().
Quoted 2 lines
PS:
qdisc_resetadded tohtb_deleteby 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.
Quoted 28 lines
diff -Nurp
linux-2.6.19-rc6-/net/sched/sch_htb.clinux-2.6.19-rc6/net/sched/sch_htb.cnet/sched/sch_htb.c +14
-0@@ -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); +
net/sched/sch_htb.c static void htb_destroy_filters(struct t · line 1292
Quoted 10 lines
net/sched/sch_htb.c +10
-0+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.
net/sched/sch_htb.c static void htb_destroy_filters(struct t · line 1301
Quoted 9 lines
net/sched/sch_htb.c +9
-0+ 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.
net/sched/sch_htb.c static int htb_delete(struct Qdisc *sch, · line 1377
Quoted 12 lines
net/sched/sch_htb.c +5
-0+} +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.
Quoted 4 lines
net/sched/sch_htb.c +0
-0if (--cl->refcnt ==0 )htb_destroy_class (sch, cl);
net/sched/sch_htb.c static void htb_put(struct Qdisc *sch, u · line 1394
Quoted 10 lines
net/sched/sch_htb.c +4
-1@@ -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.
Quoted 5 lines · Patrick McHardy
Quoted 4 lines · Jarek Poplawski
Here is a trial to do something suggested by Patrick McHardy.
[
NET_SCHED]sch_htb:
Quoted 8 lines
Quoted 5 lines
- turn intermediate classes into leaves again when their last child is deleted (qdisc of deleted class is reused; struct
htb_classchanged)-
sch_tree_lockadded inhtb_putbeforehtb_destroy_class(for consistency withhtb_deleteandhtb_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 beforehtb_destroy_class call in htb_delete, please?
Quoted 38 lines
Quoted 2 lines
PS:
qdisc_resetadded tohtb_deleteby 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.
Quoted 32 lines
diff -Nurp
linux-2.6.19-rc6-/net/sched/sch_htb.clinux-2.6.19-rc6/net/sched/sch_htb.cnet/sched/sch_htb.c +18
-0@@ -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 ;
Quoted 8 lines
net/sched/sch_htb.c static void htb_destroy_filters(struct t · line 1292
Quoted 6 lines
net/sched/sch_htb.c +6
-0+ + 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.
Quoted 5 lines
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.
Quoted 4 lines
Quoted 4 lines
net/sched/sch_htb.c +4
-0+ parent->un.leaf.quantum = parent->quantum; + parent->un.leaf.prio = parent->prio; + parent->tokens = parent->buffer; + parent->ctokens = parent->cbuffer;
Quoted 8 lines
net/sched/sch_htb.c static void htb_destroy_filters(struct t · line 1301
Quoted 5 lines
net/sched/sch_htb.c +5
-0+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?
Quoted 9 lines
Quoted 9 lines
net/sched/sch_htb.c +2
-0+} +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);
Quoted 6 lines
net/sched/sch_htb.c static int htb_delete(struct Qdisc *sch, · line 1377
Quoted 3 lines
net/sched/sch_htb.c +3
-0+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.
Quoted 20 lines
Quoted 5 lines
net/sched/sch_htb.c +0
-0if (--cl->refcnt ==0 )htb_destroy_class (sch, cl);net/sched/sch_htb.c static void htb_put(struct Qdisc *sch, u · line 1394
Quoted 10 lines
net/sched/sch_htb.c +4
-1@@ -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 1/1 sch_htb: turn intermediate classes into leaves
In reply to Patrick McHardy[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)
---
net/sched/sch_htb.c +51 -0
@@ -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;
Quoted 6 lines · 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_classchanged)
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.
Quoted 11 lines · Patrick McHardy
Quoted 6 lines · 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_classchanged)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.
Quoted 24 lines · Jarek Poplawski
Quoted 12 lines · Patrick McHardy
Quoted 6 lines · 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_classchanged)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.
net/sched/sch_htb.c +7
-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 ;
Quoted 2 lines
I've thought this is enough, but probably you mean something else?
I missed that, thanks.
David Miller
maintainerFrom: Patrick McHardy <[email protected]>
Date: Thu, 30 Nov 2006 14:12:32 +0100
Quoted 25 lines
Quoted 24 lines · Jarek Poplawski
Quoted 12 lines · Patrick McHardy
Quoted 6 lines · 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_classchanged)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.
net/sched/sch_htb.c +7
-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 ;
Quoted 4 lines
Quoted 2 lines
I've thought this is enough, but probably you mean something else?
I missed that, thanks.
Patch applied, thanks again.