* stdio-common/printf_fp.c (__printf_fp): Add prototype for nested
[kopensolaris-gnu/glibc.git] / elf / dl-deps.c
1 /* Load the dependencies of a mapped object.
2    Copyright (C) 1996, 1997, 1998, 1999, 2000 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 Library General Public License as
7    published by the Free Software Foundation; either version 2 of the
8    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    Library General Public License for more details.
14
15    You should have received a copy of the GNU Library General Public
16    License along with the GNU C Library; see the file COPYING.LIB.  If not,
17    write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18    Boston, MA 02111-1307, USA.  */
19
20 #include <assert.h>
21 #include <dlfcn.h>
22 #include <errno.h>
23 #include <libintl.h>
24 #include <stdlib.h>
25 #include <string.h>
26 #include <unistd.h>
27 #include <sys/param.h>
28 #include <ldsodefs.h>
29
30 #include <dl-dst.h>
31
32 /* Whether an shared object references one or more auxiliary objects
33    is signaled by the AUXTAG entry in l_info.  */
34 #define AUXTAG  (DT_NUM + DT_THISPROCNUM + DT_VERSIONTAGNUM \
35                  + DT_EXTRATAGIDX (DT_AUXILIARY))
36 /* Whether an shared object references one or more auxiliary objects
37    is signaled by the AUXTAG entry in l_info.  */
38 #define FILTERTAG (DT_NUM + DT_THISPROCNUM + DT_VERSIONTAGNUM \
39                    + DT_EXTRATAGIDX (DT_FILTER))
40
41 /* This is zero at program start to signal that the global scope map is
42    allocated by rtld.  Later it keeps the size of the map.  It might be
43    reset if in _dl_close if the last global object is removed.  */
44 size_t _dl_global_scope_alloc;
45
46 extern size_t _dl_platformlen;
47
48 /* When loading auxiliary objects we must ignore errors.  It's ok if
49    an object is missing.  */
50 struct openaux_args
51   {
52     /* The arguments to openaux.  */
53     struct link_map *map;
54     int trace_mode;
55     const char *strtab;
56     const char *name;
57
58     /* The return value of openaux.  */
59     struct link_map *aux;
60   };
61
62 static void
63 openaux (void *a)
64 {
65   struct openaux_args *args = (struct openaux_args *) a;
66
67   args->aux = _dl_map_object (args->map, args->name, 0,
68                               (args->map->l_type == lt_executable
69                                ? lt_library : args->map->l_type),
70                               args->trace_mode, 0);
71 }
72
73
74
75 /* We use a very special kind of list to track the two kinds paths
76    through the list of loaded shared objects.  We have to
77
78    - produce a flat list with unique members of all involved objects
79
80    - produce a flat list of all shared objects.
81 */
82 struct list
83   {
84     int done;                   /* Nonzero if this map was processed.  */
85     struct link_map *map;       /* The data.  */
86
87     struct list *unique;        /* Elements for normal list.  */
88     struct list *dup;           /* Elements in complete list.  */
89   };
90
91
92 /* Macro to expand DST.  It is an macro since we use `alloca'.  */
93 #define expand_dst(l, str, fatal) \
94   ({                                                                          \
95     const char *__str = (str);                                                \
96     const char *__result = __str;                                             \
97     size_t __cnt = DL_DST_COUNT(__str, 0);                                    \
98                                                                               \
99     if (__cnt != 0)                                                           \
100       {                                                                       \
101         char *__newp;                                                         \
102                                                                               \
103         /* DST must not appear in SUID/SGID programs.  */                     \
104         if (__libc_enable_secure)                                             \
105           _dl_signal_error (0, __str,                                         \
106                             N_("DST not allowed in SUID/SGID programs"));     \
107                                                                               \
108         __newp = (char *) alloca (DL_DST_REQUIRED (l, __str, strlen (__str),  \
109                                                    __cnt));                   \
110                                                                               \
111         __result = DL_DST_SUBSTITUTE (l, __str, __newp, 0);                   \
112                                                                               \
113         if (*__result == '\0')                                                \
114           {                                                                   \
115             /* The replacement for the DST is not known.  We can't            \
116                processed.  */                                                 \
117             if (fatal)                                                        \
118               _dl_signal_error (0, __str, N_("\
119 empty dynamics string token substitution"));                                  \
120             else                                                              \
121               {                                                               \
122                 /* This is for DT_AUXILIARY.  */                              \
123                 if (__builtin_expect (_dl_debug_libs, 0))                     \
124                   _dl_debug_message (1, "cannot load auxiliary `", __str,     \
125                                      "' because of empty dynamic string"      \
126                                      " token substitution\n", NULL);          \
127                 continue;                                                     \
128               }                                                               \
129           }                                                                   \
130       }                                                                       \
131                                                                               \
132     __result; })
133
134
135 void
136 internal_function
137 _dl_map_object_deps (struct link_map *map,
138                      struct link_map **preloads, unsigned int npreloads,
139                      int trace_mode)
140 {
141   struct list known[1 + npreloads + 1];
142   struct list *runp, *utail, *dtail;
143   unsigned int nlist, nduplist, i;
144
145   auto inline void preload (struct link_map *map);
146
147   inline void preload (struct link_map *map)
148     {
149       known[nlist].done = 0;
150       known[nlist].map = map;
151
152       known[nlist].unique = &known[nlist + 1];
153       known[nlist].dup = &known[nlist + 1];
154
155       ++nlist;
156       /* We use `l_reserved' as a mark bit to detect objects we have
157          already put in the search list and avoid adding duplicate
158          elements later in the list.  */
159       map->l_reserved = 1;
160     }
161
162   /* No loaded object so far.  */
163   nlist = 0;
164
165   /* First load MAP itself.  */
166   preload (map);
167
168   /* Add the preloaded items after MAP but before any of its dependencies.  */
169   for (i = 0; i < npreloads; ++i)
170     preload (preloads[i]);
171
172   /* Terminate the lists.  */
173   known[nlist - 1].unique = NULL;
174   known[nlist - 1].dup = NULL;
175
176   /* Pointer to last unique object.  */
177   utail = &known[nlist - 1];
178   /* Pointer to last loaded object.  */
179   dtail = &known[nlist - 1];
180
181   /* Until now we have the same number of libraries in the normal and
182      the list with duplicates.  */
183   nduplist = nlist;
184
185   /* Process each element of the search list, loading each of its
186      auxiliary objects and immediate dependencies.  Auxiliary objects
187      will be added in the list before the object itself and
188      dependencies will be appended to the list as we step through it.
189      This produces a flat, ordered list that represents a
190      breadth-first search of the dependency tree.
191
192      The whole process is complicated by the fact that we better
193      should use alloca for the temporary list elements.  But using
194      alloca means we cannot use recursive function calls.  */
195   for (runp = known; runp; )
196     {
197       struct link_map *l = runp->map;
198       struct link_map **needed = NULL;
199       unsigned int nneeded = 0;
200
201       /* Unless otherwise stated, this object is handled.  */
202       runp->done = 1;
203
204       /* Allocate a temporary record to contain the references to the
205          dependencies of this object.  */
206       if (l->l_searchlist.r_list == NULL && l->l_initfini == NULL
207           && l != map && l->l_ldnum > 0)
208         needed = (struct link_map **) alloca (l->l_ldnum
209                                               * sizeof (struct link_map *));
210
211       if (l->l_info[DT_NEEDED] || l->l_info[AUXTAG] || l->l_info[FILTERTAG])
212         {
213           const char *strtab = (const void *) D_PTR (l, l_info[DT_STRTAB]);
214           struct openaux_args args;
215           struct list *orig;
216           const ElfW(Dyn) *d;
217
218           args.strtab = strtab;
219           args.map = l;
220           args.trace_mode = trace_mode;
221           orig = runp;
222
223           for (d = l->l_ld; d->d_tag != DT_NULL; ++d)
224             if (__builtin_expect (d->d_tag, DT_NEEDED) == DT_NEEDED)
225               {
226                 /* Map in the needed object.  */
227                 struct link_map *dep;
228                 /* Allocate new entry.  */
229                 struct list *newp;
230                 /* Object name.  */
231                 const char *name;
232
233                 /* Recognize DSTs.  */
234                 name = expand_dst (l, strtab + d->d_un.d_val, 0);
235
236                 dep = _dl_map_object (l, name, 0,
237                                       l->l_type == lt_executable ? lt_library :
238                                       l->l_type, trace_mode, 0);
239
240                 /* Add it in any case to the duplicate list.  */
241                 newp = alloca (sizeof (struct list));
242                 newp->map = dep;
243                 newp->dup = NULL;
244                 dtail->dup = newp;
245                 dtail = newp;
246                 ++nduplist;
247
248                 if (! dep->l_reserved)
249                   {
250                     /* Append DEP to the unique list.  */
251                     newp->done = 0;
252                     newp->unique = NULL;
253                     utail->unique = newp;
254                     utail = newp;
255                     ++nlist;
256                     /* Set the mark bit that says it's already in the list.  */
257                     dep->l_reserved = 1;
258                   }
259
260                 /* Remember this dependency.  */
261                 if (needed != NULL)
262                   needed[nneeded++] = dep;
263               }
264             else if (d->d_tag == DT_AUXILIARY || d->d_tag == DT_FILTER)
265               {
266                 const char *objname;
267                 const char *errstring;
268                 struct list *newp;
269                 /* Object name.  */
270                 const char *name;
271
272                 /* Recognize DSTs.  */
273                 name = expand_dst (l, strtab + d->d_un.d_val,
274                                    d->d_tag == DT_AUXILIARY);
275
276                 if (d->d_tag == DT_AUXILIARY)
277                   {
278                     /* Store the tag in the argument structure.  */
279                     args.name = name;
280
281                     /* Say that we are about to load an auxiliary library.  */
282                     if (__builtin_expect (_dl_debug_libs, 0))
283                       _dl_debug_message (1, "load auxiliary object=",
284                                          name, " requested by file=",
285                                          l->l_name[0]
286                                          ? l->l_name : _dl_argv[0],
287                                          "\n", NULL);
288
289                     /* We must be prepared that the addressed shared
290                        object is not available.  */
291                     if (_dl_catch_error (&objname, &errstring, openaux, &args))
292                       {
293                         /* We are not interested in the error message.  */
294                         assert (errstring != NULL);
295                         if (errstring != _dl_out_of_memory)
296                           free ((char *) errstring);
297
298                         /* Simply ignore this error and continue the work.  */
299                         continue;
300                       }
301                   }
302                 else
303                   {
304                     /* Say that we are about to load an auxiliary library.  */
305                     if (__builtin_expect (_dl_debug_libs, 0))
306                       _dl_debug_message (1, "load filtered object=", name,
307                                          " requested by file=",
308                                          l->l_name[0]
309                                          ? l->l_name : _dl_argv[0],
310                                          "\n", NULL);
311
312                     /* For filter objects the dependency must be available.  */
313                     args.aux = _dl_map_object (l, name, 0,
314                                                (l->l_type == lt_executable
315                                                 ? lt_library : l->l_type),
316                                                trace_mode, 0);
317                   }
318
319                 /* The auxiliary object is actually available.
320                    Incorporate the map in all the lists.  */
321
322                 /* Allocate new entry.  This always has to be done.  */
323                 newp = alloca (sizeof (struct list));
324
325                 /* We want to insert the new map before the current one,
326                    but we have no back links.  So we copy the contents of
327                    the current entry over.  Note that ORIG and NEWP now
328                    have switched their meanings.  */
329                 orig->dup = memcpy (newp, orig, sizeof (*newp));
330
331                 /* Initialize new entry.  */
332                 orig->done = 0;
333                 orig->map = args.aux;
334
335                 /* Remember this dependency.  */
336                 if (needed != NULL)
337                   needed[nneeded++] = args.aux;
338
339                 /* We must handle two situations here: the map is new,
340                    so we must add it in all three lists.  If the map
341                    is already known, we have two further possibilities:
342                    - if the object is before the current map in the
343                    search list, we do nothing.  It is already found
344                    early
345                    - if the object is after the current one, we must
346                    move it just before the current map to make sure
347                    the symbols are found early enough
348                 */
349                 if (args.aux->l_reserved)
350                   {
351                     /* The object is already somewhere in the list.
352                        Locate it first.  */
353                     struct list *late;
354
355                     /* This object is already in the search list we
356                        are building.  Don't add a duplicate pointer.
357                        Just added by _dl_map_object.  */
358                     for (late = newp; late->unique; late = late->unique)
359                       if (late->unique->map == args.aux)
360                         break;
361
362                     if (late->unique)
363                       {
364                         /* The object is somewhere behind the current
365                            position in the search path.  We have to
366                            move it to this earlier position.  */
367                         orig->unique = newp;
368
369                         /* Now remove the later entry from the unique list
370                            and adjust the tail pointer.  */
371                         if (utail == late->unique)
372                           utail = late;
373                         late->unique = late->unique->unique;
374
375                         /* We must move the object earlier in the chain.  */
376                         if (args.aux->l_prev)
377                           args.aux->l_prev->l_next = args.aux->l_next;
378                         if (args.aux->l_next)
379                           args.aux->l_next->l_prev = args.aux->l_prev;
380
381                         args.aux->l_prev = newp->map->l_prev;
382                         newp->map->l_prev = args.aux;
383                         if (args.aux->l_prev != NULL)
384                           args.aux->l_prev->l_next = args.aux;
385                         args.aux->l_next = newp->map;
386                       }
387                     else
388                       {
389                         /* The object must be somewhere earlier in the
390                            list.  That's good, we only have to insert
391                            an entry for the duplicate list.  */
392                         orig->unique = NULL;    /* Never used.  */
393
394                         /* Now we have a problem.  The element
395                            pointing to ORIG in the unique list must
396                            point to NEWP now.  This is the only place
397                            where we need this backreference and this
398                            situation is really not that frequent.  So
399                            we don't use a double-linked list but
400                            instead search for the preceding element.  */
401                         late = known;
402                         while (late->unique != orig)
403                           late = late->unique;
404                         late->unique = newp;
405                       }
406                   }
407                 else
408                   {
409                     /* This is easy.  We just add the symbol right here.  */
410                     orig->unique = newp;
411                     ++nlist;
412                     /* Set the mark bit that says it's already in the list.  */
413                     args.aux->l_reserved = 1;
414
415                     /* The only problem is that in the double linked
416                        list of all objects we don't have this new
417                        object at the correct place.  Correct this here.  */
418                     if (args.aux->l_prev)
419                       args.aux->l_prev->l_next = args.aux->l_next;
420                     if (args.aux->l_next)
421                       args.aux->l_next->l_prev = args.aux->l_prev;
422
423                     args.aux->l_prev = newp->map->l_prev;
424                     newp->map->l_prev = args.aux;
425                     if (args.aux->l_prev != NULL)
426                       args.aux->l_prev->l_next = args.aux;
427                     args.aux->l_next = newp->map;
428                   }
429
430                 /* Move the tail pointers if necessary.  */
431                 if (orig == utail)
432                   utail = newp;
433                 if (orig == dtail)
434                   dtail = newp;
435
436                 /* Move on the insert point.  */
437                 orig = newp;
438
439                 /* We always add an entry to the duplicate list.  */
440                 ++nduplist;
441               }
442         }
443
444       /* Terminate the list of dependencies and store the array address.  */
445       if (needed != NULL)
446         {
447           needed[nneeded++] = NULL;
448
449           l->l_initfini = malloc (nneeded * sizeof needed[0]);
450           if (l->l_initfini == NULL)
451             _dl_signal_error (ENOMEM, map->l_name,
452                               N_("cannot allocate dependency list"));
453           memcpy (l->l_initfini, needed, nneeded * sizeof needed[0]);
454         }
455
456       /* If we have no auxiliary objects just go on to the next map.  */
457       if (runp->done)
458         do
459           runp = runp->unique;
460         while (runp != NULL && runp->done);
461     }
462
463   if (map->l_initfini != NULL && map->l_type == lt_loaded)
464     {
465       /* This object was previously loaded as a dependency and we have
466          a separate l_initfini list.  We don't need it anymore.  */
467       assert (map->l_searchlist.r_list == NULL);
468       free (map->l_initfini);
469     }
470
471   /* Store the search list we built in the object.  It will be used for
472      searches in the scope of this object.  */
473   map->l_initfini =
474     (struct link_map **) malloc ((2 * nlist + 1
475                                   + (nlist == nduplist ? 0 : nduplist))
476                                  * sizeof (struct link_map *));
477   if (map->l_initfini == NULL)
478     _dl_signal_error (ENOMEM, map->l_name,
479                       N_("cannot allocate symbol search list"));
480
481
482   map->l_searchlist.r_list = &map->l_initfini[nlist + 1];
483   map->l_searchlist.r_nlist = nlist;
484
485   for (nlist = 0, runp = known; runp; runp = runp->unique)
486     {
487       if (trace_mode && 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   map->l_searchlist.r_nduplist = nduplist;
499   if (nlist == nduplist)
500     map->l_searchlist.r_duplist = map->l_searchlist.r_list;
501   else
502     {
503       unsigned int cnt;
504
505       map->l_searchlist.r_duplist = map->l_searchlist.r_list + nlist;
506
507       for (cnt = 0, runp = known; runp; runp = runp->dup)
508         if (trace_mode && runp->map->l_faked)
509           /* This can happen when we trace the loading.  */
510           --map->l_searchlist.r_nduplist;
511         else
512           map->l_searchlist.r_duplist[cnt++] = runp->map;
513     }
514
515   /* Now determine the order in which the initialization has to happen.  */
516   memcpy (map->l_initfini, map->l_searchlist.r_list,
517           nlist * sizeof (struct link_map *));
518   /* We can skip looking for the binary itself which is at the front
519      of the search list.  Look through the list backward so that circular
520      dependencies are not changing the order.  */
521   for (i = 1; i < nlist; ++i)
522     {
523       struct link_map *l = map->l_searchlist.r_list[i];
524       unsigned int j;
525       unsigned int k;
526
527       /* Find the place in the initfini list where the map is currently
528          located.  */
529       for (j = 1; map->l_initfini[j] != l; ++j)
530         ;
531
532       /* Find all object for which the current one is a dependency and
533          move the found object (if necessary) in front.  */
534       for (k = j + 1; k < nlist; ++k)
535         {
536           struct link_map **runp;
537
538           runp = map->l_initfini[k]->l_initfini;
539           if (runp != NULL)
540             {
541               while (*runp != NULL)
542                 if (*runp == l)
543                   {
544                     struct link_map *here = map->l_initfini[k];
545
546                     /* Move it now.  */
547                     memmove (&map->l_initfini[j] + 1,
548                              &map->l_initfini[j],
549                              (k - j) * sizeof (struct link_map *));
550                     map->l_initfini[j] = here;
551
552                     break;
553                   }
554                 else
555                   ++runp;
556             }
557         }
558     }
559   /* Terminate the list of dependencies.  */
560   map->l_initfini[nlist] = NULL;
561 }