netdev - Re: [PATCH 1/2] iproute2: Improve list add.

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] [day] [month] [year] [list]

Date:	Mon, 11 Jun 2012 15:01:07 -0700
From:	Stephen Hemminger <shemminger@...tta.com>
To:	Pravin B Shelar <pshelar@...ira.com>
Cc:	netdev@...r.kernel.org, jpettit@...ira.com, jesse@...ira.com
Subject: Re: [PATCH 1/2] iproute2: Improve list add.

On Tue, 22 May 2012 15:37:19 -0700
Pravin B Shelar <pshelar@...ira.com> wrote:

> ip command reads entire list of devices on every flush command.
> While adding device record to list is does list traversal O(n).
> This is time consuming for large batch commands.
> Following patch improves list add operation to O(1).
> 
> Reported-by: Justin Pettit <jpettit@...ira.com>
> Signed-off-by: Pravin B Shelar <pshelar@...ira.com>
> ---
>  ip/ipaddress.c |   16 ++++++++++++----
>  1 file changed, 12 insertions(+), 4 deletions(-)
> 

This no longer applies, after a similar patch I just accepted
from Eric.

commit 62e2e540919d31147165dabd35431c0649122c96
Author: Eric Dumazet <edumazet@...gle.com>
Date:   Sat Jun 9 13:55:55 2012 +0200

    ip: speedup ip link
    
    ip link has quadratic behavior because store_nlmsg()
    has a head list pointer and search the end of list.
    
    Provides a head/tail to cut time.
    
    Time with 128000 net devices, to do "ip link show dev xxx"
    
    Before: 2m3.594s
    After: 0m2.830s
    
    Signed-off-by: Eric Dumazet <edumazet@...gle.com>


If that doesn't fix your problem go ahead and resubmit.


--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html