This is the mail archive of the
glibc-bugs@sourceware.org
mailing list for the glibc project.
Re: [Bug dynamic-link/15310] New: _dl_sort_fini is O(n^3) causing slow exit when many dsos
- From: OndÅej BÃlka <neleai at seznam dot cz>
- To: dhatch at ilm dot com <sourceware-bugzilla at sourceware dot org>
- Cc: glibc-bugs at sourceware dot org
- Date: Wed, 27 Mar 2013 21:45:58 +0100
- Subject: Re: [Bug dynamic-link/15310] New: _dl_sort_fini is O(n^3) causing slow exit when many dsos
- References: <bug-15310-131 at http dot sourceware dot org/bugzilla/>
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));