1/* Load the dependencies of a mapped object.
2 Copyright (C) 1996-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 <atomic.h>
20#include <assert.h>
21#include <dlfcn.h>
22#include <errno.h>
23#include <libintl.h>
24#include <stddef.h>
25#include <stdlib.h>
26#include <string.h>
27#include <unistd.h>
28#include <sys/param.h>
29#include <ldsodefs.h>
30#include <scratch_buffer.h>
31
32#include <dl-dst.h>
33
34/* Whether an shared object references one or more auxiliary objects
35 is signaled by the AUXTAG entry in l_info. */
36#define AUXTAG (DT_NUM + DT_THISPROCNUM + DT_VERSIONTAGNUM \
37 + DT_EXTRATAGIDX (DT_AUXILIARY))
38/* Whether an shared object references one or more auxiliary objects
39 is signaled by the AUXTAG entry in l_info. */
40#define FILTERTAG (DT_NUM + DT_THISPROCNUM + DT_VERSIONTAGNUM \
41 + DT_EXTRATAGIDX (DT_FILTER))
42
43
44/* When loading auxiliary objects we must ignore errors. It's ok if
45 an object is missing. */
46struct openaux_args
47 {
48 /* The arguments to openaux. */
49 struct link_map *map;
50 int trace_mode;
51 int open_mode;
52 const char *strtab;
53 const char *name;
54
55 /* The return value of openaux. */
56 struct link_map *aux;
57 };
58
59static void
60openaux (void *a)
61{
62 struct openaux_args *args = (struct openaux_args *) a;
63
64 args->aux = _dl_map_object (args->map, args->name,
65 (args->map->l_type == lt_executable
66 ? lt_library : args->map->l_type),
67 args->trace_mode, args->open_mode,
68 args->map->l_ns);
69}
70
71/* We use a very special kind of list to track the path
72 through the list of loaded shared objects. We have to
73 produce a flat list with unique members of all involved objects.
74*/
75struct list
76 {
77 int done; /* Nonzero if this map was processed. */
78 struct link_map *map; /* The data. */
79 struct list *next; /* Elements for normal list. */
80 };
81
82
83/* Macro to expand DST. It is an macro since we use `alloca'. */
84#define expand_dst(l, str, fatal) \
85 ({ \
86 const char *__str = (str); \
87 const char *__result = __str; \
88 size_t __dst_cnt = _dl_dst_count (__str); \
89 \
90 if (__dst_cnt != 0) \
91 { \
92 char *__newp; \
93 \
94 /* DST must not appear in SUID/SGID programs. */ \
95 if (__libc_enable_secure) \
96 _dl_signal_error (0, __str, NULL, N_("\
97DST not allowed in SUID/SGID programs")); \
98 \
99 __newp = (char *) alloca (DL_DST_REQUIRED (l, __str, strlen (__str), \
100 __dst_cnt)); \
101 \
102 __result = _dl_dst_substitute (l, __str, __newp); \
103 \
104 if (*__result == '\0') \
105 { \
106 /* The replacement for the DST is not known. We can't \
107 processed. */ \
108 if (fatal) \
109 _dl_signal_error (0, __str, NULL, N_("\
110empty dynamic string token substitution")); \
111 else \
112 { \
113 /* This is for DT_AUXILIARY. */ \
114 if (__glibc_unlikely (GLRO(dl_debug_mask) & DL_DEBUG_LIBS)) \
115 _dl_debug_printf (N_("\
116cannot load auxiliary `%s' because of empty dynamic string token " \
117 "substitution\n"), __str); \
118 continue; \
119 } \
120 } \
121 } \
122 \
123 __result; })
124
125static void
126preload (struct list *known, unsigned int *nlist, struct link_map *map)
127{
128 known[*nlist].done = 0;
129 known[*nlist].map = map;
130 known[*nlist].next = &known[*nlist + 1];
131
132 ++*nlist;
133 /* We use `l_reserved' as a mark bit to detect objects we have
134 already put in the search list and avoid adding duplicate
135 elements later in the list. */
136 map->l_reserved = 1;
137}
138
139void
140_dl_map_object_deps (struct link_map *map,
141 struct link_map **preloads, unsigned int npreloads,
142 int trace_mode, int open_mode)
143{
144 struct list *known = __alloca (sizeof *known * (1 + npreloads + 1));
145 struct list *runp, *tail;
146 unsigned int nlist, i;
147 /* Object name. */
148 const char *name;
149 int errno_saved;
150 int errno_reason;
151 struct dl_exception exception;
152
153 /* No loaded object so far. */
154 nlist = 0;
155
156 /* First load MAP itself. */
157 preload (known, &nlist, map);
158
159 /* Add the preloaded items after MAP but before any of its dependencies. */
160 for (i = 0; i < npreloads; ++i)
161 preload (known, &nlist, preloads[i]);
162
163 /* Terminate the lists. */
164 known[nlist - 1].next = NULL;
165
166 /* Pointer to last unique object. */
167 tail = &known[nlist - 1];
168
169 struct scratch_buffer needed_space;
170 scratch_buffer_init (&needed_space);
171
172 /* Process each element of the search list, loading each of its
173 auxiliary objects and immediate dependencies. Auxiliary objects
174 will be added in the list before the object itself and
175 dependencies will be appended to the list as we step through it.
176 This produces a flat, ordered list that represents a
177 breadth-first search of the dependency tree.
178
179 The whole process is complicated by the fact that we better
180 should use alloca for the temporary list elements. But using
181 alloca means we cannot use recursive function calls. */
182 errno_saved = errno;
183 errno_reason = 0;
184 errno = 0;
185 name = NULL;
186 for (runp = known; runp; )
187 {
188 struct link_map *l = runp->map;
189 struct link_map **needed = NULL;
190 unsigned int nneeded = 0;
191
192 /* Unless otherwise stated, this object is handled. */
193 runp->done = 1;
194
195 /* Allocate a temporary record to contain the references to the
196 dependencies of this object. */
197 if (l->l_searchlist.r_list == NULL && l->l_initfini == NULL
198 && l != map && l->l_ldnum > 0)
199 {
200 /* l->l_ldnum includes space for the terminating NULL. */
201 if (!scratch_buffer_set_array_size
202 (&needed_space, l->l_ldnum, sizeof (struct link_map *)))
203 _dl_signal_error (ENOMEM, map->l_name, NULL,
204 N_("cannot allocate dependency buffer"));
205 needed = needed_space.data;
206 }
207
208 if (l->l_info[DT_NEEDED] || l->l_info[AUXTAG] || l->l_info[FILTERTAG])
209 {
210 const char *strtab = (const void *) D_PTR (l, l_info[DT_STRTAB]);
211 struct openaux_args args;
212 struct list *orig;
213 const ElfW(Dyn) *d;
214
215 args.strtab = strtab;
216 args.map = l;
217 args.trace_mode = trace_mode;
218 args.open_mode = open_mode;
219 orig = runp;
220
221 for (d = l->l_ld; d->d_tag != DT_NULL; ++d)
222 if (__builtin_expect (d->d_tag, DT_NEEDED) == DT_NEEDED)
223 {
224 /* Map in the needed object. */
225 struct link_map *dep;
226
227 /* Recognize DSTs. */
228 name = expand_dst (l, strtab + d->d_un.d_val, 0);
229 /* Store the tag in the argument structure. */
230 args.name = name;
231
232 int err = _dl_catch_exception (&exception, openaux, &args);
233 if (__glibc_unlikely (exception.errstring != NULL))
234 {
235 if (err)
236 errno_reason = err;
237 else
238 errno_reason = -1;
239 goto out;
240 }
241 else
242 dep = args.aux;
243
244 if (! dep->l_reserved)
245 {
246 /* Allocate new entry. */
247 struct list *newp;
248
249 newp = alloca (sizeof (struct list));
250
251 /* Append DEP to the list. */
252 newp->map = dep;
253 newp->done = 0;
254 newp->next = NULL;
255 tail->next = newp;
256 tail = newp;
257 ++nlist;
258 /* Set the mark bit that says it's already in the list. */
259 dep->l_reserved = 1;
260 }
261
262 /* Remember this dependency. */
263 if (needed != NULL)
264 needed[nneeded++] = dep;
265 }
266 else if (d->d_tag == DT_AUXILIARY || d->d_tag == DT_FILTER)
267 {
268 struct list *newp;
269
270 /* Recognize DSTs. */
271 name = expand_dst (l, strtab + d->d_un.d_val,
272 d->d_tag == DT_AUXILIARY);
273 /* Store the tag in the argument structure. */
274 args.name = name;
275
276 /* Say that we are about to load an auxiliary library. */
277 if (__builtin_expect (GLRO(dl_debug_mask) & DL_DEBUG_LIBS,
278 0))
279 _dl_debug_printf ("load auxiliary object=%s"
280 " requested by file=%s\n",
281 name,
282 DSO_FILENAME (l->l_name));
283
284 /* We must be prepared that the addressed shared
285 object is not available. For filter objects the dependency
286 must be available. */
287 int err = _dl_catch_exception (&exception, openaux, &args);
288 if (__glibc_unlikely (exception.errstring != NULL))
289 {
290 if (d->d_tag == DT_AUXILIARY)
291 {
292 /* We are not interested in the error message. */
293 _dl_exception_free (&exception);
294 /* Simply ignore this error and continue the work. */
295 continue;
296 }
297 else
298 {
299 if (err)
300 errno_reason = err;
301 else
302 errno_reason = -1;
303 goto out;
304 }
305 }
306
307 /* The auxiliary object is actually available.
308 Incorporate the map in all the lists. */
309
310 /* Allocate new entry. This always has to be done. */
311 newp = alloca (sizeof (struct list));
312
313 /* We want to insert the new map before the current one,
314 but we have no back links. So we copy the contents of
315 the current entry over. Note that ORIG and NEWP now
316 have switched their meanings. */
317 memcpy (newp, orig, sizeof (*newp));
318
319 /* Initialize new entry. */
320 orig->done = 0;
321 orig->map = args.aux;
322
323 /* Remember this dependency. */
324 if (needed != NULL)
325 needed[nneeded++] = args.aux;
326
327 /* We must handle two situations here: the map is new,
328 so we must add it in all three lists. If the map
329 is already known, we have two further possibilities:
330 - if the object is before the current map in the
331 search list, we do nothing. It is already found
332 early
333 - if the object is after the current one, we must
334 move it just before the current map to make sure
335 the symbols are found early enough
336 */
337 if (args.aux->l_reserved)
338 {
339 /* The object is already somewhere in the list.
340 Locate it first. */
341 struct list *late;
342
343 /* This object is already in the search list we
344 are building. Don't add a duplicate pointer.
345 Just added by _dl_map_object. */
346 for (late = newp; late->next != NULL; late = late->next)
347 if (late->next->map == args.aux)
348 break;
349
350 if (late->next != NULL)
351 {
352 /* The object is somewhere behind the current
353 position in the search path. We have to
354 move it to this earlier position. */
355 orig->next = newp;
356
357 /* Now remove the later entry from the list
358 and adjust the tail pointer. */
359 if (tail == late->next)
360 tail = late;
361 late->next = late->next->next;
362
363 /* We must move the object earlier in the chain. */
364 if (args.aux->l_prev != NULL)
365 args.aux->l_prev->l_next = args.aux->l_next;
366 if (args.aux->l_next != NULL)
367 args.aux->l_next->l_prev = args.aux->l_prev;
368
369 args.aux->l_prev = newp->map->l_prev;
370 newp->map->l_prev = args.aux;
371 if (args.aux->l_prev != NULL)
372 args.aux->l_prev->l_next = args.aux;
373 args.aux->l_next = newp->map;
374 }
375 else
376 {
377 /* The object must be somewhere earlier in the
378 list. Undo to the current list element what
379 we did above. */
380 memcpy (orig, newp, sizeof (*newp));
381 continue;
382 }
383 }
384 else
385 {
386 /* This is easy. We just add the symbol right here. */
387 orig->next = newp;
388 ++nlist;
389 /* Set the mark bit that says it's already in the list. */
390 args.aux->l_reserved = 1;
391
392 /* The only problem is that in the double linked
393 list of all objects we don't have this new
394 object at the correct place. Correct this here. */
395 if (args.aux->l_prev)
396 args.aux->l_prev->l_next = args.aux->l_next;
397 if (args.aux->l_next)
398 args.aux->l_next->l_prev = args.aux->l_prev;
399
400 args.aux->l_prev = newp->map->l_prev;
401 newp->map->l_prev = args.aux;
402 if (args.aux->l_prev != NULL)
403 args.aux->l_prev->l_next = args.aux;
404 args.aux->l_next = newp->map;
405 }
406
407 /* Move the tail pointer if necessary. */
408 if (orig == tail)
409 tail = newp;
410
411 /* Move on the insert point. */
412 orig = newp;
413 }
414 }
415
416 /* Terminate the list of dependencies and store the array address. */
417 if (needed != NULL)
418 {
419 needed[nneeded++] = NULL;
420
421 struct link_map **l_initfini = (struct link_map **)
422 malloc ((2 * nneeded + 1) * sizeof needed[0]);
423 if (l_initfini == NULL)
424 {
425 scratch_buffer_free (&needed_space);
426 _dl_signal_error (ENOMEM, map->l_name, NULL,
427 N_("cannot allocate dependency list"));
428 }
429 l_initfini[0] = l;
430 memcpy (&l_initfini[1], needed, nneeded * sizeof needed[0]);
431 memcpy (&l_initfini[nneeded + 1], l_initfini,
432 nneeded * sizeof needed[0]);
433 atomic_write_barrier ();
434 l->l_initfini = l_initfini;
435 l->l_free_initfini = 1;
436 }
437
438 /* If we have no auxiliary objects just go on to the next map. */
439 if (runp->done)
440 do
441 runp = runp->next;
442 while (runp != NULL && runp->done);
443 }
444
445 out:
446 scratch_buffer_free (&needed_space);
447
448 if (errno == 0 && errno_saved != 0)
449 __set_errno (errno_saved);
450
451 struct link_map **old_l_initfini = NULL;
452 if (map->l_initfini != NULL && map->l_type == lt_loaded)
453 {
454 /* This object was previously loaded as a dependency and we have
455 a separate l_initfini list. We don't need it anymore. */
456 assert (map->l_searchlist.r_list == NULL);
457 old_l_initfini = map->l_initfini;
458 }
459
460 /* Store the search list we built in the object. It will be used for
461 searches in the scope of this object. */
462 struct link_map **l_initfini =
463 (struct link_map **) malloc ((2 * nlist + 1)
464 * sizeof (struct link_map *));
465 if (l_initfini == NULL)
466 _dl_signal_error (ENOMEM, map->l_name, NULL,
467 N_("cannot allocate symbol search list"));
468
469
470 map->l_searchlist.r_list = &l_initfini[nlist + 1];
471 map->l_searchlist.r_nlist = nlist;
472 unsigned int map_index = UINT_MAX;
473
474 for (nlist = 0, runp = known; runp; runp = runp->next)
475 {
476 /* _dl_sort_maps ignores l_faked object, so it is safe to not consider
477 them for nlist. */
478 if (__builtin_expect (trace_mode, 0) && runp->map->l_faked)
479 /* This can happen when we trace the loading. */
480 --map->l_searchlist.r_nlist;
481 else
482 {
483 if (runp->map == map)
484 map_index = nlist;
485 map->l_searchlist.r_list[nlist++] = runp->map;
486 }
487
488 /* Now clear all the mark bits we set in the objects on the search list
489 to avoid duplicates, so the next call starts fresh. */
490 runp->map->l_reserved = 0;
491 }
492
493 /* Maybe we can remove some relocation dependencies now. */
494 struct link_map_reldeps *l_reldeps = NULL;
495 if (map->l_reldeps != NULL)
496 {
497 for (i = 0; i < nlist; ++i)
498 map->l_searchlist.r_list[i]->l_reserved = 1;
499
500 /* Avoid removing relocation dependencies of the main binary. */
501 map->l_reserved = 0;
502 struct link_map **list = &map->l_reldeps->list[0];
503 for (i = 0; i < map->l_reldeps->act; ++i)
504 if (list[i]->l_reserved)
505 {
506 /* Need to allocate new array of relocation dependencies. */
507 l_reldeps = malloc (sizeof (*l_reldeps)
508 + map->l_reldepsmax
509 * sizeof (struct link_map *));
510 if (l_reldeps == NULL)
511 /* Bad luck, keep the reldeps duplicated between
512 map->l_reldeps->list and map->l_initfini lists. */
513 ;
514 else
515 {
516 unsigned int j = i;
517 memcpy (&l_reldeps->list[0], &list[0],
518 i * sizeof (struct link_map *));
519 for (i = i + 1; i < map->l_reldeps->act; ++i)
520 if (!list[i]->l_reserved)
521 l_reldeps->list[j++] = list[i];
522 l_reldeps->act = j;
523 }
524 }
525
526 for (i = 0; i < nlist; ++i)
527 map->l_searchlist.r_list[i]->l_reserved = 0;
528 }
529
530 /* Sort the initializer list to take dependencies into account. Always
531 initialize the binary itself last. */
532 assert (map_index < nlist);
533 if (map_index > 0)
534 {
535 /* Copy the binary into position 0. */
536 l_initfini[0] = map->l_searchlist.r_list[map_index];
537
538 /* Copy the filtees. */
539 for (i = 0; i < map_index; ++i)
540 l_initfini[i+1] = map->l_searchlist.r_list[i];
541
542 /* Copy the remainder. */
543 for (i = map_index + 1; i < nlist; ++i)
544 l_initfini[i] = map->l_searchlist.r_list[i];
545 }
546 else
547 memcpy (l_initfini, map->l_searchlist.r_list,
548 nlist * sizeof (struct link_map *));
549
550 /* If libc.so.6 is the main map, it participates in the sort, so
551 that the relocation order is correct regarding libc.so.6. */
552 _dl_sort_maps (l_initfini, nlist,
553 (l_initfini[0] != GL (dl_ns)[l_initfini[0]->l_ns].libc_map),
554 false);
555
556 /* Terminate the list of dependencies. */
557 l_initfini[nlist] = NULL;
558 atomic_write_barrier ();
559 map->l_initfini = l_initfini;
560 map->l_free_initfini = 1;
561 if (l_reldeps != NULL)
562 {
563 atomic_write_barrier ();
564 void *old_l_reldeps = map->l_reldeps;
565 map->l_reldeps = l_reldeps;
566 _dl_scope_free (old_l_reldeps);
567 }
568 if (old_l_initfini != NULL)
569 _dl_scope_free (old_l_initfini);
570
571 if (errno_reason)
572 _dl_signal_exception (errno_reason == -1 ? 0 : errno_reason,
573 &exception, NULL);
574}
575