From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <glibc-bugs-return-18249-listarch-glibc-bugs=sources.redhat.com@sourceware.org>
Received: (qmail 14541 invoked by alias); 27 Mar 2013 20:50:47 -0000
Mailing-List: contact glibc-bugs-help@sourceware.org; run by ezmlm
Precedence: bulk
List-Id: <glibc-bugs.sourceware.org>
List-Subscribe: <mailto:glibc-bugs-subscribe@sourceware.org>
List-Post: <mailto:glibc-bugs@sourceware.org>
List-Help: <mailto:glibc-bugs-help@sourceware.org>, <http://sourceware.org/lists.html#faqs>
Sender: glibc-bugs-owner@sourceware.org
Received: (qmail 14356 invoked by uid 55); 27 Mar 2013 20:50:40 -0000
From: "neleai at seznam dot cz" <sourceware-bugzilla@sourceware.org>
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 20:50: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: neleai at seznam dot cz
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: <bug-15310-131-Cyn4racLay@http.sourceware.org/bugzilla/>
In-Reply-To: <bug-15310-131@http.sourceware.org/bugzilla/>
References: <bug-15310-131@http.sourceware.org/bugzilla/>
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/msg00148.txt.bz2

http://sourceware.org/bugzilla/show_bug.cgi?id=15310

--- Comment #4 from Ondrej Bilka <neleai at seznam dot cz> 2013-03-27 20:50:40 UTC ---
On Wed, Mar 27, 2013 at 07:47:46AM +0000, dhatch at ilm dot com wrote:
> http://sourceware.org/bugzilla/show_bug.cgi?id=15310
> 
> This is just a topsort, which can be done simply in O(n) time
> with no fancy data structures.
> 
I do not have domain knowledge to understand what is necessary to
consider.

However I could write topsort if I knew dependencies. From code I think
following pseudocode should work upto possibility that some arrows need
be reversed.

add_edge(g,x,y) // add edge from x to y
topsort(g)      // returns topologic ordering of g

graph *g; 
for(k=0;k<nmaps;k++)
  {
      /* Add dependencies of the object.  */
      struct link_map **runp = maps[k]->l_initfini;
      if (runp != NULL)
        while (*runp != NULL) 
          add_edge(g,maps[k],*runp);

          /* Add relocation dependencies.  */
      if (__builtin_expect (maps[k]->l_reldeps != NULL, 0))
        {
          unsigned int m = maps[k]->l_reldeps->act;
          struct link_map **relmaps = &maps[k]->l_reldeps->list[0];
          for (j=0;j<m;j++)
            add_edge(g,relmaps[k],*runp) 
        }
  }

    memcpy(maps,topsort(g));

-- 
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.