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