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  PHC 
Open Source and information security mailing list archives
Hash Suite for Android: free password hash cracker in your pocket
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date:	Sat, 12 Jan 2008 13:08:24 -0800
From:	Stephen Hemminger <>
To:	Eric Dumazet <>
Cc:	David Miller <>,
	Robert Olsson <>,
Subject: Re: [PATCH 9/9] fix sparse warnings

On Sat, 12 Jan 2008 12:16:13 +0100
Eric Dumazet <> wrote:

> Stephen Hemminger a écrit :
> > Make FIB TRIE go through sparse checker without warnings.
> > 
> > Signed-off-by: Stephen Hemminger <>
> Hi Stephen
> While reviewing your patches (and fib code) I had some questions :
> 1) I was wondering isn't trie_collect_stats() a potential cpu hog
> (big latency) ?
> 2) struct tnode layout
>     If tnode->bits is large enough, we allocate a big area
>     of memory but roughly use only first half of it.
>     We could use a better scheme with an extra indirection. For small
>     nodes, we use space right after tnode, but for big nodes, we allocate
>     a power of two set of pages, to exactly match the memory need.
> 3) 'pos' and 'bits' fields of 'struct tnode' might be converted to
>     plain uchar, instead of 5-bits fields, to reduce complexity for
>     generated code.
> 4) full_children & empty_children being 'unsigned short',
>     we probably are limited to 2^15 elements, but I could not
>     find this limit enforced somewhere.

Remember that the code should be optimized for lookup, not management
operations. We ran into this during testing (the test suite was looking
for number of routes), thats why I put in the size field.

The existing dump code is really slow:

1) FIB_TRIE   Under KVM:
     load 164393 routes		12.436 sec
     ip route | wc -l		12.569 sec
     grep /proc/net/route	25.357 sec

99% of the cpu time is spent in nextleaf() during these dump operations.

2) FIB_HASH 	Under KVM:
     load 164393 routes		10.833 sec
     ip route | wc -l		1.981 sec
     grep /proc/net/route	0.204 sec

Stephen Hemminger <>
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to
More majordomo info at

Powered by blists - more mailing lists