From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 18284 invoked by alias); 27 Mar 2013 21:00:42 -0000 Mailing-List: contact glibc-bugs-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Post: List-Help: , Sender: glibc-bugs-owner@sourceware.org Received: (qmail 18219 invoked by uid 48); 27 Mar 2013 21:00:35 -0000 From: "carlos at redhat dot com" To: glibc-bugs@sourceware.org Subject: [Bug dynamic-link/15310] _dl_sort_fini is O(n^3) causing slow exit when many dsos Date: Wed, 27 Mar 2013 21:00:00 -0000 X-Bugzilla-Reason: CC X-Bugzilla-Type: changed X-Bugzilla-Watch-Reason: None X-Bugzilla-Product: glibc X-Bugzilla-Component: dynamic-link X-Bugzilla-Keywords: X-Bugzilla-Severity: critical X-Bugzilla-Who: carlos at redhat dot com X-Bugzilla-Status: NEW X-Bugzilla-Priority: P2 X-Bugzilla-Assigned-To: unassigned at sourceware dot org X-Bugzilla-Target-Milestone: --- X-Bugzilla-Changed-Fields: Message-ID: In-Reply-To: References: X-Bugzilla-URL: http://sourceware.org/bugzilla/ Auto-Submitted: auto-generated Content-Type: text/plain; charset="UTF-8" MIME-Version: 1.0 X-SW-Source: 2013-03/txt/msg00150.txt.bz2 http://sourceware.org/bugzilla/show_bug.cgi?id=15310 --- Comment #5 from Carlos O'Donell 2013-03-27 21:00:34 UTC --- (In reply to comment #3) > (In reply to comment #2) > > Don, > > > > I agree that the sorting could be made *far* faster. > > > > Thanks for submitting this. We were well aware that the minimal fix for bug > > 13882 would cause some kind of performance regression, but it was a balance > > between a minimal fix and low risk of breakage. I reviewed the patch for 13882 > > and even build a minimal framework for testing that dynamic loader function > > outside of the build. > > > > Do you have the time to investigate this and propose a patch (requires > > copyright assignment)? > > I do. I am working on a patch that resolves both this and bug 15311, > and I'll submit it here in a day or two. I look forward to the patch. > I am very interested in what you came up with in the way of a unit > testing scheme for this function... I could certainly use it. I aggrandized a bit here. I copied the relevant sorting code out of the loader code, wrapped it up in a function, created some static arrays to simulate DSOs loaded in a certain order, and then ran the sorting function against the the simulated DSO list. The best description is that I ran a simulation. I looked for the code I used to test bug 13882, but I've lost it (changed employers). You can see my comments here: http://sourceware.org/ml/libc-alpha/2012-06/msg00560.html > I've found it frustrating that the existing tests run by "make check" > (the ones I saw anyway) > involve just creating/compiling/running a handful of real programs... > to really stress test an implementation of _dl_sort_fini properly, > I'd want to (at least) enumerate all possible graphs > of up to 3 or 4 nodes, and call it on each of them, > which would be millions of examples... > and a few million randomly generated larger examples as well. > It's *really* easy to get this stuff wrong otherwise. I fully agree. As a volunteer project we live and die by the companies and individuals that choose to contribute to the project. I would be more than happy to see all possible 3 or 4 node graphs tested. The random testing is more problematic as you are probably well aware of; you can still auto-generate millions of test cases just make it deterministic :-) > Also I'd like to start by moving the init sorting code into a function. > It looks to me like this code is duplicated in two places (dl-open.c > and dl-deps.c), and (after the fix for bug 15309) > it's identical in both places except that > one of them starts at i0=0 and the other starts at i0=1. > So this could be expressed cleanly as a new function _dl_sort_init that takes > i0 > as a parameter. That sounds like a great idea. > Should I start by submitting a patch that does that, > with no functional change, and go from there? Or should I let you > or someone else do this refactoring (possibly in conjunction > with making these sorting functions unit testable)? > Let me know how to proceed. Always break the work into as small a piece as conceivably possible. Doing just the refactoring is a great first step. Once we have that in place we can talk about next steps. The Contribution Checklist for this project is rather long, but we are a conservative project and it helps to have everything documented and well specified. You can see the checklist here: http://sourceware.org/glibc/wiki/Contribution%20checklist -- Configure bugmail: http://sourceware.org/bugzilla/userprefs.cgi?tab=email ------- You are receiving this mail because: ------- You are on the CC list for the bug.