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
| ||
|
Date: Tue, 14 Oct 2014 12:56:11 -0700 From: ebiederm@...ssion.com (Eric W. Biederman) To: nicolas.dichtel@...nd.com Cc: netdev@...r.kernel.org, linux-kernel@...r.kernel.org, davem@...emloft.net, akpm@...ux-foundation.org, adobriyan@...il.com, rui.xiang@...wei.com, viro@...iv.linux.org.uk, oleg@...hat.com, gorcunov@...nvz.org, kirill.shutemov@...ux.intel.com, grant.likely@...retlab.ca, tytso@....edu, Linus Torvalds <torvalds@...ux-foundation.org>, Andrew Morton <akpm@...ux-foundation.org> Subject: Re: [PATCH linux v3 1/1] fs/proc: use a rb tree for the directory entries Nicolas Dichtel <nicolas.dichtel@...nd.com> writes: > Le 07/10/2014 11:02, Nicolas Dichtel a écrit : >> The current implementation for the directories in /proc is using a single >> linked list. This is slow when handling directories with large numbers of >> entries (eg netdevice-related entries when lots of tunnels are opened). >> >> This patch replaces this linked list by a red-black tree. >> >> Here are some numbers: >> >> dummy30000.batch contains 30 000 times 'link add type dummy'. >> >> Before the patch: >> $ time ip -b dummy30000.batch >> real 2m31.950s >> user 0m0.440s >> sys 2m21.440s >> $ time rmmod dummy >> real 1m35.764s >> user 0m0.000s >> sys 1m24.088s >> >> After the patch: >> $ time ip -b dummy30000.batch >> real 2m0.874s >> user 0m0.448s >> sys 1m49.720s >> $ time rmmod dummy >> real 1m13.988s >> user 0m0.000s >> sys 1m1.008s >> >> The idea of improving this part was suggested by >> Thierry Herbelot <thierry.herbelot@...nd.com>. >> >> Signed-off-by: Nicolas Dichtel <nicolas.dichtel@...nd.com> >> Acked-by: David S. Miller <davem@...emloft.net> Acked-by: "Eric W. Biederman" <ebiederm@...ssion.com> >> --- > > I'm not sure who is in charge of taking this patch. Should I resend it to > someone else or is it already included in a tree? There are a couple of things going on here. This patch came out at the beginning of the merge window which is a time when everything that was ready and well tested ahead of time gets merged. Your numbers don't look too bad, so I expect this code is ready to go (although I am a smidge disappointed in the small size of the performance improvement), my quick read through earlier did not show anything scary. Do you have any idea why going from O(N^2) algorithm to a O(NlogN) algorithm showed such a small performance improvement with 30,000 entries? Normally proc is looked at by a group of folks me, Alexey Dobriyan, and Al Viro all sort of tag team taking care of the proc infrastructure with (except for Al) Andrew Morton typically taking the patches and merging them. I am currently in the middle of a move so I don't have the time to carry this change or do much of anything until I am settled again. What I would recommend is verifying your patch works against v3.18-rc1 at the begginning of next week and sending the code to Andrew Morton. Eric -- 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
Powered by blists - more mailing lists