netdev - Re: [RFC] fib_trie: flush improvement

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <47F3E031.1030806@cosmosbay.com>
Date:	Wed, 02 Apr 2008 21:36:17 +0200
From:	Eric Dumazet <dada1@...mosbay.com>
To:	Stephen Hemminger <shemminger@...tta.com>
CC:	Robert Olsson <Robert.Olsson@...a.slu.se>,
	David Miller <davem@...emloft.net>, netdev@...r.kernel.org
Subject: Re: [RFC] fib_trie: flush improvement

Stephen Hemminger a écrit :
> On Wed, 02 Apr 2008 16:35:04 +0200
> Eric Dumazet <dada1@...mosbay.com> wrote:
> 
>> Eric Dumazet a écrit :
>>> Stephen Hemminger a écrit :
>>>> This is an attempt to fix the problem described in:
>>>>      http://bugzilla.kernel.org/show_bug.cgi?id=6648
>>>> I can reproduce this by loading lots and lots of routes and the taking
>>>> the interface down. This causes all entries in trie to be flushed, but
>>>> each leaf removal causes a rebalance of the trie. And since the removal
>>>> is depth first, it creates lots of needless work.
>>>>
>>>> Instead on flush, just walk the trie and prune as we go.
>>>> The implementation is for description only, it probably doesn't work 
>>>> yet.
>>>>
>>>>   
>>> I dont get it, since the bug reporter mentions with recent kernels :
>>>
>>> Fix inflate_threshold_root. Now=15 size=11 bits
>>>
>>> Is it what you get with your tests ?
>>>
>>> Pawel reports :
>>>
>>> cat /proc/net/fib_triestat
>>> Main: Aver depth: 2.26 Max depth: 6 Leaves: 235924
>>> Internal nodes: 57854 1: 31632 2: 11422 3: 8475 4: 3755 5: 1676 6: 893 
>>> 18: 1
>>>
>>> Pointers: 609760 Null ptrs: 315983 Total size: 16240 kB
>>>
>>> warning messages comes from rootnode that cannot be expanded, since it 
>>> hits MAX_ORDER (on a 32bit x86)
>>>
>>>
>>>
>>> (sizeof(struct tnode) + (sizeof(struct node *) << bits);) is rounded 
>>> to 4 << (bit + 1), ie 2 << 20
>>>
>>> For larger allocations Pawel has two choices :
>>>
>>> change MAX_ORDER from 11 to 13 or 14
>>> If this machine is a pure router, this change wont have performance 
>>> impact.
>>>
>>> Or (more difficult, but more appropriate for mainline) change 
>>> fib_trie.c to use vmalloc() for very big allocaions (for the root 
>>> only), and vfree()
>>>
>>> Since vfree() cannot be called from rcu callback, one has to setup a 
>>> struct work_struct helper.
>>>
>> Here is a patch (untested unfortunatly) to implement this.
>>
>> [IPV4] fib_trie: root_tnode can benefit of vmalloc()
>>
>> FIB_TRIE root node can be very large and currently hits MAX_ORDER limit.
>> It also wastes about 50% of allocated size, because of power of two 
>> rounding of tnode.
>>
>> A switch to vmalloc() can improve FIB_TRIE performance by allowing root 
>> node to grow
>> past the alloc_pages() limit, while preserving memory.
>>
>> Special care must be taken to free such zone, as rcu handler is not 
>> allowed to call vfree(),
>> we use a worker instead.
>>
>> Signed-off-by: Eric Dumazet <dada1@...mosbay.com>
>>
>>
> 
> Rather than switching between three allocation strategies, I would rather
> just have kmalloc and vmalloc.

Yes, probably :)

[IPV4] fib_trie: root_tnode can benefit of vmalloc()

FIB_TRIE root node can be very large and currently hits MAX_ORDER limit.
It also wastes about 50% of allocated size, because of power of two
rounding of tnode.

A switch to vmalloc() can improve FIB_TRIE performance by allowing root
node to grow past the alloc_pages() limit, while preserving memory.

Special care must be taken to free such zone, as rcu handler is not
allowed to call vfree(), we use a worker instead.

Signed-off-by: Eric Dumazet <dada1@...mosbay.com>



View attachment "trie_vmalloc.patch" of type "text/plain" (1837 bytes)