1/* Sort array of link maps according to dependencies.
2 Copyright (C) 2017-2023 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 bool force_first, bool for_fini)
31{
32 /* Allows caller to do the common optimization of skipping the first map,
33 usually the main binary. */
34 maps += force_first;
35 nmaps -= force_first;
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/* We use a recursive function due to its better clarity and ease of
125 implementation, as well as faster execution speed. We already use
126 alloca() for list allocation during the breadth-first search of
127 dependencies in _dl_map_object_deps(), and this should be on the
128 same order of worst-case stack usage.
129
130 Note: the '*rpo' parameter is supposed to point to one past the
131 last element of the array where we save the sort results, and is
132 decremented before storing the current map at each level. */
133
134static void
135dfs_traversal (struct link_map ***rpo, struct link_map *map,
136 bool *do_reldeps)
137{
138 /* _dl_map_object_deps ignores l_faked objects when calculating the
139 number of maps before calling _dl_sort_maps, ignore them as well. */
140 if (map->l_visited || map->l_faked)
141 return;
142
143 map->l_visited = 1;
144
145 if (map->l_initfini)
146 {
147 for (int i = 0; map->l_initfini[i] != NULL; i++)
148 {
149 struct link_map *dep = map->l_initfini[i];
150 if (dep->l_visited == 0
151 && dep->l_main_map == 0)
152 dfs_traversal (rpo, dep, do_reldeps);
153 }
154 }
155
156 if (__glibc_unlikely (do_reldeps != NULL && map->l_reldeps != NULL))
157 {
158 /* Indicate that we encountered relocation dependencies during
159 traversal. */
160 *do_reldeps = true;
161
162 for (int m = map->l_reldeps->act - 1; m >= 0; m--)
163 {
164 struct link_map *dep = map->l_reldeps->list[m];
165 if (dep->l_visited == 0
166 && dep->l_main_map == 0)
167 dfs_traversal (rpo, dep, do_reldeps);
168 }
169 }
170
171 *rpo -= 1;
172 **rpo = map;
173}
174
175/* Topologically sort array MAPS according to dependencies of the contained
176 objects. */
177
178static void
179_dl_sort_maps_dfs (struct link_map **maps, unsigned int nmaps,
180 bool force_first, bool for_fini)
181{
182 struct link_map *first_map = maps[0];
183 for (int i = nmaps - 1; i >= 0; i--)
184 maps[i]->l_visited = 0;
185
186 /* We apply DFS traversal for each of maps[i] until the whole total order
187 is found and we're at the start of the Reverse-Postorder (RPO) sequence,
188 which is a topological sort.
189
190 We go from maps[nmaps - 1] backwards towards maps[0] at this level.
191 Due to the breadth-first search (BFS) ordering we receive, going
192 backwards usually gives a more shallow depth-first recursion depth,
193 adding more stack usage safety. Also, combined with the natural
194 processing order of l_initfini[] at each node during DFS, this maintains
195 an ordering closer to the original link ordering in the sorting results
196 under most simpler cases.
197
198 Another reason we order the top level backwards, it that maps[0] is
199 usually exactly the main object of which we're in the midst of
200 _dl_map_object_deps() processing, and maps[0]->l_initfini[] is still
201 blank. If we start the traversal from maps[0], since having no
202 dependencies yet filled in, maps[0] will always be immediately
203 incorrectly placed at the last place in the order (first in reverse).
204 Adjusting the order so that maps[0] is last traversed naturally avoids
205 this problem.
206
207 To summarize, just passing in the full list, and iterating from back
208 to front makes things much more straightforward. */
209
210 /* Array to hold RPO sorting results, before we copy back to maps[]. */
211 struct link_map *rpo[nmaps];
212
213 /* The 'head' position during each DFS iteration. Note that we start at
214 one past the last element due to first-decrement-then-store (see the
215 bottom of above dfs_traversal() routine). */
216 struct link_map **rpo_head = &rpo[nmaps];
217
218 bool do_reldeps = false;
219 bool *do_reldeps_ref = (for_fini ? &do_reldeps : NULL);
220
221 for (int i = nmaps - 1; i >= 0; i--)
222 {
223 dfs_traversal (&rpo_head, maps[i], do_reldeps_ref);
224
225 /* We can break early if all objects are already placed. */
226 if (rpo_head == rpo)
227 goto end;
228 }
229 assert (rpo_head == rpo);
230
231 end:
232 /* Here we may do a second pass of sorting, using only l_initfini[]
233 static dependency links. This is avoided if !FOR_FINI or if we didn't
234 find any reldeps in the first DFS traversal.
235
236 The reason we do this is: while it is unspecified how circular
237 dependencies should be handled, the presumed reasonable behavior is to
238 have destructors to respect static dependency links as much as possible,
239 overriding reldeps if needed. And the first sorting pass, which takes
240 l_initfini/l_reldeps links equally, may not preserve this priority.
241
242 Hence we do a 2nd sorting pass, taking only DT_NEEDED links into account
243 (see how the do_reldeps argument to dfs_traversal() is NULL below). */
244 if (do_reldeps)
245 {
246 for (int i = nmaps - 1; i >= 0; i--)
247 rpo[i]->l_visited = 0;
248
249 struct link_map **maps_head = &maps[nmaps];
250 for (int i = nmaps - 1; i >= 0; i--)
251 {
252 dfs_traversal (&maps_head, rpo[i], NULL);
253
254 /* We can break early if all objects are already placed.
255 The below memcpy is not needed in the do_reldeps case here,
256 since we wrote back to maps[] during DFS traversal. */
257 if (maps_head == maps)
258 return;
259 }
260 assert (maps_head == maps);
261 return;
262 }
263
264 memcpy (maps, rpo, sizeof (struct link_map *) * nmaps);
265
266 /* Skipping the first object at maps[0] is not valid in general,
267 since traversing along object dependency-links may "find" that
268 first object even when it is not included in the initial order
269 (e.g., a dlopen'ed shared object can have circular dependencies
270 linked back to itself). In such a case, traversing N-1 objects
271 will create a N-object result, and raise problems. Instead,
272 force the object back into first place after sorting. This naive
273 approach may introduce further dependency ordering violations
274 compared to rotating the cycle until the first map is again in
275 the first position, but as there is a cycle, at least one
276 violation is already present. */
277 if (force_first && maps[0] != first_map)
278 {
279 int i;
280 for (i = 0; maps[i] != first_map; ++i)
281 ;
282 assert (i < nmaps);
283 memmove (&maps[1], maps, i * sizeof (maps[0]));
284 maps[0] = first_map;
285 }
286}
287
288void
289_dl_sort_maps_init (void)
290{
291 int32_t algorithm = TUNABLE_GET (glibc, rtld, dynamic_sort, int32_t, NULL);
292 GLRO(dl_dso_sort_algo) = algorithm == 1 ? dso_sort_algorithm_original
293 : dso_sort_algorithm_dfs;
294}
295
296void
297_dl_sort_maps (struct link_map **maps, unsigned int nmaps,
298 bool force_first, bool for_fini)
299{
300 /* It can be tempting to use a static function pointer to store and call
301 the current selected sorting algorithm routine, but experimentation
302 shows that current processors still do not handle indirect branches
303 that efficiently, plus a static function pointer will involve
304 PTR_MANGLE/DEMANGLE, further impairing performance of small, common
305 input cases. A simple if-case with direct function calls appears to
306 be the fastest. */
307 if (__glibc_likely (GLRO(dl_dso_sort_algo) == dso_sort_algorithm_original))
308 _dl_sort_maps_original (maps, nmaps, force_first, for_fini);
309 else
310 _dl_sort_maps_dfs (maps, nmaps, force_first, for_fini);
311}
312