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