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