tsort.c revision 7c478bd95313f5f23a4c958a745db2134aa03244
/*
* CDDL HEADER START
*
* The contents of this file are subject to the terms of the
* Common Development and Distribution License, Version 1.0 only
* (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
*/
/*
* Copyright 2005 Sun Microsystems, Inc. All rights reserved.
* Use is subject to license terms.
*/
#pragma ident "%Z%%M% %I% %E% SMI"
/*
* 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 "_synonyms.h"
#include <stdarg.h>
#include <stdio.h>
#include <dlfcn.h>
#include <signal.h>
#include <locale.h>
#include <string.h>
#include <libintl.h>
#include "_rtld.h"
#include "msg.h"
#include "debug.h"
/*
* Structure for maintaining sorting state.
*/
typedef struct {
int s_sndx; /* present stack index */
int s_lndx; /* present link-map index */
int s_num; /* number of objects to sort */
int s_initfirst; /* no. of INITFIRST entries */
} 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
{
static int cnt = 1;
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 identified 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_mask) {
}
}
/*
* If we're looking for unused dependencies determine if any of these
* cyclic components are referenced from outside of the cycle.
*/
/*
* 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
{
int num;
if (tracing) {
return (0);
return (0);
}
do {
/*
* If tracing, save the strongly connected component.
*/
if (tracing) {
return (0);
}
/*
* Determine if there are cyclic dependencies to process.
*/
return (0);
}
return (1);
}
/*
* Visit the dependencies of each object.
*/
static uint_t
{
sort->s_initfirst++;
/*
* Traverse both explicit and implicit dependencies.
*/
/*
* Only collect objects that belong to the callers link-map.
*/
continue;
if (flag & RT_SORT_REV) {
/*
* For .init processing, only collect objects that have
* been relocated and haven't already been collected.
*/
continue;
} else {
/*
* For .fini processing only collect objects that have
* had their .init collected, and haven't already been
* .fini collected.
*/
continue;
/*
* If we're deleting a subset of objects only collect
* those marked for deletion.
*/
if ((flag & RT_SORT_DELETE) &&
continue;
}
return (0);
}
}
if (flag & RT_SORT_REV) {
} else
return (0);
}
return (min);
}
#ifndef LD_BREADTH_DISABLED
/*
* Reverse LD_BREATH search (used to fire .init's the old fashioned way).
*/
static void
{
/*
* Only collect objects that have been relocated and haven't already
* been collected.
*/
}
}
/*
* Forward LD_BREATH search (used to fire .fini's the old fashioned way).
*/
static void
{
while (lmp) {
/*
* If we're called from dlclose() then we only collect those
* objects marked for deletion.
*/
/*
* Only collect objects that have had their .init
* collected, and haven't already been .fini collected.
*/
(FLG_RT_INITCLCT | FLG_RT_FINICLCT)) ==
(FLG_RT_INITCLCT)) {
}
}
}
}
#endif
/*
* Find corresponding strongly connected component structure.
*/
static List *
{
return (scc);
}
}
return (NULL);
}
/*
* Print out the .init dependency information (ldd).
*/
static void
{
int ndx = 0;
continue;
if (sfmt == 0)
#ifndef LD_BREADTH_DISABLED
if (rtld_flags & RT_FL_BREADTH) {
continue;
}
#endif
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;
}
}
}
/*
* 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.
*/
#ifndef LD_BREADTH_DISABLED
/*
* A breadth first search is easy, simply add each object to the
* link-map array.
*/
if (rtld_flags & RT_FL_BREADTH) {
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);
}
#endif
/*
* We need to topologically sort the dependencies.
*/
/*
* 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, previously loaded, uninitialized objects
* may be dependencies of newly loaded objects, and in this case start
* at the head of the link-map list, not the new link-map itself.
* 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 (flag & RT_SORT_REV) {
/*
* For .init processing, only collect objects that have
* been relocated and haven't already been collected.
*/
continue;
} else if (!(flag & RT_SORT_DELETE) ||
/*
* Only collect objects that have had their .init
* collected, and haven't already been .fini collected.
*/
(FLG_RT_INITCLCT | FLG_RT_FINICLCT)) ==
(FLG_RT_INITCLCT)))
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. The caller is
* responsible for freeing the lmpa.
*/
/*
* Traverse the link-maps collected on the sort queue and delete the
* depth index. They may be traversed again to sort other components
* either for .inits and almost certainly for .finis.
*/
if (_lnp)
}
if (_lnp)
}
while (lnp1) {
while (lnp2) {
}
}
}