/*
* CDDL HEADER START
*
* The contents of this file are subject to the terms of the
* Common Development and Distribution License (the "License").
* You may not use this file except in compliance with the License.
*
* You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
* See the License for the specific language governing permissions
* and limitations under the License.
*
* When distributing Covered Code, include this CDDL HEADER in each
* file and include the License file at usr/src/OPENSOLARIS.LICENSE.
* If applicable, add the following below this CDDL HEADER, with the
* fields enclosed by brackets "[]" replaced with your own identifying
* information: Portions Copyright [yyyy] [name of copyright owner]
*
* CDDL HEADER END
*/
/*
*/
/*
* Utilities to handle shared object dependency graph.
*
* The algorithms used in this file are taken from the following book:
* Algorithms in C
* Robert Sedgewick
* Addison-Wesley Publishing company
* ISBN 0-201-51425-7
* From the following chapters:
* Chapter 29 Elementary Graph Algorithms
* Chapter 32 Directed Graph
*/
#include <stdarg.h>
#include <stdio.h>
#include <dlfcn.h>
#include <signal.h>
#include <locale.h>
#include <string.h>
#include <libintl.h>
#include <debug.h>
#include "_rtld.h"
#include "msg.h"
/*
* Structure for maintaining sorting state.
*/
typedef struct {
} Sort;
/*
* qsort(3c) comparison function.
*/
static int
{
return (-1);
return (1);
return (0);
}
/*
* This routine is called when a cyclic dependency is detected between strongly
* connected components. The nodes within the cycle are reverse breadth-first
* sorted.
*/
static int
{
int ndx;
/*
* If this is the first cyclic dependency traverse the new objects that
* have been added to the link-map list and for each object establish
* a unique depth index. We build this dynamically as we have no idea
* of the number of objects that will be inspected (logic matches that
* used by dlsym() to traverse lazy dependencies).
*/
ndx = 1;
return (0);
continue;
/*
* If we're .init processing and this depend-
* encies .init has been called, skip it.
*/
if ((flag & RT_SORT_REV) &&
continue;
return (0);
}
}
}
/*
* Sort the cyclics.
*/
compare);
/*
* Under ldd -i, or debugging, print this cycle. Under ldd -i/-U assign
* each object a group identifier so that cyclic dependent callers can
* be better traced (see trace_sort()), or analyzed for non-use.
*/
return (1);
if (init) {
if (tfmt == 0) {
}
}
/*
* Identify this cyclic group, and under ldd -i print the cycle in the
* order its components will be run.
*/
if (flag & RT_SORT_REV) {
if (init)
}
cnt++;
} else if (DBG_ENABLED) {
}
}
/*
* If we're looking for unused dependencies determine if any of these
* cyclic components are referenced from outside of the cycle.
*/
if (unref || DBG_ENABLED) {
/*
* If this object has a handle then it can be in use by
* anyone.
*/
return (1);
/*
* Traverse this objects callers looking for outside
* references.
*/
continue;
return (1);
}
}
/*
* If we're here then none of the cyclic dependents have been
* referenced from outside of the cycle, mark them as unused.
*/
}
}
return (1);
}
/*
* Take elements off of the stack and move them to the link-map array. Typically
* this routine just pops one strongly connected component (individual link-map)
* at a time. When a cyclic dependency has been detected the stack will contain
* more than just the present object to process, and will trigger the later call
* to sort_scc() to sort these elements.
*/
static int
{
do {
if (flag & RT_SORT_REV) {
/*
* Indicate the object has had its .init collected.
* Note, that regardless of the object having a .init
* the object is added to the tsort list, as it's from
* this list that any post-init flags are established.
*/
} else {
/*
* Indicate the object has had its .fini collected.
* Note, that regardless of the object having a .fini,
* the object is added to the tsort list, as it's from
* this list that any audit_objclose() activity is
* triggered.
*/
}
/*
* If tracing, save the strongly connected component.
*/
AL_CNT_SCC) == NULL))
return (0);
/*
* Determine if there are cyclic dependencies to process. If so, sort
* the components, and retain them for tracing output.
*/
return (0);
AL_CNT_SCC) == NULL))
return (0);
} else if (alp)
return (1);
}
static int
static int
{
int _min;
/*
* Only collect objects that belong to the callers link-map. Catches
* cross dependencies (filtering) to ld.so.1.
*/
return (min);
/*
* Determine if this object hasn't been inspected.
*/
if (flag & RT_SORT_REV) {
/*
* For .init processing, only collect objects that have
* been relocated and haven't already been collected.
*/
return (min);
/*
* If this object contains no .init, there's no need to
* establish a dependency.
*/
return (min);
} else {
/*
* For .fini processing only collect objects that have
* had their .init collected, and haven't already been
* .fini collected.
*/
return (min);
/*
* If we're deleting a subset of objects, only collect
* those marked for deletion.
*/
if ((flag & RT_SORT_DELETE) &&
return (min);
/*
* If this object contains no .fini, there's no need to
* establish a dependency.
*/
return (min);
}
/*
* Inspect this new dependency.
*/
return (-1);
}
/*
* Keep track of the smallest SORTVAL that has been encountered. If
* this value is smaller than the present object, then the dependency
* edge has cycled back to objects that have been processed earlier
* along this dependency edge.
*/
return (_min);
} else
return (min);
}
/*
* Visit the dependencies of each object.
*/
static int
int flag)
{
int min;
sort->s_initfirst++;
/*
* Traverse both explicit and implicit dependencies.
*/
return (-1);
}
/*
* Traverse any filtee dependencies.
*/
continue;
continue;
gdp)) {
continue;
return (-1);
}
}
}
}
/*
* Having returned to where the minimum SORTVAL is equivalent to the
* object that has just been processed, collect any dependencies that
* are available on the sorting stack.
*/
return (-1);
}
return (min);
}
/*
* Find corresponding strongly connected component structure.
*/
static APlist *
{
return (alp);
}
}
return (NULL);
}
/*
* Print out the .init dependency information (ldd).
*/
static void
{
int ndx = 0;
continue;
if (sfmt == 0)
/*
* If the only component on the strongly connected list is
* this link-map, then there are no dependencies.
*/
continue;
}
/*
* Establish message formats for cyclic dependencies.
*/
if (cfmt == 0) {
}
continue;
}
}
}
}
/*
* A reverse ordered list (for .init's) contains INITFIRST elements. Move each
* of these elements to the front of the list.
*/
static void
{
continue;
/*
* If the INITFIRST element is already at the front of
* the list leave it there.
*/
break;
}
/*
* Move the elements from the front of the list up to
* the INITFIRST element, back one position.
*/
/*
* Insert INITFIRST element at the front of the list.
*/
break;
}
}
}
/*
* A forward ordered list (for .fini's) contains INITFIRST elements. Move each
* of these elements to the front of the list.
*/
static void
{
continue;
/*
* If the INITFIRST element is already at the end of
* the list leave it there.
*/
break;
/*
* Move the elements from after the INITFIRST element
* up to the back of the list, up one position.
*/
/*
* Insert INITFIRST element at the back of the list.
*/
break;
}
}
}
/*
* Determine whether .init or .fini processing is required.
*/
static int
{
if (flag & RT_SORT_REV) {
/*
* For .init processing, only collect objects that have been
* relocated and haven't already been collected.
*/
return (0);
return (1);
/*
* Only collect objects that have had their .init collected,
* and haven't already been .fini collected.
*/
(FLG_RT_INITCLCT)))
return (0);
return (1);
}
return (0);
}
/*
* Sort the dependency
*/
Rt_map **
{
if (num == 0)
return (0);
/*
* Prior to tsorting any .init sections, insure that the `environ'
* symbol is initialized for this link-map list.
*/
(LML_FLG_TRC_ENABLE | LML_FLG_ENVIRON)) == 0))
/*
* Allocate memory for link-map list array. Calloc the array to insure
* all elements are zero, we might find that no objects need processing.
* At the same time, allocate a stack for any topological sorting that
* might be necessary.
*/
/*
* Determine where to start searching for tsort() candidates. Any call
* to tsort() for .init processing is passed the link-map from which to
* start searching. However, if new objects have dependencies on
* existing objects, or existing objects have been promoted (RTLD_LAZY
* to RTLD_NOW), then start searching at the head of the link-map list.
* These previously loaded objects will have been tagged for inclusion
* in this tsort() pass. They still remain on an existing tsort() list,
* which must have been prempted for control to have arrived here.
* However, they will be ignored when encountered on any previous
* tsort() list if their .init has already been called.
*/
else
/*
* If interposers exist, inspect these objects first.
*
* Interposers can provide implicit dependencies - for example, an
* application that has a dependency on libumem will caused any other
* dependencies of the application that use the malloc family, to
* have an implicit dependency on libumem. However, under the default
* condition of lazy binding, these dependency relationships on libumem
* are unknown to the tsorting process (ie. a call to one of the malloc
* family has not occurred to establish the dependency). This lack of
* dependency information makes the interposer look "standalone",
* whereas the interposers .init/.fini should be analyzed with respect
* to the dependency relationship libumem will eventually create.
*
* By inspecting interposing objects first, we are able to trigger
* their .init sections to be accounted for before any others.
* Selecting these .init sections first is important for the malloc
* libraries, as these libraries need to prepare for pthread_atfork().
* However, handling interposer libraries in this generic fashion
* should help provide for other dependency relationships that may
* exist.
*/
/*
* Unless the executable is tagged as an interposer, skip to
* the next object.
*/
break;
&sort) != 0)
}
/*
* Once all interposers are processed, there is no need to
* look for interposers again. An interposer can only
* be introduced before any relocation takes place, thus
* interposer .init's will be grabbed during the first tsort
* starting at the head of the link-map list.
*
* Interposers can't be unloaded. Thus interposer .fini's can
* only be called during atexit() processing. The interposer
* tsort flag is removed from each link-map list during
* atexit_fini() so that the interposers .fini sections are
* processed appropriately.
*/
}
/*
* Inspect any standard objects.
*/
continue;
}
/*
* The dependencies have been collected such that they are appropriate
* for an .init order, for .fini order reverse them.
*/
if (flag & RT_SORT_FWD) {
}
}
/*
* If INITFIRST objects have been collected then move them to the front
* or end of the list as appropriate.
*/
if (sort.s_initfirst) {
if (flag & RT_SORT_REV)
else
}
/*
* If tracing .init sections (only meaningful for RT_SORT_REV), print
* out the sorted dependencies.
*/
if (init)
trace_sort(&sort);
/*
* Clean any temporary structures prior to return.
*/
/*
* Traverse the link-maps collected on the sort queue and
* delete the depth index. These link-maps may be traversed
* again to sort other components either for inits, and almost
* certainly for .finis.
*/
}
}
/*
* The caller is responsible for freeing the sorted link-map list once
* the associated .init/.fini's have been fired.
*/
}