1 diff -rup a/elf/dl-close.c b/elf/dl-close.c
2 --- a/elf/dl-close.c 2012-01-19 12:59:42.759484350 -0700
3 +++ b/elf/dl-close.c 2012-01-19 14:10:20.439263806 -0700
4 @@ -223,7 +223,7 @@ _dl_close_worker (struct link_map *map)
7 /* Sort the entries. */
8 - _dl_sort_fini (ns->_ns_loaded, maps, nloaded, used, nsid);
9 + _dl_sort_fini (maps, nloaded, used, nsid);
11 /* Call all termination functions at once. */
13 diff -rup a/elf/dl-deps.c b/elf/dl-deps.c
14 --- a/elf/dl-deps.c 2012-01-19 12:59:42.716484301 -0700
15 +++ b/elf/dl-deps.c 2012-01-19 13:52:35.223720556 -0700
16 @@ -614,51 +614,67 @@ Filters not supported with LD_TRACE_PREL
17 map->l_searchlist.r_list[i]->l_reserved = 0;
20 - /* Now determine the order in which the initialization has to happen. */
21 + /* Sort the initializer list to take dependencies into account. The binary
22 + itself will always be initialize last. */
23 memcpy (l_initfini, map->l_searchlist.r_list,
24 nlist * sizeof (struct link_map *));
25 - /* We can skip looking for the binary itself which is at the front
26 - of the search list. Look through the list backward so that circular
27 - dependencies are not changing the order. */
28 - for (i = 1; i < nlist; ++i)
29 + if (__builtin_expect (nlist > 1, 1))
31 - struct link_map *l = map->l_searchlist.r_list[i];
35 - /* Find the place in the initfini list where the map is currently
37 - for (j = 1; l_initfini[j] != l; ++j)
40 - /* Find all object for which the current one is a dependency and
41 - move the found object (if necessary) in front. */
42 - for (k = j + 1; k < nlist; ++k)
43 + /* We can skip looking for the binary itself which is at the front
44 + of the search list. */
46 + unsigned int seen[nlist];
47 + memset (seen, 0, nlist * sizeof (seen[0]));
50 - struct link_map **runp;
52 - runp = l_initfini[k]->l_initfini;
54 + /* Keep track of which object we looked at this round. */
56 + struct link_map *thisp = l_initfini[i];
58 + /* Find the last object in the list for which the current one is
59 + a dependency and move the current object behind the object
60 + with the dependency. */
61 + unsigned int k = nlist - 1;
64 - while (*runp != NULL)
65 - if (__builtin_expect (*runp++ == l, 0))
67 - struct link_map *here = l_initfini[k];
70 - memmove (&l_initfini[j] + 1, &l_initfini[j],
71 - (k - j) * sizeof (struct link_map *));
72 - l_initfini[j] = here;
74 - /* Don't insert further matches before the last
75 - entry moved to the front. */
77 + struct link_map **runp = l_initfini[k]->l_initfini;
79 + /* Look through the dependencies of the object. */
80 + while (*runp != NULL)
81 + if (__builtin_expect (*runp++ == thisp, 0))
83 + /* Move the current object to the back past the last
84 + object with it as the dependency. */
85 + memmove (&l_initfini[i], &l_initfini[i + 1],
86 + (k - i) * sizeof (l_initfini[0]));
87 + l_initfini[k] = thisp;
89 + if (seen[i + 1] > nlist - i - 2)
95 + unsigned int this_seen = seen[i];
96 + memmove (&seen[i], &seen[i + 1],
97 + (k - i) * sizeof (seen[0]));
98 + seen[k] = this_seen;
111 + memset (&seen[i], 0, (nlist - i) * sizeof (seen[0]));
117 /* Terminate the list of dependencies. */
118 l_initfini[nlist] = NULL;
119 atomic_write_barrier ();
120 diff -rup a/elf/dl-fini.c b/elf/dl-fini.c
121 --- a/elf/dl-fini.c 2010-05-04 05:27:23.000000000 -0600
122 +++ b/elf/dl-fini.c 2012-01-19 13:56:38.653842046 -0700
124 /* Call the termination functions of loaded shared objects.
125 - Copyright (C) 1995,96,1998-2002,2004-2005,2009 Free Software Foundation, Inc.
126 + Copyright (C) 1995,96,1998-2002,2004-2005,2009,2011
127 + Free Software Foundation, Inc.
128 This file is part of the GNU C Library.
130 The GNU C Library is free software; you can redistribute it and/or
131 @@ -29,89 +30,100 @@ typedef void (*fini_t) (void);
135 -_dl_sort_fini (struct link_map *l, struct link_map **maps, size_t nmaps,
136 - char *used, Lmid_t ns)
137 +_dl_sort_fini (struct link_map **maps, size_t nmaps, char *used, Lmid_t ns)
139 - if (ns == LM_ID_BASE)
140 - /* The main executable always comes first. */
143 - for (; l != NULL; l = l->l_next)
144 - /* Do not handle ld.so in secondary namespaces and object which
145 - are not removed. */
146 - if (l == l->l_real && l->l_idx != -1)
148 - /* Find the place in the 'maps' array. */
150 - for (j = ns == LM_ID_BASE ? 1 : 0; maps[j] != l; ++j)
151 - assert (j < nmaps);
153 - /* Find all object for which the current one is a dependency
154 - and move the found object (if necessary) in front. */
155 - for (unsigned int k = j + 1; k < nmaps; ++k)
157 - struct link_map **runp = maps[k]->l_initfini;
160 - while (*runp != NULL)
163 - struct link_map *here = maps[k];
164 + /* A list of one element need not be sorted. */
168 + /* We can skip looking for the binary itself which is at the front
169 + of the search list for the main namespace. */
170 + unsigned int i = ns == LM_ID_BASE;
171 + unsigned int seen[nmaps];
172 + memset (seen, 0, nmaps * sizeof (seen[0]));
175 + /* Keep track of which object we looked at this round. */
177 + struct link_map *thisp = maps[i];
179 + /* Do not handle ld.so in secondary namespaces and object which
180 + are not removed. */
181 + if (thisp != thisp->l_real || thisp->l_idx == -1)
184 + /* Find the last object in the list for which the current one is
185 + a dependency and move the current object behind the object
186 + with the dependency. */
187 + unsigned int k = nmaps - 1;
190 + struct link_map **runp = maps[k]->l_initfini;
192 + /* Look through the dependencies of the object. */
193 + while (*runp != NULL)
194 + if (__builtin_expect (*runp++ == thisp, 0))
197 + /* Move the current object to the back past the last
198 + object with it as the dependency. */
199 + memmove (&maps[i], &maps[i + 1],
200 + (k - i) * sizeof (maps[0]));
204 - memmove (&maps[j] + 1,
205 - &maps[j], (k - j) * sizeof (struct link_map *));
209 + char here_used = used[i];
210 + memmove (&used[i], &used[i + 1],
211 + (k - i) * sizeof (used[0]));
212 + used[k] = here_used;
217 - char here_used = used[k];
218 + if (seen[i + 1] > nmaps - i - 2)
224 - memmove (&used[j] + 1,
225 - &used[j], (k - j) * sizeof (char));
226 - used[j] = here_used;
228 + unsigned int this_seen = seen[i];
229 + memmove (&seen[i], &seen[i + 1], (k - i) * sizeof (seen[0]));
230 + seen[k] = this_seen;
242 - if (__builtin_expect (maps[k]->l_reldeps != NULL, 0))
244 - unsigned int m = maps[k]->l_reldeps->act;
245 - struct link_map **relmaps = &maps[k]->l_reldeps->list[0];
246 + if (__builtin_expect (maps[k]->l_reldeps != NULL, 0))
248 + unsigned int m = maps[k]->l_reldeps->act;
249 + struct link_map **relmaps = &maps[k]->l_reldeps->list[0];
252 + /* Look through the relocation dependencies of the object. */
254 + if (__builtin_expect (relmaps[m] == thisp, 0))
256 - if (relmaps[m] == l)
258 - struct link_map *here = maps[k];
261 - memmove (&maps[j] + 1,
263 - (k - j) * sizeof (struct link_map *));
268 - char here_used = used[k];
270 - memmove (&used[j] + 1,
271 - &used[j], (k - j) * sizeof (char));
272 - used[j] = here_used;
277 + /* If a cycle exists with a link time dependency,
278 + preserve the latter. */
279 + struct link_map **runp = thisp->l_initfini;
281 + while (*runp != NULL)
282 + if (__builtin_expect (*runp++ == maps[k], 0))
299 + memset (&seen[i], 0, (nmaps - i) * sizeof (seen[0]));
306 @@ -196,9 +208,8 @@ _dl_fini (void)
307 assert (ns == LM_ID_BASE || i == nloaded || i == nloaded - 1);
311 - /* Now we have to do the sorting. */
312 - _dl_sort_fini (GL(dl_ns)[ns]._ns_loaded, maps, nmaps, NULL, ns);
313 + /* Now we have to do the sorting. */
314 + _dl_sort_fini (maps, nmaps, NULL, ns);
316 /* We do not rely on the linked list of loaded object anymore from
317 this point on. We have our own list here (maps). The various
318 diff -rup a/sysdeps/generic/ldsodefs.h b/sysdeps/generic/ldsodefs.h
319 --- a/sysdeps/generic/ldsodefs.h 2012-01-19 12:59:42.446483997 -0700
320 +++ b/sysdeps/generic/ldsodefs.h 2012-01-19 14:16:36.242453532 -0700
321 @@ -947,7 +947,7 @@ extern void _dl_init (struct link_map *m
322 extern void _dl_fini (void) internal_function;
324 /* Sort array MAPS according to dependencies of the contained objects. */
325 -extern void _dl_sort_fini (struct link_map *l, struct link_map **maps,
326 +extern void _dl_sort_fini (struct link_map **maps,
327 size_t nmaps, char *used, Lmid_t ns)