This is the mail archive of the
glibc-bugs@sourceware.org
mailing list for the glibc project.
[Bug dynamic-link/15310] _dl_sort_fini is O(n^3) causing slow exit when many dsos
- From: "neleai at seznam dot cz" <sourceware-bugzilla at sourceware dot org>
- To: glibc-bugs at sourceware dot org
- Date: Wed, 27 Mar 2013 20:50:40 +0000
- Subject: [Bug dynamic-link/15310] _dl_sort_fini is O(n^3) causing slow exit when many dsos
- Auto-submitted: auto-generated
- References: <bug-15310-131 at http dot sourceware dot org/bugzilla/>
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.