[Top] [All Lists]

Re: Fw: hfsc and huge set of rules

To: Tomasz Paszkowski <tomasz.paszkowski@xxxxxxxx>
Subject: Re: Fw: hfsc and huge set of rules
From: Patrick McHardy <kaber@xxxxxxxxx>
Date: Sun, 01 Aug 2004 19:53:52 +0200
Cc: "David S. Miller" <davem@xxxxxxxxxx>, hadi@xxxxxxxxxx, devik@xxxxxx, netdev@xxxxxxxxxxx
In-reply-to: <20040730110815.GA7812@xxxxxxxxxxxxxxxx>
References: <20040729211844.61e8d328.davem@xxxxxxxxxx> <410A2449.3020701@xxxxxxxxx> <20040730110815.GA7812@xxxxxxxxxxxxxxxx>
Sender: netdev-bounce@xxxxxxxxxxx
User-agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.6) Gecko/20040413 Debian/1.6-5
Tomasz Paszkowski wrote:

On Fri, Jul 30, 2004 at 12:34:49PM +0200, Patrick McHardy wrote:
hfsc_destroy_qdisc takes O(n) time wrt. the number of classes,
but 5-6 seconds is still long. If all these classes contain inner
qdiscs other than the default, I guess removing the classes from
dev->qdisc_list in qdisc_destroy takes up most of the time, with
n O(n) operations. The __qdisc_destroy rcu callback also calls
reset before destroy, I don't know any qdisc where this is really
neccessary. Without inner qdiscs, I need to see the script first to
judge what's going wrong. Tomasz ? In my opinion it's not the case
of expensive algorithms, but the number of classes. With this rule set loaded
(tc -b tc.batch) command:

for i in 'e1.903 e0.930 e0.931 e0.932' ; do
        tc qdisc del dev ${i} root
completly freezes machine for about 5-6 seconds.
I've done some profiles with your script (on an old kernel without
the lockless loopback patch), qdisc_destroy takes up 89% of the time
when destroying the qdiscs.

These are the exact results:

- execute the script on unpatched kernel:

real    2m28.822s
user    0m2.347s
sys     2m25.395s

top 5 in profile:
799773 65.4986 vmlinux vmlinux qdisc_lookup 199964 16.3763 vmlinux vmlinux qdisc_destroy 92504 7.5758 sch_hfsc.ko sch_hfsc hfsc_adjust_levels 36722 3.0074 sch_hfsc.ko sch_hfsc hfsc_get_class 12471 1.0213 vmlinux vmlinux mark_offset_tsc

- execute the script on kernel using double-linked lists for dev->qdisc_list:

real    0m51.804s
user    0m2.286s
sys     0m48.795s

top 5 in profile:
201152 49.6049 vmlinux vmlinux qdisc_lookup 92706 22.8617 sch_hfsc.ko sch_hfsc hfsc_adjust_levels 37140 9.1589 sch_hfsc.ko sch_hfsc hfsc_get_class 12310 3.0357 sch_hfsc.ko sch_hfsc hfsc_bind_tcf 12190 3.0061 sch_hfsc.ko sch_hfsc hfsc_change_class

- destroy the qdiscs on unpatched kernel:

real    0m13.258s
user    0m0.019s
sys     0m13.206s

top 5 in profile:
29839 89.5367 vmlinux vmlinux qdisc_destroy 1229 3.6878 sch_hfsc.ko sch_hfsc hfsc_reset_class 338 1.0142 vmlinux vmlinux mark_offset_tsc 289 0.8672 vmlinux vmlinux qdisc_reset 287 0.8612 sch_hfsc.ko sch_hfsc rtsc_init

- destroy the qdiscs on kernel using double-linked lists for dev->qdisc_list:

real    0m0.389s
user    0m0.019s
sys     0m0.363s

top 5 in profile:
1261 33.6896 sch_hfsc.ko sch_hfsc hfsc_reset_class 311 8.3088 sch_hfsc.ko sch_hfsc rtsc_init 277 7.4005 vmlinux vmlinux qdisc_reset 187 4.9960 vmlinux vmlinux free_block
181       4.8357  vmlinux                  vmlinux                  kfree

So double-linked lists clearly solve your problem. Using a hash would speed up
creating the qdiscs even more, but it wastes too much memory in my opinion.
I'm going to send a patch after I've fixed the other problems with qdisc_destroy.

I was trying do modify the code od hfsc_qdisc_destroy scheduling another
task using schedule_task (), but i don't have enough knowledge to do deal
with proper locking of qdisc structures.
That doesn't work, hfsc_qdisc_destroy is called under a lock.


<Prev in Thread] Current Thread [Next in Thread>