From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <glibc-bugs-return-18248-listarch-glibc-bugs=sources.redhat.com@sourceware.org>
Received: (qmail 14387 invoked by alias); 27 Mar 2013 20:50:46 -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 14316 invoked by uid 89); 27 Mar 2013 20:50:38 -0000
X-Spam-SWARE-Status: No, score=-0.8 required=5.0 tests=AWL,BAYES_00,FREEMAIL_FROM,SPF_NEUTRAL autolearn=no version=3.3.1
X-Spam-User: qpsmtpd, 2 recipients
Received: from popelka.ms.mff.cuni.cz (HELO popelka.ms.mff.cuni.cz) (195.113.20.131)    by sourceware.org (qpsmtpd/0.84/v0.84-167-ge50287c) with ESMTP; Wed, 27 Mar 2013 20:50:35 +0000
Received: from domone.kolej.mff.cuni.cz (popelka.ms.mff.cuni.cz [195.113.20.131])	by popelka.ms.mff.cuni.cz (Postfix) with ESMTPS id 3E4C74420B;	Wed, 27 Mar 2013 21:50:29 +0100 (CET)
Received: by domone.kolej.mff.cuni.cz (Postfix, from userid 1000)	id 6808E6045C; Wed, 27 Mar 2013 21:45:58 +0100 (CET)
Date: Wed, 27 Mar 2013 20:50:00 -0000
From: =?utf-8?B?T25kxZllaiBCw61sa2E=?= <neleai@seznam.cz>
To: dhatch at ilm dot com <sourceware-bugzilla@sourceware.org>
Cc: glibc-bugs@sourceware.org
Subject: Re: [Bug dynamic-link/15310] New: _dl_sort_fini is O(n^3) causing slow exit when many dsos
Message-ID: <20130327204558.GA4961@domone.kolej.mff.cuni.cz>
References: <bug-15310-131@http.sourceware.org/bugzilla/>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <bug-15310-131@http.sourceware.org/bugzilla/>
User-Agent: Mutt/1.5.20 (2009-06-14)
X-SW-Source: 2013-03/txt/msg00147.txt.bz2

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));