Fw: hfsc and huge set of rules

Fw: hfsc and huge set of rules

[David S. Miller]

[-- Attachment #1: Type: text/plain, Size: 882 bytes --]


Looks like qdisc destruction has some expensive algorithms.
Any quick ideas about the root culprit at least in the hfsc
case?  He says htb does it too.

Begin forwarded message:

Date: Tue, 27 Jul 2004 11:47:02 +0200
From: Tomasz Paszkowski <tomasz.paszkowski@e-wro.pl>
To: linux-kernel@vger.kernel.org
Subject: hfsc and huge set of rules


Hello,

I'am running hfsc qdisc with huge set of rules loaded.

root@hades:/home/system/scr/etc/hfsc_rebuild# cat tc.batch | grep hfsc | wc -l
  27884


Always when I delete the root qdisc (qdisc del dev eth0 root)
the machine stop responding for about 5-6 seconds. As I think it's due the
hfsc_destory_qdisc is executed in main kernel thread. Similar problem is
present also in htb scheduler.

Is there any quick solution to solve this problem ?

-- 
Tomasz Paszkowski
Administrator
Miejskie Sieci Informatyczne e-wro
http://www.e-wro.pl


[-- Attachment #2: 00000000.mimetmp --]
[-- Type: application/pgp-signature, Size: 190 bytes --]

Re: Fw: hfsc and huge set of rules

[Patrick McHardy]

David S. Miller wrote:
> Looks like qdisc destruction has some expensive algorithms.
> Any quick ideas about the root culprit at least in the hfsc
> case?  He says htb does it too.

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 ?

BTW: The lockless loopback patch broke qdisc_destroy in multiple ways.
The rcu callback doesn't do any locking, to add locking all
read/write_lock(qdisc_tree_lock) need to be changed to
read/write_lock_bh because the callback is called from a tasklet,
until now all changes to the tree structure were made in
process-context. Additionally it invalidates the assumption made by
dev_shutdown that qdisc_destroy will destroy all qdiscs and clear
dev->qdisc_list immediately. Since qdisc->dev is not refcounted
netdev_wait_allrefs won't notice when the rcu callback hasn't destroyed
all qdiscs yet and free the device, but qdisc_destroy called from
ops->destroy called from the callback will still access the memory.
Patch coming up soon.

Regards
Patrick

> Begin forwarded message:
> 
> Date: Tue, 27 Jul 2004 11:47:02 +0200
> From: Tomasz Paszkowski <tomasz.paszkowski@e-wro.pl>
> To: linux-kernel@vger.kernel.org
> Subject: hfsc and huge set of rules
> 
> 
> Hello,
> 
> I'am running hfsc qdisc with huge set of rules loaded.
> 
> root@hades:/home/system/scr/etc/hfsc_rebuild# cat tc.batch | grep hfsc | wc -l
>   27884
> 
> 
> Always when I delete the root qdisc (qdisc del dev eth0 root)
> the machine stop responding for about 5-6 seconds. As I think it's due the
> hfsc_destory_qdisc is executed in main kernel thread. Similar problem is
> present also in htb scheduler.
> 
> Is there any quick solution to solve this problem ?
> 

Re: Fw: hfsc and huge set of rules

[Tomasz Paszkowski]

[-- Attachment #1: Type: text/plain, Size: 1306 bytes --]

On Fri, Jul 30, 2004 at 12:34:49PM +0200, Patrick McHardy wrote:
> David S. Miller wrote:
> >Looks like qdisc destruction has some expensive algorithms.
> >Any quick ideas about the root culprit at least in the hfsc
> >case?  He says htb does it too.
> 
> 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 ?

http://www.e-wro.pl/~acid/tc.batch.gz. 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
done
completly freezes machine for about 5-6 seconds.

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.

-- 
Tomasz Paszkowski

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: Fw: hfsc and huge set of rules

[devik]

Also IIRC class lookup is done before each remove. With
hashing size a few tens of buckets the complexity
starts to be very near to O(n^2).

devik

On Fri, 30 Jul 2004, Patrick McHardy wrote:

> David S. Miller wrote:
> > Looks like qdisc destruction has some expensive algorithms.
> > Any quick ideas about the root culprit at least in the hfsc
> > case?  He says htb does it too.
>
> 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 ?
>
> BTW: The lockless loopback patch broke qdisc_destroy in multiple ways.
> The rcu callback doesn't do any locking, to add locking all
> read/write_lock(qdisc_tree_lock) need to be changed to
> read/write_lock_bh because the callback is called from a tasklet,
> until now all changes to the tree structure were made in
> process-context. Additionally it invalidates the assumption made by
> dev_shutdown that qdisc_destroy will destroy all qdiscs and clear
> dev->qdisc_list immediately. Since qdisc->dev is not refcounted
> netdev_wait_allrefs won't notice when the rcu callback hasn't destroyed
> all qdiscs yet and free the device, but qdisc_destroy called from
> ops->destroy called from the callback will still access the memory.
> Patch coming up soon.
>
> Regards
> Patrick
>
> > Begin forwarded message:
> >
> > Date: Tue, 27 Jul 2004 11:47:02 +0200
> > From: Tomasz Paszkowski <tomasz.paszkowski@e-wro.pl>
> > To: linux-kernel@vger.kernel.org
> > Subject: hfsc and huge set of rules
> >
> >
> > Hello,
> >
> > I'am running hfsc qdisc with huge set of rules loaded.
> >
> > root@hades:/home/system/scr/etc/hfsc_rebuild# cat tc.batch | grep hfsc | wc -l
> >   27884
> >
> >
> > Always when I delete the root qdisc (qdisc del dev eth0 root)
> > the machine stop responding for about 5-6 seconds. As I think it's due the
> > hfsc_destory_qdisc is executed in main kernel thread. Similar problem is
> > present also in htb scheduler.
> >
> > Is there any quick solution to solve this problem ?
> >
>
>
>

Re: Fw: hfsc and huge set of rules

[jamal]

Tomasz,
Have you verified that this happens on other Linux versions
like earlier 2.4.x (2.4.21 for example)?
Also can you try just deleting the filters first and see what happens?
i.e something like:

filter add dev e0.931 protocol ip parent 1:101 pref 5
filter del dev e0.932 protocol ip parent 1:101 pref 5
..

delete them as specified above because that nips them at the
prio level.

BTW, since you are one of the few people i have seen use clever
hashing tricks with u32, could you test out u32 in 2.6.8-rc2 and
make sure it doesnt break anything? There is a bug fix that deals with 
selecting hash buckets.

cheers,
jamal

Re: Fw: hfsc and huge set of rules

[Patrick McHardy]

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 ?
>>    
>>
>
>http://www.e-wro.pl/~acid/tc.batch.gz. 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
>done
>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:

time:
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:

time:
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:

time:
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:

time:
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.

Regards
Patrick

Re: Fw: hfsc and huge set of rules

[Patrick McHardy]

devik wrote:

>Also IIRC class lookup is done before each remove. With
>hashing size a few tens of buckets the complexity
>starts to be very near to O(n^2).
>  
>
I think the hash size of HTB, HFSC and CBQ should be increased,
the hash function performs well even with 2^16. With HFSC using
many classes doesn't scale well right now, but with the rbtree patches
it will.

Regards
Patrick

>devik
>
>On Fri, 30 Jul 2004, Patrick McHardy wrote:
>
>  
>
>>David S. Miller wrote:
>>    
>>
>>>Looks like qdisc destruction has some expensive algorithms.
>>>Any quick ideas about the root culprit at least in the hfsc
>>>case?  He says htb does it too.
>>>      
>>>
>>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 ?
>>    
>>

Re: Fw: hfsc and huge set of rules

[Tomasz Paszkowski]

[-- Attachment #1: Type: text/plain, Size: 637 bytes --]

On Sun, Aug 01, 2004 at 07:53:52PM +0200, Patrick McHardy wrote:
> 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 kernel using double-linked lists for 
> dev->qdisc_list:
> 
> time:
> real    0m51.804s
> user    0m2.286s
> sys     0m48.795s

The results are great ! Thanks ! I'am using hfsc with 2.4.x kernel so there will
be no problem with lockless loopback patch ;] So could you please send me
a patch ?


-- 
Tomasz Paszkowski

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]