]>
Commit | Line | Data |
---|---|---|
c2c299fd | 1 | /* Sort array of link maps according to dependencies. |
2b778ceb | 2 | Copyright (C) 2017-2021 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 AS |
18 | |
19 | #include <ldsodefs.h> | |
20 | ||
21 | ||
22 | /* Sort array MAPS according to dependencies of the contained objects. | |
23 | Array USED, if non-NULL, is permutated along MAPS. If FOR_FINI this is | |
24 | called for finishing an object. */ | |
25 | void | |
26 | _dl_sort_maps (struct link_map **maps, unsigned int nmaps, char *used, | |
27 | bool for_fini) | |
28 | { | |
29 | /* A list of one element need not be sorted. */ | |
30 | if (nmaps <= 1) | |
31 | return; | |
32 | ||
33 | unsigned int i = 0; | |
34 | uint16_t seen[nmaps]; | |
35 | memset (seen, 0, nmaps * sizeof (seen[0])); | |
36 | while (1) | |
37 | { | |
38 | /* Keep track of which object we looked at this round. */ | |
39 | ++seen[i]; | |
40 | struct link_map *thisp = maps[i]; | |
41 | ||
42 | if (__glibc_unlikely (for_fini)) | |
43 | { | |
44 | /* Do not handle ld.so in secondary namespaces and objects which | |
45 | are not removed. */ | |
46 | if (thisp != thisp->l_real || thisp->l_idx == -1) | |
47 | goto skip; | |
48 | } | |
49 | ||
50 | /* Find the last object in the list for which the current one is | |
51 | a dependency and move the current object behind the object | |
52 | with the dependency. */ | |
53 | unsigned int k = nmaps - 1; | |
54 | while (k > i) | |
55 | { | |
56 | struct link_map **runp = maps[k]->l_initfini; | |
57 | if (runp != NULL) | |
58 | /* Look through the dependencies of the object. */ | |
59 | while (*runp != NULL) | |
60 | if (__glibc_unlikely (*runp++ == thisp)) | |
61 | { | |
62 | move: | |
63 | /* Move the current object to the back past the last | |
64 | object with it as the dependency. */ | |
65 | memmove (&maps[i], &maps[i + 1], | |
66 | (k - i) * sizeof (maps[0])); | |
67 | maps[k] = thisp; | |
68 | ||
69 | if (used != NULL) | |
70 | { | |
71 | char here_used = used[i]; | |
72 | memmove (&used[i], &used[i + 1], | |
73 | (k - i) * sizeof (used[0])); | |
74 | used[k] = here_used; | |
75 | } | |
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 | } |