1/* Load the dependencies of a mapped object.
2 Copyright (C) 1996-2016 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
71internal_function
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, 0); \
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, 0); \
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
156internal_function
157_dl_map_object_deps (struct link_map *map,
158 struct link_map **preloads, unsigned int npreloads,
159 int trace_mode, int open_mode)
160{
161 struct list *known = __alloca (sizeof *known * (1 + npreloads + 1));
162 struct list *runp, *tail;
163 unsigned int nlist, i;
164 /* Object name. */
165 const char *name;
166 int errno_saved;
167 int errno_reason;
168 const char *errstring;
169 const char *objname;
170
171 /* No loaded object so far. */
172 nlist = 0;
173
174 /* First load MAP itself. */
175 preload (known, &nlist, map);
176
177 /* Add the preloaded items after MAP but before any of its dependencies. */
178 for (i = 0; i < npreloads; ++i)
179 preload (known, &nlist, preloads[i]);
180
181 /* Terminate the lists. */
182 known[nlist - 1].next = NULL;
183
184 /* Pointer to last unique object. */
185 tail = &known[nlist - 1];
186
187 /* No alloca'd space yet. */
188 struct link_map **needed_space = NULL;
189 size_t needed_space_bytes = 0;
190
191 /* Process each element of the search list, loading each of its
192 auxiliary objects and immediate dependencies. Auxiliary objects
193 will be added in the list before the object itself and
194 dependencies will be appended to the list as we step through it.
195 This produces a flat, ordered list that represents a
196 breadth-first search of the dependency tree.
197
198 The whole process is complicated by the fact that we better
199 should use alloca for the temporary list elements. But using
200 alloca means we cannot use recursive function calls. */
201 errno_saved = errno;
202 errno_reason = 0;
203 errstring = NULL;
204 errno = 0;
205 name = NULL;
206 for (runp = known; runp; )
207 {
208 struct link_map *l = runp->map;
209 struct link_map **needed = NULL;
210 unsigned int nneeded = 0;
211
212 /* Unless otherwise stated, this object is handled. */
213 runp->done = 1;
214
215 /* Allocate a temporary record to contain the references to the
216 dependencies of this object. */
217 if (l->l_searchlist.r_list == NULL && l->l_initfini == NULL
218 && l != map && l->l_ldnum > 0)
219 {
220 size_t new_size = l->l_ldnum * sizeof (struct link_map *);
221
222 if (new_size > needed_space_bytes)
223 needed_space
224 = extend_alloca (needed_space, needed_space_bytes, new_size);
225
226 needed = needed_space;
227 }
228
229 if (l->l_info[DT_NEEDED] || l->l_info[AUXTAG] || l->l_info[FILTERTAG])
230 {
231 const char *strtab = (const void *) D_PTR (l, l_info[DT_STRTAB]);
232 struct openaux_args args;
233 struct list *orig;
234 const ElfW(Dyn) *d;
235
236 args.strtab = strtab;
237 args.map = l;
238 args.trace_mode = trace_mode;
239 args.open_mode = open_mode;
240 orig = runp;
241
242 for (d = l->l_ld; d->d_tag != DT_NULL; ++d)
243 if (__builtin_expect (d->d_tag, DT_NEEDED) == DT_NEEDED)
244 {
245 /* Map in the needed object. */
246 struct link_map *dep;
247
248 /* Recognize DSTs. */
249 name = expand_dst (l, strtab + d->d_un.d_val, 0);
250 /* Store the tag in the argument structure. */
251 args.name = name;
252
253 bool malloced;
254 int err = _dl_catch_error (&objname, &errstring, &malloced,
255 openaux, &args);
256 if (__glibc_unlikely (errstring != NULL))
257 {
258 char *new_errstring = strdupa (errstring);
259 objname = strdupa (objname);
260 if (malloced)
261 free ((char *) errstring);
262 errstring = new_errstring;
263
264 if (err)
265 errno_reason = err;
266 else
267 errno_reason = -1;
268 goto out;
269 }
270 else
271 dep = args.aux;
272
273 if (! dep->l_reserved)
274 {
275 /* Allocate new entry. */
276 struct list *newp;
277
278 newp = alloca (sizeof (struct list));
279
280 /* Append DEP to the list. */
281 newp->map = dep;
282 newp->done = 0;
283 newp->next = NULL;
284 tail->next = newp;
285 tail = newp;
286 ++nlist;
287 /* Set the mark bit that says it's already in the list. */
288 dep->l_reserved = 1;
289 }
290
291 /* Remember this dependency. */
292 if (needed != NULL)
293 needed[nneeded++] = dep;
294 }
295 else if (d->d_tag == DT_AUXILIARY || d->d_tag == DT_FILTER)
296 {
297 struct list *newp;
298
299 /* Recognize DSTs. */
300 name = expand_dst (l, strtab + d->d_un.d_val,
301 d->d_tag == DT_AUXILIARY);
302 /* Store the tag in the argument structure. */
303 args.name = name;
304
305 /* Say that we are about to load an auxiliary library. */
306 if (__builtin_expect (GLRO(dl_debug_mask) & DL_DEBUG_LIBS,
307 0))
308 _dl_debug_printf ("load auxiliary object=%s"
309 " requested by file=%s\n",
310 name,
311 DSO_FILENAME (l->l_name));
312
313 /* We must be prepared that the addressed shared
314 object is not available. For filter objects the dependency
315 must be available. */
316 bool malloced;
317 int err = _dl_catch_error (&objname, &errstring, &malloced,
318 openaux, &args);
319
320 if (__glibc_unlikely (errstring != NULL))
321 {
322 if (d->d_tag == DT_AUXILIARY)
323 {
324 /* We are not interested in the error message. */
325 assert (errstring != NULL);
326 if (malloced)
327 free ((char *) errstring);
328
329 /* Simply ignore this error and continue the work. */
330 continue;
331 }
332 else
333 {
334
335 char *new_errstring = strdupa (errstring);
336 objname = strdupa (objname);
337 if (malloced)
338 free ((char *) errstring);
339 errstring = new_errstring;
340
341 if (err)
342 errno_reason = err;
343 else
344 errno_reason = -1;
345 goto out;
346 }
347 }
348
349 /* The auxiliary object is actually available.
350 Incorporate the map in all the lists. */
351
352 /* Allocate new entry. This always has to be done. */
353 newp = alloca (sizeof (struct list));
354
355 /* We want to insert the new map before the current one,
356 but we have no back links. So we copy the contents of
357 the current entry over. Note that ORIG and NEWP now
358 have switched their meanings. */
359 memcpy (newp, orig, sizeof (*newp));
360
361 /* Initialize new entry. */
362 orig->done = 0;
363 orig->map = args.aux;
364
365 /* Remember this dependency. */
366 if (needed != NULL)
367 needed[nneeded++] = args.aux;
368
369 /* We must handle two situations here: the map is new,
370 so we must add it in all three lists. If the map
371 is already known, we have two further possibilities:
372 - if the object is before the current map in the
373 search list, we do nothing. It is already found
374 early
375 - if the object is after the current one, we must
376 move it just before the current map to make sure
377 the symbols are found early enough
378 */
379 if (args.aux->l_reserved)
380 {
381 /* The object is already somewhere in the list.
382 Locate it first. */
383 struct list *late;
384
385 /* This object is already in the search list we
386 are building. Don't add a duplicate pointer.
387 Just added by _dl_map_object. */
388 for (late = newp; late->next != NULL; late = late->next)
389 if (late->next->map == args.aux)
390 break;
391
392 if (late->next != NULL)
393 {
394 /* The object is somewhere behind the current
395 position in the search path. We have to
396 move it to this earlier position. */
397 orig->next = newp;
398
399 /* Now remove the later entry from the list
400 and adjust the tail pointer. */
401 if (tail == late->next)
402 tail = late;
403 late->next = late->next->next;
404
405 /* We must move the object earlier in the chain. */
406 if (args.aux->l_prev != NULL)
407 args.aux->l_prev->l_next = args.aux->l_next;
408 if (args.aux->l_next != NULL)
409 args.aux->l_next->l_prev = args.aux->l_prev;
410
411 args.aux->l_prev = newp->map->l_prev;
412 newp->map->l_prev = args.aux;
413 if (args.aux->l_prev != NULL)
414 args.aux->l_prev->l_next = args.aux;
415 args.aux->l_next = newp->map;
416 }
417 else
418 {
419 /* The object must be somewhere earlier in the
420 list. Undo to the current list element what
421 we did above. */
422 memcpy (orig, newp, sizeof (*newp));
423 continue;
424 }
425 }
426 else
427 {
428 /* This is easy. We just add the symbol right here. */
429 orig->next = newp;
430 ++nlist;
431 /* Set the mark bit that says it's already in the list. */
432 args.aux->l_reserved = 1;
433
434 /* The only problem is that in the double linked
435 list of all objects we don't have this new
436 object at the correct place. Correct this here. */
437 if (args.aux->l_prev)
438 args.aux->l_prev->l_next = args.aux->l_next;
439 if (args.aux->l_next)
440 args.aux->l_next->l_prev = args.aux->l_prev;
441
442 args.aux->l_prev = newp->map->l_prev;
443 newp->map->l_prev = args.aux;
444 if (args.aux->l_prev != NULL)
445 args.aux->l_prev->l_next = args.aux;
446 args.aux->l_next = newp->map;
447 }
448
449 /* Move the tail pointer if necessary. */
450 if (orig == tail)
451 tail = newp;
452
453 /* Move on the insert point. */
454 orig = newp;
455 }
456 }
457
458 /* Terminate the list of dependencies and store the array address. */
459 if (needed != NULL)
460 {
461 needed[nneeded++] = NULL;
462
463 struct link_map **l_initfini = (struct link_map **)
464 malloc ((2 * nneeded + 1) * sizeof needed[0]);
465 if (l_initfini == NULL)
466 _dl_signal_error (ENOMEM, map->l_name, NULL,
467 N_("cannot allocate dependency list"));
468 l_initfini[0] = l;
469 memcpy (&l_initfini[1], needed, nneeded * sizeof needed[0]);
470 memcpy (&l_initfini[nneeded + 1], l_initfini,
471 nneeded * sizeof needed[0]);
472 atomic_write_barrier ();
473 l->l_initfini = l_initfini;
474 l->l_free_initfini = 1;
475 }
476
477 /* If we have no auxiliary objects just go on to the next map. */
478 if (runp->done)
479 do
480 runp = runp->next;
481 while (runp != NULL && runp->done);
482 }
483
484 out:
485 if (errno == 0 && errno_saved != 0)
486 __set_errno (errno_saved);
487
488 struct link_map **old_l_initfini = NULL;
489 if (map->l_initfini != NULL && map->l_type == lt_loaded)
490 {
491 /* This object was previously loaded as a dependency and we have
492 a separate l_initfini list. We don't need it anymore. */
493 assert (map->l_searchlist.r_list == NULL);
494 old_l_initfini = map->l_initfini;
495 }
496
497 /* Store the search list we built in the object. It will be used for
498 searches in the scope of this object. */
499 struct link_map **l_initfini =
500 (struct link_map **) malloc ((2 * nlist + 1)
501 * sizeof (struct link_map *));
502 if (l_initfini == NULL)
503 _dl_signal_error (ENOMEM, map->l_name, NULL,
504 N_("cannot allocate symbol search list"));
505
506
507 map->l_searchlist.r_list = &l_initfini[nlist + 1];
508 map->l_searchlist.r_nlist = nlist;
509
510 for (nlist = 0, runp = known; runp; runp = runp->next)
511 {
512 if (__builtin_expect (trace_mode, 0) && runp->map->l_faked)
513 /* This can happen when we trace the loading. */
514 --map->l_searchlist.r_nlist;
515 else
516 map->l_searchlist.r_list[nlist++] = runp->map;
517
518 /* Now clear all the mark bits we set in the objects on the search list
519 to avoid duplicates, so the next call starts fresh. */
520 runp->map->l_reserved = 0;
521 }
522
523 if (__builtin_expect (GLRO(dl_debug_mask) & DL_DEBUG_PRELINK, 0) != 0
524 && map == GL(dl_ns)[LM_ID_BASE]._ns_loaded)
525 {
526 /* If we are to compute conflicts, we have to build local scope
527 for each library, not just the ultimate loader. */
528 for (i = 0; i < nlist; ++i)
529 {
530 struct link_map *l = map->l_searchlist.r_list[i];
531 unsigned int j, cnt;
532
533 /* The local scope has been already computed. */
534 if (l == map
535 || (l->l_local_scope[0]
536 && l->l_local_scope[0]->r_nlist) != 0)
537 continue;
538
539 if (l->l_info[AUXTAG] || l->l_info[FILTERTAG])
540 {
541 /* As current DT_AUXILIARY/DT_FILTER implementation needs to be
542 rewritten, no need to bother with prelinking the old
543 implementation. */
544 _dl_signal_error (EINVAL, l->l_name, NULL, N_("\
545Filters not supported with LD_TRACE_PRELINKING"));
546 }
547
548 cnt = _dl_build_local_scope (l_initfini, l);
549 assert (cnt <= nlist);
550 for (j = 0; j < cnt; j++)
551 {
552 l_initfini[j]->l_reserved = 0;
553 if (j && __builtin_expect (l_initfini[j]->l_info[DT_SYMBOLIC]
554 != NULL, 0))
555 l->l_symbolic_in_local_scope = true;
556 }
557
558 l->l_local_scope[0] =
559 (struct r_scope_elem *) malloc (sizeof (struct r_scope_elem)
560 + (cnt
561 * sizeof (struct link_map *)));
562 if (l->l_local_scope[0] == NULL)
563 _dl_signal_error (ENOMEM, map->l_name, NULL,
564 N_("cannot allocate symbol search list"));
565 l->l_local_scope[0]->r_nlist = cnt;
566 l->l_local_scope[0]->r_list =
567 (struct link_map **) (l->l_local_scope[0] + 1);
568 memcpy (l->l_local_scope[0]->r_list, l_initfini,
569 cnt * sizeof (struct link_map *));
570 }
571 }
572
573 /* Maybe we can remove some relocation dependencies now. */
574 assert (map->l_searchlist.r_list[0] == map);
575 struct link_map_reldeps *l_reldeps = NULL;
576 if (map->l_reldeps != NULL)
577 {
578 for (i = 1; i < nlist; ++i)
579 map->l_searchlist.r_list[i]->l_reserved = 1;
580
581 struct link_map **list = &map->l_reldeps->list[0];
582 for (i = 0; i < map->l_reldeps->act; ++i)
583 if (list[i]->l_reserved)
584 {
585 /* Need to allocate new array of relocation dependencies. */
586 l_reldeps = malloc (sizeof (*l_reldeps)
587 + map->l_reldepsmax
588 * sizeof (struct link_map *));
589 if (l_reldeps == NULL)
590 /* Bad luck, keep the reldeps duplicated between
591 map->l_reldeps->list and map->l_initfini lists. */
592 ;
593 else
594 {
595 unsigned int j = i;
596 memcpy (&l_reldeps->list[0], &list[0],
597 i * sizeof (struct link_map *));
598 for (i = i + 1; i < map->l_reldeps->act; ++i)
599 if (!list[i]->l_reserved)
600 l_reldeps->list[j++] = list[i];
601 l_reldeps->act = j;
602 }
603 }
604
605 for (i = 1; i < nlist; ++i)
606 map->l_searchlist.r_list[i]->l_reserved = 0;
607 }
608
609 /* Sort the initializer list to take dependencies into account. The binary
610 itself will always be initialize last. */
611 memcpy (l_initfini, map->l_searchlist.r_list,
612 nlist * sizeof (struct link_map *));
613 if (__glibc_likely (nlist > 1))
614 {
615 /* We can skip looking for the binary itself which is at the front
616 of the search list. */
617 i = 1;
618 uint16_t seen[nlist];
619 memset (seen, 0, nlist * sizeof (seen[0]));
620 while (1)
621 {
622 /* Keep track of which object we looked at this round. */
623 ++seen[i];
624 struct link_map *thisp = l_initfini[i];
625
626 /* Find the last object in the list for which the current one is
627 a dependency and move the current object behind the object
628 with the dependency. */
629 unsigned int k = nlist - 1;
630 while (k > i)
631 {
632 struct link_map **runp = l_initfini[k]->l_initfini;
633 if (runp != NULL)
634 /* Look through the dependencies of the object. */
635 while (*runp != NULL)
636 if (__glibc_unlikely (*runp++ == thisp))
637 {
638 /* Move the current object to the back past the last
639 object with it as the dependency. */
640 memmove (&l_initfini[i], &l_initfini[i + 1],
641 (k - i) * sizeof (l_initfini[0]));
642 l_initfini[k] = thisp;
643
644 if (seen[i + 1] > nlist - i)
645 {
646 ++i;
647 goto next_clear;
648 }
649
650 uint16_t this_seen = seen[i];
651 memmove (&seen[i], &seen[i + 1],
652 (k - i) * sizeof (seen[0]));
653 seen[k] = this_seen;
654
655 goto next;
656 }
657
658 --k;
659 }
660
661 if (++i == nlist)
662 break;
663 next_clear:
664 memset (&seen[i], 0, (nlist - i) * sizeof (seen[0]));
665
666 next:;
667 }
668 }
669
670 /* Terminate the list of dependencies. */
671 l_initfini[nlist] = NULL;
672 atomic_write_barrier ();
673 map->l_initfini = l_initfini;
674 map->l_free_initfini = 1;
675 if (l_reldeps != NULL)
676 {
677 atomic_write_barrier ();
678 void *old_l_reldeps = map->l_reldeps;
679 map->l_reldeps = l_reldeps;
680 _dl_scope_free (old_l_reldeps);
681 }
682 if (old_l_initfini != NULL)
683 _dl_scope_free (old_l_initfini);
684
685 if (errno_reason)
686 _dl_signal_error (errno_reason == -1 ? 0 : errno_reason, objname,
687 NULL, errstring);
688}
689