Re: [Bug dynamic-link/15310] New: _dl_sort_fini is O(n^3) causing slow exit when many dsos

[OndÅej BÃlka <neleai at seznam dot cz>]

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