diff options
Diffstat (limited to 'elf/dl-deps.c')
| -rw-r--r-- | elf/dl-deps.c | 86 |
1 files changed, 49 insertions, 37 deletions
diff --git a/elf/dl-deps.c b/elf/dl-deps.c index a51fb6e414..440fb563da 100644 --- a/elf/dl-deps.c +++ b/elf/dl-deps.c @@ -1,5 +1,5 @@ /* Load the dependencies of a mapped object. - Copyright (C) 1996-2003, 2004, 2005, 2006, 2007, 2010 + Copyright (C) 1996-2003, 2004, 2005, 2006, 2007, 2010, 2011 Free Software Foundation, Inc. This file is part of the GNU C Library. @@ -591,7 +591,7 @@ Filters not supported with LD_TRACE_PRELINKING")); /* Need to allocate new array of relocation dependencies. */ struct link_map_reldeps *l_reldeps; l_reldeps = malloc (sizeof (*l_reldeps) - + map->l_reldepsmax + + map->l_reldepsmax * sizeof (struct link_map *)); if (l_reldeps == NULL) /* Bad luck, keep the reldeps duplicated between @@ -616,48 +616,60 @@ Filters not supported with LD_TRACE_PRELINKING")); /* Now determine the order in which the initialization has to happen. */ memcpy (l_initfini, map->l_searchlist.r_list, nlist * sizeof (struct link_map *)); + /* We can skip looking for the binary itself which is at the front - of the search list. Look through the list backward so that circular - dependencies are not changing the order. */ - for (i = 1; i < nlist; ++i) + of the search list. */ + assert (nlist > 1); + i = 1; + bool seen[nlist]; + memset (seen, false, nlist * sizeof (seen[0])); + while (1) { - struct link_map *l = map->l_searchlist.r_list[i]; - unsigned int j; - unsigned int k; - - /* Find the place in the initfini list where the map is currently - located. */ - for (j = 1; l_initfini[j] != l; ++j) - ; - - /* Find all object for which the current one is a dependency and - move the found object (if necessary) in front. */ - for (k = j + 1; k < nlist; ++k) + /* Keep track of which object we looked at this round. */ + seen[i] = true; + struct link_map *thisp = l_initfini[i]; + + /* Find the last object in the list for which the current one is + a dependency and move the current object behind the object + with the dependency. */ + unsigned int k = nlist - 1; + while (k > i) { - struct link_map **runp; - - runp = l_initfini[k]->l_initfini; + struct link_map **runp = l_initfini[k]->l_initfini; if (runp != NULL) - { - while (*runp != NULL) - if (__builtin_expect (*runp++ == l, 0)) - { - struct link_map *here = l_initfini[k]; - - /* Move it now. */ - memmove (&l_initfini[j] + 1, &l_initfini[j], - (k - j) * sizeof (struct link_map *)); - l_initfini[j] = here; + /* Look through the dependencies of the object. */ + while (*runp != NULL) + if (__builtin_expect (*runp++ == thisp, 0)) + { + /* Move the current object to the back past the last + object with it as the dependency. */ + memmove (&l_initfini[i], &l_initfini[i + 1], + (k - i) * sizeof (l_initfini[0])); + l_initfini[k] = thisp; + + if (seen[i + 1]) + { + ++i; + goto next_clear; + } + + memmove (&seen[i], &seen[i + 1], (k - i) * sizeof (seen[0])); + seen[k] = true; + + goto next; + } + + --k; + } - /* Don't insert further matches before the last - entry moved to the front. */ - ++j; + if (++i == nlist) + break; + next_clear: + memset (&seen[i], false, (nlist - i) * sizeof (seen[0])); - break; - } - } - } + next:; } + /* Terminate the list of dependencies. */ l_initfini[nlist] = NULL; atomic_write_barrier (); |