Update copyright dates with scripts/update-copyrights.
[platform/upstream/glibc.git] / elf / dl-deps.c
1 /* Load the dependencies of a mapped object.
2    Copyright (C) 1996-2015 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.  */
45 struct 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
58 static void
59 openaux (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
70 static ptrdiff_t
71 internal_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 */
91 struct 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_("\
113 DST 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_("\
126 empty 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_("\
132 cannot load auxiliary `%s' because of empty dynamic string token "            \
133                                             "substitution\n"), __str);        \
134                 continue;                                                     \
135               }                                                               \
136           }                                                                   \
137       }                                                                       \
138                                                                               \
139     __result; })
140
141 static void
142 preload (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
155 void
156 internal_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_("\
545 Filters 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 }