]>
Commit | Line | Data |
---|---|---|
c2c299fd | 1 | /* Sort array of link maps according to dependencies. |
6d7e8eda | 2 | Copyright (C) 2017-2023 Free Software Foundation, Inc. |
c2c299fd AS |
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 | |
5a82c748 | 17 | <https://www.gnu.org/licenses/>. */ |
c2c299fd | 18 | |
15a0c573 | 19 | #include <assert.h> |
c2c299fd | 20 | #include <ldsodefs.h> |
15a0c573 | 21 | #include <elf/dl-tunables.h> |
c2c299fd | 22 | |
15a0c573 CLT |
23 | /* Note: this is the older, "original" sorting algorithm, being used as |
24 | default up to 2.35. | |
c2c299fd | 25 | |
15a0c573 CLT |
26 | Sort array MAPS according to dependencies of the contained objects. |
27 | If FOR_FINI is true, this is called for finishing an object. */ | |
28 | static void | |
29 | _dl_sort_maps_original (struct link_map **maps, unsigned int nmaps, | |
dbb75513 | 30 | bool force_first, bool for_fini) |
c2c299fd | 31 | { |
15a0c573 CLT |
32 | /* Allows caller to do the common optimization of skipping the first map, |
33 | usually the main binary. */ | |
dbb75513 FW |
34 | maps += force_first; |
35 | nmaps -= force_first; | |
15a0c573 | 36 | |
c2c299fd AS |
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 | ||
c2c299fd AS |
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 | } | |
15a0c573 | 123 | |
15a0c573 CLT |
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 | ||
134 | static void | |
135 | dfs_traversal (struct link_map ***rpo, struct link_map *map, | |
136 | bool *do_reldeps) | |
137 | { | |
3a0588ae AZ |
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) | |
15a0c573 CLT |
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 | ||
178 | static void | |
179 | _dl_sort_maps_dfs (struct link_map **maps, unsigned int nmaps, | |
1df71d32 | 180 | bool force_first, bool for_fini) |
15a0c573 | 181 | { |
1df71d32 | 182 | struct link_map *first_map = maps[0]; |
15a0c573 CLT |
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 | ||
15a0c573 CLT |
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); | |
1df71d32 FW |
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 | } | |
15a0c573 CLT |
286 | } |
287 | ||
288 | void | |
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 | ||
296 | void | |
297 | _dl_sort_maps (struct link_map **maps, unsigned int nmaps, | |
dbb75513 | 298 | bool force_first, bool for_fini) |
15a0c573 CLT |
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)) | |
dbb75513 | 308 | _dl_sort_maps_original (maps, nmaps, force_first, for_fini); |
15a0c573 | 309 | else |
dbb75513 | 310 | _dl_sort_maps_dfs (maps, nmaps, force_first, for_fini); |
15a0c573 | 311 | } |