diff options
Diffstat (limited to 'elf')
| -rw-r--r-- | elf/dl-deps.c | 371 |
1 files changed, 266 insertions, 105 deletions
diff --git a/elf/dl-deps.c b/elf/dl-deps.c index e2fd340822..36f5ee0606 100644 --- a/elf/dl-deps.c +++ b/elf/dl-deps.c @@ -22,17 +22,27 @@ #include <dlfcn.h> #include <stdlib.h> +#include <assert.h> + +/* Whether an shared object references one or more auxiliary objects + is signaled by the AUXTAG entry in l_info. */ +#define AUXTAG (DT_NUM + DT_PROCNUM + DT_VERSIONTAGNUM \ + + DT_EXTRATAGIDX (DT_AUXILIARY)) + + +/* When loading auxiliary objects we must ignore errors. It's ok if + an object is missing. */ struct openaux_args -{ - /* The arguments to openaux. */ - struct link_map *map; - int trace_mode; - const char *strtab; - ElfW(Dyn) *d; + { + /* The arguments to openaux. */ + struct link_map *map; + int trace_mode; + const char *strtab; + const ElfW(Dyn) *d; - /* The return value of openaux. */ - struct link_map *aux; -}; + /* The return value of openaux. */ + struct link_map *aux; + }; static void openaux (void *a) @@ -45,78 +55,56 @@ openaux (void *a) args->trace_mode); } + + +/* We use a very special kind of list to track the three kinds paths + through the list of loaded shared objects. We have to + + - go through all objects in the correct order, which includes the + possible recursive loading of auxiliary objects and dependencies + + - produce a flat list with unique members of all involved objects + + - produce a flat list of all shared objects. +*/ +struct list + { + int done; /* Nonzero if this map was processed. */ + struct link_map *map; /* The data. */ + + struct list *unique; /* Elements for normal list. */ + struct list *dup; /* Elements in complete list. */ + }; + + void _dl_map_object_deps (struct link_map *map, struct link_map **preloads, unsigned int npreloads, int trace_mode) { - struct list - { - struct link_map *map; - struct list *next; - }; - struct list *head, *tailp, *scanp; - struct list duphead, *duptailp; - unsigned int nduplist; - unsigned int nlist, naux, i; + struct list known[1 + npreloads + 1]; + struct list *runp, *head, *utail, *dtail; + unsigned int nlist, nduplist, i; + inline void preload (struct link_map *map) { - head[nlist].next = &head[nlist + 1]; - head[nlist++].map = map; + known[nlist].done = 0; + known[nlist].map = map; + + known[nlist].unique = &known[nlist + 1]; + known[nlist].dup = &known[nlist + 1]; + ++nlist; /* We use `l_reserved' as a mark bit to detect objects we have already put in the search list and avoid adding duplicate elements later in the list. */ map->l_reserved = 1; } - naux = nlist = 0; - - /* XXX The AUXILIARY implementation isn't correct in the moment. XXX - XXX The problem is that we currently do not handle auxiliary XXX - XXX entries in the loaded objects. XXX */ - -#define AUXTAG (DT_NUM + DT_PROCNUM + DT_VERSIONTAGNUM \ - + DT_EXTRATAGIDX (DT_AUXILIARY)) - - /* First determine the number of auxiliary objects we have to load. */ - if (map->l_info[AUXTAG]) - { - ElfW(Dyn) *d; - for (d = map->l_ld; d->d_tag != DT_NULL; ++d) - if (d->d_tag == DT_AUXILIARY) - ++naux; - } - - /* Now we can allocate the array for the linker maps. */ - head = (struct list *) alloca (sizeof (struct list) - * (naux + npreloads + 2)); - - /* Load the auxiliary objects, even before the object itself. */ - if (map->l_info[AUXTAG]) - { - /* There is at least one auxiliary library specified. We try to - load it, and if we can, use its symbols in preference to our - own. But if we can't load it, we just silently ignore it. */ - struct openaux_args args; - args.strtab - = ((void *) map->l_addr + map->l_info[DT_STRTAB]->d_un.d_ptr); - args.map = map; - args.trace_mode = trace_mode; - - for (args.d = map->l_ld; args.d->d_tag != DT_NULL; ++args.d) - if (args.d->d_tag == DT_AUXILIARY) - { - char *errstring; - const char *objname; - if (! _dl_catch_error (&errstring, &objname, openaux, &args)) - /* The auxiliary object is actually there. Use it as - the first search element, even before MAP itself. */ - preload (args.aux); - } - } + /* No loaded object so far. */ + nlist = 0; - /* Next load MAP itself. */ + /* First load MAP itself. */ preload (map); /* Add the preloaded items after MAP but before any of its dependencies. */ @@ -124,30 +112,51 @@ _dl_map_object_deps (struct link_map *map, preload (preloads[i]); /* Terminate the lists. */ - head[nlist - 1].next = NULL; - duphead.next = NULL; + known[nlist - 1].unique = NULL; + known[nlist - 1].dup = NULL; + + /* Pointer to the first member of the unique and duplicate list. */ + head = known; - /* Start here for adding dependencies to the list. */ - tailp = &head[nlist - 1]; + /* Pointer to last unique object. */ + utail = &known[nlist - 1]; + /* Pointer to last loaded object. */ + dtail = &known[nlist - 1]; /* Until now we have the same number of libraries in the normal and the list with duplicates. */ nduplist = nlist; - duptailp = &duphead; - /* Process each element of the search list, loading each of its immediate - dependencies and appending them to the list as we step through it. - This produces a flat, ordered list that represents a breadth-first - search of the dependency tree. */ - for (scanp = head; scanp; scanp = scanp->next) + /* Process each element of the search list, loading each of its + auxiliary objects and immediate dependencies. Auxiliary objects + will be added in the list before the object itself and + dependencies will be appended to the list as we step through it. + This produces a flat, ordered list that represents a + breadth-first search of the dependency tree. + + The whole process is complicated by the fact that we better + should use alloca for the temporary list elements. But using + alloca means we cannot use recursive function calls. */ + for (runp = known; runp; ) { - struct link_map *l = scanp->map; + struct link_map *l = runp->map; - if (l->l_info[DT_NEEDED]) + if (runp->done == 0 && (l->l_info[AUXTAG] || l->l_info[DT_NEEDED])) { - const char *strtab - = ((void *) l->l_addr + l->l_info[DT_STRTAB]->d_un.d_ptr); + const char *strtab = ((void *) l->l_addr + + l->l_info[DT_STRTAB]->d_un.d_ptr); + struct openaux_args args; + struct list *orig; const ElfW(Dyn) *d; + + /* Mark map as processed. */ + runp->done = 1; + + args.strtab = strtab; + args.map = l; + args.trace_mode = trace_mode; + orig = runp; + for (d = l->l_ld; d->d_tag != DT_NULL; ++d) if (d->d_tag == DT_NEEDED) { @@ -156,32 +165,182 @@ _dl_map_object_deps (struct link_map *map, = _dl_map_object (l, strtab + d->d_un.d_val, l->l_type == lt_executable ? lt_library : l->l_type, trace_mode); + /* Allocate new entry. */ + struct list *newp = alloca (sizeof (struct list)); + + /* Add it in any case to the duplicate list. */ + newp->map = dep; + newp->dup = NULL; + dtail->dup = newp; + dtail = newp; + ++nduplist; if (dep->l_reserved) /* This object is already in the search list we are - building. Don't add a duplicate pointer. Release the - reference just added by _dl_map_object. */ + building. Don't add a duplicate pointer. + Release the reference just added by + _dl_map_object. */ --dep->l_opencount; else { - /* Append DEP to the search list. */ - tailp->next = alloca (sizeof *tailp); - tailp = tailp->next; - tailp->map = dep; - tailp->next = NULL; + /* Append DEP to the unique list. */ + newp->done = 0; + newp->unique = NULL; + utail->unique = newp; + utail = newp; ++nlist; /* Set the mark bit that says it's already in the list. */ dep->l_reserved = 1; } + } + else if (d->d_tag == DT_AUXILIARY) + { + char *errstring; + const char *objname; - /* In any case append DEP to the duplicates search list. */ - duptailp->next = alloca (sizeof *duptailp); - duptailp = duptailp->next; - duptailp->map = dep; - duptailp->next = NULL; - ++nduplist; + /* Store the tag in the argument structure. */ + args.d = d; + + if (_dl_catch_error (&errstring, &objname, openaux, &args)) + { + /* We are not interested in the error message. */ + assert (errstring != NULL); + free (errstring); + } + else + { + /* The auxiliary object is actually available. + Incorporate the map in all the lists. */ + + /* Allocate new entry. This always has to be done. */ + struct list *newp = alloca (sizeof (struct list)); + + /* Copy the content of the current entry over. */ + memcpy (newp, orig, sizeof (*newp)); + + /* Initialize new entry. */ + orig->done = 0; + orig->map = args.aux; + orig->dup = newp; + + /* We must handle two situations here: the map is new, + so we must add it in all three lists. If the map + is already known, we have two further possibilities: + - if the object is before the current map in the + search list, we do nothing. It is already found + early + - if the object is after the current one, we must + move it just before the current map to make sure + the symbols are found early enough + */ + if (args.aux->l_reserved) + { + /* The object is already somewhere in the + list. Locate it first. */ + struct list *late; + + /* This object is already in the search list + we are building. Don't add a duplicate + pointer. Release the reference just added + by _dl_map_object. */ + --args.aux->l_opencount; + + for (late = orig; late->unique; late = late->unique) + if (late->unique->map == args.aux) + break; + + if (late->unique) + { + /* The object is somewhere behind the current + position in the search path. We have to + move it to this earlier position. */ + orig->unique = newp; + + /* Now remove the later entry from the unique + list. */ + late->unique = late->unique->unique; + + /* We must move the earlier in the chain. */ + if (args.aux->l_prev) + args.aux->l_prev->l_next = args.aux->l_next; + if (args.aux->l_next) + args.aux->l_next->l_prev = args.aux->l_prev; + + args.aux->l_prev = newp->map->l_prev; + newp->map->l_prev = args.aux; + if (args.aux->l_prev != NULL) + args.aux->l_prev->l_next = args.aux; + args.aux->l_next = newp->map; + } + else + { + /* The object must be somewhere earlier in + the list. That's good, we only have to + insert an entry for the duplicate list. */ + orig->unique = NULL; /* Never used. */ + + /* Now we have a problem. The element pointing + to ORIG in the unique list must point to + NEWP now. This is the only place where we + need this backreference and this situation + is really not that frequent. So we don't + use a double-linked list but instead search + for the preceding element. */ + late = head; + while (late->unique != orig) + late = late->unique; + late->unique = newp; + } + } + else + { + /* This is easy. We just add the symbol right + here. */ + orig->unique = newp; + ++nlist; + /* Set the mark bit that says it's already in + the list. */ + args.aux->l_reserved = 1; + + /* The only problem is that in the double linked + list of all objects we don't have this new + object at the correct place. Correct this + here. */ + if (args.aux->l_prev) + args.aux->l_prev->l_next = args.aux->l_next; + if (args.aux->l_next) + args.aux->l_next->l_prev = args.aux->l_prev; + + args.aux->l_prev = newp->map->l_prev; + newp->map->l_prev = args.aux; + if (args.aux->l_prev != NULL) + args.aux->l_prev->l_next = args.aux; + args.aux->l_next = newp->map; + } + + /* Move the tail pointers if necessary. */ + if (orig == utail) + utail = newp; + if (orig == dtail) + dtail = newp; + + /* Move on the insert point. */ + orig = newp; + + /* We always add an entry to the duplicate list. */ + ++nduplist; + } } } + else + /* Mark as processed. */ + runp->done = 1; + + /* If we have no auxiliary objects just go on to the next map. */ + if (runp->done) + do + runp = runp->unique; + while (runp && runp->done); } /* Store the search list we built in the object. It will be used for @@ -192,24 +351,26 @@ _dl_map_object_deps (struct link_map *map, "cannot allocate symbol search list"); map->l_nsearchlist = nlist; - nlist = 0; - for (scanp = head; scanp; scanp = scanp->next) + for (nlist = 0, runp = head; runp; runp = runp->unique) { - map->l_searchlist[nlist++] = scanp->map; + map->l_searchlist[nlist++] = runp->map; /* Now clear all the mark bits we set in the objects on the search list to avoid duplicates, so the next call starts fresh. */ - scanp->map->l_reserved = 0; + runp->map->l_reserved = 0; } - map->l_dupsearchlist = malloc (nduplist * sizeof (struct link_map *)); - if (map->l_dupsearchlist == NULL) - _dl_signal_error (ENOMEM, map->l_name, - "cannot allocate symbol search list"); map->l_ndupsearchlist = nduplist; + if (nlist == nduplist) + map->l_dupsearchlist = map->l_searchlist; + else + { + map->l_dupsearchlist = malloc (nduplist * sizeof (struct link_map *)); + if (map->l_dupsearchlist == NULL) + _dl_signal_error (ENOMEM, map->l_name, + "cannot allocate symbol search list"); - for (nlist = 0; nlist < naux + 1 + npreloads; ++nlist) - map->l_dupsearchlist[nlist] = head[nlist].map; - for (scanp = duphead.next; scanp; scanp = scanp->next) - map->l_dupsearchlist[nlist++] = scanp->map; + for (nlist = 0, runp = head; runp; runp = runp->dup) + map->l_searchlist[nlist++] = runp->map; + } } |