1/* Sort array of link maps according to dependencies.
2 Copyright (C) 2017-2022 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
4
5 The GNU C Library is free software; you can redistribute it and/or
6 modify it under the terms of the GNU Lesser General Public
7 License as published by the Free Software Foundation; either
8 version 2.1 of the License, or (at your option) any later version.
9
10 The GNU C Library is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 Lesser General Public License for more details.
14
15 You should have received a copy of the GNU Lesser General Public
16 License along with the GNU C Library; if not, see
17 <https://www.gnu.org/licenses/>. */
18
19#include <assert.h>
20#include <ldsodefs.h>
21#include <elf/dl-tunables.h>
22
23/* Note: this is the older, "original" sorting algorithm, being used as
24 default up to 2.35.
25
26 Sort array MAPS according to dependencies of the contained objects.
27 If FOR_FINI is true, this is called for finishing an object. */
28static void
29_dl_sort_maps_original (struct link_map **maps, unsigned int nmaps,
30 unsigned int skip, bool for_fini)
31{
32 /* Allows caller to do the common optimization of skipping the first map,
33 usually the main binary. */
34 maps += skip;
35 nmaps -= skip;
36
37 /* A list of one element need not be sorted. */
38 if (nmaps <= 1)
39 return;
40
41 unsigned int i = 0;
42 uint16_t seen[nmaps];
43 memset (seen, 0, nmaps * sizeof (seen[0]));
44 while (1)
45 {
46 /* Keep track of which object we looked at this round. */
47 ++seen[i];
48 struct link_map *thisp = maps[i];
49
50 if (__glibc_unlikely (for_fini))
51 {
52 /* Do not handle ld.so in secondary namespaces and objects which
53 are not removed. */
54 if (thisp != thisp->l_real || thisp->l_idx == -1)
55 goto skip;
56 }
57
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 = nmaps - 1;
62 while (k > i)
63 {
64 struct link_map **runp = maps[k]->l_initfini;
65 if (runp != NULL)
66 /* Look through the dependencies of the object. */
67 while (*runp != NULL)
68 if (__glibc_unlikely (*runp++ == thisp))
69 {
70 move:
71 /* Move the current object to the back past the last
72 object with it as the dependency. */
73 memmove (&maps[i], &maps[i + 1],
74 (k - i) * sizeof (maps[0]));
75 maps[k] = thisp;
76
77 if (seen[i + 1] > nmaps - i)
78 {
79 ++i;
80 goto next_clear;
81 }
82
83 uint16_t this_seen = seen[i];
84 memmove (&seen[i], &seen[i + 1], (k - i) * sizeof (seen[0]));
85 seen[k] = this_seen;
86
87 goto next;
88 }
89
90 if (__glibc_unlikely (for_fini && maps[k]->l_reldeps != NULL))
91 {
92 unsigned int m = maps[k]->l_reldeps->act;
93 struct link_map **relmaps = &maps[k]->l_reldeps->list[0];
94
95 /* Look through the relocation dependencies of the object. */
96 while (m-- > 0)
97 if (__glibc_unlikely (relmaps[m] == thisp))
98 {
99 /* If a cycle exists with a link time dependency,
100 preserve the latter. */
101 struct link_map **runp = thisp->l_initfini;
102 if (runp != NULL)
103 while (*runp != NULL)
104 if (__glibc_unlikely (*runp++ == maps[k]))
105 goto ignore;
106 goto move;
107 }
108 ignore:;
109 }
110
111 --k;
112 }
113
114 skip:
115 if (++i == nmaps)
116 break;
117 next_clear:
118 memset (&seen[i], 0, (nmaps - i) * sizeof (seen[0]));
119
120 next:;
121 }
122}
123
124#if !HAVE_TUNABLES
125/* In this case, just default to the original algorithm. */
126strong_alias (_dl_sort_maps_original, _dl_sort_maps);
127#else
128
129/* We use a recursive function due to its better clarity and ease of
130 implementation, as well as faster execution speed. We already use
131 alloca() for list allocation during the breadth-first search of
132 dependencies in _dl_map_object_deps(), and this should be on the
133 same order of worst-case stack usage.
134
135 Note: the '*rpo' parameter is supposed to point to one past the
136 last element of the array where we save the sort results, and is
137 decremented before storing the current map at each level. */
138
139static void
140dfs_traversal (struct link_map ***rpo, struct link_map *map,
141 bool *do_reldeps)
142{
143 if (map->l_visited)
144 return;
145
146 map->l_visited = 1;
147
148 if (map->l_initfini)
149 {
150 for (int i = 0; map->l_initfini[i] != NULL; i++)
151 {
152 struct link_map *dep = map->l_initfini[i];
153 if (dep->l_visited == 0
154 && dep->l_main_map == 0)
155 dfs_traversal (rpo, dep, do_reldeps);
156 }
157 }
158
159 if (__glibc_unlikely (do_reldeps != NULL && map->l_reldeps != NULL))
160 {
161 /* Indicate that we encountered relocation dependencies during
162 traversal. */
163 *do_reldeps = true;
164
165 for (int m = map->l_reldeps->act - 1; m >= 0; m--)
166 {
167 struct link_map *dep = map->l_reldeps->list[m];
168 if (dep->l_visited == 0
169 && dep->l_main_map == 0)
170 dfs_traversal (rpo, dep, do_reldeps);
171 }
172 }
173
174 *rpo -= 1;
175 **rpo = map;
176}
177
178/* Topologically sort array MAPS according to dependencies of the contained
179 objects. */
180
181static void
182_dl_sort_maps_dfs (struct link_map **maps, unsigned int nmaps,
183 unsigned int skip __attribute__ ((unused)), bool for_fini)
184{
185 for (int i = nmaps - 1; i >= 0; i--)
186 maps[i]->l_visited = 0;
187
188 /* We apply DFS traversal for each of maps[i] until the whole total order
189 is found and we're at the start of the Reverse-Postorder (RPO) sequence,
190 which is a topological sort.
191
192 We go from maps[nmaps - 1] backwards towards maps[0] at this level.
193 Due to the breadth-first search (BFS) ordering we receive, going
194 backwards usually gives a more shallow depth-first recursion depth,
195 adding more stack usage safety. Also, combined with the natural
196 processing order of l_initfini[] at each node during DFS, this maintains
197 an ordering closer to the original link ordering in the sorting results
198 under most simpler cases.
199
200 Another reason we order the top level backwards, it that maps[0] is
201 usually exactly the main object of which we're in the midst of
202 _dl_map_object_deps() processing, and maps[0]->l_initfini[] is still
203 blank. If we start the traversal from maps[0], since having no
204 dependencies yet filled in, maps[0] will always be immediately
205 incorrectly placed at the last place in the order (first in reverse).
206 Adjusting the order so that maps[0] is last traversed naturally avoids
207 this problem.
208
209 Further, the old "optimization" of skipping the main object at maps[0]
210 from the call-site (i.e. _dl_sort_maps(maps+1,nmaps-1)) is in general
211 no longer valid, since traversing along object dependency-links
212 may "find" the main object even when it is not included in the initial
213 order (e.g. a dlopen()'ed shared object can have circular dependencies
214 linked back to itself). In such a case, traversing N-1 objects will
215 create a N-object result, and raise problems.
216
217 To summarize, just passing in the full list, and iterating from back
218 to front makes things much more straightforward. */
219
220 /* Array to hold RPO sorting results, before we copy back to maps[]. */
221 struct link_map *rpo[nmaps];
222
223 /* The 'head' position during each DFS iteration. Note that we start at
224 one past the last element due to first-decrement-then-store (see the
225 bottom of above dfs_traversal() routine). */
226 struct link_map **rpo_head = &rpo[nmaps];
227
228 bool do_reldeps = false;
229 bool *do_reldeps_ref = (for_fini ? &do_reldeps : NULL);
230
231 for (int i = nmaps - 1; i >= 0; i--)
232 {
233 dfs_traversal (&rpo_head, maps[i], do_reldeps_ref);
234
235 /* We can break early if all objects are already placed. */
236 if (rpo_head == rpo)
237 goto end;
238 }
239 assert (rpo_head == rpo);
240
241 end:
242 /* Here we may do a second pass of sorting, using only l_initfini[]
243 static dependency links. This is avoided if !FOR_FINI or if we didn't
244 find any reldeps in the first DFS traversal.
245
246 The reason we do this is: while it is unspecified how circular
247 dependencies should be handled, the presumed reasonable behavior is to
248 have destructors to respect static dependency links as much as possible,
249 overriding reldeps if needed. And the first sorting pass, which takes
250 l_initfini/l_reldeps links equally, may not preserve this priority.
251
252 Hence we do a 2nd sorting pass, taking only DT_NEEDED links into account
253 (see how the do_reldeps argument to dfs_traversal() is NULL below). */
254 if (do_reldeps)
255 {
256 for (int i = nmaps - 1; i >= 0; i--)
257 rpo[i]->l_visited = 0;
258
259 struct link_map **maps_head = &maps[nmaps];
260 for (int i = nmaps - 1; i >= 0; i--)
261 {
262 dfs_traversal (&maps_head, rpo[i], NULL);
263
264 /* We can break early if all objects are already placed.
265 The below memcpy is not needed in the do_reldeps case here,
266 since we wrote back to maps[] during DFS traversal. */
267 if (maps_head == maps)
268 return;
269 }
270 assert (maps_head == maps);
271 return;
272 }
273
274 memcpy (maps, rpo, sizeof (struct link_map *) * nmaps);
275}
276
277void
278_dl_sort_maps_init (void)
279{
280 int32_t algorithm = TUNABLE_GET (glibc, rtld, dynamic_sort, int32_t, NULL);
281 GLRO(dl_dso_sort_algo) = algorithm == 1 ? dso_sort_algorithm_original
282 : dso_sort_algorithm_dfs;
283}
284
285void
286_dl_sort_maps (struct link_map **maps, unsigned int nmaps,
287 unsigned int skip, bool for_fini)
288{
289 /* It can be tempting to use a static function pointer to store and call
290 the current selected sorting algorithm routine, but experimentation
291 shows that current processors still do not handle indirect branches
292 that efficiently, plus a static function pointer will involve
293 PTR_MANGLE/DEMANGLE, further impairing performance of small, common
294 input cases. A simple if-case with direct function calls appears to
295 be the fastest. */
296 if (__glibc_likely (GLRO(dl_dso_sort_algo) == dso_sort_algorithm_original))
297 _dl_sort_maps_original (maps, nmaps, skip, for_fini);
298 else
299 _dl_sort_maps_dfs (maps, nmaps, skip, for_fini);
300}
301
302#endif /* HAVE_TUNABLES. */
303