dmake: do not set MAKEFLAGS=k

[unleashed/tickless.git] / usr / src / cmd / sgs / rtld / common / tsort.c

/*
 * 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
 * or http://www.opensolaris.org/os/licensing.
 * 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 (c) 1996, 2010, Oracle and/or its affiliates. All rights reserved.
 */

/*
 * 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        <sys/types.h>
#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 {
        Rt_map          **s_lmpa;       /* link-map[] (returned to caller) */
        Rt_map          *s_lmp;         /* originating link-map */
        Rt_map          **s_stack;      /* strongly connected component stack */
        APlist          *s_scc;         /* cyclic list */
        APlist          *s_queue;       /* depth queue for cyclic components */
        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;

#define AL_CNT_SCC      10

/*
 * qsort(3c) comparison function.
 */
static int
compare(const void *lmpp1, const void *lmpp2)
{
        Rt_map  *lmp1 = *((Rt_map **)lmpp1);
        Rt_map  *lmp2 = *((Rt_map **)lmpp2);

        if (IDX(lmp1) > IDX(lmp2))
                return (-1);
        if (IDX(lmp1) < IDX(lmp2))
                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
sort_scc(Sort *sort, int fndx, int flag)
{
        static const char       *tfmt = 0, *ffmt;
        static int              cnt = 1;
        int                     ndx;
        Rt_map                  *lmp;
        Lm_list                 *lml = LIST(sort->s_lmp);
        Word                    lmflags = lml->lm_flags;
        Word                    init, unref;

        /*
         * 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).
         */
        if (sort->s_queue == NULL) {
                Aliste  idx1;
                Rt_map  *lmp, *lmp2;

                lmp = sort->s_lmp;
                ndx = 1;

                if (aplist_append(&sort->s_queue, lmp, sort->s_num) == NULL)
                        return (0);

                IDX(lmp) = ndx++;

                for (APLIST_TRAVERSE(sort->s_queue, idx1, lmp2)) {
                        Bnd_desc        *bdp;
                        Aliste          idx2;

                        for (APLIST_TRAVERSE(DEPENDS(lmp2), idx2, bdp)) {
                                Rt_map  *lmp3 = bdp->b_depend;

                                if (IDX(lmp3) || (LIST(lmp3) != lml))
                                        continue;

                                /*
                                 * If we're .init processing and this depend-
                                 * encies .init has been called, skip it.
                                 */
                                if ((flag & RT_SORT_REV) &&
                                    (FLAGS(lmp3) & FLG_RT_INITCALL))
                                        continue;

                                if (aplist_append(&sort->s_queue, lmp3,
                                    sort->s_num) == NULL)
                                        return (0);

                                IDX(lmp3) = ndx++;
                        }
                }
        }

        /*
         * Sort the cyclics.
         */
        qsort(&(sort->s_lmpa[fndx]), sort->s_lndx - fndx, sizeof (Rt_map *),
            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.
         */
        init = lmflags & LML_FLG_TRC_INIT;
        unref = lmflags & LML_FLG_TRC_UNREF;
        if ((init == 0) && (unref == 0) && (DBG_ENABLED == 0))
                return (1);

        if (init) {
                if (tfmt == 0) {
                        tfmt = MSG_INTL(MSG_LDD_INIT_FMT_01);
                        ffmt = MSG_ORIG(MSG_LDD_INIT_FMT_FILE);
                }
                (void) printf(tfmt, cnt);
        }
        DBG_CALL(Dbg_util_scc_title(lml, (flag & RT_SORT_REV)));

        /*
         * Identify this cyclic group, and under ldd -i print the cycle in the
         * order its components will be run.
         */
        if (flag & RT_SORT_REV) {
                for (ndx = fndx; ndx < sort->s_lndx; ndx++) {
                        lmp = sort->s_lmpa[ndx];
                        CYCGROUP(lmp) = cnt;

                        if (init)
                                (void) printf(ffmt, NAME(lmp));
                        DBG_CALL(Dbg_util_scc_entry(lmp, ndx));
                }
                cnt++;

        } else if (DBG_ENABLED) {
                for (ndx = sort->s_lndx - 1; ndx >= fndx; ndx--) {
                        lmp = sort->s_lmpa[ndx];
                        DBG_CALL(Dbg_util_scc_entry(lmp, ndx));
                }
        }

        /*
         * 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) {
                for (ndx = fndx; ndx < sort->s_lndx; ndx++) {
                        Bnd_desc        *bdp;
                        Aliste          idx;

                        lmp = sort->s_lmpa[ndx];

                        /*
                         * If this object has a handle then it can be in use by
                         * anyone.
                         */
                        if (HANDLES(lmp))
                                return (1);

                        /*
                         * Traverse this objects callers looking for outside
                         * references.
                         */
                        for (APLIST_TRAVERSE(CALLERS(lmp), idx, bdp)) {
                                Rt_map          *clmp = bdp->b_caller;

                                if ((bdp->b_flags & BND_REFER) == 0)
                                        continue;

                                if (CYCGROUP(lmp) != CYCGROUP(clmp))
                                        return (1);
                        }
                }

                /*
                 * If we're here then none of the cyclic dependents have been
                 * referenced from outside of the cycle, mark them as unused.
                 */
                for (ndx = fndx; ndx < sort->s_lndx; ndx++) {
                        lmp = sort->s_lmpa[ndx];
                        FLAGS1(lmp) &= ~FL1_RT_USED;
                }
        }
        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
visit(Lm_list *lml, Rt_map *lmp, Sort *sort, int flag)
{
        APlist          *alp = NULL;
        int             num = sort->s_lndx;
        Word            tracing = lml->lm_flags & LML_FLG_TRC_ENABLE;
        Rt_map          *tlmp;

        do {
                tlmp = sort->s_stack[--(sort->s_sndx)];
                SORTVAL(tlmp) = sort->s_num;
                DBG_CALL(Dbg_util_collect(tlmp, sort->s_lndx, flag));
                sort->s_lmpa[(sort->s_lndx)++] = tlmp;

                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.
                         */
                        FLAGS(tlmp) |= FLG_RT_INITCLCT;
                        lml->lm_init--;
                } 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.
                         */
                        FLAGS(tlmp) |= FLG_RT_FINICLCT;
                }

                /*
                 * If tracing, save the strongly connected component.
                 */
                if (tracing && (aplist_append(&alp, tlmp,
                    AL_CNT_SCC) == NULL))
                        return (0);
        } while (tlmp != lmp);

        /*
         * Determine if there are cyclic dependencies to process.  If so, sort
         * the components, and retain them for tracing output.
         */
        if (sort->s_lndx > (num + 1)) {
                if (sort_scc(sort, num, flag) == 0)
                        return (0);

                if (tracing && (aplist_append(&sort->s_scc, alp,
                    AL_CNT_SCC) == NULL))
                        return (0);
        } else free(alp);

        return (1);
}

static int
dep_visit(Lm_list *, Rt_map *, uint_t, Rt_map *, Sort *, int);

static int
_dep_visit(Lm_list *lml, int min, Rt_map *clmp, Rt_map *dlmp, uint_t bflags,
    Sort *sort, int flag)
{
        int     _min;

        /*
         * Only collect objects that belong to the callers link-map.  Catches
         * cross dependencies (filtering) to ld.so.1.
         */
        if (LIST(dlmp) != lml)
                return (min);

        /*
         * Determine if this object hasn't been inspected.
         */
        if ((_min = SORTVAL(dlmp)) == -1) {
                if (flag & RT_SORT_REV) {
                        /*
                         * For .init processing, only collect objects that have
                         * been relocated and haven't already been collected.
                         */
                        if ((FLAGS(dlmp) & (FLG_RT_RELOCED |
                            FLG_RT_INITCLCT)) != FLG_RT_RELOCED)
                                return (min);

                        /*
                         * If this object contains no .init, there's no need to
                         * establish a dependency.
                         */
                        if ((INIT(dlmp) == 0) && (INITARRAY(dlmp) == 0))
                                return (min);
                } else {
                        /*
                         * For .fini processing only collect objects that have
                         * had their .init collected, and haven't already been
                         * .fini collected.
                         */
                        if ((FLAGS(dlmp) & (FLG_RT_INITCLCT |
                            FLG_RT_FINICLCT)) != FLG_RT_INITCLCT)
                                return (min);

                        /*
                         * If we're deleting a subset of objects, only collect
                         * those marked for deletion.
                         */
                        if ((flag & RT_SORT_DELETE) &&
                            ((FLAGS(dlmp) & FLG_RT_DELETE) == 0))
                                return (min);

                        /*
                         * If this object contains no .fini, there's no need to
                         * establish a dependency.
                         */
                        if ((FINI(dlmp) == 0) && (FINIARRAY(dlmp) == 0))
                                return (min);
                }

                /*
                 * Inspect this new dependency.
                 */
                if ((_min = dep_visit(lml, clmp, bflags, dlmp,
                    sort, flag)) == -1)
                        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.
         */
        if (_min < min) {
                DBG_CALL(Dbg_util_edge_out(clmp, sort->s_stack[_min]));
                return (_min);
        } else
                return (min);
}

/*
 * Visit the dependencies of each object.
 */
static int
dep_visit(Lm_list *lml, Rt_map *clmp, uint_t cbflags, Rt_map *lmp, Sort *sort,
    int flag)
{
        int             min;
        Aliste          idx1;
        Bnd_desc        *bdp;
        Dyninfo         *dip;

        min = SORTVAL(lmp) = sort->s_sndx;
        sort->s_stack[(sort->s_sndx)++] = lmp;

        if (FLAGS(lmp) & FLG_RT_INITFRST)
                sort->s_initfirst++;

        DBG_CALL(Dbg_util_edge_in(lml, clmp, cbflags, lmp, min, flag));

        /*
         * Traverse both explicit and implicit dependencies.
         */
        for (APLIST_TRAVERSE(DEPENDS(lmp), idx1, bdp)) {
                if ((min = _dep_visit(lml, min, lmp, bdp->b_depend,
                    bdp->b_flags, sort, flag)) == -1)
                        return (-1);
        }

        /*
         * Traverse any filtee dependencies.
         */
        if (((dip = DYNINFO(lmp)) != NULL) && (FLAGS1(lmp) & MSK_RT_FILTER)) {
                uint_t  cnt, max = DYNINFOCNT(lmp);

                for (cnt = 0; cnt < max; cnt++, dip++) {
                        Alist   *falp;
                        Pdesc   *pdp;

                        if (((falp = (Alist *)dip->di_info) == NULL) ||
                            ((dip->di_flags & MSK_DI_FILTER) == 0))
                                continue;

                        for (ALIST_TRAVERSE(falp, idx1, pdp)) {
                                Aliste          idx2;
                                Grp_hdl         *ghp;
                                Grp_desc        *gdp;

                                if ((pdp->pd_plen == 0) ||
                                    ((ghp = (Grp_hdl *)pdp->pd_info) == NULL))
                                        continue;

                                for (ALIST_TRAVERSE(ghp->gh_depends, idx2,
                                    gdp)) {

                                        if (gdp->gd_depend == lmp)
                                                continue;
                                        if ((min = _dep_visit(lml, min, lmp,
                                            gdp->gd_depend, BND_FILTER,
                                            sort, flag)) == -1)
                                                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.
         */
        if (min == SORTVAL(lmp)) {
                if (visit(lml, lmp, sort, flag) == 0)
                        return (-1);
        }
        return (min);
}

/*
 * Find corresponding strongly connected component structure.
 */
static APlist *
trace_find_scc(Sort *sort, Rt_map *lmp)
{
        APlist          *alp;
        Aliste          idx1;

        for (APLIST_TRAVERSE(sort->s_scc, idx1, alp)) {
                Rt_map  *lmp2;
                Aliste  idx2;

                for (APLIST_TRAVERSE(alp, idx2, lmp2)) {
                        if (lmp == lmp2)
                                return (alp);
                }
        }
        return (NULL);
}

/*
 * Print out the .init dependency information (ldd).
 */
static void
trace_sort(Sort *sort)
{
        int             ndx = 0;
        APlist          *alp;
        Rt_map          *lmp1;

        (void) printf(MSG_ORIG(MSG_STR_NL));

        while ((lmp1 = sort->s_lmpa[ndx++]) != NULL) {
                static const char       *ffmt, *cfmt = 0, *sfmt = 0;
                Bnd_desc                *bdp;
                Aliste                  idx1;

                if ((INIT(lmp1) == 0) || (FLAGS(lmp1) & FLG_RT_INITCALL))
                        continue;

                if (sfmt == 0)
                        sfmt = MSG_INTL(MSG_LDD_INIT_FMT_02);

                /*
                 * If the only component on the strongly connected list is
                 * this link-map, then there are no dependencies.
                 */
                if ((alp = trace_find_scc(sort, lmp1)) == NULL) {
                        (void) printf(sfmt, NAME(lmp1));
                        continue;
                }

                /*
                 * Establish message formats for cyclic dependencies.
                 */
                if (cfmt == 0) {
                        cfmt = MSG_INTL(MSG_LDD_INIT_FMT_03);
                        ffmt = MSG_ORIG(MSG_LDD_INIT_FMT_FILE);
                }

                (void) printf(cfmt, NAME(lmp1), CYCGROUP(lmp1));

                for (APLIST_TRAVERSE(CALLERS(lmp1), idx1, bdp)) {
                        Rt_map  *lmp3, *lmp2 = bdp->b_caller;
                        Aliste  idx2;

                        for (APLIST_TRAVERSE(alp, idx2, lmp3)) {
                                if (lmp2 != lmp3)
                                        continue;

                                (void) printf(ffmt, NAME(lmp3));
                        }
                }
        }
}

/*
 * A reverse ordered list (for .init's) contains INITFIRST elements.  Move each
 * of these elements to the front of the list.
 */
static void
r_initfirst(Sort * sort, int end)
{
        Rt_map *tlmp;
        int     bgn, ifst, lifst = 0;

        for (bgn = 0; bgn < sort->s_initfirst; bgn++) {
                for (ifst = lifst; ifst <= end; ifst++) {
                        tlmp = sort->s_lmpa[ifst];

                        if (!(FLAGS(tlmp) & FLG_RT_INITFRST))
                                continue;

                        /*
                         * If the INITFIRST element is already at the front of
                         * the list leave it there.
                         */
                        if (ifst == bgn) {
                                lifst = ifst + 1;
                                break;
                        }

                        /*
                         * Move the elements from the front of the list up to
                         * the INITFIRST element, back one position.
                         */
                        (void) memmove(&sort->s_lmpa[bgn + 1],
                            &sort->s_lmpa[bgn],
                            ((ifst - bgn) * sizeof (Rt_map *)));

                        /*
                         * Insert INITFIRST element at the front of the list.
                         */
                        sort->s_lmpa[bgn] = tlmp;
                        lifst = ifst + 1;
                        break;
                }
        }
}

/*
 * A forward ordered list (for .fini's) contains INITFIRST elements.  Move each
 * of these elements to the front of the list.
 */
static void
f_initfirst(Sort *sort, int end)
{
        Rt_map *tlmp;
        int     bgn, ifst, lifst = 0;

        for (bgn = 0; bgn < sort->s_initfirst; bgn++) {
                for (ifst = lifst; ifst <= end; ifst++) {
                        tlmp = sort->s_lmpa[ifst];

                        if (!(FLAGS(tlmp) & FLG_RT_INITFRST))
                                continue;

                        /*
                         * If the INITFIRST element is already at the end of
                         * the list leave it there.
                         */
                        if (ifst == end)
                                break;

                        /*
                         * Move the elements from after the INITFIRST element
                         * up to the back of the list, up one position.
                         */
                        (void) memmove(&sort->s_lmpa[ifst],
                            &sort->s_lmpa[ifst + 1],
                            ((end - ifst) * sizeof (Rt_map *)));

                        /*
                         * Insert INITFIRST element at the back of the list.
                         */
                        sort->s_lmpa[end--] = tlmp;
                        lifst = ifst;
                        break;
                }
        }
}

/*
 * Determine whether .init or .fini processing is required.
 */
static int
initorfini(Lm_list *lml, Rt_map *lmp, int flag, Sort *sort)
{
        if (flag & RT_SORT_REV) {
                /*
                 * For .init processing, only collect objects that have been
                 * relocated and haven't already been collected.
                 */
                if ((FLAGS(lmp) & (FLG_RT_RELOCED | FLG_RT_INITCLCT)) !=
                    FLG_RT_RELOCED)
                        return (0);

                if (dep_visit(lml, 0, 0, lmp, sort, flag) == -1)
                        return (1);

        } else if (!(flag & RT_SORT_DELETE) || (FLAGS(lmp) & FLG_RT_DELETE)) {
                /*
                 * Only collect objects that have had their .init collected,
                 * and haven't already been .fini collected.
                 */
                if (!((FLAGS(lmp) & (FLG_RT_INITCLCT | FLG_RT_FINICLCT)) ==
                    (FLG_RT_INITCLCT)))
                        return (0);

                if (dep_visit(lml, 0, 0, lmp, sort, flag) == -1)
                        return (1);
        }
        return (0);
}

/*
 * Sort the dependency
 */
Rt_map **
tsort(Rt_map *lmp, int num, int flag)
{
        Rt_map  *_lmp;
        Lm_list *lml = LIST(lmp);
        Word    init = lml->lm_flags & LML_FLG_TRC_INIT;
        Sort    sort = { 0 };
        size_t  size;

        if (num == 0)
                return (0);

        /*
         * Prior to tsorting any .init sections, insure that the `environ'
         * symbol is initialized for this link-map list.
         */
        if ((flag & RT_SORT_REV) && ((lml->lm_flags &
            (LML_FLG_TRC_ENABLE | LML_FLG_ENVIRON)) == 0))
                set_environ(lml);

        /*
         * 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.
         */
        sort.s_lmp = lmp;
        sort.s_num = num + 1;
        size = sort.s_num * sizeof (Rt_map *);
        if ((sort.s_lmpa = calloc(2, size)) == NULL)
                return ((Rt_map **)S_ERROR);
        sort.s_stack = (Rt_map **)((uintptr_t)sort.s_lmpa + size);

        /*
         * 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.
         */
        if (lml->lm_flags & LML_FLG_OBJREEVAL)
                _lmp = lml->lm_head;
        else
                _lmp = lmp;

        DBG_CALL(Dbg_file_bindings(_lmp, flag));
        lml->lm_flags &=
            ~(LML_FLG_OBJREEVAL | LML_FLG_OBJADDED | LML_FLG_OBJDELETED);

        /*
         * 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.
         */
        if ((lml->lm_flags & (LML_FLG_INTRPOSE | LML_FLG_INTRPOSETSORT)) ==
            LML_FLG_INTRPOSE) {
                Rt_map  *ilmp = _lmp;

                /*
                 * Unless the executable is tagged as an interposer, skip to
                 * the next object.
                 */
                if ((FLAGS(ilmp) & MSK_RT_INTPOSE) == 0)
                        ilmp = NEXT_RT_MAP(ilmp);

                for (; ilmp; ilmp = NEXT_RT_MAP(ilmp)) {
                        if ((FLAGS(ilmp) & MSK_RT_INTPOSE) == 0)
                                break;

                        if (initorfini(lml, ilmp, (flag | RT_SORT_INTPOSE),
                            &sort) != 0)
                                return ((Rt_map **)S_ERROR);
                }

                /*
                 * 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.
                 */
                lml->lm_flags |= LML_FLG_INTRPOSETSORT;
        }

        /*
         * Inspect any standard objects.
         */
        for (; _lmp; _lmp = NEXT_RT_MAP(_lmp)) {
                if (FLAGS(_lmp) & MSK_RT_INTPOSE)
                        continue;

                if (initorfini(lml, _lmp, flag, &sort) != 0)
                        return ((Rt_map **)S_ERROR);
        }

        /*
         * The dependencies have been collected such that they are appropriate
         * for an .init order, for .fini order reverse them.
         */
        if (flag & RT_SORT_FWD) {
                int     bgn = 0, end = sort.s_lndx - 1;

                while (bgn < end) {
                        Rt_map  *tlmp = sort.s_lmpa[end];

                        sort.s_lmpa[end] = sort.s_lmpa[bgn];
                        sort.s_lmpa[bgn] = tlmp;

                        bgn++, end--;
                }
        }

        /*
         * 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)
                        r_initfirst(&sort, sort.s_lndx - 1);
                else
                        f_initfirst(&sort, sort.s_lndx - 1);
        }

        /*
         * 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.
         */
        if (sort.s_queue) {
                Aliste idx;
                Rt_map  *lmp2;

                /*
                 * 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.
                 */
                for (APLIST_TRAVERSE(sort.s_queue, idx, lmp2))
                        IDX(lmp2) = 0;

                free(sort.s_queue);
        }

        if (sort.s_scc) {
                Aliste  idx;
                APlist  *alp;

                for (APLIST_TRAVERSE(sort.s_scc, idx, alp))
                        free(alp);
                free(sort.s_scc);
        }

        /*
         * The caller is responsible for freeing the sorted link-map list once
         * the associated .init/.fini's have been fired.
         */
        DBG_CALL(Dbg_file_bindings_done(lml));
        return (sort.s_lmpa);
}