3fbb3dbf92833cbd1299d4529341ce289090e12e
[kopensolaris-gnu/glibc.git] / elf / dl-deps.c
1 /* Load the dependencies of a mapped object.
2    Copyright (C) 1996, 1997 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 <link.h>
21 #include <errno.h>
22 #include <dlfcn.h>
23 #include <stdlib.h>
24 #include <string.h>
25 #include <assert.h>
26
27 /* Whether an shared object references one or more auxiliary objects
28    is signaled by the AUXTAG entry in l_info.  */
29 #define AUXTAG  (DT_NUM + DT_PROCNUM + DT_VERSIONTAGNUM \
30                  + DT_EXTRATAGIDX (DT_AUXILIARY))
31
32
33 /* When loading auxiliary objects we must ignore errors.  It's ok if
34    an object is missing.  */
35 struct openaux_args
36   {
37     /* The arguments to openaux.  */
38     struct link_map *map;
39     int trace_mode;
40     const char *strtab;
41     const ElfW(Dyn) *d;
42
43     /* The return value of openaux.  */
44     struct link_map *aux;
45   };
46
47 static void
48 openaux (void *a)
49 {
50   struct openaux_args *args = (struct openaux_args *) a;
51
52   args->aux = _dl_map_object (args->map, args->strtab + args->d->d_un.d_val,
53                               (args->map->l_type == lt_executable
54                                ? lt_library : args->map->l_type),
55                               args->trace_mode);
56 }
57
58
59
60 /* We use a very special kind of list to track the two kinds paths
61    through the list of loaded shared objects.  We have to
62
63    - produce a flat list with unique members of all involved objects
64
65    - produce a flat list of all shared objects.
66 */
67 struct list
68   {
69     int done;                   /* Nonzero if this map was processed.  */
70     struct link_map *map;       /* The data.  */
71
72     struct list *unique;        /* Elements for normal list.  */
73     struct list *dup;           /* Elements in complete list.  */
74   };
75
76
77 void
78 _dl_map_object_deps (struct link_map *map,
79                      struct link_map **preloads, unsigned int npreloads,
80                      int trace_mode)
81 {
82   struct list known[1 + npreloads + 1];
83   struct list *runp, *head, *utail, *dtail;
84   unsigned int nlist, nduplist, i;
85
86   inline void preload (struct link_map *map)
87     {
88       known[nlist].done = 0;
89       known[nlist].map = map;
90
91       known[nlist].unique = &known[nlist + 1];
92       known[nlist].dup = &known[nlist + 1];
93
94       ++nlist;
95       /* We use `l_reserved' as a mark bit to detect objects we have
96          already put in the search list and avoid adding duplicate
97          elements later in the list.  */
98       map->l_reserved = 1;
99     }
100
101   /* No loaded object so far.  */
102   nlist = 0;
103
104   /* First load MAP itself.  */
105   preload (map);
106
107   /* Add the preloaded items after MAP but before any of its dependencies.  */
108   for (i = 0; i < npreloads; ++i)
109     preload (preloads[i]);
110
111   /* Terminate the lists.  */
112   known[nlist - 1].unique = NULL;
113   known[nlist - 1].dup = NULL;
114
115   /* Pointer to the first member of the unique and duplicate list.  */
116   head = known;
117
118   /* Pointer to last unique object.  */
119   utail = &known[nlist - 1];
120   /* Pointer to last loaded object.  */
121   dtail = &known[nlist - 1];
122
123   /* Until now we have the same number of libraries in the normal and
124      the list with duplicates.  */
125   nduplist = nlist;
126
127   /* Process each element of the search list, loading each of its
128      auxiliary objects and immediate dependencies.  Auxiliary objects
129      will be added in the list before the object itself and
130      dependencies will be appended to the list as we step through it.
131      This produces a flat, ordered list that represents a
132      breadth-first search of the dependency tree.
133
134      The whole process is complicated by the fact that we better
135      should use alloca for the temporary list elements.  But using
136      alloca means we cannot use recursive function calls.  */
137   for (runp = known; runp; )
138     {
139       struct link_map *l = runp->map;
140
141       if (l->l_info[AUXTAG] || l->l_info[DT_NEEDED])
142         {
143           const char *strtab = ((void *) l->l_addr
144                                 + l->l_info[DT_STRTAB]->d_un.d_ptr);
145           struct openaux_args args;
146           struct list *orig;
147           const ElfW(Dyn) *d;
148
149           /* Mark map as processed.  */
150           runp->done = 1;
151
152           args.strtab = strtab;
153           args.map = l;
154           args.trace_mode = trace_mode;
155           orig = runp;
156
157           for (d = l->l_ld; d->d_tag != DT_NULL; ++d)
158             if (d->d_tag == DT_NEEDED)
159               {
160                 /* Map in the needed object.  */
161                 struct link_map *dep
162                   = _dl_map_object (l, strtab + d->d_un.d_val,
163                                     l->l_type == lt_executable ? lt_library :
164                                     l->l_type, trace_mode);
165                 /* Allocate new entry.  */
166                 struct list *newp = alloca (sizeof (struct list));
167
168                 /* Add it in any case to the duplicate list.  */
169                 newp->map = dep;
170                 newp->dup = NULL;
171                 dtail->dup = newp;
172                 dtail = newp;
173                 ++nduplist;
174
175                 if (dep->l_reserved)
176                   /* This object is already in the search list we are
177                      building.  Don't add a duplicate pointer.
178                      Release the reference just added by
179                      _dl_map_object.  */
180                   --dep->l_opencount;
181                 else
182                   {
183                     /* Append DEP to the unique list.  */
184                     newp->done = 0;
185                     newp->unique = NULL;
186                     utail->unique = newp;
187                     utail = newp;
188                     ++nlist;
189                     /* Set the mark bit that says it's already in the list.  */
190                     dep->l_reserved = 1;
191                   }
192               }
193             else if (d->d_tag == DT_AUXILIARY)
194               {
195                 char *errstring;
196                 const char *objname;
197
198                 /* Store the tag in the argument structure.  */
199                 args.d = d;
200
201                 if (_dl_catch_error (&errstring, &objname, openaux, &args))
202                   {
203                     /* We are not interested in the error message.  */
204                     assert (errstring != NULL);
205                     free (errstring);
206                   }
207                 else
208                   {
209                     /* The auxiliary object is actually available.
210                        Incorporate the map in all the lists.  */
211
212                     /* Allocate new entry.  This always has to be done.  */
213                     struct list *newp = alloca (sizeof (struct list));
214
215                     /* Copy the content of the current entry over.  */
216                     memcpy (newp, orig, sizeof (*newp));
217
218                     /* Initialize new entry.  */
219                     orig->done = 0;
220                     orig->map = args.aux;
221                     orig->dup = newp;
222
223                     /* We must handle two situations here: the map is new,
224                        so we must add it in all three lists.  If the map
225                        is already known, we have two further possibilities:
226                        - if the object is before the current map in the
227                          search list, we do nothing.  It is already found
228                          early
229                        - if the object is after the current one, we must
230                          move it just before the current map to make sure
231                          the symbols are found early enough
232                     */
233                     if (args.aux->l_reserved)
234                       {
235                         /* The object is already somewhere in the
236                            list.  Locate it first.  */
237                         struct list *late;
238
239                         /* This object is already in the search list
240                            we are building.  Don't add a duplicate
241                            pointer.  Release the reference just added
242                            by _dl_map_object.  */
243                         --args.aux->l_opencount;
244
245                         for (late = orig; late->unique; late = late->unique)
246                           if (late->unique->map == args.aux)
247                             break;
248
249                         if (late->unique)
250                           {
251                             /* The object is somewhere behind the current
252                                position in the search path.  We have to
253                                move it to this earlier position.  */
254                             orig->unique = newp;
255
256                             /* Now remove the later entry from the unique
257                                list.  */
258                             late->unique = late->unique->unique;
259
260                             /* We must move the earlier in the chain.  */
261                             if (args.aux->l_prev)
262                               args.aux->l_prev->l_next = args.aux->l_next;
263                             if (args.aux->l_next)
264                               args.aux->l_next->l_prev = args.aux->l_prev;
265
266                             args.aux->l_prev = newp->map->l_prev;
267                             newp->map->l_prev = args.aux;
268                             if (args.aux->l_prev != NULL)
269                               args.aux->l_prev->l_next = args.aux;
270                             args.aux->l_next = newp->map;
271                           }
272                         else
273                           {
274                             /* The object must be somewhere earlier in
275                                the list.  That's good, we only have to
276                                insert an entry for the duplicate list.  */
277                             orig->unique = NULL;        /* Never used.  */
278
279                             /* Now we have a problem.  The element pointing
280                                to ORIG in the unique list must point to
281                                NEWP now.  This is the only place where we
282                                need this backreference and this situation
283                                is really not that frequent.  So we don't
284                                use a double-linked list but instead search
285                                for the preceding element.  */
286                             late = head;
287                             while (late->unique != orig)
288                               late = late->unique;
289                             late->unique = newp;
290                           }
291                       }
292                     else
293                       {
294                         /* This is easy.  We just add the symbol right
295                            here.  */
296                         orig->unique = newp;
297                         ++nlist;
298                         /* Set the mark bit that says it's already in
299                            the list.  */
300                         args.aux->l_reserved = 1;
301
302                         /* The only problem is that in the double linked
303                            list of all objects we don't have this new
304                            object at the correct place.  Correct this
305                            here.  */
306                         if (args.aux->l_prev)
307                           args.aux->l_prev->l_next = args.aux->l_next;
308                         if (args.aux->l_next)
309                           args.aux->l_next->l_prev = args.aux->l_prev;
310
311                         args.aux->l_prev = newp->map->l_prev;
312                         newp->map->l_prev = args.aux;
313                         if (args.aux->l_prev != NULL)
314                           args.aux->l_prev->l_next = args.aux;
315                         args.aux->l_next = newp->map;
316                       }
317
318                     /* Move the tail pointers if necessary.  */
319                     if (orig == utail)
320                       utail = newp;
321                     if (orig == dtail)
322                       dtail = newp;
323
324                     /* Move on the insert point.  */
325                     orig = newp;
326
327                     /* We always add an entry to the duplicate list.  */
328                     ++nduplist;
329                   }
330               }
331         }
332       else
333         /* Mark as processed.  */
334         runp->done = 1;
335
336       /* If we have no auxiliary objects just go on to the next map.  */
337       if (runp->done)
338         do
339           runp = runp->unique;
340         while (runp && runp->done);
341     }
342
343   /* Store the search list we built in the object.  It will be used for
344      searches in the scope of this object.  */
345   map->l_searchlist = malloc (nlist * sizeof (struct link_map *));
346   if (map->l_searchlist == NULL)
347     _dl_signal_error (ENOMEM, map->l_name,
348                       "cannot allocate symbol search list");
349   map->l_nsearchlist = nlist;
350
351   for (nlist = 0, runp = head; runp; runp = runp->unique)
352     {
353       map->l_searchlist[nlist++] = runp->map;
354
355       /* Now clear all the mark bits we set in the objects on the search list
356          to avoid duplicates, so the next call starts fresh.  */
357       runp->map->l_reserved = 0;
358     }
359
360   map->l_ndupsearchlist = nduplist;
361   if (nlist == nduplist)
362     map->l_dupsearchlist = map->l_searchlist;
363   else
364     {
365       map->l_dupsearchlist = malloc (nduplist * sizeof (struct link_map *));
366       if (map->l_dupsearchlist == NULL)
367         _dl_signal_error (ENOMEM, map->l_name,
368                           "cannot allocate symbol search list");
369
370       for (nlist = 0, runp = head; runp; runp = runp->dup)
371         map->l_dupsearchlist[nlist++] = runp->map;
372     }
373 }